Динамическое программирование (планирование)

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

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

Имеется некоторая управляемая операция (целенаправленное действие), распадающаяся (естественно или искусственно) на m шагов – этапов. На каждом шаге осуществляется распределение и перераспределение участвующих в операции с целью улучшения ее результата в целом. Эти распределения в динамическом программировании называются управлениями операцией и обозначаются буквой U. Эффективность операции в целом оценивается тем же показателем, что и эффективность ее управления W (U).

W = W(U) = W(U1, U2, ..., Um).

Управление, при котором показатель W достигает максимума, называется оптимальным управлением. Оптимальное управление обозначается буквой U.

Оптимальное управление многошаговым процессом состоит из совокупности оптимальных шаговых управлений:

U = (U1, U2, ..., Um).

Задача динамического программирования – определить оптимальное управление на каждом шаге Ui (i = 1, 2, …, m) и, тем самым, оптимальное управление всей операцией в целом.

В большинстве практических задач принимается, что показатель эффективности операции W в целом представляет собой сумму эффективности действий на всех этапах (шагах) операции:

W =  i,

где i – эффективность операции на i-м шаге.

При этом в случае оптимального управления

W = max i

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

• 
  Оптимизация производится методом последовательных приближений (итераций) в два круга; в начале от последнего шага операции к первому, а затем наоборот от первого к последнему;
  
• 
  На первом круге, идя от последующих шагов к предыдущим, находится так называемое условное оптимальное управление;
  
• 
  Условное оптимальное управление выбирается таким, чтобы все предыдущие шаги обеспечивали максимальную эффективность последующего шага, иными словами, на каждом шаге имеется такое управление, которое обеспечивает оптимальное продолжение операции; этот принцип выбора управления называется принципом оптимальности;
  
• 
  Так продолжается до первого шага, но поскольку первый шаг не имеет предыдущего, то полученное для него условное оптимальное управление теряет свой условный характер и становится просто оптимальным управлением, которое мы ищем;
  
• 
  Второй круг оптимизации начинается с первого шага, для которого оптимальное управление известно.
  

Пусть имеется m типов различных грузов, которыми необходимо загрузить транспортное средство таким образом, чтобы общая ценность груза W была максимальной. Ценность груза является функцией отгрузоподъемности транспортного средства:

W = f (G)

Известны массы грузов i-го типа Рi и их стоимости Ci.

Необходимо загрузить транспортное средство таким образом, чтобы общая ценность груза была максимальной:

W = fm(G) = max  xiCi,

где xi – число предметов груза i-го типа, загружаемых в транспортное средство; xi выступает здесь в качестве управления (Ui=xi)

Ограничивающими условиями являются:

 xi Pi  G

xi = 0, 1, 2...