- •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 Транспортная задача
- •Список литературы
Алгоритм Форда-Фалкерсона
Шаг 0. Пропускаем по сети некоторый допустимый поток (возможно нулевой). В процессе работы алгоритма (на каждом этапе) каждая вершина относится к одному из трех множеств:
непомеченные вершины,
помеченные, но не просмотренные, (окрашенные).
просмотренные (окрашенные).
Шаг 1. Пометим вершину S меткой (S+, ). Остальные вершины не помечены, S помеченная, но не просмотрена.
Шаг 2. Пусть — некоторая помеченная, но не просмотренная вершина с пометкой. Рассмотрим все соседние с непомеченные вершины. Для каждой из таких вершин u возможны следующие ситуации:
и , тогда вершина u получает метку ( .
и , тогда u получает метку .
В обоих случаях a) и b) помечаем вершину u меткой и вносим в множество помеченных, но не просмотренных вершин.
Если и или и , то u не помечается.
Когда все соседние с вершины проанализированы, переходит в множество просмотренных вершин. Окрашиваем вершину .
Шаг 3. Повторяем шаг 2 (т.е. расширяем просмотренное множество) до тех пор, пока не возникнет одна из следующих ситуаций:
Все вершины графа разбиты на два подмножества:
просмотренные (окрашенные);
непомеченные вершины, включающие в себя и вершину t.
Тогда в сети построен максимальный поток мощности V и минимальный разрез (X, X*), где X – окрашенные вершины.
Если вершина T получила метку, то в сети существует увеличивающий путь s t, который можно определить, идя из t обратно назад к s. Т.е. если метка у t была , то соединяем t с ν1 и т.д. Для найденного пути определяем величину увеличения мощности потока. На всех прямых дугах найденного пути изменяем f на (+ ), а на всех обратных дугах на (- ).
Мощность потока увеличилась на , т.е. V=V+ .
Переходим опять к шагу 1.
При этом множество X окрашенных вершин задает разрез (X, X*) пропускная способность которого равна мощности потока.
Пример. Для сети с заданными пропускными способностями дуг (рис. 1.17) необходимо построить поток максимальной мощности и указать разрез (X, X*) для которого M(f)=C(X, X*).
Решение На первом шаге помечается узел S (S+, ).
Шаг 1. Рассмотрим узлы, соседние с S.
Узел a помечается меткой (S+,3), т.к. (s, a) – дуга, f(s, a)=2<c(s, a)=5 и min( , 5-2)=3.
Узел b помечается меткой (S+,1), т.к. (s, b) – дуга, f(s, b)=3<c(s, b)=4 и min( , 4-3)=1.
Узел d не помечается, т.к. (s, d) – дуга и f(s, d)=4=c(c, d). Данный узел отнесем к множеству просмотренных узлов (рис. 1.18).
Рис. 1.17
(s+,)
Рис. 1.18
Шаг 2. Рассмотрим непомеченный узел t, соседний с помеченным и не просмотренным узлом a. Узел t не помечается, т.к. (a, t) – дуга и f(a, t)=2=c(a,t). Узел a после этого отнесем к множеству просмотренных узлов
Шаг 3. Рассмотрим непомеченные узлы, соседние с узлом b. Узел t не помечается, т.к. f(b, t) = 4 = c(b,t). Узел d получает пометку (b-, 1), т.к (d, b) – дуга и f(d, b)=1>0 и min( =1, f(d, b)=1). Узел b переходит к множеству просмотренных узлов (рис. 1.19).
Рис. 1.19
Шаг 4. Узел t получает метку (d+, 1), поскольку является соседним с помеченным и не просмотренным узлом d, (d, t) – дуга, и f(d, t) = 3< c(d, t) = 5 и = 1= min(1, 5-3). Определим путь P, увеличивающий поток.
Т.к. xt=d+, xd=b-, xb=s+, то P(s, b, d, t).
На прямых дугах (s, b) и (d, t) этого пути увеличиваем поток на =1, а на обратной дуге (d, b) уменьшаем на 1. Т.о. получается новый поток, больший исходного (рис. 1.20)
Рис. 1.20
Необходимо снова увеличить поток.
Пометим узел S(s+, ). Из узлов, соседних с s можно пометить лишь узел a(s+,3). Узел s переходит в множество просмотренных узлов.
Рассмотрим непомеченные узлы, соседние с узлом a.
Узел t не помечается, т.к. (a, t) – дуга и f(a, t)=2=c(a, t).
Узел b не помечается, т.к. (b, a) – дуга и f(b, a)=0.
Узел a переходит в множество просмотренных узлов.
Поскольку в сети нет помеченных и не просмотренных узлов, то полученный поток является максимальным.
Определим минимальный разрез. К множеству X относятся все помеченные узлы: X = {s, a}, к = {b, d, t}. В разрез входят дуги, идущие из узлов множества X в узлы множества , т.е. (s, b), (s, d), (a, t) (рис. 1.21).
Величина потока V=10 равна суммарной пропускной способности дуг разреза.
Рис. 1.21