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

БЕ́ЛЛМАНА УРАВНЕ́НИЕ

  • рубрика

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

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

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

    Том 3. Москва, 2005, стр. 223

  • image description

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


    Книжная версия:



    Электронная версия:

БЕ́ЛЛМАНА УРАВНЕ́НИЕ, ре­кур­рент­ное со­от­но­ше­ние для ре­ше­ния за­да­чи оп­ти­маль­но­го управ­ле­ния с ад­ди­тив­ной це­ле­вой функ­ци­ей. Ме­тод на­хо­ж­де­ния оп­ти­маль­но­го управ­ле­ния с по­мо­щью Б. у. по­лу­чил на­зва­ние ди­на­ми­че­ско­го про­грам­ми­ро­ва­ния

 >>
. Урав­не­ние но­сит имя Р. Белл­ма­на
 >>
, сфор­му­ли­ро­вав­ше­го прин­ци­пы ди­на­мич. про­грам­ми­ро­ва­ния в кон. 1950-х гг.

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

Напр., в за­да­че рас­пре­де­ле­ния ре­сур­сов од­но­род­ный ре­сурс X дол­жен быть рас­пре­де­лён ме­ж­ду N про­из­вод­ст­вен­ны­ми про­цес­са­ми. Ес­ли для k-го про­цес­са вы­де­ля­ет­ся ре­сурс xk, то по­лу­ча­ет­ся до­ход φk(xk),k=1,,N. Тре­бу­ет­ся рас­пре­де­лить ре­сурс X по про­цес­сам та­ким об­ра­зом, что­бы сум­мар­ный до­ход был мак­си­маль­ным. Др. сло­ва­ми, тре­бу­ет­ся най­ти мак­си­мум fN(X)=maxNk=1φk(xk) ад­ди­тив­ной це­ле­вой функ­ции Nk=1φk(xk) при ус­ло­ви­ях xk0,k=1,,N,x1++xN=X.

Для при­ме­не­ния под­хо­да ди­на­мич. про­грам­ми­ро­ва­ния к дан­ной за­да­че рас­смат­ри­ва­ет­ся се­мей­ст­во за­дач с лю­бым чис­лом ша­гов nN и лю­бым за­па­сом ре­сур­са 0xX. Мно­го­ша­го­вость при­ня­тия ре­ше­ния вво­дит­ся ис­кус­ст­вен­но, на 1-м ша­ге вы­де­ля­ет­ся ре­сурс xn для n-го про­цес­са, на 2-м ша­ге вы­де­ля­ет­ся ре­сурс xn1 для (n1)-го про­цес­са и т. д. В си­лу ад­ди­тив­но­сти це­ле­вой функ­ции спра­вед­ли­во ре­кур­рент­ное со­от­но­ше­ние fn(x)=maxxn(φn(xn)+fn1(xxn)),n=2,...,N, где f1(x)=φ1(x). Это ре­кур­рент­ное со­от­но­ше­ние пред­став­ля­ет со­бой Б. у. в этой за­да­че. Оно по­зво­ля­ет при всех до­пус­ти­мых зна­че­ни­ях xX по­сле­до­ва­тель­но на­хо­дить функ­ции f1(x),,fn(x), на­чи­ная с f1(x), и со­от­вет­ст­вую­щие оп­ти­маль­ные управ­ле­ния x1(x),,xn(x), где xk(x) – оп­ти­маль­ный вы­бор ре­сур­са для k-го про­цес­са в за­да­че k ша­га­ми, k=1,,n.

Оп­ти­маль­ный до­ход для ис­ход­ной за­да­чи ра­вен fN(X). Тем са­мым ре­ше­ние ис­ход­ной за­да­чи мак­си­ми­за­ция функ­ции от N пе­ре­мен­ных сво­дит­ся к ре­ше­нию N за­дач, в ка­ж­дой из ко­то­рых мак­си­ми­за­ция про­во­дит­ся по од­ной пе­ре­мен­ной.

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

Лит.: Белл­ман Р. Ди­на­ми­че­ское про­грам­ми­ро­ва­ние. М., 1960; Белл­ман Р., Дрей­фус С. При­клад­ные за­да­чи ди­на­ми­че­ско­го про­грам­ми­ро­ва­ния. М., 1965; Фле­минг У., Ри­шел Р. Оп­ти­маль­ное управ­ле­ние де­тер­ми­ни­ро­ван­ны­ми и сто­хас­ти­че­ски­ми сис­те­ма­ми. М., 1978.

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