Пиши Дома Нужные Работы

Обратная связь

Общая постановка задачи динамического программирования

Динамическое программирование (ДП) — метод оптимизации, приспособленный к операциям, в которых процесс принятия ре­шения может быть разбит на этапы (шаги). Такие операции назы­ваются многошаговыми. Начало развития ДП относится к 50-м годам XX в. Оно связано с именем Р.Беллмана1.

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

В реально функционирующих больших экономических систе­мах еженедельно требуется принимать микроэкономические ре-


Беллман Р.Э. (р. 1920 г.) — американский математик.


               
   
   
 
       
 
 
 

Глава 12

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



Приведем общую постановку задачи ДП. Рассматривается управляемый процесс, например, экономический процесс распре­деления средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования, пополнения запасов и т. п. В результате управления система (объект управления) S пере­водится из начального состояния s0 в состояние s . Предположим, что управление можно разбить на п шагов, т.е. решение принима­ется последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность п пошаговых управлений.

Обозначим через Хк управление на k-м шаге (к=\, 2, ..., л). Пе­ременные Хк удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Хк может быть числом, точкой в «-мерном пространстве, качественным признаком).

Пусть Х(Х\, Xj, ..., Х„) — управление, переводящее систему S из состояния s0 в состояние s. Обозначим через s^ состояние сис­темы после к-ro шага управления. Получаем последовательность состояний s0, Si, ..., s/c-i, %..., sn-\, s„=s, которую изобразим кружками (рис. 12.1).

0i0£- ■ ■ ^©^(Э^ • ■ ^0^0

Рис. 12.1

Показатель эффективности рассматриваемой управляемой опе­рации — целевая функция — зависит от начального состояния и управления:

Z=F(s0,X). (12.1)

Сделаем несколько предположений.

1. Состояние Sk системы в конце А:-го шага зависит только от предшествующего состояния sk-\ и управления на к-м шаге Хк


Модели динамического программирования 247

(и Не зависит от предшествующих состояний и управлений) Это требование называется "отсутствием последействия". Сформули­рованное положение записывается в виде уравнений

= Ф*С**-ь Хк), к= \,2, ..., п, (12.2)

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

2. Целевая функция (12.1) является аддитивной от Показателя эффективности каждого шага [3]. Обозначим показатель эффек­тивности к-то шага через

Zk ~fk(sk-\, Xk), k=\, 2, ..., п, (12.3)

тогда

п

Z = Yjfk(sk-\,Xk). (12.4)

*=i

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление X, переводящее сис­тему s из состояния s0 в состояние s , при котором целевая функция (12-4) принимает наибольшее (наименьшее) значение.

Выделим особенности модели ДП:

1- Задача оптимизации интерпретируется как п-шаговый процесс
управления.

2- Целевая функция равна сумме целевых функции каждого шага.
3. Выбор управления на k-м шаге зависит только от состояния

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

4- Состояние sk после k-го шага управления зависит только от предшествующего состояния sk~\ и управления Хк (отсутствие по­следействия).

5- На каждом шаге управление Хк зависит от конечного числа управляющих переменных, а состояние sk от конечного числа па­раметров (смысл замечания 5 станет ясным из рассмотренных ниже примеров).

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



Глава 12


Модели динамического программирования



 


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

Принцип оптимальностивпервые был сформулирован Р. Белл-маном в 1953 г. Каково бы ни было состояние s системы в резуль­тате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управле­нием на всех последующих шагах приводило к оптимальному выигры­шу на всех оставшихся шагах, включая данный]. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование — процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно ока­зывать влияния на предшествующие шаги.

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

Уравнения Беллмана.Вместо исходной задачи ДП (см. разд. 12.1) с фиксированным числом шагов п и начальным состоянием 5Ь рассмотрим последовательность задач, полагая последовательно л=1, 2, ... при различных s — одношаговую, двухшаговую и т.д., — используя принцип оптимальности.

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

На каждом шаге любого состояния системы s^-i решение Х# нужно выбирать "с оглядкой", так как этот выбор влияет на по­следующее состояние Sk и дальнейший процесс управления, зави­сящий от St. Это следует из принципа оптимальности.

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


Рассмотрим л-й шаг: s„-\ — состояние системы к началу я-го шага, sn=s— конечное состояние, Х„ — управление на «-м шаге af„(s„-i, X„) — целевая функция (выигрыш) «-го шага.

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

Обозначим через Z*„(sn-\) максимум целевой функции — показателя эффективности «-го шага при условии, что к на­чалу последнего шага система S была в произвольном состоя­нии s„~\, а на последнем шаге управление было оптималь­ным.

Z„(s„-\) называется условным максимумом целевой функции на п-м шаге. Очевидно, что

(12.5)

К^п-\) = max f„ Су„_ь Х„).

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

Решение Х„, при котором достигается Z*„ Cv-r), также зависит от s„_i и называется условным оптимальным управлением на п-м шаге. Оно обозначается через Х*п {sn-\).

Значение целевой функции (я—1)-го шага при произвольном управлении Х„ , и состоянии s„ ,

£,(*„,, К,)

Рис. 12.2

Условно оптимальный выигрыш на п-м шаге


 


1 Формулировка принадлежит Е.С.Вентцель [3] и немного отличается от предложенной Беллманом.


Ограничимся здесь задачей максимизации целевой функии.-,.



Глава 12


Модели динамического программирования



 


Решив одномерную задачу локальной оптимизации по уравне­нию (12.5), найдем для всех возможных состояний sn-\ две функ­ции: Z'„{s„-x) и Х'„ (s„-x).

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

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

fn-i(sn-b Хп-Х)+Z'„{sn-X). (12.6)

Согласно принципу оптимальности для любых sn-i решение нужно выбирать так, чтобы оно вместе с оптимальным управле­нием на последнем (п-и) шаге приводило бы к максимуму целе­вой функции на двух последних шагах. Следовательно, нужно найти максимум выражения (12.6) по всем допустимым управле­ниям Х„-\. Максимум этой суммы зависит от s„-i, обозначается через Z„_| (sn-2) и называется условным максимумом целевой функ­ции при оптимальном управлении на двух последних шагах. Соответ­ствующее управление Хп-\ на (п~1)-и шаге обозначается через

X*„.i(sn-2) и называется условным оптимальным управлением на (п— 1)-м шаге.

2*п-\ fe-2)= maxJ/„_i(V2.*fl-i) + zl (-Vi)) ■ (12.7)

Следует обратить внимание на то, что выражение, стоящее в фигурных скобках (12.7), зависит только от s„-2 и Хп-\, так как s„-\ можно найти из уравнения состояний (12.2) при к=п—\.

^-1=9/7-1(^-2 п-\) и подставить вместо sn-\ в функцию Z* (sn-\).

В результате максимизации только по одной переменной Х„-х согласно уравнению (12.7) вновь получаются две функции:

К-1 (sn-2) И Х*п_х (s„-2).

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

Обозначим через Z*k (sk-\) условный максимум целевой функции, полученный при оптимальном управлении на п—к+1 шагах, начиная с


к-го до конца, при условии, что к началу k-го шага система находи­лась в состоянии sk-h Фактически эта функция равна

Тогда

^*(**-i)= max tfi(Si-i>Xi)-Z'k+l(sk) = max £fi{si-UXi)-

{(** + ! .-.*«)} i = k + \

fk(sk4, Xk)+Zk+I{sk)

J к № h Лк)

Рис. 12.3

Целевая функция на п~к последних шагах (рис. 12.3) при про­извольном управлении Хк на к-и шаге и оптимальном управлении на последующих п-к шагах равна

fk{sk-\, Xk)+ Z*k+l{sk).

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

(12.8)

7-l(sk_x) = max{fk(sk_uXk) + Z*k+l(sk)},

к = п-\, п-2, ..., 2, 1. Управление Хк на к-и шаге, при котором достигается макси­мум в (12.8), обозначается через X*k(sk-i) и называется условным оптимальным управлением на к-м шаге (в правую часть уравнения



Глава 12


Модели динамического программирования



 


(12.8) следует вместо ^ подставить выражение s^—cp^Sk-i, Хк), найденное из уравнений состояния).

Уравнения (12.8) называют уравнениями Беллмана. Это ре­куррентные соотношения, позволяющие найти предыдущее значение функции, зная последующие. Если из (12.5) найти Z*n(s„-\), то при к=п-\ из (12.8) можно определить, решив задачу максимизации для всех возможных значений sn-2, вы­ражения для Z„_| Cv-2) и соответствующее X*n_\(sn-j). Далее, зная Z*_, (sn-2), находим, используя (12.8) и (12.2), уравнения состояний.

Процесс решения уравнений (12.5) и (12.8) называется условной оптимизацией1.

В результате условной оптимизации получаются две последова­тельности:

Zn(sn-l)> Z„-i(S„_2), •■•> Z2{S\), Zx (S0) —

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

X>Asn-i)i X„_l(s„_2),..., X2(s{), Х\ (s0) —

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

Используя эти последовательности, можно найти решение

задачи ДП при данных я и sQ. По определению (см. разд. 12.1)

Z\{sq) — условный максимум целевой функции за я шагов при

условии, что к началу 1-го шага система была в состоянии s0,

т.е.

Zmax = Z;(s0). (12.9)

Далее следует использовать последовательность условных оп­тимальных управлений и уравнения состояний (12.2).

При фиксированном s0 получаем Х\ = X\{sq). Далее из урав­нений (12.2) находим sx = <$\{s0, X\) и подставляем это выраже-


ние в последовательность условных оптимальных управлений: Х*2 - X*2(s*{) и т.д. по цепочке1:

Х\ = X\{Sq) -> s\ = ср,(% Х{) -> Х*2 = Xlisl) ->

-> *2 = ФгСч*, Xl) => Х*Ъ = Х'з(4) ->■■■-> ~* sn-\ = Фл-1(5л-2' Хп-\) => Х„ = X„{sn_i).

Получаем оптимальное решение задачи ДП:

X = \Х1, Х2,..., Xnj.

(Стрелка -» означает использование уравнений состояния, а стрелка => — последовательности условных оптимальных управ­лений).






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2021 pdnr.ru Все права принадлежат авторам размещенных материалов.