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

      1.3 ПРИНЦИП ОПТИМАЛЬНОСТИ  И МАТЕМАТИЧЕСКОЕ  ОПИСАНИЕ ДИНАМИЧЕСКОГО ПРОЦЕССА УПРАВЛЕНИЯ 

      В основе метода динамического программирования лежит принцип оптимальности, впервые  сформулированный в 1953 г. американским математиком Р. Э. Беллманом: каково бы ни было состояние системы в  результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. Однако, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства, поэтому доход от ее эксплуатации в начале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохода в текущем году, то в дальнейшем это приведет к значительным убыткам. Этот пример демонстрирует следующий факт: в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс.

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

      1) возможные исходы предыдущего  шага S_k-1;

      2) влияние управления х_k на все оставшиеся до конца процесса шаги         (n - k).

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

      Условная  оптимизация. На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге, оптимальное управление – х*_n определяется функцией Беллмана:              F(S) = max {W_n (S, x_n)}, в соответствии с которой максимум выбирается из всех возможных значений х_n, причем х_n∈Х.

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

      F_n (S) = max {W_n (S, x_n) + F_k+1 (S¹(S, x_k))}, x_k∈Х.

      Этот  максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

      Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно – это ее начальное состояние S_o, можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге x₁, которое этот результат доставляет. После применения этого управления система перейдет в другое состояние S¹(S,х*₁), зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге х*₂, и так далее до последнего n-го шага. Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам прямой прогонки (от начала) и обратной прогонки (от конца к началу). Рассмотрим примеры решения различных по своей природе задач, содержание которых требует выбора переменных состояния и управления. 

1.4  ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ИНВЕСТИЦИЙ 

      Требуется распределить имеющиеся В единиц средств среди n предприятий, доход g_i(x_i) от которых, в зависимости от количества вложенных средств х_i, определяется матрицей (n*n), приведенной в табл. 1, так, чтобы суммарный доход со всех предприятий был бы максимальным. 
 
 
 

      Таблица 1

      Запишем математическую модель задачи.

      Определить  X* = (х^*₁, х^*₂, …, х^*_i, …, х^*_n), удовлетворяющий условиям

      и обеспечивающий максимум целевой функции

      F(X) = ∑x_i g_i ( x_i ) → max

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

      С этой целью разобьем процесс оптимизации  на n шагов и будем на каждом k-м шаге оптимизировать инвестирование не всех предприятий, а только предприятий с k-го по n-е. При этом естественно считать, что в остальные предприятия (с первого по (k–1)-е тоже вкладываются средства, и поэтому на инвестирование предприятий с k-го по n-е остаются не все средства, а некоторая меньшая сумма С_k ≤ В. Эта величина и будет являться переменной состояния системы. Переменной управления на k-м шаге назовем величину х_k средств, вкладываемых в k-e предприятие. В качестве функции Беллмана F_k(C_k) на k-м шаге можно выбрать максимально возможный доход, который можно получить с предприятий с k-го по n-е при условии, что на их инвестирование осталось С_k средств. Очевидно, что при вложении в k-e предприятие х_k средств будет получена прибыль g_k(x_k), а система к (k+1)-му шагу перейдет в состояние S_k+1 и, следовательно, на инвестирование предприятий с (k+1)-го до n-го останется С_k+1 = (С_k – х_k) средств.

      Таким образом, на первом шаге условной оптимизации  при k = n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может остаться количество средств С_n, 0 ≤ С_n ≤ В. Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е. F_n(С_n) = g_n(С_n) и х_n = С_n.

      На  каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на k-м шаге для инвестирования предприятий с k-го по n-е осталось С_k средств (0 ≤ С_k ≤ В). Тогда от вложения в k-e предприятие х_k средств будет получена прибыль g_k(C_k), а на инвестирование остальных предприятий (с k-го по n-е) останется            С_k+1 = (С_k – х_k) средств. Максимально возможный доход, который может быть получен с предприятий (с k-го по n-е), будет равен:

F_k (C_k) = max {g_k(x_k ) + F_k+1 (с_k - x_k )} , k = 1, …, n

      Максимум  выражения достигается на некотором  значении х^*_k, которое является оптимальным управлением на k-м шаге для состояния системы S_k. Действуя таким образом, можно определить функции Беллмана и оптимальные управления до шага k = 1.

      Значение  функции Беллмана F₁(c₁) представляет собой максимально возможный доход со всех предприятий, а значение х^*₁, на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина С_k = (С_k-1 – х_k-1) оптимальным управлением на k-м шаге является то значение х_k, которое обеспечивает максимум дохода при соответствующем состоянии системы S_k. 
 

      1.5 ВЫБОР ОПТИМАЛЬНОЙ СТРАТЕГИИ ОБНОВЛЕНИЯ ОБОРУДОВАНИЯ 

      Важной  экономической проблемой является своевременное обновление оборудования: автомобилей, станков, телевизоров, магнитол и т. п. Старение оборудования включает физический и моральный износ, в результате чего растут затраты на ремонт и обслуживание, снижается производительность труда и ликвидная стоимость. Задача заключается в определении оптимальных сроков замены старого оборудования. Критерием оптимальности являются доход от эксплуатации оборудования (задача максимизации) либо суммарные затраты на эксплуатацию в течение планируемого периода (задача минимизации).

      Предположим, что планируется эксплуатация оборудования в течение некоторого периода  времени продолжительностью n лет. Оборудование имеет тенденцию с течением времени  стареть и приносить все меньший доход r(t)          (t – возраст оборудования). При этом есть возможность в начале любого года продать устаревшее оборудование за цену S(t), которая также зависит от возраста t, и купить новое оборудование за цену P.

      Под возрастом оборудования понимается период эксплуатации оборудования после последней замены, определенный в годах. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарный доход за все n лет был бы максимальным, учитывая, что к началу эксплуатации возраст оборудования составлял t₀ лет.

      Исходными данными в задаче являются доход r(t) от эксплуатации в течение одного года оборудования возраста t лет, остаточная стоимость S(t), цена нового оборудования P и начальный возраст оборудования t₀.

      Таблица 2

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

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

      Поскольку процесс оптимизации ведется  с последнего шага (k = n), то на k-м шаге неизвестно, в какие годы с первого по (k-1)-й должна осуществляться замена и, соответственно, неизвестен возраст оборудования к началу k-го года. Возраст оборудования, который определяет состояние системы, обозначим t. На величину t накладывается следующее ограничение:

      1 ≤ t ≤ t₀ + k – 1

      Это выражение свидетельствует о том, что t не может превышать возраст оборудования за (k–1)-й год его эксплуатации с учетом возраста к началу первого года, который составляет t₀ лет; и не может быть меньше единицы (этот возраст оборудование будет иметь к началу k-го года, если замена его произошла в начале предыдущего (k–1)-го года).

      Таким образом, переменная t в данной задаче является переменной состояния системы на k-м шаге. Переменной управления на k-м шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (С) или заменить (З) оборудование в начале k-го года:

      x_k(t) = { С, если оборудование сохраняется

                                            {  З, если оборудование заменяется

      Функцию Беллмана F_k(t) определяют как максимально возможный доход от эксплуатации оборудования за годы с k-го по n-й, если к началу k-го возраст оборудования составлял t лет. Применяя то или иное управление, система переходит в новое состояние. Так, например, если в начале k-го года оборудование сохраняется, то к началу (k + 1)-го года его возраст увеличится на единицу (состояние системы станет t+1), в случае замены старого оборудования новое достигнет к началу (k + 1)-го года возраста t = 1 год.