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

 

Изобретение относится к вычислительной технике и может быть использовано для решения задачи назначения в системах распределенной обработки АСУ. Целью изобретения является сокращение аппаратурных затрат при решении задачи назначения методом максимальной строки (столбца). Устройство содержит регистры 1, 2, 3, кольцевой регистр 4 сдвига, блоки 5, 6 элементов И, элементы 7...10 задержки, счетчики 11, 12, элементы ИЛИ 13, 14, 15, блок 16 сравнения, блок 17 памяти, дешифратор 18, вход 19 начальной установки устройства, тактовый вход 20 устройства, информационный вход 21 устройства, вход 22 чтения устройства, информационный выход 23 устройства и выход 24 признака окончания работы устройства. На вход 21 устройства подают последовательно по строкам (по столбцам) коды элементов матрицы стоимости, сопровождая каждый из них импульсом уровня логической единицы на тактовом входе 20 устройства. При этом в блоке 17 памяти формируется матрица назначений. 3 ил.

СООЗ СОВЕтсних

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

РЕСПУБЛИК (19) (И) (51) 5 G 06 F 15/20

ОПИСАНИЕ ИЗОБР-ЕТЕНЮ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4450604/24-24 (22) 28,06.88 (46) 15.04.90, Бюл, ))- 14 (72) В.F. Êîçëîâ (53) 681.333 (088 ° 8) (56) Авторское свидетельство СССР

У 1320812, кл. G 06 F 15/20, 1986.

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

1374241, кл. G 06 Г 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ РЕП ЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАЮИРОВАНИЯ

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

АСУ, Целью изобретения является сокращение аппаратурных затрат при решении задачи назначения методом макси2 мальной строки (столбца). Устройство содержит регистры 1,2 3 кольцевой регистр 4 сдвига, блоки 5 6 элементов И, элементы 7-10 задержки, счетчики 11, 12, элементы ИЛИ 13,14, 15, блок 16 сравнения, блок 17 памяти, дешифратор 18, вход 19 начальной установки устройства, тактовый вход 20 устройства, информационный вход 21 устройства, вход 22 чтения устройства, информационный выход 23 устройства и выход 24 признака окончания работы устройства. На вход 21 устройства подают последовательно по строкам (по столбцам) коды-элементов матрицы стоимости, сопровождая каждый из них импульсом уровня логической единицы на тактовом входе 20 устройства. При этом в блоке 17 памяти формируется матрица назначений. 3 ил.

1557569

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

АСУ.

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

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

Устройство содержит (фиг.1) с пер- 15

:3 вого по третий регистры 1, 2 и 3 соответственно, кольцевой регистр 4 сдвига, первый и второй блоки S и 6 элементов И, с первого по четвертый элементы 7-10 задержки, первый и вто- 20 рой счетчики 11 и 12, второй, третий и первый элементы ИЛИ 13, 14 и 15 соответственно, блок 16 сравнения, блок 17 памяти, дешифратор 18, вход

19 начальной установки устройства, тактовый вход 20 устройства, информационный вход 21 устройства, вход 22 чтения устройства, информационный выход 23 устройства и выход 24 признака окончания работы устройства.

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

Пусть необходимо решить задачу назначения для матрицы стоимости, показаннои на фиг.2.

Сигнал, подаваемый на вход 19, устанавливает в нулевое состояние регистры 2,3 и 4 и счетчики 11 и 12.

На вход 21 последовательно во времени поступают коды элементов матрицы стоимости, начиная с первого

40 элемента первого столбца-С11. По сигналу, подаваемому на вход 20, код элемента принимается в регистр 1.Сигнал единичного уровня с инверсного выхода первого триггера регистра 4 разрешает прохождение кода С11 через блок 5 элементов И на вход блока 16 сравнения и информационный вход регистра 2. Синхронизирующий сигнал, задержанный элементом 8 задержки, разрешает сравнение, Поскольку С11=6 > О, на выходе признака "Больше" блока 16 появляется сигнал единичного уровня, поступающий на суммирующий вход счетчика 12 через элемент ИЛИ 14, на вход 55 признака записи регистра 2 и на вход признака сдвига регистра 4. Этот же сигнал. задержанный элементом 9, разрешает запись содержимого счетчика 12 (на первом шаге это 1) в регистр 3.

Код с выхода регистра 3 преобразуется дешифратором в позиционный код

1000, поступающий на входы блока 6 элементов И. Сигнал нулевого уровня с выхода элемента 10 задержки не раз решает прохождение позиционного кода ереэ блок 6 элементов И.

Второй элемент столбца С21 анало-

1 гично рассмотренному выше поступает на вход регистра 2 и блока 16, где сравнивается с элементом С 11 ° Поскольку (;11 ) C?1, 6>4, сигнал единичного уровня образуется на выходе признака "Не больше" блока 16 и поступает на суммирующий вход счетчика 12 и вход признака сдвига регистра 4.

Аналогично на третьем и четвертом шаге устройство анализирует значения элементов С31 и С41, После сравнения элемента С41 на выходе счетчика 12 появляется сигнал переполнения единичного уровня, который разрешает прохождение позиционного кода 1000 через блок 6 элементов И на информационный вход блока 17 па1 мяти и на входы регистра 4. Этот же сигнал поступает на суммирующий вход счетчика 11, обеспечивая выбор первого адреса, куда и произойдет запись позиционного кода по задержанному в элементе 7 сигналу. Кроме того, сиг нал признака переполнения с выхода счетчика 12 устанавливает регистр 2 в нулевое состояние, а задержанный элементом 7 обнуляет регистр 3 и счетчик 12, На этом цикл обработки столбца матрицы стоимости заканчивается.

Работа во втором цикле с элементами матрицы С12,С22,С32,С42 происходит аналогично. Отличие заключается в том, что из сравнения будет исключен элемент С12, так как код "1", записанный в первый триггер регистра 4, обеспечит наличие на его инверсном выходе сигнала нулевого уровня, запрещающего прохождение кода С12 через блок 5 элементов И. Наличие кольцевой связи в регистре 4 обеспечит перезапись на втором mare работы устройства кода "1" из первого в последний триггер указанного регистра 4. На каждом иэ последующих шагов код сдвигается на позицию.

К концу обработки второго столбца (на четвертом шаге второго цикла рабо57569

15 ты устройства) в регистр 2 будет записан элемент 042=7, а в регистр 3номер его позиции — 4, который в виде позиционного кода 0001 будет записан по сигналу переполнения по второму адресу блока 17 и в регистр 4. Цикл обработки заканчивается.

В третьем цикле записанный в регистре 4 позиционный код 1001 исключит из процесса анализа элементы С13, С43 матрицы стоимости. Результат работы устройства — позиционный код

0100 — запишется по третьему адресу блока 17 и в регистр 4.

В четвертом цикле записанный в регистре 4 позиционный код 1101 исключит из процесса анализа элементы С14, С24, С44 матрицы стоимости. Результат работы устройства — позиционный код

0010 — запишется по четвертому адресу блока 17 и в регистр 4. На выходе 24 появляется сигнал окончания работы единичного уровня, В блоке 17 памяти содержится матрица назначения Х (фиг.3).

Чтение из блока 17 можно выполнять по окончании или в процессе работы устройства (построчно во время сравнения).

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

Устройство для решения транспортных задач линейного программирования, содержащее три регистра, ПЕРвый блок элементов И, блок сравнения, блок памяти, первый счетчик и первый элемент задержки, причем информационный вход устройства подключен к информационному входу первого регистра, выход которого подключен к информационному входу первого блока элементов И, выход которого подключен к первому информационному входу блока сравнения, выход второго регистра подключен к второму информационному входу блока сравнения, выход первого элемента задержки подключен к входу признака записи блока памяти, вход начальной установки устройства подключен к входу установки в "0" первого счетчика, выход которого подключен к адресному входу блока. памяти, выход которого является информационным выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат при решении задачи назначения методом максимальной строки (столбца), в него введены кольцевой регистр сдвига, с второго по четвертый элементы задержки, три элемента

ИЛИ, второй счетчик, второй блок элементов К и дешифратор, причем вход начальной установки устройства подключен к входу начальной установки кольцевого регистра, первым входам первого и второго элементов ИЛК, вы1ð ход последнего подключен к входу установки в "О" второго регистра, тактовый вход устройства подключен к входу признака записи первого регистра и входу второго элемента эадерж15 ки, выход которого подключен к входу опроса блока сравнения, выход признака "Больше" которого подключен к первому входу третьего элемента КЛИ, входу признака записи второго регистра

20 и входу третьего элемента задержки, выход которого подключен к входу признака записи третьего регистра, выход признака "Не больше" блока сравнения подключен к второму входу третьего

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

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

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

50 к второму входу второго элемента КЛИ, суммирующему входу первого счетчика входам четвертого элемента задержки и первого элемента задержки, выход которого подключен к второму входу первого элемента ИЛИ, выход котоРого подключен к входам установки в "0" второго счетчика и третьего регистра, выход четвертого элемента задержки подключен к управляющему входу второ1557569 ся выходом признака окончания работы устройства.

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

Редактор А.Лежнина Техред Л.Олийнык Корректор И.Ревская

Тираж 562

Заказ,718

Подписное

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

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

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

ro блока элементов И, выход признака переполнения первого счетчика являетФ 5 3

O» >

Фи 2

1 0 0 0

0 д 1 д

Р 0 0 1

0 1 n g