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

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

Иллюстрации

Показать все

Реферат

 

OnИСАйИE

ИЗОБРЕТЕНИЯ

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

387369

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

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

Республик

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

М. Кл. G 06f 15/20

Заявлено 30.Ill.1971 (№ 1640777/18-24) с присоединением заявки №

Приоритет

Опубликовано 21.V1.1973. Бюллетень ¹ 27

Дата опубликования описания 26.XII.1973

Гасударственный комитет

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

УДК 681.333(088.8) Авторы изобретения

В. В. Васильев, А. Г. Додонов и В. В. Федотов

Киевский ордена Трудового Красного Знамени институт инженеров гражданской авиации

Заявитель

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

О МАКСИМАЛЬНОМ ДИНАМИЧЕСКОМ ПОТОКЕ

Изобретение относится к области вычислительной техники.

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

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

На чертеже приведена блок-схема устройства.

Устройство содержит генератор импульсов

1, модели задач кратчайшего пути 2 и 8, блок определения динамического потока 4 и блок определения ветвей 5.

Устройство для моделирования задачи о максимальном динамическом потоке работает следующим образом, Устройство представляет связанные между собой две сети — «сеть времени» и «транспортную сеть». На «сети времени», начиная с времени ее кратчайшего пути, определяются последовательно на каждый следующий момент времени пути заданной продолжительности. Соответственно для

5 каждого момента времени на подмножестве ветвей сети, попавших в путь заданной продолжительности, па «транспортпой сети» определяется стационарный поток. Если на какойлибо момент времени нового пути не образу10 ется, на «транспортной сети» повторяется предыдущий стационарный поток. Сумма всех стационарных потоков за время, в течение которого определяется динамический поток, и определит его, 15

Модель задачи кратчайшего пути 2, предназначенная для моделирования «сетн времени», содержит соединенные между собой согласно топологии исследуемой сети модели

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

«транспортной сети», содержит соединенные

25 между собой согласно топологии двойственной сети модели ветвей («a чертеже пе показаны), в которые записывается информация, соотвегствующая пропускным способностям ветвей. В блоке определения ветвей 5 записывается вреЗО мя, за которое определяется поток.

387369 д

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

Составитель Г. Сорокин

Техред Т. Курилко

Редактор E. Гончар

Корректоры: А. Васильева и Т. Гревцова

Заказ 3453/2 Изд, Ма 924 Тираж 647 Подписное

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

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

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

5 строЙство I I моделирования задQ IH максимальном динамическом потоке, содержащее генератор импульсов, выход которого соединен со входами модели задачи кратчайшего пути, блока определения динамического потока и блока определения ветвей, соединенного двуеторонними связями с моделью зада !и кратчайшего пути и блоком определения динамического потока, отличаюцееся тем, IIT(), с целью упрощения устройства, оно содержит

5 вторую модель задачи кратчайшего пути, соединенную с блоком определения ветвей и блоком определения динамического потока и подключенную к генератору импульсов.