Алгоритм Симплекс-метода

Исходные данные: задача в канонической форме; целевая функция мини­мизируется; найдено начальное базисное допустимое решение (опорный план),

то есть система уравнений (2) имеет базис и все правые части уравнений b_i ³ 0 - неотрицательны; целевая функция выражена через свободные переменные.

При выполнении этих условий каждая итерация метода состоит из трех шагов:

Шаг 1. Имеющийся план проверяется на оптимальность. Если в Z – стро­ке нет отрицательных элементов, то имеющийся план оптимален и задача реше­на. Если отрицательные элементы есть, то план не оптимален. Выбираем любой отрицательный элемент Z – строки (как правило, максимальный по модулю) и считаем столбец, в котором он находится в качестве разрешающего. Пусть для определенности это столбец переменной х_s.

Шаг 2. Выбор разрешающей строки. Пусть разрешающий столбец, вы­бранный на предыдущем шаге, это столбец переменной х_s. Для каждой i -ой строки (i = 1,...,m) делим элементы столбца свободных членов “Значение” (напомним, что все они неотрицательные) на положительные элементы разрешающего столбца, стоящие в этой строке, и находим минимальное из полученных частных, т.е. находим

Пусть этот минимум достигается в строке r. Тогда r -ая строка является разрешающей, элемент a_rs - разрешающий элемент таблицы.

Шаг 3. Пересчет таблицы. Преобразованиями Жордана-Гаусса пересчи­тываем таблицу относительно разрешающего элемента a_rs, найденного на предыдущем шаге, для чего:

3.1. Делим разрешающую строку на разрешающий элемент. В результате, на месте элемента a_rs будет стоять а¢_rs = 1.

3.2. Ко всем остальным строкам таблицы (включая Z - строку) прибав­ляем полученную разрешающую, умноженную на элемент (-a_is), где i – номер изменяемой строки i =1,2,...,r-1,r+1,...,m. К Z – строке прибавляем разрешаю­щую строку, умноженную на (- c_s). Иначе говоря, элементы новой таблицы (со штрихом) вычисляются по формулам:

а¢_rj = a_rj / a_rs; - новые элементы разрешающей строки (j = 1, 2,..., n);

b¢_r = b_r / a_rs

а¢_ij = a_ij - a¢_rj× a_is; - новые элементы i-й строки (i =1, 2,...,m; j = 1, 2,..., n);

b¢_i = b_i - b¢_r × a_is

c¢_j = c_j - a¢_rj× c_s; - новые элементы Z - строки (j = 1, 2,..., n);

Z¢ = Z - b¢_r × c_s

В результате этих преобразований в столбце х_s везде будут стоять нули кроме r -строки, где будет 1, т.е. х_s будет новой базисной переменной, целевая функция будет выражена через новые свободные переменные, новый план Х¢ находится в столбце “Значение” и лучше предыдущего, так как значение целевой функции для нового плана равно -Z¢ < Z. Переходим к шагу 1 и повторяем всю процедуру для нового плана Х¢.

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

Решение задачи линейного программирования в общем случае. Рас­смотрим следующую задачу ЛП:

Z = - 3x₁ + х₂ ® min

2x₁ – х₂ ³ 2,

-x₁ + 2х₂ ³ 5,

x₁ + х₂ £ 10,

x_1, х₂ ³ 0.

Приведем ее к каноническому виду введением трех неотрицательных пе­ременных х₃, х₄, х₅. Получим задачу:

Z = - 3x₁ + х₂ ® min

2x₁ – х₂ - х₃ = 2,

-x₁ + 2х₂ - х₄ = 5, (7)

x₁ + х₂ + х₅ = 10,

x_1, х₂, х₃, х₄, х₅ ³ 0.

При попытке решить эту задачу симплекс-методом возникает опреде­ленная трудность, связанная с тем, что нет очевидного начального базисного допустимого решения (опорного плана), так как переменные х₃ и х₄ не являют­ся базисными. Умножение первых двух уравнений на -1 также ничего не дает, поскольку соответствующее базисное решение (0, 0, -2, -5, 10) не будет до­пустимым. Пытаться просто перебирать базисные решения в попытке отыскать допустимое, нецелесообразно, так как неясно, имеет ли эта задача вообще допустимые решения.

Для решения проблемы применим метод искусственного базиса. Введем в первые два уравнения (третье не создает проблем) искусственные перемен­ные х₆ ³ 0 и х₇ ³ 0. В результате получим базис из переменных х₆, х₇, х₅.

2x₁ – х₂ - х₃ + х₆ = 2,

-x₁ + 2х₂ - х₄ + х₇ = 5, (8)

x₁ + х₂ + х₅ = 10,

Соответствующее базисное решение Х₀ = (0, 0, 0, 0, 10, 2, 5) является до­пустимым для ограничений (8). Однако ограничения (7) и (8) не являются экви­валентными в том смысле, что любому допустимому решению системы ограни­чений (8), в котором хотя бы одна искусственная переменная отлична от нуля, нельзя поставить в соответствие допустимое решение системы ограничений (7). С целью исключения искусственных переменных из базисного решения систе­мы ограничений (8), т.е. для получения допустимого базисного решения систе­мы ограничений (7), используем алгоритм симплекс-метода. Для того, чтобы искусственные переменные стали свободными, необходимо, чтобы они были равны нулю (сейчас х₆ = 2, х₇ = 5). Поэтому введем искусственную целевую функцию

W = х₆ + х₇.

и будем ее минимизировать при ограничениях (8). Если удастся найти базисное допустимое решение при котором W = 0 (сейчас W = 7), то тогда х₆ и х₇ будут равны нулю, поскольку они неотрицательны, и мы получим базис из основных и дополнительных переменных.

Таким образом, задача разбивается на два этапа. На первом этапе мини­мизируется искусственная целевая функция W. Этот этап закончится либо нахождением опорного плана исходной задачи (7), либо тем, что минимизи­ровать функцию W до нуля не удастся, т.е. допустимых планов нет, а значит (ввиду теоремы 1) и нет вообще допустимых решений задачи.

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

Этап 1. Составим исходную симплекс-таблицу для задачи (8). Все вычис­ления будем проводить также и для целевой функции Z. Тогда после заверше­ния первого этапа получим целевую функцию Z, выраженную через свободные переменные.

Базис	х1 х2 х3 х4 х5 х6 х7	Значение
x6 х7 x5	2 -1 -1 0 0 1 0 -1 2 0 -1 0 0 1 1 1 0 0 1 0 0
- Z	-3 1 0 0 0 0 0
- W	0 0 0 0 0 1 1

Для того, чтобы начать минимизацию функции W, ее надо выразить через свободные переменные. Для этого, из W - строки вычтем первую и вторую строки. Получим

Таблица 1.

Базис	х1 х2 х3 х4 х5 х6 х7	Значение
x6 х7 x5	2 -1 -1 0 0 1 0 -1 2 0 -1 0 0 1 1 1 0 0 1 0 0
- Z	-3 1 0 0 0 0 0
- W	-1 -1 1 1 0 0 0	-7

Так как в W – строке есть отрицательные элементы, то выбираем в качест­ве разрешающего любой из первых двух столбцов, например первый. Посколь­ку min{2/2, 10/1} = 1 достигается в первой строке, то разрешающая строка – первая и разрешающий элемент а₁₁ = 2. Пересчитывая таблицу относительно этого элемента, получим новую таблицу:

Таблица 2.

Базис	х1 х2 х3 х4 х5 х7	Значение
x1 х7 x5	1 -½ -½ 0 0 0 0 3/2 -½ -1 0 1 0 3/2 ½ 0 1 0
- Z	0 -½ -3/2 0 0 0
- W	0 -3/2 ½ 1 0 0	-6

Так как переменная х₆ вышла из базиса, то в дальнейшем ее не исполь­зуем (вычеркиваем столбец х₆). Теперь разрешающим столбцом будет второй, разрешающей строкой – вторая и после пересчета получим (поскольку искусственная переменная х₇ выйдет из базиса, столбец х₇ также вычеркиваем):

Таблица 3.

Базис	х1 х2 х3 х4 х5	Значение
x1 х2 x5	1 0 -2/3 -1/3 0 0 1 1/3 -2/3 0 0 0 1 1 1
- Z	0 0 -5/3 -1/3 0

Этап 1 успешно завершен, так как искусственные переменные выведены из базиса и мы получили опорный план Х₀ = (3, 4, 0, 0, 3) исходной задачи (7), к которому можно применить алгоритм симплекс-метода. На втором этапе W - строка уже не нужна и мы ее вычеркиваем.

Этап 2. Таблица 3.

Базис	х1 х2 х3 х4 х5	Значение
x1 х2 x5	1 0 -2/3 -1/3 0 0 1 -1/3 -2/3 0 0 0 1 1 1
- Z	0 0 -5/3 -1/3 0

Целевую функцию Z можно уменьшить (сейчас Z = -5) если ввести в базис х₃ или х₄.

Выбираем третий столбец в качестве разрешающего, т.к. –5/3 < -1/3. Разрешающей строкой будет третья, т.к. только в ней есть положительный эле­мент разрешающего столбца. Разрешающий элемент а₃₃ = 1. Пересчитывая таблицу, получим:

Таблица 4.

Базис	х1 х2 х3 х4 х5	Значение
x1 х2 x3	1 0 0 1/3 2/3 0 1 0 -1/3 1/3 0 0 1 1 1
- Z	0 0 0 4/3 5/3

Поскольку в Z – строке таблицы 4 нет отрицательных элементов, то новый план Х₁ = (5, 5, 3, 0, 0) является оптимальным и Z_min = Z(5,5) = -10.

Задача решена полностью.

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 3. Решить задачу линейного программирования симплекс-методом (x, y ³ 0).

Варианты:

1. Z = x - 2y ® min 2. Z = -x + y ® min

3x + y ³ 8 3x - 2y ³ 7

4x + 5y £ 29 x + 2y £ 13

x + 4y ³ 10 x - 2y £ 1

3. Z = 2x + y ® max 4. Z = x - y ® max

-x + 2y ³ 3 -2x + 3y £ 5

-x + y £ 1 x + 2y ³ 8

3x - 2y £ 3 3x - y £ 10

5. Z = 2x + y ® max 6. Z = x + y ® max

x - y £ 0 x - y ³ 0

3x - 2y £ 3 -x + 2y £ 4

5x - 4y ³ 1 -3x + 4y ³ 2

7. Z = 5x + 2y ® max 8. Z = 2x + 4y ® max

3x + y ³ 9 3x + y ³ 8

2x + y ³ 7 -x + 3y ³ 4

5x + 2y £ 17 x + 2y £ 11

9. Z = 2x + y ® max 10. Z = x - y ® min

-x + 5y £ 4 x + 3y £ 7

x - y £ 4 2x - y £ 7

x + y ³ 2 5x + y ³ 7

V. ТРАНСПОРТНАЯ ЗАДАЧА

Общая постановка транспортной задачи состоит в определении оптималь­ного плана перевозок некоторого однородного груза из m пунктов отправления А ₁, А ₂,..., А _m в n пунктов назначения B₁, B ₂,..., B _n. При этом в качестве критерия оптимальности берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

Математическая модель транспортной задачи имеет вид: , (14)

(15)

(16)

(17)

Здесь c _ij - тарифы перевозки единицы груза из i – го пункта отправления А _i в j – ый пункт назначения B _j, b_j - потребность в грузе в j – ом пункте на­значения, a_i – запасы груза в i – ом пункте отправления.

Наличие линейных уравнений (15) и (16) обеспечивает доставку необхо­димого количества груза в каждый из пунктов назначения и вывоз всего имею­щегося груза из всех пунктов отправления. При этом, ввиду (17), исключаются обратные перевозки. Задача (14) – (17) является частным случаем задачи линей­ного программирования, однако, в силу своей специфики решается специаль­ным методом.

Если выполняется так называемое условие баланса

, (18)

то такая транспортная задача называется закрытой. Если условие баланса (18) не выполняется, то задача называется открытой.

Теорема 1. Для разрешимости транспортной задачи необходимо и доста­точно, чтобы выполнялось условие баланса (5).

Если то вводится фиктивный (n + 1) - ый пункт назначения с потребностью и соответствующие тарифы полагают рав­ными нулю, т.е. c _{i n+1} = 0 (i = 1,2,..., m). Аналогично, при вводится фиктивный, (m+1) – ый пункт отправления с запасами груза , при этом тарифы на перевозку из этого пункта также полагают равными нулю, c _{m+1 j} = 0.

Для решения задачи (14) – (17) применяется метод потенциалов, который по существу, является другой формой симплекс-метода.

Опишем алгоритм метода. Исходные данные транспортной задачи запишем в таблице

bj ai	b 1	b 2	...	b n
a 1	c 11	c 12	...	c 1n
a 2	c 21	c 22	...	c 2n
	...	...	...	...
a m	c m1	c m2	...	c mn

1. Построение начального опорного плана. Система ограничений (16)-(17) содержит m×n неизвестных и m+ n уравнений, связанных отношением (18). Невырожденный опорный план задачи содержит m + n – 1 положительных пе­ревозок или компонент. Таким образом, если каким-либо способом получен не­вырожденный опорный план задачи, то в матрице (x_ij) значений его компонент положительными являются только m + n – 1, а остальные равны нулю.

Клетки, в которых находятся отличные от нуля перевозки, называются за­нятыми, остальные – незанятыми. Занятые клетки соответствуют базисным не­известным, и для невырожденного опорного плана их количество равно m + n.

Для построения начального опорного плана применим метод минималь­ной стоимости.

Выбираем клетку с минимальной стоимостью (если их несколько, возь­мем любую из них). Пусть, например, . Тогда в клетку (i, j) записы­вают число . При этом, если , то значение b_k уменьшают на a_l и «закрывают» строку с номером l, так как ресурсы l -го поставщика исчерпаны. Если , то значение a_l уменьшают на b_k и «закрывают» столбец с номером k, что означает удовлетворение спроса k- го потребителя. Если же a_l = b_k, то «закрывают» строку или столбец по выбору.

Вышеописанную процедуру повторяют для оставшейся транспортной таблицы до тех пор, пока не будут закрыты все строки и столбцы.

2. Построение системы потенциалов. Система потенциалов строится для невырожденного опорного плана и имеет вид:

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

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

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

Если , то опорный план оптимален и задача решена. В противном случае план не является оптимальным, следовательно, его нужно улучшить.

4. Построение цикла и нахождение нового опорного плана. Среди отрица­тельных оценок выбираем наименьшую. Пусть

В клетке (l, k) нарушено условие оптимальности. Для улучшения опорно­го плана необходимо в клетку (l, k) отправить некоторое количество груза, превратив ее тем самым в базисную. Эта операция эквивалентна действию по замене базиса в симплекс-методе.

Клетку (l, k) отмечают знаком «+» и затем строят цикл, расставляя пооче­редно знаки «-» и «+» в базисных клетках так, чтобы в строках и столбцах стоя­ло по одному знаку «+» иди «-». Цикл строится единственным образом.

Обозначим , где - перевозки, стоящие в вершинах цикла, от­меченных знаком «-». Величина l определяет количество груза, которое можно перераспределить по найденному циклу. Значение l записывают в незанятую клетку (l, k). Двигаясь по циклу, вычитают или прибавляют l к объемам перевозок, расположенных в клетках, помеченными знаками «-» или «+» соответственно. Перевозки в остальных базисных клетках остаются без изменения. Переходим к построению системы потенциалов.

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

Пример. Компания контролирует 3 фабрики, производительность кото­рых в неделю (в тыс. изделий) задается вектором . Компания за­ключила договоры с четырьмя заказчиками, еженедельные потребности кото­рых (в тыс.изделий) задаются вектором Стоимость транс­портировки 1 тыс. изделий с i -ой фабрики j- му заказчику задается матрицей тарифов .

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

Так как , то введем в рассмотрение фиктивного 5-го заказчика с потребностью в b ₅ = 100 – 90 = 10 (тыс. ед.) груза. При этом положим c _i5 = 0, i = 1, 2, 3. Исходные данные запишем в виде таблицы.

Таблица 1.

bj ai	20	15	25	30	10
30	+		-
25
45	-		+

Построим начальный опорный план методом минимального элемента. Первой заполним клетку (1, 3) т. к. тариф этой клетки с ₁₃ = 2 меньше других та­рифов (фиктивный столбец заполняется в последнюю очередь). Поставка для клетки (1, 3) будет равна х ₁₃ = min( 30, 25) = 25. Записываем это число в верх­ний левый угол клетки. Это означает, что с первой фабрики третьему заказчику планируется поставить 25 тыс. ед. груза. При этом требования 3-го заказчика будут полностью удовлетворены и мы закрываем 3-й столбец. Затем в остав­шейся части таблицы (без 3-го столбца) ищем клетку с минимальным тарифом. Таких клеток две (1, 1) и (2, 4). Заполняем любую из них, например, клетку (1, 1). Остаток продукции 1-ой фабрики равен 30 – 25 = 5. Поэтому записать в клетку (1, 1) можно x ₁₁ = min(5, 20) = 5. Поскольку с первой фабрики вывезен весь груз (30 тыс. ед.), то закрываем первую строку. Далее поступаем аналогич­но, заполняя свободные клетки в порядке возрастания тарифов, закрывая каждый раз нужные строку или столбец. В результате начальный план имеет вид (см. табл.1):

Проверим этот план на оптимальность. Для этого найдем потенциалы u _i и v _j поставщиков и потребителей. Для этого по занятым клеткам составим систе­му уравнений вида u _i + v _j = c _ij:

u 1 + v 1 = 3 u 1 + v 3 = 2

u 2 + v 4 = 3

u 3 + v 1 = 8 u 3 + v 2 = 6 u 3 + v 4 = 9 u 3 + v 5 = 0.

Поскольку уравнений в системе столько же, сколько занятых клеток, то есть 7, а неизвестных - 8, то система имеет бесконечное множество решений. Положим, например, u ₃ = 0. Тогда остальные потенциалы находятся однознач­но: v ₅ = 0; v ₄ = 9; v ₂ = 6; v ₁ = 8; u ₂ = -6; u ₁ = -5; v ₃ = 7.

Теперь вычисляем оценки s _ij свободных клеток по формуле s _ij = c _ij – (u _i + v _j):

s 12 = 5 – (6-5) = 4 > 0; s 14 = 6 – (-5+9) = 2 > 0; s 15 = 0 – (-5+0) = 5 > 0;

s 21 = 6 – (-6 + 8) = 4 > 0; s 22 = 7 – (-6+6) = 7 > 0; s 23 = 5 – (-6+7) = 4 > 0; s 25 = 0 – (6+0) = 6 > 0;

s 33 = 4 – (0+7) = -3 < 0.

Среди оценок есть отрицательная (s ₃₃ = -3 < 0), следовательно план не является оптимальным. Необходимо улучшить план, загружая клетку с отрица­тельной оценкой.

Для этого построим для клетки (3, 3) цикл с вершинами в загруженных клетках (см. табл. 1), расставляя поочередно в вершинах, начиная с клетки (3, 3), знаки «+» и «-». Из поставок в клетках, помеченных знаком «минус», выбираем наименьшую: l = min(15, 25) = 15.

Для получения нового опорного плана изменим поставки в вершинах цикла: к поставкам в клетках, помеченных знаком «+», прибавляем величину l=15, в клетках, помеченных знаком «-», вычитаем эту величину 15. Новый опорный план поместим в таблицу 2.

Таблица 2.

b j ai	20	15	25	30	10	-2     -6
30		1 5		1 8	2 0
25	7 6	7 7	7 5		6 0
45	3 8

5 6 4 9 0

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

Выписываем матрицу Х^* (без последнего столбца):

Минимальные суммарные затраты по оптимальному плану составляют:

Z_min = 20×3+10×2+25×3+15×6+15×4+15×9 = 430 ден. ед. Из таблицы 2 видно, что избыточная продукция в количестве 10 тыс. изд. остается на третьей фабрике.

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 5. Определить оптимальный план перевозок с целью минимизации общих затрат на транспортировку с заданными векторами и и матрицей стоимостей С.

Варианты			С

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

Рассмотрим сеть G(V, U), где V множество вершин, а U множество дуг их соединяющих, (i, j) Î U поставлено в соответствие неотрицательное число d_ij (d_ij ³ 0), называемое пропускной способностью этой дуги (если дуга (i, j) – неориентированная, то полагаем d_ij = d_ji). Выделим в сети две вершины. Одну из них назовем источником и обозначим s, а другую – стоком и обозначим t.

Каждой дуге (i, j) сети поставим в соответствие неотрицательное число x_ij, которое назовем потоком на дуге (i, j). Потоком из источника s в сток t в сети G (V,U) называется множество неотрицательных чисел , удовлетво­ряющих ограничениям:

, (19)

, (20)

(21)

(22)

Неотрицательная величина v называется величиной потока в сети. Огра­ничения (1), (2) означают, что суммарная величина v потока, выходящего из источника s, равна суммарной величине v потока, входящего в сток t. Огра­ничения (3) выражают тот факт, что в каждую вершину (кроме источника и стока) приходит столько потока, сколько из нее уходит. Если для дуги (i, j) имеем x_ij = d_ij, то дуга (i, j) называется насыщенной потоком.

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

и ограничениями (19) – (22). В силу своей специфики для ее решения существует более эффективный алгоритм, чем симплекс-метод.

Разобьем множество вершин v сети G(V,U) на два непересекающихся подмножества R и Разрезом сети G(V,U) называется множество всех дуг (i, j), таких, что-либо i Î R, jÎ , либо jÎ R, iÎ . Т.е. разрез - это множество всех дуг, концевые вершины которых при­надлежат разным множествам: R и . При этом положим sÎ R, tÎ . Тогда мы получим разрез, отделяющий источник s от стока t. Если удалить все дуги некоторого разреза, отделяющего источник s от стока t, то на сети не останется пути ведущего из s в t.

Пропускной способностью разреза (R, ) называется величина

,

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

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

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

Алгоритм расстановки пометок нахождения увеличивающего пути

Шаг 1. Источник s получает метку (s⁺).

Шаг 2. Для всех дуг (s,j) выходящих из вершины s, соответствующие вершины j получают метку s⁺, если x_{sj <} d_sj. Для дуг (i,s), входящих в вершину s, соответствующие вершины i получают метку (s^-), если x_is> 0.

Шаг k. Просматриваем все вершины, помеченные на (k- 1)- ом шаге. Для каждой такой вершины k, соответствующие им вершины j, для которых x_ki< d_kj, получают метку (k⁺), для всех дуг (i,k), входящих в вершину k, соответст­вующих им вершины i, для которых x_ik > 0, получают метку (k ^-).

Алгоритм заканчивает работу одним из двух состояний: а) после некото­рого шага мы не можем пометить ни одной вершины, и сток t остался непоме­ченным. Это означает, что имеющийся поток является максимальным, а (R, ), где R – множество помеченных, - множество непомеченных вершин, образует минимальный разрез; б) сток t оказался помеченным. Двигаясь от стока t к вершине, номер которой указан в ее метке и т.д., мы придем к источнику.

Дата добавления: 2017-02-01