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

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

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

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

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

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

К

ю ел кэ

ПО х ПН элементов И 12, группу из ПН элементов ИЛИ 13. элемент ИЛИ 14 и элемент И 15, причем вход 16 блокировки элементов К-ro столбца блока 1 (,...ПН) подключен к первым входам всех элементов ИЛИ-НЕ 10 К-ro столбца матрицы, вход 17 блокировки элементов М-й строки блока 1 подключен к вторым входам всех элементов ИЛИ-НЕ 10 М-й строки матрицы (,...ПО). выход (К,М)-го элемента ИЛИ- НЕ 10 матрицы подключен к первому входу (К,М}-го элемента И 12 и к входу разрешения счета (К.М)-го счетчика 11 матрицы, выход признака переполнения которого подключен к входу установки в 1 (К,М)-го триггера 9 матрицы, выход которого подключен к второму входу (К,М)-го элемента И 12 матрицы, выход которого подключен к М-у входу К-ro элемента ИЛИ группы, выход которого является выходом признака принадлежно- сти (К,М)-го элемента множеству минимальных и подключен к К-у входу элемента ИЛИ 14, выход которого подключен к первому входу элемента И 15, выход которого подключен к вычитающим входам всех счетчи- ков И матрицы, вход 18 начальной установки блока 1 подключен к входам установки в О всех триггеров 9 матрицы, тактовый вход 19 блока 1 подключен к второму входу элемента И 15.

Модель 2 транспортной сети содержит группу из ПО элементов ИЛИ 20, группу из ПО счетчиков 21, группу из ПО триггеров 22, группу из ПН элементов ИЛИ 23, группу из ПН счетчиков 24, группу из ПН триггеров 25, два элемента И 26.27 и элемент ИЛИ 28, причем вход 29 разрешения моделирования перевозок из М-го пункта отправления в К-й пункт назначения блока 2 подключен к К-у входу М-ro элемента И Л VI 20 группы и к М-у входу К-го элемента ИЛИ 23 группы, выход которого подключен к входу разрешения счета К-го счетчика 24 группы, выход признака переполнения которого подключен к входу установки в 1 К-го триггера 25 группы, выход которого является выходом 30 признака удовлетворения потребностей К-ro пункта назначения блока 2 и подключен к К-у входу элемента И 27, выход которого подключен к первому входу элемента ИЛИ 28, выход М-го элемента ИЛИ 20 подключен к входу разрешения счета М-го счетчика 21 группы, выход признака переполнения которого подключен к входу установки в 1 М-го триггера 22 группы, прямой выход ко- торого является выходом 31 признака исчерпания запасов М-го пункта отправления и подключен к М-у входу элемента И 26, выход которого подключен к второму входу элемента ИЛИ 28, выход которого является

выходом 32 признака исчерпания запасов всех пунктов отправления и/или потребностей всех пунктов назначения модели 2, вход 33 начальной установки которой подключен к входам установки в О всех триггеров 22 и 25 групп, тактовый вход 34 модели 2 подключен к вычитающим входам всех счетчиков 21 и 24 групп.

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

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

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

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

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

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

Перед началом работы на вход 18 начальной установки подают импульс уровня логической единицы. При этом устанавливаются в О все триггеры 9 матрицы. В счетчики 1t заносят информацию о транспортных затратах при перевозках из М-ro пункта отправления в К-й пункт назначения. При поступлении на тактовый вход t9 импульсов уровня логической единицы счетчика 11 последовательно уменьшают содержащиеся в них значения на единицу. При переходе через ноль счетчик 11 устанавливается в 1 соответствующий ему триггер 9. При этом поступление на входы счетчиков 11 импульсов прекращается, Пои поступлении на входы 16. 17 потенциалов уровня логической единицы счет продолжается.

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

Перед началом работы на вход 33 подают импульс уровня логической единицы. При этом устанавливаются в О все триггеры 22 и 25. В счетчики 21 и 24 заносят информацию о запасах пунктов отправления и потребностях пунктов назначения соответственно. При поступлении на вход 34 импульсов уровня логической единицы счетчика 21, 24, работа которых разрешена наличием потенциала уровня логической единицы с выходов соответствующих им элементов ИЛИ 20, 23, уменьшают на единицу (по каждому импульсу) содержащиеся в чих значения (тем самым моделируется перевозка из М-ro пункта отправления в К-й пункт назначения). При переходе счетчиков 2t, 24 через ноль устанавливаются в 1 соответствующие им триггеры 22, 25. При этом на выходах 30, 31 формируются признаки удовлетворения потребностей и/или исчерпания запасов. После того как все триггеры 22 и/или 25 будут установлены в 1, появится потенциал уровня логической единицы на выходе 32 - признак исчерпания запасов всех пунктов отправления

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

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

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

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

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

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

блока задания матрицы транспортных затрат, выход признака удовлетворения потребностей К-го пункта назначения модели транспортной сети (,...,ПН, где ПН - количество пунктов назначения в транспортной сети) подключен к входу признака блокировки элементов К-ro столбца блока задания матрицы транспортных затрат, выход признака принадлежности (К,М)-го элемента множеству минимальных которого

подключен к (К.М)-му входу блока приоритета, выход признака выбора (К.М}й позиции которого подключен к входу разрешения моделирования (К,М)-й перевозки модели транспортной сети и к входу

разрешения работы (К,М)-го канала многоканального счетчика, (К,М)-й информационный выход которого является выходом объема оптимального плана перевозок из М-го пункта отправления в К-й пункт назначения устройства, выход признака исчерпания запасов всех,пунктов отправления и/или потребностей всех пунктов назначения модели транспортной сети подключен к входу останова блока синхронизации.

.

Фш.1

9T t

да//

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

Mffff

П

/юп#

Фиг. 2

29атЪ

ТЗпнпо

J

36ц $ипа1 $6(2 Збпаг

f/TOf

37пог

м

Нfst

№

1 30пн

ФигЪ

/ Зб/лН 36попн

. - . Зв

39 -3№$

Г2ПН

38 39

d- 35/wrt

ФигЛ

Ъ7/7ОР#