Выбор оптимального маршрута

Задача № 2.2

Определить оптимальный план маршрута перевозок грузов от А до В, при минимальных затратах. На рис. 16 указаны номера пунктов (в кругах) и стоимость перевозок между пунктами.

Рис. 16 Схема маршрутов из пункта А в пункт В

Данная задача относится к разделу динамического программирования.

Для решения задачи определим стратегию:

– процесс решения задачи построим с конца, то есть с пункта В;

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

Отобразим план решения задачи с учетом стратегии:

Шаги 1 2 3 4 5 6 7

А 1 2 3 5 6 4 В

Рис. 17 Определение шагов оптимизации

Каждый шаг определен с учетом прохождения не более путей к пункту В. Например, к шагу 7 относится пункт 4, тат как только из него можно попасть в точку В, пройдя не более одного пути. К шагу 6 отнесем пункты, из которых можно попасть в пункт В, пройдя не более двух путей. По этому показателю подходит только один пункт 6 и т.д.

Как отмечалось выше, процесс решения строим с конца. Начнем с 7 шага. Количественную и качественную оценку решения запишем в следующем виде:

Так как на этом шаге возможно только одно решение, то оно и будет оптимальным, поэтому запишем в рамке окончательное решение на этом шаге (введем «*»):

Значение Z определяет количественную оценку решения 7-го шага и 4-го пункта и равно 10. Параметр U указывает качественную сторону решения на этом шаге, т.е. управление. В нашем случае направление в пункт В.

Шаг 6. На этом шаге задействован пункт 6. Как следует из схемы, возможно два варианта решения (выход по двум путям), тогда решение запишется в следующем виде (по формуле Беллмана):

Шаг 5.

Шаг 4.

Шаг 3.

Шаг 2.

Шаг 1.

Решение задача Z _min = 10. Для определения маршрута движения, необходимо воспользоваться управлением U. Выпишем управления соответствующие оптимальному варианту решения:

Откуда следует решение (А, 1, 3, 6, В). Проверкой убеждаемся правильностью выбора маршрута движения- 2+3+4+1=10.

Ответ: Z _min =10; (А, 1, 3, 6, В).

Дата добавления: 2014-01-07