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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советскик

Сощиалистических

Республик (61) Дополнительное к авт. свид-ву— (22) Заявлено 310378 (21) 2600619/18-24 с присоединением заявки Ио (23) Приоритет р 2

G 06 G 7/122

Государственный комитет

СССР но делам изобретений и открытий

Опубликовано 30.06.80, Бюллетень Но 24

Дата опубликования описания 300680 (53) УДК 681. 333 (088.8) (72) Авторы изобретения

С.В.Цой, Ким Ген Хо и Ю.С.Васильев

Институт горного дела AH Казахской ССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ

О МИНИМАЛЬНОМ ПОТОКЕ

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

Известно вычислительное устройство для моделирования задачи о мияимальном потоке, состоящее "иэ моделей дуг, в каждую иэ которой включена схема индикации дугового минимального потока, и регулируемого источника противо-ЭДС, включенного между начальной и конечной точками моделируемой сети (1), Недостаток устройства заключается в том, что оно решает задачу о минимальном потоке не для всех исходных 20 данных. Действительно,при решении задачи на известном устройстве могут возникать пути в исследуемой сети,на всех дугах которых поток оказывается больше минимального предела потока 25 по дугам. С таких путей следует снять излишек потока, а поскольку на известном устройстве эта операция не предусмотрена, то получаемое решение не всегда правильно, т.е, величина мини-ЗО мального потока может оказаться завышенной.

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

Недостатком устройства является сложность его конструкции. Кроме того, оно не всегда дает правильное реше- ние задачи в связи с тем, что поток распределяется не по критическим путям, а по произвольным путям.

744620

Цель изобретения - увеличение

" точности моделирования и упрощение конструкции.

Указанная цель достигается тем, что в устройстне, содержащем счетчик, йабираемую с помощью моделей дуг модель сети, счетчики дуг, выходы которых соединены с входами соответствующих блоков индикации дуговых потоков, первые выходы которых соединены с первыми входами соответствующих моделей дуг, выходи которых подключены к входам соответствующих счетчиков дуг, введены блоки коммутации дуг, блок коммутации, распределитель и компаратор, первый выход которого соединен с первыми входами блоков коммутации дуг, выходы которых подключены к вторым входам, соответствующих моделей дуг, третьи, входы которых соединены с первым выходом блока коммутации, второй выход которого подключен к входу: компаратора, второй выход которогосоединен с входом модели сети, выход которой подключен к первому входу блока коммутации, второй вход которого соединен с выходом распределителя и с вторыми входами блоков коммутации дуг, третьи нходы которых подклн)чены к вторым выходам "cо»ответ»- ствующих блоков индикации дуговых потоков, третьи выходы которых соединены с входом распределителя,третий выход компаратора подключен к входу счетчика.

На фиг.1 изображена блок-схема устройства.

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

На фиг.2 изображен один иэ возможных вари(нтон конкретного исполнения устройства. Каждый блок 9 коммутации дуги выполнен на реле 10 и 11 и содержит контактную группу 12 реле, -входящее н блок 8.

Модель 2 дуги содержит послед(о»йа- . тельно соединенный конденсатор 13 (фиг.2), индикатор 14 тока, диод 15и контактную группу 16 реле блока 8.

Блок 3 коммутации выполнен на реле

17 и реле 18 с контактными группами

19 и 20. Компаратор 7 выполнен на конденсаторе 21 и,днух индикаторах

22 и 23 тока, имеющих контактные группы 24 и 25 соответственно.

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

На собранной модели 1 сети (фиг.2) заряжают конденсаторы 13 моделей 2 дуг до напряжения некоторой величи-, ны, а в счетчиках 5 дуг устанавли вают емкости счета, соответствующие мйнимальным дуговым потокам. В йод= готовленной таким обраэОм модели 1 сети включают на малый отрезок времени внешнюю цепь с индикатором 22 тока. В результате этого, через модель 1 сети по ее критическому пути, пройдет импульс тока, отчего конденсатор 21 компаратора 7 заря дится до напряжения критического пути и сработают:. индикаторы 14 тока в моделях 2 дуг этого пути и индикатор 22 тока компаратора 7, что, н свою очередь, застанляет сработать соответствующие счетчики

5 и счетчик 4, которые и отсчитают по одному импульсу (по одной. единице потока). На этом заканчивается один

15 шаг работы устройстна. Следующий шаг начинается новым кратконременный включением внешней цепи, в результате чего через модель 1 сети проходит второй импульс тока (нто20 рая единица потока), который засчитают соответствующие, счетчики 5 и счетчик 4. Если на первом или на некотором очередном шаге появляется дуга (или дуги), поток в которой стал равен минимальному пределу потока по этой дуге, то сработает соотнетстнующий блок 8 индикации дугового минимального потока: эагдрится соответствующая индикаторная

З0 лампочка (на чертеже не показана), кратковременно включит распределитель 6, своей контактной группой

16 разорвет данную модель 2 дуги и контактной группой 12 подготовит включение реле 10 и 11 соответствующего блока 9. Распределитель б поочередно включит реле 17 на определенный отрезок времени, достаточный для осуществления операции сравнения критических путей в компара40 торе 7, и реле 18 вместе с подготовленными реле 11 н соответствующей модели 2 дуги. При срабатывании реле

17 одна его контактная группа (а, б — фиг.2) включает внешнюю цепь с индикатором 22 тока, другая — отключает индикаторы 14 тока но всех моделях 2 дуг, третья (которая не показана на чертеже) - отключает нход счетчика 4, при этом конденсатор 21 компаратора 7 эарядится до напряжения критического пути н модели 1 сети. Затем, как только распределитель б включит реле 18 и реле 11 в соответствующей модели 2 дуги, то заново включится разорванная модель

2 дуги, причем напряжение на ее конденсаторе 13 упадет до нуля. При этом во внешней цепи с помощью контактной группы 20 реле 18 включится индикатор 23 тока, который срабо60 тает, если в модели 1 сети критический путь оказался больше, чем критический путь при разорванной модели

2 дуги и не сработает, если критические пути при обоих состояниях

65 модели 2 дуги равны друг другу, так

7446 20

6 как в этом случае через конденсатор

21 компаратора 7 импульс тока пройти не может. Если критйческий путь оказался большим, т.е. если сработал индикатор 23 тока, то его контактная группа 25 подключит реле 10 в соответствующей модели 2 дуги к плюсу источника постс)янного напряжения, в результате чего разорван- ная модель 2 дуги включится заново и в дальнейшем не может подвегнуться разрыву, так как реле 10 этой модели 2 дуги самоблокируется. Поскольку переключение внешней цепи на индикатор 23 тока приводит к срабатыванию контактной группы 24 индикатора тока 22, то ее функция пере- 5 дается контактной группе 19 реле 18 блока 3. Если на некотором шаге в модели 1 сети (фиг.2) не образуется ни одного пути от Н до К, а индикаторные лампочки (на чертеже не по- 20 казаны) блоков 8 горят не все (это ,показывает, что потребность в потоке удовлетворена не во всех дугах), то кратковременно включается контактная группа 24 (фиг.2) индика- 25 тора 22 тока, отчего все реле 10 подключатся к источнику постоянного напряжения, При этом сработают только те реле 10, которые были предварительно подготовлены к включенйю "j() с помощью контактных групп 12, т.е. те реле 10, которые входят в разорванные на предыдущих шагах модели 2 дуг, При этом одни контактные группы таких реле 10 заново включат разорванные модели 2 дуг, разряжая нри этом соответствующие конденсаторы 3 до нуля, а сами реле 10 самоблокируются другими своими контактными группами. Эта операция восстанавливает все пути в модели 1 сети, что 4О обеспечивает возможность дальнейшего решения задачи. Решение задачи заканчивается тогда, когда зажгутся индикаторные лампочки всех блоков 8.

Результат решения снимается со-счет- 45 чиков, причем со счетчика 4 снимается величина минимального потока. исследуемой сети, а с дуговых счетчиков 5 снимается информация о распределении этого потока по дугам 5Q сети.

Разрыв моделей дуг, в которых в процессе решения поток становится равным минимальным дуговым потокам, позволяет отказаться в каждой модели 55 дуги от второго счетчика импульсов

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

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

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

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

Источники информации принятые во внимание при экспертизе

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

9324632, кл. G 06 G 7/48, 1970.

2. Васильев В.В., Додонов A.Ã.

Гибридные модели задач оптимизации.

К., Наукова думка -, 1974. с. 163165 (прототип) .

744б20

ЖиР. Л

Составитель А. Яицков

Техред М. Кузьма

Редактор А.Долинич

Корректор Н. Стец

Заказ 3818/15 Тираж 751 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 .Филиал ППП Патент, г. Ужгород, ул. Проектная, 4