Устройство для определения экстремальных путей в графе Советский патент 1980 года по МПК G06G7/48 

Изобретение относится к вычислительной технике и может быть использовано для решення минимаксной задачи выбора.i Известно устройство для моделирования задач математического программирования, содержащее блок измерения и }Т1равления, блоки операционных усилителей, блоки трехнолюсников и блоки питания 1. Известное устройство может быть использовано для приближенного решения комбинаторных задач, сформулированных в терминах линейного программирования. Недостатком устройства является большое время t поиска решения комбинаторных задач, обусловленное резким возрастанием их размерности при переходе к линейным моделям и увеличением количества итераций вследствие введения отсечений. Наиболее близким по технической суишости к предложе шому изобретению является устройст во для определения кратчайших путей в графе, содet)жaшee блоки индикации, первые выходы которых объединены и подключены к входу коммутатора 2. Известное устройство позволяет моделировать сетевые 1Т)афы и может быть использовано для решения минимаксной задачи выбора в сетевой интерпретации. Однако вследствие неаддитивности целевой функции и комбинаторного характера указанной задачи при зтом потребовалось, бы моделировать и сопоставлять множество вариантов графов, обусловлеиное возможными разбиениями множества работ на подмножества назначений каждому исполнителю. Перебор множества вариантов приводит к большим затратам времени. Цель изобретения - ускорения процесса поиска р«пения. Поставленная цель достигаегся тем.чго в устройство введены блоки памяти и блок выделения экстремума.причем первые выходы блоков индикация объединены и подключены ко входу коммутатора, а вторые выходы блоков инд1жации соединены со входами соответствующих блоков памяти, выходы которых соответственно соединены со входами блока выделения зкстремума. Структурная схема приведена на чертеже. 37 Устройство состоит из п блоков, индикации Ь -Ifir п блоков памяти 2. -2, блока вьщеления экстремума 3 и коммутатора 4. Каждый из блоков Ц-In индикации содержит m блоков постоянных коэффициентов, выходы которых соединены с контактами поля искателя и коммутатора 4, m транспарантов и m реле, соединенных через соответствующие замыкающие контакты .реле РУ1-РУ блока 3 и контакты искателя И коммутатора 4 с плюсовой шиной питания. Каждый из блоков памяти содержит по два операционных усилителя, причем выход первого усилителя через замыкающий контакт соответствующего реле Р1-Рп коммутатора 4 соединен со входом второго усилителя, выход которого через размыкающий контакт реле Р1-РП соединен со вторым входом первого усилителя, К выходу первого усилителя подключей вольтметр. С поМЬиЬю контактов репе Р1-РП в цепях обратной связи осуществляется зшравление режимом работы усилителей. Блок 3 выделения экстремума содержит Операционньге усилителей, включенных по схем с общим выходом и содержащих диоды в цепях обратной связи. К выходам усилителей через диоды подключены обмотки реле ТУ1-РУ управляющих коммутацией цепей блоков 1 1п и коммутатора 4. Коммутатор 4 содержит реле РК1, РК2, ИСЗ, Pl-P, искатель И,.выключатель В и транспарант Л1. Устройство предназначено для решения мини максной задачи выбора, состоящей в распреДелении m работ межлу п исполнителями, минимизирующем наибольшие среди всех исполнителей суммарные затраты. Принцип работы устройства основан на пошаговом формированин вариантов распределения очередной работы с учетом предшеству1ощях назначений, выборе и запоминании HatDqmiero варйайта. Перед решением должны быть заданы числа m и п, определяюцще количество Шмёнтое и блоков устройства. С noMoiittio блоков постоянных коэффициентов 11 - rnn устанавлиЯагбтся отрйцатёльньк выходнь1ё йайряжёния блоков , пропор1)сйояалы}ые зна чениям С, таким образом, )бы шздексь последних совпадали с номерами блоков постоянньк коэффициентов. На дополнительнь1:е входы усилителей блока 3 подаются одинаковые отрицательные смещения, пропорциональные числу М. Здесь - затраты, связанные с выполнением I -и работы j -м исполнителем, М - достахочно большое число, вводимое для замены поиск минимума выбором максимума.. Процесс поиска решения состоит из m шагов. На первом шаге решения происходит автоматическое формирование вариантов назначения работы с номером 1 путем одновременного подключения первых блоков постоянных коэффициентов блоков к соответствующим входам блоков с помощью искателя И. В блоке 3 осуществляется выбор знашах f /-1 m-in Г чения ,| (M-C,j), т.е. . 4 -tj которое запоминается в блоке 2 и регистрируется в блоке 1 ц. Щетки искателя И перемещаются в следзтощее положение, и происходит переход ко второму шагу решения, на котором производится формировйние вариантов назначения работы с номером 2, выбор, и запоминание значения пци (C + --2j)Устройство работает следующим образом. При замыкании выключателя В коммзггатора 4 через размыкающие контакты реле РК2 подается питание на обмотку искателя И. Щетки искателя совместятся с первыми контактами полей искателя. Отрицательные напряжения с вь1ход6в блоков Ц-Дп чярез размыкающие контакты реле РКЗ, Pl-P коммутатора 4 поступают на первые входь уоиттителей УIj-УIn блоков , с выходов которых через размыкающие контакты реле РК1 и РКЗ инвертированные напряжения, пропорциональные значениям Cjj, подаются на соответствующие входы блока 3., Предположим, что первоначально . С. Тогда Напряжение на выходе усилителя У блока 2. обусловит максимальное положительное напряжение на выходе первого усилителя блока 3, которое вызовет срабатывание реле РУ1 и запирание диодов цепей обратной связи остальных усилителей блока 3. Замыкающие сонтакты реле РУ1 готовят: цепи питания обмоток реле РИ-РщЬ блока 1 и реле Р1 коммутатора 4. Поскольку на первом щаге peпJeния щетки искателя И совмещены с первыми контактами полей искателя, в блоке 1 j срабатывает и самоблокируется реле Р11 и загорается транспарант ЛИ. Одновременно срабатывает реле Р1 коммутатора 4. Размыкающие контакты реле Р1 отключают входы усилителя У1 и nepeisoдят его в режим запоминания. Замыкающие koHTaKTH реле Р1 переводят усилитель У2 в малоинерционный режим, подключает к его входу выход усилителя У1 , замыкают цепь питания реле РКЗ и отключают обмотку искателя И коммутатора 4. Реле РКЗ срабатывает и своими размыкающими контактами разрывает входньш цепи блоков 3. При этом обесточивается обмотка реле РУ1 блока 3. Замыкающие контакты реле РУ1 разрывают цепи питания.реле Pll-P l блока 1 и реле Р1 коммутатора 4. Реле Р1 отпускает, его контакты разрывают цепь питания реле РК2 коммутатора 4 и переводят усилитель У2 блока 2

в режим запоминания, причем его входная цепь разрывается, выход подключается ко второму входу усилителя УЬ, который вновь переводится в малоинерционный режим, а на выходе усилителя У2, и, следовательно, на втором входе зсилителя У1. блока 2 ж сохраняется напряжение, пропорциональное значению С. Реле РК2 отпускает, еГо контакты piiyfiJMвают цепь питания реле РКЗ и замыкают цейь питания искателя И коммутатора 4. Реле РКЗ отпускает и сво1ими размыкайгдими koHfaktaми замыкает входйые цепи блоков 2)-2п, 3, щетки искателя И перемещаются в cлёдyik)Щёe положение и происходит переход ко второму iiiary решения.

На втором шаге решения с выходив блоков входы блоков 2.-2п подаются наЦ-1п на

пряжения, пропорциональные значениям .

Таким образом, на выходе усилителя У, блока 2 установится напряжение, пропорциональ2 -2п ное С., +С„ , а на выходах блоков пропорциональные значениям С„2- напряжения

С2 соответственно. Аналогично тому, как этр осуществлялось на первом шаге решения, б блоке 3 происходит выделение значения ; .

Н11И (С + Cg, u.2.-v -2h одном из блоков , его запоминание, а з соответствздащем блоке индикация выбранного варианта назначения работы с номером 2. В результате коммутации цепей устройстЁЗ : щетки искателя И перемещаются в новое положени е и происходит переход к следующему шагу .решения;,,

После выполнения m шагов через (т+1)-й контакт поля искателя И образуется цепь питания реле РК1 и транспаранта Л1 коммутатора 4. Реле РК1 срабатывает и своими размыкающими контактами разрывает цепи питания реле Р1-РП, РК2, РКЗ, искателя И коммутатора 4 и входные депи блока 3.

Загорание транспаранта Л1 коммутатора 4 сигнализирует об окончании процесса решения. Номера горящих транспарантов блоков определяют индексы значений , вошедших в решение. Показания вольтметров VI-Vp блоков пропорциональны суммарным затратам соответствующего исполнителя.

Для приведения схемы в исходное положение снимается напряжение с шин питания, с помощью кнопок в цепях обратной связи обнуляются выходы усилителей У2 -У2 блоков и осуществляется возврат щеток искателя И и раз «ыкание выключателя В коммутатора 4,:

Благодаря введению новых блоков и связей ускорился процесс поиска решения.

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

Устройство для отфеделения зкстре1йальнь Х путей в графе, содержащее блоки индикации, первые выходы Которых объединены и подключены ко входу KOMNfyraTopa, .отличающееся тем, что, с целью ускорения процесса поиска решения, и него дополнительно введень блоки памяти и блок выделения экстремума, причем первые выходы блоков индикации объединены и подключены ко входу коммутатора, а вторые вькоды блоков индикации соединены со входами соответствующих блоков

памяти, выходы которь1х соответственно соединены со входами блока вьщеления экстремума.

Источники информации, принятьге во внимание при экспертизе . 1. Васгшьев В. В. и др. Решение задач Оптимального готанщюванйя на электронных моделях. .К., Наукова Думка, 1966, с. 36-38.

2. Авторское свидетельство СССР № 417802, кл. G 06 G 7/48, 1974 (прототип).