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

Иллюстрации

Показать все

Реферат

 

289073

О П И С А Н И Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Республик

Зависимое от авт. свидетельства №вЂ”

МПК б 06g 3/10

G 06f 15/46

Заявлено 30.1Ч.1969 {№ 1327322/18-24) с присоединением заявки №вЂ”

Приоритет

Комитет по делам изобретений и открытий при Совете Министров

СССР

УДК 681.325.6{088.8) Опубликовано 08.Х11,1970. Бюллетень № 1 за 1971

Дата опубликования описания 5.1 I.1971

Авторы изобретения

А. А. Илюхин, Ю. П. Летунов и А. М. Плахотишин

Московский инженерно-физический институт

Заявитель

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ТРАНСПОРТНОЙ СЕТИ

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

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

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

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

q (u) + V (u ) = c (u); с (и ) = с (и); р (и) ) = 0;

<р(и ) )0, где р(и) и

25 Дуги и (или и ) считается заблокированной, если <р(и) =с(и) или V(u ) =с(и). В исходном состоянии р (и) = О, следовательно (и ) = c (u), и все дуги и заблокированы.

Процедура построения наибольшего потока

30 во вспомогательной сети, эквивалентная алгоритму Форда — Фуркерсона, и состоит в вы-. полнении конечного числа шагов, на каждом из которых: а) во вспомогательной сети, из которой исключены все заблокированные дуги, определяется какой-нибудь путь, соединяющий источник и сток; б) поток по выбранному пути увеличивгется на величину е; в=гп II(c(u), с(и ) — <р(и ) при этом дуга и, на которой достигается минимум, будет заблокирована, так как поток cp(u) станст равным пропускной способности с(и).

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

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

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

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

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

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

9 — по одному потенциальному и одному импульсному входу. Вход 11 и выход 12 коммутируются со входами и выходами аналогичных схем, образуя модель вспомогательной сети.

Входы 13 — 19 играют вспомогательную роль и служат для задания режимов работы. Такие схемы объединяются попарно, вход с выходом, как показано на фиг. 1, и образуют модели дуг и и и вспомогательной сети.

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

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

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

По входу 18 подается запирающий потенциал. Счетчики всех схем-модулей устанавливаются в «О» импульсом по входу 14. В датчиках 1 всех основных дуг и устаназливаются постоянные составляющие to случайной задержки пропорционально соответствующим пропускным способностям c(u), а в моделях всех вспомогательных дуг tg-— — О. Случайные составляющие величн t во всех схемах устанавливаются произвольно. Подается серия;lмпульсов па вход 15. Затем подается одиночный импульс на вход 16, в результате ",åãî вентнл I

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

2. 1цаг вычислительного процесса. а) Определение кратчайшего пути. На глод

15 импульсы не подаются; на вход 18 подаегся запирающий потенциал, а па вход 18 — огпшрающий потенциал; импульс установки подается на вход 17, после этого модель готова к определению кратчайших путей. Импульс подается на вход сети и получается дерево кратчайших путей, зафиксированное триггерами 20; на первом шаге вентили 10 и б вспомогательных дуг заперты потенциалом с выхода схемы совпадения 8, т. е. эти дуги заблокированы и не участвуют в процессе определения кратчайшего пути; б) Увеличение потока на единицу. На входы

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

Эти вентили образуют дерево, ориентированное противоположно, т. е. направленное к источнику (фиг. 2). Затем подается импульс на выход сети, т. е. в узел (сток сети), который проходит в обратном направлении (через вентили б) кратчайший путь, соединяющий источник и сток. При этом импульс, проходя через вентили 8 дуги и (или и ), принадлежащих этому пути, вычитает по единице из содержимого счетчиков этих дуг и добавляет по единице к содержимому счетчиков соответствующих дуг и (или и). Таким образом, уже после первого шага некоторые дуги и будут разблокированы, а содержимое их счетчиков будет равно единице. Вообще на любом шаге содержимое счетчика дуги и содержит величину, пропорциональную потоку с (и) через соответствующую дугу исходной транспортной сети, а содержимое, счет-иков дуг и — величину, пропорциональную разности с(и) — r,;,(u). Это следует из условия q(u)+- р(и ) =с(и).

3. Индикация минимального разреза.

Об окончании процесса построения наибольшего потока свидетельствует тот факт, что им289073 пульс, поданный на вход сети, не приходит на ее выход (так как все пути заблокированы).

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

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

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

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

2. Представляет интерес задача статистического анализа транспортной сети со случайными пропускными способностями дуг. Как уже отмечалось, эта задача не может быть эффективно решена»a универсальных ЗВМ.

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

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

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

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

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

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

289073

Фиа t фиг. Я

Составитель И. Н, Горелова

Редактор И. Г. Карнас Техред А. А. Камышникова Корректор Л, Л, Евдонов

Изд. № 33 Заказ 24/2 Тираж 4SO Подписное

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

Москва, )К-35, Ра шская наб., д. 4/5

Типография, пр, Сапунова, 2