6. Математический аппарат,
применяемый при курсовом проектировании

6.5. Динамическое программирование

К задачам динамического программирования относятся задачи, обладающие следующими свойствами:

1. задача может быть разбита на этапы (по времени, в пространстве, этапы технологического производства, реконструкции, строительства и пр.);
2. аддитивность решения и аддитивность критерия оптимальности, те. решение всей задачи получается путем суммирования результатов решения задач на отдельных этапах, а значение критерия оптимальности всей задачи получается путем суммирования значений частных критериев оптимальности на отдельных этапах;
3. регрессивность решения – процесс решения разворачивается от конца к началу.

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

В общем случае задача динамического программирования может быть сформулирована следующим образом. Имеется некоторая экономическая система, находящаяся в начальный момент времени Т₀ в состоянии S₀. Это состояние определяется n-мерным вектором параметров системы в заданный начальный момент времени. Такими параметрами могут быть сочетания показателей производственно-хозяйственной деятельности предприятия: объем реализуемой продукции, прибыль, производительность труда, стоимость основных производственных фондов, ассортимент выпускаемой продукции и пр.

В соответствии с планом развития за период времени T_k–T_j система должна быть переведена в некоторое конечное состояние S_k, определяемое соответствующими значениями составляющих вектора состояний в момент времени T_k. Переход может быть обеспечен за конечное число шагов, на каждом из которых система переводится в некоторое промежуточное состояние S_k. При этом необходимо обеспечить оптимум критерия, обеспечивающего качество управления.

Перевод системы из состояния в состояние характеризуется набором последовательных состояний S₀, S₁, ...,S_i, ..., S_k и называется траекторией системы. Этот перевод из состояния в состояние обеспечивается посредством ряда последовательных управляющих воздействий или управлений, которые будем обозначать через w_i.

Совокупность управлений w_i обозначим через W. Тогда можно сказать, что задача динамического программирования заключается в выборе оптимального управления W, последовательно переводящего систему из состояния в состояние, начиная из S₀ в состояние S_k, при условии, что критерий оптимальности F(W) принимает экстремальное значение.