Поток минимальной стоимости
Сущность задачи о потоке минимальной стоимости: нахождение оптимального способа передачи потока через транспортную сеть. Использование потенциалов, решение задачи без отрицательных рёбер. Применение на первом шаге алгоритмов Беллмана-Мура, Дейкстры.
Рубрика | Математика |
Вид | творческая работа |
Язык | русский |
Дата добавления | 16.06.2012 |
Размер файла | 523,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Министерство образования и науки России
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Брянский государственный университет имени академика И.Г. Петровского
Физико-математический факультет
Кафедра алгебры
Направление «Информационные технологии»
Творческая работа
Поток минимальной стоимости
Выполнили: студенты 3 курса ФМФ
Овчаров Б.С., Прокудин А.В.
Свентицкий Е.И., Свентицкий П.И.
Научный руководитель:
К. ф.-м. н. М.М. Сорокина
Брянск 2012
Поток минимальной стоимости
Рассмотрим задачу определения потока, заданной величины от к в сети , в которой каждая дуга характеризуется пропускной способностью и неотрицательной стоимостью пересылки единичного потока из и вдоль дуги . Если , где - величина максимального потока в сети от к , то решения нет. Если же , то может быть определено несколько различных потоков величины от к . Математическая модель задачи выглядит следующим образом. Минимизировать
(1)
где - поток по дуге при ограничениях:
1.
2. Для начальной вершины
- уравнение истока
3. Для конечной вершины
- уравнение стока
4. Для любой другой вершины
- условие сохранения потока
Если - кратчайший путь от к в сети , - минимальная из пропускных способностей дуг, входящих в путь , и если , то задача имеет тривиальное решение - весь поток направлен вдоль пути . Общее решение о потоке минимальной стоимости строится следующим образом. Сначала находится кратчайший путь от к и величина максимально возможного потока вдоль этого пути. Если окажется, что , то задача решена. В противном случае сеть модифицируют следующим образом. Затем опять находят кратчайший путь от к и максимально возможный поток вдоль этого пути в модифицированной сети. Процедуры модификации сети и нахождения кратчайшего пути в ней повторяются до тех пор, пока либо нужное количество не будет переправлено, либо возникает сеть, в которой нет пути от к , что означает отсутствие решения у исходной задачи.
Модификация сети допускается только определенного порядка. Пусть - исходная сеть, S - множество вершин, U - множество ребер, - множество весов (пропускных способностей дуг), D - набор стоимостей пересылки единичного потока из в вдоль дуги .
Модификация относительно данного потока сеть строится следующим образом.
1. , т.е. число и набор вершин в модифицированной сети не изменяется.
2. , где - некоторое множество фиксированных дуг. Таким образом, после модификации число дуг сети увеличивается.
3. Если и , то дуга включается в множество V. При этом полагается . Этот пункт применяется только к дугам, по которым проходит поток , относительно которой происходит модификация сети.
4. Для всех ненасыщенных дуг, где нет противоположного потока, в том числе и для ненасыщенных дуг с потоком, относительно которого происходит модификация сети, т.е. для и полагают
.
5. Для всех насыщенных дуг и полагают
Это довольно сложный и «длительный» алгоритм. Нахождение кратчайшего пути как в исходной, так особенно в модифицированной сети может потребовать использование алгоритма Белмана-Мура. Кроме того, решение типичных учебных задач требует три-четыре интерполяции алгоритма.
Пример 1
Пусть матрицами и заданы пропускные способности дуг сети и стоимости транспортировки единичного потока вдоль всех дуг.
Требуется:
1) построить максимальный поток от к и указать минимальный разрез, отделяющий от
2) построить поток величины , имеющий минимальную стоимость, здесь […] - целая часть числа.
Построим рисунок соответствующей сети (рис. 1); первое число на дугах - стоимость транспортировки единичного потока вдоль этой дуги, второе - пропускная способность дуги.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Рис. 1
Найдём максимальный поток от вершины к вершине по алгоритму Форда-Фалкерсона.
Этап 1
Путь Увеличиваем поэтому поток до 11 единиц, ребро станет насыщенным. Второй возможный путь
Поток по этому пути будет равен 10 единицам. Дуга станет насыщенной. Третий путь, по которому возможен ненулевой поток, - это путь Здесь По этому пути можно увеличить поток лишь на единицу, при этом дуга станет насыщенной. Больше путей нет.
Этап 2
Рассмотрим маршруты с противоположными рёбрами. Маршрут Поток можно увеличить на две единицы на дуге . Эта дуга станет насыщенной. Тогда потоки по этому маршруту будут такими Больше маршрутов нет. Поток максимален. На рисунке 2 на дугах графа стоят две цифры: первая - пропускная способность дуги, вторая - поток на дуге (насыщенные дуги выделены). Теперь можно сделать несоклько разрезов, например, отделяя исток и сток. И по разрезу I, и по разрезу II поток одинаков
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Рис. 2
Построим теперь поток величины
единиц
По рассмотренному алгоритму для этого надо построить кратчайший путь от к на графе Этот граф изображён на рисунке 3; веса всех дуг в нём положительны, можно использовать алгоритм Дейкстры.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Рис. 3
Этап 1.
Шаг 1
1-я итерация.
Шаг 2
={x1,x2}, d(x1)=min(?, 0*+9),
d(x2)=min(?, 0*+10)=10.
Шаг 3
Min (9,10,?,?)=9*=d(x1), =x1.
Шаг 4. =t? Нет. Переход на начало второго шага.
2-я итерация
Шаг 2. ={x2,x3}, d(x2)=min(10, 9*+12)=10,
d(x3)=min(?, 9*+9)=18.
Шаг 3
min(10,18,?,?)=10*=d(x2), =x2.
Шаг 4
=t? Нет
3-я итерация
Шаг 2
={x3,x4,t}, d(x3)=min(18, 10*+7)=17,
d(x4)=min(?, 10+9)=19, d(t)=min(?,10+13)=23.
Шаг 3
min(17,19,23)=17*=d(x3), =x3.
Шаг 4
=t? Нет
Переход на начало второго шага
4-я итерация
Шаг 2
={x4}, d(x4)=min(19, 17*+14)=19.
Шаг 3
min(19,23)=19*=d(x4), =x4.
Шаг 4
=t? Нет
Переход на начало второго шага
5-я итерация
Шаг 2
={t}, d(t)=min(23, 19*+9)=23.
Шаг 3
min(23)=23*=d(t), =t.
Шаг 4
=t? Нет
Переход. Конец первого этапа
Этап 2
Кратчайший путь здесь очевиден, это путь
µ1*=(s,x2)-(x2,t)
Максимальный поток по этому пути
цmax=сmin(µ1*)=min(11,17)=11
Так как и=18, то цmax< и; требуется модификация сети.
Положим ц(s,x2)= ц(x2,t)=11 и ц (xi,xj)=0 для остальных дуг. Тогда по третьему пункту правил модификации сети включим обратные дуги (x2,s) и (t,x2). При этом (x2,s)=11, (x2,s)=-10, (t,x2)=17, (t,x2)=13. По четвертому пункту правил характеристики всех дуг, где нет потока, останутся без изменений, для дуг потока ц=11, т.е. только для дуги (x2,t), изменятся характеристики (x2,t)=13, (x2,t)=17-11=6. По пятому пункту правил для насыщенной дуги (s,x2)(s,x2)=0, (s,x2)=?. В результате имеем новую сеть G=(S,U,D)(рис. 4). Необходимо найти кратчайший путь между s и t в этой сети. Так как теперь есть дуги с отрицательным весом, следует применить алгоритм Беллмана-Мура.
минимальний оптимальный поток сеть
Рис. 4
Этап 1
d(s)=0, d(x1)=d(x2)= …=d(t)=?, Q={s}.
1-я итерация.
Шаг 2
=s, Q=Ш, ={x1,x2},
d(x1)=min(?,0+9)=9,
9<??
Да, корректировка очереди. Q={x1},
d{x2}=min(?,0+?)=?,
?<?? Нет, корректировка очереди не проводится
Шаг 3
Q=Ш? Нет
2-я итерация.
Шаг 2
=x1, Q=Q\{x1}=Ш, ={x2,x3},
d(x2)=min(?,9+12)=21,
21<?? Да, корректировка очереди. Q={x2},
d{x3}=min(?,9+9)=18,
18<?? Да, корректировка очереди. Q={x2,x3}.
Шаг 3
Q=Ш? Нет
3-я итерация.
Шаг 2
=x2, Q={x3}, ={s,x3,x4},
0<0? Нет, корректировка очереди не проводится,
d(x3)=min(18,21+7)=18,
18<18? Нет
d{x4}=min(?,21+9)=30,
30<?? Да, корректировка очереди. Q={x3,x4},
d{t}=min(?,21+13)=34,
34<?? Да, корректировка очереди. Q={x3,x4,t}.
Шаг 3
Q=Ш? Нет.
4-я итерация
Шаг 2
=x3, Q={x4,t}, ={x4},
d(x4)=min(30,18+13)=30,
30<30? Нет, очередь не корректируется.
Шаг 3
Q=Ш? Нет
5-я итерация
Шаг 2
=x4, Q={t}, ={t},
d(t)=min(34,30+9)=34,
34<34? Нет, очередь не корректируется.
Шаг 3
Q=Ш? Нет
6-я итерация
Шаг 2
=t, Q=Ш, =Ш.
Шаг 3
Q=Ш? Да. Конец первого этапа алгоритма Беллмана-Мура
Итак, кратчайший путь найден. Это путь
=(s, x1)-(x1,x2)-(x2,t)
Его вес
d()=9+12+13=34
цmax=cmin()=min(13, 11, 6)=6
Общий поток по двум уже рассмотренным путям
цобщ=11+6=17<18=и,
т. е. требуется еще одна модификация сети
Положим опять ц(s,x1)=ц(x1,x2)=ц(x2,t)=6, ц(s,x2)=11 и , ц(xi,xj)=0 для остальных дуг. По третьему пункту правил включаем обратные дуги (x1,s), (x2,x1), (t,x2), причем последняя дуга уже присутствует. Полагаем (x1,s)=6, (x1, s)=-9, (x2,x1)=6, (x2,x1)=-12, (t,x2)=17, (t,x2)=-13. По четвертому пункту правил все ненасыщенные дуги, где нет потока остаются без изменений, кроме дуг с потоком (x1,s), (x1,x2). Здесь (s,x1)=13-6=7, (s,x1)=9, (x1,x2)=11-6=5, (x1,x2)=12. По пятому пункту правил для насыщенной дуги (x2,t) (x2,t)=0, (x2,t)=?. В полученной после второй модификации сети G=(S,U,D) необходимо найти кратчайший путь между вершинами s и t. Так как опять имеются отрицательные веса, то снова придется применить алгоритм Беллмана-Мура (рис. 5).
Этап 1
Шаг 1
d(s)=0, d(x1)=d(x2)= …=d(t)=?, Q={s}.
Шаг 2
=s, Q=Ш, ={x1, x2}.
d(x1)=min(?, 0+9)=9, 9<?? Да. Q={x1},
d(x2)=min(?,0+?)=?.
Шаг 3
Q?. Переход на второй шаг.
2-я итерация
Шаг 2
=x1, Q=Ш.
={s, x1, x2}, d(s)=min{0, 9-9}=0,
0<0? нет корректировки очереди,
d(x2)=min(?, 9+12)=21, 21<?? Да. Q={x2},
d(x3)=min(?, 9+9)=18, 18<?? Да. Q={x2, x3},
Шаг 3
Q?Ш. Переход на второй шаг.
3-я итерация
Шаг 2
=x2, Q={x3}, ={s, x1, x3, x4, t},
d(s)=min{0, 21-10}=0, нет корректировки очереди,
d(x1)=min{9, 21-12}=9, нет корректировки очереди,
d(x3)=min{18, 21+7}=18, нет корректировки очереди,
d(x4)=min{?, 21+9}=30, Q={x3, x4},
d(t)=min{?, 21+?}=?, нет корректировки очереди,
Шаг 3
Q?Ш. Переход на второй шаг.
4-я итерация
Шаг 2
=x3, Q={x4}, ={x4},
d(x4)=min{30, 18+14}=30, нет корректировки очереди,
Шаг 3
Q?Ш.
5-я итерация
Шаг 2
=x4, Q=Ш, ={t}.
Шаг 3
Q?Ш.
6-я итерация
Шаг 2
=t, Q=Ш, =Ш.
Шаг 3
Q?Ш
Конец первого этапа. Критический путь найден.
=(s,x1) - (x1,x2) - (x2,x4) - (x4,t)
Его вес
d() = 9 + 12 + 9 + 9 = 34
цmax=cmin()=min(7,5,13,10)=5
Таким образом, по этому пути можно пустить поток в пять единиц. Тогда общий поток будет
цобщ=17+5=22>и=18
Для того чтобы сформировать поток требуемой величины и=18, необходимо по пути направить поток величиной всего в одну еденицу.
Тогда ц(s,x1)=7, ц(x1,x2)=7, ц(x2,x4)=1, ц(x4,t)=1. Кроме того два предыдущих потока дали ц(s,x2)=11, ц(x2,t)=17. Таким образом, минимальная стоимость всего потока и=18 равна
(xi,xj)•ц(xi,xj)=9•7+12•7+10•11+13•17+9•1+9•1=496.
Размещено на Allbest.ru
Подобные документы
Элементы теории графов. Центры и периферийные вершины графов, их радиусы и диаметры. Максимальный поток транспортировки груза и поток минимальной стоимости. Пропускная способность пути. Анализ сетей Петри, их описание аналитическим и матричным способами.
задача [1,3 M], добавлен 28.08.2010Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа [23,5 K], добавлен 12.06.2011Основные понятия, связанные с графом. Решение задачи Эйлера о семи кёнигсбергских мостах. Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов. Применение теории графов к решению задач по математике; степени вершин и подсчёт рёбер.
курсовая работа [713,8 K], добавлен 16.05.2016Понятие интерполяционного многочлена Лагранжа как многочлена минимальной степени, порядок его построения. Решение и оценка остаточного члена. Нахождение приближающей функции в виде линейной функции, квадратного трехчлена и других элементарных функций.
курсовая работа [141,5 K], добавлен 23.07.2011Сущность методов сведения краевой задачи к задаче Коши и алгоритмы их реализации на ПЭВМ. Применение метода стрельбы (пристрелки) для линейной краевой задачи, определение погрешности вычислений. Решение уравнения сшивания для нелинейной краевой задачи.
методичка [335,0 K], добавлен 02.03.2010Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Описание метода потенциалов Математическая постановка задачи об оптимальных перевозках. Метод решения задачи об оптимальных перевозках средствами Ms Excel. Постановка параметрической транспортной задачи, ее математическое и компьютерное моделирование.
курсовая работа [802,5 K], добавлен 21.10.2014Экзаменационные задачи по математике: расчет процентной концентрации раствора; решение уравнений и неравенств; задачи по геометрии, планиметрии и стереометрии; определение тригонометрических функций, вероятности события; нахождение экстремумов функции.
задача [493,9 K], добавлен 28.12.2011Понятие волнового уравнения, описывающего различные виды колебаний. Рассмотрение явной разностной схемы "крест" для решения данной задачи. Нахождение решений на нулевом и первом слоях с помощью начальных условий. Виды и решения интегральных уравнений.
презентация [240,6 K], добавлен 18.04.2013Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011