<<
>>

Задача о кратчайшем маршруте

Рассмотрим задачу определения кратчайшего пути между двумя вершинами сети. Эта задача является частным случаем задачи об оптимальном потоке. Она охватывает широкий круг важных приложений моделей исследования операций (замена оборудования, календарное планирование и др.).

Пусть задана сеть , каждой дуге (ребру) которой соответствует некоторое расстояние . Требуется найти кратчайший маршрут из источника в сток .

Математическая постановка задачи имеет вид: минимизировать

при ограничениях:

Приведем пример решения подобной задачи с помощью 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

4. Понятие о сетевых графиках

5. Правила построения сетевых графиков

6. Расчет временных параметров сетевых графиков

7. Оптимизация комплекса операций по времени

8. Оптимизация комплекса операций по затратам

9. Оптимизация потоков в сетях

<< | >>
Источник: Теория принятия решений. Учебный курс. 2003

Еще по теме Задача о кратчайшем маршруте:

  1. 2.2. Разработка общей модели функционирования распределительной сети «Нефтебаза - АЗС»
  2. 2.2.3 Логистический процесс на складе
  3. 2.2.3 Логистический процесс на складе
  4. УКАЗАНИЯ СТАВКИ ГИТЛЕРА О ВЕДЕНИИ ВОЙНЫОТ 9 ОКТЯБРЯ 1939 г.
  5. § 4. РЕГУЛИРОВАНИЕ И УПРАВЛЕНИЕ. ТИПЫ УПРАВЛЕНИЯ
  6. 1. Боръба партии и Советского правительства за ликвидацию последствий неурожая в Поволжье и первые итоги восстановления сельского хозяйства к концу 1921 г. 
  7. ПолковникШпион в небеюстицииИ. РУБИНШТЕЙН
  8. Минимизация сети
  9. История и современное применение бережливого производство
  10. 18. Выход с территории противника