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

(51)5 С 06 Г ОБР ПИСАН АВТОРСКОМ ДЕТЕЛЬСТВУ(21) 4450604/2 (22) 28,06,88 (46) 15,04,90, (72) В.Е.Козло (53) 681.333 ( (56) Авторское У 1320812, кл,Авторское с В 1374241, кл. Бюл, Ф 14 ТРАНС ГРАНИ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР 888)свидетельство СССРС 06 Р 15/20, 1986.идетельство СССРС 06 Г 15/20, 1986.(54) УСТРОЙСТВО ДЛЯ РЕИЕНКЯ ПОРТНЫХ ЗАДАЧ ЛИНЕЙНОГО ПРО РО ВАНИЯ(57) Изобретение относится к вычисл тельной технике и может быть исполь зовано для решения задачи наэначени в системах распределенной обработки АСУ, Целью изобретения является сок ращение аппаратурных затрат при реш нии задачи назначения методом макси мальной строки (столбца). Устройствосодержит регистры 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 ил.Изобретение отйосится к вычислительной технике и может быть использовано для решения задачи назначенияв системах распределенной обработкиАСУ,Целью изобретения является сокращение аппаратурных затрат при решениизадачи назначения методом Факсимальной строки (столбца).10На фиг. 1 представлена функциональная схема предлагаемого устройства;на фиг.2 - пример матрицы стоимости;на фиг.3 - пример матрицы назначений.Устройство содержит (Фиг.1) с пер 15вого потретий регистры 1, 2 и 3 соответственно, кольцевой регистр 4сдвига, первый и второй блоки 5 и 6элементов И, с первого по четвертыйэлементы 7-10 задержки, первый и второй счетчики 11 и 12, второй, третийи первый элементы ИЛИ 13, 14 и 15соответственно, блок 16 сравнения,блок 17 памяти, дешифратор 18, вход19 начальной установки устройства, 25тактовый вход 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 анало-гично рассмотренному выше поступаетна вход регистра 2 и блока 16, гдесравнивается с элементом С 11Поскольку С 11 ) С 21, 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 обеспечит перезапись на втором шаге работы устройствакода "1" из первого в последний триггер указанного регистра 4, На каждомиэ последующих шагов код сдвигаетсяна позицию.К концу обработки второго столбца(на четвертом шаге второго цикла рабо57569 515ты устройства) в регистр 2 будет записан элемент С 42=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 п ход последнего подключен к входуустановки в "О" второго регистра,тактовый вход устройства подключенк входу признака записи первого регистра и входу второго элемента эадерж ки, выход которого подключен к входуопроса блока сравнения, выход призна"ка "Больше" которого подключен к первому входу третьего элемента КЛИ,входу признака записи второго регистра 20 и входу третьего элемента задержки,выход которого подключен к входу признака записи третьего регистра, выходпризнака "Не больше" блока сравненияподключен к второму входу третьего 25 элемента ИЛИ, выход которого подключен к входу признака сдвига кольцевого регистра сдвига и суммирующемувходу второго счетчика, информационныйвыход .которого подключен к информаци онному входу третьего регистра, выходкоторого подключен к входу дешифратора, выход которого подключен к информационному входу второго блока элементов И, разряды информационного выхода 35 которого подключены к разрядам информационного входа блока памяти и входамустановки в "1" разрядов информационного слова кольцевого регистра сдвига,прямой выход старшего разряда инфор мационного выхода которого подключенк младшему разряду информационноговхода того же кольцевого регистрасдвига, инверсный выход старшего разряда информационного выхода которого 45 подключен к управляющему входу первого блока элементов И, выход которогоподключен к информационному входувторого регистра, выход признака переполнения второго счетчика подключен 50 к второму входу второго элемента ИЛИ,суммирующему входу первого счетчикавходам четвертого элемента задержкии первого элемента задержки, выходкоторого подключен к второму входупервого элемента ИЛИ, выход которогоподключен к входам установки в "О"второго счетчика и третьего регистра,выход четвертого элемента задержкиподключен к управляющему входу второ1557569 ся выходом признака окончания работыустройства. Составиедактор А.Лежнина Техред Л ель А.Ми Олийнык ректор И,Ревск Тираж 562 Подп Заказ, 1 но ВНИИПИ Госуд открытиям при ГКНТ СССР д. 4/5 . твенного комитета по изобретениям 113035, Москва, Ж, Раушская нПроизводственно-издательский комбинат "Патент", г,ужгород, ул, Гагарина,10 го блока элементов И, выход признакапереполнения первого счетчика являетд 0 Р О д 1 д Р О О 1 О 1 Р Р Фиг, Л