Добавим фиктивные исток и сток. От истока ко всем белым вершинам проведем ребра, весом в B (цена перекраски в черный). От черных вершин ко стоку проведем ребра, весом в W (цена перекраски в белый). И между всеми соседними вершинами (будь они одного или разных цветов) - ставим ребро весом в G (серая линия). Величина максимального потока будет ответом на задачу.
Источник: Всеукраинская школьная олимпиада по информатике, 2007, День 1
Решение
Все, что нам надо - это разделить каждую вершину на две, и между ними поставить ребро, весом в ограничение пропускной способности данной вершиныРешение
В классической задаче о минимальном разрезе удалять нужно ребра. Не проблема! Разобьем вершины на 2, и поставим между ними ребро, весом в 1. Тогда ответ к задаче - нахождение минимального разреза в графе (что и есть максимальным потоком).Источник: Харьковская зимняя школа по программированию, 2009, День 3
После перехода по автомату из i в j по ребру k, стираются все переходы из i по ребру k, а также все переходы в j по ребру k. Требуется вывести количество путей из A в B по такому автомату.
Решение
Задача сводится к нахождению максимального количества путей, причем из одной вершины не выходят более одного ребра одного цвета. Сведем задачу к нахождения максимального потока. Для каждой вершин создадим k+1 вершину в перестроенной сети. Первая вершина будет входом, остальные вершины будут представлять цвета. Из вершины входа проведем по ребру пропускной способностью 1 в каждую из k вершин, соответствующих цвету. Из вершины соответствующих цвету i проведем все ребра цвета i во входы концов ребер. Найдя максимальный поток в такой сети, получим максимальное количество путей удовлетворяющих требуемому свойству.Решение
Построим сеть. Создадим для каждого типа монет по одной вершине. Эти вершины будут соответствовать Вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности 1 в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у Вас.Для каждого члена клуба (кроме 1, тоесть Вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать
не более k-1 монеты, которых у него k (k > 1). Естественно, член клуба отдает одну монету взамен одной полученной.
Таким образом, в каждую такую вершину нужно провести ребро пропускной способности 1 из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью k i - 1 в вершину i, соответствующую монетам, которых у члена клуба больше одной.
Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны Вами.
Источник: Харьковская зимняя школа по программированию, 2009, День 4
Дано описание системы охлаждения. Нужно выяснить, каким образом можно пустить жидкость по трубам, чтобы выполнялись все указанные условия.
Решение
Это задача на нахождение циркуляции в сети с заданными нижними ограничениями на ребра. Если по ребру (u, v) должен проходить поток в отрезке , то в перестроенной сети будет три ребра (откуда, куда, вес): (u, v, r - l), (S, v, l), (u, T, l). S, T - дополнительно введенные сток и исток соответственно. Фактически мы пропускаем по ребру необходимый минимальный поток, после чего балансируем его так, чтобы получить циркуляцию.Сумма потоков через дуги, инцидентные 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) Уилсон Р. Введение в теорию графов
Гамильтоновы циклы
Граф задан в форме матрицы, где в ячейках задана стоимость передвижения между пунктами. На главной диагонали ставится символ ∞, чтобы исключить бессмысленный путь в сам себя.
Т.к. в полученной матрице оказался столбец без нулевых элементов, то найдем в нем минимальный элемент и вычтем его из всех элементов этого столбца.
| A | B | C | D | |
| A | ∞ | |||
| B | ∞ | |||
| C | ∞ | |||
| D | ∞ |
Просуммируем все вычтенные элементы и получим нижнюю границу цикла в= 2+2+3+2+1=10
1.2. Проведём оценку всех нулевых элементов матрицы.
Оценку нулей удобно представлять в таблице.
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
θ=max γ=γ А C =2
1.3. Множество путей разобьём на два подмножества:QAC – пути, содержащие дугу (AC) и QAC – пути, не содержащие дугу (АC). Для второго подмножества нижней границей будет: в / =в+ θ =10+2=12.
Чтобы вычислить границу для первого подмножества, перейдём к матрице на порядок ниже, вычеркнув A-строку и C-столбец. В новой матрице для исключения обратного пути (CA) в соответствующую клетку поставим знак ∞.
Вычислим границу полученной матрицы 2+0=2
и добавим её к нижней границе цикла. Эта сумма в // =10+2=12 и будет границей для первого подмножества.
1.4. Сравним границы всех висячих вершин и выберем вершину с наименьшей границей. Если этих вершин две, выбираем любую из них. Это вершина QAC , нижняя граница которой =12.
Выберем максимальную из оценок θ=max γ=γ BD =3
в / =12+3=15.
1.6. Все последующие пункты выполняем аналогично предыдущим.
Выберем максимальную из оценок θ=max γ=γ С B = ∞
в / =в+ θ=∞
| A | |
| D |
Все строки и столбцы этой матрицы содержат нули. Следовательно, граница остается равной 12.
ЗАДАЧА. Найти величину максимального потока на транспортной сети.
ПОСТАНОВКА ЗАДАЧИ.
Рассмотрим транспортную задачу на сети (I,D,G ) с заданными пропускными способностями дуг c(i,j).
Выделим две фиксированные вершины: s - источник и t – сток. Потоком на сети s→t назовем числовую функцию f , определенную на множестве дуг и удовлетворяющую следующим линейным уравнениям и неравенствам:
0≤ f(i,j) ≤c(i,j) для любых (i,j)
Требуется максимизировать переменную x
Разрезом L
в сети, отделяющим вершины s t
называется множество дуг 
Любой путь s→t содержит по крайней мере одну дугу разреза.
КРИТЕРИЙ ОПТИМАЛЬНОСТИ: на реальной сети величина произвольного потока не превосходит пропускной способности разреза, а величина максимального потока равна минимальной пропускной способности разреза.
ПРИМЕР 3.12.
М 9 К
М 8 К
ПРИМЕР 3.13.
М 2 К
РЕШЕНИЕ:
Пропускная способность исходящей дуги (Т,В) превышает суммарную пропускную способность входящих в соответствующую вершину дуг. Для того, чтобы сеть стала реальной, заменим с(Т,В)=5.
Найдем и вычислим значение пропускных способностей всех разрезов. (К,В) – (Т,В) разрез с минимальной пропускной способностью =6. Следовательно, максимальный поток =6.
Сеть, имеющую несколько источников и стоков можно свести к сети с одним источником и стоком.
ПРИМЕР. Пусть имеется несколько источников S и стоков T (транспортная задача). Расширим сеть, добавив два узла s* , t* и все дуги (s*, S) , (T,t*). Доопределим функцию пропускной способности, положив
МЕТОД РАССТАНОВКИ ПОМЕТОК.
1. Начальный поток f(i,j) = 0.
Припишем вершинам данной сети пометки, которые будут иметь вид (i+, ε)
или
(i - , ε).
Источник пометим (-, ∞),
т.е. ε(s)=
∞.
2. Для любой помеченной вершины i
выберем все непомеченные вершины j
для которых f(i,j)
Эту операцию повторяем до тех пор, пока не окажется помеченным сток. Если сток остался непомеченным, то найденный поток - максимальный, а множество дуг, связывающих помеченные вершины с непомеченными, образуют минимальный разрез.
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 К
| 1 шаг | А → (-, ∞) М → (А+,8) Р → (А+,3) К → (Р+,3) Т → (Р+,3) В → (Т+,3) | f(Т,В)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(А,М)=0 f(М,Р)=0 f(М,К)=0 f(М,Т)=0 f(К,Т)=0 f(К,В)=0 |
| 2 шаг | А → (-, ∞) М → (А+,8) Р → (М+,1) К → (М+,4) Т → (М+,2) | f(К,В)=3 f(М,К)=3 f(А,М)=3 f(Т,В)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(М,Т)=0 f(М,Р)=0 f(К,Т)=0 |
| 3 шаг | А → (-, ∞) М → (А+,5) Р → (М+,1) К → (М+,1) Т → (М+,2) В → (Т+,2) | f(Т,В)=5 f(М,Т)=2 f(А,М)=5 f(К,В)=3 f(М,К)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(М,Р)=0 f(К,Т)=0 |
| 4 шаг | А → (-, ∞) М → (А+,3) Р → (М+,1) К → (М+,1) Т → (Р+,1) В → (Т+,1) | f(А,М)=6 f(Т,В)=6 f(Р,Т)=4 f(М,Р)=1 f(М,Т)=2 f(К,В)=3 f(М,К)=3 f(А,Р)=3 f(Р,К)=0 f(К,Т)=0 |
| 5 шаг | А → (-, ∞) М → (А+,2) Р → (М-,1) К → (М+,1) Т → (К+,1) В → (Т+,1) | f(А,М)=7 f(М,К)=4 f(К,Т)=1 f(Т,В)=7 f(Р,Т)=4 f(М,Р)=1 f(М,Т)=2 f(К,В)=3 f(А,Р)=3 f(Р,К)=0 |
| 6 шаг | А → (-, ∞) М → (А+,1) | Поток оптимален f=10 Минимальный разрез:М →Т-М →Р-М →К |
ЗАДАЧА. Найти наибольший поток на сети
АЛГОРИТМ
Обозначим вершину 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. Значит условное оптимальное управление – идти на север. Пометим его стрелкой и занесем соответствующие затраты.
| |
| |
| |
| ЗАДАЧА 2. О загрузке машины (о рюкзаке). Имеется N предметов. Известны вес a i и ценность φ i каждого предмета. Требуется заполнить рюкзак, способный вместить вес ≤ R , таким набором предметов, который обладал бы наибольшей ценностью.
Процесс загрузки рюкзака можно разбить на N шагов. На каждом шаге мы решаем вопрос: брать данный предмет или не брать? На каждом шаге имеется всего 2 управления: управление =1, если мы берем данный предмет; и 0 – если не берем. Состояние системы перед очередным шагом характеризуется весом S, который еще остался в нашем распоряжении до конца полной загрузки после того, как предыдущие шаги выполнены (какие-то предметы уже загружены), т.е. количеством свободного пространства в рюкзаке. АЛГОРИТМ. 1. Начнем с последнего шага. Сделаем различные предположения о свободном пространстве в рюкзаке: S=0,1,…R. Положим последний предмет в рюкзак, если в нем сводного пространства достаточно. 2. На каждом предыдущем шаге для всех возможных состояний S рассмотрим 2 варианта: брать или не брать предмет. Найдем выигрыш в каждом случае, как сумму выигрышей на текущем шаге и на следующем уже оптимизированном шаге. Результаты занесем во вспомогательную таблицу. 3. На первом шаге рассмотрим только единственно возможное состояние S=R. 4. Найдем решение, «пятясь назад», т.е. взяв оптимальное управление на первом шаге, изменим состояние системы на втором шаге: S=R–x 1 a 1 и выберем оптимальное управление х 2 для этого состояния. И т.д. ПРИМЕР 4.2. Исходные данные
Основная таблица
Вспомогательная таблица.
Ответ: x 4 =0; x 3 =1; x 2 =0; x 1 =1; W=15 ЗАДАЧА 3. О распределении ресурсов. Имеется N предприятий П 1 , П 2 ,… П N , каждое из которого дает доход φ k (x), если ему выделен ресурс в количестве x. Требуется имеющийся в количестве А ресурс распределить между объектами так, чтобы суммарный доход был максимальным. Пусть x k – количество ресурса, выделенное k-ому предприятию. Тогда рассматриваемая задача сводится к обычной задаче нелинейного программирования.
Сформулируем задачу, как задачу динамического программирования. За первый шаг примем вложение средств в предприятие П 1 , за второй – в П 2 и т.д. Управляемая система в данном случае – средства, которые распределяются. Состояние системы перед каждым шагом характеризуется одним параметром – наличным запасом еще не вложенных средств. В этой задаче шаговыми управлениями являются средства, выделяемые предприятиям. Требуется найти оптимальное управление (х 1 , х 2 ,…х N), при котором суммарный доход максимален: | 1,1 0,5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=3 | 0,1 0,5 | 1,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=4 | 0,1 0,5 | 2,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=5 | 0,1 0,5 2,5 | 3,1 2,5 2,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| i=1 S=5 | 0,5 1,5 | 3,1 1,1 | 3,1 3,5 2,1 2,6 |
Ответ: 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. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ
Алгоритм расчета максимального потока в сетях
ШАГ 1. Начальные присваивания. Текущему значению А т максимального потока в сети присваиваем значение 0. ШАГ 2. Выбор независимых маршрутов в сети и определение потоков в них. Из всего множества возможных маршрутов в сети от источника к стоку выбираем независимые маршруты М 1 , … , М k , не имеющие общих вершин, кроме начальной (источника v и ) и конечной (стока v с ). Для каждого выбранного маршрута М i (1£ i £ k ) определяем максимальный поток А (М i ).ШАГ 3. Коррекция текущего значения максимального потока в сети. Прибавляем найденные на ШАГе 2 значения максимальных потоков в независимых маршрутах М 1 , … , М k к текущему общему максимальному потоку в сети: А т := А т + А (М 1)+ А (М 2)+…+ А (М k ).ШАГ 4. Коррекция сети. Найденные на ШАГе 2 максимальные потоки А (М 1), … , А (М k )вычитаем из пропускной способности соответствующих дуг сети. Дуги с нулевой остаточной пропускной способностью удаляем.ШАГ 5. Проверка завершения работы алгоритма. Если после коррекции в сети не осталось маршрутов из источника v и в сток v с , то искомый максимальный поток в сети равен найденному текущему А := А т , алгоритм завершает свою работу, поскольку все пропускные возможности сети исчерпаны. Если же в корректированной сети существуют маршруты из источника v и в сток v с , то переход на ШАГ 2 и продолжение выполнения алгоритма. Пример 2. Найти максимальный поток в сети на рис.1.15 по данному алгоритму. Решение.ШАГ 1. Начальные присваивания. А т : = 0.I итерация. ШАГ 2. Выбор независимых маршрутов в сети и определение потоков в них. В качестве М 1 возьмем маршрут(v и =V 1 , V 2 , V 5 , v с =V 7), рассмотренный в примере 1. Для него А (М 1) = 10.
Также несложно выделить независимый от М 1 маршрут М 2 = (v и =V 1 , V 3 , V 6 , v с =V 7). Выполним для него расчет максимальной пропускной способности и скорректируем пропускную способность дуг: А (М 2)= min {d 13 , d 36 , d 67 }= min {45, 40, 30}= 30. d 13 ¢= d 13 - 30 = 15, d 36 ¢= d 36 - 30 = 10, d 67 ¢= d 67 - 30 = 0.
ШАГ 3. Коррекция текущего значения максимального потока в сети. А т := А т + А (М 1)+ А (М 2) = 0 + 10+ 30 = 40.ШАГ 4. Коррекция сети. Найденные на ШАГе 2 максимальные потоки А (М 1), А (М 2) в маршрутах М 1 , М 2 вычитаем из пропускной способности их дуг. Дуги с нулевой остаточной пропускной способностью удаляем. Результат дан на рис.1.16 а. а) б)Рис.1.16. Результат коррекции сети после итераций I и IIШАГ 5. Проверка завершения работы алгоритма. В корректированной сети (рис.1.16 а) существуют маршруты из источника v и в сток v с , например М 3 = (v и =V 1 , V 4 , V 2 , V 5 , v с =V 7). Продолжение выполнения алгоритма.II итерация. ШАГ 2. В качестве единственного независимого маршрута примем М 3 = (v и =V 1 , V 4 , V 2 , V 5 , v с =V 7). Для него:
А (М 3)= min {d 14 , d 42 , d 25 , d 57 }= min {15, 10, 10, 15}= 10.
d 14 ¢= d 14 - 10 = 5, d 42 ¢= d 42 - 10 = 0, d 25 ¢= d 25 - 10 = 0, d 57 ¢= d 57 - 10 = 5.
ШАГ 3. А т := А т + А (М 3) = 40 + 10= 50.ШАГ 4. Коррекция сети. Максимальный поток А (М 3)вычитаем из дуг маршрута М 13 . Результат дан на рис.1.16 б.
ШАГ 5. В корректированной сети не осталось маршрутов из источникав сток. А := А т := 50, завершение работы алгоритма.Ответ: максимальный поток в сети на рис.1.15 равен 50.Еслив сети задано несколькоисточников, ее достраивают, вводя новый общий источник, который соединяют с исходными источниками дугами, имеющими неограниченную пропускную способность. Затем задачу решают по обычному алгоритму. Искомыми потоками через исходные источники будут потоки по вновь добавленным дугам, входящим в них из нового общего источника. Аналогично поступают при наличии в сети нескольких стоков.
Сетевое планирование
Любую задачу по проектированию либо построению достаточно сложного объекта (проект ) можно разбить на ряд более мелких составляющих шагов. От правильного выбора последовательности выполнения данных шагов зависят сроки выполнения всего проекта.
Весь комплекс действий по выполнению проекта представляют в виде совокупности событий и работ . Событиями называют отдельные этапы проекта. Работами называют процесс их выполнения. Весь комплекс событий и работ, необходимых для выполнения проекта, может быть представлен в виде двухполюсной сети Г = ({v и, v з }, V, X ), в которой:
а) все события обозначены множеством вершин V, среди них выделено исходное событие v и (начало работ) и завершающее событие v з (завершение выполнения всего проекта), внутренние вершины сети задают промежуточные события - этапы, которые необходимо выполнить в процессе реализации проекта,
б) все работы обозначены дугами, соединяющими между собой пары событий - вершин.
Графическое изображение данной сети называют сетевым графиком. Для обозначения последовательности действий в сетевой график вводят также фиктивные работы , которые не связаны с выполнением каких-либо действий. Соответствующие работы обозначают штриховыми дугами.
В качестве примера рассмотрим организацию некоторого производства. Проект требует выполнения следующих работ:
I) маркетинговые исследования, II) предпроектные исследования по оборудованию, III) организация сети сбыта, IV) проведение рекламной кампании, V) разработка технического задания на производственное оборудование, VI) разработка технической документации на производственные помещения и коммуникации, VII) закупка стандартного оборудования, VIII) проектирование и изготовление нестандартного оборудования, IX)строительство производственных помещений и монтаж коммуникаций, X) монтаж стандартного оборудования, XI) монтаж нестандартного оборудования, XII) пусконаладочные работы.
Данные работы обозначим в сетевом графике дугами с соответствующими номерами.
Событиями в данном проекте будут следующие:
1) начало работ (исходное событие), 2) завершение маркетинговых исследований, 3) завершение предпроектных исследований, 4) организация сети сбыта, 5) организация рекламной кампании, 6) подготовка технического задания на производственное оборудование, 7) завершение разработки технической документации на производственные помещения и коммуникации, 8) завершение закупки стандартного оборудования, 9) завершение проектирования и изготовления нестандартного оборудования, 10) завершение строительства производственных помещений и монтажа коммуникаций, 11) завершение установки оборудования и пуско-наладочных работ,
12) завершение проекта (завершающее событие).
Событиям сопоставляем вершины с соответствующими номерами. Сетевой график выполнения проекта дан на рис. 1.17:
Рис.1.17. Сетевой график выполнения проекта
Транспортная задача
Может возникать в физике, экономике и т.д.
На отдельные компоненты транспортной сети
(сеть железнодорожных, автомобильных и т.д.
путей; сеть трубопроводов и т.д.) наложены
ограничения – их максимально допустимая
нагрузка.
Необходимо определить максимально
возможное количество пассажиров, товара,
продукта и т.д., которое можно провезти по этой
сети и каким образом.
Мы построим графовую дискретную модель
этой транспортной задачи и решим ее в этой
модели.
работая в отделе статистического управления Военновоздушных сил США в Вашингтоне, впервые решил
задачу о максимальном потоке в ходе подготовки
воздушного моста во время блокады Западного Берлина.
В 1951 году Джордж Данциг впервые сформулировал
задачу в общем виде. В 1955 году, Лестер Форд и
Делберт Фалкерсон впервые построили алгоритм,
специально предназначенный для решения этой задачи.
Их алгоритм получил название алгоритм ФордаФалкерсона.
В 2010 году исследователи Джонатан Кёлнер и
Александер Мондры из МТИ вместе со своими
коллегами Дэниелем Спилманом из Йельского
университета и Шень-Хуа Тенем из ЮжноКалифорнийского университета продемонстрировали
очередное улучшение алгоритма.Дан ориентированный граф
(транспортная сеть) G=(V, E), вершина
графа s (источник) и вершина t (сток).
Каждой дуге (i, j) приписана некоторая
пропускная способность с(i,j) 0 (без
потери общности считаем её
целочисленной величиной),
определяющая максимальное значение
потока, который может протекать по
данной дуге.Потоком
в
сети
называют
целочисленную функцию f(i, j), заданную
на множестве дуг E и обладающей
следующими свойствами:
1. Ограничение потока пропускной
способностью
Для любой дуги (i, j) E выполняется
неравенство f(i, j) c(i, j).2. Сохранение потока
Для любой вершины q V,
выполняется равенство
q s
и
q t
f (i, q) f (q, j)
i V
(i , q) E
j V
(q , j) E
Т. е. сумма потока, заходящего в q, равна
сумме потока, выходящего из q (поток без
потерь и накоплений)Требуется определить значение
максимального потока, который
можно пропустить от источника s к
стоку t, и его распределение по дугам.Пример
У компании Lycky Puck в Ванкувере есть фабрика
(источник s), производящая хоккейные шайбы, а в
Виннипеге – склад (сток t), где эти шайбы хранятся.
Компания арендует места на грузовиках других фирм
для доставки шайб с фабрики на склад. Поскольку
грузовики ездят по определенным маршрутам (ребрам)
между городами (вершинами) и имеют ограниченную
грузоподъемность, компания Lycky Puck может
перевозить не более c(u,v) ящиков в день между каждой
парой городов u и v. Компания Lycky Puck не может
повлиять на маршруты и пропускную способность. Ее
задача – определить, какое наибольшее количество
ящиков в день можно отгружать, и затем производить
именно такое количество, поскольку не имеет смысла
производить шайб больше, чем можно отправить на
склад.Методы решения задачи
Линейное программирование
Представить задачу о максимальном потоке как задачу
линейного программирования. Переменными являются
потоки по рёбрам, а ограничениями - сохранение потока
и ограничение пропускной способности.
Алгоритм Форда-Фалкерсона
Найти любой увеличивающий путь. Увеличить поток по
всем его рёбрам на минимальную из их остаточных
пропускных способностей. Повторять, пока
увеличивающий путь есть. Алгоритм работает только
для целых пропускных способностей.
10.
Пример 1Дадим формулировку задачи о максимальном
потоке в терминах линейного программирования.
Пусть ХKM - объем перевозок из пункта К в пункт М.
К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны
лишь в пункт с большим номером. Значит, всего
имеется 9 переменных ХKM, а именно, Х01 , Х02 , Х03 , Х12
, Х13 , Х14 , Х23 , Х24 , Х34 .
s=0
t=4
11.
Задача линейного программирования,нацеленная на максимизацию потока, имеет вид:
F → max ,
Х01 +Х02 +Х03 =F
-Х01 +Х12 +Х13 +Х14 = 0
-Х02 -Х12 +Х23 +Х24 = 0
-Х03 -Х13 -Х23 +Х34 = 0
-Х14 -Х24 -Х34 = - F
Х01 ≤ 2
Х02 ≤ 3
Х03 ≤ 1
Х12 ≤ 4
Х13 ≤ 1
Х14 ≤ 3
Х23 ≤ 1
Х24 ≤ 2
Х34 ≤ 2
ХКМ ≥ 0 , К, М = 0, 1, 2, 3, 4
F≥0.
12.
Разрезомназывают множество дуг,
удаление которых из сети приводит к
«разрыву» всех путей, ведущих из s в t.
Пропускная способность разреза – это
суммарная пропускная способность дуг, его
составляющих.
!!! Найти разрезы в примере 1
13.
Теорема Л. Форда и Д. Фалкерсона:Величина каждого потока из s в t не
превосходит
пропускной
способности
минимального разреза, разделяющего s и t,
причем поток, достигающий этого значения,
существует.
(Величина
максимального
потока
в
транспортной
сети
равна
величине
минимального разреза в ней)
!!! Найти минимальный разрез в примере 1
14.
С алгоритмической точки зрения этатеорема малопродуктивна.
Генерация всех подмножеств дуг и
проверка,
является
ли
очередное
подмножество разрезом – «лобовое решение»,
приводит к высокой сложности алгоритма.
Кроме того, данный факт не помогает
найти способ распределения максимального
потока по дугам.
15.
Алгоритм Форда-Фалкерсона«Техника меток» Л. Форда и Д. Фалкерсона
заключается в последовательном
(итерационном, поиском в ширину) построении
максимального потока путем поиска на каждом
шаге увеличивающей цепи, то есть пути, по
которому можно увеличить поток.
При этом узлы (вершины графа)
специальным образом помечаются. Отсюда и
возник термин «метка».
16.
Алгоритм Форда-ФалкерсонаЧто представляет из себя метка
вершины?
первая цифра в метке – это номер
вершины, из которой идет поток в
данную вершину;
вторая цифра в метке – численное
значение потока, который можно
передать в данную вершину.
17.
Алгоритм Форда-ФалкерсонаНа каждом шаге алгоритма вершины сети
могут находиться в одном из трех состояний:
вершина не имеет метки;
вершине присвоена метка, и она не
просмотрена, т. е. не все смежные с ней
вершины обработаны;
вершине присвоена метка, и она
просмотрена.
18.
Алгоритм Форда-ФалкерсонаКак только вершина-сток становится
помеченной, это говорит о том, что
очередная увеличивающая поток цепочка
найдена, итоговый суммарный поток
необходимо увеличить на величину потока
найденной цепочки, и перейти к
следующему шагу алгоритма.
19.
Алгоритм Форда-ФалкерсонаДуга e=(u, v) сети является допустимой
дугой из u в v относительно потока f, если
e=(u, v) и f(e)
e=(v, u) и f(e)>0 (дуги второго типа,
обратные).
Второе условие говорит о том, что
допустимыми являются и дуги, входящие в
вершину u, по которым «уже пропущен
ненулевой поток».
