рефераты конспекты курсовые дипломные лекции шпоры

Раздел Программирование
/
МЕТОД ФОРДА-ФАЛКЕРСОНА

Реферат Курсовая Конспект

Выберите учебное заведение

МЕТОД ФОРДА-ФАЛКЕРСОНА

МЕТОД ФОРДА-ФАЛКЕРСОНА - раздел Программирование, Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения Постановка Задачи О Максимальном Потоке На Сети. ...

Постановка задачи о максимальном потоке на сети.

На сети, что задается графом (I,U), где I — множество вершин, U — множество дуг, с определенной на ней функцией пропускных способностей r_ij ((і,j) — дуга с U), зафиксированные две вершины — i1 и in. Вершина i1 (источник) имеет интенсивность d, вершина in (стек) — интенсивность –d, все другие вершины нейтральные. Нужно найти максимальную интенсивность источника d, при которой сеть допускает поток. Поток, что отвечает такому максимальному значению интенсивности d*, называется максимальным потоком, а именно значение d* — величиной этого потока.

Алгоритм Форда-Фалкерсона применяется для построения максимального потока на сети из заданной начальной вершины-источника в заданную конечную вершину-сток.

Будем считать, что вершиной-источником является 1-я вершина, вершиной-стоком — вершина с номером n.

Входные данные.

Для работы алгоритма необходимо задать следующую информацию:

1. Число вершин сети.

2. Матрицу смежности С, элементы которой с_іj определяются соотношениями:

с_ij=1, если существует дуга (і,j);

с_ij=0, если дуга (і,j) отсутствует.

3. Величины r_ij пропускных способностей дуг (і,j).

4. Начальный поток на сети, то есть величины x_ij, которые удовлетворяют условия:

a) 0£x_ij£r_ij;

b) Для произвольной вершины (кроме первой и последней) поток, что входит в вершину, равняется потоку, что выходит из нее.

Изложение алгоритма Форда-Фалкерсона.

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

В каждой итерации можно выделить два этапа.

Этап 1 (этап выставления отметок).

1. В каждый момент времени каждая вершина может находиться в одном из трех положений:

а) не обозначенная;

б) обозначенная, но не рассмотрена;

в) обозначена и рассмотрена.

Общий вид отметки j-ї вершины: [i+qj], или [и–,qj], где и — номер некоторой обозначенной вершины, при просмотре которой была обозначена вершина j. Вершина 1 всегда обозначена и имеет отметку [1+q1], где q1 равное + ¥ (бесконечности).

2. Просмотр произвольной обозначенной вершины j заключается в следующем:

a) произвольная необозначенная вершина k, для которой существует дуга (j,k) и имеет место неравенство x_jk<r_jk, получает отметку вида [j+qk], где

qk=min{qj, r_jk – x_jk};

б) произвольная необозначенная вершина k, для которой существует дуга (k,j) и имеет место условие x_kj>0, получает отметку вида [j–,qk], где

qk=min{qj, x_kj}.

3. Процесс выставления отметок заканчивается в одном из двух случаев:

а) вершина с номером n обозначена;

б) условие а) не выполняется, но ни одну вершину больше пометить нельзя.

В первом случае переходим к этапу изменения потока на сети. Во втором — до определения минимального разреза сети и максимального потока.

Этап 2 (этап изменения потока).

Поток в сети изменяется на величину qn согласно правила.

Если вершина n имеет отметку [k+qn], где k — номер некоторой вершины, то x_kn=x_kn+qn. Если отметка имеет вид [k–,qn], то x_nk=x_nk–qn. Переходим к вершине с номером k. Если отметка вершины k имеет вид [j+qk], то x_jk=x_jk+qn; если она равняется [j–,qk], то x_kj=x_kj–qn. Подобные действия продолжаем до тех пор, пока не будет достигнута начальная вершина. В этом случае все старые отметки вытираем и возвращаемся к первому этапу.

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

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

Величина максимального потока ровная суммарной пропускной способности минимального разреза.

Программное обеспечение.

Обучающий модуль, с помощью которого задача о максимальном потоке на сети Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО.

Задание.

Решить методом Форда-Фалкерсона задачи о максимальном потоке на сети, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи, в каждой из которых сеть задается матрицами смежности C и пропускных способностей R. Во всех задачах источником считается вершина 1, а стоком — вершина 6.

1)		1	1	0	0	0			10	18	0	0	0
		0	0	0	1	1			0	0	0	14	1
	C =	1	0	1	0	0	,	R =	10	0	17	0	0	;
		1	0	0	1	1			9	0	0	22	12
		0	0	0	0	1			0	0	0	0	18
		0	0	0	0	0			0	0	0	0	0

2)		1	1	0	0	0			11	33	0	0	0
		0	0	1	1	0			0	0	14	4	0
	C =	1	0	1	1	0	,	R =	5	0	15	23	0	;
		0	0	0	0	1			0	0	0	0	23
		0	0	1	0	1			0	0	11	0	22
		0	0	0	0	0			0	0	0	0	0

3)		1	1	1	0	0			20	21	22	0	0
		0	1	1	1	0			0	5	13	14	0
	C =	0	0	0	1	1	,	R =	0	0	0	12	28	;
		0	1	0	1	1			0	12	0	11	10
		0	0	0	0	1			0	0	0	0	17
		0	0	0	0	0			0	0	0	0	0

4)		1	1	1	0	0			5	19	27	0	0
		0	0	0	1	1			0	0	0	17	15
	C =	1	0	0	1	1	,	R =	23	0	0	7	8	;
		1	1	0	1	0			5	12	0	11	0
		0	0	0	0	1			0	0	0	0	28
		0	0	0	0	0			0	0	0	0	0

5)		1	1	1	1	0			24	33	6	12	0
		0	1	1	1	0			0	10	15	7	0
	C =	0	0	1	1	1	,	R =	0	0	11	15	17	;
		0	0	0	1	1			0	0	0	12	26
		0	0	0	0	1			0	0	0	0	25
		0	0	0	0	0			0	0	0	0	0

6)		1	1	1	1	0			19	16	8	18	0
		0	1	1	0	0			0	20	1	0	0
	C =	0	0	0	1	1	,	R =	0	0	0	32	42	.
		0	1	0	0	1			0	45	0	0	2
		0	0	1	0	1			0	0	31	0	20
		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.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения

СОДЕРЖАНИЕ... Общие рекомендации по использованию программного обеспечения... Элементарные преобразования матриц Метод Гаусса...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: МЕТОД ФОРДА-ФАЛКЕРСОНА

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Программного обеспечения
Программное обеспечение ПО–МО содержит диалоговые обучающие программы из линейных и нелинейных методов оптимизации (математического программирования), каждая из которых вызывается с п

Постановка задачи.
Решить систему линейных алгебраических уравнений a11x1 + . . . + a1n xn = a10 . . . . . . . . . . . . . . . . . .

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД
Постановка задачи линейного программирования в стандартной форме (СЗЛП). Найти вектор x=

МОДИФИЦИРОВАН СИМПЛЕКС-МЕТОД.
Изложение модифицированного симплекс-метода. Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенапра

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
Изложение двойственного симплекс-метода. Двойственный симплекс-метод (ДСМ) непосредственно применяется к решению почти каноничной задачи линейного програм

Постановка транспортной задачи.
В каждом из пунктов Pi, i=1...,m, производится ai единиц некоторого однородного продукта, а в каждом из пунктов Qj, j=1...,n, потребляется b

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

Свойства транспортной задачи.
1. Сбалансированная транспортная задача всегда допустимая и имеет оптимальное решение. 2. Ранг матрицы А ограничений транспортной

Основные теоремы.
1. Решение транспортной задачи базисное, если из его основных коммуникаций невозможно составить замкнутый маршрут (цикл). 2. ДБР

Метод северо-западного угла.
Метод состоит из однотипных шагов, поэтому его формальное изложение дадим лишь для 1-го шага. Заполняем северо-западную клеточку таблицы, покладая x11 = min{a1,

Алгоритм метода потенциалов.
1. Находится исходное допустимое базисное решение (ДБР), например, с помощью одного из упомянутых выше методов. 2. В дальнейшем метод потенциалов с

Программное обеспечение.
Обучающий модуль, с помощью которого транспортная задача Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО

СПОСОБНОСТЯМИ. МЕТОД ПОТЕНЦИАЛОВ
Постановка транспортной задачи с ограниченными пропускными способностями (ТЗО). В пункте Pi (i=1

Свойства ТЗО и основные теоремы.
1. Ранг сложенной из векторов Aij матрицы А, ограничений транспортной задачи равняется m+n–1, откуда выплывает, чт

Выходной ДБР ТЗО. 1 этап.
На множестве невычеркнутых клеточек транспортной таблицы находят клеточку (i1,j1) с минимальными транспортными расходами

Выходной ДБР ТЗО. II этап.
Пусть X=||xij||, i=1...,m, j=1...,n — матрица перевозок, построенная на первом этапе. Положим xi,n+1 = ai – (

Потенциалы.
Потенциалы строк ui, i=1...,m, и столбцов vj, j=1...,n, определяются как решение системы vj–ui=cij

Оценки.
Оценки Dijпеременных xij для всех небазисных клеточек вычисляются за формулой Dij=cij–vj+ui (оценки базисных переменных — нулевые). Те

Новый ДБР.
Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки Dij. Пометим та

Алгоритм метода потенциалов.
1. Строится выходной ДБР. 2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых: i) Вычисляются потенциалы u

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА СЕТИ. МЕТОД МИНТИ
Постановка задачи о кратчайшем пути на сети. На сети, что задается графом (I,U), где И — множество вершин,

Постановка целочисленной задачи линейного программирования.
Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (9.1)

Изложение метода Гомори-1.
Метод Гомори-1 является одним из методов отсечения, идея которых заключается в следующем. Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9

Алгоритм метода Гомори-1.
1. Решаем вспомогательную ЗЛП (9.1)–(9.3). Пусть x(0) — ее оптимальное решение. Если оптимальное решение не существует, то исходная ЦЗЛП также

ПРОГРАММИРОВАНИЯ. МЕТОД ГОМОРИ-2
Постановка частично целочисленной задачи линейного программирования (ЧЦЗЛП). Найти вектор x=(x1...,xn

МЕТОД ГОМОРИ-3
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

ПРОГРАММИРОВАНИЯ. МЕТОД ДАЛЬТОНА-ЛЛЕВЕЛИНА
Постановка частично дискретной задачи линейного программирования (ЧДЗЛП). Найти вектор x=(x1...,xn

МЕТОД ВЕТВЕЙ И ГРАНИЦ.
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

Изложение метода Ленд-Дойга.
Решается вспомогательная ЗЛП (13.1)–(13.3), которая получена из исходной ЦЗЛП (13.1)–(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1

Алгоритм метода Ленд-Дойга.
1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления

ЗАДАЧА О НАЗНАЧЕНИИ. ВЕНГЕРСКИЙ МЕТОД
Постановка задачи о назначении. Найти вектор (матрицу) X=(xij, і,j=1...,n), что минимизирует целевую функцию

ЗАДАЧА О НАЗНАЧЕНИИ. МЕТОД МАКА
Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4). Алгоритм метода Мака.

МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН
Постановка матричной игры двух лиц с нулевой суммой. Найти цену игры и оптимальные смешанные стратегии игроков для матричной игры двух лиц с нулевой суммой и заданн

Метод золотого сечения.
Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм мето

Метод случайного поиска.
Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.

Метод дихотомии (половинного деления).
Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм метода реа

КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД
Постановка задачи нелинейного программирования. Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию

Градиентные методы безусловной оптимизации.
Для задачи безусловной минимизации метод заключается в вычислении последовательности приближений x[s] по правилу x[s+1]=

Метод самого быстрого спуска.
Метод самого быстрого спуска представляет собой градиентный метод, в котором величина шага r[s] выбирается по правилу F(x[s]–r

Лiтература
1. Ю.М.Ермольев, И.И.Ляшко, В.С.Михалевич, В.И.Тюптя.Математические методы исследования операций. Киев, «Высшая школа», 1979. 2. Ю.Д.Попов. Линейное и нел

Хотите получать на электронную почту самые свежие новости?

Подпишитесь на Нашу рассылку

Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail

Новости и инфо для студентов

Свежие новости
Актуальные обзоры событий
Студенческая жизнь

Соответствующий теме материал

Похожее
Популярное
Облако тегов

Здесь
Временно
Пусто

Теги