- •1. Введение в исо. Предмет и история исо. Основные этапы и принципы операционного исследования. Постановка задач исо.
- •2. Постановка многокритериальной задачи.
- •3. Неопределенность природы и действий противника: принцип гарантированного результата
- •4. Основные понятия, принципы и классификация игр.
- •5. Решение матричных игр в смешанных стратегиях.
- •6. Решение игры 22
- •7. Упрощение игр
- •8. Игры с природой. Критерий Байеса
- •9. Бескоалиционные игры. Определение бескоалиционной игры. Равновесные ситуации и стратегии.
- •10. Теорема Нэша для бескоалиционных игр.
- •11. Методы анализа сетей. Потоки на сетях.
- •12. Теорема Форда-Фалкерсона
- •13. Комбинированные приложения з-чи о максимальном потоке. Простейшая з-ча о назначении.
- •I. Предварительный этап.
- •II. Этап расстановки пометок.
- •III. Этап переброски.
- •14. Классическая задача о назначении.
- •I этап. Приведение матрицы.
- •II этап. Выбор назначений.
- •III этап. Дополнительное приведение матрицы.
- •15. Основные этапы и понятия сетевого планирования и управления(спу)
- •17. Задача оптимального по времени распределения ограниченных ресурсов на сетевых графиках
- •19. Общая задача теории расписаний.
12. Теорема Форда-Фалкерсона
Основная теорема Форда-Фалкерсона: Для любой сети с истоком и стоком величина потока из истока в сток пропускной способности разреза раздел. исток от стока .
Док-во: Пусть - величина максимального потока по сети из истока в сток . Покажем, что существует разрез , для которого и построим некоторое мн-во по следующим правилам:
1) ;
2) если , дуга ; если , то ;
3) если , дуга ; если , то .
Докажем, что мн-во определяет разрез. Предположим обратное. Тогда вершина и пусть существует путь из в по вершинам мн-ва , определим величину и определим величину .
Выберем . По найденному пути изменим дуговые потоки следующим образом: на прямых дугах поток увеличим на , а на обратных – уменьшим на , при этом условия (3) не нарушится, а величина потока увеличится, что противоречит условию теоремы. Это означает, что мн-во построено по правилам 1-3 определяет разрез . По построению в разрез входят прямые дуги , для которых и входят обратные дуги . Для которых . Поэтому суммируя данное равенство по дугам разреза .
Опр. Будем говорить, сто путь из в увеличивает поток по сети, если на всех прямых дугах , а на всех обратных дугах .
Следствие: Поток является максимальным, если не существует путей из в увеличивающих поток.
Алгоритм расстановки пометок для построения максимального потока на сети.
1 этап (Предварительный): построить начальный поток , удовлетворяющий условиям 2 и 3. Таким потоком явл., например, нулевой поток.
2 этап (Расстановки пометок): он позволяет либо найти путь увеличивающий поток, либо доказывает, что ранее построенный поток максимальный.
На этом этапе каждая вершина находится в одном из трех состояний:
1. вершина не помечена;
2. помечена, но не просмотрена;
3. помечена и просмотрена.
Пометка вершины состоит из двух частей , здесь - номер вершины, из которой можно послать дополнительный поток в (т.е. вершина помечена из вершины );
«+» - ставится, если вершина помечена из вершины по прямой дуге;
«-» - ставится, если по обратной;
- максимальная величина дополнительного потока, который можно послать из истока в вершину не нарушая пропускных способностей дуг.
В начале все вершины не помечены.
1) вершина помечается , но не просмотрена;
2) выбираем любую помеченную, но не просмотренную вершину , если таковых нет, то переходим к 5);
3) для всех непомеченных , для которых к вершине присваиваем пометку , где для всех непомеченных , для которых к вершине приписываем пометку , .
После выполнения шага 3) вершины помечены, но не просмотрены, а вершины - помечены и просмотрены.
4) если помечен сток , то переходим к 3 этапу. Если на шаге 3) появились новые помеченные вершины, то мы возвращаемся к шагу 2);
5) если не помечен и других пометок расставить нельзя, при этом минимальный разрез, где - мн-во помеченных вершин, а - мн-во непомеченных вершин.
3 этап (Изменение потока по пути найденному в этапе 2):
1) положить ;
2) если у вершины потока , то положить . Если у вершины потока , то положить .
3) положить ;
4) если , то все пометки стираются и осуществляется переход к этапу 2, иначе возвращаются к шагу 2.