Устройство для решения оптимизационных задач
Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства путем решения задач упаковки. Устройство содержит блок 1 назначения элементов множества упаковки, первый блок 2 памяти, блок 3 синхронизации, второй блок 4 памяти, накапливающий сумматор 5, блок 6 сравнения, счетчик 7, вход 8 начальной установки устройства , вход 9 пуска устройства, вход 10 задания емкости множества упаковки устройства, выход 11 номера текущего множества упаковки устройства , выход 12 признака перехода к очередному множеству упаковки устройства , информационный выход 13 устройстг ва и с первого по третий выходы 14- 16 блока 3 синхронна ацни. Перед лом работы устанавливают в исходное состояние блок 1, обнуляют счетчик 7 и ячейки блока 2 памяти, в блок 4 памяти заносят информацию об объемах упаковываемых предметов, по входу 10 задают объем (емкость) однотипных контейнеров, в которые производится упаковка. После запуска блок 3 синхронизации формирует на CBOJDC выходах последовательность сигналов, под управлением которой в блоке 2 памяти формируется план упаковки. 3 ил. а (Л С со со to Фиг1 at
СОЮЗ СОВЕТСНИХ
СОЭЮЛИСТИЧЕСНИХ
РЕСПУБЛИН (Д1) С 06 F 15/20
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ сО
К)
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
IlO ИЗОБРЕТЕНИЯМ И ОЗНРЫТИЯМ
flPH ГКНТ СССР
1 (21) 4453412/24 (22) 01.06.88 (46) 07.01.91. Бюл. М 1 (72) О.Г.Алексеев, С.A.Васильковский, В.А.Иалимов и Н.И.Ячкула (53) 681.333(088.8) (56) Авторское свидетельство СССР
Р 1298774, кл. С 06 С 7/122, 1985.
Авторское свидетельство СССР .lit 1524065, кл. С 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства путем решения задач упаковки. Устройство содержит блок 1 назначения элементов множества упаковки, первый блок 2 памяти, блок 3 синхронизации, второй
„„SU„„1619292 А f
2 блок 4 памяти, накапливаюций сумматор 5, блок 6 сравнения, счетчик 7, вход 8 начальной установки устройс1 ва, вход 9 пуска устройства, вход
10 задания емкости множества упаковки устройства, выход 11 номера.текуцего множества упаковки устройства, выход 12 .признака перехода к очередному множеству упаковки устройства, информационный выход 13 устройств. ва и с первого по третий выходы 14-, 16 блока 3 синхронизации. Перед нача лом работы устанавливают в исходное : состояние блок 1, обнуляют счетчик
7 и ячейки блока 2 памяти, в блок 4 памяти заносят информацию об объемах упаковываемых предметов, по входу:
10 задают объем (емкость) однотипных контейнеров, в которые производится упаковка. После запуска блок 3 син- хронизации формирует на своих выходах последовательность сигналов, под управлением которой в блоке 2 памяти формируется план упаковки. 3 ил.
1619292
Изобретение отноаится к вычислительной технике и может быть исполь- . зовано для решения задач линейного программирования.
Дель изобретения — расширение фун.5 кциональных возможностей путем решения задач упаковки.
На фиг. 1 предстявлена функциональная схема устройства,на фиг.2 — временная ди:грамма работы блока синхронизации; на фиг.3 — функциональная схема блока назначения элементов множества упаковки.
Устройство содержит блок 1 наз15 качения элементов множества упаковки, первый блок 2 памяти, блок 3 синхронизации, второй блок 4 памяти, накапливаюший умматор.5, блок
6 сравнения, счетчик 7, вход 8 начальной установки устройства, вход
9 пуска устроиства„ вход 10 задания емкости множества упаковки устройства, выход 1.1 номера текущего множества упаковки устройства, выход
12 признака перехода к очередному множеству упаковки устройства, информационный выход 13 устройства и с первого 14 по третий 16 выходы блока 3 синхронизации.
Блок 1 назначения элементов мно30 жества упаковки (фиг.3) содержит счетчики 17-19, переключатель 20 и дешифратор 21, причем вход 22 началь" ной установки бчока 1 подключен к установочным входам счетчиков 17-19, вход 23 признака продолжения назначения блока подключен к вычитающему входу счетчика 17, к первому управляющему входу переключателя 20 и к вычитающему входу счетчика 19, инфор" мационный выход которого подключен к первому информационному входу перекыочателя 20, информационньп выход когорого подключен к входу дешифратора 21, выход которого являет- 45 ся выходом 24 номера элемента блока 1, выход 25 признака отсутствия свободных элементов упаковки которого является выходом признака перехода через нуль счетчика 17, вход
26 признака отмены назначения блока;
1 подключен к суммирующему входу счетчика 19, к второму управляющему входу переключателя и к суммирующему входу счетчика 18, информационный выход которого подключен к второму информационному входу переключателя 20.
Устройство работает следующим образом.
Пусть требуется упаковать в кон . тейнеры фиксированного объема ll пред" метов (элементов упаковки) известных объемов. Перед началом работы на вход 8 начальной установки устройства подают импульс уровня логической единицы. При этом приводится в исходное состояние блок 1 и ус-, танавливается в "0" счетчик 7 и сумматор 5. Ячейки блока 2 памяти обнуляют. В блок 4 памяти по адресам, совпадаюцнм с номерами элементов упа- ковки, заносят объемы элементов, упорядоченные по невозрастанию.
Па вход пуска устройства подают импульс уровня логической единицы.
При этом блок 3 синхронизации формирует на своих выходах 14-16 последовательность сигналов, предусмотренную временной диаграммой его работы.
Потенциал уровня логической единицы появляется на выходе 15 блока 3. При .этом из блока 4 памяти считывается. .объем элемента, назначенного блоком
1 в первом такте работы, Через время, ;достаточное для чтения, блок 3 форми;. .рует потенциал уровня логической единиць на своем выходе 16. При этом
:сумматор 5 добавляют к накопленному ! значению очередного слагаемого (тем
,самым определяется общий объем всех .упакованных элементов). Через время, достаточное для выполнения операции сложения и сравнения чисел в блоке 6 ° ,блок 3 снимает потенциалы с выходов
15 и 16 и форимрует потенциал уров:ня логической единицы на выходе 14. При этом-блок 6 сравнения формирует
I на Одьом из своих выходов потенциал
1уровня логической единицы. В этом
1 ,случае, если значение на первом ин-! формационном входе (т.е. суммарный
,объем упакованных предметов} не больше значения на ворог. входе (т.е., ;объема контейнера), появляется сиг. нал на выхоце признака "Не больше"
;(T å., очередной элемент может быть ,упакован в текущий контейнер). При ,этом в блок 2 памяти по адресу, соответствующему номеру упаковываемого предмета, заносится номер текущего множества упаковки (т.e., номер контейнера, в который должен быть упакован предмет), блок 1 назначает очередной элемент упаковки.
9292
5 161
В противном случае сигнал появляется на выходе признака "Больше" (т.е., суммарный объем всех предметов оказался больше объема контейнера). При этом счетчик 7 увегвлчиваетсвое значение на единицу (выбирается новый контейнер) устанавливается в
"0" сумматор 5 (контейнер пуст) и блок 1 отменяет текущее назначение.
Через время, достаточное для выполнения указанных выше процессов, блок
3 снимает потенциал уровня логической единицы со своего выхода 14 и формирует потенциал уровня логической единицы на выходе 15. Далее работа устройства повторяется до тех пор, пока все элементы упаковки не будут назначены. При этом появляется потенциал уровня логической единицы на выходе признака отсутствия свободных элементов блока 1 и останавливает блок 3 синхронизации, Блок 1 назначения элементов множества упаковки работает следующим образом. Перед началом работы на вход 22 подают потенциал уровня логической единицы. При этом в счетчик
17 заносится информация о количестве упаковываемых элементов, в младший разряд счетчика 18 заносится единица (элемент с максимальньял объемом имеет номер один), в счетчик f9 sa- носится код, на единицу превышающий омер элемента упаковки с миннмальньм объемом, переключатель 20 устанавливается в такое состояние, нри котором на его информационньпЪ выход подключен второй информационный вход.
При поступлении на вход 23 импульса уровня логической единицы переключатель 20 подключает к своему информационному выходу первый информационный вход, счетчик 19 уменьшает значение своего кода на единицу (т.е., выбирается элемент упаковки со старшим номером), счетчик 17 уменьшает значение своего кода на единицу (обцее количество неупакованных элементов уменьшается на единицу). При поступлении импульса уровня логической единицы на вход 2б признака отмены назначения счетчик 18 увеличивает свое значение на единицу (выбирается следующий по объему элемент упаковки), переключатель 20 подключает свой информационный выход к второму информационному входу, счетчик 19 увеличивает свое значение на единицу (восстанавливается номер последнего эле15
30 ,35
55 мента, для которого произошла отмена назначения). Указанные операции выполняются до тех пор, пока значение, хранимое в счетчике 17, не достигнет нуля. При этом на выходе 25 блока появляется потенциал уровня логической единицы — признак отсутствия свободных (неупакованных) элементов.
Формула изобретения
Устройство для решения оптимизационных задач, содержащее блок назначения элементов множества упаковки, блок синхронизации, блок памяти и блок сравнения, причем вход началь- . ной установки устройства подключен к входу начальной установки блока назначения элементов множества упаковки, вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к входу опроса блока сранения, о т —, л и ч а ю ц е е с я тем, что, с целью расширения функциональных возможностей устройства за счет решения задач упаковки, в него введены накапливающий сумматор, счетчик и второй блок памяти, причем вход начальной установки устройства подключен к входу установки в "0" счетчика, выход которого является выходом номе ра текущего множества упаковки устройства и подключен к информационному входу первого блока памяти, выход которого является информационным выходом устройства, второй выход блока синхронизации подключен к входу признака чтения второго блока памяти, третий выход блока синхронизации подключен к тактовому входу накаплню ваюцего сумматора, выход которого подключен к первому информационному входу блока сравнения, выход признака Больше" которого является выходом признака перехода к очередному множеству упаковки устройства и подключен к суммируюцему входу счетчика, к входу установки в "0 накапливающего сумматора и к входу признака отмены назначения блока назначения элементов множества упаковки, выход номера элемента которого подключен к адресному входу первого блока памяти и и адресному входу второго блока памяти, выход которого подключен к входу слагаемого накапливающего сумматора, вход задания емкости множества упаковки устройства под(Ри. Г
ФР8. if
Составитель А.Мишин
Техред Л.Сердюкова Корректор M.Иароши
Редактор Н.Тупица
Заказ 49 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям н открытиям при ГКНТ СССР
1 13035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101
7 1619292 8 ключен к второму информационному вхо; ния назначения блока назначения эледу блока сравнения, выход признака ментов множества упаковки, выход при "Не больше" которого подключен к .знака отсутствия свободных элементов
: входу признака записи первого блока которого подключен к входу останова: .памяти и к входу признака продолже- блока синхронизации.
