Задача о кратчайшем маршруте
Задача о кратчайшем маршруте
Рассмотрим задачу определения кратчайшего пути между двумя вершинами сети. Эта задача является частным случаем задачи об оптимальном потоке. Она охватывает широкий круг важных приложений моделей исследования операций (замена оборудования, календарное планирование и др.).
Пусть задана сеть 
, каждой дуге (ребру) которой соответствует некоторое расстояние 
. Требуется найти кратчайший маршрут из источника 
в сток 
.
Математическая постановка задачи имеет вид: минимизировать
при ограничениях:
 |
Рекомендуемые материалы
Приведем пример решения подобной задачи с помощью Microsoft Excel.
Пример 6.
Транспортная система представлена схематически на Рис. 3.17. Расстояния между узлами сети указаны у соответствующих дуг (масштаб не соответствует реальным расстояниям). Требуется определить кратчайший (по расстоянию) маршрут между узлами 1 и 7.
Рис. 3.17. Схема транспортной системы примера 6.
Очевидно, задача сводится к определению минимума функции
при ограничениях
.
Смысл ограничений достаточно очевиден: необходимо, чтобы из узла 1 (источник) перевозимый продукт был отправлен (
); в узел 7 (сток или приемник) продукт был доставлен (
); полный поток через все промежуточные пункты должен быть равен нулю, так как предполагается, что продукт не остается ни в одном из них. Введем данные на рабочий лист в соответствии с Рис. 3.18.
Рис. 3.18. Форма для решения примера 6.
Отведем под расчетные значения переменных 
ячейки A6:K6. Введем следующие функции для ограничений и целевую функцию
| Ячейка | Формула |
| A8 | =A6+B6 |
| A9 | =A6+C6-D6-E6 |
| A10 | =B6-C6-F6-G6 |
| A11 | =D6+F6-H6-I6 |
| A12 | =G6+H6-J6 |
| A13 | =J6-K6 |
| A14 | =E6+I6+K6 |
| E13 | =СУММПРОИЗВ(A4:K4;A6:K6) |
В окне диалога Поиска решения введем следующие ограничения:
| $A$8=1 | $A$10=0 | $A$12=0 | $A$4=1 |
| $A$9=0 | $A$11=0 | $A$13=0 | $A$6:$K$6=двоичное |
После запуска Поиска решения получим ответ:
;
данному значению целевой функции, т.е. кратчайшему расстоянию между пунктами 1 и 7 соответствует маршрут (1,3) – (3,4) – (4,7), на что указывает отличие от нуля лишь переменных X13, X34, X47.
Контрольные вопросы к теме:
1. Понятие о методах сетевого планирования и управления
2. Метод PERT
3. Метод CPM
Люди также интересуются этой лекцией: 9 Место БИС с программируемой структурой.
4. Понятие о сетевых графиках
5. Правила построения сетевых графиков
6. Расчет временных параметров сетевых графиков
7. Оптимизация комплекса операций по времени
8. Оптимизация комплекса операций по затратам
9. Оптимизация потоков в сетях
