Задача о кратчайшем маршруте
Рассмотрим задачу определения кратчайшего пути между двумя вершинами сети. Эта задача является частным случаем задачи об оптимальном потоке. Она охватывает широкий круг важных приложений моделей исследования операций (замена оборудования, календарное планирование и др.).
Пусть задана сеть
,
каждой дуге (ребру) которой соответствует
некоторое расстояние
.
Требуется найти кратчайший маршрут из
источника
в сток
.
Математическая постановка задачи имеет вид:
минимизировать
при ограничениях:
Приведем пример решения подобной задачи с помощью Microsoft Excel.
Пример 6
Транспортная система представлена схематически на Рис. 3.17. Расстояния между узлами сети указаны у соответствующих дуг (масштаб не соответствует реальным расстояниям). Требуется определить кратчайший (по расстоянию) маршрут между узлами 1 и 7.
Очевидно, задача сводится к определению минимума функции:
при ограничениях:
Смысл ограничений достаточно очевиден:
необходимо, чтобы из узла 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.
Контрольные вопросы к теме №3
Понятие о методах сетевого планирования и управления.
Метод PERT.
Метод CPM.
Понятие о сетевых графиках.
Правила построения сетевых графиков.
Расчет временных параметров сетевых графиков.
Оптимизация комплекса операций по времени.
Оптимизация комплекса операций по затратам.
Оптимизация потоков в сетях.
Тема 4. Методы теории игр в управлении Лекция 6. Информационные технологии теории игр
Основные понятия:
неопределенность; ситуация риска; количественная неопределенность; информационная неопределенность; стоимостная неопределенность; профессиональная неопределенность; ограничительная неопределенность; неопределенность внешней среды; конфликтные ситуации; теория игр; стратегия игры; парные игры; бескоалиационные игры; коалиационные игры; игры с нулевой суммой; игры с ненулевой суммой; матричные игры; биматричные игры; оптимальная стратегия игры; максиминная стратегия; минимаксная стратегия; игры с cедловой точкой; чистая цена игры; оптимальная чистая стратегия; сложная стратегия; игры с природой; риск в играх с природой; принцип недостаточного основания Лапласа; критерий Вальда; критерий Сэвиджа; критерий Гурвица.