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

:й,6,Цц,Ч И К 17,анченко и А.Ю,Северьдетельство СССР Р 7/04, 1977.детельство СССР 6 Г 15/20, 1988. ЛЯ РЕШЕНИ ЛИНЕЙНО Н-, СРГОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВОСССР(54) УСТРОЙСТВОПОРТНЫХ ЗАДАГРАММИРОВАНИ фИзобретение относится к вычислительной технике и может быть использовано в качестве специализированного вычислителя для решения задач назначения и транспортных задач в системах распределенной обработки АСУ.Цель изобретения - расширение функциональных возможностей,На фиг. 1 представлена структурная схема устройства для решения транспортных задач линейного программирования; на фиг. 2 - пример матрицы стоимости перевозок для размерности и) х и = 4 х 4 и результаты работы устройства по циклам; на фиг.3 - матрица распределения перевозок; на фиг. 4 - пример матрицы стоимости для размерности и х п = 4 х.4 и результаты работы устройства по циклам; на фиг. 5 - матрица назначения,Устройство для решения транспортных задач линейного программирования (фиг. 1) содержит с первого по пятый регистры 1;5, кольцевой регистр сдвига 6, блок 7 сравне(57) Устройство относится к вычислительной технике и может быть использовано в качестве специализированного вычислителя для решения задач назначения и транспортных задач в системах распределенной обработки АСУ. Цель изобретения - расширение области применения за счет обеспечения решения, транспортной задачи линейного программирования общего вида. Для этого в устройство введены три блока памяти, два сумматора, четыре блока элементов И, три блока элементов ИЛИ, два регистра, а также логические элементы и элементы задержки. 5 ил. ния, первый 8 и второй 9 счетчики, с первого Я по пятый блоки элементов И 1014, с первого потретий блоки элементов ИЛИ 15,17, блоки памяти значений потребностей 18, 1 матрицы назначений 19, матрицы стоимо- ( сти 20 и значений запасов 21, первый 22 и второй 23 сумматоры, дешифратор 24, с пер- д вого по шестой элементы И 2530, с первого по четвертый элементы ИЛИ 3134, спервого по восьмой элементы задержки ф3542, вход 43 начальной установки, с пер Я ваго по третий информационные входы 4446, с первой по шестую адресные шины 4752, входы записи 53 и чтения 54, вход 55 режима транспортной задачи, вход 56 режима задачи назначения, вход "1" 57, тактовый вход 58, выход 59 признака окончания работы, информационный выход 60, пятый 61 и шестой 62 элементы ИЛИ, вход "0" 63.Блоки элементов И состоят из двухвходовых элементов И, первые входы которых являются информационным входом блока, а вторые входы объединены и являются управляющим входом блока, выходы элемен1814082 3е 50 55 тов И являются информационным выходом блока.Блоки элементов ИЛИ состоят из двухвходовых элементов ИЛИ, первые входы которых.являются первым входом блока, вторые входы - вторым входом блока, а выходы - выходом блока.Устройство работает в одном из двух режимов: транспортной задачи (ТЗ) и задачи назначения (3 Н). Суть его работы заключается в реализации метода минимального элемента стройки (столбца) матрицы стоимости перевозок для режима ТЗ и метода максимального элемента строки (столбца) матрицы стоимости для режима ЗН, Поскольку для существования решения в первом случае необходимым условием задачи является ееф иП 3сбалансированность(Х а 1 = Х Ь), этот факт должен быть учтен на предварительном этапе путем введения фиктивного потребителя (или склада) с потребностью (или запасом), определяемой как соответствующая рази П ность запасов Х а и потребностей Х Ь) и1=1 1=1 нулевой стоимости перевозки. Размерность транспортной задачи может быть произвольной, не превышающей И х Й, где Й - предельное значение размерности матрицы, определяющее объем блоков памяти, регистров, значение модуля счетчиков,Второй режим .можно рассматривать для случая задания а = Ь; = 1,д=т,Устройство работает следующим образом.В блоки памяти 20, 18, 21 под воздействием сигналов записи, подаваемых на вход 53, засылается информация: элементы матрицы стоимости С, поступающие на вход 44 и сопровождаемые номерами строки(шина 47) и столбца (шина 48); значения запасов аь поступающие на вход 46 по номеру строки(шина 50); значения потребностей Ь;, поступающие на вход 45 по номеру столбца (шина 49). Пусть необходимо решить транспортную задачу для матрицы стоимости перевозок, приведенной на фиг, 2,На вход 55 подается сигнал единичного уровня, стробирующий элементы И 27, 29.Сигнал, подаваемый на вход 43, устанавливает регистры 4, 6 в нулевое состояние, счетчик 9 - в единичное состояние. Пройдя через элемент ИЛИ 33, этот сигнал устанавливает регистр 3 в нулевое, а счетчик 8 в единичное состояние. Этот же сигнал, пройдя через элемент ИЛИ 32 и стробированный элемент И 29, установит в единичное состояние триггеры регистра 2, обеспечивзапись максимально представимого числа.Дальнейшая работа устройства происходит под действием серии из тактовых импульсов (ТИ), подаваемых на вход 58, в йциклах,Временная диаграмма работы устройства формируется последовательностью ТИ. и элементами задержки,10 Под действием ТИ, поступающего на,вход чтения блока 20, в регистр 1 записывается код элемента с 11 матрицы С. С выходаэтого регистра код поступает на первыйвход блока 7 и информационный вход реги 15 стра 2. ТИ, задержанный элементом 36, поступает на первый вход элемента И 25,стробируемого сигналом с инверсного выхода старшего разряда регистра 6 (в котором в начале первого цикла содержится20 позиционный код 0000); сигнал с выходаэлемента И 25 разрешает сравнение, Поскольку с 1 = 6(2 -1), где 1 - разрядностьоперандов (элементов матрицы стоимости,запасов и потребностей), на выходе "мень 25 ше" блока 7 появляется сигнал единичногоуровня, проходящий через стробированныйИ 27 и элемент ИЛИ 31 и разрешающийзапись в регистр 2 содержимого регистра 1(с 1) и в регистр 3 содержимого счетчика 8 -ЗО адреса минимального элемента строки, Кодс выхода регистра 3 преобразуется дешифратором 24 в позиционный код 1000, поступающий на информационный вход блока10 элементов И. Сигнал нулевого уровня с35 выхода элемента задержки 35 не разрешает прохождение позиционного кода черезблок 10,Тактовый импульс, задержанный элементом 42, поступает на суммирующий вход40 счетчика 8 и вход признака сдвига регистра6, обеспечивая перезапись кода из триггерастаршего разряда в триггер младшего разряда указанного регистра.Аналогично на каждом из последующих45 тактов код в регистре 6 сдвигается на позицию,На этом первый такт работы устройства заканчивается.На втором такте элемент строки с 12 аналогично рассмотренному выше поступает на вход регистров 1 и 3 и блока 7, где сравнивается с элементом с 1 ъ Поскольку с 12 =4с 11= 6, на выходе "Меньше" блока 7 появляется сигнал единичного уровня. В регистр 2 записывается код с 12, в регистр 3 - номер позиции минимального элемента строки. Позиционный код 0100, поступающий с выхода дешифратора на вход блока 10, на еговыход не проходит, т,к. на выходе элемента задержки 35 сигнал нулевого уровня.Второй такт работы устройства заканчивается аналогично рассмотренному вы ше.На третьем такте элемент с 1 з сравнивается с элементом с 12, код которого записан в регистре 2. Поскольку с 1 з= 5сц = 4, на выходе "Больше" блока 7 появляется сигнал 10единичного уровня, поступающий на второй вход элемента И 26, на первом входе которого нулевой уровень режима ЗН, Запись в регистры 2 и 3 не произойдет. Такт работы устройства заканчивается аналогично рас смотрен ному выше.На четвертом (последнем) такте элемент, с 14 сравнивается с элементом саар. Поскольку си = 3си = 4, на выходе "Меньше" блока 7 появляется сигнал единичного уров ня. В регистр 2 запишется код минимально- ф го элемента с 1 а, а в регистр 3 - номер его позиции, преобразуемый дешифратором в позиционный код 0001,Последний такт работы устройства не сколько отличается от предыдущих.Тактовый импульс, задержанный элементом 42, сдвигает регистр 6 в исходное состояние и вызывает переполнение счет,чика 8. Сигнал с выхода признака перепол нения счетчика поступает на входы элементов задержки 37; 39, через элемент ИЛИ 32 и стробированный элемент И 29 на установку в единичное состояние триггеров регистра 2, а также на входы признака чте ния блоков памяти 18 и 21. Из этих блоков на входы сумматора 23 поступят соответственно инвертированный код потребности Ь 4 = 2 и код запаса а 1 = 7 (соответствующие позиции минимального элемента строки), 40 выбранные по адресам, поступающим с выхода регистра 3 и счетчика 9. В сумматоре 23 выполнится сложение кодов Ь 4,а 1 и единицы младшего разряда (для образования дополнительного кода результата), посу пающей н вход 57, Результат сложения Ь=ф а 1 - Ь 1=7-2=5 запишется в регистр 5. Поскольку знак результата положителен, с инверсного выхода триггера старшего разряда регистра 5 снимается сигнал еди ничного уровня. Этот сигнал разрешает прохождение кода остатка А= Й через блок 13 элементов И на вход блока 21 памяти и, задержанный элементом 41, его запись (через элемент ИЛИ 62). 55Этот же сигнал, задержанный элементом 35, разрешает прохождение позиционного кода через блок 10 на вход установки в "1" разрядов информационного слова реги- . стра б; в регистр окажется записанным код 82 б0001. Этим же сигналом стробируется блок 11 элементов И, обеспечивая прохождение кода Ь 4 = 2 через блок 15 элементов ИЛИ на информационный вход регистра 43, на вход признака записи которого поступает сигнал с выхода признака переполнения сумматора 8, задержанный элементом 39. Код Ь с выхода регистра 4 поступает на вход блока 19 памяти и записывается по адресу, соответствующему положению минимального элемента строки (с выхода регистра 3 через блок 16 элементов .ИЛИ на вход второго адреса (столбца); с выхода счетчика 9 через блок 47 элементов ИЛИ на вход первого адреса(строки) блока (19), по сигналу, поступающему на вход признака записи блока 19 с выхода элемента 37 задержки. Этот же сигнал, пройдя через элемен ИЛИ 33, устанавливает счетчик 8 в единичное, а регистр 3 в нулевое состояние. На этомпервый цикл работы устройствазаканчивается.Результаты работы устройства по циклам отражены на фиг. 2 в таблицах справа(для запасов а) и снизу(для потребностей Ь)от матрицы С стоимости перевозо,Работа во втором, цикле с элементамиматрицы с 11, си, с 1 з, с 14 происходит аналогично. Отличие заключается в том, что изсравнения будет исключен элемент с 14, т.к."1", записанная в четвертый триггер регистра 6, обеспечит наличие на инверсном выходе его старшего разряда на четвертом тактеработы устройства сигнала нулевого уровня, не разрешающего прохождения ТИ, задержанного элементом 36, через элемент И25 на блок 7, Минимальным элементом вданном случае окажется элемент с 1 г. Навход установки в "1" разрядов информационного слова регистра 6 поступит код 0100,В регистре окажешься записанным код 0101.На входы сумматора 23 поступят коды а 1= 5и Ьг = 5; на выходе сумматора - результатЬ= О, В отличие от предыдущего цикла, этот .результат, поступая на входы элемента И 30в виде инвертированного кода Ь, вызываетпоявление на выходе элемента ИЛИ 34 сигнала единичного уровня, Этот сигнал, задержанный элементом 39 до окончанияпроцесса записи в блок 19 значения Ь 2 - 5по адресу минимального элемента (сц), поступит на суммирующий вход счетчика,9.В следующем цикле устройство будет обрабатывать вторую строку.В третьем цикле из сравнения будут исключены элементы си и со. Результаты работы устройства: значение элемента Ь 1- 3,записанное в блок 19 на позицию мини510 20 25 30 ао 45 50 м ального элемента с 2; позиционный код1101 - в регистре 6; а 2 = 1.В четвертом цикле из сравнения будут исключены элементы с 21, сг 2 и с 24. На входы сумматора 23 поступают коды а 2 = 1 и Ьз = 4. На выходе сумматора - результат Ь= - 3,Работа устройства в этом случае отличается от рассмотренных в предыдущих циклах. Сигнал единичного уровня с прямого выхода триггера старшего разряда регистра 5 разрешает прохождение кода а 2 через блок 12 элементов И на вторые входы блока 15 элементов ИЛИ и далее через регистр 4 на вход блока 19; этот же сигнал разрешает прохождение инвертированного кода результата Ь через блок 14 элементов И на первый вход сумматора 22, где происходит преобразование йнвертированного дополнительного кода результата путем сложения с "0" и добавления к его младшему разряду единицы, поступающей по входу 57, и запись в виде значения 1 Ьз=3 в блок 18 этим же сигналом, задержанным элементом 40 (через элемент ИЛИ 61); этот же сигнал,пройдя через элемент ИЛИ 34 и элемент 38 задержки, добавляет единицу в счетчик 9. В последующих циклах устройство работает аналогично. Признаком окончания работы устройства является наличие сигнала единичного уровня йа выходе 59 Результат работы устройства - матрица назначения Х (фиг, 3) - содержится в блоке 19. Чтение из блока 19 можно выполнять по окончании или в процессе работы построчно по окончании обработки одной строки Пусть необходимо решить задачу назначения для матрицы стоимости, приведенной на фиг. 4. В блоки памяти 20, 18, 21 аналогично рассмотренному выше засылаются элементы матрицы стоимости, значения запасов и потребностей а = Ь = 1,Для реализации режима решения задачи назначения на вход 56 подается сигнал единичного уровня, стробирующий элементы И 26,28.Сигнал, подаваемый на вход 43, в отличие от рассмотренного выше, проходит через элемент ИЛИ 32 и стробированный элемент И 28 и устанавливает триггеры регистра 2 в нулевое состояние, Работа устройства практически не отличается отрассмотренной выше. В первом такте происходит сравнение элемента с 11 с "0", записанным в регистр 2. Поскольку с 11 = 6О, на выходе "Больше" ."Больше" блока 7 появляется сигнал еди- ничного уровня, проходящий через стробированный элемент И 26 и элемент ИЛИ 31 и разрешающий запись содержимого регистра 1 в регистр 2 и содержимого счетчика 8 в регистр 3, Во втором, третьем и четвертом тактах содержимое регистров 2 и 3 не изменяется, т.к. с 12с 11, с 1 зс 11, с 14с 11. Сигнал с выхода признака переполнения счетчика 8 разрешает чтение из блоков 18. 21 соответственно Ь 1 и а 1. Поскольку а 1 = Ь 1, т.е. Ь= О, цикл работы устройствазаканчивается записью в блок 19 значения Ь 1 = 1 по адресу максимального элемента с 11 строки, записью в регистр 6 позиционного кода 1000 и увеличением на единицу содержимого счетчика 9,На втором цикле работы устройства (обработка второй строки) из сравнения будет исключен с 21. Максимальный элемент - с 2 З, Результаты работы устройства на втором цикле; значение "1", записанное в блок 1 ф по адресу максимального элемента; позица. онный код 1010 в регистре 6; увеличенная на единицу содержимого счетчика 9.В следующих двух циклах устройствЕ работает аналогично. Результаты его работы по циклам определены на фиг. 4 в таблицах справа и снизу от матрицы С,Результат решения задачи назначения - матрица назначения Х (фиг, 5) - может считываться по окончании или в процессе работы устройства - построчно по окончании обработки строки (цикла устройства). Формула изобретения Устройство для решения транспортных задач линейного программирования, содержащее первый, второй и третий регистры, кольцевой регистр сдвига, блок сравнения, первый и второй счетчики, выход признака переполнения последнего является выходом признака окончания работы устройства, блок памяти матрицы назначений, вход чтения которого является входом чтения устройства, а информационный выход - информационным выходом устройства, последовательно соединенные дешифратор и первый блок элементов И, а также первый, второй и третий элементы ИЛИ, второй блок элементов И, с первого по четвертый элементы задержки, выход последнего из которых подключен к управляющему входу первого блока элементов И, выход которого подключен к входу установки в "1" разрядов . информационного слова кольцевого регистра сдвига, вход признака сдвига которого подключен к суммирующему входу первого счетчика, вход младшего разряда - к прямому выходу старшего разряда кольцевого регистра сдвига, вход начальной установки - к первому входу третьего элемента ИЛИ, к входу установки в "1" второго счетчика, к35 40 45 50 55 первому входу второго элемента ИЛИ и является входом начальной установки устройства, вход первого элемента задержки является тактовым входом устройства, выход второго регистра подключен к первому информационному входу блока сравнения, вход дешифратора подключен к выходу третьего регистра, вход установки в "0" которого подключен к входу установки в "1" первого счетчика и к выходу второго элемента ИЛИ, информационный вход - к информационному выходу первого счетчика, второй вход второго элемента ИЛИ подключен к входу признака записи блока памяти матрицы назначений, к выходу третьего элемента задержки, вход которого подключен к выходу признака переполнения первого счетчика, к второму входу третьего элемента ИЛИ, о т л и ч а ю щ е е с я тем,"что, с целью расширения области применения путем ; обеспечения решения транспортной задачилинейного программирования общего вида, дополнительно введены блок памяти значений потребностей, блок памяти матрицы стоимости, блок памяти значений запасов, четвертый и пятый регистры, первый и второй сумматоры, последовательно соединенные первый элемент И, четвертый элемент ИЛИ, пятый элемент задержки, последовательно соединенные шестой элемент задержки, пятый элемент ИЛИ, последовательно соединенные седьмой элемент задержки, шестой элемент ИЛИ, второй вход которого подключен к второму входу пятого элемента ИЛИ, к входу записи блока памяти матрицы стоимости, к входу записи устройства, к выходу третьего элементазадержки, последовательно соединенные третий блок элементов И, первый блок элементов ИЛИ, а также четвертый и пятый блоки элементов И, с второго по шестой элементы И, восьмой элемент задержки, второй и третий блоки элементов ИЛИ, с первой по шестую адресные шины, причем первый вход третьего блока ИЛИ подключен к выходу третьего регистра, второй вход - к пятой адресной шине, выход - к первому адресному входу блока памяти матрицы назначений, информационный вход которого подключен к выходу четвертого регистра, второй адресный вход - к выходу второго блока элементов ИЛИ, первый вход которого подключен к шестой адресной шине, второй вход - к выходу второго счетчика, к адресному входу блока памяти значений запасов и четвертой адресной шине, к первой адресной шине и первому адресному входу блока памяти матрицы стоимости, второй адресный вход ко- .торого подключен к второй адресной шине и выходу первого счетчика, информационный вход - к первому информационному входу устройства, вход чтения - к входам первого и второго элементов задержки, выход - к входу первого регистра, выход которого подключен к информационному входу второго регистра и к второму информационному входу блока сравнения, вход опроса которого подключен к выходу второго элемента И, выходы "больше" и "Меньше" -г10ЗО которого подключен к входу признака записоответственно к первым входам пятого и шестого элементов И, вторые входы которых подключены соответственно к входу режима задачи назначения устройства, к первому входу третьего элемента И и к вхо ду режима транспортной задачи, к первому входу четвертого элемента И, а выходы - соответственно к первому и второму входам первого элемента ИЛИ, выход которого подключен к входу признака записи третьего 20 регистра и к входу признака записи второго регистра, вход установки в "0" и вход установки в "1" которого подключены соответственно к выходам третьего и четвертого элементов И, вторые входы которых подключены к выходу третьего элемента ИЛИ,второй вход которого подключен к входам чтения блока памяти значений потребноси четвертого регистра, вход установки в "О" которого подключен к входу начальнойустановки устройства, информационный вход - к выходу первого блока элементов ИЛИ, второй вход которого подключен к выходу второго блока элементов И, информационный вход которого поразрядно подключен к первому информационному входу второго сумматора и к выходу блока памяти значений потребностей, стробирующий вход - к входам четвертого и седьмого элементов задержки, к стробирующему входу четвертого блока элементов И, к инверсному выходу старшего разряда пятого регистра, прямой выход старшего разряда которого подключен к входам четвертого элемента ИЛИ, шестого элемента задержки и к стробирующим входам пятого и третьего блоков элементов И, выход инверсного кода - поразрядно к входам первого элемента И и к информационным входам пятого блока элементов, И, выход прямого кода - поразрядно к информационным входам четвертого блока элементов И, выход которого подключен к второму информационному входу устройства и к информационному входу блока памяти значений запасов, вход признака записи которого подключен к выходу шестого элемента ИЛИ, информационный выход - к информационному входу третьего блока12 1814082 Ц 47 щ элементов И, к второму информационному входу второго сумматора, выход которого . подключен к входу пятого регистра, вход переноса. - к входу "1" устройства и к входу переноса первого сумматора, первый информационный вход которого подключен к входу "О" устройства, второй информационный вход- к выходу пятого блока элементов И, выход - к третьему информационному входу устройства и к информационному входу блока памяти эначенйй потребностей,адресный вход которого подключен к третьей адресной шине и к выходу третьего регистра, выход. пятого элемента задержки подключен к суммирующему входу второго 5 счетчика, выход второго элемента задержки, подключен к вхбду признака сдвига кольцевого регистра сдвига, инверсный выход старшего разряда которого подключен к первому входу второго элемента И, второй 10 вход котороо подключен к выходу первогоэлемента задержки,1814082 4 гвяы ЛИЬ Составитель В, Козлов Редактор Н. Рожкова Техред ММоргентал Корректор А, Мотыльвенно-издательский комбинат "Патент", г. УжгороД, ул.Гагарина,роиэ о 7Ф Заказ 1827 ТиражВНИИПИ Государственного комит113035, Москва Ю Ю РЮ У Подписноепо изобретениям и открытиям при ГКНТ СС