Алгоритм нахождения максимального потока. Метод нахождения максимального потока

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

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

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

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

Объем информации, энергии или вещества, передаваемый в сети от узла x i к узлу x j , называют потоком и обозначают j ij .

Наибольший поток, который может пропустить дуга (x i , x j), называют пропускной способностью дуги и обозначают с ij .

Очевидно, что 0£j ij £ с ij .

В вершине-истоке х 0 величина потока есть сумма потоков по всем дугам, исходящим из вершины х 0 , т.е. j=å i j 0i + .

В вершине-стоке х k величина потока есть сумма потоков по всем дугам, заходящим в вершину х k , т.е. j=å i j ik - .

Для любой промежуточной вершины х i сумма исходящих потоков равна сумме заходящих потоков, т.е. å j j ij + =å k j ik - .

На рис. 3.29 показана условная сеть, содержащая вершину-исток х 0 , вершину-сток х k и две промежуточные вершины х i и х j . На каждой дуге в круглых скобках приведены обозначения потока и пропускной способности соответствующей дуги. При этом поток, подводимый к сети равен j=(j 0i +j 0j), поток отводимый от сети равен j=(j ik +j jk), поток из вершины х i в вершину х j равен j ij . Для вершины х i имеем j 0i =(j ij +j ik), для вершину х j - j jk =(j 0j +j ij).



Если множество вершин графа разбить на два непересекающихся подмножества, одно из которых содержит вершину-исток, а другое - вершину-сток, то множество дуг, соединяющих эти два множества, формируют разрез А i , пропускная способность которого равна сумме пропускных способностей дуг. Таких разрезов может быть несколько.

В таблице приведены четыре разреза для сети на рис. 3.29

Разрез пропускная способность дуги Сij пропускная способность
С 0 i С 0 j С i j С i k С jk разреза С(A i)
А 1 С 0i + С 0j
А 2 С 0j +С ij +С ik
А 3 С ik +С jk
А 4 С 0i +С ij +С jk

Например, для разреза А 1 имеем Х’={x 0 } и X\Х’={х i , х j , х k }, для А 2 - Х’={х 0 , х i } и X\Х’={х j , х k }, для А 3 - Х’={х 0 , х i , x j } и X\Х’={х k }, для А 4 - Х’={х 0 , х j } и X\Х’={x i , х k }.

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

j max =min{С(A i)}

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

Для поиска распределения потока по дугам разработано несколько алгоритмов. Особое место среди них занимает алгоритм Форда-Фалкерсона, суть которого состоит в разметке вершин графа.

Метка вершины графа указывает на возможность изменения потока через данную вершину и указывает источник этого изменения. На рис. 3.30 дан фрагмент сети, объясняющий суть алгоритма.

Если по дуге (х s , х i) возможно увеличение потока (j si < c si), то вершину х i следует пометить +s , что указывает на источник увеличения потока.

Если по дуге (х i , х j) возможно увеличение потока j ij < c ij , то вершину х j пометить +i . Это означает, что приращение потока Dj si пойдет по направлению дуги (х i , х j) от вершины х s .

Если насыщена дуга (х s , х i), т.е. j si =c si , то метку +s нельзя ставить у вершины х i . Следовательно, если вершина x i не помечена, то у вершины x j нельзя ставить метку +i.

Если по дуге (х t , х j) возможно увеличение потока, т.е. j tj < c tj , то вершину х j следует пометить +t , что указывает на источник увеличения потока.

Если вершина х j не имеет пометки +i , то для увеличения потока в фрагменте сети, следует уменьшить поток в дуге (х i , х j) и направить его далее по другим дугам фрагмента на сток. Для указания этого у вершины x i ставят метку – j. Это означает что при общем приращении потока на участке (х i , х j) он должен быть уменьшен на величину Dj tj .

Если насыщена дуга (х t , х j), т.е. j tj =c tj , то метку +t нельзя ставить у вершины х j . Следовательно, если вершина x j не помечена, то у вершины x i нельзя ставить метку -j.

Если насыщены обе дуги (х s , х i) и (х t , х j), что означает невозможность приращения потока Dj si и Dj tj , то нельзя ставить метки у вершин x i и x j и продолжения разметки следующих вершин сети до вершины-стока.

Так достигают максимального значения потока от вершин-истоков х s и х t по дугам к вершинам - стокам х i и х j .

Алгоритм Форда-Фалкерсона:

шаг 1 : присвоить всем вершинам графа индексы 0,1,2,...k; где 0-индекс вершины-истока графа, k -индекс вершины-стока графа;

шаг 2 : присвоить начальной вершине метку “0”;

шаг 3 : все непомеченные вершины х i , в которые идут ненасыщенные дуги из помеченной вершины х s , пометить индексом “+s”, что свидетельствует о возможности увеличения потока из вершины х s по дуге (х s , х i);

шаг 4 : все непомеченные вершины х i , из которых идут дуги (насыщенные или ненасыщенные) в помеченную вершину х j , пометить индексом “-j”, что свидетельствует о возможности уменьшения потока в вершину х j по дуге (х i , х j);

шаг 5 : если в результате этих операций окажется помеченной вершина-сток x k , то между начальной и конечной вершинами сети найдется маршрут, все вершины которого различны и с точностью до знака помечены индексами предыдущих вершин, формирующих переход, по которому можно увеличить поток, и перейти к шагу 6, иначе конец.

шаг 6 : увеличить поток в маршруте, сформированном на шаге 5, на единицу и перейти к шагу 3.

Признаком окончания работы алгоритма является невозможность пометки вершины-стока.

Пример : На рис. 3.31 дан граф. Найти величину максимального потока и его распределение в сети.

На каждой дуге (х i , х j) указаны величина потока и пропускная способность - (j ij , c ij).

Все расчеты сведены в две таблицы таблица а)

х i шаг итерации
х 0
х 1 +0 +0 +0 +0, -3 -3 - -
х 2 +0;+3 +0;+3 +0 +0 +0 +0 -
х 3 +0;+1 +0;+1 +0;+1 +0 +0 - -
х k +1;+2;+3 +1;+2 +1;+2 +1;+2 +1,+2 +2 -

таблица b)

(х i , х j) С ij шаг итерации
(х 0 , х 1)
(х 0 , х 2)
(х 0 , х 3)
(х 1 , х 3)
(х 1 , х k)
(х 2 , х k)
(х 3 , х 2)
(х 3 , х k)

В таблице а) на каждом шаге итерации для каждой вершины графа указаны возможные метки, а в таблице b) даны приращения потока по дугам (х i , х j). Полужирным шрифтом выделены насыщенные дуги графа

В результате выполнения первого шага итерации возможны переходы: n 0k ={(х k , х 1 , х 0); (х k , х 2 , х 0); (х k , х 2 , х 3 , х 0); (х k , х 2 , х 3 , х 1 , х 0);

(х k , х 3 , х 0); (х k , х 3 , х 1 , х 0)}. Пусть выбран n 0k =(х k , х 3 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((х 0 , х 3), (х 3 , х k)).

На втором шаге возможны те же переходы. Пусть выбран переход n 0k =(х k , х 3 , х 0). Приращение потока на Dj=1 проходит по маршруту m={(х 0 , х 3), (х 3 , х k)}. При этом дуга (х 3 , х k) оказывается насыщенной, т. е. j 3k =c 3k =2.

На третьем шага возможны переходы: n 0k ={(х k , х 1 , х 0); (х k , х 2 , х 0); (х k , х 2 , х 3 , х 0); (х k , х 2 , х 3 , х 1 , х 0)}. Пусть выбран n 0k =(х k , х 2 , х 3 , х 1 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 1), (x 1 , x 3), (x 3 , x 2), (x 2 , x k)). При этом оказывается насыщенной дуга (х 3 , х 2), т. е. j 32 =c 32 =1.

На четвертом шаге возможны переходы: n 0k ={(х k , х 1 , х 0); (х k , х 2 , х 0)}. Пусть выбран n ok =(х k , х 1 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 1), (x 1 , x k)),. При этом оказывается насыщенной дуга (х 0 , х 1), т. е. j 01 =c 01 =2.

На пятом шаге возможны переходы: n 0k ={(х k , х 1 , -x 3 , х 0); (х k , х 2 , х 0)}. Пусть выбран n ok =(х k , х 1 , -x 3 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 3), (x 3 , x 1), (x 1 , x k))),. При этом оказывается насыщенной дуга (х 0 , х 3), т. е. j 03 =c 03 =3.

На шестом шаге возможен только один переход n 0k =(х k , х 2 , х 0), так как дуги (x 0 , x 1) и (x 0 , x 3) насыщены. Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 2), (x 2 , x k)),. При этом оказывается насыщенной дуга (х 0 , х 2), т. е. j 02 =c 02 =1.

На седьмом шаге невозможны ни один переход от x o к x k , так как дуги (x 0 , x 1), (x 0 , x 3) и (х 0 , х 2) насыщены и невозможно поставить метки у вершин x 1 , x 2 , и x 3 .

Гамильтоновы циклы

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

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

A B C D
A ∞
B ∞
C ∞
D ∞

Просуммируем все вычтенные элементы и получим нижнюю границу цикла в= 2+2+3+2+1=10

1.2. Проведём оценку всех нулевых элементов матрицы.

Оценку нулей удобно представлять в таблице.

A B C D
A
B
C
D

θ=max γ=γ А C =2

1.3. Множество путей разобьём на два подмножества:QAC – пути, содержащие дугу (AC) и QAC – пути, не содержащие дугу (АC). Для второго подмножества нижней границей будет: в / =в+ θ =10+2=12.

Чтобы вычислить границу для первого подмножества, перейдём к матрице на порядок ниже, вычеркнув A-строку и C-столбец. В новой матрице для исключения обратного пути (CA) в соответствующую клетку поставим знак ∞.

Вычислим границу полученной матрицы 2+0=2

и добавим её к нижней границе цикла. Эта сумма в // =10+2=12 и будет границей для первого подмножества.

1.4. Сравним границы всех висячих вершин и выберем вершину с наименьшей границей. Если этих вершин две, выбираем любую из них. Это вершина QAC , нижняя граница которой =12.



Выберем максимальную из оценок θ=max γ=γ BD =3

в / =12+3=15.

1.6. Все последующие пункты выполняем аналогично предыдущим.

Выберем максимальную из оценок θ=max γ=γ С B = ∞

в / =в+ θ=∞

A
D

Все строки и столбцы этой матрицы содержат нули. Следовательно, граница остается равной 12.

ЗАДАЧА. Найти величину максимального потока на транспортной сети.

ПОСТАНОВКА ЗАДАЧИ.

Рассмотрим транспортную задачу на сети (I,D,G ) с заданными пропускными способностями дуг c(i,j).

Выделим две фиксированные вершины: s - источник и t – сток. Потоком на сети s→t назовем числовую функцию f , определенную на множестве дуг и удовлетворяющую следующим линейным уравнениям и неравенствам:

0≤ f(i,j) ≤c(i,j) для любых (i,j)

Требуется максимизировать переменную x

Разрезом L в сети, отделяющим вершины s t называется множество дуг

Любой путь s→t содержит по крайней мере одну дугу разреза.

КРИТЕРИЙ ОПТИМАЛЬНОСТИ: на реальной сети величина произвольного потока не превосходит пропускной способности разреза, а величина максимального потока равна минимальной пропускной способности разреза.

ПРИМЕР 3.12.

М 9 К

М 8 К

ПРИМЕР 3.13.

М 2 К

РЕШЕНИЕ:

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

Найдем и вычислим значение пропускных способностей всех разрезов. (К,В) – (Т,В) разрез с минимальной пропускной способностью =6. Следовательно, максимальный поток =6.

Сеть, имеющую несколько источников и стоков можно свести к сети с одним источником и стоком.

ПРИМЕР. Пусть имеется несколько источников S и стоков T (транспортная задача). Расширим сеть, добавив два узла s* , t* и все дуги (s*, S) , (T,t*). Доопределим функцию пропускной способности, положив

МЕТОД РАССТАНОВКИ ПОМЕТОК.

1. Начальный поток f(i,j) = 0.
Припишем вершинам данной сети пометки, которые будут иметь вид (i+, ε) или
(i - , ε). Источник пометим (-, ∞), т.е. ε(s)= ∞.

2. Для любой помеченной вершины i выберем все непомеченные вершины j для которых f(i,j) и припишем им пометки (i+, ε(j)), где ε(j)=min[ε(i), f(i,j)]. Тем вершинам, которые останутся непомеченными, но для которых f(i,j)>0, приписываем пометку (i-, ε(j)).

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

3. Пусть сток имеет пометку (j+, ε(t)) , тогда f(j,t) заменяем на f(j,t)+ε(t) . Если же сток имеет пометку (j-, ε(t)) , то f(j,t) заменяем на f(j,t)-ε(t) . Переходим к вершине j . Если j имеет пометку (i+, ε(j)) , то заменяем f(i,j) на f(i,j)+ε(t) , а если ­(i-, ε(j)) , f(j,i) заменяем на f(j,i)-ε(t) . Переходим к вершине i . Эту операцию повторяем до тех пор, пока не достигнем источника s . Изменение потока прекращается, стираются все пометки и переходим к п.2

ПРИМЕР 3.14.

М 4 К

1 шаг А → (-, ∞) М → (А+,8) Р → (А+,3) К → (Р+,3) Т → (Р+,3) В → (Т+,3) f(Т,В)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(А,М)=0 f(М,Р)=0 f(М,К)=0 f(М,Т)=0 f(К,Т)=0 f(К,В)=0
2 шаг А → (-, ∞) М → (А+,8) Р → (М+,1) К → (М+,4) Т → (М+,2) f(К,В)=3 f(М,К)=3 f(А,М)=3 f(Т,В)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(М,Т)=0 f(М,Р)=0 f(К,Т)=0
3 шаг А → (-, ∞) М → (А+,5) Р → (М+,1) К → (М+,1) Т → (М+,2) В → (Т+,2) f(Т,В)=5 f(М,Т)=2 f(А,М)=5 f(К,В)=3 f(М,К)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(М,Р)=0 f(К,Т)=0
4 шаг А → (-, ∞) М → (А+,3) Р → (М+,1) К → (М+,1) Т → (Р+,1) В → (Т+,1) f(А,М)=6 f(Т,В)=6 f(Р,Т)=4 f(М,Р)=1 f(М,Т)=2 f(К,В)=3 f(М,К)=3 f(А,Р)=3 f(Р,К)=0 f(К,Т)=0
5 шаг А → (-, ∞) М → (А+,2) Р → (М-,1) К → (М+,1) Т → (К+,1) В → (Т+,1) f(А,М)=7 f(М,К)=4 f(К,Т)=1 f(Т,В)=7 f(Р,Т)=4 f(М,Р)=1 f(М,Т)=2 f(К,В)=3 f(А,Р)=3 f(Р,К)=0
6 шаг А → (-, ∞) М → (А+,1) Поток оптимален f=10 Минимальный разрез:М →Т-М →Р-М →К

ЗАДАЧА. Найти наибольший поток на сети

АЛГОРИТМ

Обозначим вершину s= х 0 . Все остальные – х i .

1 этап.

1. Выбираем любой путь, все дуги которого не насыщены.

2. Увеличиваем величину потока по этому пути на единицу до тех пор, пока в нем не будет насыщенной дуги.

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

2 этап.

2. Если х i уже помеченная вершина, то помечаем (+i) все непомеченные вершины, в которые идут не насыщенные дуги из х i , и индексом (–i) все непомеченные вершины, из которых идут дуги с ненулевым потоком в х i .

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

4. Когда вершину t невозможно пометить процесс прекращается и полученный поток является наибольшим потоком сети.

ПРИМЕЧАНИЕ. Перейти к 2 этапу можно, не завершая первого этапа (см. пример 3.16).

ПРИМЕР 3.15.

9

РЕШЕНИЕ:

На заданной транспортной сети найден полный поток. Насыщенные дуги выделены

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

ПРИМЕР 3.16.

8 2 1

На заданной транспортной сети найден неполный поток

Пометим сеть и увеличим в ней поток согласно алгоритму. Получим

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

Раздел IV. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

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

Лучше много раз решить одну простую задачу, чем один раз сложную.

ЗАДАЧА 1. О наивыгоднейшем пути между двумя пунктами.

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

ПРИМЕР 4.1. Найти минимальный путь от А до В.


Последний шаг – достижение т.В. Перед последним шагом мы могли находиться в точках, откуда за один шаг можно достичь т.В. Таких точки две (система могла находиться в одном из двух состояний). Для каждой из них существует единственный вариант достижения т.В: для одной – двигаться на восток; для другой – на север. Запишем затраты 4 и 3 в каждом случае.

4

Теперь оптимизируем предпоследний шаг. После предыдущего шага мы могли оказаться в одной из трех точек: С 1 , С 2 , С 3 .

Для т. С 1 существует единственное управление (пометим его стрелкой) – двигаться на восток, при этом затраты составят 2(на данном шаге)+4(на следующем шаге)=6. Аналогично для т. С 3 затраты составят 2+3=5. Для т.С 2 существует два управления: идти на восток или на север. В первом случае затраты составят 3+3=6, а во втором случае – 1+4=5. Значит условное оптимальное управление – идти на север. Пометим его стрелкой и занесем соответствующие затраты.
2 4

ЗАДАЧА 2. О загрузке машины (о рюкзаке).

Имеется N предметов. Известны вес a i и ценность φ i каждого предмета. Требуется заполнить рюкзак, способный вместить вес ≤ R , таким набором предметов, который обладал бы наибольшей ценностью.

Процесс загрузки рюкзака можно разбить на N шагов. На каждом шаге мы решаем вопрос: брать данный предмет или не брать? На каждом шаге имеется всего 2 управления: управление =1, если мы берем данный предмет; и 0 – если не берем.

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

АЛГОРИТМ.

1. Начнем с последнего шага. Сделаем различные предположения о свободном пространстве в рюкзаке: S=0,1,…R. Положим последний предмет в рюкзак, если в нем сводного пространства достаточно.

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

3. На первом шаге рассмотрим только единственно возможное состояние S=R.

4. Найдем решение, «пятясь назад», т.е. взяв оптимальное управление на первом шаге, изменим состояние системы на втором шаге: S=R–x 1 a 1 и выберем оптимальное управление х 2 для этого состояния. И т.д.

ПРИМЕР 4.2.

Исходные данные

П1 П2 П3 П4
вес a i
стоимостьj i

Основная таблица

S i=4 i=3 i=2 i=1
x 4 W 4 x 3 W 3 x 2 W 2 x 1 W 1

Вспомогательная таблица.

состояния x а S-а j i (x) W i+1 (S-а ) j i (x)+ W i+1 (S-а )
i=3 S=5
S=6
S=7
S=8
S=9
S=10
i=2 S=5
S=6
S=7
S=8
S=9
S=10
i=1 S=10

Ответ: x 4 =0; x 3 =1; x 2 =0; x 1 =1; W=15

ЗАДАЧА 3. О распределении ресурсов.

Имеется N предприятий П 1 , П 2 ,… П N , каждое из которого дает доход φ k (x), если ему выделен ресурс в количестве x. Требуется имеющийся в количестве А ресурс распределить между объектами так, чтобы суммарный доход был максимальным.

Пусть x k – количество ресурса, выделенное k-ому предприятию. Тогда рассматриваемая задача сводится к обычной задаче нелинейного программирования.

Сформулируем задачу, как задачу динамического программирования.

За первый шаг примем вложение средств в предприятие П 1 , за второй – в П 2 и т.д. Управляемая система в данном случае – средства, которые распределяются. Состояние системы перед каждым шагом характеризуется одним параметром – наличным запасом еще не вложенных средств. В этой задаче шаговыми управлениями являются средства, выделяемые предприятиям. Требуется найти оптимальное управление (х 1 , х 2 ,…х N), при котором суммарный доход максимален:

 1,1 0,5
S=3 0,1 0,5 1,1 1,5
S=4 0,1 0,5 2,1 1,5
S=5 0,1 0,5 2,5 3,1 2,5 2,5
i=1 S=5 0,5 1,5 3,1 1,1 3,1 3,5 2,1 2,6

Ответ: x 1 =1; x 3 =0; x 3 =4; W=3,5

ОБОБЩЕННЫЙ АЛГОРИТМ

1. Описать систему. Т.е выяснить, какими параметрами характеризуется состояние управляемой системы перед каждым шагом. Важно уметь правильно и “скромно” поставить задачу, не переобременяя ее лишними подробностями, упрощая сколько возможно описание управляемой системы.

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

3. Выяснить набор шаговых управлений x i для каждого шага и налагаемые на них ограничения.

4. Определить, какой выигрыш приносит на i-шаге управление x i , если перед этим система была в состоянии S, т.е. записать функции выигрыша:

w i =f i (S, x i)

5. Определить, как изменяется состояние системы под влиянием управления x i на I-м шаге, т.е. записать функции изменения состояния.

S / =φ i (S, x i)

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

W i (S)= max{f i (S,x i)+W i+1 (φ i (S, x i))}

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

W m (S)= max{f m (S, x m)}

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

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

ПРИНЦИП ОПТИМАЛЬНОСТИ. Каково бы ни было состояние системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

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

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

Раздел V. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ

Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда-Фалкерсона, и построить разрез сети S.
Исходные данные:
Дана сеть S(X,U)
- исток сети; - сток сети, где ∈X; ∈X.
Значения пропускных способностей дуг заданы по направлению ориентации дуг: от индекса i к индексу j.

r = 39; r = 44; r = 33; r = 53; r = 10;
r = 18; r = 95; r = 16; r = 23; r = 61;
r = 81; r = 71; r = 25; r = 15; r = 20

1. Зададим на сети нулевой поток (на всех дугах величина потока равна 0). Нулевой поток - это начальный допустимый поток на сети. Значение потока на каждой дуге будем указывать за скобками пропускной способности дуги.). Значение потока, равное «0», не указываем.
2. Выбираем на сети (произвольно) путь, ведущий из вершины x0 в вершину x7:
X0-X1-X4-X6-X7
3. Находим и увеличиваем поток на эту величину. Ребро Х1-Х4 помечаем как рассмотренное.


4. Выбираем еще один путь, например: Х0-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х0-Х2 помечаем как рассмотренное.


5. Выбираем еще один путь, например: Х0-Х3-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х3-Х2 помечаем как рассмотренное.


6. Более путей от Х0 до Х7 нет, суммируем увеличения потока: 25+10+20=55.
Вывод: максимальный поток равен 55.

2) Построить разрез сети S.
Процедура «пометок вершин».
Начальное состояние: все вершины не имеют пометок.
Вершине Х0 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются пометки (красные круги)


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

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

Рассмотрим ребро (i, j) с (начальной) пропускной способностью. В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Запись - остаточная пропускная способность. Сеть в которой все ребра имеют остаточную пропускную способность, назовем остаточной.

Для произвольного узла j, получающего поток из узла i, определим метку, где - величина потока, протекающего от j узла к узлу i. Чтобы найти максимальный поток, выполняем следующие действия.

Для всех ребер положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем =. Назначим и пометим узел 1 меткой. Полагаем i=1.

Множество узлов j, в которые можно перейти из узла I по ребру с положительной остаточной пропускной способностью >0 для всех j. Если, выполняем 3 этап, в противном случае переходим к 4.

В находим узел k, такой, что. Положим и пометим узел k меткой. Если k=n, сквозной путь найден, и переходим к 5 этапу, в противном случае полагаем i=k и возвращаемся к 2 этапу.

Откат назад. Если i=1, сквозной путь не возможен, и переходим к 6. Если, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем его из множества узлов, смежных с узлом r. Полагаем i=r и возвращаемся ко 2 этапу.

Определение остаточной сети. Обозначим через множество узлов, через которые проходит p_й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n).тогда максимальный поток, проходящий по этому пути

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

Т.о. для ребра (i, j), входящего в сквозной путь, текущие остаточные пропускные способности изменяются:

1) , если поток идет от узла i к j,

2) , если поток идет от узла j к i.

а) при m найденных сквозных путях максимальный поток выражается

б) Имея значения начальных и конечных пропускных способностей ребра (i, j), можно вычислить оптимальный поток через это ребро следующим образом. Положим. Если >0, поток, проходящий через ребро (i, j) равен. Если >0, тогда поток равен. (случай, когда одновременно >0 и >0, невозможен).

Пример 1. Найти максимальный поток в сети рис. 1

Итерация 1. =

3) k=3, так как. Назначаем и помечаем узел 3 меткой. i=3 и возвращаемся к 2)

5) k=5 и. Помечаем узел 5 меткой. Получаем сквозной путь.

6) сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: . и. Вычисляем остаточные пропускные способности вдоль пути:

Итерация 2.

1) и помечаем узел 1 меткой. i=1

2») (, поэтому узел 5 не включается в

3») k=4, и помечаем узел 4 меткой. i=4 и возвращаемся к 2)

2""") (так как узлы 1 и 3 помечены, они не включаются в)

3""") k=5 и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)

Итерация 3.

1) и помечаем узел 1 меткой. i=1

3) k=2, и помечаем узел 2 меткой. i=2 и возвращаемся к 2)

3") k=3 и. Помечаем узел 3 меткой. i=3 и возвращаемся к 2)

2») (так как) переходим к 4)

4) метка узла 3 показывает номер предшествующего узла. На этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем. и возвращаемся к 2)

2""") (так как узел 3 удален из возможного сквозного пути)

3""") и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)

5) и. Вычисляем остаточные пропускные способности вдоль пути:

Итерация 4. на этой итерации получен путь с

Итерация 5. на этой итерации получен путь с

Итерация 6. новые сквозные пути невозможны, поскольку все ребра, исходящие из узла 1, имеют нулевые остаточные пропускные способности. Переходим к 6) для определения решения

6) максимальный объем потока в сети равен единиц.

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

Результаты вычислений: табл. 1

Величина потока

направление

(20,0) - (0,20)=(20, - 20)

(30,0) - (0,30)=(30, - 30)

(10,0) - (0,10)=(10, - 10)

(40,0) - (40,0)=(0,0)

(30,0) - (10,20)=(20, - 20)

(10,5) - (0,15)=(10, - 10)

(20,0) - (0,20)=(20, - 20)

(20,0) - (0,20)=(20, - 20)

Графическое последовательное выполнение алгоритма нахождения максимального потока (пример 1)







д) е) Сквозных путей нет


Рис.

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 2, можно также задать таблицей (табл. 2).

Табл.2. Исходные данные к задаче о максимальном потоке

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3. Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4. Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы. Решение можно представить в виде таблицы (табл. 3)

Табл.3. Решение задачи о максимальном потоке

Пункт отправления

Пункт назначения

План перевозок

Пропускная способность

Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х KM - объем перевозок из пункта К в пункт М. Согласно рис. 2 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х KM, а именно, Х 01, Х 02, Х 03, Х 12, Х 13, Х 14, Х 23, Х 24, Х 34. Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

Х 01 + Х 02 + Х 03 = F (0)

Х 01 + Х 12 + Х 13 + Х 14 = 0 (1)

Х 02 - Х 12 + Х 23 + Х 24 = 0 (2)

Х 03 - Х 13 - Х 23 + Х 34 = 0 (3)

Х 14 - Х 24 - Х 34 = - F (4)

Х КМ? 0, К, М = 0, 1, 2, 3, 4

Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не «рождаются» в ней. Условие (4) - это условие «выхода» грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом («вход» равен «выходу»). Следующие девять неравенств задают ограничения на пропускную способность отдельных «веток» транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).

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

Математик Джордж Бернард Данциг, с 1941 года
работая в отделе статистического управления Военновоздушных сил США в Вашингтоне, впервые решил
задачу о максимальном потоке в ходе подготовки
воздушного моста во время блокады Западного Берлина.
В 1951 году Джордж Данциг впервые сформулировал
задачу в общем виде. В 1955 году, Лестер Форд и
Делберт Фалкерсон впервые построили алгоритм,
специально предназначенный для решения этой задачи.
Их алгоритм получил название алгоритм ФордаФалкерсона.
В 2010 году исследователи Джонатан Кёлнер и
Александер Мондры из МТИ вместе со своими
коллегами Дэниелем Спилманом из Йельского
университета и Шень-Хуа Тенем из ЮжноКалифорнийского университета продемонстрировали
очередное улучшение алгоритма.

Дан ориентированный граф
(транспортная сеть) G=(V, E), вершина
графа s (источник) и вершина t (сток).
Каждой дуге (i, j) приписана некоторая
пропускная способность с(i,j) 0 (без
потери общности считаем её
целочисленной величиной),
определяющая максимальное значение
потока, который может протекать по
данной дуге.

Потоком
в
сети
называют
целочисленную функцию f(i, j), заданную
на множестве дуг E и обладающей
следующими свойствами:
1. Ограничение потока пропускной
способностью
Для любой дуги (i, j) E выполняется
неравенство f(i, j) c(i, j).

2. Сохранение потока
Для любой вершины q V,
выполняется равенство
q s
и
q t
f (i, q) f (q, j)
i V
(i , q) E
j V
(q , j) E
Т. е. сумма потока, заходящего в q, равна
сумме потока, выходящего из q (поток без
потерь и накоплений)

Требуется определить значение
максимального потока, который
можно пропустить от источника s к
стоку t, и его распределение по дугам.

Пример
У компании Lycky Puck в Ванкувере есть фабрика
(источник s), производящая хоккейные шайбы, а в
Виннипеге – склад (сток t), где эти шайбы хранятся.
Компания арендует места на грузовиках других фирм
для доставки шайб с фабрики на склад. Поскольку
грузовики ездят по определенным маршрутам (ребрам)
между городами (вершинами) и имеют ограниченную
грузоподъемность, компания Lycky Puck может
перевозить не более c(u,v) ящиков в день между каждой
парой городов u и v. Компания Lycky Puck не может
повлиять на маршруты и пропускную способность. Ее
задача – определить, какое наибольшее количество
ящиков в день можно отгружать, и затем производить
именно такое количество, поскольку не имеет смысла
производить шайб больше, чем можно отправить на
склад.

Методы решения задачи
Линейное программирование
Представить задачу о максимальном потоке как задачу
линейного программирования. Переменными являются
потоки по рёбрам, а ограничениями - сохранение потока
и ограничение пропускной способности.
Алгоритм Форда-Фалкерсона
Найти любой увеличивающий путь. Увеличить поток по
всем его рёбрам на минимальную из их остаточных
пропускных способностей. Повторять, пока
увеличивающий путь есть. Алгоритм работает только
для целых пропускных способностей.

10.

Пример 1
Дадим формулировку задачи о максимальном
потоке в терминах линейного программирования.
Пусть ХKM - объем перевозок из пункта К в пункт М.
К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны
лишь в пункт с большим номером. Значит, всего
имеется 9 переменных ХKM, а именно, Х01 , Х02 , Х03 , Х12
, Х13 , Х14 , Х23 , Х24 , Х34 .
s=0
t=4

11.

Задача линейного программирования,
нацеленная на максимизацию потока, имеет вид:
F → max ,
Х01 +Х02 +Х03 =F
-Х01 +Х12 +Х13 +Х14 = 0
-Х02 -Х12 +Х23 +Х24 = 0
-Х03 -Х13 -Х23 +Х34 = 0
-Х14 -Х24 -Х34 = - F
Х01 ≤ 2
Х02 ≤ 3
Х03 ≤ 1
Х12 ≤ 4
Х13 ≤ 1
Х14 ≤ 3
Х23 ≤ 1
Х24 ≤ 2
Х34 ≤ 2
ХКМ ≥ 0 , К, М = 0, 1, 2, 3, 4
F≥0.

12.

Разрезом
называют множество дуг,
удаление которых из сети приводит к
«разрыву» всех путей, ведущих из s в t.
Пропускная способность разреза – это
суммарная пропускная способность дуг, его
составляющих.
!!! Найти разрезы в примере 1

13.

Теорема Л. Форда и Д. Фалкерсона:
Величина каждого потока из s в t не
превосходит
пропускной
способности
минимального разреза, разделяющего s и t,
причем поток, достигающий этого значения,
существует.
(Величина
максимального
потока
в
транспортной
сети
равна
величине
минимального разреза в ней)
!!! Найти минимальный разрез в примере 1

14.

С алгоритмической точки зрения эта
теорема малопродуктивна.
Генерация всех подмножеств дуг и
проверка,
является
ли
очередное
подмножество разрезом – «лобовое решение»,
приводит к высокой сложности алгоритма.
Кроме того, данный факт не помогает
найти способ распределения максимального
потока по дугам.

15.

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

16.

Алгоритм Форда-Фалкерсона
Что представляет из себя метка
вершины?
первая цифра в метке – это номер
вершины, из которой идет поток в
данную вершину;
вторая цифра в метке – численное
значение потока, который можно
передать в данную вершину.

17.

Алгоритм Форда-Фалкерсона
На каждом шаге алгоритма вершины сети
могут находиться в одном из трех состояний:
вершина не имеет метки;
вершине присвоена метка, и она не
просмотрена, т. е. не все смежные с ней
вершины обработаны;
вершине присвоена метка, и она
просмотрена.

18.

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

19.

Алгоритм Форда-Фалкерсона
Дуга e=(u, v) сети является допустимой
дугой из u в v относительно потока f, если
e=(u, v) и f(e) прямые);
e=(v, u) и f(e)>0 (дуги второго типа,
обратные).
Второе условие говорит о том, что
допустимыми являются и дуги, входящие в
вершину u, по которым «уже пропущен
ненулевой поток».