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

(56) Авторское свидетельство СССРМ 1263094, кл, 0 06 С 7/122, 1985.Авторское свидетельство СССРМ 1711174 кл, б 06 Е 15/20, О 06 О 7/122,1988,(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ(57) Изобретение относится к вычислительной технике и может быть использовано длярешения транспортных задач линейногопрограммирования. Целью изобретения является расширение функциональных возможностей устройства за счет решениязадачи назначения, Устройство содержитблок 1 синхронизации, накапливающийблок 2 регистрации, накапливающий блок 3 7- О,Ы Ж ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР выбора минимального элемента матрицы, блок 4 регистрации матрицы транспортных затрат, вход 5 пуска устройства, выход 6 признака выдачи очередного назначения устройства, выходы 8 признаков назначений устройства, первый и второй выходы 9 и 10 блока синхронизации соответственно.Пусть необходимо с минимальными затратами распределить (назначить) Р работ (заданий) среди И исполнителей, Перед началом работы разряды блока 2 обнуляют, в блок 4 заносят матрицу транспортных затрат. На вход пуска устройства подают сигнал уровня логической "1". При атом блок 1 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой на выхо- ф дах 8 устройства формируются оптимальные назначения, сопровождаемые (Л импульсами на выходе 6 устройства, 1 ил, С9, При этом блок 3 выбирает среди всех элементовматрицы, поступивших на его информационные входы, минимальный элемент и фиксирует его координаты (номер строки и номер столбца) на своих выходах.Через время, достаточное для выполнения указанной операции, блок 1 синхронизации формирует импульс уровнялогической "1" на своем выходе 10, При этом блок 3 формирует на том своем выходе признака выброса элемента, номер которого соответствует двойному индексу элемента, на том своем выходе признакапринадлежности выбранного элемента столбцу матрицы, номер которого соответствует номеру столбца выбранного элемента, и на том своем выходе признака принадлежности элемента строке матрицы, номер которого соответствует номеру строки выбранного элемента, сигналы уровнялогической "1". При этом блок 4 обнуляет все элементы тех строк и столбцов матрицы, которые определены сигналами уровня логической "1" на соответствующих им входах обнуления, и выдает на свои выходы значе 404550 55 Изобретение относится к вычислительной технике и может быть использовано длярешения транспортных задач линейногопрограммирования.Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи назначения.На чертеже представлена функциональная схема устройства,Устроьство содержит блок 1 синхронизации, накапливающий блок 2 регистрации,накапливающий блок 3 выбора минимальногоэлемента матрицы, блок 4 регистрацииматрицы транспортных затрат, вход 5 пускаустройства, выход б признака выдачи очередного назначения устройства, выходы 7,8 признаков назначений устройства, первый и второй выходы 9 и 10 блока синхронизации соответственно.Устройство работает следующим образом.Пусть необходимо с минимальными затратами распределить (назначить) Р работ(заданий) среди И исполнителей,Перед началом работы разряды блока 2 25обнуляют, в блок 4 заносят матрицу транспортных затрат.На вход пуска устройства подают сигнал уровня логической "1", При этом блок 1синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы.Блок 1 синхронизации формирует сигнал уровня логической "1" на своем выходе ния элементов модифицированной таким образом матрицы транспортных затрат, а блок 2 устанавливает в единицу те свои разряды, которые определены сигналами уровня логической "1" на соответствующих входах установки, и проверяет факт заполнения разрядной сетки (т, е. установки в единицу всех своих разрядов).В том случае, если его разрядная сетка заполнена (т, е, если все работы уже распределены между исполнителями), блок 2 регистрации формирует на своем выходе признака заполнения разрядной сетки сигнал уровня логической "1", При этом блок 1 синхронизации прекращает формирование синхросигналов на своих выходах 9, 10 и работа устройства прекращается,В том случае, если его разрядная сетка не заполнена т, е. если имеются нераспределенные работы), блок 2 регистрации сохраняет на своем выходе признака заполнения разрядной сетки потенциал уровня логического "0". При этом блок 1 синхронизации через заранее определенное время ожидания формирует на своих выходах 9, 10 синхросигналы уровня логической "1". При этом работа устройства повторяется. Формула изобретения Устройство для решения задач линейного программирования, содержащее блок синхронизации, накапливающий блок регистрации, накапливающий блок выбора минимального элемента матрицы и блок регистрации матрицы транспортных затрат; причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу накапливающего блока выбора минимального элемента матрицы, выход признака принадлежности выбранного элемента К-му столбцу которого (К = 1, , Р, где Р - количество назначаемых заданий) подключен к входу обнуления элементов К-го столбца блока регистрации матрицы транспортных затрат, выход значения (К, М)-го элемента которого (М = 1, И, где И = Р - количество исполнителей) подключен к входу задания значения (К, М)-го элемента накапливающего блока выбора минимального элемента матрицы, выход признака принадлежности выбранного элемента М-й строке которого подключен к входу признака обнуления элементов М-й строки блока регистрации матрицы транспортных затрат, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет решения задач назначения, второй выход блока синхронизации являет10 15 20 25 30 35 40 45 50 Составитель А,МишинТехред М,Моргентал Корректор М,Максимишинец Редактор Л,Волкова Заказ 3549 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 ся выходом пр нака выдачи очередного назначения уст,:лства и подключен к входу опроса накапливающего блока выбора минимального элемента матрицы, выход признака принадлежности выбранного элемента К-му столбцу которого подключен к входу установки в "1" К-го разряда накапливающего блока регистрации, выход признака заполнения разрядной сетки которого является выходом признака окончания работы устройства и подключен к входу останова блока синхронизации, выход при знака выбора (К, М)-го элементанакапливающего блока выбора минимального элемента матрицы является выходом признака (К, М)-го назначения устройства.