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

 

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

союз советских

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ4ЕТЕЛЬСТВУ V (21) 4453786/24 (22) 11.07,88 (46) 07.02.92. Бюл. N 5 (72) А.Н.Романов (53) 681.333(088.8) (56) Авторское свидетельство СССР

¹ 1238099, кл. G 06 F 15/20, 1984.

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

N 1649562, кл. G 06 F 15/20, 06.05.88. (54) УСТРОЙСТВО ДЛЯ PЕШЕНИЯ ЗАДАЧ

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

1711174

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

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

1 синхронизации.

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

Пусть известны запасы некоторого продукта пунктов отправления, потребности в нем пунктов назначения и транспортные затраты при перевозках из К-го пункта отправления (К=1, ..., О, где Π— количество пунктов отправления) в М-й пункт назначения (М = 1, ..., Н, где Н вЂ” количество пунктов назначения), т.е. матрица транспортных затрат, Необходимо составить план перевозок всего объема запасов пунктов отправления (или удовлетворения потребностей всех пунктов назначения) с минимальными транспортными затратами, Перед началом работы обнуляют блок 4 регистрации матрицы плана перевозок, в блок 3 заносят матрицу транспортных затрат, в блок 5 памяти по адресам, соответствующим номерам пунктов отправления, заносят их запасы, в блок 7 памяти по адресам, соответствующим номерам пунктов отправления, заносят их потребности.

На вход 8 пуска устройства подают импульс уровня логической "1". При этом блок

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

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

;т,е. запасы пункта отправления), до прихо5

55 да следующего импульса чтения, а блок 7 памяти фиксирует на своем информационном выходе значение, соответствующее его адресу (т.е. потребности пункта назначения для транспортного пути с наименьшими затратами), до прихода следующего импульса чтения. Через время, достаточное для окончания указанных процессов, блок 1 формирует импульс уровня логической "1" на выходе 12. При этом блок 6 сравнения выдает на свой информационный выход абсолютное значение разности поступающих на его информационные входы значений, сопровождая его импульса и уровня логической

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

I (т.е.запасы пункта отправления окажутся больше потребностей пункта назначения), импульс появится на выходе признака "Не больше", При этом выбранная ячейка блока

7 памяти устанавливается в ноль, в выбранную ячейку блока 5 памяти записывается абсолютная величина разности (остаток запасов пункта отправления после удовлетворения потребностей пункта назначения), блок 4 регистрации в ячейке, выбранной координатами строки и столбца, записывает информацию, поступающую с второго информационного входа (объем перевозок), и блок 3 удаляет выбранную строку (потребности соответствующего ей пункта назначения исчерпаны). В том случае, если импульс . появится на выходе признака "Не меньше" блока 6 (т,е. если запасы пунктов отправления окажутся меньше потребностей пунктов назначения), устройство работает аналогично; устанавливается в ноль ячейка блока 5 памяти (запасы исчерпаны), в ячейку блока

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

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

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

1711174

Составитель А,Мишин

Редактор С.Патрушева Техред М.Моргентал Корректор И.Муска

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

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

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

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 и блок регистрации матрицы плана перевозок, причем вход пуска устройства подключен к входу пуска блока синхронизации, о тл и ч а ю щ е е с я тем, что, с целью повышения быстродействия при решении транспортной задачи линейного программирования, в него введены блок выбора минимального элемента матрицы, блок сравнения и два блока памяти, причем первый выход блока синхронизации подключен к тактовому входу блока выбора минимального элемента матрицы, выход номера столбца которого подключен к входам задания номера столбца блока задания матрицы транспортных затрат и блока регистрации матрицы плана перевозок и к адресному входу первого блока памяти, выход которого подключен к первому информационному входу блока регистрации матрицы плана перевозок и к первому информационному входу блока сравнения, выход признака "Не меньше" которого подключен к входу признака записи второго блока памяти, к входу установки в "0" первого блока памяти, к первому входу признака записи блока регистрации матрицы плана перевозок и к входу признака удаления столбца блока задания матрицы транспортных затрат, (K, M)й информационный выход которого (К = 1, ...О, где Π— количество пунктов отправления; М = 1, „„Н, где Н вЂ” количество пунктов назначения в транспортной сети) подключен к (К, М)-му информационному входу блока выбора минимального элемента матрицы, выход номера строки которого

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

15 первого блока памяти, к входу установки в

"0" второго блока памяти, к входу признака удаления строки блока задания матрицы транспортных затрат и к второму входу признака записи блока регистрации мат20 рицы плана перевозок, (К, M)-й информационный выход которого является выходом обьема перевозок из К-го пункта отправления в M-й пункт назначения устройства, второй выход блока синхрониза25 ции подключен к входу опроса блока сравнения, выход абсолютной величины разности которого подключен к информационным входам первого и второго блоков памяти, третий выход блока синхрониза30 ции — к входам признаков чтения первого и второго блоков памяти.