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

ВЫ́ПУКЛОЕ ПРОГРАММИ́РОВАНИЕ

  • рубрика

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

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

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

    Том 6. Москва, 2006, стр. 126

  • image description

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




ВЫ́ПУКЛОЕ ПРОГРАММИ́РОВАНИЕ, раз­дел ма­те­ма­тич. про­грам­ми­ро­ва­ния, в ко­то­ром ис­сле­ду­ет­ся за­да­ча мак­си­ми­за­ции во­гну­той це­ле­вой функ­ции $f(x)$ век­тор­но­го ар­гу­мен­та $x=(x_1, …, x_n)$, удов­ле­тво­ряю­ще­го ог­ра­ни­че­ни­ям $g_i(x)⩾0, x∈X, i=1, ..., m,$ где $g_i$ – во­гну­тые функ­ции, $X$ – вы­пук­лое мно­же­ст­во. Точ­ка $x$, удов­ле­тво­ряю­щая этим ог­ра­ни­че­ни­ям, на­зы­ва­ет­ся до­пус­ти­мой. Осн. ре­зуль­та­том тео­рии В. п. яв­ля­ет­ся тео­ре­ма о сед­ло­вой точ­ке: для то­го что­бы до­пус­ти­мая точ­ка $x$* за­да­чи В. п. бы­ла оп­ти­маль­ной, не­об­хо­ди­мо (при до­воль­но ши­ро­ких ус­ло­ви­ях) и дос­та­точ­но су­ще­ст­во­ва­ние век­то­ра $y^*=(y^*1, …, y^*_m)$ с не­от­ри­ца­тель­ны­ми ком­по­нен­та­ми та­ко­го $y^*_1$, что точ­ка ($x^*, y^*$) яв­ля­ет­ся сед­ло­вой для функ­ции Ла­гран­жа$$L(x,y)=f(x)+\sum_{i=1}^my_ig_i(x)$$ за­да­чи В. п., т. е. для лю­бых $x∈X$ и $y$ с не­от­ри­ца­тель­ны­ми ком­по­нен­та­ми вы­пол­ня­ют­ся не­ра­вен­ст­ва $L(x, y^*)⩽L(x^*, y^*)⩽L(x^*, y)$.

На тео­ре­му о сед­ло­вой точ­ке опи­ра­ет­ся ряд ме­то­дов В. п., в ко­то­рых ли­бо ми­ни­ми­зи­ру­ет­ся функ­ция $φ(y_1, …, y_m)=\text {max}_{x∈X}L(x, y)$ при $y_i⩾ 0, i= 1, …, m$, ли­бо не­по­сред­ст­вен­но оты­ски­ва­ет­ся сед­ло­вая точ­ка, при­чём вме­сто функ­ции Ла­гран­жа ино­гда ис­поль­зу­ют­ся не­ко­то­рые её мо­ди­фи­ка­ции. Дру­гой под­ход к ре­ше­нию за­да­чи В. п. свя­зан с по­ис­ком воз­мож­ных на­прав­ле­ний дви­же­ния до­пус­ти­мой точ­ки $x$, ко­то­рые не вы­во­дят из мно­же­ст­ва до­пус­ти­мых то­чек и при дви­же­нии вдоль ко­то­рых це­ле­вая функ­ция воз­рас­та­ет. Этот под­ход реа­ли­зу­ет­ся с по­мо­щью по­сле­до­ва­тель­но­сти ите­ра­ций. На ка­ж­дой ите­ра­ции вы­чис­ля­ет­ся воз­мож­ное на­прав­ле­ние, ис­хо­дя­щее из оче­ред­ной точ­ки, по­сле че­го про­из­во­дит­ся сдвиг по это­му на­прав­ле­нию на не­ко­то­рое рас­стоя­ние до сле­дую­щей точ­ки. Су­ще­ст­ву­ют ме­то­ды ре­ше­ния за­дач В. п., спе­ци­аль­но при­спо­соб­лен­ные к то­му слу­чаю, ко­гда це­ле­вая функ­ция не­ли­ней­на, а ог­ра­ни­че­ния ли­ней­ны. Как пра­ви­ло, ме­то­ды В. п. тре­бу­ют для точ­но­го оп­ре­де­ле­ния оп­ти­маль­ной точ­ки бес­ко­неч­но­го чис­ла ите­ра­ций. Ис­клю­че­ни­ем яв­ля­ют­ся за­да­чи квад­ра­тич­но­го про­грам­ми­ро­ва­ния (це­ле­вая функ­ция – сум­ма во­гну­той квад­ра­тич­ной и ли­ней­ной функ­ций, ог­ра­ни­че­ния ли­ней­ны) и ли­ней­но­го про­грам­ми­ро­ва­ния (це­ле­вая функ­ция и ог­ра­ни­че­ния ли­ней­ны), для ко­то­рых в осн. ис­поль­зу­ют­ся ко­неч­ные ме­то­ды. Мно­гие вы­чис­ли­тель­ные ме­то­ды В. п. реа­ли­зо­ва­ны в ви­де про­грамм для ЭВМ; су­ще­ст­ву­ют так­же па­ке­ты про­грамм, ох­ва­ты­ваю­щие за­да­чи ли­ней­но­го про­грам­ми­ро­ва­ния и В. п. См. так­же Ис­сле­до­ва­ние опе­ра­ций.

Лит.: Голь­штейн Е. Г. Вы­пук­лое про­грам­ми­ро­ва­ние. Эле­мен­ты тео­рии. М., 1970; Занг­вилл У. И. Не­ли­ней­ное про­грам­ми­ро­ва­ние. Еди­ный под­ход. М., 1973.

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