Устройство для решения задачи о минимальном потоке Советский патент 1980 года по МПК G06G7/122 

(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ПОТОКЕ Изобретение относится к вычислительной технике и может быть, использовано при ранении ряда задач теории операций, в частности при решении задачи оптимального распределения ресурсов и задачи синтеза сетевых графиков в системе СПУ, Известно вычислительное устройство для моделирования задачи о ми йимальном потоке, состоящее из моделей дуг, в каждую из которой вк.точен схема индикации дугового минимального потока, и регулируемого источника противо-ЭДС, включенного между начальной и конечной точками моделируемой сети 1. Недостаток устройства заключается в том, что оно решает задачу о минимальном потоке не для всех исходных данных.Действительно,при решении задачи на известном устройстве могут возникать пути в исследуемой сети,на всех дугах которых поток оказывается больше минимального предела потока по дугам. С таких путей следует снят излишек потока, а поскольку на извес ном устройстве эта операция не предусмотрена, то получаемое решение не всегда правильно, т.е. величина мини мального потока может оказаться завышенной . Наиболее близким техническим решением к предлагаемому является устройство для решения задачи о- минимальном потоке, содержащее счетчик, набираемую с помощью моделей дуг модель сети, счетчики дуг, выходы которых соединены с входами соответствующих блоков индикации дуговых потоков первые выходы которых соединены с , первыми входами соответствующих моделей дуг, выходы которых подключены к входам соответствующих счетчиков дуг. Кроме того, устройство содержит генератор импульсов, блок управления и блок ввода-вывода информации, а каждая модель дуги состоит из двух формирователей потоковых ограничений, соединенных с задатчиками потоковых ограничений, и блока выбора потокового ограничения 2. Недостатком устройства является сложность его конструкции.Кроме того, оно не всегда дает правильное peiiieние задачи в связи с тем, что поток распределяется не по критическим путям, а по произвольным путям.

Цель изобретения - увеличение ТОЧНОСТИ моделирования и упрощение конструкции.

Ука айная Цель достигается тём, что в устройстве, содержащем счетчик, набираемую с помощью моделей дуг модель сети, счетчики дуг, выходы которых соединены с входами соответствующих блоков индикации дуговых потоков, первые выходы которых соединены q первыми входами соответствующих моделей дуг, выходы которых подключены к входам соответствующих бчетчйков дуг,введены блоки коммутаций ЛУГ, блок коммутации, распределитель и компаратор, первый выход которого соединен с первыми входами блоков коммутации дуг, выходы которых подключены к вторым входам , соответствующих моделей дуг, третьи входы которых соединены с первым выходом блока коммутации, второй выход которого подключен к входу ,: X компаратора, второй выход которого соединен с входом модели сети, выход которой подключен к первому входу блока коммутации, второй вход которого соединен с выходом распределителя и с вторыми входами блоков коммутации дуг, третьи входы которых подключены к вторым ствующих блрков индикации дуговых потоков, третьи выходы которых соединены с входом распределителя,третий выход компаратора подключен к входу счетчика.

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

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

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

Модель 2 дуги сЬдёржит rrdTSffejS.. ельно соединенный конденсатор 13 (фиг.2), индикатор 14 тока, диод 15 и контактную группу 16 реле блока 8. Блок 3 коммутации выполнен на реле 17 и реле 18 с контактными группами 19 и ,26. Компаратор 7 выполнен на йбндёнсатбре 21 и,двух индикаторах 22 и 23 тока, имеющих контактные руппы 24 и 25 соответственно.

Уст рой ств о р або тает ел едующ им бразом. С. .. .-:-/На собранной модели 1 сети (фиг.2) аряжают конденсаторы 13 моделей 2 yt до напряжения некоторой величи-; ы, §.в счетчиках 5 дуг устанавлиают емкости счета, срответствуквдие инимальным дуговьм потокам. В под744620

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

16разорвет данную модель 2 дуги

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

17одна его контактная группа (а - фиг.2) включает внешнюю цеп

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

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

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

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

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

to

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

Устройство для решения задачи о минимальнее потоке, содержащее счет5чик, модель сети, счетчики дуг, выходы которых соединены с входами со6тветств1ую1дих блоков индикации дуговых потоков, первые выходы которых соедийены с пё эвыми входами ссэответ0ствующих моделей дуг, выходы которых подключены к входам соотвётствуЮЩи х счётчиков дуг, отличающеес я тем, что, с целью увеличения точности моделирования и упрощения

5

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

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

1.Авторское свидетельство СССР №324632, кл. G Об G 7/48, 1970.

2.Васильев В.В., Додонов А.Г. Гибридные модели задач оптимизации. К.,Наукова думка-, 1974. с. 163165 (прототип)