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

До сих пор рассматривались такие задачи оптимизации, в которых принятие решения осуществлялось в один этап. Зависимость рассматриваемого этапа от прошлого и его влияние на будущее не учитывалось.

В реальных задачах управления приходится принимать и реализовывать решения по нескольким этапам. Такие задачи многоэтапной оптимизации называют задачами динамического программирования, в том числе:

- распределение ресурсов, например, ограниченного объема капиталовложений между возможными направлениями их использования по объему и времени;

- разработка правил управления запасами, устанавливающих момент пополнения и размер пополняемого запаса;

- выбор транспортных маршрутов или технологических способов изготовления изделий;

- разработка принципов календарного планирования производства.

Пример 7.1

Пусть установлены возможные варианты транспортной сети из маршрутов, соединяющих исходный пункт 1 с конечным пунктом 10. Все 10 пунктов можно отнести к пяти зонам (этапам). На линиях, соединяющих пункты, поставлено время проезда между соседними пунктами (рис. 8.1).

Рис. 7.1

Требуется выбрать путь от начального пункта до конечного пункта с минимальным временем.

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

Искомый путь может быть найден интуитивно, а затем его можно сравнить с полученным оптимальным решением.

В основе решения задач ДП лежит принцип оптимальности: на каждом этапе принимается такое решение, которое обеспечивает оптимальность с данного этапа до конца процесса, то есть на каждом этапе необходимо принимать решение, просматривая его последствия до самого конца. А так как последовательность решения следует просматривать до конца процесса, то варианты анализируют, начиная с конца процесса.

Допустим, мы оказались в зоне IV (пп. 8, 9), из которой надо продвинуться в зону V (п. 10) (табл. 8.1).

Таблица 7.1

Из пп. IV зоны	В п. 10 зоны V	min T IV – V

Таблица 7.2

Из пп. III зоны	Через пп. IV зоны	min T III – V
	7 + 1	5 + 4
	3 + 1	4 + 4
	7 + 1	1 + 4

Таблица 7.3

Из пп. II зоны	Через пп. Ш зоны	min T II – V
	10 + 8	12 + 4	–
	5 + 8	10 + 4	7 + 5
	–	15 + 4	13 + 5

Таблица 7.4

Из пп. I зоны	Через пп. II зоны	min T I – V
	2 + 16	5 + 12	1 + 18

Таким образом, следуя от конца маршрутов, мы сначала определили, через какой пункт двигаться при условии, чтобы оказаться в зоне III, затем при условии, чтобы оказаться в зоне II, и, наконец – в зоне I. Следовательно, на первом цикле решения определилось условно-оптимальное Решение. Во втором – следуя от начала к концу маршрута по табл. 8.1–8.4, где условно-оптимальные решения не затемнены, находим действительно оптимальное Решение:

из табл. 8.4: п.1®п.3;

из табл. 8.3: п.3®п.7;

из табл. 8.2: п.7®п.9;

из табл. 8.1: п.9®п.10.