Тема 5. Потоки в сетях

При изучении темы «Потоки в сетях» следует обратить внимание на то, что в отличие от предыдущей темы эти задачи в терминах математического программирования не являются булевыми. При использовании математического программирования нужно помнить, что в задачах оптимизации на сетях основным ограничением является уравнение материального баланса для каждого узла сети, которое требует равенства суммы входящих и суммы выходящих потоков. Это вытекает из закона сохранения материи и физического состояния реального объекта, моделируемого узлом сети.

Для усвоения раздела «Максимальный поток в сети» следует хорошо уяснить понятие материального потока (вещества, энергии, информации и т.п.) и то, что во взвешенном графе может быть несколько потоков одинаковой величины с различным распределением по дугам. Таким образом, максимальный поток – это один из потоков с максимальной величиной (безразлично, какой именно).

При изучении теоремы и алгоритма Форда-Фалкерсона нахождения максимального потока нужно шорошо усвоить понятия разреза, частичного потока, остаточной пропускной способности, расширяющего (аугментального) пути в графе. Алгоритм пометок Форда-Фалкерсона является одним из самых простых и с помощью расширяющих путей итеративно увеличивает поток в сети до полного её насыщения. Существуют алгоритм Диница и алгоритм Карзанова, более эффективные, чем алгоритм пометок Форда-Фалкерсона.

В постановке задачи о максимальном потоке в терминах математического программирования следует обратить внимание на то, что в качестве целевой функции можно взять сумму частичных потоков, проходящих через любой разрез сети. Если сеть имеет только один источник или только один сток, то удобно целевую функцию выражать именно через него.

При разработке электронного шаблона Excel для нахождения максимального потока следует помнить, что задание основного ограничения на баланс потоков в стандартной форме весьма затруднительно. В связи с этим рекомендуется использовать уравнение баланса в форме, приведённой в лекциях по курсу.

Нужно хорошо знать задачи организационного управления, приводящие к максимальному потоку:

• строительство сети автомобильных или железных дорог;
• строительство сети нефтепроводов и газопроводов;
• прокладка кабельных сетей;
• строительство линий электропередачи;
• и многие другие.

Во всех этих задачах требуется обеспечить максимальную пропускную способность транспортных, энергетических или информационных сетей.

Полезно также иметь представление о нестандартных задачах, сводящихся к максимальному потоку:

• поиск непересекающихся путей в графе;

• задача о множественном назначении;
• календарное планирование трудовых ресурсов.

Задача о потоке минимальной стоимости эквивалентна обобщённой транспортной и является наиболее общей. Большинство сетевых задач (транспортная, о назначении, минимальный и максимальный пути и другие) могут быть сформулированы в терминах задачи о потоке минимальной стоимости. Показательно, что после определения величины максимального потока в сети, как правило, решается задача о нахождения максимального потока минимальной стоимости, который и принимается за окончательное решение.

На сегодняшний день не существует устоявшегося эффективного специального алгоритма нахождения потока минимальной стоимости, поэтому применение математического программирования пока не имеет альтернативы.

Решение задачи о потоке минимальной стоимости в Excel аналогично максимальному потоку за исключением структуры целевой функции, при этом следует придерживаться рекомендаций, приведённых выше для задачи о максимальном потоке.

Нужно хорошо знать задачи организационного управления, приводящие к потоку минимальной стоимости:

• управление транспортными потоками в сетях автомобильных или железных дорог;
• управление транспортными потоками в сетях нефтепроводов и газопроводов;
• управление потоками информации в информационных сетях;
• управление потоками энергии в сетях электропередач;
• и многие другие.

Во всех этих задачах требуется обеспечить минимальную стоимость прохождения фиксированного потока в транспортных, энергетических или информационных сетях.

Полезно также иметь представление о нестандартных задачах, сводящихся к потоку минимальной стоимости:

• многопродуктовый поток минимальной стоимости;

• календарное планирование.

Контрольные вопросы для самопроверки:

1. Дайте определения терминов «сеть» и «поток».
2. Какие задачи организационного управления приводят к задаче нахождения максимального потока в сети?
3. Дайте содержательную (словесную) постановку задачи нахождения максимального потока в сети.
4. Почему в сети может существовать несколько максимальных потоков одинаковой величины и чем они отличаются друг от друга?
5. Сформулируйте теорему Форда-Фалкерсона и поясните её использование для нахождения максимального потока в сети.
6. Перечислите и поясните основные шаги алгоритма Форда-Фалкерсона нахождения максимального потока в сети.
7. Напишите математическую постановку задачи о нахождения максимального потока в терминах математического программирования.
8. Опишите структуру электронного шаблона Excel для нахождения максимального потока в сети.
9. Какие задачи организационного управления приводят к задаче нахождения в сети потока минимальной стоимости?
10. Дайте содержательную (словесную) постановку задачи нахождения в сети потока минимальной стоимости.
11. Что общего и в чём различия задач о максимальном потоке и потоке минимальной стоимости?
12. Напишите математическую постановку задачи о потоке минимальной стоимости в терминах математического программирования.
13. Опишите структуру электронного шаблона Excel для нахождения потока минимальной стоимости.
14. Дайте содержательную (словесную) постановку задачи нахождения максимального потока минимальной стоимости.
15. Опишите общую методику нахождения максимального потока минимальной стоимости.

Дата добавления: 2015-04-29