- •Киевский университет имени Тараса Шевченко
- •Общие рекомендации к использованию программного обеспечения
- •Элементарные преобразования матриц. Метод гаусса
- •Задача линейного программирования. Симплекс-метод Постановка задачи линейного программирования в стандартной форме (сзлп).
- •Задача линейного программирования. Модифицирован симплекс-метод.
- •Задача линейного программирования. Двойственный симплекс-метод
- •Транспортная задача. Метод потенциалов
- •Транспортная задача с ограниченными пропускными
- •Способностями. Метод потенциалов
- •Постановка транспортной задачи с ограниченными
- •Пропускными способностями (тзо).
- •Задача о кратчайшем пути на сети. Метод минти
- •Задача о максимальном потоке на сети. Метод форда-фалкерсона
- •Задача целочисленного линейного программирования. Метод гомори-1
- •Задача частично целочисленного линейного программирования. Метод гомори-2 Постановка частично целочисленной задачи линейного программирования (чцзлп).
- •Задача целочисленного линейного програмування. Метод гомори-3
- •Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
- •Задача целочисленного линейного программирования. Метод ветвей и границ.
- •Лабораторная работа 14. Задача о назначении. Венгерский метод
- •Лабораторная работа 15. Задача о назначении. Метод мака Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
- •6. Если каждый столбец матрицы расходов имеет элемент с отметкой *, тогда задача об оптимальных назначениях решена. Иначе переходим к следующему пункту.
- •Матричные игры. Связь с задачей линейного программирования. Метод брауна-робiнсон
- •Лабораторная работа 17. Методы одномерной оптимiзации
- •Лабораторная работа 18. Задача выпуклого квадратичного программирования. Квадратичный симплекс-метод
- •Задача безусловной оптимизации. Метод самого быстрого спуску
- •Лiтература
Задача о максимальном потоке на сети. Метод форда-фалкерсона
Постановка задачи о максимальном потоке на сети.
На сети, что задается графом (I,U), где I — множество вершин, U — множество дуг, с определенной на ней функцией пропускных способностей rij ((і,j) — дуга с U), зафиксированные две вершины — i1 и in. Вершина i1 (источник) имеет интенсивность d, вершина in (стек) — интенсивность –d, все другие вершины нейтральные. Нужно найти максимальную интенсивность источника d, при которой сеть допускает поток. Поток, что отвечает такому максимальному значению интенсивности d*, называется максимальным потоком, а именно значение d* — величиной этого потока.
Алгоритм Форда-Фалкерсона применяется для построения максимального потока на сети из заданной начальной вершины-источникав заданную конечную вершину-сток.
Будем считать, что вершиной-источником является 1-я вершина, вершиной-стоком — вершина с номером n.
Входные данные.
Для работы алгоритма необходимо задать следующую информацию:
1. Число вершин сети.
2. Матрицу смежности С, элементы которой сіjопределяются соотношениями:
сij=1, если существует дуга (і,j);
сij=0, если дуга (і,j) отсутствует.
3. Величины rijпропускных способностей дуг (і,j).
4. Начальный поток на сети, то есть величины xij, которые удовлетворяют условия:
a) 0xijrij;
b) Для произвольной вершины (кроме первой и последней) поток, что входит в вершину, равняется потоку, что выходит из нее.
Изложение алгоритма Форда-Фалкерсона.
Алгоритм состоит из последовательных итераций, которые проводятся до тех пор, пока не будет выполняться признак оптимума.
В каждой итерации можно выделить два этапа.
Этап 1 (этап выставления отметок).
1. В каждый момент времени каждая вершина может находиться в одном из трех положений:
а) не обозначенная;
б) обозначенная, но не рассмотрена;
в) обозначена и рассмотрена.
Общий вид отметки j-ївершины: [i+j], или [и–,j], где и — номер некоторой обозначенной вершины, при просмотре которой была обозначена вершина j. Вершина 1 всегда обозначена и имеет отметку [1+1], где 1 равное + (бесконечности).
2. Просмотр произвольной обозначенной вершины j заключается в следующем:
a) произвольная необозначенная вершина k, для которой существует дуга (j,k) и имеет место неравенство xjk<rjk, получает отметку вида [j+k], где
k=min {j, rjk – xjk};
б) произвольная необозначенная вершина k, для которой существует дуга (k,j) и имеет место условие xkj>0, получает отметку вида [j–,k], где
k=min {j, xkj}.
3. Процесс выставления отметок заканчивается в одном из двух случаев:
а) вершина с номером n обозначена;
б) условие а) не выполняется, но ни одну вершину больше пометить нельзя.
В первом случае переходим к этапу изменения потока на сети. Во втором — до определения минимального разреза сети и максимального потока.
Этап 2 (этап изменения потока).
Поток в сети изменяется на величину n согласно правила.
Если вершина n имеет отметку [k+n], где k — номер некоторой вершины, то xkn=xkn+n. Если отметка имеет вид [k–,n], то xnk=xnk–n. Переходим к вершине с номером k. Если отметка вершины k имеет вид [j+k], то xjk=xjk+n; если она равняется [j–,k], то xkj=xkj–n. Подобные действия продолжаем до тех пор, пока не будет достигнута начальная вершина. В этом случае все старые отметки вытираем и возвращаемся к первому этапу.
В результате работы согласно алгоритма определяются минимальный разрез сети и, как следствие, максимальный поток.
Минимальный разрез определяется совокупностью дуг, которые выходят из множества обозначенных вершин и заходят в множество необозначенных.
Величина максимального потока ровная суммарной пропускной способности минимального разреза.
Программное обеспечение.
Обучающий модуль, с помощью которого задача о максимальном потоке на сети Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО.
Задание.
Решить методом Форда-Фалкерсона задачи о максимальном потоке на сети, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи, в каждой из которых сеть задается матрицами смежности C и пропускных способностей R. Во всех задачах источником считается вершина 1, а стоком — вершина 6.
1) |
|
0 |
1 |
1 |
0 |
0 |
0 |
|
|
0 |
10 |
18 |
0 |
0 |
0 |
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
0 |
0 |
14 |
1 |
|
|
C = |
0 |
1 |
0 |
1 |
0 |
0 |
, |
R = |
0 |
10 |
0 |
17 |
0 |
0 |
; |
|
|
0 |
1 |
0 |
0 |
1 |
1 |
|
|
0 |
9 |
0 |
0 |
22 |
12 |
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
0 |
0 |
18 |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
2) |
|
0 |
1 |
1 |
0 |
0 |
0 |
|
|
0 |
11 |
33 |
0 |
0 |
0 |
|
|
|
0 |
0 |
0 |
1 |
1 |
0 |
|
|
0 |
0 |
0 |
14 |
4 |
0 |
|
|
C = |
0 |
1 |
0 |
1 |
1 |
0 |
, |
R = |
0 |
5 |
0 |
15 |
23 |
0 |
; |
|
|
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
0 |
0 |
23 |
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
|
|
0 |
0 |
0 |
11 |
0 |
22 |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
3) |
|
0 |
1 |
1 |
1 |
0 |
0 |
|
|
0 |
20 |
21 |
22 |
0 |
0 |
|
|
|
0 |
0 |
1 |
1 |
1 |
0 |
|
|
0 |
0 |
5 |
13 |
14 |
0 |
|
|
C = |
0 |
0 |
0 |
0 |
1 |
1 |
, |
R = |
0 |
0 |
0 |
0 |
12 |
28 |
; |
|
|
0 |
0 |
1 |
0 |
1 |
1 |
|
|
0 |
0 |
12 |
0 |
11 |
10 |
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
0 |
0 |
17 |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
4) |
|
0 |
1 |
1 |
1 |
0 |
0 |
|
|
0 |
5 |
19 |
27 |
0 |
0 |
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
0 |
0 |
17 |
15 |
|
|
C = |
0 |
1 |
0 |
0 |
1 |
1 |
, |
R = |
0 |
23 |
0 |
0 |
7 |
8 |
; |
|
|
0 |
1 |
1 |
0 |
1 |
0 |
|
|
0 |
5 |
12 |
0 |
11 |
0 |
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
0 |
0 |
28 |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
5) |
|
0 |
1 |
1 |
1 |
1 |
0 |
|
|
0 |
24 |
33 |
6 |
12 |
0 |
|
|
|
0 |
0 |
1 |
1 |
1 |
0 |
|
|
0 |
0 |
10 |
15 |
7 |
0 |
|
|
C = |
0 |
0 |
0 |
1 |
1 |
1 |
, |
R = |
0 |
0 |
0 |
11 |
15 |
17 |
; |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
0 |
0 |
12 |
26 |
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
0 |
0 |
25 |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
6) |
|
0 |
1 |
1 |
1 |
1 |
0 |
|
|
0 |
19 |
16 |
8 |
18 |
0 |
|
|
|
0 |
0 |
1 |
1 |
0 |
0 |
|
|
0 |
0 |
20 |
1 |
0 |
0 |
|
|
C = |
0 |
0 |
0 |
0 |
1 |
1 |
, |
R = |
0 |
0 |
0 |
0 |
32 |
42 |
. |
|
|
0 |
0 |
1 |
0 |
0 |
1 |
|
|
0 |
0 |
45 |
0 |
0 |
2 |
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
|
|
0 |
0 |
0 |
31 |
0 |
20 |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
Ответы:
1) d* = 28. 2) d* = 44. 3) d* = 55. 4) d* = 51. 5) d* = 68. 6) d* = 61.
Лабораторная работа 9.