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

 

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

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

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

РЕСПУБЛИК

„.80„„1476493 (51)4 G 06 G 7/122

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

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

ПРИ ГКНТ СССР

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

Н А ВТОРСНОМ,К СВИДЕТЕЛЬСТВУ транспортных затрат. Целью изобретения является повышение точности решения транспортных задач за счет реализации метода двойного назначения.

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

С2 каждого столбца. Планы перевозок фик- у сируются в матрице счетчиков. 2 ил. (21) 4148656/24-24 (22) 01.10.86 (46) 30.04.89. Бюл. У 16 (72) О.Г.Алексеев, В.Ю.Мержанов, Н.И.Ячкула и А.Н.Мардас (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 219924, кл. G 06 G 7/26, 1968.

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

У 1263094, кл. G 06 G 7/122, 1985. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ТРАНСПОРТHbIK ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (57) Изобретение относится к вычислительной технике, может быть использовано для решения транспортных эа« дач линейного программирования и позволяет определить оптимальные планы перевозок с учетом коэффициентов

2 матрицу из О Н элементов НЕ 5, первую матрицу из О Н блоков 6 элементов 4

И, вторую матрицу из О Н блоков 7 элементов И, первую группу из 0 эле- 1 Ь ментов И 8, вторую группу из Н эле- р ментов И 9, первую и вторую группы 1„ © из О блоков 10 и 11 выбора макси- (;А1 мального кода, третью и четвертую

Г группы из Н блоков 12 и 13 выбора . максимального кода, первую группу из

О блоков 14 вычитания, вторую группу из Н блоков 15 вычитания, первый 16 и второй 17 блоки выбора максимальной» го кода, первую группу из О счетчиков

18, вторую группу из Н счетчиков 19, первую группу из О ключей 20, вторую группу из Н ключей 21, первую группу из О генераторов 22 одиночного импульса, вторую группу из Н генерато.

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

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

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

Устройство содержит матрицу из

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

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

24, второй 25, третий 26 и четвертый

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

32 пуска устройства, входы 33 задания величины запасов К-го пункта отправления устройства (К 1, . °,О); входы 34 задания величины потребностей М-го пункта назначения устройства (М1,,... .° .H), выходы 35 признаков отсутствия запасов в К.-ом пункте отправления устройства, выходы 36 призиаков удовлетворения потребностей

М-го пункта назначения устройства, первый 37 и второй 38 выходы блока

28 синхронизации, входы 39 задания величины транспортных затрат при перевозках иэ К-го пункта отправления в М-й пункт назначения устройства, Устройство работает следующим образом.

Пусть требуется определить план перевозок в транспортной сети из трех пунктов отправления, имеющих запасы соответственно А1=40, А2=80 и АЗ=60, и трех пунктов назначения с объемами потребностей B1=30 B2=100 и B3=50.

Транспортная сеть характеризуется ,матрицей транспортных затрат:

10 1 3

6 2 5

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 и 9 устанавливаются в ноль счетчики 30. После этого блоки .12(10} выбирают максимальные коды в соответствующих строках (столбцах) матрицы транспортных затрат. В случае равенства нескольких кодов выбирается код с наибольшим приоритетом.

Максимальный в строке (столбце) код исключается при помощи соответству,ющего элемента 5(4) HE и блока 7(6) элементов И из дальнейшего анализа и с помощью блоков 13 (» ) выбираются следующие по. величине числа в строках (столбцах) матрицы транспортных зат" рат. При помощи блоков 15 (14) вычитания и блоков 17 (15) выбора максимального кода производится выбор мак-. симальной разности максимального и следующего за ним по величине члена матрицы транспортных затрат среди всех ее строк (столбцов), выход позиции максимального кода (с наибольшим приоритетом} поступает на входы разрешения счета соответствующих позиций максимального кода счетчиков

19(18) и одного из счетчиков 30. Аналогичным образом работает устройство и при отключении ключей 2.

На вход 32 пуска устройства подают импульсный сигнал единичного ,уровня, при этом блок 28 синхрониза25 ции начинает формировать сигналы в соответствии с временной диаграммой

его работы на фиг.2. Импульс единичного уровня формируется на выходе 37 блока 28, при этом выключаются ключи

2, для которых выполнено условие отключения — отсутствие запасов в М-м пункте отправления или полное удовлетворение потребностей К-ro пункта назначения. Через время Тl, достаточ1ное для выключения соответствующего

35 ключа 2. и окончания процесса выбора максимальных (по строкам и столбцам) разностей, блок 28. снимает сигнал с выхода 37 и начинает выдавать импульсы на выход 38. При этом счетчики 18, 19 и 30 на входы разрешения счета которых подан потенциал единичного уровня, начинают счет:импульсов.

В рамках данного примера счет импульсов ведет первый счетчик 19, третий счетчик 18 и третий счетчик 30 первой строки матрицы. Счет импульсов эквивалентен моделированию перевозки иэ третьего пункта отправления в первый пункт назначения. Через сорок импульсов на выходе первого счетчика 19 появляется сигнал переполнения (удовлетворены потребности первого пункта назначения). При этом размыкается информационная цепь первого ключа 21, а первый генератор

23 формирует импульс единичного уровня, перезапуская блок 28 синхрониза5 ?4 ции. Блок 28 прекращает выработку импульсов на выходе 38 и формирует сигнал на выходе 37. При этом все ключи 2 первой строки матрицы размыкают свои информационные цепи (первый пункт назначения исключается из дальнейшего анализа), после чего работа. устройства повторяется. По окончании работы в счетчиках 30 матрицы фиксируется план оптимальных перевозок, который в рамках рассматриваемого примера имеет вид:

О 0 40

30 40 10

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

Устройство для решения транспортных задач линейного программирования, содержащее матрицу из О Н регистров, где Π— количество пунктов отправления в транспортной сети, Н вЂ” количество пунктов назначения в транспортной сети, группу из ОхН ключей, матрицу из О Н элементов ИДИ, матрицу из О Н элементов И, матрицу из О Н счетчиков, первую группу иэ О счетчиков, вторую группу из Н счетчиков, первую группу из О ключей, вторую группу из Н ключей, первую группу из

О генераторов одиночного импульса, вторую группу из Н генераторов одиночного импульса, три элемента ИЛИ, первую группу иэ О элементов И, вторую группу из Н элементов И и блок синхронизации, причем вход начальной установки устройства подключен к входам признаков записи всех регистров матрицы к входам всех ключей матрицы, входам признаков записи всех счет чиков первой и второй групп, входам: включения всех ключей первой и второй групп и входам установки в "0" всех счетчиков матрицы, вход задания величины транспортных затрат при перевозках из К-ro пункта отправления (K=l 0) в M-й пункт назначения (M= l Н) устройства подключен к информационному входу К-ro регистра

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

-ro пункта отправления устройства подключен к информационному входу

-ro счетчика первой группы, выход признака переполнения которого является выходом признака отсутствия эа76493 е пасов в К-м пункте отправления устройства и подключен к входу пуска

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

5 ключа первой группы и первому входу

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

30 ИЛИ, выход М-го генератора одиночного импульса второй группы подключен к M-му входу второго элемента

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

4р выход блока синхронизации подключен к вторым входам всех элементов И первой и второй групп, второй выход блока синхронизации подключен к суммирующим входам всех счетчиков матрицы

45 и информационным входам всех ключей первой и .второй групп, выход К-го ключа первой группы подключен к суммирующему входу К-го счетчика первой группы, выход M-ro ключа второй груп5п пы подключен к суммирующему входу

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

55 метода двойного предпочтения, в него введены две матрицы из О. Н блоков элементов И, две матрицы из О Н элементов НЕ, первая и вторая группы иэ

О блоков выбора максимального кода, l476493 третья и четвертая группы из Н блоков выбора максимального кода, первая группа из 0 блоков вычитания, вторая группа из Н блоков вычитания

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

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

К-го блока вычитания первой группы, З0 выход которого подключен к К-му входу первого блока выбора максимального кода, К"й .выход позиции максимального кода с наибольшим приоритетом которого подключен к входу разре- gg шен записи К-го счетчика первой группы и к первым входам всех элементов

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

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

1476493

1476493

Составитель Д.Пак

Редактор Л,ПчолинсКая Техред И.Ходанич Корректор М.Самборская

Заказ 2158/50 Тираж 669 Подписное

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

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

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