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

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

Цель изобретения - расширение функциональных возможностей.

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

Устройство для решения транспортных задач линейного программирования (фиг. 1) содержит с первого по пятый регистры 1...5, кольцевой регистр сдвига 6, блок 7 сравнения, первый 8 и второй 9 счетчики, с первого С по пятый блоки элементов И 10...14, с первого по третий блоки элементов ИЛИ 15...17, блоки памяти значений потребностей 18, матрицы назначений 19, матрицы стоимости 20 и значений запасов 21, первый 22 и второй 23 сумматоры, дешифратор 24, с первого по шестой элементы И 25...30, с первого по четвертый элементы ИЛИ 31...34, с первого по восьмой элементы задержки 35...42, вход 43 начальной установки, с первого по третий информационные входы 44...46, с первой по шестую адресные шины 47...52, входы записи 53 и чтения 54, вход 55 режима транспортной задачи, вход 56 режима задачи назначения, вход 1 57, тактовый вход 58, выход 59 признака окончания работы, информационный выход 60, пятый 61 и шестой 62 элементы ИЛИ, вход О 63.

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

ю

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

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

Устройство работает в одном из двух режимов: транспортной задачи (ТЗ) и задачи назначения (ЗН). Суть его работы заключается в реализации метода минимального элемента стройки (столбца) матрицы стоимости перевозок для режима ТЗ и метода максимального элемента строки (столбца) матрицы стоимости для режима ЗН. Поскольку для существования решения в первом случае необходимым условием задачи является ее s nm .- сбалансированность а - 2 bj),этот факт

i 1

должен быть учтен на предварительном этапе путем введения фиктивного потребителя (или склада) с потребностью (или запасом), определяемой как соответствующая разnmность запасов 2 ai и потребностей Sbjn

1 нулевой стоимости перевозки. Размерность транспортной задачи может быть произвольной, не превышающей N х N, где N - предельное значение размерности матрицы, определяющее объем блоков памяти, регистров, значение модуля счетчиков,

Второй режим .можно рассматривать для случая задания ai bj 1 ,.

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

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

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

На вход 55 подается сигнал единичного уровня, стробирующий элементы И 27, 29.

Сигнал, подаваемый на вход 43, устанавливает регистры 4, 6 в нулевое состояние, счетчик 9 - в единичное состояние. Пройдя через элемент ИЛИ 33, этот сигнал устанавливает регистр 3 в нулевое, а счетчик 8 в единичное состояние. Этот же сигнал, пройдя через элемент ИЛИ 32 и стробиро- ванный элемент И 29. установит в единичное

состояние триггеры регистра 2, обеспечив запись максимально предстэвимого числа. Дальнейшая работа устройства происходит под действием серии из тактовых импульсов (ТИ)°, подаваемых на вход 58, в N циклах,

Временная диаграмма работы устройства формируется последовательностью ТИ и элементами задержки,

Под действием ТИ, поступающего на вход чтения блока 20, в регистр 1 записывается код элемента си матрицы С. С выхода этого регистра код поступает на первый вход блока 7 и информ ационный вход регистра 2. ТИ, задержанный элементом 36, поступает на первый вход элемента И 25, стробируемого сигналом с инверсного выхода старшего разряда регистра 6 (в котором в начале первого цикла содержится

позиционный код 0000); сигнал С выхода элемента И 25 разрешает сравнение. Поскольку си 6 (2k-1), где k - разрядность операндов (элементов матрицы стоимости, запасов и потребностей), на выходе меньше блока 7 появляется сигнал единичного уровня, проходящий черезстробированный И 27 и элемент ИЛИ 31 и разрешающий запись в регистр 2 содержимого регистра 1 (си) и в регистр 3 содержимого счетчика 8 адреса минимального элемента строки. Код с выхода регистра 3 преобразуется дешифратором 24 в позиционный код 1000, поступающий на информационный вход блока 10 элементов И. Сигнал нулевого уровня с

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

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

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

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

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

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

На втором такте элемент строки С12 аналогично рассмотренному выше поступает на вход регистров 1 и 3 и блока 7, где сравнивается с элe seнтoм ci 1. Посколькуci2 4 си 6, на выходе Меньше блока 7 появляется сигнал единичного уровня. В регистр 2 записывается код с12, в регистр 3 - номер позиции минимального элемента строки. Позиционный код 0100, поступающий с выхода дешифратора на вход блока 10. на его

выход не проходит, т.к. на выходе элемента задержки 35 сигнал нулевого уровня.

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

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

На четвертом (последнем) такте элемент см сравнивается с элементом сп. Поскольку си 3 С12 4, на выходе Меньше блока появляется сигнал единичного уровня. В регистр 2 запишется код минимального элемента ci4, а в регистр 3 - номер его позиции, преобразуемый дешифратором в позиционный код 0001.

Последний такт работы устройства несколько отличается от предыдущих.

Тактовый импульс, задержанный элементом 42, сдвигает регистр 6 в исходное состояние и вызывает переполнение счет- чика 8. Сигнал с выхода признака перепол- нения счетчика поступает на входы элементов задержки 37, 39, через элемент ИЛИ 32 и стробированный элемент И 29 на установку в единичное состояние триггеров регистра 2, а также на входы признака чтения блоков памяти 18 и 21. Из этих блоков на входы сумматора 23 поступят соответственно инвертированный код потребности D4 . 2 и код запаса ai 7 (соответствующие позиции минимального элемента строки), выбранные по адресам, поступающим с выхода регистра 3 и счетчика 9. В сумматоре 23 выполнится сложение кодов b4,ai и единицы младшего разряда (для образования ополнительного кода результата), поступающей н вход 57. Результат сложения ai-bi 7-2 5 запишется в регистр 5, Поскольку знак результата положителен, с инверсного выхода триггера старшего разряда регистра 5 снимается сигнал единичного уровня. Этот сигнал разрешает прохождение кода остатка Д Ai через лок 13 элементов И на вход блока 21 паяти и, задержанный элементом 41, его апись (через элемент ИЛИ 62).

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

0001. Этим же сигналом стробируется блок 11 элементов И, обеспечивая прохождение кода Ь 4 2 через блок 15 элементов ИЛИ на

5 информационный вход регистра 43, на вход признака записи которого поступает сигнал с выхода признака переполнения сумматора 8, задержанный элементом 39. Код Ь4 с выхода регистра 4 поступает на вход блока

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

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

0 навливает счетчик 8 в единичное, а регистр

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

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

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

Работа во втором, цикле с элементами

0 матрицы cii, ci2, ci3, ci4 происходит аналогично. Отличие заключается в том, что из сравнения будет исключен элементен, т.к. 1, записанная в четвертый триггер регистра 6, обеспечит наличие на инверсном выхо5 де его старшего разряда на четвертом такте работы устройства сигнала нулевого уровня, не разрешающего прохождения ТИ, задержанного элементом 36, через элемент И .25 на блок 7. Минимальным элементом в

0 данном случае окажется элемент С12. На вход установки в 1 разрядов информационного слова регистра 6 поступит код 0100. В регистре окажется записанным код 0101. На входы сумматора 23 поступят коды ai 5

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

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

В третьем цикле из срав нения будут исключены элементы С22 и С24. Результаты работы устройства: значение элемента bi « 3, записанное в блок 19 на позицию минимального элемента С2; позиционный код 1101-в регистре 6; Э21 1.

В четвертом цикле из сравнения будут исключены элементы С21, C22vi С24. На входы сумматора 23 поступают коды Э21 1 и Ьз 4. На выходе сумматора - результат Д - 3.

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

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

Результат работы устройства - матрица назначения X (фиг. 3) - содержится в блоке 19. Чтение из блока 19 можно выполнять по окончании или в процессе работы построчно по окончании обработки одной строки.

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

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

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

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

В первом такте происходит сравнение элемента си с О, записанным в регистр 2. Поскольку си 6 0, на выходе Больше Больше блока 7 появляется сигнал еди- ничного уровня, проходящий через стробированный элемент И 26 и элемент ИЛИ 31 и

разрешающий запись содержимого регистра 1 в регистр 2 и содержимого счетчика 8 в регистр 3. Во втором, третьем и четвертом тактах содержимое регистров 2 и 3 не изменяется,т.к.,,. Сигнал с выхода признака переполнения счетчика 8 разрешает чтение из блоков 18, 21 соответственно bi и ai. Поскольку ai bi, т.е. Дг О, цикл работы устройства4 заканчивается записью в блок 19 значения bi 1 по адресу максимального элемента си строки, записью в регистр 6 позиционного кода 1000 и увеличением на единицу содержимого счетчика 9.

На втором цикле работы устройства (обработка второй строки) из сравнения будет исключен С21. Максимальный элемент - С23. Результаты работы устройства на второ цикле: значение 1, записанное в блок ||

по адресу максимального элемента; позиции онный код 1010 в регистре 6; увеличенное на единицу содержимого счетчика 9.

В следующих двух циклах устройству работает аналогично. Результаты его работы по циклам определены на фиг. 4 б таблицах справа и снизу от матрицы С.

Результат решения задачи назначения - матрица назначения X (фиг, 5) - может считываться по окончании или в процессе

работы устройства - построчно по окончании обработки строки (цикла устройства).

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

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

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

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

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

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

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

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

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

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

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

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

0

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

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

fur. f