Файл: Руководство по изучению ОУ.doc

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

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

• календарное планирование производства;

• планирование коллективной работы;

• задача о разбиении;

• и другие.

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

При изучении раздела «Задача коммивояжёра» следует обратить внимание на комбинаторный характер этой задачи, который из-за огромных вычислительных затрат делает её одной из «труднорешаемых».

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

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

1. Разрыв подциклов;

2. Заполнение «нулевых» сечений.

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

• составление расписаний.

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

1. Дайте определение термина «минимальный остов графа».

2. Какие задачи организационного управления приводят к задаче нахождения минимального остова графа?

3. Дайте содержательную (словесную) постановку задачи нахождения минимального остова графа.

4. Перечислите и поясните основные шаги алгоритма Прима поиска минимального остова графа.

5. Напишите математическую постановку задачи о минимальном остове графа в терминах булева программирования.

6. Какую роль играют булевы переменные в задаче о минимальном остове графа?

7. Дайте сравнительную характеристику известных Вам способов представления взвешенных графов в Excel.

8. Опишите структуру электронного шаблона Excel для нахождения минимального остова графа.

9. Какие задачи организационного управления приводят к задаче нахождения минимального и максимального путей в графе?

10. Дайте содержательную (словесную) постановку задачи нахождения минимального и максимального путей в графе.

11. Перечислите и поясните основные шаги алгоритма Дейкстры поиска минимального пути в графе.

12. Перечислите и поясните основные шаги алгоритма поиска максимального пути в графе.

13. Напишите математическую постановку задачи о минимальном и максимальном пути в терминах булева программирования.

14. Какую роль играют булевы переменные в задаче о минимальном и максимальном путях в графе?

15. Опишите структуру электронного шаблона Excel для нахождения минимального и максимального путей в графе.

16. Какие задачи и какими методами решает сетевое планирование и управление (СПУ)?

17. Дайте содержательную (словесную) постановку задачи коммивояжёра.

18. Какие задачи организационного управления приводят к задаче коммивояжёра?

19. Напишите математическую постановку задачи коммивояжёра в терминах булева программирования для орграфа и неорграфа.

20. Опишите структуру электронного шаблона Excel для решения задачи коммивояжёра в орграфе.

21. Опишите структуру электронного шаблона Excel для решения задачи коммивояжёра в неорграфе.

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

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

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

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

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

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

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

• строительство сети автомобильных или железных дорог;

• строительство сети нефтепроводов и газопроводов;

• прокладка кабельных сетей;

• строительство линий электропередачи;

• и многие другие.

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

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

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

• задача о множественном назначении;

• календарное планирование трудовых ресурсов.

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

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

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

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

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

• управление транспортными потоками в сетях нефтепроводов и газопроводов;

• управление потоками информации в информационных сетях;

• управление потоками энергии в сетях электропередач;

• и многие другие.

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

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

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

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

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

1. Дайте определения терминов «сеть» и «поток».

2. Какие задачи организационного управления приводят к задаче нахождения максимального потока в сети?

3. Дайте содержательную (словесную) постановку задачи нахождения максимального потока в сети.

4. Почему в сети может существовать несколько максимальных потоков одинаковой величины и чем они отличаются друг от друга?

5. Сформулируйте теорему Форда-Фалкерсона и поясните её использование для нахождения максимального потока в сети.

6. Перечислите и поясните основные шаги алгоритма Форда-Фалкерсона нахождения максимального потока в сети.

7. Напишите математическую постановку задачи о нахождения максимального потока в терминах математического программирования.

8. Опишите структуру электронного шаблона Excel для нахождения максимального потока в сети.

9. Какие задачи организационного управления приводят к задаче нахождения в сети потока минимальной стоимости?

10. Дайте содержательную (словесную) постановку задачи нахождения в сети потока минимальной стоимости.

11. Что общего и в чём различия задач о максимальном потоке и потоке минимальной стоимости?

12. Напишите математическую постановку задачи о потоке минимальной стоимости в терминах математического программирования.

13. Опишите структуру электронного шаблона Excel для нахождения потока минимальной стоимости.

14. Дайте содержательную (словесную) постановку задачи нахождения максимального потока минимальной стоимости.

15. Опишите общую методику нахождения максимального потока минимальной стоимости.