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

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

Уравнения Беллмана. На каждом шаге любого состояния системы S_k-1 решение Х_k нужно выбирать "с оглядкой", так как этот выбор влияет на последующее состояние S_k и дальнейший процесс управления, зависящий от S_k. Но есть один шаг, последний, который можно для любого состояния S_n-1 планировать локально-оптимально, исходя только из

соображений этого шага. Z_n = f_n(S_n-1; X_n) Согласно принципу оптимальности Хn нужно выбирать так, чтобы для любых состояний S_n-1 получить максимум целевой функции на этом шаге. Z_n*(S_n-1) = opt f_n(S_n-1; X_n) - называется условным оптимумом (max, min) целевой функции на n-м шаге.

Решение Хn при котором достигается Zn* также зависит от S_n-1 и называется условным оптимальным управлением на n-м шаге. Решив одномерную задачу локальной оптимизации по уравнению Z_n*(S_n-1) = opt f_n(S_n-1; X_n) найдем для всех возможных состояний S_n-1 две функции: Z_n*(S_n-1) и Xn*(S_n-1).

Рассмотрим теперь двухшаговую задачу: присоединим к n-му шагу (n-1)-й: f_n-1(S_n-2; X_n-1),

f_n-1(S_n-2; X_n-1)+Zn*(S_n-1) – значение целевой функции на 2-х последних шагах.

Согласно принципу оптимальности для любых Sn-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем (n-м) шаге приводило бы к максимуму целевой функции на двух последних шагах. Следовательно, нужно найти максимум выражения по всем допустимым управлениям X_n-1.

Z*_n-1(S_n-2) = opt (f_n-1 (S_n-2; X_n-1)+Zn*(S_n-1)). Z*(n-2) – условный max (min) целевой функции при оптимальном управлении на 2-х последних шагах. Управление, соответствующее этому значению целевой функции обозначается X*_n-1(S_n-2) и называется условным оптимальным управлением на n-1 – шаге.

S_n-1 = φ _n-1 (S_n-2; S_n-1), Z*_n-1(S_n-2), т.к. состояние S_n-1 можно выразить через состояние S_n-2, то Z зависит только от S_n-2.

Z*_k(S_k-1) = opt (f_k(S_k-1;X_k) + Z*_k+1(S_k)) – уравнение Беллмана, k=n-1, n-2, n-3 (изменяется в сторону уменьшения).

Постановка и решение задачи о распределении ресурсов между предприятиями.

 

Постановка и решение задачи о ремонте и замене оборудования.

 

Постановка и решение задачи о выборе оптимального маршрута.

 

V. Задачи Теории игр