7.2. Методика оптимального решения задачи
Методику и порядок решения задачи на оптимальность методом динамического программирования рассмотрим на конкретном примере.
Пример 7.1. На рис. 7.1 показана модель участка транспортной сети и дороги, соединяющие начальный пункт 1 с конечным пунктом 12. Указаны
также расстояния между пунктами в километрах. Условно пункты транспортной сети разбиты на 6 этапов.
Требуется выбрать маршруты движения от пункта 1 до пункта 12 наименьшей протяженности.
Большинство задач динамического программирования решаются с помощью функциональных уравнений, а также используется табличный способ.
Для рассматриваемой задачи аналитическая модель (функциональное уравнение) имеет следующий вид:
,
где
-
расстояние между пунктами i
и j;
fj
– минимальное
расстояние передвижения от пункта j
к конечному пункту 12 по допустимым
маршрутам при использовании оптимальной
стратегии.
Критерием оптимальности является минимальное расстояние в км при движении между пунктами 1 и 12.
Табличный способ решения
Согласно алгоритму метода динамического программирования анализ вариантов начинается с конца процесса. Вначале определим минимальные расстояния от пунктов 10 и 11 до конечного пункта 12 (V этап). Минимальное расстояние определим с помощью расчетных таблиц. Так, из табл. 7.1 следует, что на V этапе никаких комбинаций нет, из пунктов 10 и 11 в пункт 12 имеется только по одному пути, соответственно 12 и 10 км. На IV этапе выбрать самый короткий путь из пунктов 8 и 9 через пункты V этапа в конечный пункт 12.
Возможные варианты представлены в табл. 7.2. Для перемещения из пункта 8 в пункт 10 необходимо пройти 9 км, а из пункта 10 в пункт 12 (см. табл. 7.1) – 12 км, общая длина пути составит 21 км. Если этот путь будет проходить через пункт 11, то его длина составит 16 км. Из двух возможных комбинаций выбираем ту, которая соответствует минимальному расстоянию – 16 км, т. е. путь должен пройти через пункт 11. Аналогично находим расстояние перемещения из пункта 9 IV этапа через пункты V этапа в конечный пункт 12. Рациональным при этом оказался путь через пункт 11длиной 14 км. Это значение проставляем в столбце min Liv-vi, а клетки таблицы с нерациональными расстояниями зачеркиваем. Таким образом, рассматриваем варианты перемещения из пунктов III этапа в пункт 12 через пункты IV этапа (табл. 7.3), а из пунктов II этапа через пункты III этапа в конечный пункт 12 (табл. 7.4). И наконец, расстояния перемещения из начального пункта 1 через пункты 2,3 и 4 II этапа представлены в табл. 7.5.
Таким образом, следуя от конца маршрута, мы вначале определили, через какой пункт рационально двигаться, чтобы оказаться в пунктах IV этапа, затем III этапа и так до пункта 1. Следовательно, получено условное оптимальное решение задачи. После этого, следуя от начала маршрута к концу, используя данные табл. 7.1-7.5, в которых условные оптимальные решения остались незачеркнутыми, находим, действительно, оптимальное решение. Из табл. 7.5 видно, что необходимо двигаться из пункта 1 в пункт 3. Из табл. 7.4 следует, что
Таблица 7.1