Устройство для решения задач оптимизации Советский патент 1992 года по МПК G06F15/20 

ч

Јь

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

Цель изобретения - повышение быстродействия устройства при решении транспортных задач линейного программирования.

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

Устройство содержит блок 1 синхронизации, блок 2 выбора минимального элемента матрицы, блок 3 задания матрицы транспортных затрат, блок 4 регистрации матрицы плана перевозок, первый блок 5 памяти, блок 6 сравнения, второй блок 7 памяти, вход 8 пуска устройства, выходы 9 обьема перевозок из пунктов отправления в пункты назначения и выходы 10-12 блока 1 синхронизации.

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

Пусть известны запасы некоторого продукта пунктов отправления, потребности в нем пунктов назначения и транспортные затраты при перевозках из К-го пункта отправления (К 1.....0, где О-количество пунктов отправления)в М-й пункт назначения(М 1, .... Н, где Н - количество пунктов назначения), т.е. матрица транспортных затрат. Необходимо составить план перевозок всего обьема запасов пунктов отправления (или удовлетворения потребностей всех пунктов назначения) с минимальными транспо ртны- ми затратами.

Перед началом работы обнуляют блок 4 регистрации матрицы плана перевозок, в блок 3 заносят матрицу транспортных затрат, в блок 5 памяти по адресам, соответствующим номерам пунктов отправления, заносят их запасы, в блок 7 памяти по адресам, соответствующим номерам пунктов отправления, заносят их потребности.

На вход 8 пуска устройства подают импульс уровня логической 1. При этом блок 1 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы. Импульс уровня логической 1 появляется на выходе 10 блока 1. При этом блок 2 выбирает минимальный элемент матрицы транспортных затрат и фиксирует его координаты (номер строки и номер столбца) до прихода следующего тактового импульса. Через время, достаточное для выполнения этой операции, блок 1 формирует импульс на своем выходе 11. При этом блок 5 памяти фиксирует на своем информационном выходе значение, соответствующее заданному адресу (т.е. запасы пункта отправления), до прихода следующего импульса чтения, а блок 7 памяти фиксирует на своем информационном выходе значение, соответствующее его адресу (т.е. потребности пункта назначения

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

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

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

0 (т.е.запасы пункта отправления окажутся больше потребностей пункта назначения), импульс появится на выходе признака Не больше. При этом выбранная ячейка блока 7 памяти устанавливается в ноль, в выбран5 ную ячейку блока 5 памяти записывается абсолютная величина разности (остаток запасов пункта отправления после удовлетворения потребностей пункта назначения), блок 4 регистрации в ячейке, выбранной ко0 ординатами строки и столбца, записывает информацию, поступающую с второго информационного входа (объем перевозок), и блок 3 удаляет выбранную строку (потребности соответствующего ей пункта назначе5 ния исчерпаны). В том случае, если импульс появится н а выходе признака Не меньше блокад (т.е. если запасы пунктов отправления окажутся меньше потребностей пунктов назначения), устройство работает аналогич0 но: устанавливается в ноль ячейка блока 5 памяти (запасы исчерпаны), в ячейку блока 7 записывается абсолютное значение разности (неудовлетворенные потребности), в блок 4 заносится с первого входа объем пе5 ревозок, а в блоке 3 удаляется один из столбцов (запасы, соответствующего которому пункта отправления исчерпаны). Через время, достаточное для окончания указанных процессов, блок 1 формирует импульс уров0 ня логической единицы на своем выходе 11. Далее работа устройства повторяется до полного исчерпания запасов пунктов отправления и/или потребностей пунктов назначения. При этом на выходах 9 устройства

5 формируется план объема перевозок из пунктов отправления в пункты назначения. Формула изобретения Устройство для решения задач оптимизации, содержащее блок синхронизации, блок задания матрицы транспортных затрат

и блок регистрации матрицы плана перевозок, причем вход пуска устройства подключен к входу пуска блока синхронизации, отличающееся тем, что, с целью повышения быстродействия при решении транспортнойзадачилинейногопрограммирования, в него введены блок выбора минимального элемента матрицы, блок сравнения и два блока памяти, причем первый выход блока синхронизации подключен к тактовому входу блока выбора ми- нимальн.ого элемента матрицы, выход номера столбца которого подключен к входам задания номера столбца блока задания матрицы транспортных затрат и блока регистрации матрицы плана перевозок и к адресному входу первого блока памяти, выход которого подключен к первому информационному входу блока регистрации матрицы плана перевозок и к первому информационному входу блока сравнения, выход признака Не меньше которого подключен к входу признака записи второго блока памяти, к входу установки в О первого блока памяти, к первому входу признака записи блока регистрации матрицы плана перевозок и к входу признака удаления столбца блока задания матрицы транспортных затрат, (К, М)- й информационный выход которого (К 1, „.О, где О - количество пунктов отправления; М 1Н, где Н - количество пунктов

назначения в транспортной сети) подключен к (К, М)-му информационному входу блока выбора минимального элемента матрицы, выход номера строки которого

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

первого блока памяти, к входу установки в О второго блока памяти, к входу признака удаления строки блока задания матрицы транспортных затрат и к второму входу признака записи блока регистрации матрицы плана перевозок, (К, М)-й информа- ционный выход которого является выходом объема перевозок из К-го пункта отправления в М-й пункт назначения устройства, второй выход блока синхронизации подключен к входу опроса блока сравнения, выход абсолютной величины разности которого подключен к информационным входам первого и второго блоков памяти, третий выход блока синхронизации - к входам признаков чтения первого и второго блоков памяти.

Изобретение относится к вычислительной технике и может быть использовано для решения транспортных задач линейного программирования. Целью изобретения является повышение быстродействия устройства при решении транспортных задач линейного программирования. Устройство содержит блок 1 синхронизации, блок 2 выбора минимального элемента матрицы. блок 3 задания матрицы транспортных затрат, блок 4 регистрацию матрицы плана перевозок, первый блок 5 памяти, блок 6 сравнения, второй блок 7 памяти, вход 8 пуска устройства, выходы 9 объема перевозок из пунктов отправления в пункты назначения и выходы 10-12 блока 1. Перед началом работы обнуляют блок 4 регистрации матрицы плана перевозок, в блок 3 заносят матрицу транспортных затрат, в блоки 5, 7 памяти заносят объемы запасов пунктов отправления и потребностей пунктов назначения.На вход 8 пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих выходах 10-12 последовательность сигналов уровня логической единицы, под управлением которой на выходах 9 устройства формируется план перевозок из пунктов отправления в пунктьГ назначения. 2 ил,1 сл с