III Практическое применение динамического программирования

Задача о выборе наиболее экономного маршрута доставки груза.

На данной сети дорог имеется несколько маршрутов, по которым можно доставлять груз из пункта 1 в пункт 10 (рис. 1). Известны стоимости перевозки единицы груза между отдельными промежуточными пунктами сети (они проставлены на сети у соответствующих ребер). Требуется в системе дорог выбрать маршрут доставки груза из пункта 1 в пункт 10, которому соответствует наименьшие затраты.

рис. 1

Для решения задачи методом динамического программирования разобьем все пункты сети на группы (табл. 1).

Таблица 1

К группе I отнесем пункт 1, к группе II - пункты, в которые можно попасть из пункта 1 (таковыми будут 2; 3; 4), к группе III отнесем пункты, в которые можно попасть непосредственно из любого пункта группы II (таковыми будут 5; 6; 7), и т.д. в результате движение транспорта с грузом из пункта 1 в пункт 10 примет поэтапный характер: на первом этапе транспорт перемещается из пункта 1 в какой-то пункт группы II, на втором этапе - из пункта группы II в пункт группы III и т.д. Вместе с этим и процесс нахождения наиболее экономного маршрута из пункта 1 в пункт 10 распадается на шаги. На каждом шаге надо так выбрать маршрут следования груза в пункт соседней группы, чтобы доставка груза по всему маршруту была сопряжена с минимальными затратами. Избранный нами подход к решению задачи учитывает особенности сети, изображенной на рис. 1: после разбиения на группы пункты, оказавшиеся в одной и той же группе, дорогами не соединены.

Применительно к рассматриваемой задаче принцип оптимальности можно сформулировать так: оптимальный маршрут доставки груза из пункта 1 в пункт 10 обладает тем свойством, что, каков бы ни был маршрут достижения некоторого промежуточного пункта сети, дальнейший маршрут следования должен совпадать с оптимальным маршрутом для части маршрута, начинающейся с этого пункта.

В данном случае процесс состоит из четырех шагов (рис. 2). Будем оптимизировать каждый шаг, начиная с последнего - четвертого. На этом шаге в пункт 10 можно попасть из пункта 8 или 9, причем из каждого пункта только одним способом. Если предпоследний, третий, шаг привел груз в пункт 8, то дальше следует двигаться по маршруту 8 - 10, и затраты на перевозку единицы груза будут равны единице; если же в пункт 9 - то следует двигаться по маршруту 9 - 10, на котором затраты составят 4 единицы. Условное оптимальное решение помечаем на сети стрелкой, выходящей из соответствующего кружка, а величину затрат записываем в нижней половинке кружка.

1 шаг 2 шаг 3 шаг 4 шаг

рис.2

Переходим к оптимизации предпоследнего, третьего, шага. Для этого рассмотрим все возможные исходы предшествующего, второго, шага. После этого шага груз может оказаться только в одном из пунктов - 5,6,7. Для каждого пункта выбираем условное оптимальное решение - оптимальный маршрут в пункт 10 и соответствующие минимальные затраты. Так, если груз оказался в пункте, 5, то далее можно следовать либо через пункт 8, либо через пункт 9. В первом случаи затраты равны 7+1=8 единицам, во втором - 5+4=9 единицам. Значит, условный оптимальный маршрут из пункта 5 в пункт 10 проходит через пункт 8, а условные минимальные затраты составляют 8 единиц. На ребре 5 - 8 сети ставим стрелку, а в кружке 5 записываем минимальные затраты: 8=7+1. ребро 5 - 9 остается без стрелки. Аналогично для пункта 6 находим условно-оптимальный маршрут 6 - 8 - 10 с затратами в 4 единицы; для пункта 7 - условно-оптимальный маршрут 7 - 9 - 10 с затратами в 5 единиц.

Далее оптимизируем путь доставки груза на втором шаге процесса. Для этого рассматриваем все возможные исходы первого шага. После первого шага груз мог оказаться только в одном из пунктов: 2, 3 или 4. При нахождении условного оптимального решения в каждом из этих пунктов надо просмотреть все возможные маршруту их этого пункта и для каждого из них найти сумму затрат на этом шаге и условных минимальных затрат на оптимальном продолжении маршрута, уже построенном для следующего пункта. Этого требует принцип оптимальности. Из всех возможных маршрутов выбирается тот, для которого эта сумма меньше (если суммы равны, выбирается любой маршрут). Для пункта 2 оптимальным будет маршрут 2 - 6 - 8 - 10 с затратами 12+4=16 единиц; для пункта 3 - маршрут 3 - 7 - 9 - 10 с затратами 7+5=12 единиц; для пункта 4 - маршрут 4 - 7 - 9 - 10 с затратами 13+5=18 единиц.

Оптимизируем, наконец, первый шаг. Для выбора условного оптимального решения рассматриваем три возможных маршрута: через пункты 2, 3 или 4. Устанавливаем, что наивыгоднейшим будет маршрут 1 - 3 с затратами в 17 единиц. Итак, этап условной оптимизации закончен, и остается пройти процесс в направлении от пункта 1 к пункту 10 и прочитать оптимальный маршрут: 1 - 3 - 7 - 9 - 10.

Заметим, что на первом этапе нами выбран маршрут 1- 3 доставки груза, по которому затраты в 2,5 раза превышают затраты на маршруте 1 - 2 и в 5 раз на маршруте 1 - 4. Оказалось, что с точки зрения всего четырехэтапного маршрута, а не одного первого этапа, следует пойти на «жертву» на первом этапе с тем, чтобы минимизировать общие затраты на всем четырехэтапном маршруте. Это иллюстрирует одну из главных особенностей метода: выбирать решение на каждом шаге, руководствуясь не выгодой, получаемой на данном шаге, а общей выгодой, получаемой по окончании всего процесса.

Примененный метод рассуждения не только позволил найти оптимальный маршрут доставки груза из пункта 1 в пункт 10, но и всю структуру оптимальных маршрутов относительно пункта 10 для данной сети дорог. Например, наиболее экономный маршрут доставки груза из пункта 4 в пункт 10 пройдет через пункты 7 и 9. Этот факт для практических нужд часто более ценен, чем нахождение только одного оптимального маршрута (рис. 3). (4)

рис. 3