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

СОЮЗ СОВЕТСКИСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ЯО 15434(51)5 г, 06 20) С 06 С 7/122 ОПИСАНИЕ ИЗОБРЕТН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ содержит де Т - коеляемыхок 2 выбора из ТхРейка 5 содиод 8 ) цироана 43 ь ОСУДАРСТ 8 ЕННЫЙ КОМИТЕТо изОБРетениям и ОТКРытиямРИ П(НТ СССР(21) 4361344/24-24 (22) 09,11,87 (46) 15,0290.Бюл, Кф 6 (72) О,Г,Алексеев и Н,И,Ячкула (53) 681.333 (088, 8) (56) Авторское свидетельство СССР И, кл,С 06 Р 15/20, 1984,Авторское свидетельство СССР В 1444830, кл. С 06 Р 15/20, 1987, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ (57) Изобретение относится к вычисли тельной технике и может быть использовано для оптимизации рецений о наз начении заданий исполнителям, Целью изобретения является повьпцение быстр действия устройства нри рещении задачи оптимального распределения за" даний между исполнителями, С этой целью устройство содержит блок 1 регистровой памяти, блок 2 выбора максимума,кнопочные выключатели 3 и 4,Блок 1 регистровой памятиматрицу из ТхР ячеек 5, гличество заданий, распредмежду Р исполнителями, Блмаксимума содержит группуячеек 6 выбора, Каждая ячдержит элемент ИЛИ-НЕ 7,светодиод 9, регистр 1 О илоговый преобразователь 11, Каждаяячейка 6 выбора содержит операционный усилитель 12, токозадающий резистор 13, резистор обратной связи14, щунтирующий диод 15, ключевойдиод 16 и триггер 17, Устройствореализует алгоритм определения варианта распределения мест между исполкителями, основанный на идее осуществления назначений по максимальньм элементам матрицы эффективности выполнения заданий исполнителямикоторые перед началом работы заносяся в регистры 10 ячеек 5, 2 илИзобретение относится к вычислительной технике и может быть использовано для оптимизации решений оназначении заданий исполнителям.Цель изобретения - повышение быст.родействия устройства при решениизадачи оптимального распределенияЗаданий между исполнителями.Иа фиш,1 представлена функциональйая схема примера реализации устройства; на фиг,2 - обобщенная структурйая схема устройства.Устройство содержит блок 1 регистровой памяти, блок 2 выбора максимума и кнопочные выключатели Э и 4,Блок 1 регистровой памяти содержит матрицу.иэ ТхР ячеек 5, гдеТ - количество заданий, распределяемых между Р исполнителями, блок 2Выбора максимума - группу из ТхР ячеек 6 выбора, Каядая ячейка 5 состоит8 э элемента ИЛИ-ИЕ 7, диода 8, светодиода 9, регистра 10,и цифроаналого-.вого преобразователя (ЦАП ) 11, 25Каждый элемент 6 выбора содержитоперационный усилитель 12, токозадаюЩий резисиор 13, резистор 14 обратнойвсвязи, шунтирующий диод 15, ключевойдиод 16 и триггер 17,30Устройство работает следующим образом,Перед началом работы значенияКоэффициентов эффективности использования К-го исполнителя (К=1 Р)а М-и месте (М=1 Т) (при нцпол -35ненни М"го задания) заносятся н регистр 10 (К,М)-й ячейки 5,Решение начинается нажатием выключателя 3, При этом его размцкающие"контакты рвут цель подачи напряженияот шины питания на объединенные полю-.са всех ячеек 5, Снимается сигналвысокого уровня с второго входа элемента 7 всех ячеек 5, Сигнал Уровня 45"1" с выхода элементов 7 всех ячеек5 поступает на считывающий вход ихрегистров 10, Значения коэффициентовэффективности (В) с информационных выходов регистров 10 поступаютна вход соответствующих ЦАП 11 с выходов которых напряжения, пропорцио-:нальные знаЧениям коэффициентов эФфективности, подаются на. вторые входы соответствующих элементов 6 вцбо 55ра блока 2. Эти напряжения с вторыхвходов элементов выбора через токозадающие резисторы 13 поступают навход их операционных усилителей 12,Так как узлы соединения резисторов 14 обратной связи и шунтирующих диодов 15 всех элементов выбора объединены, в блоке 2 осуществляется выбор максимального из входных напряжений и на единичном входе триггера 17, на входе операционного усилителя которого присутствует наибольший входной сигнал, появляется сигнал высокого уровня, Так, например, если В= шах 1 В ,то на первом шаге решения сигнал высокого уровня поступает на единичный вход триггера 17 элемента ныбора 6, . Триггер переходит в единичное состояние,и сигнал высокого уровня с его единичного выхода поступает на третий полюс ячейки 5блока 1, с него через диод 8 - на третий вход элемента 7 этой ячейки и ее четвертый полюс, а через светодиод 9, загорание которого сигнализирует о назначении первого исполнителя, на первое рабочее место, на первый вход элемента 7 и четвертый полюс ячейки 5. Так как первые полюса объединены у всех ячеек 5, имеющих одинаковый второй индекс (по столбцам), а четвертые полюса объединены у всех ячеек, имеющих одинаковый первый индекс (то есть по строкам) то сигнал уровня "1" поступает на первые входы элементов 7 ячеек 5К = 2,Р, и на третьи входы элементов 7 ячеек 5, , М = 2 Т, Снимается сигнал высокого уровня с управляющих входов регистров 10 ячеек первого столбца и первой строки блока 1 и снимаются напряжения, На этом заканчивается первый шаг решения, На последующих шагах работа устройства аналогична его работе на первом шаге Решение заканчивается при Р 4 Т закреплением всех исполнителей, д при Р ) Т закреплением всех рабочих мест, о чем свидетельствует свечение одного из светодиодов в каждой из строк или н каждом нз столбцов ячеек 5 блока 1 соответственно. По окончании решения выключатель 3 отпускается, Вариант закрепления мест между исполнителями определяется по светящимся светодиодам 9 блока 1 и зафиксирован триггерами 17, перешедшими в единичное состояние,Для возврата схемы н исходное состояние кратковременно ьажимаетсявыключатель 4, через замыкающие контакты которого напряжение от шины пи-,5 15434тания поступает при этом на объединенные первые воды всех элементов 6выбора блока 2, а с них на нулевыевходы триггеров 17, обеспечивая5возврат в нулевое состояние тех иэних, которые в ходе решения перешлив единичное состояние,На фиг,2 цифровые обозначения имеют элементы 18 памяти матрицы, элементы ИЛИ 9 матрицы, блок 20 выборамаксимального кода, блок 21 заданиятопологии, элементы ИЛИ 22 группыи вход 23 пуска устройства,Работа устройства по его обобщен-.ной схеме аналогична описанной,Однако блок 21 задания топологиипредставляет собой совокупностьтриггеров 17 с соответствующими функциональными связями, элементы 22 ИЛИ группы соответствуют совокупности диодов 8 всехячеек соответствующих столбцов матрицы, а светодиоды 9 исключеныиз обобщенной структурной схемы, так 25как триггеры 17 (или триггеры. блока21 задания топологии) установленныев единичное состояние, содержат полную информацию о решении задачи оптимального распределения заданий междуисполнителями,Формула изобретенияУстройство для решения транспортных задач, содержащее матрицу иэ 18 6ТхР элементов памяти, где Т - количество заданий распределяемых между Р исполнителями, блок задания топологии и блок выбора максимального кода,(К,М)-й выход позиции максимального кода которого (К у ерТ М 1в ф у Р) подключен к входу установки признака наличия дуги из К-й в М-ю вершину транспортной сети блока задания топологии, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства при решении задачи оптимального распределения заданий между исполнителями, в него введеиа матрица из ТхР элементов ИЛИ и группа из Р элементов ИЛИ, при" чем выход признака наличия дуги из К-й в М-ю вершину транспортной сети блока задания топологии подключен к М-му входу К-го элемента ИЛИ группы, выход которого подключен к первым входам всех элементов ИЛИ К-го столбФца матрицы и к вторым входам всех элементов ИЛИ К-й .строки матрицы, выход К-го элемента ИЛИ М-й строки матрицы подключен к входу блокировки чтения К-го элемента памяти М-й строки матрицы, выход которого подключен к (К,М)-му информационному входу блока выбора максимального кода, вход опроса которого является входом пуска устройства.1543418 Составитель А, Редактор Л,Пчолинская Техред М,Дидык в те "7 н рректор В, Гирняк аказ 402 Тираж 565 ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ113035, Москва, Ж, Раушская наб. д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 1