Принцип оптимальности Беллмана. Решение задач методом динамического программирования

При решении  поставленной задачи методом динамического  программирования в качестве функции  состояния управляемой системы  Λ_k(ξ) логично взять минимальный объем затрат, возникающих за первые k периодов при условии, что в k-й период имеется запас ξ . Тогда можно записать основное рекуррентное соотношение

поскольку

Система рекуррентных соотношений (5.27)-(5.28) позволяет  найти последовательность функций  состояния Λ₁(ξ), Λ₂(ξ), …, Λ_n(ξ) и условных оптимальных управлений  ₁(ξ),  ₂(ξ), …,  _n(ξ). На n-м шаге с помощью начального условия (5.26) можно определить х*_n =  _n (y_n+1). Остальные значения оптимальных управлений x*_k определяются по формуле:

Особый  интерес представляет частный случай задачи (5.24)-(5.25), при котором предполагается, что функции затрат на пополнение запаса с_k(х_k) являются вогнутыми по х_k , а функции затрат на хранение s_k(ξ_k) являются линейными относительно объема хранимого запаса, т. е. s_k(ξ_k) = s_kξ_k . Параллельно заметим, что обе предпосылки являются достаточно реалистичными.

Обозначим функцию затрат в течение k-ro периода через

или, что то же самое,

В силу сделанных предположений все  функции затрат f_k (x_k , y_k+1) являются вогнутыми (как суммы вогнутой и линейной функций). Данное свойство значительно упрощает процесс решения, так как для поиска минимума вогнутых функций f_k (x_k , y_k+1) достаточно рассмотреть только две крайние точки множества, на котором отыскивается минимум. С учетом введенного обозначения задачу (5.24)-(5.25) можно записать в виде:

при условиях

Рассмотрим  процедуру решения (5.32)-(5.33). Так как  ищется минимум суммы вогнутых функцийf_k(x_k , y_k+1), то решение будет достигаться на одной из крайних точек множества, определяемого условиями (5.33). Общее число переменных x_k и y_k в системе (5.33) равно 2п. Однако, учитывая то, что в ней только п уравнений, в оптимальном плане будет не более п ненулевых компонент, причем для каждого периода k значения x_k и y_k не могут равняться нулю одновременно (в силу необходимости удовлетворения спроса либо за счет заказа, либо за счет запаса). Формально это утверждение можно представить в виде условия дополняющей нежесткости:

где

С точки  зрения содержательной интерпретации  условия (5.34)-(5.35) означают, что приоптимальном управлении заказ поставщику на новую партию не должен поступать, если в начале периода имеется ненулевой запас, или размер заказа должен равняться величине спроса за целое число периодов. Отсюда следует, что запас на конец последнего периода должен равняться нулю: у*_n+1=0. Последнее позволяет решать задачу в прямом направлении, применяя рекуррентное соотношение

где ξ = у_k+1= х_k + у_k - d_k .

Учитывая (5.34)-(5.35) и вогнутость f_k (x_k, ξ), заключаем, что минимум (5.36) достигается в одной из крайних точек x_k =0 или x_k = ξ + d_k поэтому

тогда для предыдущего периода функция  состояния может быть выражена как

на oснове чего в общем виде получаем модифицированную форму для рекуррентного соотношения

При дальнейших конкретизирующих предположениях о  виде функций f_k (x_k , у_k+1) можно получить еще более компактные формы для рекуррентных соотношений. Однако эти вопросы носят достаточно частный характер, и мы их рассматривать не будем. Отметим лишь, что приведенные в данном пункте преобразования неплохо иллюстрируют общие подходы, применяемые в динамическом программировании, а также те свойства задач, которые открывают возможности, для эффективного и плодотворного использования соответствующих методов.

Список  используемых источников:

1. Высшая  математика для экономистов. Учебник  Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман (1999)
2. Высшая математика для студентов экономических, технических, естественно-научных специальностей вузов, Виленкин И.В., Гробер В.М. (2002)
3. Математика в экономике Малыхин В.И. Москва ИНФРА-М, 2001
4. Высшая математика. Примеры, задачи, упражнения 
   О. А. Кастрица (2003)
5. http://www.exponenta.ru/educat/class/courses/ma/theme1/theme.asp Математический анализ в высшей математике