УСТРОЙСТВО для МОДЕЛИРОВАНИЯ ТРАНСПОРТНОЙ СЕТИ Советский патент 1971 года по МПК G06F17/14 

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

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

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

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

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

ф(«)+ф(и )с(«); с(и )с{и); ф(и)0; 20ф(.

где ф(ы) и ф(и )-потоки через дуги и и и; с(и) - пропускная способность дуги исходной транспортной сети.

25 Дуги и (или и ) считается заблокированной,

если ф(«)с(«) или f(u)c(u). В исходном

состоянии ф(и)0, следовательно ф(и ) с(и),

полнении конечного числа шагов, на каждом из которых:

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

б)ноток по выбранному нути увеличивгется на величину е; е (с(ы), с (и )-ф(«0 ири этом дуга и, на которой достигается минимум, будет заблокирована, так как ноток ф(и) станет рапным нронускной способности с(«).

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

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

Отличие предложенного устройства от нрототипа состоит в том что в него введены:

ДСВИ -датчик случайных временных интервалов 1, который в ответ на импульс, поданный на его вход, выдает импульс на выходе через случайное время t, распределенное по заданному закону;

Реверсивный счетчик 2, нагрул :енный на схему совпадения 3 и собирательную схему 4, индикационный триггер 5, вентили 6-9.

Схема совпадения имеет на выходе потенциал отпирания (вентиля) лишь в том случае, когда содержимое счетчика равно нулю, а собирательная схема 4 лишь в этом случае имеет на выходе потенциал запирания.

Вентили 10, 6 имеют по три потенциальных входа и по одному импульсному, а вентили 7- 9 - по одному потенциальному и одному импульсному входу. Вход 11 и выход 12 коммутируются со входами и выходами аналогичных схем, образуя модель всномогательной сети. Входы 13-19 играют вспомогательную роль и служат для задания режимов работы. Такие схемы объединяются попарно, вход с выходом, как показано на фиг. 1,и образуют модели дуг м и ы вспомогательной сети.

Датчики случайных временных интервалов имеют два выхода: импульсный и потенциальный. Носледний подключен ко входу веитиля 6. В ответ на выходной сигнал на нервом из выходов ноявляется импульс через случайное время t, а на втором (потенциальном) выходе появляется широкий импульс, который начинается в момент поступления входного ймп-ульса и оканчивается через время о (о - лостоянная составляющая случайной величины t). Таким образом, в течение времени о вентиль 7 открыт.

Процесс построения наибольшего нотока осуществляется следующим образом.

1.Ввод исходных данных.

По входу 13 подается запирающий нотенциал. Счетчики всех схем-модулей устанавливаются в «О импульсом по входу 14. В датчиках / всех основных дуг и устанавливаются постоянные составляющие о случайной задержки пропорционально соответствующим

пропускным способностям с(и), а в моделях всех вспомогательных дуг 0. Случайные составляющие величин t во всех схемах устанавливаются произвольно. Подается серия импульсов на вход 15. Затем подается одиночный

импульс на вход 16, в результате чего вентили 5 и 7 открываются на время /о и в счетчики моделей основных дуг записываются числа, пропорциональные пропускным способностям дут исходной транспортной сети. Содержимое

счетчиков вспомогательных дуг остается разным нулю.

2.Шаг вычислительного процесса.

а)Определение кратчайщего пути. На БХОД 15 импульсы не подаются; на вход 18 подается

запирающий потенциал, а на вход 13 - отпирающий потенциал; импульс установки подается на вход 17, после этого модель готова к определению кратчайших путей. Р1мпульс подается на вход сети и получается дерево кратчайших путей, зафиксированное триггерами 20; на первом шаге вентили 10 и 6 вспомогательных дуг заперты потенциалом с выхода схемы совпадения 3, т. е. эти дуги заблокированы и не участвуют в процессе определения кратчайшего пути;

б)Увеличение потока на единицу. На входы 18 и 19 подаются отпирающие потенциалы, а на вход 13 - запирающий потенциал, в результате чего вентили 10 всех дуг запираются,

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

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

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

содержимое, счетчнков дуг и - величину, пропорциональную разности с(и)-(и). Это следует из условия ф(и)+ф() ()3. Индикация минимального разреза. Об окончании процесса построения наибольпульс, поданный на вход сети, не приходит на ее выход (так как все .пути заблокированы). Следовательно, величина максимального потока равна числу импульсов, пришедших на выход сети, а потоки в отдельных дугах равны содержимому счетчиков дуг и вспомогательной оси. Кроме того, представляет интерес разрез с минимальной пропускной способностью. Этот разрез состоит из тех заблокированных основных дуг и, к которым можно прийти по незаблокированным дугам, выйдя из стока, если ориентировать все незаблокированные дуги в обратном направлении. Это реализуется следующим образом. На входы 13 и 19 подаются запирающие потенциалы, а на вход 18-отпирающий потенциал. Подается импульс установки на вход 17. После этого вентили 6 незаблокированных дуг открыты, а вентили 9 заперты, в заблокированных дугах наоборот, вентили 6 заперты, а вентили 9 открыты.

Импульс, поданный на вход сети, проходит через незаблокированные дуги и не проходит через заблокированные дуги, устанавливая триггеры 5 этих дуг в «О, что фиксируется индикационными лампочками. Те из зафиксированных дуг, которые являются основными, и составляют минимальный разрез. Теперь поясним смысл введения датчика случайной задержки (ДСВИ).

ДСВИ выполняет две функции;

1.На некотором щаге вычислительного процесса могут быть одновременно получены два или более кратчайших путей. При этом может возникнуть ошибка, так как из всех дуг этих путей вычтется по единице потока, так как из всех дуг этих путей вычтется по единице потока, что неверно, если эти пути частично совпадают. Поэтому необходимо на каждом шаге получать единственный кратчайший путь. Для этого при определении кратчайшего дерева вслед за первым импульсом на вход сети через некоторое время подается второй, который вновь выбирает кратчайший путь, но только среди тех путей, которые совпали. Так как длины дуг случайны, вероятность повторного совпадения пренебрежимо мала. Если же сразу выбран единственный путь, второй импульс оставит его неизменным.

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

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

Предмет изобретения

1. Устройство для моделирования транспортной сети, содержащее в схеме-модели каждой сети триггер, один вход которого через

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

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

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

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

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

У1сточник

Сток

Фм. 2