Алгоритм расчета максимального потока в сетях

ШАГ 1. Начальные присваивания. Текущему значению Ат максимального потока в сети присваиваем значение 0. ШАГ 2. Выбор независимых маршрутов в сети и определение потоков в них. Из всего множества возможных маршрутов в сети от источника к стоку выбираем независимые маршруты М1, … , Мk, не имеющие общих вершин, кроме начальной (источника vи) и конечной (стока vс). Для каждого выбранного маршрута Мi (1£ i £ k) определяем максимальный поток А(Мi).ШАГ 3. Коррекция текущего значения максимального потока в сети. Прибавляем найденные на ШАГе 2 значения максимальных потоков в независимых маршрутах М1, … , Мk к текущему общему максимальному потоку в сети: Ат:= Ат + А(М1)+ А(М2)+…+ А(Мk).ШАГ 4. Коррекция сети. Найденные на ШАГе 2 максимальные потоки А(М1), … , А(Мk)вычитаем из пропускной способности соответствующих дуг сети. Дуги с нулевой остаточной пропускной способностью удаляем.ШАГ 5. Проверка завершения работы алгоритма. Если после коррекции в сети не осталось маршрутов из источника vи в сток vс, то искомый максимальный поток в сети равен найденному текущему А:= Ат, алгоритм завершает свою работу, поскольку все пропускные возможности сети исчерпаны. Если же в корректированной сети существуют маршруты из источника vи в сток vс, то переход на ШАГ 2 и продолжение выполнения алгоритма.Пример 2. Найти максимальный поток в сети на рис.1.15 по данному алгоритму. Решение.ШАГ 1. Начальные присваивания. Ат: = 0.

I итерация. ШАГ 2. Выбор независимых маршрутов в сети и определение потоков в них. В качестве М1 возьмем маршрут(vи=V1, V2, V5, vс=V7), рассмотренный в примере 1. Для него А(М1) = 10.

Также несложно выделить независимый от М1 маршрут М2 = (vи=V1, V3, V6, vс=V7). Выполним для него расчет максимальной пропускной способности и скорректируем пропускную способность дуг: А(М2)= min {d13, d36, d67}= min {45, 40, 30}=30. d13¢= d13 - 30 = 15, d36¢= d36 - 30 = 10, d67¢= d67 - 30 = 0.

ШАГ 3. Коррекция текущего значения максимального потока в сети. Ат:= Ат + А(М1)+ А(М2) = 0 + 10+ 30 = 40.ШАГ 4. Коррекция сети. Найденные на ШАГе 2 максимальные потоки А(М1), А(М2) в маршрутах М1, М2 вычитаем из пропускной способности их дуг. Дуги с нулевой остаточной пропускной способностью удаляем. Результат дан на рис.1.16 а. а) б)Рис.1.16. Результат коррекции сети после итераций I и IIШАГ 5. Проверка завершения работы алгоритма. В корректированной сети (рис.1.16 а) существуют маршруты из источника vи в сток vс, например М3 = (vи=V1, V4, V2, V5, vс=V7). Продолжение выполнения алгоритма.

II итерация. ШАГ 2. В качестве единственного независимого маршрута примем М3 = (vи=V1, V4, V2, V5, vс=V7). Для него:

А(М3)= min {d14, d42, d25, d57}= min {15, 10, 10, 15}=10.

d14¢= d14 - 10 = 5, d42¢= d42 - 10 = 0, d25¢= d25 - 10 = 0, d57¢= d57 - 10 = 5.

ШАГ 3. Ат:= Ат + А(М3) = 40 + 10= 50.

ШАГ 4. Коррекция сети. Максимальный поток А(М3)вычитаем из дуг маршрута М13. Результат дан на рис.1.16 б.

ШАГ 5. В корректированной сети не осталось маршрутов из источникав сток. А:= Ат:=50, завершение работы алгоритма.Ответ: максимальный поток в сети на рис.1.15 равен 50.

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

Сетевое планирование

Любую задачу по проектированию либо построению достаточно сложного объекта (проект) можно разбить на ряд более мелких составляющих шагов. От правильного выбора последовательности выполнения данных шагов зависят сроки выполнения всего проекта.

Весь комплекс действий по выполнению проекта представляют в виде совокупности событий и работ. Событиями называют отдельные этапы проекта. Работами называют процесс их выполнения. Весь комплекс событий и работ, необходимых для выполнения проекта, может быть представлен в виде двухполюсной сети Г = ({vи , vз }, V, X), в которой:

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

б) все работы обозначены дугами, соединяющими между собой пары событий — вершин.

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

В качестве примера рассмотрим организацию некоторого производства. Проект требует выполнения следующих работ:

I) маркетинговые исследования, II) предпроектные исследования по оборудованию, III) организация сети сбыта, IV) проведение рекламной кампании, V) разработка технического задания на производственное оборудование, VI) разработка технической документации на производственные помещения и коммуникации, VII) закупка стандартного оборудования, VIII) проектирование и изготовление нестандартного оборудования, IX)строительство производственных помещений и монтаж коммуникаций, X) монтаж стандартного оборудования, XI) монтаж нестандартного оборудования, XII) пусконаладочные работы.

Данные работы обозначим в сетевом графике дугами с соответствующими номерами.

Событиями в данном проекте будут следующие:

1) начало работ (исходное событие), 2) завершение маркетинговых исследований, 3) завершение предпроектных исследований, 4) организация сети сбыта, 5) организация рекламной кампании, 6) подготовка технического задания на производственное оборудование, 7) завершение разработки технической документации на производственные помещения и коммуникации, 8) завершение закупки стандартного оборудования, 9) завершение проектирования и изготовления нестандартного оборудования, 10) завершение строительства производственных помещений и монтажа коммуникаций, 11) завершение установки оборудования и пуско-наладочных работ,

12) завершение проекта (завершающее событие).

Событиям сопоставляем вершины с соответствующими номерами. Сетевой график выполнения проекта дан на рис. 1.17:

Рис.1.17. Сетевой график выполнения проекта

 








Дата добавления: 2015-10-05; просмотров: 2442; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2022 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.007 сек.