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

НЕЛИНЕ́ЙНОЕ ПРОГРАММИ́РОВАНИЕ

  • рубрика

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

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

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

    Том 22. Москва, 2013, стр. 345

  • image description

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




НЕЛИНЕ́ЙНОЕ ПРОГРАММИ́РОВАНИЕ, раз­дел ма­те­ма­тич. про­грам­ми­ро­ва­ния, по­свя­щён­ный тео­рии и ме­то­дам на­хо­ж­де­ния экс­тре­му­мов не­ли­ней­ных функ­ций мно­гих пе­ре­мен­ных при на­ли­чии до­пол­ни­тель­ных ус­ло­вий на эти пе­ре­мен­ные. Об­щая по­ста­нов­ка за­да­чи Н. п. со­сто­ит в сле­дую­щем: мак­си­ми­зи­ро­вать це­ле­вую функ­цию $f(x)$ при ус­ло­ви­ях$$g_i(x)⩾0,\; i=1,\:\dots,\: m;\\h_j(x)=0,\; j=1,\:\dots,\: k,$$где $x=(x_1,\dots, x_n)$. В со­от­вет­ст­вии с об­щей тер­ми­но­ло­ги­ей ма­те­ма­тич. про­грам­ми­ро­ва­ния точ­ка $x$, удов­ле­тво­ряю­щая всем $m+k$ ог­ра­ни­че­ни­ям за­да­чи, на­зы­ва­ет­ся до­пус­ти­мой или до­пус­ти­мым ре­ше­ни­ем за­да­чи Н. п. До­пус­ти­мая точ­ка, в ко­то­рой $f$ при­ни­ма­ет наи­боль­шее зна­че­ние по срав­не­нию с др. до­пус­ти­мы­ми точ­ка­ми (близ­ки­ми к дан­ной), на­зы­ва­ет­ся (ло­каль­но) оп­ти­маль­ной или (ло­каль­но) оп­ти­маль­ным ре­ше­ни­ем. В за­ви­си­мо­сти от свойств функ­ций $f, g_i, h_j$ в Н. п. вы­де­ля­ют­ся раз­де­лы, сре­ди ко­то­рых – вы­пук­лое про­грам­ми­ро­вание и квад­ра­тич­ное про­грам­ми­ро­ва­ние ($f$ – квад­ра­тич­ная фор­ма или сум­ма квад­ра­тич­ной и ли­ней­ной форм, а $g_i, h_j$ ли­ней­ные функ­ции).

Ос­но­вой всех чис­лен­ных ме­то­дов Н. п. яв­ля­ют­ся ус­ло­вия оп­ти­маль­но­сти. Не­об­хо­ди­мые ус­ло­вия оп­ти­маль­но­сти пер­во­го по­ряд­ка со­сто­ят в сле­дую­щем. Ес­ли $x^*$ – ло­каль­но оп­ти­маль­ная точ­ка, то при вы­пол­не­нии не­ко­то­рых до­пол­нит. ус­ло­вий су­ще­ст­ву­ют та­кие чис­ла (мно­жи­те­ли Ла­гран­жа) $y^*_1,\:\dots,\: y^*_m$ и $z^*_1,\:\dots,\: z^*_k$, что все ча­ст­ные про­из­вод­ные $𝜕L(x, y^*, z^*)/𝜕x_l$ функ­ции Ла­гран­жа$$L(x, y^*, z^*)=f(x) + \sum_{i=1}^{m}y^*_ig_i(x)+\sum_{j=1}^{k}z^*_jg_j(x)$$
за­да­чи Н. п. об­ра­ща­ют­ся в нуль при $x=x^*$, т. е.$$\frac {\partial L(x^*, y^*, z^*)}{\partial x_l}=0,\; l=1,\:\dots,\: n,$$при­чём , $i=1,\:\dots,\: m$. Это ут­вер­жде­ние обоб­ща­ет хо­ро­шо из­вест­ное в ма­те­ма­тич. ана­ли­зе не­об­хо­ди­мое ус­ло­вие экс­тре­му­ма для диф­фе­рен­ци­руе­мой функ­ции $φ (t)$ од­ной пе­ре­мен­ной: $φ′ (t^*)= 0$, ес­ли $t^*$ – ло­каль­но оп­ти­маль­ная точ­ка. Не­об­хо­ди­мые (дос­та­точ­ные) ус­ло­вия оп­ти­маль­но­сти вто­ро­го по­ряд­ка для за­да­чи Н. п. яв­ля­ют­ся обоб­ще­ния­ми ана­ло­гич­ных ус­ло­вий то­го, что­бы функ­ция $φ(t)$ дос­ти­га­ла в точ­ке $t^*$ сво­его ло­каль­но­го мак­си­му­ма: $φ′(t^*)=0,\: {φ}''(t^*)⩽0\: (φ′(t^*)=0,\: {φ}''(t^*)<0)$, они фор­му­ли­ру­ют­ся с по­мо­щью пер­вых и вто­рых ча­ст­ных про­из­вод­ных функ­ций $f, g_i, h_j$.

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

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

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

Лит.: Фи­ак­ко А.-В., Мак-Кор­мик Г.-П. Не­ли­ней­ное про­грам­ми­ро­ва­ние. Ме­то­ды по­сле­до­ва­тель­ной без­ус­лов­ной ми­ни­ми­за­ции. М., 1972; По­ляк Б. Т. Вве­де­ние в оп­ти­ми­за­цию. М., 1983; Кар­ма­нов В. Г. Ма­те­ма­ти­че­ское про­грам­ми­ро­ва­ние. 3-е изд. М., 1986.

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