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

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

За­да­ча М. п. со­сто­ит в том, что­бы ми­ни­ми­зи­ро­вать ска­ляр­ную функ­цию $φ (x)$ век­тор­но­го ар­гу­мен­та $х∈\mathbf{R}^n$ , при­ни­маю­ще­го зна­че­ния из мно­же­ст­ва

$X=\{x: g_i(x) ⩾ 0, i=1,2,...,k; h_j(x)=0, j=1,2,...,m\},$

где $g_i(x), i=1,2,...,k,\:и \:h_j(x), j= 1,2,...,m,$ – ска­ляр­ные функ­ции; функ­цию $φ(x)$ на­зы­ва­ют це­ле­вой функ­ци­ей или функ­ци­ей це­ли, мно­же­ст­во $X$ – мно­же­ст­вом до­пус­ти­мых ре­ше­ний, ре­ше­ние за­да­чи М. п. – оп­ти­маль­ной точ­кой.

В М. п. вхо­дят ли­ней­ное про­грам­ми­ро­ва­ние, где це­ле­вая функ­ция $φ (x)$ и функ­ции $g_i(x), i=1,2,...,k,$ и $h_j(х), j=1,2,...,m,$ ли­ней­ны; вы­пук­лое про­грам­ми­ро­ва­ние, где це­ле­вая функ­ция и мно­же­ст­во до­пус­ти­мых ре­ше­ний вы­пук­лы; квад­ра­тич­ное про­грам­ми­ро­ва­ние, где це­ле­вая функ­ция квад­ра­тич­на и мно­же­ст­во до­пус­ти­мых ре­ше­ний оп­ре­де­ля­ет­ся ли­ней­ны­ми ра­вен­ст­ва­ми и не­ра­вен­ст­ва­ми; дис­крет­ное про­грам­ми­ро­ва­ние, где ре­ше­ние ищет­ся лишь в дис­крет­ных, напр. це­ло­чис­лен­ных, точ­ках мно­же­ст­ва $X$; сто­хас­тич. про­грам­ми­ро­ва­ние, где, в от­ли­чие от де­тер­ми­ни­ро­ван­ных за­дач, вход­ная ин­фор­ма­ция но­сит эле­мен­ты не­оп­ре­де­лён­но­сти.

За­да­чи пе­ре­чис­лен­ных раз­де­лов М. п. об­ла­да­ют сле­дую­щим свой­ст­вом: вся­кая точ­ка ло­каль­но­го ми­ни­му­ма яв­ля­ет­ся оп­ти­маль­ной точ­кой. По-ино­му об­сто­ит де­ло в т. н. мно­го­экс­тре­маль­ных за­да­чах, в ко­то­рых ука­зан­ное свой­ст­во не име­ет мес­та.

В ос­но­ве вы­пук­ло­го про­грам­ми­ро­ва­ния, и в ча­ст­но­сти ли­ней­но­го и квад­ра­тич­но­го, ле­жит тео­ре­ма Ку­на – Так­ке­ра о не­об­хо­ди­мых и дос­та­точ­ных ус­ло­ви­ях су­ще­ст­во­ва­ния оп­ти­маль­ной точ­ки $x^*$: для то­го что­бы точ­ка $x^*$ бы­ла оп­ти­маль­ной, т. е.

$$\varphi (x^*)=\min_{x\in X}\varphi (x),$$

$$X=\{x: f_i(x) ⩾ 0,\: i=1,2,...,k\},$$

не­об­хо­ди­мо и дос­та­точ­но, что­бы су­ще­ст­во­ва­ла та­кая точ­ка $y^*= (y^*_1, y^*_2,...,y^*_k)$, что­бы па­ра то­чек $x^*$, $y^*$ бы­ла сед­ло­вой точ­кой функ­ции Ла­гран­жа $$L(x,y)=\varphi (x)+\sum_{i=1}^{k}y_ig_i(x).$$

По­след­нее оз­на­ча­ет, что $L(x^*, y) ⩽ L(x^*, y^*) ⩽ L(x, у^*)$ для лю­бых $х$ и всех $у ⩾ 0$. Ес­ли ог­ра­ни­че­ния не­ли­нейны, то эта тео­ре­ма спра­вед­ли­ва при не­ко­то­рых до­пол­нит. пред­по­ло­же­ни­ях о мно­же­ст­ве до­пус­ти­мых ре­ше­ний. Ес­ли функ­ции $φ(x)$ и $f_i(x), \:i=1,2,…,k,$ диф­фе­рен­ци­руе­мы, то сед­ло­вую точ­ку оп­ре­де­ля­ют со­от­но­ше­ния $$\frac{\partial L}{\partial x_j}\geqslant 0,\:j=1,2,...,n;$$  $$\sum_{j=1}^{k}\frac{\partial L}{\partial x_j}x_j=0;\:\frac{\partial L}{\partial y_i}\leqslant 0,\:i=1,2,...,k;$$

$$\sum_{j=1}^{k}\frac{\partial L}{\partial y_j}y_j=0;\:\ y_i\leqslant 0,\:i=1,2,...,k.$$

Т. о., за­да­ча вы­пук­ло­го про­грам­ми­ро­ва­ния сво­дит­ся к ре­ше­нию сис­те­мы урав­не­ний и не­ра­венств.

На ос­но­ве тео­ре­мы Ку­на – Так­ке­ра раз­ра­бо­та­ны разл. ите­ра­ци­он­ные ме­то­ды ми­ни­ми­за­ции, сво­дя­щие­ся к по­ис­ку сед­ло­вой точ­ки функ­ции Ла­гран­жа.

В М. п. важ­ную роль иг­ра­ют вы­чис­лит. ме­то­ды ре­ше­ния экс­тре­маль­ных за­дач. Ши­ро­ким клас­сом та­ких ме­то­дов яв­ля­ют­ся ме­то­ды про­ек­ти­ро­ва­ния. Идея этих ме­то­дов со­сто­ит в сле­дую­щем. В точ­ке $x^k∈X$ вы­би­ра­ет­ся на­прав­ле­ние спус­ка $s^k$, т. е. од­но из на­прав­ле­ний, по ко­то­ро­му функ­ция $φ(x)$ убы­ва­ет, и вы­чис­ля­ет­ся

$x^{k+1}=p(x^k+α_ks^k)$, где $p(x^k+α_ks^k)$ оз­на­ча­ет про­ек­цию точ­ки $x^k+α_ks^k$ на мно­же­ст­во $X$: $$\left | p(x^k+\alpha _ks^k) -(x^k+\alpha _ks^k)\right |=\min_{x\in X}\left | x-(x^k+\alpha _ks^k) \right |,$$ чис­ло $α_k > 0$ вы­би­ра­ет­ся при этом так, что­бы $φ (x^{k+1}) < φ (x^k)$. Су­ще­ст­ву­ют разл. ва­ри­ан­ты ме­то­дов про­ек­ти­ро­ва­ния. Наи­бо­лее рас­про­стра­нён­ным из них яв­ля­ется ме­тод про­ек­ции гра­ди­ен­та, ко­гда $s^k=-\text{grad}φ(x^k)$.

Ха­рак­тер­ной осо­бен­но­стью вы­чис­лит. ме­то­дов ре­ше­ния за­дач М. п. яв­ля­ет­ся ис­поль­зо­ва­ние ЭВМ, в пер­вую оче­редь по­то­му, что за­да­чи М. п., свя­зан­ные с си­туа­ция­ми управ­ле­ния ре­аль­ны­ми сис­те­ма­ми, – за­да­чи боль­шо­го объ­ё­ма.

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

М. п. как нау­ка сфор­ми­ро­ва­лось в 1950–70-х гг. Это обу­слов­ле­но гл. обр. раз­ви­ти­ем ЭВМ, что да­ло воз­мож­ность про­во­дить ма­те­ма­тич. об­ра­бот­ку боль­ших объ­ё­мов ин­фор­ма­ции.