8. 25. Принцип оптимальности и уравнение Беллмана.

9. Принцип оптимальности:

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

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

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

Уравнение Беллмана. Вместо исходной задачи ДП с фиксированным числом шагов п и начальным состоянием s₀ рассмотрим последовательность следующих задач:

при n=1 – одношаговая задача;

при n=2 – двухшаговая задача; …

На каждом шаге любого состояния системы s_k-1 решение X_k нужно выбирать "с оглядкой", так как этот выбор влияет на последующее состояние s_k и дальнейший процесс управления, зависящий от s_k. Например в нашей задаче присуждая на первом шаге первому предприятию все ресурсы мы можем получить в итоге не самое оптимальное решение. Это следует из принципа оптимальности.

Но на последнем шаге можно для любого состояния s_n-₁ планировать локально-оптимально, исходя только из соображений этого шага.

Рассмотрим последний шаг (n-ый шаг) :

s_n-1 - состояние системы к началу этого шага,

s_n=s^ - конечное состояние,

X_n – управление на n-ом (последнем) шаге,

f_n(s_n-1,X_n) – целевая функция (выигрыш) n-го шага

Согласно принципу оптимальности, Х_п нужно выбирать так, чтобы для любых состояний s_n-₁ получить максимум целевой функции на этом шаге.

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

Очевидно, что.

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

Решение Х_n, при котором достигается также зависит от s_n-₁ и называется условным оптимальным управлением на п-м шаге. Оно обозначается через . Если у нас, к примеру, осталось 3 ресурса в казне присуждать предприятию более 3 ресурсов не представляется возможным.

Решая одномерную задачу локальной оптимизации, найдем для всех возможных состояний s_n-₁ две функции: .

Для нашего примера решаем одношаговую задачу: Рассматриваем переход из состояния s₃ в s_4.

Рассматриваем поведение остальных участников задачи, когда s₃ принимает значение ноль, то бишь все ресурсы розданы раннее. Тогда X₄ принимает единственное решение – 0, новое состояние S₄ =0. Выигрыш f₄(s₃,x₄)=0 и естественно условно оптимальный выигрыш тоже = 0.

При s₃ =1 X₄ может принимать уже два значения 0 и 1. Если принимается решение X₄ не отдавать ресурс, то переходим к новому состоянию казны, где количество ресурсов =1, но если же принимается решение отдать на этом шаге единственный ресурс, то мы опустошим казну окончательно и получим некий выигрыш f₄(s₃,x₄)=4 (из таблицы прибыли предприятия 4). Очевидно, в этом случае такое решение будет в рамках принципа оптимальности, ибо функция 4-го предприятия монотонно увеличивается.

Значит, вложение всех оставшихся средств приведет только к увеличению общей прибыли.

Рассматривая возможные дальнейшие состояния S₃ объекта управления, занесем значения по аналогии в таблицу.

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

S3	X4	S4	f4(s3,x4)
0	0		0	0		0
1	0 1		1 0	0 4		4
2	0 1 2		2 1 0	0 4 6		6
3	0 1 2 3		3 2 1 0	0 4 6 8		8
...	…		…	…		…