Устройство для решения оптимизационных задач Советский патент 1991 года по МПК G06F15/20 

Изобретешие относится к вычисли- тельной технике и может быть исполь- зовано для решения задач линейного программирования„

Цепь изобретения - расширение функциональных возможностей путем решения задач упаковкио

На фиг. 1 представлена функциональна схема устройства,на фиг. 2 - временная диаграмма работы блока синхронизации; на фиг.З - функциональная схема блока назначения элементов множества упаковки.

. Устройство содержит блок 1 назначения элементов множества упаковки, первый блок 2 памяти, блок 3 синхронизации, второй блок 4 памяти, накапливающий сумматор 5, блок 6 сравнения, счетчик 7, вход 8 начальной установки устройства, вход 9 пуска устройства, вход 10 задания емкости множества упаковки устройства, выход 11 номера текущего множества упаковки устройства, выход 12 признака перехода к очередному множеству упаковки устройства, информационный выход 13 устройства и с первого 14 по третий 16 выходы блока 3 синхронизации.

Блок 1 назначения элементов мно жества упаковки (фиг.З) содержит счетчики 17-19, переключатель 20 и дешифратор 21, причем вход 22 начальной установки б пока 1 подключен к установочным входам счетчиков 17-19, вход 23 признака продолжения назначения блока подключен к вычитающему входу счетчика 17, к первому управляющему входу переключателя 20 и к вычитающему входу счетчика 19, информационный выход которого подключен к петэвому информационному входу пе- реюлочателя 20, информационный выход которого подключен к входу дешифратора 21, выход которого является выходом 24 номера элемента бло- ка 1, выход 25 признака отсутствия свободных элементов упаковки которого является выходом признака перехода через нуль счетчика 17, вход 26 признака отмены назначения блока 1 подключен к суммирующему входу счетчика 19, к второму управляющему входу переключателя и к суммирующему входу счетчика 18, информационный выход которого подключен к второму информационному входу переключателя 20.

,-

5

0

n

5

5 0

0

0

5

Устройство работает следующим образом.

Пуст, требуется упаковать в кон тейнеры фиксированного объема п пред1 метов (элементов упаковки) известных объемов. Перед началом работы на вход 8 начальной установки устройства подают импульс уровня логической единицы. При этом приводится в исходное состояние блок 1 и устанавливается в О счетчик 7 и сумматор 5. Ячейки блока 2 памяти обнуляют. В блок 4 памяти по адресам, совпадающим с номерами элементов упаковки, ЗсШосят объемы элементов, упорядоченные по невозрастанию. I

На вход пуска устройства подают импульс уровня логической единицы. При этом блок 3 синхронизации формирует на своих выходах 14-16 последовательность сигналов, предусмотренную временной диаграммой его работы,/ Потенциал уровня логической единицы появляется на выходе 15 блока 3. При этом из блока 4 памяти считывается, объем элемента, назначенного блоком 1 в первом такте работы. Через время, достаточное для чтения, блок 3 форми- рует потенциал уровня логической единицы на своем выходе 16„ При этом сумматор 5 добавляют к накопленному значению очередного слагаемого (тем самым определяется общий объем всех упакованных элементов). Через время, достаточное для выполнения операций сложения и сравнения чисел з блоке 6, блок 3 снимает потенциалы с выходов 15 и 16 и форимрует потенциал уровня логической единицы на выходе 14„ При этом блок 6 сравнения формирует iна одном из своих выходов потенциал iуровня логической единицы. В этом случае, если значение на первом информационном входе (т„е. суммарный объем упакованных предметов) не больше значения на входе (т.е„, , объема контейнера), появляется нал на выходе признака Не больше (т.е., очередной элемент может1 быть ,упакован в текущий контейнер). При ,этом в блок 2 памяти по адресу, соответствующему номеру упаковываемого предмета, заносится номер текущего множества упаковки (т.е., номер контейнера, в который должен быть упакован предмет), блок 1 назначает очередной элемент упаковки.

В противном случае сигнал появляется на выходе признака Больше (т.е., суммарный объем всех предметов оказался больше объема контейнера) . При этом счетчик 7 увеличивает- свое значение на единицу (выбирается новый контейнер), устанавливается в О сумматор 5 (контейнер пуст) и блок 1 отменяет текущее назначение0 Через время, достаточное для выполнения указанных выше процессов, блок 3 снимает потенциал уровня логической единицы со своего выхода 14 и формирует потенциал уровня логической единицы на выходе 15. Далее работа устройства повторяется до тех пор пока все элементы упаковки не будут назначены При этом появляется потенциал уровня логической единицы на выходе признака отсутствия свободных элементов блока 1 и останавливает блок 3 синхронизации.

Блок 1 назначения элементов множества упаковки работает следующим образом. Перед началом работы на вход 22 подают потенциал уровня логической единицы. При этом в счетчик 17 заносится информация о количестве упаковываемых элементов, в младший разряд счетчшса 18 заносится единица (элемент с максимальным объемом имеет номер один), в счетчик 19 за- .носится код, на единицу превышающий (номер элемента упаковки с минимальным объемом, переключатель 20 устанавливается в такое состояние, при котором на его информационный выход подключен второй информационный вход При поступлении на вход 23 импульса уровня логической единицы переключатель 20 подключает к своему информационному выходу первый информационный вход, счетчик 19 уменьшает значение своего кода на единицу (т.е., выбирается элемент упаковки со старшим номером), счетчик 17 уменьшает значение Своего кода на единицу (обцее количество неупакованных элементов уменьшается на единицу). При поступлении импульса уровня логической единицы на вход 26 признака отмены назначения счетчик 18 увеличивает свое значение на единицу (выбирается следующий по объему элемент упаковки)s переключатель 20 подключает свой информационный выход к второму информационному входу, счетчик 19 увеличивает свое значение на единицу (восстанавливается номер последнего эле

5

0

5

0

5

0

5

0

5

мента, для которого произошла отмена назначения). Указанные операции выполняются до тех пор, пока значение, хранимое в счетчике 17, не достигнет нуля. При этом на выходе 25 блока 1 появляется потенциал уровня логической единицы - признак отсутствия свободных (неупакованных) элементов.

Формула изобретения

Устройство для решения оптимизационных задач, содержащее блок назначения элементов множества упаковки, блок синхронизации, блок памяти и блок сравнения, причем вход начальной установки устройства подключен к входу начальной установки блока назначения элементов множества упаковки, вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к входу опроса блока сранения, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет решения задач упаковки, в него введены накапливающий сумматор, счетчик и второй блок памяти, причем вход начальной установки устройства подключен к входу установки в О счетчика, выход которого является выходом номег ра текущего множества упаковки устройства и подключен к информационному входу первого блока памяти, выход которого является информационным выходом устройства, второй выход блока синхронизации подключен к входу признака чтения второго блока памяти, третий выход блока синхронизации подключен к тактовому входу накагапда вающего сумматора, выход которого подключен к первому информационному входу блока сравнения, выход признака Больые которого является выходом признака перехода к очередному множеству упаковки устройства и подключен к суммирующему входу счетчика, к входу установки в О накапливающего сумматора и к входу признака отмены назначения блока назначения элементов множества упаковки, выход номера элемента которого подключен к адресному входу первого блока памяти и к адресному входу второго блока памяти, выход которого подключен к входу слагаемого накапливающего сумматора, вход задания емкости множества упаковки устройства под716192928

ключей к второму информационному вхогния назначения блока назначения эледу блока сравнения, выход признакаментов множества упаковки, выход больше которого подключен кзнака отсутствия свободных элементов

входу признака записи первого блокакоторого подключен к входу останова

памяти и к входу признака продолже-блока синхронизация.

Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства путем решения задач упаковки. Устройство содержит блок 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