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

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

I итерация. ШАГ 2. Выбор независимых маршрутов в сети и определение потоков в них. В качестве М₁возьмем маршрут(v_и=V₁, V₂, V₅, v_с=V₇), рассмотренный в примере 1. Для него А(М₁) = 10.

Также несложно выделить независимый от М₁ маршрут М₂= (v_и=V₁, V₃, V₆, v_с=V₇). Выполним для него расчет максимальной пропускной способности и скорректируем пропускную способность дуг: А(М₂)= min {d₁₃, d₃₆, d₆₇}= min {45, 40, 30}=30. d₁₃¢= d₁₃- 30 = 15, d₃₆¢= d₃₆- 30 = 10, d₆₇¢= d₆₇- 30 = 0.

ШАГ 3. Коррекция текущего значения максимального потока в сети. А_т:= А_т+ А(М₁)+ А(М₂) = 0 + 10+ 30 = 40.ШАГ 4. Коррекция сети. Найденные на ШАГе 2 максимальные потоки А(М₁), А(М₂) в маршрутах М₁, М₂вычитаем из пропускной способности их дуг. Дуги с нулевой остаточной пропускной способностью удаляем. Результат дан на рис.1.16 а.

а) б)Рис.1.16. Результат коррекции сети после итераций I и IIШАГ 5. Проверка завершения работы алгоритма. В корректированной сети (рис.1.16 а) существуют маршруты из источника v_и в сток v_с, например М₃= (v_и=V₁, V₄, V₂, V₅, v_с=V₇). Продолжение выполнения алгоритма.

II итерация. ШАГ 2. В качестве единственного независимого маршрута примем М₃= (v_и=V₁, V₄, V₂, V₅, v_с=V₇). Для него:

А(М₃)= min {d₁₄, d₄₂, d₂₅, d₅₇}= min {15, 10, 10, 15}=10.

d₁₄¢= d₁₄- 10 = 5, d₄₂¢= d₄₂- 10 = 0, d₂₅¢= d₂₅- 10 = 0, d₅₇¢= d₅₇- 10 = 5.

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

ШАГ 4. Коррекция сети. Максимальный поток А(М₃)вычитаем из дуг маршрута М₁₃. Результат дан на рис.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. Сетевой график выполнения проекта

<121314 15 16 17 18 >

Дата добавления: 2015-10-05; просмотров: 2843;