Методы применения алгоритма нахождения максимального потока в сети.
Это пособие предназначено для студентов, изучающих курс дискретной математики и (или) теории графов. С его помощью Вы освоите тему "Максимальный поток и минимальный разрез в сети". Прямо из этого пособия Вы можете посчитать своё ИДЗ, даже если у Вас нет на компьютере 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 − количество дуг.
Посчитать
Алгоритм расчета максимального потока в сетях
ШАГ 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. Сетевой график выполнения проекта
Гамильтоновы циклы
Граф задан в форме матрицы, где в ячейках задана стоимость передвижения между пунктами. На главной диагонали ставится символ ∞, чтобы исключить бессмысленный путь в сам себя.
Т.к. в полученной матрице оказался столбец без нулевых элементов, то найдем в нем минимальный элемент и вычтем его из всех элементов этого столбца.
| 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. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ
При планировании рационального распределения продукции в сети распределения необходимо согласовывать пропускную способность каналов с потребностями клиентов и с мощностью производственного предприятия. Данный класс задач решается методом нахождения максимального потока.
Рассмотрим сеть распределения (рис. 4.21), в которой выделены пункты 0 (вход, например, склад готовой продукции производителя) и п (выход, распределительные центры, склады оптовых и розничных организаций, потребитель) и каждой дуге (отрезку), связывающей пункты i и j, сопоставлено число dij > 0, называемое пропускной способностью дуги. Величина пропускной способности характеризует максимальное допустимое количество материального потока, которое может проходить по соответствующей дуге в единицу времени.
Рис. 4.21.
Количество продукции, проходящее по дуге от i до j , будем называть потоком по дуге (i ,j ) и обозначать через . Очевидно, что
Если учесть, что весь материальный поток, вошедший в промежуточный пункт сети, должен полностью выйти из него, получим
Из естественного требования равенства потоков на входе и на выходе имеем
Величину Z назовем величиной потока в сети и поставим задачу максимизации Z при соблюдении обозначенных выше условий.
Поиск максимального потока сводится к поиску пропускной способности минимального разреза.
Рассмотрим универсальный алгоритм поиска в матричной форме.
Начальный этап алгоритма состоит в построении матрицы D 0, в которую заносятся значения пропускных способностей (для неориентированной дуги берем симметричные значения элементов матрицы ).
Основные шаги алгоритма состоят в поиске некоторого пути и коррекции потока на этом пути.
При поиске пути используем процесс отмечаний. Метим символом * нулевые строку и столбец матрицы (вход сети). В 0-й строке отыскиваем , метим соответствующие столбцы индексами
и переносим метки столбцов на строки. Затем берем ί-ю отмеченную строку, ищем в ней непомеченный столбец с , которому сопоставляем метки-индексы
Метки столбцов переносим на строки, и этот процесс продолжаем до тех пор, пока не будет отмечен п-й столбец.
Затем "обратным ходом" по индексам выясняем путь, приведший к η-й вершине, уменьшаем пропускные способности дуг пути (элементы матрицы) на V n и увеличиваем симметричные элементы на эту же величину.
Такая процедура продолжается до тех пор, пока отмечание n -й вершины не станет невозможным.
Максимальный поток может быть найден вычитанием из исходной матрицы D 0, получаемой после приведенной выше корректуры матрицы пропускных способностей:
Пример 4.4
Производство размещено в Москве. Для распределения продукции предприятие привлекает посредников, которые работают с предприятием через распределительные центры различных уровней. В европейской части России работает оптовое предприятие 1, обслуживаемое центральным распределительным центром. Оптовое предприятие 2 работает в ближайшем зарубежье (Украина, Белоруссия) и обслуживается региональным распределительным центром. Есть у предприятия на местном рынке (Москва и Московская область) свои клиенты – ритейлеры, которые получают продукцию с городского распределительного центра. Запасы регионального и городского распределительных центров пополняются с центрального распределительного центра.
Выделим фрагмент распределительной сети:
- склад готовой продукции производственного предприятия;
- центральный распределительный центр;
- региональный распределительный центр;
- городской распределительный центр;
- два оптовых предприятия;
- розничная точка, принадлежащая компании;
- потребители.
Рис. 4.22.
Каждое звено сети распределения обозначим цифрой, а над дугами проставим пропускную способность. Пропускная способность в зависимости от вида звена может быть выражена через объем производственной мощности, плановую потребность (спрос) потребителей и емкость рынка.
Граф сети распределения продукции представлен на рис. 4.23. Построим матрицу D 0, в которую занесем значения пропускных способностей звеньев распределительной сети (рис. 4.24).
Рис. 4.23.
Рис. 4.24.
Из нулевой строки отметим вершины (строки-столбцы) 1, 2 и 3 индексами μ = 0 и V, равными 30,10 и 10.
Из помеченной строки 1 отметим вершины 4 и 5 индексами μ = 1 и V4 = min (30,15) = 15, V5 = min (30,10) = 10.
Из строки 3 отметим вершину 6 и, наконец, из строки 4 – вершину 7 (рис. 4.25).
Рис. 4.25.
Обратным ходом по μ обнаруживаем путь: к вершине 7 от 4, к вершине 4 от 1, к вершине 1 от 0; корректируем элементы D 0 на величину потока V7 = 15.
Очередной шаг дает путь с потоком 5 (рис. 4.26).
Рис. 4.26.
Последующий шаг дает результат, представленный на рис. 4.27.
Рис. 4.27.
Дальнейшее отмечание невозможно. Отсюда получаем матрицу максимального потока (рис. 4.28).
Рис. 4.28.
В результате применения алгоритма нахождения максимального потока в сети получены результаты, представленные на рис. 4.29. Пары цифр в скобках, показанные на дугах графа, означают максимальную пропускную способность дуги и рекомендуемый объем поставки товаров в сеть.
