Тема 4. Кратчайшие пути в графах

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

Для решения сетевых задач в Excel следует по материалу лабораторной работы №1 уяснить различные способы представления графов:

• векторный;
• матричный;
• веторно-матричный,

а также структуру шаблона и сценария оптимизации для каждого представления в конкретной задаче.

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

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

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

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

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

Особое внимание нужно обратить на проблему связности остова (отсутствия циклов) и хорошо уяснить способы её преодоления:

1. Разрыв циклов;
2. Заполнение «нулевых» сечений.

При изучении раздела «Минимальный и максимальный пути в графе» следует обратить внимание на сходство этих задач. Различие состоит только в операциях минимизации и максимизации.

При использовании методов математического программирования нужно хорошо уяснить булеву постановку задачи для орграфа. При этом важно понять, что двоичные переменные, приписанные к дугам графа, показывают, входит (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 для решения задачи коммивояжёра в неорграфе.

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