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

 

Устройство относится к вычислительной технике и может быть использовано в качестве специализированного вычислителя для решения задач назначения и транспортных задач в системах распределенной обработки АСУ. Цель изобретения - расширение области применения за счет обеспечения решения транспортной задачи линейного программирования общего вида. Для этого в устройство введены три блока памяти, два сумматора, четыре блока элементов И, три блока элементов ИЛ И, два регистра, а также логические элементы и элементы задержки. 5 ил.

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

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

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

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОспАтент сссР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ """ и4Д

1 «!

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4901026/24 (22) 09.01.91 (46) 07,05.93. Бюл. М 17, (72) В.E.Êîçëoâ, А.А.Панченко и А.Ю, Северьянов (56) Авторское свидетельство СССР

М 732857, кл, G 06 F 7/04, 1977.

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

% 1557569, кл, G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ТРАНС-, ПОРТНЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ а

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

Цель изобретения — расширение функциональных возможностей, На фиг. 1 представлена структурная схема устройства для решения транспортных задач линейного программирования; на фиг. 2 — пример матрицы стоимости перевозок для размерности m x n = 4 х 4 и результаты работы устройства по циклам; на фиг.

3 — матрица распределения перевозок; на фиг. 4 — пример матрицы стоимости для размерности и х п = 4 х 4 и результаты работы устройства по циклам; на фиг. 5 — матрица назначения, Устройство для решения транспортных задач линейного программирования (фиг. 1) содержит с первого по пятый регистры 1;..5, кольцевой регистр сдвига 6, блок 7 сравне. Ж„„1814082 А1 (57) Устройство относится к вычислительной технике и может быть использовано в качестве специализированного вычислителя для решения задач назначения и транспортных задач в системах распределенной обработки АСУ. Цель изобретения — расширение области применения за счет обеспечения решения транспортной задачи линейного программирования общего вида. Для этого в устройство введены три блока памяти, два сумматора, четыре блока элементов И, три блока элементов

ИЛИ, два регистра, а также логические элементы и элементы задержки. 5 ил. е ния, первый 8 и второй 9 счетчики, с первого Я по пятый блоки элементов И 10...14, с первого потретий блоки элементов ИЛИ 15„,17, блоки памяти значений потребностей 18, 1 матрицы назначений 19, матрицы стоимо- Q) сти 20 и значений запасов 21, первый 22 и второй 23 сумматоры, дешифратор 24, с пер- д вого по шестой элементы И 25...30, с первого по четвертый элементы ИЛИ 31...34, с первого по восьмой элементы задержки О© 35...42, вход 43 начальной установки, с пер- 1Я вого по третий информационные входы

44...46, с первой по шестую адресные шины

47...52, входы записи 53 и чтения 54, вход 55 режима транспортной задачи, вход 56 режима задачи назначения, вход "1" 57, тактовый вход 58, выход 59 признака окончания работы, информационный выход 60, пятый 61 и шестой 62 элементы ИЛИ, вход "0" 63.

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

3 е

55 тов И являются информационным выходом блока.

Блоки элементов ИЛИ состоят из двухвходовых элементов ИЛИ, первые входы которых.являются первым входом блока, вторые входы — вторым входом блока, а выходы — выходом блока.

Устройство работает в одном из двух режимов: транспортной задачи {ТЗ) и задачи назначения (ЗН). Суть его работы заключается в реализации метода минимального элемента стройки (столбца) матрицы стоимости перевозок для режима ТЗ и метода максимального элемента строки (столбца) матрицы стоимости для режима ЗН. Поскольку для существования решения в первом случае необходимым условием задачи является ее и П) сбалансирован ность (Z а = Х b>), этот факт

l=1 l=1 должен быть учтен на предварительном этапе путем введения фиктивного потребителя (или склада) с потребностью (или запасом), определяемой как соответствующая рази П\ ность запасов Z а и потребностей Х Ь) и

I =1 1=1 нулевой стоимости перевозки. Размерность транспортной задачи может быть произвольной, не превышающей N x N, где Й— предельное значение размерности матрицы, определяющее объем блоков памяти, регистров, значение модуля счетчиков, Второй режим .можно рассматривать для случая задания а = b; = 1,n=m.

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

В блоки памяти 20, 18, 21 под воздействием сигналов записи, подаваемых на вход

53, засылается информация: элементы матрицы стоимости С, поступающие на вход 44 и сопровождаемые номерами строки (шина 47) и столбца (шина 48); значения запасов al, поступающие на вход 46 по номеру строки (шина 50); значения потребностей Ь;, поступающие на вход 45 по номеру столбца (шина 49).

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

Сигнал, подаваемый на вход 43, устанавливает регистры 4, 6 в нулевое состояние, счетчик 9 — в единичное состояние.

Пройдя через элемент ИЛИ 33, этот сигнал устанавливает регистр 3 в нулевое, а счетчик

8 в единичное состояние. Этот же сигнал, пройдя через элемент ИЛИ 32 и стробированный элемент И 29, установит в единичное

t состояние триггеры регистра 2, обеспечив запись максимально представимого числа.

Дальнейшая работа устройства происходит под действием серии из тактовых им5 . пульсов (ТИ), подаваемых на вход 58, в N циклах, Временная диаграмма работы устройства формируется последовательностью ТИ . и элементами задержки, "0 Под действием ТИ, поступающего на, вход чтения блока 20, в регистр 1 записывается код элемента с 1 матрицы С. С выхода этого регистра код поступает на первый вход блока 7 и информационный вход реги15 стра 2. ТИ, задержанный элементом 36, поступает на первый вход элемента И 25, стробируемого сигналом с инверсного выхода старшего разряда регистра 6 (в котором в начале первого цикла содержится позиционный код 0000); сигнал с выхода

° элемента И 25 разрешает сравнение. Поскольку с < = 6 < (2 -1), где k — разрядность

k операндов (элементов матрицы стоимости, запасов и потребностей), на выходе "мень25 ше" блока 7 появляется сигнал единичного уровня, проходящий через стробированный

И 27 и элемент ИЛИ 31 и разрешающий запись в регистр 2 содержимого регистра 1 (с1 ) и в регистр 3 содержимого счетчика 8—

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

10 элементов И. Сигнал нулевого уровня с выхода элемента задержки 35 не разрешает прохождение позиционного кода через блок 10.

Тактовый импульс, задержанный элементом 42, поступает на суммирующий вход

40 счетчика 8 и вход признака сдвига регистра

6, обеспечивая перезапись кода из триггера старшего разряда в триггер младшего разряда указанного регистра.

Аналогично на каждом из последующих

45 тактов код в регистре 6 сдвигается на позицию.

На этом первый такт работы устройства заканчивается.

На втором такте элемент строки с12 аналогично рассмотренному выше поступает на вход регистров 1 и 3 и блока 7, где сравнивается с элементом с», Поскольку с12 =4<

< c» = 6, на выходе "Меньше" блока 7 появляется сигнал единичного уровня. В регистр

2 записывается код с12, в регистр 3 — номер позиции минимального элемента строки.

Позиционный код 0100, поступающий с выхода дешифратора на вход блока 10. на его выход не проходит, т,к. на выходе элемента задержки 35 сигнал нулевого уровня.

Второй такт работы устройства заканчивается аналогично рассмотренному вы- 5 ше.

На третьем такте элемент с1з сравнивается с элементом с12, код которого записан в регистре 2. Поскольку c13 = 5 > G12 = 4, на выходе "Больше" блока 7 появляется сигнал 10 единичного уровня, поступающий на второй вход элемента И 26, на первом входе которого нулевой уровень режима 3Н. Запись в регистры 2 и 3 не произойдет. Такт работы устройства заканчивается аналогично рас- 15 смотренному выше.

На четвертом (последнем) такте элемент си сравнивается с элементом с1г. Поскольку си = 3 < с1г = 4, на выходе "Меньше" блока 7 появляется сигнал единичного уров- 20 ня. В регистр 2 запишется код минимального элемента с14, а в регистр 3 — номер его позиции, преобразуемый дешифратором в позиционный код 0001, Последний такт работы устройства не- 25 сколько отличается от предыдущих.

Тактовый импульс, задержанный элементом 42, сдвигает регистр 6 в исходное состояние и вызывает переполнение счет,чика 8. Сигнал с выхода признака перепол- 30 нения счетчика поступает на входы элементов задержки 37; 39, через элемент

ИЛИ 32 и стробированный элемент И 29 на установку в единичное состояние триггеров регистра 2, а также на входы признака чте- 35 ния блоков памяти 18 и 21. Из этих блоков на входы сумматора 23 поступят соответственно инвертированный код потребности

b4 = 2 и код запаса а1 = 7 (соответствующие позиции минимального элемента строки), 40 выбранные по адресам, поступающим с выхода регистра 3 и счетчика 9. В сумматоре

23 вы полнится сложение кодов Ь4,а1 и единицы младшего разряда (для образования дополнительного кода результата), пос у- 45 пающей н вход 57. Результат сложения

Л а — b1=7-2=5 запишется в регистр 5. Поскольку знак результата положителен, с инверсного выхода триггера старшего разряда регистра 5 снимается сигнал еди- 50 ничного уровня. Этот сигнал разрешает прохождение кода остатка А= и через блок 13 элементов И на вход блока 21 памяти и, задержанный элементом 41, его запись (через элемент ИЛИ 62). 55

Этот же сигнал, задержанный элементом 35, разрешает прохождение позиционного кода через блок 10 на вход установки в

"1" разрядов информационного слова реги- . стра 6; в регистр окажется записанным код

82 6

Ф

0001. Этим же сигналом стробируется блок

11 элементов И, обеспечивая прохождение кода b4 = 2 через блок 15 элементов ИЛИ на информационный вход регистра 43. на вход признака записи которого поступает сигнал с выхода признака переполнения сумматора 8, задержанный элементом 39. Код Ь4 с выхода регистра 4 поступает на вход блока

19 памяти и записывается по адресу, соответствующему положению минимального элемента строки (с выхода регистра 3 через блок 16 элементов .ИЛИ на вход второго адреса (столбца); с выхода счетчика 9 через блок 47 элементов ИЛИ на вход первого адреса(строки) блока (19), по сигналу, поступающему на вход признака записи блока 19 с выхода элемента 37 задержки. Этот же сигнал, пройдя через элемен ИЛИ 33, устанавливает счетчик 8 в единичное, а регистр

3 в нулевое состояние.

На этом первый цикл работы устройства заканчивается.

Результаты работы устройства по циклам отражены на фиг. 2 в таблицах справа (для запасов ai) и снизу(для потребностей Ь1) от матрицы С стоимости перевозо .

Работа во втором, цикле с элементами матрицы с11, с1г, с13, с14 происходит аналогично. Отличие заключается в том, что из сравнения будет исключен элемент с14, т.к.

"1", записанная в четвертый триггер регистра 6, обеспечит наличие на инверсном выходе его старшего разряда на четвертом такте работы устройства сигнала нулевого уровня, не разрешающего прохождения ТИ, задержанного элементом 36, через элемен И

25 на блок 7. Минимальным элементом в данном случае окажется элемент сп. На вход установки в "1" разрядов информационного слова регистра 6 поступит код 0100, В регистре окажешься записанным код 0101.

На входы сумматора 23 поступят коды a> = 5 и Ьг = 5; на выходе сумматора — результат

Л= О. В отличие от предыдущего цикла, этот . результат, поступая на входы элемента И 30 в виде инвертированного кода Ь, вызывает появление на выходе элемента ИЛИ 34 сигнала единичного уровня. Этот сигнал, задержанный элементом 39 до окончания процесса записи в блок 19 значения Ьг - 5 по адресу минимального элемента (си), поступит на суммирующий вход счетчика,9.

В следующем цикле устройство будет обрабатывать вторую строку.

В третьем цикле из сравнения будут исключены элементы сгг и сг4. Результаты ра-. боты устройства: значение элемента bi - 3, записанное в блок 19 на позицию мини7

1814082

10

25

35

45

55 м ального элемента сг; позиционный код

1101 — в регистре 6; аг = 1.

В четвертом цикле из сравнения будут исключены элементы с21 сг2и с24 На входы сумматора 23 поступают коды а2 = 1 и Ьз = 4.

На выходе сумматора — результат Л= - 3.

Работа устройства в этом случае отличается от рассмотренных в предыдущих циклах. Сигнал единичного уровня с прямого выхода триггера старшего разряда регистра

5 разрешает прохождение кода аг через блок 12 элементов И на вторые входы блока

15 элементов ИЛИ и далее через регистр 4 на вход блока 19; этот же сигнал разрешает прохождение инвертированного кода результата Л через блок 14 элементов И на первый вход сумматора 22, где происходит преобразование йнвертированного дополнительного кода результата путем сложения с "О" и добавления к его младшему разряду единицы, поступающей по входу 57, и запись в виде значения iba =3 в блок 18 этим же сигналом, задержанным элементом 40 (через элемент ИЛИ 61); этот же сигнал, пройдя через элемент ИЛИ 34 и элемент 38 задержки, добавляет единицу в счетчик 9.

В последующих циклах устройство работает аналогично. Признаком ркончания работы устройства является наличие сигнала единичного уровня йа выходе 59

Результат работы устройства — матрица назначения Х (фиг, 3) — содержится в блоке

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

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

В блоки памяти 20, 18, 21 аналогично рассмотренному выше засылаются элементы матрицы стоимости, значения. запасов и потребностей а = b = 1.

Для реализации режима решения задачи назначения на вход 56 подается сигнал единичного уровня, стробирующий элементы И 26,28.

Сигнал, подаваемый на вход 43, в отличие от рассмотренного выше, проходит через элемент ИЛИ 32 и стробированный элемент И 28 и устанавливает триггеры регистра 2 в нулевое состояние. Работа устройства практически не отличается от рассмотренной выше.

В первом такте происходит сравнение элемента с11 с "0", записанным в регистр 2.

Поскольку с11 = 6 > О, на выходе "Больше" ."Больше" блока 7 появляется сигнал еди- ничного уровня, проходящий через стробированный элемент И 26 и элемент ИЛИ 31 и разрешающий запись содержимого регистра 1 в регистр 2 и содержимого счетчика 8 в регистр 3, Во втором, третьем и четвертом тактах содержимое регистров 2 и 3 не изменяетсяя, т.к. с 12 < c11, c13 < с11, с i4 < с11. Сигнал с выхода признака переполнения счетчика 8 разрешает чтение из блоков 18. 21 соответственно Ь1 и а1. Поскольку а1 = b>, т.е. Л= О, цикл работы устройства заканчивается записью в блок 19 значения b> = 1 по адресу максимального элемента с1 строки, записью в регистр 6 позиционного кода 1000 и увеличением на единицу содержимого счетчика 9, На втором цикле работы устройства (обработка второй строки) из сравнения будет исключен с21. Максимальный элемент — czj, Результаты работы устройства на второц цикле; значение "1", записанное в блок 1ф по адресу максимального элемента; позиционный код 1010 в регистре 6; увеличенно® на единицу содержимого счетчика 9.

В следующих двух циклах устройствЕ работает аналогично. Результаты его работы по циклам определены на фиг. 4 в таблицах справа и снизу от матрицы С, Результат решения задачи назначения — матрица назначения X (фиг, 5) — может считываться по окончании или в процессе работы устройства — построчно по окончании обработки строки (цикла устройства).

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

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

1814082

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

ИЛИ, о т л и ч а ю щ е е с я тем,"что, с целью расширения области применения путем

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

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

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

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

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

ЗО которого подключен к входу признака запишестого элементов И, вторые входы которых подключены соответственно к входу режима задачи назначения устройства, к первому входу третьего элемента И и к вхо15 ду режима транспортной задачи, к первому входу четвертого элемента И, а выходы— соответственно к первому и второму входам первого элемента ИЛИ, выход которого подключен к входу признака записи третьего

20 регистра и к входу признака записи второго

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

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

1814082

12 элементов И, к второму информационному входу второго сумматора, выход которого . подключен к входу пятого регистра, вход переноса. — к входу "1" устройства и к входу переноса первого сумматора, первый информационный вход которого подключен к входу "О" устройства, второй информационный вход- к выходу пятого блока элементов

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

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

10 вход которого подключен к выходу первого элемента задержки, 1814082

4июы

0 5 д Г .7 0 / д

0 д 1 0 д

Ю,ЮЮ

0 Ю 1 Ю

0 Ю

Ю 7

Составитель В, Козлов

Техред ММоргентал

Корректор: А. Мотыль

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

Заказ 1827 Тираж Подписное

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

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