Устройство для решения оптимизационных задач

)5 С 0 5/2 ГОСУД ПО ИЗО ОПИСАНИЕ ИЗОБРЕТ.У 15 о СССР 1985.СССР 1988. идетельст 6 С 7/12 тельство 6 Р 15/2 тороп АРСТВЕННЫЙ КОМИТЕТ ЕТЕНИЯМ И ОЗНРЫТИЯМ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВ(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ОППЗАЦИОНННХ ЗАДАЧ(57) Изобретение относится к вычислительной технике и может быть исползовано для решения задач линейногопрограммирования. Целью изобретенияявляется расширение функциональныхвозможностей устройства путем решения задач упаковки. Устройство содержит блок 1 назначения элементовмножества упаковки, первый блок 2памяти, блок 3 синхронизации, в 2 блок 4 памяти, накапливаюций сумматор 5, блок 6 сравнения, счетчик 7, вход 8 начальной установки устройства, вход 9 пуска устройства, вход 10 задания емкости множества упаковки устройства, выход 11 номера текуцего множества упаковки устройства, выход 12 .признака перехода к очередному множеству упаковки устройства, инФормационный выход 13 устройств. ва и с первого по третий выходы 14-, 16 блока 3 синхронизации. Перед нача;. лом работы устанавливают в исходное : состояние блок 1, обнуляют счетчик 7 и ячейки блока 2 памяти, в блок 4 памяти заносят информацию об объемах а упаковываемых предметов, по входу 10 еедеыт объем (емкость) однотипных Щ контейнеров, в которые производится упаковка. После запуска блок 3 син-хронизации формирует на своих выходах последовательность сигналов, под управлением которой в блоке 2 памяти Формируется план упаковки. 3 ил.Изобретение отноаится к вычислительной технике и может быть использовано для решения задач линейного программирования.1Дель изобретения - расширение Фун.- 5 кциональных возможностей путем решения задач упаковки.На фиг.1 предстявлена функциональная схема устройства,на фиг.2 - временная ди грамма работы блока синхронизации; на фиг.З - функциональная схема блока назначения элементов множества упаковки.Устройство содержит блок 1 наз 15 качения элементов множества упаковки первый блок 2 памяти, блок 3 синхронизации, второй блок 4 памяти, накапливаюший умматор.5, блок 6 сравнения, счетчик 7, вход 8 начальной установки устройства, вход 9 пуска устроиства вход 10 задания емкости множества упаковки устройства, выход 1.1 номера текущего множества упаковки устройства, выход 12 признака перехода к очередному множеству упаковки устройства, инФормационный выход 13 устройства и с первого 14 по третий 16 выходы блока 3 синхронизации.Блок 1 назначения элементов мно 30 жества упаковки (Фиг.З) содержит счетчики 17-19, переключатель 20 и дешифратор 21, причем вход 22 началь" ной установки бчока 1 подключен к установочным входам счетчиков 17-19, вход 23 признака продолжения назначения блока подключен к вычитающему входу счетчика 17, к первому управляющему входу переключателя 20 и к вычитающему входу счетчика 19, инфор" мационный выход которого подключен к первому информационному входу перекыочателя 20, информационньп выход когорого подключен к входу дешифратора 21, выход которого являет ся выходом 24 номера элемента блока 1, выход 25 признака отсутствия свободных элементов упаковки которого является выходом признака перехода через нуль счетчика 17, вход 26 признака отмены назначения блока;1 подключен к суммирующему входу счетчика 19, к второму управляющемувходу переключателя и к суммирующему входу счетчика 18, информационный выход которого подключен к второму информационному входу переключателя 20. Устройство работает следующим образом.Пусть требуется упаковать в кон тейнеры Фиксированного объема и пред" метов (элементов упаковки) известных объемов. Перед началом работы на вход 8 начальной установки устройства подают импульс уровня логической единицы. При этом приводится в исходное состояние блок 1 и ус-, танавливается в "0" счетчик 7 и сумматор 5. Ячейкиблока 2 памяти обнуляют. В блок 4 памяти по адресам, совпадаюцим с номерами элементов упа- ковки, заносят объемы элементов, упорядоченные по невозрастанию.На вход пуска устройства подают импульс уровня логической единицы. При этом блок 3 синхронизации Формирует на своих выходах 14-16 последовательность сигналов, предусмотренную временной диаграммой его работы. Потенциал уровня логической единицы появляется на выходе 15 блока 3. При этом из блока 4 памяти считывается. объем элемента, назначенного блоком 1 в первом такте работы, Через время, достаточное для чтения, блок 3 Форми;. ,рует потенциал уровня логической ,"единицы на своем выходе 16. При этом :сумматор 5 добавляют к накопленномузначению очередного слагаемого (тем ,самым Определяется общий объем всеХ упакованных элементов). Через время, достаточное для выполнения операции сложения и сравнения чисел в блоке 6,блок 3 снимает потенциалы с выходов 15 и 16 и форимрует потенциал уровня логической единицы на выходе 14. При этом. блок 6 сравнения Формирует на Одьом из своих ВыхОдОВ пОтенциал 1 уровня логической единицы, В этом ,случае, если значение на первом инФормационном входе (т.е. суммарный объем упакованных предметов) не больше значения на в ороь, входе (т.е., ;объема контейнера), появляется сиг.- нал на выхоце признака "Не больше" (т.е., очередной элемент может бьггь ,упакован в текущий контейнер). При ,этом в блок 2 памяти по адресу, соответствующему номеру упаковываемого предмета, заносится номер текущего множества упаковки (т.е., номер контейнера, в который должен быть упакован предмет), блок 1 назначает очередной элемент упаковки.9292 5 161В противном случае сигнал появляется на выходе признака "Больше"(т.е., суммарный объем всех предметов оказался больше объема контейнера). При этом счетчик 7 увегжчиваетсвое значение на единицу (выбираетсяновый контейнер)устанавливается в"О" сумматор 5 (контейнер пуст) иблок 1 отменяет текущее назначение.Через время, достаточное для выполнения указанных выше процессов, блок3 снимает потенциал уровня логической единицы со своего выхода 14 иформирует потенциал уровня логической единицы на выходе 15. Далее работа устройства повторяется до тех пор,пока все элементы упаковки не будутназначены. При этом появляется потенциал уровня логической единицы навыходе признака отсутствия свободных элементов блока 1 и останавливает блок Э синхронизации,Блок 1 назначения элементов множества упаковки работает следующимобразом. Перед началом работы навход 22 подают потенциал уровня логической единицы. При этом в счетчик17 заносится информация о количестве упаковываемых элементов, в младшийразряд счетчика 18 заносится единица (элемент с максимальнык объемомимеет номер один), в счетчик 19 за-носится код, на единицу превышающийомер элемента упаковки с миннмальнья объемом, переключатель 20 устанавливается в такое состояние, нрикотором на его информационньй выходподключен второй информационный вход.При поступлении на вход 23 импульсауровня логической единицы переключатель 20 подключает к своему информационному выходу первый информационныйвход, счетчик 19 уменьшает значениесвоего кода на единицу (т.е выбирается элемент упаковки со старшимномером), счетчик 17 уменьшает значение своего кода на единицу (обцееколичество неупакованных элементовуменьшается на единицу). При поступлении импульса уровня логической единицы на вход 2 б признака отмены назначения счетчик 18 увеличивает своезначение на единицу (выбирается следующий по объему элемент упаковки),переключатель 20 подключает свой информационный выход к второму информационному входу, счетчик 19 увеличивает свое значение на единицу (восстанавливается номер последнего эле-. 15 20 25 ЗО .35 40 45 50 55 мента, для которого произошла отменаназначения), Указанные операции выполняются до тех пор, пока значение,хранимое в счетчике 17, не достигнетнуля. При этом на выходе 25 блокапоявляется потенциал уровня логической единицы - признак отсутствия свободных (неупакованных) элементов. Формула изобретения Устройство для решения оптимизационных задач, содержащее блок назначения элементов множества упаковки, блок синхронизации, блок памяти и блок сравнения, причем вход началь- . ной установки устройства подключен к входу начальной установки блока назначения элементов множества упаковки, вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к входу опроса блока сранения, о т - , л и ч а ю ц е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет решения задач упаковки, в него введены накапливающий сумматор, счетчик и второй блок памяти, причем вход начальной установки устройства подключен к входу установки в "О" счетчика, выход которого является выходом номе;. ра текущего множества упаковки устройства и подключен к информационному входу первого блока памяти, выход которого является информационным выходом устройства, второй выход блока синхронизации подключен к входу признака чтения второго блока памяти, третий выход блока синхронизации подключен к тактовому входу накаплив вающего сумматора, выход которого подключен к первому информационному входу блока сравнения, выход признака Больше" которого является выходом признака перехода к очередному множеству упаковки устройства и подключен к суммирчацему входу счетчика, к входу установки в "О накапливающего сумматора и к входу признака отмены назначения блока назначения элементов множества упаковки, выход номера элемента которого подключен к адресному входу первого блока памяти и к адресному входу второго блока памяти, выход которого подключен к входу слагаемого накапливающего сумматора, вход задания емкости множества упаковки устройства под%СоставительА. Мишинтор Н.Тупица Техред Л.Сердюкова Корректор МЛароши аз 49 Подписное 1 ПИ Государственного комитета по изобретениям и открытиям 1 13035, Москва, Ж-З 5, Раушская наб., д. 4/5 КНТ СССР твенно-издательский комбинат Патент , г.11 гарина, 1 О од,Произв 7 1619292ключен к второму инФормационному вхо; ния назначения блока назначения эледу блока сравнения, выход признакаментов множества упаковки, выход при. "Не больше" которого подключен к . знака отсутствия свободных элементов входу признака записи первого блока которого подключен к входу останова: .памяти и к входу признака продолже- блока синхронизации.5