Устройство для определения экстремальных путей в графе

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союэ Советсиын

Соцыалыстычесиых

Республыи (61) Дополнительное к авт. саид-ву (22) Заявлено 16.02.77 (21) 2454134/18 — 24 с присоединением заявки М (23) П риоритет йюуднрстнннньЖ камнтат

СССР ю ланам нзабуетеннй н нтннытнй

Опубликовано 05,02.80.. Бюллетень М 5

Дата опубликования описания 05.02.80 (72) Авторы изобретения

О. Г. Алексеев и В, Ю. Мержанов (7l ) Заявитель

Военная артиллерийная ордена Ленина Краснознаменная академия им,. М. И. Калинина (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ

ПУТЕЙ В ГРАФЕ

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

Известно устройство для моделирования задач математического программирования, со- держащее блок измерения и управления, блоки

3 операционных усилителей, блоки трехполюсников и блоки питания (1).

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

Недостатком устройства является большое время < поиска решения комбинаторных задач, обусловленное резким возрастанием их размерности при переходе к линейным моделям и увеличением количества итераций вследствие введения отсечений.

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

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

Перебор множества вариантов приводит к большим затратам времени.

Цель изобретения — ускорения процесса поиска решения.

Поставленная цель достигается тем,чго в устройство введены блоки памяти и блок выделения экстремума,причем первые выходы блоков индикации объединены и подключены ко входу коммутатора, а вторые выходы блоков индикации соединены со входами соответствующих блоков памяти, выходы которых соответственно соединены со вхоДами блока выделения экстремума.

Структурная схема приведена на чертеже.

Каждый нз блоков 2г — 2п памяти содержит по два операционных усилителя, причем выход первого усилителя через замыкающий контакт соответствующего реле Pl — Рп коммутатора 4 соединен со входом второго усилителя, выход которого через размыкающий контакт реле

Pl — Рп соединен со вторым входом первого усилителя, К выходу первого усилителя подключен вольтметр. С помойью контактов реле Рl — Рп в цепях обратной связи осуществляется управление режимом работы усилителей.

Блок 3 выделения экстремума содержит операционных усилителей, включенных по схеме 2 с общим выходом и содержащих диода в цепях обратной связи. K выходам усилителей через диоды подключены обмотки реле ТУ1 — РУп, управляющих коммутацией цепей блоков 1—

lrI и коммутатора 4.

Коммутатор 4 содержит реле РК1, РК2, РКЗ, Pl — P, искатель И,.выключатель В и транспарант Лl.

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

Перед решением дотакньт быть заданы числа

m и и, определяющие количество элементов

H 6JIoKoB устроиства. С помощью блОкОВ постояннь1х коэффициентов 11 — rnn устанавливаются отрицательные Выходные напряжения блоков 1„— 1п, пропорциональные значениям

С4 ° таким образом, чтобы индексы последнич совпадали с номерами блоков постоянных коэффициентов. На дополнительнйе входы усилителей блока 3 подаются одинаковые отрицательные смещения, пропорциональные числу М.

Здесь С„ — затраты, связанные с выполнением

1 -й pa60TbI ) -M исполнителем, М вЂ” достаточно большое число, вводимое для замены поиска минимума выбором максимума

Процесс поиска решения состоит из m шагов. На первом шаге решения происходит ав30

714421

Устройство состоит из и блоков, индикации

11--1П, и блоков памяти 2 — 2п, блока вьщеления экстремума 3 и коммутатора 4.

Каждый из блоков 14 — ln индикации содержит m блоков постоянных коэффициентов, выходы которых соединены с контактами поля искателя ц коммутатора 4, m транспарантов и m реле, соединенных через соответствующие замыкающие контакты, реле РУ1 — РУ блока 3 и контакты. искателя И коммутатора 4 с плю- 1О совой шиной питания.

4 томатическое .формирование вариантов назначения работы с номером 1 путем одновременного подключения первых блоков постоянных коэффициентов блоков 14 — 1п к соответствующим входам блоков 2 — 2„с помощью иска4 теля И, В блоке 3 осуществляется выбор значения (М вЂ” С4 ), т.е. С4, = ."" С ° которое запоминается в блоке 2 и регистри4к руется в блоке 1к, 1цетки искателя И перемещаются в следующее положение, и происходит переход ко второму шагу решения, на котором производится формирование вариантов назначения работы с номером 2, выбор и запоминание значения yrIjrI (С„, + С,, " С )

> К

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

При замыкании выключателя В коммутатора 4 через размыкающие контакты реле РК2 подается питание на обмотку искателя И. 1цетки искателя .совместятся с первыми контактами полей искателя. Отрицательные напряжения с выходов блоков 14 — l„через размыкающие контакты реле РКЗ, Pl — 1 коммутатора 4 поступают на первые входы у:ичителей

У1, — У1п блоков 24 — 2„, с выходов к,. т рых через размыкающие контакты реле РК1 и РК3 инвертированные напряжения, пропорциональные значениям С„, подаются на соответствующие входы блока 3, Предположим, чтО первоначально . .. «С,, °

Тогда напряжение на выходе усилителя У14 блока 2 обусловит максимальное положительное напряжение на выходе первого усилителя блока 3, которое вызовет срабатывание реле

Руl и запирание диодов целей обратной связи остальных усилителей блока 3. Замыкающие контакты реле РУ1 готовят цепи питания обмоток реле Pl 1-Pml блока 1 и реле Pl коммутатора 4.

Поскольку на первом шаге решения щетки искателя И совмещены с первыми контактами полей искателя, в блоке 1 срабатывает и самоблокируется реле Pll и загорается транспа. рант Лl l. Одновременно срабатывает реле Pl коммутатора 4. Размыкающие контакты реле

Р1 отключают входы усилителя Уl и переводят его в режим запоминания. Замыкающие контакты реле Pl переводят усилитель У2 в малоинерционный режим, подключает к его входу выход усилителя Уl, замыкают цель

4 питания реле РКЗ и отключают обмотку искателя И коммутатора 4. Реле РКЗ срабатывает и своими размыкающими контактами разрывает входные цепи блоков 24 — 2„, 3. При этом обесточивается обмотка реле РУ1 блока 3.

Замыкающие контакты реле РУ1 разрывают цепи питания, реле Рl l — Pml блока 1 и реле

Pl коммутатора 4. Реле Pl отпускает, его контакты разрывают цепь питания реле РК2 коммутатора 4 и переводят усилитель У24 блока 24

5 7 в режим запоминания, причем его входная цепь разрывается, выход подключается ко второму входу усилителя Yl который вновь переводится в малоинерционный режим, а на выходе усилителя У2 и, следовательно, на втором входе усилителя У1 блока 2, сохраняется напряжение, пропорциональное значению

С+ . Реле РК2 отпускает, его контакты разрывают цепь питания реле РКЗ и замыкают. цепь питания искателя И коммутатора 4. Реле РКЗ отпускает и своими размыкайщими контактами замыкает входйые цепи блоков 21 — 2п, 3, щетки искателя И перемещаются в следующее положение и происходит переход ко второму пвгу. решения.

На втором шаге решения с выходов блоков

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

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

C2h соответственно Ана огично то у, как это осуществлялось на первом шаге решения, в . блоке 3 происходит выделение значения п1и (С„„+ С „, С, „,C ), в одном из блоков 21 — 2>, его запоминание, а в соответствующем блоке 1 — 1> — индикация выбран- ного варианта назначения работы с номером 2.

В результате коммутации цепей устройства".- щетки искателя И перемещаются в новое положение и пройсходит переход к следующему шагу решения .

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

14421 6

Загорание транспаранта Л1 коммутатора 4 сигнализирует об окончании процесса решения.

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

Для приведения схемы в исходное положе, ние снимается напряжение с шин питания, с

10 помощью кнопок в цепях обратной связи обну ляются выходы усилителей У2 — У2 блоков и

2 — 2п и осуществляется возврат щеток иска-: теля И и размыкание выключателя В коммутатора 4.

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

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

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

Источники информации*

35 принятые во внимание при экспертизе

1. Васильев В. B. и др, Решение задач опти- мального иланировайия на электронных моделях..K., "Наукова Думка", 1966, с. 36 — 38.

2, Авторское свидетельство СССР Х 417802

Э кл. G О6 G 7/48, 1974 (прототип).

714421

Составитель И Лебедев

Техред М.Келемеш

Корректор, Г. Назарова

Редактор Д. Зубов

Заказ 9291/48

1иРаж 751 Подписное

ЦНИИПИ Государственного комитета СССР по делам юобретений и открытий

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

Филиал ППП "Патент", г, Ужгород, ул, Проектная, 4