Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Процедура решения задачи динамического программирования

Введем некоторые обозначения.

S'_i - состояние системы в начале i-го шага;

W'_i (S) - условный оптимальный выигрыш, получаемый на всех последующих шагах, начиная с i-го и до конца;

U'_i (S) - условное оптимальное управление на i-м шаге, которое, совместно с оптимальными управлениями на всех последующих шагах, обращает выигрыш на всех оставшихся шагах, начиная с данного, в максимум;

S'_i = Ф_i (S, U'_i) - новое состояние системы, в которое она перейдет из состояния S (в котором она была перед этим шагом) под влиянием управления U'_i на i-м шаге.

Поставим задачу: определить функции W'_i (S) и U'_i (S) (i = 1, k), то есть, условный оптимальный выигрыш и условное оптимальное управление для всех шагов.

Запишем выигрыш, который мы получим на всех шагах, начиная с i-го, если на i-м шаге будет применено любое (вообще говоря, не оптимальное) управление U_i, а на всех последующих (от (i+1)-го до m-го) - оптимальное управление. Этот выигрыш будет равен выигрышу W_i на данном, i-м шаге, плюс условный оптимальный выигрыш на всех последующих шагах, начиная с (i+1)-го, определяемый для нового состояния системы S'; обозначим такой "полуоптимальный" выигрыш через W" (S, U_i):

W"_i (S,Ui) = W_i (S,U_i) + W'_i+1 (S'),

или W"_i (S,U_i) = W_i (S,U_i) + W'_i+1 (Ф_i (S,U_i)) (5.3)

Теперь, в соответствии с принципом оптимальности, мы должны выбрать такое управление Ui = U'_i, при котором величина (5.3) максимальна и достигает значения:

(5.4)

Управление U_i = U'_i (S), при котором этот максимум достигается, и есть условное оптимальное управление на i-м шаге, а сама величина W'_i (S) - условный оптимальный выигрыш (на всех шагах, начиная с i-го и до конца).

В уравнении (5.4) функции W_i (S, U_i ) и Ф_i (S, U_i ) известны. Неизвестными остаются функции W'_i (S) и W'_i+1 (S).

Формула (5.4) представляет собой так называемое основное функциональное уравнение динамического программирования или рекуррентное соотношение^*) Беллмана; она позволяет определить функцию W'_i(S), если известна следующая за ней по порядку функция W'_i+1 (S), что предопределяет порядок действия в динамическом программировании - от последнего шага к первому.

-------------------------------------------------------------------------------------------------------------

^*) - рекуррентное соотношение (формула) – это соотношение(формула), позволяющее вычислить все члены последовательности некоторых величин, если известны первые члены этой последовательности.

-------------------------------------------------------------------------------------------------------------

В каждом многошаговом процессе имеется последний k-ый шаг, принятие решения на котором не зависит от будущего. Поэтому условный оптимальный выигрыш на последнем шаге W'_k(S_k) может быть определен очень просто. Действительно, за последним шагом нет никакого другого, и нужно попросту обратить в максимум выигрыш на последнем шаге:

(5.5)

То есть, на последнем шаге выбирают управление, позволяющее получить наибольший эффект только на одном шаге. Спланировав этот шаг, к нему можно присоединить предпоследний (k-1)–ый шаг, решение на котором принимают уже с учетом принятого на k-ом шаге решения. К этим шагам можно присоединить (k-2)–ой шаг, решение на котором принимают уже с учетом принятых на k-ом и (k-1)–ом шагах решений. И так далее, до первого шага. То есть, процесс как бы «разворачивается» от конца к началу.

При этом на каждом шаге, то есть для каждой точки траектории системы на плоскости Р₁OР₂ точка S может перемещаться под любым углом в пределах некоторого сектора, называемого "розой направлений" (рис.5.1), причем каждому направлению соответствует своя величина выигрыша.

Схема решения такой задачи методом динамического программирования может быть представлена в виде, приведенном на рис. 5.2.

Однако, для того, чтобы спланировать k-ый шаг, нужно знать состояние, в котором система окажется после (k-1)–ого шага. Если состояние системы после (k-1)–ого шага неизвестно, то, исходя из характера процесса, делают предположения о возможных состояниях системы после этого (k-1)–ого шага, то есть, в начале k–ого шага. Для каждого предположения выбирают оптимальное решение (или управление), обеспечивающее получение наибольшего эффекта на последнем k-ом шаге. Однако, мы заранее не знаем окажется ли система в каждом конкретном из предполагаемых состояний. Поэтому принятое оптимальное управление называется условно оптимальным. Таким образом, на всех шагах, двигаясь от последнего шага к первому, находим условно оптимальные управления на этих шагах. В итоге приходим к состоянию S_о Î системы.

Для первого шага, в отличие от остальных, предположений о возможном состоянии системы не делаем, так как состояние S_о известно, а находим оптимальное управление, учитывая условно оптимальные управления, найденные на 2–ом шаге. Далее, проходя от S_о к S_k, получим искомые оптимальные (уже безусловные) управления на всех шагах и для исследуемого процесса в целом.

То есть, зная W'_k(S) для последнего шага, по формуле (5.4) найдем функцию W'_k-1(S) и U'_k-1(S) для предпоследнего шага, затем W'_k-2(S) и U'_k-2(S) и так далее, вплоть до первого шага, для которого найдем функции W'₁(S) и U'₁(S).

Далее, зная исходное состояние So и оптимальное управление U*₁ на первом шаге, можем найти состояние системы после первого шага: S*₁ = Ф₁(S_o, U*₁)

Зная это состояние S*₁, можно найти оптимальное управление на втором шаге U*₂ = U'₂ (S*₁), затем состояние системы после второго шага S*₂ = Ф₂ (S*₁, U'₁) и т.д. Таким образом, идя по цепочке

S_o → U'₁ (S_o) → S*₁→ U'₂ (S*₁) → → S*_m-1→ U'_m (S*_m-1) → S*_m (5.7)

мы определим, одно за другим, все шаговые оптимальные управления и найдем состоящее из них оптимальное управление операцией в целом

U* = (U*₁, U*₂,..., U*_k),

Таким образом, процедуру построения оптимального управления методом динамического программирования можно рассматривать состоящим из двух стадий - предварительную и окончательную:

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

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

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

В принципе процесс динамического программирования может разворачиваться (хотя и не так естественно) и в направлении, обратном тому, которое мы приняли: условные оптимальные управления могут отыскиваться от первого шага к последнему, а безусловные - от последнего к первому.

Пример 5.3. Планируется деятельность двух отраслей производства I и II сроком на 5 лет (m = 5).

Заданы "функции дохода": f (х) = 1 – e ^–х; g (y) = 1 - e^{-2• y}

и "функции траты": Ф (х) = 0,75 • х; P (y) = 0,3 • y.

Требуется распределить имеющиеся средства в размере Кo = 2 усл. единиц между отраслями I и II по годам, исходя из условия максимума дохода за m лет.

Пример 5.4. Планируется деятельность некоторой системы промышленных предприятий Р₁, Р₂,..., Р_n на некоторый период времени Т, состоящий из k хозяйственных лет t_i (i = 1, k), причем Т = (t_i).

Пусть заданы "функции доходов" и "функции трат" предприятий.

В начале каждого хозяйственного года производится финансирование всей системы предприятий, то есть, выделяется доля основных средств. Известны первоначальное состояние системы S_o, характеризуемое количеством средств D_o, вложенных в предприятия к началу исследуемого периода, и конечное состояние Sk, характеризуемое всей дополнительно вложенной суммой D_k.

Следует распределить по предприятиям и по годам основные средства D_k таким образом, чтобы к концу периода Т суммарный доход W от всей системы предприятий был максимальным.