Устройство для моделирования транспортной сети

Союз Советских Социалистических РеспубликЗаявлено 30,1 Ч.1969 ( 1327322/18-24) кием заявки-п исо иоритет Комитет по деламобретеивй и открцтнрк Совете сликистровСССР 1.325.6 (088.8) УД публиковано 08,Х 11,1970. Бюллетень1за 1971ата опубликования описания 5.11.1971 Авторыизобретения А. Илюхин, Ю. П, Летунов и А. М, Плахотиши Москов инженерно-физический инстит аявите СТРОЙ С ЛЯ МОДЕЛИРОВАНИЯ ТРАНСПОРТНОЙ СЕТ Задача о наибольшем потоке решается с помощью алгоритма Форда - Фуркерсона и сводится к отысканию цегей, увеличивающих поток, Эквивалентное преобразование заданной транспортной сети сводит задачу к отысканию кратчайших путей во вновь полученной сети, которую в дальнейшем будем называть вспомогательной.Вспомогательная сеть получается из исход ной заменой каждой дуги двумя дугами, ориентированными в разных направлениях. Дуги вспомогательной сети, совпадающие по направлению с соответствующими дугами исходной сети, будем называть основными и обозна чать через и, остальные дуги - вспомогательными и обозначить их через и, Кроме того, вводятся следующие условия: р(и)+р(и) =с(и); с(и) =с(и); р(ир(и) )О,где р(и) и с(и) - про п транспортно Дуги и (и если р(и) = состоянии р и все дуги и Процедура во вспомога ритму Форди и; дной ннои одном с(и)тока алго- выПредложенное устройство относится к вычислительной технике и предназначено для построения максимального потока в транспортной сети с учетом пропускной способности и объема перемещаемого груза от источников к стокам в каждой из ветвей. Схема моделирует одну ветвь (дугу) сети с учетом ее пропускной способности и потока через нее, имеющих строго определенные (детерминированные) или вероятностные значения, Соединение этих моделей в адекватную схему транспортной сети позволяет просто и в наглядной форме получать оптимальный план распределения грузов.Известны устройства для решения детерминированных транспортных задач с применением источников тока и напряжений с пассивными линейными и нелинейными элементами, содержащие триггеры, вентили, линии задержки, К недостаткам этих устройств относятся: зависимость точности решения задачи от объема моделируемой сети, возможность решения задач только с детерминированными параметрами, сложность автоматизации управления моделью.Предложенное моделирующее устройство выполнено на дискретных логических элементах и отличается тем, что в него введены датчик случайных временных интервалов, реверсивный счетчик и индикационный триггер. Это позволяет расширить функциональные возможности устройства и повысить точность,р(и) - потоки через дуги иускная способность дуги исхой сети.ли и) считается заблокировас(и) или р(и) =с(и), В исхполнении конечного числа шагов, на каждомиз которых;а) во вспомогательной сети, из которой исключены все заблокированные дуги, определяется какОЙ-нибудь путь, соединяющиЙ истО 1 ник и сток;б) поток по выбранному пути увеличивгетсяна величину е; в=п 1 п(с(и), с(иИ - ср(и) приэтом дуга 11, на которой достигается минимум,будет заблокирована, так как поток ср(и) станст равным пропускноц способности с(и).1-1 апбольший поток построен, когда все пут 11пз исто шика в сток заблокированы. Отметим,что на некотором шаге процесса заблокированная дга 11 (или 11) может разблокироваться. Это происходит в том случае, если на этомшаге увеличивается поток через соответствующую дугу и (или и), Тем не менее, процесскончен, так как на каждом шаге поток увеличивается. Таким образом, на каждом шаге необходимо находить какой-нибудь путь из источника в сток. В частности, если придать всемдугам произвольные длины, можно каждыйраз находить кратчайший путь,На фиг. 1 изображена схема предлокенного устройства; на фиг. 2 - дуги транспортнойсети.Отличие предложенного устройства от прототипа состоит в том что в него введены:ДСВИ - датчик случайных временных интервалов 1, который в ответ на импульс, поданный на его вход, выдает импульс на выходечерез случайное время 1, распределенное позаданному закону;Реверсивный 1 счетчик 2, нагруженный на схему совпадения 3 и собирательную схему 4, индикационный триггер 5, вентили 6 в .Схема совпадения имеет на выходе потенциал отпирания (вентиля) лишь в том случае,когда содержимое счетчика равно нулю, а собирательная схема 4 лишь в этом случаеимеет на выходе потенциал запирания,Вентили 10, б имеют по три потенциальныхвхода и по одному импульсному, а вентили 7 -9 - по одному потенциальному и одному импульсному входу. Вход 11 и выход 12 коммутируются со входами и выходами аналогичныхсхем, образуя модель вспомогательной сети.Входы 13 - 19 играют вспомогательную роль ислужат для задания режимов работы. Такиесхемы объединяются попарно, вход с выходом,как показано на фиг. 1, и образуют модели дуги и и вспомогательной сети.Датчики случайных временных интерваловимеют два выхода: импульсный и потенциальный, Последний подключен ко входу вентиля б. В ответ на выходной сигнал на первомиз выходов появляется импульс через случайное время 1, а на втором (потенцпальном) выходе появляется широкий импульс, которыйначинается в момент поступления входногоимпульса и оканчивается через время 1, (1, -постоянная составляющая случайной величины 1 И. Таким образом, в течение временивентиль 7 открыт.5 Щ 15 20 25 30 35 4 О 45 50 55 60 65 Процесс построения наибольшего потокаосуществляется следую 1 цим образом.Ввод исходных данных,По входу 13 подается запирающий потенциал, Счетчики всех схем-модулей устанавливаются в О импульсом по входу 14. В датчиках 1 всех основных дуг и устанавливаютсяпостоянные составляющие 1 о случайной задержки пропорционально соответствующимпропускным способностям с(и), а в моделяхвсех вспомогательных дуг 1= - О. Случайные составляющие велич:11 во всех схемах устанавлпваются произвольно. Подается серия;1 мпульсов па вход 15, Затем подается одиночныйимпульс на вход 16, в результате чего вентили6 и 7 открываются на время 1 и в счетчикимоделей основных дуг записывгпотся числа,пропорциональные пропускным способностямдуг исходной транспортной сети, Содержимоесчетчиков вспомогательных дуг остается равНЫМ НУЛ 10.2. 1 Цаг вычислительного процесса.а) Определение кратчайшего пути. На гход15 импульсы не подаются; на вход 18 подае 1 сязапирающий потенциал, а па вход 13 - оггшрающий потенциал; импульс установки подается на вход 17, после этого модель готова копределению кратчайших путей. Импульс подается на вход сети и получается дерево кратчайших путей, зафиксированное триггерами 20;на первом шаге вентили 10 и б вспомогательных дуг заперты потенциалом с выхода схемысовпадения 3, т. е. эти дуги заблокированы ине участвуют в процессе определения кратчайшего пути;б) Увеличение потока на единицу. На входы18 и 19 подаются отпирающие потенциалы,а на вход 13 - запирающий потенциал, в результате чего вентили 10 всех дуг запираются,а вентили б открываются лишь в тех дугах,которые относятся к дереву кратчайших путей.Эти вентили образуют дерево, ориентированное противоположно, т. е. направленное к источнику (фиг. 2), Затем подается импульс навыход сети, т. е. в узел (сток сети), которыйпроходит в обратном направлении (через вентили б) кратчайший путь, соединяющий источник и сток. При этом импульс, проходя черезвентили 8 дуги и (или 11 И, принадлежащихэтому пути, вычитает по единице из содержимого счетчиков этих дуг и добавляет по единице к содержимому счетчиков соответствующих дуг и (или и). Таким образом, уже послепервого шага некоторые дуги и будут разблокированы, а содержимое их счетчиков будетравно единице, Вообще на любом шаге содержимое счетчика дуги и содержит величину,пропорциональную потоку ср(и) через соответствующую дугу исходной транспортной сети, асодержимое, счет иков дуг и - величину, пропорциональную разности с(и) - ,;,(и), Это следует из условия с(и)+1 р(и) =с(и),3, Индикация минимального разреза,Об окончании процесса построения наибольшего потока свидетельствует тот факт, что импульс, поданный на вход сети, не приходит на ее выход (так как все пути заблокированы). Следовательно, величина максимального потока равна числу импульсов, пришедших на выход сети, а потоки в отдельных дугах равны содержимому счетчиков дуг и вспомогательной оси. Кроме того, представляет интерес разрез с минимальной пропускной способностью. Этот разрез состоит из тех заблокированных основных дуг и, к которым можно прийти по незаблокированным дугам, выйдя из стока, если ориентировать все незаблокированные дуги в обратном направлении, Это реализуется следующим образом. На входы 13 и 19 подаются запирающие потенциалы, а на вход 18 - отпирающий потенциал. Подается импульс установки на вход 17. После этого вентили б незаблокированцых дуг открыты, а вентили 9 заперты, в заблокированных дугах наоборот, вентили 6 заперты, а вентили 9 открыты.Импульс, поданный на вход сети, проходит через незаблокировацные дуги и не проходит через заблокированные дуги, устанавливая триггеры б этих дуг в О, что фиксируется индикационными лампочками. Те из зафиксированных дуг, которые являются основными, и составляют минимальный разрез. Теперь поясним смысл введения датчика случайной задержки (ДСВИ).ДСВИ выполняет две функции:1. На некотором шаге вычислительного процесса могут быть одновременно получены два или более кратчайших путей. При этом может возникнуть ошибка, так как из всех дуг этих путей вычтется по единице потока, так как из всех дуг этих путеи вычтется по единице потока, что неверно, если эти пути частично совпадают. Поэтому необходимо на каждом шаге получать единственный кратчайший путь. Для этого при определении кратчайшего дерева вслед за первым импульсом ца вход сети через некоторое время подается второй, который вновь выбирает кратчайший путь, но только среди тех путей, которые совпали. Так как длины дуг случайны, вероятность повторного совпадения пренебрежимо мала. Если же сразу выбран единственный йуть, второй импульс оставит его неизменным.2. Представляет интерес задача статистического анализа транспортной сети со случайными пропускными способностями дуг. Как уже отмечалось, эта задача не может быть эффективно решена ца универсальных ЗВМ, Описанная модель благодаря ее быстродействию (которое объясняется, во-первых, скоростью определения кратчайшего пути и, вовторых, тем, что большое число случайных параметров вырабатывается одновременно) позволяет эффективно решать указанную задачу. Для этого длительность импульса на потенциальном выходе датчика 1 должна равняться не постоянной составляющей, а самой 5 10 15 20 25 30 35 40 45 50 55 60 случайной величине 1, а в качестве 1 необходимо взять случайную величину, распределенную по тому же закону, что и пропускная способность дуги с(и). Тогда, определяя наибольший поток, мы будем каждый раз получать одно цз возможных случайных значений этого потока ц по накопленным статическим данным можно будет определить функцшо распределения величины наибольшего потока.Предмет изобретения1. Устройство для моделирования транспортной сети, содержащее в схеме-модели каждой сети триггер, один вход которого через линию задержки подключен к аноду диода, а другой - к катоду диода, соединенного с выходом вентиля, связанного с выходом триггера, отличающееся тем, что, с целью определения наибольшего потока в транспортной сети со случайными пропускными способностями дуг, в схему модели введены датчик случайных временных интервалов, подключенный ко входу указанного вентиля, и р евер сивный счетчик, связанньш с потенциальной собирательной схемой и потенциальной схемой совпадения, вход сложения которого через вентиль, соединенный с потенциальным выходом датчика случайных временных интервалов, связан с устройством управления, выход схемы совпадения соединен со вторым потенциальным входом вентиля, через который импульсный выход датчика случайных временных интервалов соединен со входом линии задержки и анодом диода, п вторым потенциальным входом вентиля, подключенного к нулевому выходу триггера; импульсный вход этого вентиля соединен с катодом диода, а его выход подключен к одиночному входу трцтгера, ко входу датчика случайных временных интервалов и через вентиль, связанный с устройством управления, подключен ко входу вычитания реверсивного счетчика ц ко входу сложения реверсивного счетчика, входящего в состав схемы-модели другой дуги.2. Устройство по п, 1, отличающеся тем, что, с целью фиксации разреза с минимальной пропускной способностью, выход схемы совпа. дения связан с потенциальным входом вентиля, через который катод диода соединен с нулевым входом дополнительно введенного индикационного триггера, нулевой выход которого соединен с индикационной лампочкой.3. Устройство по пп. 1 и 2, отличающееся тем, что, с целью задания режимов работы, с устройством управления соединены один из потенциальных входов вентиля, подключающего выход датчика случайных временных интервалов к аноду диода, один из потенциальных входов вентиля, соединяющего катод диода с датчиком случайных временных интервалов, нулевой вход триггера, связанного с указанными вентилями, единичный вход установки нуля реверсивного счетчика,289073 фаз 1ф.иг. ЯСоставитель И. Н, Горелова Редактор И. Г. Карнас Техред А. А. Камышникова Корректор Л, Л, ЕвдоновИзд.33 Заказ 24/2 Тираж 480 Подписное ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Ж, Раунская наб., д. 4/5Типография, пр, Сапунова, 2