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

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

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

Напр., в за­да­че рас­пре­де­ле­ния ре­сур­сов од­но­род­ный ре­сурс $X$ дол­жен быть рас­пре­де­лён ме­ж­ду $N$ про­из­вод­ст­вен­ны­ми про­цес­са­ми. Ес­ли для $k$-го про­цес­са вы­де­ля­ет­ся ре­сурс $x_k$, то по­лу­ча­ет­ся до­ход $φ_k(x_k),\, k=1,\, …,\, N$. Тре­бу­ет­ся рас­пре­де­лить ре­сурс $X$ по про­цес­сам та­ким об­ра­зом, что­бы сум­мар­ный до­ход был мак­си­маль­ным. Др. сло­ва­ми, тре­бу­ет­ся най­ти мак­си­мум $$f_N(X)=\max \sum^N_{k=1} φ_k (x_k)$$ ад­ди­тив­ной це­ле­вой функ­ции $\sum^N_{k=1} φ_k (x_k)$ при ус­ло­ви­ях $x_k⩾0,\, k=1,\, …,\, N,\, x_1+…+x_N=X$.

Для при­ме­не­ния под­хо­да ди­на­мич. про­грам­ми­ро­ва­ния к дан­ной за­да­че рас­смат­ри­ва­ет­ся се­мей­ст­во за­дач с лю­бым чис­лом ша­гов $n⩽N$ и лю­бым за­па­сом ре­сур­са $0⩽x⩽X$. Мно­го­ша­го­вость при­ня­тия ре­ше­ния вво­дит­ся ис­кус­ст­вен­но, на 1-м ша­ге вы­де­ля­ет­ся ре­сурс $x_n$ для $n$-го про­цес­са, на 2-м ша­ге вы­де­ля­ет­ся ре­сурс $x_{n–1}$ для ($n-1$)-го про­цес­са и т. д. В си­лу ад­ди­тив­но­сти це­ле­вой функ­ции спра­вед­ли­во ре­кур­рент­ное со­от­но­ше­ние $$f_n(x)=\max_{xn} (φ_n(x_n)+f_{n-1}(x-x_n)),\, n=2,\, ...,\, N,$$ где $f_1(x)=φ_1(x)$. Это ре­кур­рент­ное со­от­но­ше­ние пред­став­ля­ет со­бой Б. у. в этой за­да­че. Оно по­зво­ля­ет при всех до­пус­ти­мых зна­че­ни­ях $x⩽X$ по­сле­до­ва­тель­но на­хо­дить функ­ции $f_1(x),\, …, \,f_n(x)$, на­чи­ная с $f_1(x)$, и со­от­вет­ст­вую­щие оп­ти­маль­ные управ­ле­ния $x_1(x), \,…,\, x_n(x)$, где $x_k(x)$ – оп­ти­маль­ный вы­бор ре­сур­са для $k$-го про­цес­са в за­да­че $k$ ша­га­ми, $k=1,\, …,\, n$.

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

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