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

 

Изобретение относится к вычислительной технике и может быть использовано для решения задач оптимизации плана перевозок в транспортной сети. Целью изобретения является расширение функциональных возможностей устройства за счет решения транспортной задачи линейного программирования. Устройство содержит блок 1 задания матрицы транспортных затрат, модель 2 транспортной сети, блок 3 синхронизации, блок 4 приоритета , многоканальный счетчик 5, вход б начальной установки устройства, вход 7 пуска устройства и выходы 8 оптимального плана перевозок из пунктов отправления в пункты назначения. Перед началом работы устанавливают в исходное состояние счетчик 5. блок 1 и модель 2. В блок 1 заносят информацию о транспортных затратах при перевозках между пунктами отправления и пунктами назначения. В модель 2 заносят информацию о запасах пунктов отправления и потребностях пунктов назначения. После подачи на вход 7 пуска устройства потенциала уровня логической единицы блок 3 синхронизации формирует на своем выходе последовательность импульсов, под управлением которой на выходах 8 устройства формируется оптимальный план перевозок . 4 ил. fe

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

/ (я)э G (% F 15/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4443234/24 (22) 06.05.88 (46) 15.05.91. Бюл. гв 18 (72) О.Г.Алексеев, С.А.Васильковский, А.H.Мардас и Н.И.Ячкула (53) 681.333 (088.8) (56) Авторское свидетельство СССР

5h 1263094, кл. G 06 6 7/122, 1983.

Авторское свидетельство СССР

1Ф 1559354, кл. G 06 F 15/20, 1988..(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ОПТИМИЗАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач оптимизации плана перевозок в транспортной сети, Целью изобретения является расширение функциональных возможностей устройства эа счет решения транспортной задачи линейного программирования. Устройство содержит блок 1 задания матрицы

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

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

На фиг, 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 — функциональная схема блока задания матрицы транспортных затрат; на фиг. 3 — функциональная схема модели . транспортной сети; на фиг. 4 — функциональная схема многоканального счетчика.. Ж, 1649562 Аl транспортных затрат. модель 2 транспорт= ной сети, блок 3 синхронизации, блок 4 приоритета, многоканальный счетчик 5, вход б начальной установки устройства, вход 7 пуска устройства и выходы 8 оптимального плана перевозок из пунктов отправления в пункты назначения, Перед началом работы устанавливают в исходное состояние счетчик 5. блок 1 и модель 2. В блок 1 заносят информацию о транспортных затратах при перевозках между пунктами отправления и пунктами назначения. В модель 2 заносят информацию о запасах пунктов отправления и потребностях пунктов назначения. После подачи на вход 7 пуска устройства потенциала уровня логической единицы блок 3 синхронизации формирует на своем выходе последовательность импульсов, под управлением которой на выходах 8 устройства формируется оптимальный план перевозок. 4 ил.

Устройство содержит блок 1 задания матрицы транспортных затрат, модель 2 транспортной сети, блок 3 синхронизации, блок 4 приоритета, многоканальный счетчик

5, вход 6 начальной установки устройства, вход 7 пуска устройства 4 выходы 8 оптимального плана перевозок иэ пунктов отправления в пункты назначения.

Блок 1 задания матрицы транспортных затрат содержит матрицу из ПО х ПН триггеров 9. где ПΠ— количество пунктов отправления, а ПН вЂ” количество пунктов назначения в транспортной сети, матрицу из ПОхПН элементов ИЛИ-НЕ 10, матри цу из flO х ПН счетчиков 11, матрицу из

1649562

20

К-у входу M-ro элемента ИЛИ 20 группы и к. 40

50

ПО х ПН элементов И 12, группу из ПН элементов ИЛИ 13, элемент ИЛИ 14 и элемент И 15, причем вход 16 блокировки элементов К-го столбца блока 1 (К=1,...tlH) подключен к первым входам всех элементов

ИЛИ-НЕ 10 К-го столбца матрицы, вход 17 блокировки элементов М-й строки блока 1 подключен к вторым входам всех элементов ИЛИ-НЕ 10 M-й строки матрицы (M 1,...ÏO), выход (К,М)-го элемента ИЛИWE 10 матрицы подключен к первому входу (К,М)-го элемента И 12 и к входу разрешения счета (К,М)-го счетчика 11 матрицы, выход признака переполнения которого подключен к входу установки в "1" (К,M)-го триггера

9 матрицы, выход которого подключен к второму входу (К,M) го элемента И 12 матрицы, выход которого подключен к M-у входу

К-ro элемента ИЛИ группы, выход которого является выходом признака принадлежности (К,M)-ro элемента множеству минимальных и подключен к К-у входу элемента ИЛИ

14, выход которого подключен к первому входу элемента И 15, выход которого подключЕн к вычитающим входам всех счетчиков 11 матрицы, вход 18 начальной установки блока 1 подключен к входам установки в "0" всех триггеров 9 матрицы, тактовый вход 19 блока 1 подключен к второму входу элемента И 15.

Модель 2 транспортной сети содержит группу из ПО элементов ИЛИ 20, группу из

AG счетчиков 21, группу из ПО триггеров 22, группу из ПН элементов ИЛИ 23, группу из

ПН счетчиков 24, группу из ПН триггеров 25, два элемента И 26,27 и элемент ИЛИ 28, причем вход 29 разрешения моделирования перевозок из M-го пункта отправления в

К-й пункт назначения блока 2 подключен к

M-у входу К-го элемента ИЛИ 23 группы, выход которого подключен к входу разрешения счета К-го счетчика 24 группы, выход признака переполйения которого подключен к входу установки в "1" К-го триггера 25 группы, выход которого является выходом

30 признака удовлетворения потребностей

К-го пункта назначения блока 2 и подключен к К-у входу элемента И. 27, выход которого подключен к первому входу элемента ИЛИ

28, выход M-го элемента ИЛИ 20 подключен к входу разрешения счета M-ro счетчика 21 группы, выход признака переполнения которого подключен к входу установки в "1"

M-го триггера 22 группы, прямой выход которого является выходом 31 признака исчерпания запасов M-го пункта отправления и подключен к M-у входу элемента И 26, выход которого подключен к второму входу элемента ИЛИ 28, выход которого является выходом 32 признака исчерпания запасов всех пунктов отправления и/или потребностей всех пунктов назначения модели 2, вход 33 начальной установки которой подключен к входам установки в "0" всех триггеров 22 и 25 групп, тактовый вход 34 модели 2 подключен к вычитающим входам всех счетчиков 21 и 24 групп.

Многоканальный счетчик 5 содержит матрицу из ПО х ПН счетчиков 35, причем вход 36 разрешения работы (К,M)-го канала счетчика 5 подключен к входу разрешения счета (К,М)-го счетчика 35 матрицы, информационный выход которого является инфор5 мационным выходом 37 (К,M)-го канала многоканального счетчика 5, вход 38 начальной установки и тактовый вход 39 которого подключены к входам установки в "0" и суммирующим входам соответствЕнно всех счетчиков 35 матрицы, Устройство работает следующим образом.

Перед началом работы на вход 6 начальной установки подают импульс уровня логической единицы, При этом устанавливаются в "0" все каналы счетчика 5 и приводятся в исходное состояние блок 1 задания матрицы транспортных затрат и модель 2 транспортной сети, В блок 1 заносят информацию о транспортных затратах при перевозках из M-го пункта отправления в

К-й пункт назначения, В модель 2 заносят информацию о запасах пунктов отправления и потребностях пунктов назначения.

5 На вход 7 пуска устройства подают импульс уровня логической единицы. При этом блок 3 синхронизации формирует на своем выходе последовательность импульсов уровня логической единицы. При поступлении на его вход тактовых импульсов блок 1 выбирает минимальный элемент матрицы транспортных затрат и формирует на соответствующем ему выходе потенциал (или потенциалы, если имеется несколько равных элементов) уровня логической единицы. При этом блок 5 выбирает направление перевозок, обладающее наибольшим приоритетом. При поступлении на ее вход тактовых импульсов модель 2 моделирует перевозки по разрешенному направлению, После того, как запасы пункта отправления и/или потребности пункта назначения будут исчерпаны, на соответствующих выходах модели

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

1649562 пор, пока не будут исчерпаны запасы всех пунктов отправления и/или потребности всех пунктов назначения. При этом блок 3 прекращает формирование импульсов на своем выходе и информация на выходе многоканального счетчика 5 соответствует оптимальному плану перевозок из М-ro пункта отправления в К-й пункт назначения.

Блок 1 задания матрицы транспортных затрат работает следующим образом.

Перед началом работы на вход 18 начальной установки подают импульс уровня логической единицы. При этом устанавливаются в "0" все триггеры 9 матрицы. В счетчики 11 заносят информацию о транспортных затратах при перевозках из

М-го пункта отправления в К-й пункт назначения. При поступлении на тактовый вход 19 импульсов уровня логической единицы счетчика 11 последовательно уменьшают содержащиеся е них значения на единицу, При переходе через ноль счетчик 11 устанавливается в "1" соответствующий ему триггер 9, При этом поступление на входы счетчиков

11 импульсов прекращается, При поступлении на входы 16, 17 потенциалов уровня логической единицы счет продолжается.

Модель 2 транспортной сети работает следующим образом.

Перед началом работы на вход 33.подают импульс уровня логической единицы.

При этом устанавливаются s "0" все триггеры 22 и 25, В счетчики 21 и 24 заносят информацию о запасах пунктов отправления и потребностях пунктов назначения соответственно. При поступлении на вход 34 импульсовуровня логической единицы счетчика 21, 24, работа которых разрешена наличием потенциала уровня логической единицы с выходов соответствующих им элементов ИЛИ 20, 23, уменьшают на единицу (no каждому импульсу} содержащиеся в них значения (тем самым моделируется перевозка иэ М-ro пункта отправления в К-й пункт назначения). При переходе счетчиков

2t, 24 через ноль устанавливаются в "1" соответствующие им триггеры 22; 25, При этом на выходах 30, 31 формиру отся признаки удовлетворения потребностей и/или исчерпания запасов. После того как все триггеры 22 и/или 25 буду установлены в

"1", появится потенциал уровня логической единицы на выходе 32 — признак исчерпания запасов всех пунктов отправления

15

45 разрешения работы (К,М)-го канала многоканального счетчика, (К,M)-й информационный выход которого является выходом

50 ния модели транспортной сети подключен к входу останова блока синхронизации.

25 и/или потребностей всех пунктов назначения, Формула изобретения

Устройство для решения задач оптимизации. содержащее блок задания матрицы транспортных затрат, модель транспортной сети, многоканальный счетчик и блок синхронизации, вход пуска которого является входом пуска устройства, вход начальной установки которого подключен к входу установки в "0" многоканального счетчика и к входам начальной установки модели транспортной сети и блока задания матрицы транспортных затрат, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет решения транспортной задачи линейного программирования, в него введен блок приоритета, причем выход блока синхронизации подключен к тактовым входам многоканального счетчика, блока задания матрицы транспортных затрат и к тактовому входу модели транспортной сети, выход признака исчерпания запасов М-го пункта отправления которой (M=1,...,ÏO, где ПО— количество пунктов отправления в трансспортной сети) подключен к входу признака блокировки элементов M-й строки матрицы блока задания матрицы транспортных затрат, выход признака удовлетворения потребностей К-го пункта назначения модели транспортной сети (К=1,...,ПН, где ПН вЂ” количество пунктов назначения в транспортной сети) подключен к входу признака блокировки элементов К-го столбца блока задания матрицы транспортных затрат, выход признака принадлежности (К,M)-ro элемента множеству минимальных которого подключен к (K,M)-му входу блока приоритета, выход признака выбооа (КАЛА поэиции которого подключен к входу разрешения моделирования (К,M)-й перевозки модели транспортной сети и к входу объема оптимально(о плана перевозок из

М-го пункта отправления в К-й пункт назначения устройства, выход признака исчерпания запасов всех. пунктов отправления и/или потребностей всех пунктов назначе° ° е ° Ф °

° Ф Ф °

° Ф Ф °

1649662 б Ф

° °

° °

° ° ° е ° °

Ф ° °

° ° °

° ° °

° ° б

Ф ° °

Ф Ф °

° ° °

° ° °

° Ф °

° ° °

° ° Ф

° Ф

Ф °

° °

Ф °

1649562 и пи

Фиг 3

ЗЬг

Составитель А.Мишин

Техред М,Моргентал Корректор О,Ципле

Редактор В.Фельдман

Заказ 1870 Тираж 419 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. ужгород, ул.Гагарина, 101

Игп

29а

37nag

ФОГ 4Ф

38

ЗУ

М