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

1

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

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

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

Устройство содержит матрицу из регистров 1, где О - количество пунктов назначения в транспортной сети, матрицу из ключей 2, матрицу из элементов ИЛИ 3, первую матрицу из элементов НЕ 4, вторую

матрицу из элементов НЕ 5, первую матрицу из блоков 6 элементов И, вторую матрицу из блоков 7 элементов И, первую группу из 0 элементов И 8, вторую группу из Н элементов И 9, первую и вторую группы из 0 блоков 10 и 11 выбора максимального кода, третью и четвертую группы из Н блоков 12 и 13 выбора максимального кода, первую группу из О блоков 14 вычитания, вторую группу из Н блоков 15 вычитания, первый 16 и второй 17 блоки выбора максимального кода, первую группу из О счетчиков 18, вторую группу из Н счетчиков 19, первую группу из О ключей 20, вторую группу из Н ключей 21, первую группу из О генераторов 22 одиночного импульса, вторую группу из Н генерато4ъЧ

СЭ Ј СО

СО

ров 23 одиночного импульса, первый 24, второй 25, третий 26 и четвертьй

27элементы ИЛИ, блок 28 синхронизации, матрицу из элементов И 29, матрицу из счетчиков 30, вход 31 начальной установки устройства, вход

32 пуска устройства, входы 33 задания величины запасов К-го пункта отправления устройства (,...,0), входы 34 задания величины потребностей М-го пункта назначения устройства (,...Н), выходы 35 признаков отсутствия запасов в К-ом пункте отправления устройства, выходы 36 приз наков удовлетворения потребностей М-го пункта назначения устройства, первый 37 и второй 38 выходы блока

28синхронизации, входы 39 задания величины транспортных затрат при пе- ревозках из К-го пункта отправления

в М-й пункт назначения устройства.

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

Пусть требуется определить план перевозок в транспортной сети из трех пунктов отправления, имеющих запасы соответственно , и , и трех пунктов назначения с объемами потребностей , и . Транспортная сеть характеризуется )Матрицей транспортных затрат: 10 1 3 625 12 5 14 Пусть емкость счетчиков 18 и 19 равна 100. Перед началом работы на входы 33 с первого по третий подают коды чисел 100-40 60, 100-80 20 и 100-60 40 соответственно, на входы 34 с первого по т.ретий подают коды чисел 100-30 70, 100-100 0 и 100-50 50 соответственно На входы 39 подают числа в соответствии с матрицей транспортных затрат. На вход 31 на- чальной установки устройства подают импульсный сигнал единичного уровня, при этом замыкаются информационные цепи ключей 2, 21 и 20, коды указанных чисел заносятся в регистры 1 и счетчики 18 и 19 устанавливаются в ноль счетчики 30. После этого блоки .12(10) выбирают максимальные коды в соответствующих строках (столбцах) матрицы транспортных затрат. В слу- чае равенства нескольких кодов выбирается код с наибольшим приоритетом Максимальный в строке (столбце) код

0 0 5 Q 5

5

исключается при помощи соответствующего элемента 5(4) НЕ и блока 7(6) элементов И из дальнейшего анализа и с помощью блоков 13 (11) выбираются следующие по величине числа в строках (столбцах) матрицы транспортных затрат. При помощи блоков 15 (14) вычитания и блоков 17 (15) выбора максимального кода производится выбор максимальной разности максимального и следующего за ним по величине члена матрицы транспортных затрат среди в.сех ее строк (столбцов), выход позиции максимального кода (с наибольшим приоритетом) поступает на входы разрешения счета соответствующих позиций максимального кода счетчиков 19(18) и одного из счетчиков 30. Аналогичным образом работает устройство и при отключении ключей 2,

На вход 32 пуска устройства подают импульсный сигнал единичного уровня, при этом блок 28 синхрониза- ции начинает формировать сигналы в соответствии с временной диаграммой его работы на фиг.2. Импульс единичного уровня формируется на выходе 37 блока 281, при этом выключаются ключи 2, для которых выполнено условие отключения - отсутствие запасов в М-м пункте отправления или полное удовлетворение потребностей К-го пункта назначения. Через время 11, достаточное для выключения соответствующего клзэча 2 и окончания процесса выбора максимальных (по строкам и столбцам) разностей, блок 28 снимает сигнал с выхода 37 и начинает выдавать импульсы на выход 38. При этом счетчики 18, 19 и 30 на входы разрешения счета которых подан потенциал единичного уровня, начинают счет импульсов. В рамках данного примера счет им- пульсав ведет первый счетчик 19, третий счетчик 18 и третий счетчик 30 первой строки матрицы. Счет импульсов эквивалентен моделированию перевозки из третьего пункта отправления в первый пункт назначения. Через сорок импульсов на выходе первого счетчика 19 появляется сигнал переполнения (удовлетворены потребности первого пункта назначения). При этом размыкается информационная цепь первого ключа 21, а первый генератор 23 формирует импульс единичного уровня, перезапуская блок 28 синхронизации. Блок 28 прекращает выработку импульсов на выходе 38 и формирует сигнал на выходе 37. При этом все ключи 2 первой строки матрицы размыкают свои информационные цепи (первый пункт назначения исключается из дальнейшего анализа), после чего работа устройства повторяется. По окончании работы в счетчиках 30 матрицы фиксируется план оптимальных перевозок, который в рамках рассматриваемого примера имеет вид:

О 0 40

30 40 10

О 60 О

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

Устройство для решения транспортных задач линейного программирования содержащее матрицу из регистров где О - количество пунктов отправления в транспортной сети, Н - количество пунктов назначения в транспортной сети, группу из ключей, матрицу из ОхН элементов ИЛИ, матрицу из элементов И, матрицу из счетчиков, первую группу из О счетчиков, вторую группу из Н счетчиков, первую группу из О ключей, вторую группу из Н ключей, первую группу из О генераторов одиночного импульса, вторую группу из Н генераторов одиночного импульса, три элемента ИЛИ, первую группу из 0 элементов И, вторую группу из Н элементов И и блок синхронизации, причем вход началвной установки устройства подключен к входам признаков записи всех регистров матрицы к входам всех ключей матрицы входам признаков записи всех счетчиков первой и второй групп, входам включения всех ключей первой и второй групп и входам установки в О всех счетчиков матрицы, вход задания величины транспортных затрат при перевозках из К-го пункта отправления (,...,0) в М-й пункт назначения (М 1,... ,Н) устройства подключен к информационному входу К-го регистра М-й строки матрицы, выход которого подключен к информационному входу ключа, вход задания величины запасов К-го пункта отправления устройства подключен к информационному входу К-го счетчика первой группы, выход признака переполнения которого является выходом признака отсутствия запасов в К-м пункте отправления устройства и подключен к входу пуска К-го генератора одиночного импульса первой группы, входу выключения К-го ключа первой группы и первому входу К-го элемента И первой группы, выход которого подключен к первым входам всех элементов ИЛИ К-го столбца мат- 0 рицы, вход задания величины потребностей М-го пункта назначения устройства подключен к информационному входу М-го счетчика второй группы, выход признака переполнения которого 5 является выходом признака удовлетворения потребностей М-го пункта назначения и подключен к входу выключения М-го ключа второй группы, входу пуска М-го генератора одиноч- 0 ного импульса и первому входу М-го элемента И второй группы, выход которого подключен к вторым входам всех элементов ИЛИ М-й строки матрицы, выход К-го элемента И М-й стро- 5 ки первой матрицы подключен к входу выключения К-го ключа М-й строки матрицы, выход К-го генератора одиночного импульса первой группы подключен к К-му входу первого элемента 0 ИЛИ, выход М-го генератора одиночного импульса второй группы подключен к М-му входу второго элемента ИЛИ, выход которого подключен к первому входу третьего элемента ИЛИ к 5 второму входу которого подключен выход первого элемента ИЛИ, выход К-го элемента И М-й строки матрицы подключен к входу разрешения счета К-го счетчика М-й строки матрицы, первый 0 выход блока синхронизации подключен к вторым входам всех элементов И первой и второй групп, второй выход блока синхронизации подключен к суммирующим входам всех счетчиков матрицы 5 и информационным входам всех ключей первой и второй групп, выход К-го ключа первой группы подключен к суммирующему входу К-го счетчика первой группы, выход М-го ключа второй груп- 0 пы подключен к суммирующему входу М-го счетчика второй группы, отличающееся тем, что, с целью повышения точности решения транспортных задач за счет использования 5 метода двойного предпочтения, в него введены две матрицы из О Н блоков элементов И, две матрицы из элементов НЕ, первая и вторая группы из О блоков выбора максимального кода, .

третья и четвертая группы из Н блоков выбора максимального кода, первая группа из О блоков вычитания, вторая группа из Н блоков вычитания и два блока выбора максимального кода, причем выход К-го ключа М-й строки матрицы подключен к К-му информационному входу М-го блока выбора максимального кода третьей группы, к ин- ю формационным входам К-х блоков элементов И М-х строк первой и второй матриц и к М-му информационному входу К-го блока выбора максимального кода первой группы, М-й выход позиции максимального кода с наибольшим приоритетом которого подключен к входу М-го элемента НЕ К-го столбца первой матрицы, выход которого под14764938

шен записи К-го счетчика первой группы и к первым входам всех элементов И К-го столбца матрицы, К-й выход с позиции максимального кода с наибольшим приоритетом М-го блока выбора максимального кода третьей группы подключен к входу К-го элемента НЕ М-го столбца второй матрицы, выход которого подключен к управляющему входу К-го блока элементов И М-й строки второй матрицы, выход которого подключен к К-му входу М-го блока выбора максимального кода четвертой группы, выход которого подключен к входу вычитаемого М-го блока вычитания второй группы, информационный выход М-го блока выбора максимального кода третьей группы подключен к вхо15

ключей к управляющему входу К-го бло- 20 ДУ уменьшаемого М-го блока вычита

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

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

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

са

в «5

jg| jumiujinjij rirumnjLjmf tig.

Фаг. 2