Алгоритм поиска кратчайших путей

Запишем двойственную задачу по отношению к исходной (1)-(5). При этом в двойственной задаче столько же переменных, сколько ограничений в исходной, и столько же ограничений, сколько в исходной задаче переменных. Ограничения (2)-(4) записаны для каждого узла сети, поэтому в двойственной задаче будет содержаться n переменных, т.е. вектор двойственных переменных запишется:

.

Тогда двойственная ЗЛП будет иметь вид:

(6)

Здесь - вектор ограничений (2)-(4), в котором на r -том месте стоит 1, а на s -том стоит –1. - вектор коэффициентов в ограничениях (2)-(4), в котором на i -том месте стоит 1, а на j -том стоит -1. Двойственные переменные не ограничены по знаку. В скалярной форме (6) запишется:

(7)

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

(8)

(9)

(10)

Таким образом, вместо исходной задачи (1)-(5) необходимо решить двойственную задачу (8)-(10).

Для этого исходные данные записываются в следующую таблицу:

			…		…		…
	i j		…	r	…	s	…	n
			…		…		…
…	…	…	…					…
	r
…	…				…			…
	n		…		…		…

Клетки строк и столбцов заполняются величинами по мере решения задачи (8)-(10). Остальные клетки соответствуют дугам и заполняются значениями длин дуг . Оставшиеся клетки не заполняются и в расчетах не участвуют.

Вначале в строке и столбце с номерами r записываются нулевые значения . Далее последовательно заполняются элементы столбцов начиная с №1. Для определения элемента просматривается столбец № j и если в этом столбце существует хотя бы одна клетка с известным элементом и известным значением , то вычисляется:

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

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

Если при просмотре столбцов с неизвестными значениями невозможно их определить, то это значит, что до этих узлов jне существует пути из узла r. Строки и столбцы, соответствующие узлу j, из таблицы вычеркиваются.

Пусть найдены все для конечных узлов . Далее поверяются условия оптимальности (9). При этом возможны 2 случая:

1. Для любых дуг справедливо неравенство . Это означает, что кратчайшие пути найдены.

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

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

Когда задача решена, то величины , соответствующие концам пути, определяют длину кратчайшего пути из r в s, т.е. .

Сам кратчайший путь, т.е. узлы, через которые он проходит, восстанавливается следующим образом: в столбце s находится клетка , для которой . Такая клетка обязательно существует. Дуга будет последним звеном искомого пути. Далее в столбце с номером находится клетка , для которой . Дуга будет предпоследним звеном цепи. Далее просматривается столбец и т.д. до тех пор, пока не найдется первое звено пути , для которого .

Таким образом, найден путь . Длина этого пути

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

Так как предполагается, что для дуг пути выполняются неравенства (9), то можно записать:

…

Если сложить левые и правые части этих неравенств, то можно записать . Таким образом . Что и требовалось доказать.

Пример.

Найти кратчайший путь на заданной транспортной сети из узла №3 в узлы №5 и №7.

r=3, s=5,7.

	i j
			4	3	1
						2
		2
				1			7
				5	1			4
			4					1

Полагаем сначала . Далее:

1. j=1, v=3, =2. Þ.

2. j=2, v=1, =4. =2Þ=6.

3. j=4, v=1, =1. =2Þ=3.

4. j=5, v=6, =2. =6Þ=8.

5. j=6, v=4, =7. =3Þ=10.

6. j=7, v₁=5, =4. =8Þ=12

v₂=6, =1. =10Þ=11

Þ=11.

Проверка на оптимальность:

1. (1,2): =4= 7. (4,6): =7=

2. (1,3): =-2< 8. (5,3): =-8<

3. (1,4): =1= 9. (5,4): =-5<

4. (2,5): =2= 10. (5,7): =3<

5. (3,1): =2= 11. (6,2): =-8<

6. (4,3): =-3< 12. (6,7): =1=

Условие оптимальности выполняется для всех .

Длина пути ==11, ==8.

Восстановление пути:

1. Путь : (3,1,4,6,7)

2. Путь (3,1,2,5).

Задача о замене оборудования.

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

Пример такого типа задачи –

Задача о замене оборудования.

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

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

Всевозможные случаи замены оборудования можно изобразить с помощью ориентированного графа:

Здесь узлы графа соответствуют номерам начала периодов. Если оборудование эксплуатируется в течение промежутка (i, j), то на графе ставится соответствующая дуга, взвешенная числом . Оборудование арендуется в начале 1-го периода, а процесс функционирования предприятия завершается в начале периода времени n.

Допустим, в процессе эксплуатации оборудование заменяется при i=2 и i=7, т.е. оборудование заменяется в начале первого, второго и седьмого периодов:

и эксплуатируется до узла n. Тогда, очевидно, общая сумма затрат будет равна . А это выражение есть ни что иное, как длина пути (1,2,7,n).Таким, образом, каждому варианту замены оборудования можно поставить в соответствие некоторый путь из узла 1 в узел n. Т.е. множество вариантов замены оборудования отражается множеством путей на рассматриваемом графе. Следовательно, задача оптимального плана замены оборудования эквивалентна задаче поиска кратчайшего пути из узла 1 в узел n на рассматриваемой сети. (Предложить студентам записать ММ самостоятельно.)

Одна задача календарного планирования трудовых ресурсов.

Рассматривается функционирование предприятия в условиях сурового климата, его производственная программа может быть связана дополнительно с сезонностью. В таких условиях предприятию невыгодно создавать постоянные производственные коллективы и соответствующую социально-экономическую инфраструктуру.

Пусть рассматривается функционирование предприятия в течение n-1 промежутка времени, причем известно потребное количество бригад рабочих R_k () для выполнения производственной программы в течение к-того промежутка времени (периода). Если одна бригада рабочих на7имается в начале i-того промежутка и увольняется в начале j-того, т.е. используется в интервале (i,j), то затраты на содержание этой бригады равны .

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

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

Построение ММ.

Пусть - количество бригад, нанимаемых в начале i-того и увольняемых в начале j-того промежутков. Тогда ММ запишется:

(1)

(2)

, (3)

(4)

-целые (5)

В модели целевая функция (1) отражает суммарные затраты на содержание рабочих бригад. Ограничение (2) требует, чтобы в первом промежутке времени было ровно столько бригад, сколько требуется для выполнения работ на первом промежутке времени. Неравенство (3) допускает целесообразность содержания резервных бригад, т.к. они могут, в конечном счете, обойтись дешевле. Равенство (4) обеспечивает в последнем промежутке наличие ровно стольких бригад, сколько требуется. Условие (5) вытекает из физического смысла.

Модель (1)-(5) относится к классу задач линейного целочисленного программирования. Однако она тождественными преобразованиями сводится к модели транспортной задачи в сетевой постановке.

Неравенство (3) приводится к равенству введением доп. переменных:

, (6)

, (7)

Идея последующих тождественных преобразований заключается в следующем: из уравнений (7) и (4) соответственно вычитаем уравнения (2) и (7), записанные для участка с номером на единицу меньше. Запишем уравнение (7) для участка с номером к-1:

, (8)

Далее, вычтем (8) из (7):

Заметим: , и =

Тогда:

.

Проведя сокращения, можно записать:

, (9)

Если вычесть из уравнения (7) с номером к=2 уравнение (2), то получим:

, (10)

Теперь из уравнения (4) вычтем уравнение (7) с номером . Т.к. уравнение (4) аналогично (7) при и , то результат вычитания следует из формулы (9) при :

, (11)

К полученной системе уравнений (9)-(11) присоединим уравнения (2) и (4), умножив (4) слева и с права на –1:

, (12)

, (13)

Полученные уравнения (9)-(13) эквивалентны уравнениям исходной задачи, которая теперь свелась к задаче (1), (9)-(13) с условиями

,

-целые

Далее можно условно интерпретировать:

- объем перевозки по дуге (i,j).

R₁ - запас продукции в первом узле,

R_к- R_к-1 – запас продукции k -того узла ,

R_n-1 - запас продукции n -ого узла.

Тогда уравнение (12) интерпретируется как объем вывоза из первого узла, равный запасу продукции в этом узле, т.е. аналогично уравнению для истока транспортной сети. Уравнение (13) интерпретируется как объем продукции, привозимой в размере потребности в узел n, т.е. аналогичное уравнению для стока транспортной сети.

Рассмотрим уравнение (10):

- определяет объем продукции, вывозимый из узла 2,

- объем продукции, ввозимый в узел 2 по дуге (1,2).

В сеть вводится дополнительная дуга (3,2), по которой перевозится продукция в объеме . Тогда - суммарный объем продукции, привозимой в узел 2. Следовательно, уравнение (10) можно интерпретировать как уравнение баланса для промежуточных узлов транспортной задачи в сетевой постановке.

Аналогично в сеть добавляются дуги (k,k-1) для всех с объемами перевозок .

Тогда уравнения (9) интерпретируются как уравнения баланса для промежуточных пунктов ТЗ в сетевой постановке: суммарный объем вывозимой продукции минус суммарный объем ввозимой продукции равняется запасу продукции в этих узлах.

Таким образом, задача календарного планирования трудовых ресурсов (1)-(5) тождественными преобразованиями и добавлением новых дуг свелась к модели транспортной задачи в сетевой постановке (1), (9)-(13).

Распределительная задача.

КТЗ обобщается в различных направлениях. Одним из наиболее часто встречающихся обобщений является так называемая распределительная задача. Далее будут рассмотрены некоторые практические задачи, приводящие к распределительной задаче или ее модификациям.

1. Распределение заказов по предприятиям.

Пусть имеется m видов заказов, причем заказ i- того вида необходимо выполнить в количестве единиц (). Эти заказы могут быть размещены на n предприятиях. Стоимость выполнения единицы i -того вида заказа на j- том предприятии равна . Для производства единицы продукции i -того вида на j -том предприятии расходуется некоторый ресурс в количестве (например, сырье, трудовые ресурсы и т.п.), причем для каждого предприятия ресурс ограничен величиной .

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

Построение ММ.

Пусть - количество заказов вида i, выполняемых на j -том предприятии. Тогда ММ задачи будет иметь вид:

(1)

(2)

(3)

(4)

Здесь целевая функция (1) отображает суммарную стоимость выполнения заказов. Ограничения (2) требуют, чтобы расходуемые ресурсы на предприятиях не превышали заданной величины запасов. Ограничения (3) требуют выполнения всех заказов в необходимых объемах. Ограничения (4) очевидны. Задача (1) –(4) относится к классу ЗЛП. Она отличается от КТЗ (открытой) тем, что коэффициент .

К модели вида (1)-(4) сводится также известная задача о распределении самолетов по авиалиниям.

2. Распределение самолетов по авиалиниям.

Пусть имеются n типов самолетов, которые должны быть использованы для перевозки пассажиров по m авиалиниям. Число самолетов j- того типа равно . Исходя из данных о себестоимости пассажирокилометра и коммерческой загрузки каждого типа самолетов на каждой авиалинии, устанавливаются:

- месячные объемы перевозок пассажиров одним самолетом j -того типа по i- той линии.

- месячные затраты на эксплуатацию одного самолета j -того вида на i -той линии.

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

Необходимо распределить самолеты по авиалиниям для перевозки заданного количества пассажиров при минимальных затратах.

Построение ММ.

Обозначим через число самолетов j-того типа на i-той авиалинии. Тогда ММ задачи запишется:

(1)

(2)

(3)

, целые (4)

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

3. Планирование парка вагонов.

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

Пусть имеются n видов вагонов , в которые могут быть погружены грузы m видов . Количество вагонов j -того вида составляет штук. Норма загрузки вагона j -того вида грузом i -того вида составляет . Количество грузов i- того вида, которое необходимо погрузить, определяется величиной . Эксплуатационные расходы на погрузку i- того вида груза в один вагон j -того типа составляет . Требуется определить такое распределение вагонов, при котором все грузы были бы погружены в имеющиеся вагоны, а суммарная стоимость погрузки всех грузов была бы минимальной.

Построение ММ.

Пусть - число вагонов j- того типа, выделенных под погрузку грузом i -того вида. Тогда ММ задачи запишется:

(1)

(2)

(3)

, (4)

Целевая функция (1) отражает суммарную стоимость погрузки всех грузов, ограничение (2) требует, чтобы грузы каждого вида были погружены полностью, ограничение (3) требует, чтобы грузы были погружены в имеющееся количество вагонов.

К задаче вида (1)-(4) сводятся также задачи планирования работы речного флота. Так при анализе практических проблем Волжского речного пароходства к распределительной задаче сведены задачи распределения однородного грузового флота по грузовым линиям, пассажирского флота по линиям, задачи распределения по объектам перегрузочных машин, дноуглубительных снарядов и т.д.

Задачи дискретного программирования.

Многие задачи ИСО, такие, как распределение ресурсов, сетевого планирования и управления, календарного планирования, описываются математическими моделями ДП.

Рассмотрим задачу вида:

(1)

(2)

(3)

Здесь , G- некоторое множество n-мерного пространства . Если множество G является конечным или счетным, то условие (3) – это условие дискретности. В таком случае данная задача является задачей дискретного программирования (ЗДП).

Если вводится ограничение - целые числа, то приходят к задаче целочисленного программирования, которая является частным случаем ЗДП.

Если условие целочисленности накладывается только на часть компонент вектора Х, то задача (1)-(3) будет задачей частично-целочисленного программирования.

Если компоненты вектора Х могут принимать только 2 значения-0 или 1, то (1)-(3) – задача булевского программирования.

В задачах ДП область допустимых решений является невыпуклой и несвязной. Поэтому отыскание решения таких задач сопряжено со многими трудностями. В частности, практически невозможно применение стандартных приемов, используемых при замене дискретной задачи ее непрерывным аналогом, состоящих в дальнейшем округлении найденного решения до ближайшего целочисленного. Например, рассматривается ЗЦЛП:

Решение соответствующей ЗЛП без требования целочисленности Х*=(0,5; 0; 4,5), а искомое целочисленное решение Х*=(2; 2; 5).

Если множество G конечно, то наиболее простой метод решения задачи (1)-(3) состоит в прямом переборе. Суть метода: в любом порядке перебираются множества возможных значений Х и для каждого значения вычисляется значение целевой функции f(Х). Далее находится наибольшее (наименьшее) значение f(Х*), которое будет соответствовать оптимальному решению Х*ÎG. Однако в реальных задачах хотя G и конечно, но его размерность бывает очень большой, и такой перебор становится практически невозможным.

Поэтому для решения ЗДП разрабатываются специальные методы, основанные на принципе целенаправленного перебора, которые позволяют сократить полный перебор. Методы решения ЗДП по принципу подхода к проблеме делятся на 3 группы:

1. Методы отсечения, или отсекающих плоскостей

2. Метод ветвей и границ

3. Методы случайного поиска и эвристические методы

Задача о максимальном потоке на сети.

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

Предполагается, что сеть является симметрическим графом, т.е. если дуга (i,j) входит в сеть, то в неё входит и симметрическая дуга (j,i), хотя реально такой дуги может и не быть. Каждой дуге поставлено в соответствие число d_ij, называемое пропускной способностью дуги. Величина d_ij определяет максимальное количество продукции, которое может быть переведено по дуге (i,j) в единицу времени. Узел с номером Ø имеет неограниченный запас продукции и называется источником, а узел с номером n имеет неограниченную потребность в этой продукции и называется стоком. В остальных узлах, которые называются промежуточными, запас продукции или потребность в ней равны нулю.

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

Данная постановка справедлива для смешанных и неориентированных графов, т.е. множество D может содержать дуги и рёбра, только дуги или только рёбра.

Для математической постановки задачи введём переменные x_ij - количество продукции, перевозимое по дуге (i,j). Эта величина называется потоком по дуге (i,j). Тогда математическая модель задачи будет иметь вид:

(1)

(2)

(3)

Целевая функция (1) отражает величину потока по сети, которая должна быть максимизирована. Очевидно, поток на сети равен количеству продукции, вывозимой из источника или ввозимой в сток. Равенство (2) для промежуточных узлов записано из условия баланса: количество продукции, привозимого в узел, должно равняться количеству продукции, вывозимого из узла. Ограничения (3) очевидны. Модель (1)- (3) относиться к классу ЗЛП. Однако существует более эффективный алгоритм решения этой модели. Это алгоритм Форда.

Важную роль в обосновании алгоритма Форда решения задачи о максимальном потоке играет понятие разреза сети.

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

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

d (R,)=

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

Следовательно, если удастся построить такой поток, что его величина V ^* окажется равной пропускной способности некоторого разреза (R ^*,^*), т.е. V ^*= d (R ^*,^*), этот поток и будет максимальным, а (R ^*,^*) - разрезом с минимальной пропускной способностью.

Теорема Форда – Фалкерсона.

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

Например, цепь µ=(3,5,4,7,6,8) на рис.1, связывающая узел 3 с вершиной 8, содержит три прямые дуги (3,5), (4,7), (6,8) и две обратные (4,5), (6,7).

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

Доказательство. Пусть имеем максимальный поток в сети. Если x_ij=d_ij, то говорят, что дуга (i,j) насыщена потоком. Предполагается, что V^* величина максимального потока в сети. Необходимо доказать, что найдется такой разрез (R ^*,^*) на этой сети, пропускная способность которого равна V^* , т.е. V ^*= d (R ^*,^*).

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

Узлы, составляющие подмножество R, определяются последовательно, начиная с источника Ø, по следующему правилу: Ø = R; если и x_ij < d_ij

то ; если и x_ji >0, то . (4)

Применение правила (4) приводит к построению разреза. Очевидно, разрез будет построен в том случае, если сток .

Пусть сток . Тогда из правила (4) следует, что существует цепь из истока Ø в сток n с пропускной способностью больше нуля µ =(i₁,i₂,…,i_n), где i₁ = Ø, i_n = n. Это следует из того, что все прямые дуги, входящие в цепь, ненасыщенные (xi_si_s+1< di_si_s+1), а для всех обратных дуг (i_s+1, i_s) величина потока xi_s+1i_s> 0.

Пусть δ₁ наименьшая разность между пропускной способностью и величиной потока, взята по всем прямым дугам цепи µ, а δ₂ - наименьшая величина потока, взятая по всем обратным дугам этой цепи. Далее определяется величина δ= min(δ₁, δ₂) > 0 и увеличивается поток по всем прямым дугам цепи на δ,а на ту же величину уменьшается поток по всем обратным дугам цепи. Таким образом, величина нового потока равна V + δ, что противоречит предположению о максимальности V. Следовательно, предположение неверно, и , а множество дуг (R,) есть разрез, отделяющий исток от стока.

Пропускная способность построенного разреза равна максимальному потоку на сети. Действительно, из правила (4) нахождения подмножества R следует, что если

, , то x_ij = d_ij; в противном случае узел j входил бы в R.

Таким образом,

Теорема доказана.

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

Исходные данные заносятся в таблицу размерности (n+1) × (n+1). Если дуга , то в соответствующей клетке таблицы записывается значение d_ij.

Если обратная дуга , то в соответствующей клетке записывается значение d_ji, если дуга , то в клетке (j,i) записывается Ø.

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

*

j i	Ll000 00 0	…	…	…	n
		…	d0j	…	d0n
i	di0	…	dij	…	din
n	dn0	…	dnj	…

Каждый шаг алгоритма Форда состоит из трёх действий.

1.Находится путь по таблице из узла - истока Ø в узел-сток n с пропускной способностью больше 0. Для этого столбец, соответствующий узлу-истоку, отмечается знаком *. Далее отыскиваются в строке с номером 0 элементы d_ij > 0 и столбцы, в которых они находятся, отмечаются сверху номером просматриваемой строки (цифрой 0). В результате окажутся выделенными все дуги (0, j) c положительными пропускными способностями. Эти дуги могут служить первыми дугами пути из истока в сток.

Далее просматриваются те строки, номера которых совпадают с номерами отмеченных столбцов. В каждой такой строке i отыскиваются элементы d_ij > 0, находящиеся в непомеченных столбцах, и эти столбцы отмечаются номером просматриваемой строки. Таким образом, окажутся выделенными дуги, которые могут служить вторыми дугами путей из истока в сток.

Аналогичный просмотр строк продолжается до тех пор, пока:

а) либо не будет помечен столбец с номером n (сток) что означает выделение пути с пропускной способностью больше нуля из истока в сток;

б) либо нельзя помечать новые столбцы (в просматриваемых строках не окажется положительных элементов), при этом столбец с номером n также останется не отмеченным.

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

В случае ” а ” искомый путь µ из источника в сток находится, используя пометки столбцов. Пусть последний столбец n помечен номером k, тогда дуга (k,n) последнее звено искомого пути. Далее просматривается столбец с номером k, пусть отметка этого столбца l. Тогда дуга (l,k) предпоследнее звено искомого пути и т.д. Этот процесс продолжается до тех пор, пока не найдётся отметка *, т.е. отметка истока Ø. Пусть эта отметка будет цифра m. Таким образом, путь от истока к стоку будет состоять из дуг

µ =((Ø, m),…, (l,k), (k,n)). (5)

2.Клетки, соответствующие дугам этого пути, отмечаются знаком (–), а симметричные им клетки, т.е. соответствующие обратным дугам – знаком (+).

По найденному пути (5) можно пропустить максимально возможный поток, величина которого равна Θ = min { d_ij^- }.Эта величина Θ отнимается от всех пропускных способностей клеток, отмеченных знаком (–) и прибавляется к пропускным способностям клеток, отмеченных знаком (+). В результате получается новая таблица, в которой записаны неиспользованные пропускные способности дуг после пропускания максимального потока по пути (5).

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

Это процесс продолжается до тех пор, пока не будет иметь место случай б).

3.Пусть имеется случай б), т.е. когда не существует пути из истока в сток, состоящий из дуг с неиспользованными пропускными способностями. Это означает, что найдены все возможные пути перевозки продукции и задача решена. Для определения максимального потока на сети V^* в последней таблице выделяются отмеченные столбцы, номера которых образуют множество R^*, причём исток ^*. В результате получается минимальный разрез (R ^*,^*) и по теореме Форда- Фалкерсона

Для нахождения значений потоков по дугам x_ij^*, образующих поток V^* из элементов первой таблицы вычитаются соответствующие элементы последней таблицы. Если в клетке получается неотрицательная величина, то она оставляется; если – отрицательная, то в клетке записывается . Значения заполненных клеток будут соответствовать потокам по дугам x_ij^*. Причём

Пример. На данной сети определить максимальный поток из узла в узел 4.

1. * 0 0 1 2

i j
	0^+		19^- 0^+		9^-

Θ₁ = min (19,9)=9.

2. * 0 0 1 3

i j
	0^+	17^-   0^+	10 9	12^- 0^+	24^-

Θ₂ = min (17,12,24)=12.

3. * 0 0 2 3

i j
	12 9^+	5	10^- 6^+ 9	8^- 12	12^-

Θ₃ = min (10,8,12)=8.

4. * 0 0 1 2

i j
	12 17	5   12	2 14 9	12	4

Пути из 0 в 4 нет! Определяются множества: R*={0,1,2}, ={3,4}.

(R ^*,^*)=((1,3),(2,3),(2,4))

d (R ^*,^*)= V^* =12+8+9=29

5. В заключительной таблице положительные элементы определяют потоки по дугам x_ij^*.

i j
	-12 -17	12	17 -8 -9	12 -12	9 20

Дата добавления: 2014-01-11