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

,1476493 9) 06 С 7 12 ОПИСАНИЕ ИЗОБРЕТЕН етение относи я к в быть ис тельн ике пользовано дл зок с мин определен альными т на еревоньяи заиспо рт ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ПНТ СССР К АВТОРСКОМ,К СВИДЕТЕЛ(56) Авторское свидетельство СССР У 219924, кл. С 06 С 7/26, 1968.Авторское свидетельство СССР У 1263094, кл, С 06 С 7/122, 985. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ТРАНСПОРТ НЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (57) Изобретение относится к вычислительной технике, может быть использовано для решения транспортных задач линейного программирования и позволяет определить оптимальные планы перевозок с учетом коэффициентов тратами.Цель изобретения - повышение точности решения транспортных задач за счет использования метода двойного предпочтения.На фиг.1 представлена функциональная схема устройства; на Фиг.2 - временная диаграмма работы блока синхронизации.Устройство содержит матрицу из ОН регистров 1, где О - количество пунктов назначения в транспортной сети, матрицу иэ ОН ключей 2, матрицу из ОН элементов ИЛИ 3, первую матрицу из ОН элементов НЕ 4, вторую транспортных затрат. Целью изобретения является повышение точности решения транспортных задач за счет реализацииметода двойного назначения.Для этого в состав устройства введены матрица регистров, в которую перед началом работы заносятся числа,характеризующие транспортные затратыпри перевозках между пунктами отправления и назначения, четыре группыблоков выбора максимального кода идве группы блоков вычитания, которыеорганизуют процедуру выбора максимальногб и следующего за ним по величине элементов матрицы транспортных затрат для каждой ее строки икаждого столбца, Планы перевозок фиксируются в матрице счетчиков. 2 ил. матрицу из ОН элементов НЕ 5, первую матрицу из ОН блоков 6 элементов И, вторую матрицу из ОН блоков 7элементов И, первую группу из О элементов И 8, вторую группу из Н эле- ф ментов И 9, первую и вторую группы 1 ф из 0 блоков 10 и 11 выбора макси- (ф мального кода, третью и четвертуюГ группы из Н блоков 12 и 13 выбора .максимального кода, первую группу из О блоков 14 вычитания, вторую группу из Н блоков 15 вычитания, первый 16 и второй 17 блоки выбора максимального кода, первую группу из О счетчиков 18, вторую группу из Н счетчиков 19, первую группу из О ключей 20, вторую группу из Н ключей 21, первую группу из О генераторов 22 одиночного импульса, вторую группу из Н генераторов 23 одиночного импульса, первый 24, второй 25, третий 26 и четвертый 27 элементы ИЛИ, блок 28 синхронизации, матрицу из ОН элементов И 29, матрицу из 01 Н счетчиков 30, вход 31 начальной установки устройства, вход32 пуска устройства, входы 33 задания величины запасов К-го пункта отправления устройства (К 10);входы 34 задания величины потребностей М-го пункта назначения устройства (М 1,Н), выходы 35 признаковотсутствия запасов в К.-ом пункте отправления устройства, выходы 36 приз"иаков удовлетворения потребностей М-го пункта назначения устройства, первый 37 и второй 38 выходы блока 28 синхронизации, входы 39 задания величины транспортных затрат при перевозках иэ К-го пункта отправления в М-й пункт назначения устройства,Устройство работает следующим образом.Пусть требуется определить планперевозок в транспортной сети из трехпунктов отправления, имеющих запасы соответственно А 1=40, А 2=80 и АЗ=60, и трех пунктов назначения с объемами потребностей В 1=30, В 2=100 и В 3=50. Транспортная сеть характеризуется ,матрицей транспортных затрат:10 1 36 2 512 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) выбирают максимальные коды в соответствующих строках (столбцах) матрицы транспортных затрат. В случае равенства нескольких кодов выби" рается код с наибольшим приоритетом. Максимальный в строке (столбце) код исключается при помощи соответству,ющего элемента 5(4) НЕ и блока 7(6) элементов И из дальнейшего анализа и с помощью блоков 13 (11) выбираются следующие по. величине числа в строках (столбцах) матрицы транспортных зат" рат, При помощи блоков 15 (14) вычитания и блоков 17 (15) выбора максимального кода производится выбор мак-.симальной разности максимального и следующего за ним по величине члена матрицы транспортных затрат среди всех ее строк (столбцов), выход позиции максимального кода (с наибольшим приоритетом) поступает на входы разрешения счета соответствующих позиций максимального кода счетчиков 19(18) и одного из счетчиков 30, Аналогичным образом работает устройство и при отключении ключей 2,На вход 32 пуска устройства подают импульсный сигнал единичного ,уровня, при этом блок 28 синхрониза ции начинает формировать сигналы всоответствии с временной диаграммой его работы на фиг.2. Импульс единичного уровня формируется на выходе 37 блока 28, при этом выключаются ключи 2, для которых выполнено условие отключения " отсутствие запасов в М-м пункте отправления или полное удовлетворение потребностей К-го пункта назначения. Через время Т 1, достаточ 1 ное для выключения соответствующего 35ключа 2.и окончания процесса выбора максимальных (по строкам и столбцам) разностей, блок 28. снимает сигнал с выхода 37 и начинает выдавать импульсы на выход 38. При этом счетчики 18, 19 и 30 на входы разрешения счета которых подан потенциал единичного уровня, начинают счет:импульсов. В рамках данного примера счет импульсов ведет первый счетчик 19, третий счетчик 18 и третий счетчик 30 первой строки матрицы. Счет импульсов эквивалентен моделированию перевозки иэ третьего пункта отправления в первый пункт назначения. Через сорок импульсов на выходе первого счет" чика 19 появляется сигнал переполнения (удовлетворены потребности первого пункта назначения). При этом размыкается информационная цепь первого ключа 21, а первый генератор 23 формирует импульс единичного уровня, перезапуская блок 28 синхрониза5 14 ции. Блок 28 прекращает выработку импульсов на выходе 38 и формирует сигнал на выходе 37. При этом все ключи 2 первой строки матрицы размыкают свои информационные цепи (первый пункт назначения исключается из дальнейшего анализа), после чего работа устройства повторяется. По окончании .работы в счетчиках 30 матрицы фиксируется план оптимальных перевозок, который в рамках рассматриваемого примера имеет вид:0 0 4030 40 1 О0 60 0 формула изобретения Устройство для решения транспортных задач линейного программирования, содержащее матрицу из ОН регистров, где О - количество пунктов отправления в транспортной сети, Н - количество пунктов назначения в транспортной сети, группу из ОН ключей, матрицу из ОН элементов ИДИ, матрицу из ОхН элементов И, матрицу из ОНсчетчиков, первую группу иэ О счетчиков, вторую группу из Н счетчиков, первую группу из О ключей, вторую группу из Н ключей, первую группу из О генераторов одиночного импульса, вторую группу из Н генераторов одиночного импульса, три элемента ИЛИ, первую группу иэ О элементов И, вторую группу из Н элементов И и блок синхронизации, причем вход начальной установки устройства подключен к входам признаков записи всех регистров матрицы к входам всех ключей матрицы, входам признаков записи всех счетчиков первой и второй групп, входам включения всех ключей первой и второй групп и входам установки в "0" всех счетчиков матрицы, вход задания величины транспортных затрат при перевозках из К-го пункта отправления (К=10) в М-й пункт назначения (М=1Н) устройства подключен к информационному входу К-го регистра М-й строки матрицы, выход которого подключен к информационному входу ключа, вход задания величины запасов К-го пункта отправления устройства подключен к информационному входу К-го счетчика первой группы, выход признака переполнения которого является выходом признака отсутствия эа 76493 епасов в К-м пункте отправления устройства и подключен к входу пускаК-го генератора одиночного импульсапервой группы, входу выключения К-го 5ключа первой группы и первому входуК-го элемента И первой группы, выходкоторого подключен к первым входамвсех элементов ИЛИ К-го столбца матрицы, вход задания величины потреб"ностей М-го пункта назначения устройства подключен к информационномувходу М-го счетчика второй группы,выход признака переполнения которого 15 является выходом признака удовлетворения потребностей М-го пунктаназначения и подключен к входу выключения М-го ключа второй группы,входу пуска М-го генератора одиноч ного импульса и первому входу М-гоэлемента И второй группы, выход которого подключен к вторым входамвсех элементов ИЛИ М-й строки матрицы, выход К-го элемента И М-й стро ки первой матрицы подключен к входувыключения К-го ключа М-й строки матрицы, выход К-го генератора одиночного импульса первой группы подключен к К-му входу первого элемента 30 ИЛИ, выход М-го генератора одиночного импульса второй группы подключен к М-му входу второго элементаИЛИ, выход которого подключен к первому входу третьего элемента ИЛИ к З 5 второму входу которого подключен выход первого элемента ИЛИ, выход К-гоэлемента И М-й строки матрицы подключен к входу разрешения счета К-госчетчика М-й строки матрицы, первый 40 выход блока синхронизации подключенк вторым входам всех элементов И первой и второй групп, второй выход блока синхронизации подключен к суммирующим входамвсех счетчиков матрицы 45 и информационным входам всех ключейпервой и .второй групп, выход К-гоключа первой группы подключен к суммирующему входу К-го счетчика первойгруппы, выход М-го ключа второй груп пы подключен к суммирующему входуМ-го счетчика второй группы, о т -л и ч а ю щ е е с я тем,. что, сцелью повышения точности решения транспортных задач за счет использования 55 метода двойного предпочтения, в неговведены две матрицы из О. Н блоковэлементов И, две матрицы из ОН элементов НЕ, первая и вторая группы иэО блоков выбора максимального кода, 1476493третья и четвертая группы из Н блоков выбора максимального кода, первая группа из 0 блоков вычитания, вторая группа из Н блоков вычитания5 и два блока выбора максимального кода, причем выход К-го ключа М-й строки матрицы подключен к К-му информационному входу М-го блока выбора максимального кода третьей группы, к ин формационным входам К-х блоков элементов И М-х строк первой и второй матриц и к М"му информационному входу К-го блока выбора максимального кодапервой группыМ-й выход пози ции максимального кода с наибольшим приоритетом которого подключен к входу М-го элемента НЕ К-го столбца первой матрицы, выход которого под" ключен к управляющему входу К-го бло ка элементов И М-й строки первой матрицы, выход которого подключен к М-му входу К-го блока выбора максимального кода второй группы, выход кото" рого подключен к входу вычитаемого К-го блока вычитания первой группы, "информационный выход К-го блока выбора максимального кода первой группы подключен к входу уменьшаемого К-го блока вычитания первой группы, З 0 выход которого подключен к К-му входу первого блока выбора максимального кода, К"й .выход позиции максимального кода с наибольшим приоритетом которого подключен к входу разре- З 5 шен записи К-го счетчика первой группы и к первым входам всех элементовИ К-го столбца матрицы, К-й выходпозиции максимального кода с наиболь"шим приоритетом М-го блока выборамаксимального кода третьей группыподключен к входу К-го элемента НЕМ-го столбца второй матрицы, вьжодкоторого подключен к управляющемувходу К-го блока элементов И М-йстроки второй матрицы, выход которого подключен к К-му входу М-го блокавыбора максимального кода четвертойгруппы, выход которого подключен квходу вычитаемого М-го блока вычитания второй группы, информационный вы"ход М-го блока выбора максимальногокода третьей группы подключен к входу уменьшаемого М-го блока вычитания второй группы, выход которогоподключен к М-му информационному входу второго блока выбора максимально-.го кода, М-й выход позиции максимального кода с наибольшим приоритетомкоторого подключен к входу разрешения счета М"го счетчика второй группы и входам всех элементов И М-йстроки матрицы, выход третьего элемента ИЛИ подключен к первому входучетвертого элемента ИЛИ, вход пускаустройства подключен к второму входучетвертого элемента ИЛИ, выход которого подключен к входу пуска блокасинхронизации.1476493 йау пуск ИСоставитель А.Пак Редактор Л,ПчолинсКая Техред М,Ходанич Корректор М.СамборскаяЗаказ 2158/50 Тираж 669 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101