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

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 К

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

АЛГОРИТМ

Обозначим вершину 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. Значит условное оптимальное управление – идти на север. Пометим его стрелкой и занесем соответствующие затраты.

Ответ: 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. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ

Потоки в сетях

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

Пусть задана сеть, состоящая из множества вершин Е и множества дуг, соединяющих некоторые упорядоченные пары вершин, взятых из Е. Будем предполагать, что она является симметрическим графом, т. е. если дуга () входит в сеть, то в нее входит и симметричная дуга (), хотя реально такой дуги может и не быть. Для определенности присвоим вершинам сети следующие номера: . Каждая вершина характеризуется интенсивностью . Вершины, для которых , назовем источниками, вершины, для которых , - стоками, а остальные - промежуточными. По путям сети направляются некоторые потоки - однородное вещество (газ, жидкость) или транспорт - из источников в стоки. Каждой дуге () сети поставлено в соответствие число , называемое пропускной способностью дуги. Под пропускной способностью дуги понимается максимальный поток, который она может пропустить за единицу времени. Пусть , и для остальных вершин, тогда - единственный источник, - единственный сток, а - промежуточные вершины сети.

Ставится задача определить для заданной сети максимальную величину потока из источника в сток . Под потоком в сети из источника в сток будем понимать совокупность потоков {} по всем дугам сети, где - поток по дуге (), , равный количеству перемещаемой по ней субстанции в единицу времени. Математически задача о максимальном потоке формулируется следующим образом: найти неотрицательные значения для всех , максимизирующие

(3.9)

при ограничениях:

(3.11)

Условие (3.9) отражает величину максимального потока, который равен количеству вещества, вытекающего из источника, или притекающего в сток. Условия (3.10) означают, что поток по каждой дуге должен быть неотрицательным и не превышать ее пропускной способности; из условия (3.11) следует, что количество вещества, притекающего в любую промежуточную вершину, равно количеству вещества, вытекающего из нее.

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

Проиллюстрируем это на примере.

Рассмотрим сеть, состоящую из трех источников и двух стоков (Рис. 3.10). Пусть, для определенности, данная сеть описывает следующую задачу.

Места добычи нефти расположены в географических пунктах . Из мест добычи нефть транспортируется на нефтеперерабатывающие заводы через некоторые промежуточные пункты . Совокупность пунктов с соединяющими их транспортными магистралями изобразим в виде сети на Рис. 3.10, дуги соответствуют транспортным магистралям, а вершины - отдельным пунктам (местам добычи, заводам, станциям перекачки или железнодорожным станциям). Пропускные способности транспортных магистралей приписаны дугам сети. Чтобы определить, какое максимальное количество нефти можно транспортировать из мест добычи на нефтеперерабатывающие заводы, необходимо расширить сеть, добавив один фиктивный источник и один фиктивный сток (фиктивные дуги на рисунке нанесены штриховыми линиями).

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

Рис. 3.10. Введение фиктивного источника и стока

Пример 3.

Приведем пример решения задачи о максимальном потоке в Excel. Рассмотрим некоторую транспортную сеть (Рис. 3.11.). Предположим также, что транспортные потоки могут идти в обоих направлениях некоторых дуг (очевидно, данный случай является более общим и сложным для решения, чем случай односторонних транспортных потоков). На рисунке обозначены максимальные пропускные способности в обоих направлениях: например из пункта 3 в пункт 6 может быть транспортирован поток интенсивностью 4 единицы, и такой же поток – из пункта 6 в пункт 3 (нули у окончаний некоторых дуг означают невозможность транспортировки в соответствующем направлении). Требуется определить максимальную пропускную способность сети в целом, т.е. максимальное значение потока .

Рис. 3.11. Сетевой график примера 3.

Решение.

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

Максимизировать при ограничениях:

Введем данные на рабочий лист в соответствии с Рис. 3.12.

Рис. 3.12. Данные для решения задачи о максимальном потоке

Диапазон ячеек A6:Q6 отведем под расчетные значения переменных. В ячейки A8:A14, а также в целевую ячейку F13 введем следующие формулы

После запуска Поиска решения введем следующие ограничения:

В окне диалога Поиска решения в для диапазона изменяемых ячеек укажем A6:Q6.

В результате решения получим ответ: ; потоки в дугах представлены ниже

Следует отметить, что данная задача имеет неединственное оптимальное решение, то есть при максимальном потоке в 17 единиц может иметь место различное распределение потоков по дугам.

Это пособие предназначено для студентов, изучающих курс дискретной математики и (или) теории графов. С его помощью Вы освоите тему "Максимальный поток и минимальный разрез в сети". Прямо из этого пособия Вы можете посчитать своё ИДЗ, даже если у Вас нет на компьютере MATLAB. Если же у Вас есть MATLAB, перейдите на эту страницу : там у Вас есть возможность вмешаться в сценарий (программу) вычислений. Здесь же задача о максимальном потоке в сети решается путём сведения к задаче линейного программирования.

Введём обозначения:

• n =|V | − размер графа (количество вершин);
• m =|E | − мощность графа (количество рёбер);
• A − матрица инцидентности орграфа сети размером n ×m ; каждый её элемент a ik =1, если из i -й вершины выходит k -я дуга; a ik =−1, если в i -ю вершину входит k -я дуга; и a ik =0 в остальных случаях; в каждом столбце такой матрицы ровно одна единица, одна минус единица, а остальные нули;
• s − номер вершины-источника сети; из этой вершины должны только выходить дуги, и любая другая вершина должна быть достижима из источника;
• t − номер вершины-стока сети; в эту вершину должны только входить дуги, и из любой другой вершины должен быть достижим сток;
• a s − s A ; в ней должны быть только единицы, т.к. из источника должны только выходить дуги;
• a t − t -я строка матрицы инцидентности орграфа сети A ; в ней должны быть только минус единицы, т.к. в сток должны только входить дуги;
• A st − матрица инцидентности орграфа сети A с выброшенными из неё s -й и t -й строками;
• e − вектор-столбец длины m ; в каждом его элементе e k будет величина потока в k -й дуге;
• c − вектор-столбец длины m ; в каждом его элементе c k ≥0 задаётся пропускная способность k -й дуги.

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

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

Задача, двойственная к задаче о максимальном потоке − это задача о минимальном разрезе. Для построения минимального разреза можно воспользоваться теоремами двойственности. Нужно:

• удалить из орграфа сети все пустые (e k = 0) и насыщенные (e k = c k ) дуги;
• найти компоненты связности оставшегося графа;
• если таких компонент две, то выброшенные дуги дают минимальный разрез;
• если появится больше двух компонент связности, то у орграфа сети есть несколько минимальных разрезов (соответствующая задача линейного программирования вырожденная).

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

Для правильной работы с этой страницей Ваш браузер должен поддерживать сценарии Java Script . Включите их.

Введите исходные данные в находящиеся ниже области ввода. В первой области нужно (точнее, можно) ввести координаты вершин для рисования орграфа сети. Они задаются в виде матрицы n ×2: в первом столбце − x -е координаты, во втором − y -е. Числа можно задавать целые, с десятичной точкой или в экспоненциальной форме. Числа разделяйте пробелами. Общее количество строк в этой области ввода определяет размер орграфа n − количество вершин. Эти исходные данные (координаты вершин) не являются обязательными: если их не задать, то орграф сети будет рисоваться в виде правильного n -угольника, а количество вершин будет определяться максимальным номером вершины в следующей области ввода.

В следующей области ввода левая часть − обязательная для заполнения. В ней определяется структура орграфа сети. Каждая дуга в орграфе соединяет две вершины. Номера этих вершин задаются в виде матрицы m ×2 в левой части второй области ввода. На каждой строке вначале задаётся 1-я вершина (хвост, источник) дуги, а затем через пробел 2-я (остриё, сток) дуги. В этих столбцах должны быть натуральные числа от 1 до n включительно. Числа разделяйте пробелами. В правой части задаются пропускные способности дуг − положительные действительные числа. Если этот столбец не задан, все пропускные способности считаются одинаковыми (единичными). Общее количество чисел в каждом из этих столбцов определяет мощность орграфа m − количество дуг.

Сумма потоков через дуги, инцидентные v , равна сумме потоков через дуги, инцидентные w ; эта сумма называется величиной потока. Будем в первую очередь интересоваться потоками, имеющими наибольшую возможную величину, - так называемыми максимальными потоками. В общем случае сеть может иметь несколько различных максимальных потоков, однако их величины должны совпадать. (4)

Изучение максимальных потоков через сеть N = (V,D,a) тесно связано с понятием разреза, т.е. такого множества A дуг орграфа D, которое обладает тем свойством, что любая простая цепь из v в проходит через дугу, принадлежащую A. Пропускной способностью разреза называется сумма пропускных способностей принадлежащих ему дуг. Разрезы, обладающие наименьшей возможной пропускной способностью, называются минимальными разрезами.

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

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

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

Шаг 1 . Сначала подберем поток, обладающий ненулевой величиной (если такой поток существует). Например, если N – сеть, представленная на рис. 29.3, то подходящим будет поток, изображенный на рис. 29.4. Стоит отметить, что чем больше величина выбранного нами начального потока , тем проще будут последующие шаги.

Шаг 2 . Исходя из N, строим новую сеть N’ путем изменения направления потока на противоположное. Более точно, любая дуга a, для которой(a) = 0, остается в N’ со своей первоначальной пропускной способностью, а любая дуга a, для которой , заменяется дугой a с пропускной способностью и противоположно направленной дугой с пропускной способностью (a). Сеть N’ в нашем примере показана на рис. 29.5. Вершина v уже не является источником,а – стоком.

Шаг 3 . Если в сети N’ мы сможем найти ненулевой поток из v в, то его можно добавить к первоначальному потокуи получить в N новый поток’большей величины. Теперь можно повторить шаг 2, используя при построении сети N’ новый поток’ вместо. Повторяя эту процедуру, мы в конце концов придем к сети N’ , не содержащей ненулевых потоков; тогда соответствующий потокбудет максимальным потоком. Например, на рис. 29.5 существует ненулевой поток, в котором потоки через дуги (v,u ), (u,z ), (z,x ), (x,y ) и (y, ) равны единице, а потоки через остальные дуги равны нулю. Добавляя этот поток к потоку на рис. 29.4, получим поток, изображенный на рис. 29.6; повторяя шаг 2, легко показать, что это и есть максимальный поток.

Используемая литература:

(1) http://pgap.chat.ru/zap/zap264.htm#0

(2) Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы матроиды, алгоритмы

(3) Басакер Р., Саати Т. Конечные графы и сети.

(4) Уилсон Р. Введение в теорию графов

Пусть задан ориентированный граф G=, в котором направление каждой дуги vÎV означает направление движения потока (например поток автомобилей), пропускная способность каждой дуги равна d(v). На множестве вершин E выделены две вершины t и s . Вершина t является источником потока, s - стоком. Требуется определить максимальный поток, который может быть пропущен из вершины t в s .

Обозначим через x(v) величину потока, движущегося по дуге v . Очевидно, что

0£ x(v) £ d(v) , vÎV . (6. 1)

В каждой вершине iÎE\{t,s} объем потока входящего равен объему потока выходящего, т.е. справедливо равенство

{x(v )|i Î V + (i)}= {x(v)| iÎ V - (i)}

{x(v)| iÎV + (i)} - {x(v)| iÎV - (i)}=0. (6.2)

Для вершины t

{x(v)| iÎV + (i)} -{x(v)¦ iÎV - (i)}=-Q, (6.3)

для вершины s

{x(v)| iÎ V + (i)} -{x(v)¦ i Î V - (i)}= Q. (6.4)

Величина Q является величиной потока, который выходит из вершины t и входит в вершину s .

Требуется определить

Q ® max (6.5)

при ограничениях (6.1-6.4).

Величины Q, x(v) , vÎV, удовлетворяющие ограничениям (6.1-6.4) будем называть потоком в сети, и если они максимизируют величину Q , то максимальным потоком. Нетрудно видеть, что значения Q=0, x(v)=0, vÎV , являются потоком в сети.

Задача (6.1-6.5) является задачей линейного программирования и ее можно решить алгоритмами симплекс-метода.

Разобьем множество вершины Е на две непересекающиеся части Е1 и Е2 таким образом, чтобы tÎE1, sÎE2 . Разрезом V(E1,E2) , разделяющим t и s будем называть множество V(E1,E2)ÌV такое, что для каждой дуги v Î V(E1,E2) либо h1(v)ÎE1 и h2(v)ÎE2 , либо h1(v)ÎE2 и h2(v)ÎE1 .

Разобьем множество V(E1,E2) на две части V(E1,E2,+),V(E1,E2,-) следующим образом:

V(E1,E2,+)={vÎV(E1,E2)| h1(v)ÎE1 и h2(v)ÎE2}

V(E1,E2,-)= { vÎV(E1,E2)| h2(v)ÎE1 и h1(v)ÎE2}

Пропускной способностью разреза будем называть

Q(E1,E2) = {x(v)| vÎV(E1,E2,+)}-{x(v)| vÎV(E1,E2,-)}

Справедлива следующая

Теорема 1 . (О максимальном потоке и минимальном разрезе).

В любой сети величина максимального потока из источника t в сток s равна минимальной пропускной способности Q(E1,E2) среди всех разрезов V(E1,E2) , разделяющих вершины t и s .

Заметим, что в максимальном потоке

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0 , vÎV(E1,E2,-).

Пусть Q, x(v), vÎV, - некоторый поток в сети, последовательность

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

является цепью, соединяющих вершины t и s . Зададим на этой цепи направление движения от вершины t к s . Дуга v(j) из этой цепи называется прямой, если ее направление совпадает с направлением движения от t к s , и обратной в противном случае. Эту цепь будем называть путем увеличения потока , если для прямых дуг v цепи x(v) < d(v) и для обратных x(v) > 0 . По этой цепи можно пропустить дополнительный поток q из t к s величиной q = min (q1,q2), где q1=min (d(v) -x(v)) , минимум берется по всем прямым дугам цепи, q1=min (x(v)) , минимум берется по всем обратным дугам цепи.

Теорема 2 .

Поток Q, x(v) , vÎV , максимальный тогда и только тогда, когда не существует пути увеличения потока.

Предлагаемый алгоритм решения задачи о максимальном потоке в сети, основан на поиске пути увеличения потока из t в s , который в свою очередь основан на процессе расстановки пометок вершин. Будем говорить, что

вершина i помечена пометкой q(i)>0 , а также известна дуга прямая дуга v(i) , через которую поступил этот поток, либо помечена пометкой , если до нее дошел некоторый дополнительный поток величиной q(i)>0 , а также известна обратная дуга v(i) , через которую поступил этот поток;

вершина i просмотрена, если помечены все соседние с ней вершины.

Если помечена вершина s, то найден путь увеличения потока величиной q , который пропускается по этому пути. Для описания алгоритма нам понадобится также массив SPW , в который помещаются номера помеченных вершин в порядке их пометки. С1 - номер в массиве SPW просматриваемой вершины, С2 - номер последней помеченной вершины в этом массиве.