- •1. Теория графов
- •1.1 Остовные деревья минимального веса.
- •Алгоритм Прим
- •Алгоритм Краскал
- •1.2 Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дийкстры
- •Алгоритм Дийкстры
- •Модифицированный алгоритм Дийкстры
- •1.3 Нахождение кратчайших цепей между всеми парами узлов в сети
- •Алгоритм Флойда (Floyd r. W.)
- •Модификация алгоритма Флойда
- •1.4 Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона
- •Алгоритм Форда-Фалкерсона
- •1.5 Обобщенные задачи о потоке
- •1.5.1 Построение потока в сети с двойным ограничением потока по дугам
- •1.5.2 Построение потока в сети с пропускными способностями узлов
- •1.5.3 Построение потока в сети с несколькими источниками-стоками
- •1.5.4 Построение потока в сети с неориентированными ребрами
- •1.6 Определение потока заданной величины минимальной стоимости. Алгоритмы Басакера-Гоуэна, Клейна
- •Алгоритм Басакера-Гоуэна (Basaker r.G., Gowen p.J)
- •Алгоритм Клейна (Klein m.)
- •2 Сетевое планирование
- •2.1 Построение сетевых моделей
- •2.2 Расчет и анализ сетевых моделей
- •Задача №1
- •Задача №2
- •I. Поиск критических путей
- •II. Поиск резервов работ
- •Правило №2.1
- •3 Линейное программирование
- •3.1 Примеры задач лп
- •3.2 Свойства решений задач линейного программирования
- •3.3 Двумерные задачи линейного программирования. Графический метод решения. Исследование на разрешимость
- •3.3.1 Построение области допустимых решений целевой функции f.
- •3.3.2 Построение прямой уровня
- •3.3.3 Максимизация целевой функции f
- •3.4 Симплекс-метод.
- •3.4.1 Построение начального опорного плана.
- •3.4.2 Симплексные таблицы
- •3.4.3 Примеры решения задач симплекс-методом
- •4. Теория двойственности в линейном программировании
- •4.1 Понятие двойственности. Построение пары взаимно двойственных задач
- •4.2 Теоремы двойственности и их экономическое содержание
- •4.3 Анализ решения задач линейного программирования
- •5. Транспортная задача
- •5.1 Постановка транспортной задачи в матричной форме. Построение исходного опорного плана
- •5.2 Метод потенциалов
- •5.3 Дополнительные условия в транспортных задачах.
- •6. Дискретное программирование.
- •6.1 Метод Гомори для решения задачи целочисленного линейного программирования
- •7. Динамическое программирование
- •7.1 Многошаговые процессы в динамических задачах
- •7.2 Принцип оптимальности и рекуррентные соотношения
- •7.3 Вычислительная схема динамического программирования
- •7.4 Оптимальное распределение средств на расширение производства
- •8. Матричные игры
- •8.1 Парные матричные игры с нулевой суммой
- •8.2 Платежная матрица
- •Нижняя и верхняя цена игры
- •8.3 Смешанные стратегии
- •8.3 Решение матричной игры сведением к задаче линейного программирования
- •8.4 Решение матричной игры графическим методом
- •8.5 Приближенный метод решения матричных игр
- •Практические работы Практическая работа №1 Построение остовного дерева графа. Нахождение найкратчайшего расстояния между заданными вершинами графа
- •Практическая работа №2 Нахождение наикратчайших расстояний между всеми парами вершин графа. Алгоритм Флойда.
- •Практическая работа №3
- •Практическая работа №4 Нахождение потока заданной величины минимальной стоимости. Алгоритм Басакера-Гоуэна
- •Практическая работа №7 Оптимизация проекта по времени.
- •Практическая работа №8
- •Практическая работа №9 Оптимизация целевой функции с помощью двухфазного симплекс метода.
- •Практическая работа №10 Решение двойственных задач. Экономическая интерпретация задач линейного программирования.
- •Практическая работа №11 Решение транспортных задач.
- •Практическая работа №12 Дополнительные условия в транспортных задачах
- •Практическая работа №13 Метод Гомори для решения задачи целочисленного линейного программирования.
- •Практическая работа №14
- •Практическая работа №15 Решение матричных игр в чистых стратегиях
- •Практическая работа №16 Графический метод решения матричных игр.
- •Каркас минимального веса. Метод р. Прима.
- •Кратчайшие пути
- •Лабораторная работа №2 Кратчайшее расстояния от заданной вершины до всех остальных вершин графа.
- •Алгоритм Дийкстры.
- •Пути в бесконтурном графе.
- •Лабораторная работа №3 Кратчайшие пути между всеми парами вершин графа.
- •Алгоритм Флойда.
- •Лабораторная работа №4 Построение потока максимальной мощности.
- •Потоки в сетях.
- •Метод построения максимального потока в сети.
- •Лабораторная работа №5 Симплекс метод
- •Лабораторная работа №6 Транспортная задача
- •Список литературы
Алгоритм Басакера-Гоуэна (Basaker r.G., Gowen p.J)
Шаг 0. Решение начинаем с нулевого потока . Полагаем .
Шаг 1. Строим граф модифицированных стоимостей нет ни одной цепи из s в t, то задача нахождения потока минимальной стоимости, имеющего заданную мощность, не имеет решения. В исходной сети G пропущен поток максимальной мощности минимальной стоимости. В противном случае находим кратчайшую цепь из s в t (роль длин дуг играют их модифицированные стоимости).
Шаг 3. В исходном графе определяем - путь P, соответствующий цепи P*. На прямых дугах пути P вычисляем:
на обратных:
.
Находим .
На прямых дугах пути P величину потока увеличиваем, а на обратных уменьшаем на .
Шаг 4 Полагаем .
Если , то переходим к шагу 1, если , то алгоритм свою работу закончил, в сети построен оптимальный поток.
Замечание. Для решения задачи о нахождении максимального потока максимальной стоимости достаточно в алгоритме Басакера-Гоуэна заменить на .
Пример. Построить поток заданной мощности =3 минимальной стоимости в сети (см. Рис. 1.24).
Итерация 1
Полагаем . Строим граф модифицированных стоимостей (см. Рис. 1.25).
Находим кратчайшую (наиболее дешевую) цепь P* из s в t:
P*: s b a t,
Длина цепи (модифицированная стоимость) равна 3.
Соответствующий ей (s, t) – путь
P: s b a t,
и .
Т.к. все дуги пути — прямые, то увеличивая пути P величину потока на 2, то получаем (см. Рис. 1.26)
Рис. 1.24
Рис. 1.25
Рис. 1.26
Пересчитываем .
Поскольку , то переходим к шагу 1.
Итерация 2
Стром граф модифицированных стоимостей (см. Рис. 1.27).
Рис. 1.27
Находим в графе модифицированных стоимостей кратчайшую цепь
P*: s a b t,
Соответствующий ей (s, t) – путь
P: s a b t.
На прямых дугах пути P вычисляем:
,
на обратных:
.
Находим .
Величину потока на прямых дугах (s, a), (b, t) увеличиваем, а на обратной (a, b) уменьшаем на 1.
Получаем (см. Рис. 1.28)
Рис. 1.28
Считаем .
Т.к. , то алгоритм свою работу закончил, в сети построен оптимальный поток.
Вычислим суммарную стоимость пропущенного потока:
S(f)=1*5+1*2+1*1+1*2+6*1=16.
Очевидно, что при достаточно больших значениях использование алгоритма Басакера-Гоуэна приводит к длительным вычислениям.
Следующий алгоритм, предложенный Клейном, позволяет эти вычисления сократить.
Алгоритм Клейна (Klein m.)
Шаг 0. Решение начинаем с любого потока f из источника в сток мощности . Это может быть сделано подбором или с помощью задачи о максимальном потоке (в котором надо проводить вычисления до тех пор, пока величина потока не станет равной ). Вычисляем стоимость пропущенного потока f по формуле:
Шаг 1. Строим граф модифицированных стоимостей .
Шаг 2. Находим в графе ориентированный цикл отрицательной длины . Если в графе модифицированных стоимостей нет ни одного цикла отрицательной длины, то задача решена: в сети построен поток минимальной стоимости мощности . В противном случае переходим к шагу 3.
Шаг 3. В исходной сети G определяем замкнутый путь P, соответствующий циклу P*. Прямыми дугами в этом цикле считаем дуги сонаправленные соответствующим дугам цикла P* в графе , обратными — дуги, имеющие противоположную ориентацию. На прямых дугах пути P вычисляем:
на обратных: .
Находим .
На прямых дугах пути P величину потока увеличиваем, а на обратных уменьшаем на .
Шаг 4. Пересчитываем и переходим к шагу 1.
Пример. Построить поток заданной мощности =5 минимальной стоимости в сети G (см. рис. 1.29):
В сети построен поток мощности =4. Пропускаем ещё одну единицу потока, получаем (см. рис. 1.30)
Итерация 1
Находим =1*3+2*3+2*3+3*2+8*2=37. Строим граф модифицированных стоимостей (см. рис. 1.31)
Находим цикл отрицательной длины P* (можно воспользоваться алгоритмом Флойда):
P*: b t c b,
Рис. 1.29
Рис. 1.30
Рис. 1.31
Длина цикла . Соответствующий ему путь в сети G: P: b t c b.
На прямых дугах пути P((b, t), (c, b)) вычисляем:
На обратной (t, c)
.
Находим .
Величину потока на прямых дугах увеличиваем, а на обратной — уменьшаем на 2. Получаем: (см. рис. 1.32)
Рис. 1.32
Находим стоимость нового потока:
.
Итерация 2
Строим граф модифицированных стоимостей (см. рис. 1.33).
Рис. 1.33
В построенном графе отсутствуют циклы отрицательной длины.
Упражнение: Доказать этот факт при помощи алгоритма Флойда.
Т.о., в данной сети построен оптимальный поток, его стоимость равна 27.
Очевидно, что оба рассмотренных алгоритма позволяют найти поток мощность , если это число не превышает максимальной мощности допустимых потоков. Менее очевидно, что эти алгоритмы позволяют найти оптимальный поток. Доказательство этого факта основано на следующей теореме, которая может рассматриваться как основная теорема в теории потоков минимальной стоимости.
Теорема. Поток величины оптимален тогда и только тогда, когда граф модифицированных стоимостей не содержит ориентированных циклов отрицательной длины.
Упражнения
Пусть — сеть, с заданными пропускными способностями , и стоимостями , дуг. Среди допустимых потоков заданной мощности найти поток минимальной стоимости . Решить эту задачу при помощи модификации алгоритма Басакера-Гоуэна.
Пусть задана сеть, в которой мощность максимального потока равна . Известно, что стоимость провоза единицы потока по дуге (x, y) равна d(x,y), а пропускная способность дуги равна c(x,y).
Пусть известно, что мощность максимального потока в сети должна быть равной , . Каким образом следует увеличить пропускные способности дуг, чтобы получить необходимый поток с минимальными затратами (то есть с минимальным увеличением стоимости потока)?
Пусть известно, что суммарные затраты на пропущенный в сети поток не должны превышать заданной величины S. Как следует увеличить пропускные способности дуг, чтобы в преобразованной сети можно было бы пропустить поток как можно большей мощности?
В задаче о потоке минимальной стоимости поток является оптимальным тогда и только тогда, когда в графе модифицированных стоимостей не существует отрицательных циклов. Объяснить, почему при поиске максимального потока минимальной стоимости, граф можно разбить на две части и в каждой из них отдельно искать отрицательные циклы.