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

 

Изобретение относится к вычислительной технике и может быть использовано для решения транспортных задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи назначения. Устройство содержит блок 1 синхронизации, накапливающий блок 2 регистрации, накапливающий блок 3 выбора минимального элемента матрицы, блок 4 регистрации матрицы транспортных затрат, вход 5 пуска устройства, выход 6 признака выдачи очередного назначения устройства , выходы 8 признаков назначений устройства, первый и второй выходы 9 и 10 блока синхронизации соответственно. Пусть необходимо с минимальными затратами распределить (назначить) Р работ (заданий ) среди I/ исполнителей. Перед началом работы разряды блока 2 обнуляют, в блок 4 заносят матрицу транспортных затрат . На вход пуска устройства подают сигнал уровня логической 1. При этом блок 1 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой на выходах 8 устройства формируются оптимальные назначения, сопровождаемые импульсами на выходе 6 устройства 1 ил. (Л С

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (51)з G 06 F 15/419

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ! д (21) 4748825/24 (22) 11.07,89 (46) 07.10,92. Бюл. М 37 (72) А.А. Батищев, B,В, Калист, A,Н. Мардас и Н.И. Ячкула (56) Авторское свидетельство СССР

М 1263094, xn, G 06 6 7/122, 1985.

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

М 1711174,, кл, G 06 Е 15/20, G 06 G 7/122, 1988, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано для решения транспортных задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи назначения, Устройство содержит блок 1 синхронизации, накапливающий блок 2 регистрации, накапливающий блок 3!

Ы 17б7505 А1 выбора минимального элемента матрицы, блок 4 регистрации матрицы транспортных затрат, вход 5 пуска устройства, выход 6 признака выдачи очередного назначения устройства, выходы 8 признаков назначений устройства, первый и второй выходы 9 и 10 блока синхронизации соответственно.

Пусть необходимо с минимальными затратами распределить (назначить) Р работ (заданий) среди И исполнителей, Перед началом работы разряды блока 2 обнуляют, в блок 4 заносят матрицу транспортных затрат. На вход пуска устройства подают сигнал уровня логической "1". При атом блок 1 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой на выходах 8 устройства формируются оптимальные назначения, сопровождаемые импульсами на выходе 6 устройства, 1 ил, 1767505

9, При этом блок 3 выбирает среди всех элементов матрицы, поступивших на его информационные входы, минимальный элемент и фиксирует его координаты (номер строки и номер столбца) на своих выходах.

Через время, достаточное для выполнения указанной операции, блок 1 синхронизации формирует импульс уровня логической "1" на своем выходе 10. При этом блок 3 формирует на том своем выходе признака выброса элемента, номер которого соответствует двойному индексу элемента, на том своем выходе признака принадлежности выбранного элемента столбцу матрицы, номер которого соответствует номеру столбца выбранного элемента, и на том своем выходе признака принадлежности элемента строке матрицы, номер которого соответствует номеру строки выбранного элемента, сигналы уровня логической "1". При этом блок 4 обнуляет все элементы тех строк и столбцов матрицы, которые определены сигналами уровня логической "1" на соответствующих им входах обнуления, и выдает на свои выходы значе40

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

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

На чертеже представлена функциональная схема устройства.

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

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

Пусть необходимо с минимальными затратами распределить (назначить) Р работ (заданий) среди И исполнителей, Перед началом работы разряды блока 2 25 обнуляют, в блок 4 заносят матрицу транспортных затрат.

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

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

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

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

Устройство для решения задач линейного программирования, содержащее блок синхронизации, накапливающий блок регистрации, накапливающий блок выбора минимального элемента матрицы и блок регистрации матрицы транспортных затрат; причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу накапливающего блока выбора минимального элемента матрицы, выход признака принадлежности выбранного элемента К-му столбцу которого (К = 1, ..., P, где

P — количество назначаемых заданий) подключен к входу обнуления элементов К-го столбца блока регистрации матрицы транспортных затрат, выход значения (К, М)-го элемента которого (М = 1, ..., И, где И = P— количество исполнителей) подключен к входу задания значения (К, М)-го элемента накапливающего блока выбора минимального элемента матрицы, выход признака принадлежности выбранного элемента М-й строке которого подключен к входу признака обнуления элементов M-й строки блока регистрации матрицы транспортных затрат, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет решения задач назначения, второй выход блока синхронизации являет10

20

30

40

50

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

Техред М.Моргентал Корректор М,Максимишинец

Редактор Л,Волкова

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

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

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

Производственно-издательский комбинат "Патент", r, Ужгород, ул,Гагарина, 101 ся выходом пр нака выдачи очередного назначения уст» лства и подключен к входу опроса накапливающего блока выбора минимального элемента матрицы, выход признака принадлежности выбранного элемента К-му столбцу которого подключен к входу установки в "1" К-го разряда накапливающего блока регистрации, выход признака заполнения разрядной сетки которого является выходом признака окончания работы устройства и подключен к входу останова блока синхронизации, выход при5 знака выбора (К, М)-го элемента накапливающего блока выбора минимального элемента матрицы является выходом признака (К, M}t.o назначения устройства.