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

Союз Советскик Сощиалистических Республик(22) Заявлено 310378 (21) 2600619/18-24с присоединением заявки Ио(23) Приоритет р2 С 06 С 7/122 Государственный комитет СССР по делам изобретений и открытий(72) Авторы изобретения С.В.Цой, Ким Ген Хо и Ю.С,Васильев Институт горного дела АН Казахской ССР(71) Заявитель 54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ПОТОКЕИзобретение относится к вычислительной технике и может бытьиспользовано при реждении ряда задачтеории операций, в частности прирешении задачи оптимального распре 5деления ресурсов и задачи синтезасетевых графиков в системе СПУ,Известно вычислительное устройство для моделирования задачи о мияимальном потоке, состоящее "иэ моделей дуг, в каждую иэ которой включенасхема индикации дугового минимального потока, и регулируемого источника противо-ЭДС, включенного междуначальной и конечной точками моделируемой сети 1,Недостаток устройства заключается в том, что оно решает задачу о минимальном потоке не для всех исходных 2 О данных. Действительно,при решении задачи на известном устройстве могут возникать пути в исследуемой сети,на всех дугах которых поток оказывается больше минимального предела потока 25 по дугам. С таких путей следует снять излишек потока, а поскольку на известном устройстве эта операция не предусмотрена, то получаемое решение не всегда правильно, т.е. величина минимального потока может оказаться завышенной. Наиболее близким техническим решением к предлагаемому является уст" ройство для решения задачи о минимальном потоке, содержащее счетчик, набираемую с помощью моделей дуг модель сети, счетчики дуг, выходы которых соединены .с входами соответствующих блоков индикации дуговых потоков, первые выходы которых соединены с первыми входами соответствующих моделей дуг, выходы которых подключены к входам соответствующих счетчиков дуг. Кроме того, устройство содержит генератор импульсов, блок управления и блок ввода-вывода информации, а каждая модель дуги состоит иэ двух формирователей потоковых ограничений, соединенных с задатчиками потоковых ограничений, и блока выбора потокового ограничения 21. Недостатком устройства являетсясложность его конструкции. Кроме того,оно не всегда дает правильное реше-ние задачи в связи с тем, что потокраспределяется не по критическимпутям, а по произвольным путям."йабираемую с помощью моделей дуг модель сети, счетчики дуг, выходыкоторых соединены с входами соответствующих блоков индикации дуговыхпотоков, первые выходы которых соединены с первыми входами соответствующих моделей дуг, выходи которыхподключены к входам соответствующихсчетчиков дуг, введены блоки коммутации дуг, блок коммутации, распределитель и компаратор, первый выходкоторого соединен с первыми входамиблоков коммутации дуг, выходы которых подключены к вторым входам.,соответствующих моделей дуг, третьи, входы которых соединены с первымвыходом блока коммутации, второйвыход которого подключен к входу:компаратора, второй выход которогосоединен с входом модели сети, выход которой подключен к первомувходу блока коммутации, второй входкоторого соединен с выходом распределителя и с вторыми входами блоковкоммутации дуг, третьи нходы которыхподклк)чены к вторым выходам соотв"ет-ствующих блоков индикации дуговыхпотоков, третьи выходы которых соединены с входом распределителя,третий выход компаратора подключен квходу счетчика,На фиг.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 сетипроходит второй импульс тока (нто рая единица потока), который засчитают соответствующие, счетчики 5и счетчик 4. Если на первом или нанекотором очередном шаге появляетсядуга (или дуги), поток в которойстал равен минимальному пределу потока по этой дуге, то сработаетсоотнетстнующий блок 8 индикациидугового минимальногопотока: эагдрится соответствующая индикаторная З 0 лампочка (на чертеже не показана),кратковременно включит распределитель 6, своей контактной группой16 разорвет данную модель 2 дугии контактной группой 12 подготовитвключение реле 10 и 11 соответствующего блока 9. Распределитель б поочередно включит реле 17 на определенный отрезок времени, достаточный для осуществления операции сравнения критических путей в компараторе 7, и реле 18 вместе с подготовленными реле 11 н соответствующеймодели 2 дуги. При срабатывании реле17 одна его контактная группа (а,ф 161 - фиг,2) включает внешнюю цепьс индикатором 22 тока, другая - отключает индикаторы 14 тока но всех моделях 2 дуг, третья (которая не показана на чертеже) - отключает нходсчетчика 4, при этом конденсатор 21компаратора 7 эарядится до напряжениякритического пути н модели 1сети. Затем, как только распределитель б включит реле 18 и реле 11в соответствующей модели 2 дуги, тозаново включится разорванная модель2 дуги, причем напряжение на ееконденсаторе 13 упадет до нуля. Приэтом во внешней цепи с помощью контактной группы 20 реле 18 включится индикатор 23 тока, который срабо тает, если вмодели 1 сети критический путь оказался больше, чем критический путь при разорванной модели2 дуги и не сработает, если критические пути при обоих состояниях 65 модели 2 дуги равны друг другу, таккак в этом случае через конденсатор21 компаратора 7 импульс тока пройти не может. Если критйческий путьоказался большим, т,е. если сработал индикатор 23 тока, то его контактная группа 25 подключит реле 10в соответствующей модели 2 дуги кплюсу источника постоянного напряжения, в результате чего разорван-ная модель 2 дуги включится зановои в дальнейшем не может подвегнуться разрыву, так как реле 10 этоймодели 2 дуги самоблокируется, Поскольку переключение внешней цепина индикатор 23 тока приводит к срабатыванию контактной группы 24 индикатора тока 22, то ее функция передается контактной группе 19 реле 18блока 3. Если на некотором шаге вмодели 1 сети (фиг,2) не образуетсяни одного пути от Н до К, а индикаторные лампочки (на чертеже не показаны) блоков 8 горят не все (этодоказывает, что потребность в потоке удовлетворена не во всех дугах),то кратковременно включается контактная группа 24 (Фиг.2) индикатора 22 тока, отчего все реле 10подключатся к источнику постоянногонапряжения, При этом сработают только те реле 10, которые были предварительно подготовлены к включенйю 30с помощью контактных групп 12, т.е,те реле 10, которые входят в разорванные на предыдущихшагах модели 2дуг, При этом одни контактные группытаких реле 10 заново включат разорванные модели 2 дуг, разряжая нриэтом соответствующие конденсаторы 3до нуля, а сами реле 10 самоблокируются другими своими контактнымигруппами. Эта операция восстанавливает все пути в модели 1 сети, что 40обеспечивает возможность дальнейшего решения задачи. Решение задачизаканчивается тогда, когда зажгутсяиндикаторные лампочки всех блоков 8,Результат решения снимается со-счет-45чиков, причем со счетчика 4 снимается величина минимального потока,исследуемой сети, а с дуговых счетчиков 5 снимается информация о распределении этого потока по дугам 50сети,Разрыв моделей дуг, в которых впроцессе решения поток становитсяравным минимальным дуговым потокам,позволяет отказаться в каждой модели 55 дуги от второго счетчика импульсовР отсчитывающего избыточный поток, а это позволяет, в свою очередь, обойтись без сложных блоков управления этими счетчикамидля каждой модели дуги.Таким образомвследствие введения новых блоков и связей между ними - увеличйлась точность"моделирования и упростилась конструкция устройства.Формула изобретенияУстройство для решения задачи оминиМальном потоке, содержащее счетчик, модель сети, счетчики дуг, выходы которых соединены с входамисоответствующих блоков индикации дуговых .потоков, первые выходы которыхсоедийены с первйми входами соответствующих моделей дуг, выходы которыхподключены к входам соответствующихсчетчиков дуг, о т л и ч а ю щ е ес я тем, что, с целью увеличенияточности моделирования и упрощенияконструкции, в него введены блоки коммутации дуг, блок коммутации, распределитель и компаратор, первый выход которогосоеди"нен с первыми входами блоков коммутации дуг, выходы которых подключенык вторым входам соответствующих моделей дуг, третьи входы которых соединены с первым выходом блока коммутации, второй выход которого подключенк входу компаратора, второй выходкоторого соединен с входом моделисети, выход которой подключен к первому входу блока коммутации, второйвход которого соединен с выходомраспределителя и с вторыми входамиблоков коммутации дуг, третьи входыкоторых подключены к вторым выходамсоответствующих блоков индикации дуговых потоков, третьи выходы которыхсоединены с входом распределителя,третий выход компаратора подключенк входу счетчика,Источники информациипринятые во внимание при экспертизе1, Авторское свидетельство СССР9324632, кл. С 06 С 7/48, 1970,2. Васильев В,В Додонов А.Г.Гибридные модели задач оптимизации.К.,Наукова думка, 1974. с. 163165 (прототип),744 б 20 ПодписноеР каз 381 5 Тираж 751ЦНИИПИ Государственного комитета Спо делам изобретений и открытий 13035, Москва, Ж, Раушская наб.,4 Филиал ППППатентф , г. Ужго Проектна Составитель А.Яицков дактор А.Долинич Техред М. Кузьма Корректор Н, Стец