Выбор метода решения задачи нахождения оптимальной стратегии

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

Важные особенности метода динамического программирования:

• функция затрат Fj нс обязана быть дифференцируемой и может задаваться таблично;

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

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

Рассматривается управляемый процесс — нахождение оптимальной стратегии управления запасами. В результате управления система (объект управления) S переводится из начального состояния sq в состояние s'⁴. Предположим, что управление можно разбить на w шагов, т. е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность w пошаговых управлений. Обозначим через х/. управление на к-м шаге (к = 1, 2,..., w). Если управления х_к удовлетворяют некоторым ограничениям решаемой задачи, то такие упраатения являются допустимыми (х* может быть числом, точкой в «-мерном пространстве, качественным признаком).

Пусть X (Х|, Х2,..., x_w) — управление, переводящее систему S из состояния so в состояние s^A. Обозначим через s* состояние системы после А>го шага управления (s^ е S_k, где Sf, — множество всех возможных состояний на шаге к). Получаем последовательность состояний so, sj,..., s* _ j,s_w = s^A. Пошаговый процесс перехода системы ,S' из состояния sg в состояние sj под действием управления X (xj, Х2,..., х_и.) представлен на рис. 8.8.

Для данного процесса действуют следующие положения.

1. Состояние Sfc системы в конце к-го шага зависит от предшествующего состояния s* _ | и управления на к-и шаге х_к (и не зависит от предшествующих состояний и упраачепий). Эго требование называется отсутствием последствия. Сформулированное положение записывается в виде уравнений:

которые называются уравнениями состояний.

Рис. 8.8. Процесс перехода системы S из состояния sq в состояние s^A

2. Эффективность каждого А-го шага также зависит от предшествующего состояния s_k _ | и управления па к-м шаге х_к. Обозначим эффективность А:-го шага через

тогда эффективность всего управления A"(X|, Х2,..., х_н) определяется как

Задача пошаговой оптимизации (задача динамического программирования) формулируется следующим образом: определить такое допустимое управление X, переводящее систему S из состояния sq в состояние з^л, при котором целевая функция (8.5) принимает наибольшее (наименьшее) значение.

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

Рассмотрим последовательно определение оптимального управления на шаге w, w — 1 и т. д., используя принцип оптимальности.

Рассмотрим tv-й шаг:

S_w - [ — состояние системы к началу w-ro шага (s_w _ | е 5„,_ |);

s_w = — конечное состояние системы;

x_w — управление на tv-м шаге;

f_w(s_w_ |, x_w) — целевая функция (выигрыш) tv-ro шага.

Согласно принципу оптимальности x_w нужно выбирать гак, чтобы для любых состояний s_w_ | получить максимум целевой функции на этом шаге. Обозначим через ?* (s_w_ ]) максимум целевой функции — показателя эффективности vv-ro шага при условии, что к началу последнего шага система 5 была в произвольном состоянии s_w- ], а на последнем шаге управление было оптимальным.

?*, (s_w- |) называется условным максимумом целевой функции на w-м шаге:

Максимизация ведется по всем допустимым управлениям x_w.

Решение x_w, при котором достигается ?*, (s_w _ ]), также зависит от s_w _ [ и называется условным оптимальным управлением на w-м шаге и обозначается х* (s_w _ ,).

Решив одномерную задачу локальной оптимизации по уравнению (8.6) для всех возможных состояний s_w _ ) находим две функции: ?’, (s_w _ j) и

Xw (— 1) •

Рассмотрим теперь двухшаговую задачу: присоединим к w-му шагу (и> — 1)-й шаг.

Для любых состояний s_w _ 2, произвольных управлений х_и, _ ₍ и оптимальном управлении на w-м шаге значение целевой функции на двух последних шагах имеет вид:

Согласно принципу оптимальности для любых з„,_ 2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем (w-м) шаге приводило бы к максимуму целевой функции на двух последних шагах. Следовательно, необходимо найти максимум выражения (8.7) по веем допустимым управлениям x_w _ j. Максимум этой суммы зависит от s_w _ 2, обозначается через ?* _ | (s_w _ ₂) и называется условным максимумом целевой функции при оптимальном управлении на двух последних шагах:

Соответствующее управление х„- ] на (w — 1)-м шаге обозначается через х* (5_W _ 2) и называется условным оптимальным управлением на (гг — 1)-м шаге.

С учетом уравнения состояния s_w- 1 = ф„, _ |(.v_w _ 2, x_w _ |) значение целевой функции зависит только от s_w _ 2 и x_iv _ 1. В результате максимизации только по одной переменной x_w _ | согласно уравнению (8.8) вновь получаем две функции: ?^,_, (s* _ ₂) и х* _, (s_w _ ₂).

Далее рассматривается трехшаговая задача: к двум последним шагам присоединяется (и> — 2)-й и т. д.

Рассмотрим общий случай определения оптимального управления на шаге k (k = 1, 2,..., w). Обозначим через Е*_к (s* _ j) условный максимум целевой функции, полученный при оптимальном управлении на w — к + 1 шагах, начиная с к-го и до конца, при условии, что к началу к-го шага система находилась в состоянии s_k _ j. Фактически эта функция равна:

В свою очередь

С другой стороны, целевая функция на w — к последних шагах (рие. 8.9) при произвольном управлении х_к на к-м шаге и оптимальном управлении на последующих шагах равна

Рис. 8.9. Процесс управления системой S на последних tv — к шагах

Согласно принципу оптимальности х_к выбирается из условия максимума этой суммы, т. е.

где s_k = <р_k(s_k _ |, х_к), к = 1, 2,..., tv - 1.

Таким образом, определив из (8.6) значения ?*, (,v_w_ |), а из уравнений состояний (8.9) значения Е*_к (s_k _ j) и соответствующие х*_к (s_k _ |), получим последовательности:

условные максимумы целевой функции на последнем, на двух последних, на tv последних шагах и

условные оптимальные управления на w-м, (tv — 1)-м,..., 1-м шагах.

Используя эти последовательности, можно найти решение задачи при данных tv и sq. При фиксированном sq получаем xj = х (sq). Далее из (8.6) определяется з* = ctp ] (л'о, ) и т. д.:

Таким образом, получаем оптимальное решение задачи: