6.3 Модели динамического программирования

Их применение связано в первую очередь с анализом так называемых многошаговых процессов принятия решений. Процесс является одношаговым, если, например, разработана схема оптимального пути из пункта А в пункт В. Если же вначале известно, как проехать из А в первый промежуточный пункт, а там станет известно, как добраться до 2-го промежуточного пункта и т.д., то весь путь будет известен только по достижении пункта В и процесс принятия решений по поводу оптимального пути из А в В станет уже многошаговым. Таким образом, динамическое программирование - это метод оптимизации, приспособленный к операциям в которых процесс принятия решений может быть разбит на отдельные этапы (шаги). Как раздел математического программирования динамическое программирование начало развиваться в 50-х годах XX века благодаря работам Р.Белмана и его сотрудников. Впервые этим методом решались задачи оптимального управления запасами, затем класс задач значительно расширился (многошаговые детерминированные модели задач оптимального распределения ресурсов; расчет развития на перспективу производственной базы стройиндустрии; установление оптимальных режимов замены изношенного оборудования, производства и хранения продукции во времени, при меняющемся спросе на нее, рациональная загрузка транспортных средств, оптимальное распределение капиталовложений и др.).

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

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

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

Сущность метода динамического программирования описывается так называемым динамическим рекурентным соотношением

(6.20)

где f_n(s) - стоимость, отвечающая стратегии минимальных затрат для пути из состояния s до конечного состояния системы, если остаток пути состоит из n шагов;

J_n(s) - решение, позволяющее достичь f_n(s);

c_sj - стоимость перевода исследуемой системы из состояния s в состояние j.

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

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

В рассматриваемом примере ответ имеет вид: 1 → 4 → 6 → 7, при этом время дооборудования этого маршрута составит 12 дней.

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

Рисунок 29 - Дорожная сеть, используемая при перевозке строительных грузов из пункта 1 в пункт 7

Таблица 15 – Исходные данные к задаче динамического программирования

Исходные данные
Сij	J	Cij	s	J
1	2	5	4	5	7
	3	10		6	1
	4	7
2	5	7	5	7	1
	6	5
3	5	3	6	7	4
	6	4

Таблица 16 – Расчёт модели динамического программирования