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

(5)5 6 АНИЕ ИЗОБРЕТЕН ОП ОРСКОМ И ЕТЕЛЬСТ ГОСУДАРСТВЕННЫИ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СССРФ 1263094, кл, 6 06 6 7/122, 1983,Авторское свидетельство СССР1 Ф 1559354, кл, 6 06 Е 15/20, 1988, .(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧОПТИМИЗАЦИИ(57) Изобретение относится к вычислительной технике и может быть использованодля решения задач оптимизации плана перевозок в транспортной сети, Целью изобретения является расширениефункциональных возможностей устройстваэа счет решения транспортной задачи линейного программирования. Устройство со. держит блок 1 задания матрицы Изобретение относится к вычислительной технике и может быть использовано для решения задачи оптимизации плана перевозок в транспортной сети.Целью изобретения является расшире. ние функциональных воэможностей устройства за счет решения транспортной задачи линейного программирования.На фиг, 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 - функциональная схема блока задания матрицы транспортных затрат; на фиг. 3 - функциональная схема модели . транспортной сети; на фиг. 4 - функциональная схема многоканального счетчика. транспортных затрат. модель 2 транспорт-. ной сети, блок 3 синхронизации, блок 4 приоритета, многоканальный счетчик 5, вход б начальной установки устройства, вход 7 пуска устройства и выходы 8 оптимального плана перевозок из пунктов отправления в пункты назначения, Перед началом работы устанавливают в исходное состояние счетчик 5. блок 1 и модель 2. В блок 1 заносят информацию о транспортных затратах при перевозках между пунктами отправления и пунктами назначения. В модель 2 заносят информацию о запасах пунктов отправления и потребностях пунктов назначения. После подачи на вход 7 пуска устройства потенциала уровня логической единицы блок 3 синхронизации формирует на своем 3 выходе последовательность импульсов, под управлением которой на выходах 8 устройства формируется оптимальный план переУстройство содержит блок 1 задания матрицы транспортных затрат, модель 2 транспортной сети, блок 3 синхронизации, блок 4 приоритета, многоканальный счетчик 5, вход 6 начальной установки устройства, вход 7 пуска устройства Ь выходы 8 оптимального плана перевозок иэ пунктов отправления в пункты назн 1 ения,Блок 1 задания матрицы транспортных затрат содержит матрицу из ПО х ПН триггеров 9. где ПО - количество пунктов отправления, а ПН - количество пунктов назначения в транспортной сети, матрицу из ПОхПН элементов ИЛИ-НЕ 10, матрицу из ПО х ПН счетчиков 11, матрицу из10 20 25 30 К-у входу М-го элемента ИЛИ 20 группы и к. 40 45 50 ПО х ПН элементов И 12, группу из ПН элементов ИЛИ 13, элемент ИЛИ 14 и элемент И 15, причем вход 16 блокировки элементов К-го столбца блока 1 (К=1.,ПН) подключен к первым входам всех элементов ИЛИ-НЕ 10 К-го столбца матрицы, вход 17 блокировки элементов М-й строки блока 1 подключен к вторым входам всех элементов ИЛИ-НЕ 10 М-й строки матрицы(М 1,.ПО), выход (К,М)-го элемента ИЛИНЕ 10 матрицы подключен к первому входу (К,М)-го элемента И 12 и к входу разрешения счета (К,М)-го счетчика 11 матрицы, выход признака переполнения которого подключен к входу установки в "1" (К,М)-го триггера 9 матрицы, выход которого подключен к второму входу (К,М) го элемента И 12 матрицы, выход которого подключен к М-у входу К-го элемента ИЛИ группы, выход которого является выходом признака принадлежности (К,М)-го элемента множеству минимальных и подключен к К-у входу элемента ИЛИ 14, выход которого подключен к первому входу элемента И 15, выход которого подключЕв к вычитающим входам всех счетчиков 11 матрицы, вход 18 начальной установки блока 1 подключен к входам установки в "0" всех триггеров 9 матрицы, тактовый вход 19 блока 1 подключен к второму входу элемента И 15. Модель 2 транспортной сети содержит группу из ПО элементов ИЛИ 20, группу из ПО счетчиков 21, группу из ПО триггеров 22, группу из ПН элементов ИЛИ 23, группу из ПН счетчиков 24, группу из ПН триггеров 25, два элемента И 2627 и элемент ИЛИ 28, причем вход 29 разрешения моделирования перевозок из М-го пункта отправления в К-й пункт назначения блока 2 подключен к М-у входу К-го элемента ИЛИ 23 группы, выход которого подключен к входу разрешения счета К-го счетчика 24 группы, выход признака переполйения которого подключен к входу установки в "1" К-го триггера 25 группы, выход которого является выходом 30 признака удовлетворения потребностей К-го пункта назначения блока 2 и подключен к К-у входу элемента И. 27, выход которого подключен к первому входу элемента ИЛИ 28, выход М-го элемента ИЛИ 20 подключен к входу разрешения счета М-го счетчика 21 группы, выход признака переполнения которого подключен к входу установки в "1" М-го триггера 22 группы, прямой выход которого является выходом 31 признака исчерпания запасов М-го пункта отправления и подключен к М-у входу элемента И 26, выход которого подключен к второму входу элемента ИЛИ 28, выход которого является выходом 32 признака исчерпания запасоввсех пунктов отправления и/или потребностей всех пунктов назначения модели 2,вход 33 начальной установки которой подключен к входам установки в "0" всех триггеров 22 и 25 групп, тактовый вход 34модели 2 подключен к вычитающим входамвсех счетчиков 21 и 24 групп,Многоканальный счетчик 5 содержитматрицу из ПО х ПН счетчиков 35, причемвход 36 разрешения работы (К,М)-го каналасчетчика 5 подключен к входу разрешениясчета (К,М)-го счетчика 35 матрицы, информационный выход которого является инфор 5 мационным выходом 37 (К,М)-го каналамногоканального счетчика 5, вход 38 начальной установки и тактовый вход 39 которогоподключены к входам установки в "0" и суммирующим входам соответствЕнно всехсчетчиков 35 матрицы,Устройство работает следующим образом,Перед началом работы на вход 6 начальной установки подают импульс уровня логической единицы, При этом устанавливаютсяв "0" все каналы счетчика 5 и приводятся висходное состояние блок 1 задания матрицы транспортных затрат и модель 2 транспортной сети, В блок 1 заносятинформацию о транспортных затратах приперевозках из М-го пункта отправления вК-й пункт назначения, В модель 2 заносятинформацию о запасах пунктов отправления и потребностях пунктов назначения,5 На вход 7 пуска устройства подают импульс уровня логической единицы. При этомблок 3 синхронизации формирует на своемвыходе последовательность импульсовуровня логической единицы. При поступлении на его вход тактовых импульсов блок 1выбирает минимальный элемент матрицытранспортных затрат и формирует на соответствующем ему выходе потенциал (или потенциалы, если имеется несколько равныхэлементов) уровня логической единицы. Приэтом блок 5 выбирает направление перевозок, обладающее наибольшим приоритетом. При поступлении на ее вход тактовыхимпульсов модель 2 моделирует перевозкипо разрешенному направлению, После того,как запасы пункта отправления и/или потребности пункта назначения будут исчерпаны, на соответствующих выходах модели2 появятся потенциалы уровня логической5 единицы. При этом блок 1 исключает изанализа (заблокирует) те строки (столбцы)матрицы транспортных затрат, которые соответствуют направлениям перевозок, мо, делирование которых окончено. Работаустройства п родоп: кается аналогично до техпор, пока не будут исчерпаны запасы всех пунктов отправления и/или потребностивсех пунктов назначения. При этом блок 3 прекращает формирование импульсов насвоем выходе и информация на выходе многоканального счетчика 5 соответствует оптимальному плану перевозок из М-го пункта отправления в К-й пункт назначения.Блок 1 задания матрицы транспортных затрат работает следующим образам,Перед началам работы на вход 18 начальной установки подают импульс уровня логической единицы, При этом устанавливаются в "О" все триггеры 9 матрицы. В счетчики 11 заносят информацию о транспортных затратах при перевозках из М-го пункта отправления в К-й пункт назначения. При поступлении на тактовый вход 19 импульсов уровня логической единицы счетчика 11 последовательно уменьшают содержащиеся в них значения на единицу, При переходе через ноль счетчик 11 устанавливается в "1" соответствующий ему триггер 9, При этом поступление на входы счетчиков 11 импульсов прекращается, При поступлении на входы 16, 17 потенциалов уровня логической единицы счет продолжается,Модель 2 транспортной сети ряботает следующим образом.Перед началом работы на вход 33.подают импульс уровня логической единицы, При этом устанавливаются в "0" все триггеры 22 и 25, В счетчики 21 и 24 заносят информацию о запасах пунктов отправления и потребностях пунктов назначения соответственно. При поступлении на вход 34 импульсовуровня логической единицы счетчика 21, 24, работа которых разрешена наличием потенциала уровня логической единицы с выходов соответствующих им элементов ИЛИ 20, 23, уменьшают на единицу (по каждому импульсу) содержащиеся в них значения (тем самым моделируется перевозка иэ М-го пункта отправления в К-й пункт назначения). При переходе счетчиков 21, 24 через ноль устанавливаются в "1" соответствующие им триггеры 22; 25, При этом на выходах 30, 31 формируотся признаки удовлетворения потребностей и/или исчерпания запасов. После того как все триггеры 22 и/или 25 буду установлены в "1", появится потенциал уровня логической едиещы на выходе 32 - признак исчерпания запасов всех пунктов отправления10 15 30 45 разрешения работы К,М)-го канала многоканального счетчика, (К,М)-й информационный выход которого является выходом 50 ния модели транспортной сети подключен к входу останова блока синхронизации.5 б. 20 25 и/или потребностей всех пунктов назначения,Формул а изобретенияУстройство для решения задач оптимизации, содержащее блок задания матрицы транспортных затрат, модель транспортной сети, многоканальный счетчик и блок синхронизации, вход пуска которого является входом пуска устройства, вход начальной установки которого подключен к входу установки в "0" многоканального счетчика и к входам начальной установки модели транспортной сети и блока задания матрицы транспортных затрат, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет решения транспортной задачи линейного программирования, в него введен блок приоритета, причем выход блока синхронизации подключен к тактовым входам многоканального счетчика, блока задания матрицы транспортных затрат и к тактовому входу модели транспортной сети, выход признака исчерпания запасов М-го пункта отправления которой (М=1,.,ПО, где ПО -количество пунктов отправления в трансспортной сети) подключен к входу признака блокировки элементов М-й строки матрицы блока задания матрицы транспортных затрат, выход признака удовлетворения патребностей К-го пункта назначения модели транспортной сети (К=1ПН, где ПН - количество пунктов назначения в транспортной сети) подключен к входу. признака блокировки элементов К-го столбца блока задания матрицы транспортных затрат, выход признака принадлежности (К,М)-го элемента множеству минимальных которого подключен к (К,М)-му входу блока приоритета, выход признака выбооа (К,М)й поэиции которого подключен к входу разрешения моделирования (К,М)-й перевозки модели транспортной сети и к входу объема оптимальноо плана перевозок из М-го пункта отправления в К-й пункт назначения устройства, выход признака исчерпания запасов всех, пунктов отправления и/или потребностей всех пунктов назначе1649562 Збюал УгуФиг 4 ЪСоставитель А.МишинФельдман Техред М,Моргентал Корректор О,Цикле Редактор зводственно-издательский комбинат "Патент", г. ужгород, ул. Гагарина, 101 каэ 1870 Тираж 419ВНИИПИ Государственного комитета оо иэоб113035, Москва, Ж, РауЗд3 Подписноетениям и открытиям при ГКНТ СС кая наб 4/5