Подпишитесь на наши новости
Вернуться к началу с статьи up
 

ДИНАМИ́ЧЕСКОЕ ПРОГРАММИ́РОВАНИЕ

  • рубрика

    Рубрика: Математика

  • родственные статьи
  • image description

    В книжной версии

    Том 9. Москва, 2007, стр. 16

  • image description

    Скопировать библиографическую ссылку:




ДИНАМИ́ЧЕСКОЕ ПРОГРАММИ́РОВАНИЕ

ДИНАМИ́ЧЕСКОЕ ПРОГРАММИ́РОВАНИЕ, раз­дел оп­ти­маль­но­го управ­ле­ния, по­свя­щён­ный тео­рии и ме­то­дам ре­ше­ния мно­го­ша­го­вых за­дач. В за­да­чах оп­ти­маль­но­го управ­ле­ния сре­ди воз­мож­ных управ­ле­ний ищет­ся то, при ко­то­ром дос­ти­га­ет­ся экс­тре­маль­ное (наи­мень­шее или наи­боль­шее) зна­че­ние т. н. це­ле­вой функ­ции – не­ко­то­рой чи­сло­вой ха­рак­те­ри­сти­ки про­цес­са. В Д. п. под мно­го­ша­го­во­стью по­ни­ма­ют ли­бо мно­го­сту­пен­ча­тую струк­ту­ру про­цес­са, ли­бо то, что управ­ле­ние раз­би­ва­ет­ся на ряд по­сле­до­ва­тель­ных эта­пов (ша­гов), со­от­вет­ст­вую­щих, как пра­ви­ло, разл. мо­мен­там вре­ме­ни. Ино­гда мно­го­ша­го­вость про­ис­те­ка­ет из су­ще­ст­ва про­цес­са, но она мо­жет вво­дить­ся и ис­кус­ст­вен­но для то­го, что­бы обес­пе­чить воз­мож­ность при­ме­не­ния ме­то­дов Д. п. Под про­грам­ми­ро­ва­ни­ем в Д. п. по­ни­ма­ют при­ня­тие ре­ше­ний (пла­ни­ро­ва­ние), а сло­во «ди­на­ми­че­ское» ука­зы­ва­ет на су­ще­ст­вен­ную роль вре­ме­ни и по­ряд­ка вы­пол­не­ния опе­ра­ций. Ме­то­ды Д. п. яв­ля­ют­ся со­став­ной ча­стью ме­то­дов, ис­поль­зуе­мых в ис­сле­до­ва­нии опе­ра­ций, и при­ме­ня­ют­ся в за­да­чах оп­ти­маль­но­го пла­ни­ро­ва­ния (напр., в за­да­чах об оп­ти­маль­ном рас­пре­де­ле­нии ре­сур­сов, в тео­рии управ­ле­ния за­па­са­ми, в за­да­чах за­ме­ны обо­ру­до­ва­ния) и при ре­ше­нии мн. тех­нич. про­блем (напр., в за­да­чах управ­ле­ния по­сле­до­ва­тель­ны­ми хи­мич. про­цес­са­ми, в за­да­чах оп­ти­маль­ной про­клад­ки до­рог).

Пусть про­цесс управ­ле­ния не­ко­то­рой сис­те­мой $X$ со­сто­ит из $m$ ша­гов (эта­пов); на $i$-м ша­ге управ­ле­ние $y_i$ пе­ре­во­дит сис­те­му из со­стоя­ния $x_{i–1}$, в ко­то­ром она на­хо­ди­лась по­сле $(i-1)$-го ша­га, в но­вое со­стоя­ние $x_i$. При этом за­да­на функ­ция $f_i(x, y)$, и но­вое со­стоя­ние оп­ре­де­ля­ет­ся по этой функ­ции зна­че­ния­ми $x_{i–1}$, $y_i$ так, что $x_i=f_i(x_{i–1}, y_i), i=1, 2, ..., m$. Т. о., управ­ле­ния $y_1, y_2, ..., y_m$ пе­ре­во­дят сис­те­му из на­чаль­но­го со­стоя­ния $x_0∈X_0$ в ко­неч­ное со­стоя­ние $x_m∈X_m$, где $X_0$ и $X_m$ – со­во­куп­но­сти до­пус­ти­мых на­чаль­ных и ко­неч­ных со­стоя­ний сис­те­мы $X$.

Од­на из воз­мож­ных по­ста­но­вок за­дач Д. п. со­сто­ит в сле­дую­щем. При за­дан­ном на­чаль­ном со­стоя­нии $x_0$ тре­бу­ет­ся вы­брать управ­ле­ния $y_1, y_2, ..., y_m$ та­ким об­ра­зом, что­бы сис­те­ма $X$ пе­ре­шла в до­пус­ти­мое ко­неч­ное со­стоя­ние и при этом за­дан­ная це­ле­вая функ­ция $F(x_0, y_1, x_1, ..., y_m, x_m)$ дос­тиг­ла макс. зна­че­ния $F^*$, т. е. $$F^*=\max F(x_0, y_1, x_1, ..., y_m, x_m),$$ где мак­си­мум бе­рёт­ся по всем управ­ле­ни­ям $y_1, ..., y_m$, для ко­то­рых $x_m∈X_m$.

В Д. п. обыч­но пред­по­ла­га­ет­ся, что це­ле­вая функ­ция яв­ля­ет­ся ад­ди­тив­ной. В рас­смот­рен­ном при­ме­ре это оз­на­ча­ет, что $$F=\sum_{i=1}^m\varphi_i(x_{i-1},y_i).$$

Кро­ме то­го, в Д. п. пред­по­ла­га­ет­ся, что в за­да­че от­сут­ст­ву­ет по­сле­дей­ст­вие: ре­ше­ния (управ­ле­ния), при­ни­мае­мые на ша­ге i, ока­зы­ва­ют влия­ние толь­ко на со­стоя­ние xi сис­те­мы в мо­мент i. Оба упо­мя­ну­тых ог­ра­ни­чит. ус­ло­вия мож­но ос­ла­бить, но толь­ко за счёт су­ще­ст­вен­но­го ус­лож­не­ния ме­то­да.

В ос­но­ве Д. п. ле­жит прин­цип оп­ти­маль­но­сти, сфор­му­ли­ро­ван­ный Р. Белл­ма­ном. Пусть вы­бра­ны не­ко­то­рые уп­рав­ле­ния $y_1, y_2, ..., y_k$ и тем са­мым тра­ек­то­рия $x_0, x_1, ..., x_k$ со­стоя­ний и тре­бу­ет­ся за­вер­шить про­цесс, т. е. вы­брать $y_{k+1}, ..., y_m$ (а зна­чит, и $x_{k+1}, ..., x_m$). Ес­ли за­вер­шаю­щая часть про­цес­са не бу­дет оп­ти­маль­ной в смыс­ле дос­ти­же­ния мак­си­му­ма функ­ции $$F_k=\sum_{i=k+1}^m\varphi_i(x_{i-1},y_i),$$

Fпро­цесс не бу­дет оп­ти­маль­ным. Поль­зу­ясь прин­ци­пом оп­ти­маль­но­сти Белл­ма­на, мож­но по­лу­чить осн. функ­цио­наль­ное со­от­но­ше­ние Д. п., ко­то­рое со­сто­ит в сле­дую­щем. Пусть ωm(x)=0,k=i=k+1mφi(xi1,yi),

 

то и весь про­цесс не бу­дет оп­ти­маль­ным. Поль­зу­ясь прин­ци­пом оп­ти­маль­но­сти Белл­ма­на, мож­но по­лу­чить осн. функ­цио­наль­ное со­от­но­ше­ние Д. п., ко­то­рое со­сто­ит в сле­дую­щем. Пусть $ω_m(x)=0, ω_{k-1}(x)=max(\varphi_k(x, y)+ω_k(f_k(x, y))), k=1, 2, ..., m$, где мак­си­мум бе­рёт­ся по всем управ­ле­ни­ям $y$, до­пус­ти­мым на ша­ге $k$. Со­от­но­ше­ние, оп­ре­де­ляю­щее за­ви­си­мость $ω_{k–1}$ от $ω_k$, на­зы­ва­ет­ся урав­не­нием Белл­ма­на. Смысл этих функ­ций дос­та­точ­но ясен: ес­ли сис­те­ма на ша­ге $k-1$ ока­за­лась в со­стоя­нии $x$, то $ω_{k–1}(x)$ есть мак­си­маль­но воз­мож­ное зна­че­ние функ­ции $F_k$. Од­но­вре­мен­но с по­строе­ни­ем функ­ций $ω_{k–1}(x)$ на­хо­дят­ся ус­лов­ные оп­ти­маль­ные управ­ле­ния $y_k(x)$ на ка­ж­дом ша­ге, т. е. зна­че­ния оп­ти­маль­но­го управ­ле­ния при все­воз­мож­ных пред­по­ло­же­ни­ях о со­стоя­нии $x$ сис­те­мы на ша­ге $k-1$. Окон­ча­тель­но оп­ти­маль­ные управ­ле­ния на­хо­дят­ся по­сле­до­ва­тель­ным вы­чис­ле­ни­ем ве­ли­чин $ω_0(x_0)=F^*, y_1, x_1, y_2, ..., y_m, x_m$.

С по­мо­щью Д. п. ре­ша­ет­ся не од­на кон­крет­ная за­да­ча при оп­ре­де­лён­ном $x_0$, а сра­зу все по­доб­ные од­но­тип­ные за­да­чи при лю­бом на­чаль­ном со­стоя­нии. Чис­лен­ная реа­ли­за­ция Д. п. до­воль­но слож­на, т. к. тре­бу­ет за­по­ми­на­ния боль­шо­го ко­ли­че­ст­ва ин­фор­ма­ции, по­это­му Д. п. це­ле­со­об­раз­но при­ме­нять в тех слу­ча­ях, ко­гда не­об­хо­ди­мо мно­го­крат­но ре­шать ти­по­вые за­да­чи (напр., оп­ре­де­ле­ние оп­ти­маль­но­го ре­жи­ма по­лё­та са­мо­лё­та при ме­няю­щих­ся по­год­ных ус­ло­ви­ях). Обыч­но за­да­ча Д. п. фор­му­ли­ру­ет­ся для дис­крет­ных про­цес­сов, но в ря­де слу­чаев Д. п. при­ме­ня­ет­ся и для ре­ше­ния ди­на­мич. за­дач с не­пре­рыв­ны­ми па­ра­мет­ра­ми.

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

Стро­гое обос­но­ва­ние Д. п. сле­ду­ет из ре­зуль­та­тов Л. С. Пон­тря­ги­на и его уче­ни­ков по ма­те­ма­тич. тео­рии управ­ляе­мых про­цес­сов.

Лит.: Белл­ман Р. Ди­на­ми­че­ское про­грам­ми­ро­ва­ние. М., 1960; Ма­те­ма­ти­че­ская тео­рия оп­ти­маль­ных про­цес­сов. М., 1961; Хо­вард Р. А. Ди­на­ми­че­ское про­грам­ми­ро­ва­ние и мар­ков­ские про­цес­сы. М., 1964; Хед­ли Дж. Не­ли­ней­ное и ди­на­ми­че­ское про­грам­ми­ро­ва­ние. М., 1967; Хед­ли Дж., Уай­тин Т. Ана­лиз сис­тем управ­ле­ния за­па­са­ми. М., 1969.

Вернуться к началу