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

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

  • рубрика

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

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

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

    Том 17. Москва, 2010, стр. 500-501

  • image description

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




ЛИНЕ́ЙНОЕ ПРОГРАММИ́РОВАНИЕ, раз­дел ма­те­ма­ти­ки, по­свя­щён­ный тео­рии и ме­то­дам ре­ше­ния за­дач об экс­тре­му­мах ли­ней­ных функ­ций на мно­же­ст­вах, за­да­вае­мых сис­те­ма­ми ли­ней­ных ра­венств и не­ра­венств. За­да­чи Л. п. яв­ля­ют­ся ма­те­ма­тич. мо­де­ля­ми разл. за­дач тех­ни­ко-эко­но­мич. со­дер­жа­ния.

Ти­пич­ной за­да­чей Л. п. яв­ля­ет­ся за­да­ча на­хо­ж­де­ния мак­си­му­ма по $x_1,...,x_n$ ли­ней­ной функ­ции $$\sum_{j=1}^{n}c_jx_j\tag1$$при ус­ло­ви­ях$$\sum_{j=1}^n a_{ij}x_j ⩽ b_i,\;i=1,\:...,\:m, \tag2$$$$x_j⩾0,\; j=1,\:...,\:n,\tag3$$ где $n$, $m$, $c_j$, $a_{ij}$ и $b_i$ – за­дан­ные чис­ла.

Та­кая за­да­ча воз­ни­ка­ет, напр., при пла­ни­ро­ва­нии ра­бо­ты пред­при­ятия. Пусть пред­при­ятие мо­жет вы­пус­кать $n$ ви­дов про­дук­ции, еди­ни­ца про­дук­ции ви­да $j$ да­ёт при­быль $c_j$, $j=1,...,n$. В про­из-ве ис­поль­зу­ют­ся ре­сур­сы $n$ ви­дов (сы­рьё, вре­мя ра­бо­ты стан­ков, ра­бо­чая си­ла, энер­гия и т. п.). Рас­ход ре­сур­са $i$ на про­из-во еди­ни­цы про­дук­ции ви­да $j$ со­став­ля­ет $a_{ij}$. Об­щий ре­сурс ви­да $i$ ог­ра­ни­чен ве­ли­чи­ной $b_i$, $i= 1, ..., m$. Тре­бу­ет­ся оп­ре­де­лить про­из­водств. план (про­грам­му; от­сю­да назв.), т. е. най­ти объё­мы вы­пус­ка $x_j⩾0$ по ка­ж­до­му из ви­дов про­дук­ции с тем, что­бы бы­ли вы­пол­не­ны ог­ра­ни­че­ния (2), а сум­мар­ная при­быль (1) бы­ла мак­си­маль­ной.

Функ­цию (1) в Л. п. при­ня­то на­зы­вать це­ле­вой функ­ци­ей (кри­те­ри­ем оп­ти­маль­но­сти, кри­те­ри­ем эф­фек­тив­но­сти), век­тор $x= (x_1,...,x_n)$, удов­ле­тво­ряю­щий ус­ло­ви­ям (2), (3), на­зы­ва­ет­ся до­пус­ти­мым ре­ше­ни­ем или пла­ном, а мно­же­ст­во век­то­ров $x$, оп­ре­де­ляе­мое ус­ло­вия­ми (2), (3), на­зы­ва­ет­ся до­пус­ти­мым мно­же­ст­вом или мно­же­ст­вом пла­нов. До­пус­ти­мое ре­ше­ние $x^*$, дос­тав­ляю­щее мак­си­мум це­ле­вой функ­ции (1), на­зы­ва­ет­ся оп­ти­маль­ным. Ещё од­ним при­ме­ром при­клад­ных за­дач Л. п. яв­ля­ет­ся транс­порт­ная за­да­ча.

В за­да­чах Л. п. бо­лее об­ще­го ви­да по срав­не­нию с (1)–(3) не­ко­то­рые (или все) из ус­ло­вий (2) мо­гут быть ра­вен­ст­ва­ми, а на не­ко­то­рые (ли­бо на все) пе­ре­мен­ные $x_j$ не на­ла­га­ют­ся ус­ло­вия не­от­ри­ца­тель­но­сти. Лю­бая за­да­ча Л. п. мо­жет быть при­ве­де­на к эк­ви­ва­лент­ной за­да­че ви­да (1)–(3). В не­ко­то­рых за­да­чах Л. п. воз­ни­ка­ет ог­ра­ни­че­ние, свя­зан­ное с це­ло­чис­лен­но­стью ве­ли­чин $x_1,...,x_n$. В этом слу­чае го­во­рят о за­да­чах це­ло­чис­лен­но­го ли­ней­но­го про­грам­ми­ро­ва­ния.

За­да­чей Л. п., двой­ст­вен­ной за­да­че (1)–(3), на­зы­ва­ет­ся за­да­ча ми­ни­ми­за­ции функ­ции $$\sum_{i=1}^{m}b_iy_i\tag4$$при ус­ло­ви­ях$$\sum_{i=1}^ma_{ij}y_i⩾c_j,\;j=1,\:...,\:n,\tag5$$$$y_i⩾0,\; i=1,\:...,\:m.\tag6$$

За­да­чи (1)–(3) и (4)–(6) ли­бо обе име­ют ре­ше­ния, ли­бо обе не­раз­ре­ши­мы. Зна­че­ния це­ле­вых функ­ций (1) и (4) на ре­ше­ни­ях сов­па­да­ют.

Од­ним из осн. ме­то­дов ре­ше­ния за­дач Л. п. яв­ля­ет­ся сим­плекс­ный ме­тод. Его идея со­сто­ит в сле­дую­щем: до­пус­ти­мое мно­же­ст­во пла­нов, за­да­вае­мое ог­ра­ни­че­ния­ми (2) и (3), пред­став­ля­ет со­бой вы­пук­лое мно­го­гран­ное мно­же­ст­во; ес­ли оно ог­ра­ни­че­но, то оно яв­ля­ет­ся вы­пук­лым мно­го­гран­ни­ком. Ес­ли за­да­ча Л. п. име­ет ре­ше­ние, то су­ще­ст­ву­ет вер­ши­на $x^*$ это­го мно­го­гран­ни­ка, яв­ляю­щая­ся оп­ти­маль­ным пла­ном. Сим­плекс­ный ме­тод со­сто­ит в на­прав­лен­ном пе­ре­бо­ре, при ко­то­ром зна­че­ния це­ле­вой функ­ции воз­рас­та­ют от вер­ши­ны к вер­ши­не. Ка­ж­дой вер­ши­не со­от­вет­ст­ву­ет сис­те­ма урав­не­ний, по­лу­чае­мая из сис­те­мы не­ра­венств (2), (3), и вы­чис­ли­тель­ная про­це­ду­ра сим­плекс­но­го ме­то­да со­сто­ит в по­сле­до­ва­тель­ном ре­ше­нии сис­тем ли­ней­ных ал­геб­ра­ич. урав­не­ний. Про­сто­та ал­го­рит­ма де­ла­ет этот ме­тод удоб­ным для реа­ли­зации. Для ре­ше­ния за­дач Л. п. при­меня­ют­ся так­же ите­ра­ци­он­ные ме­то­ды по­строе­ния по­сле­до­ва­тель­но­сти при­бли­же­ний, пре­де­лом ко­то­рой яв­ля­ет­ся оп­ти­маль­ный план.

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

Раз­ви­тие Л. п. на­ча­лось в 1939 с ис­сле­до­ва­ний Л. В. Кан­то­ро­ви­ча, в ко­то­рых он пред­ло­жил уни­вер­саль­ный ма­те­ма­тич. ме­тод для ре­ше­ния за­дач эко­но­мич. ха­рак­те­ра – та­ких, как за­да­ча о наи­луч­шей за­груз­ке ма­шин, о рас­крое ма­те­риа­лов с наи­мень­ши­ми рас­хо­да­ми, о рас­пре­де­ле­нии гру­зов по не­сколь­ким ви­дам транс­пор­та. Во 2-й пол. 1940-х гг. Т. Куп­манс об­ра­щал вни­ма­ние ма­те­ма­ти­ков на за­да­чи, сво­дя­щие­ся к на­хо­ж­де­нию экс­тре­му­мов ли­ней­ных функ­ций на мно­го­гран­ни­ках. В это же вре­мя амер. ма­те­ма­тик Дж. Дан­циг (ввёл тер­мин «Л. п.») и Кан­то­ро­вич не­за­ви­си­мо друг от дру­га пред­ло­жи­ли эф­фек­тив­ный ме­тод ре­ше­ния та­ких за­дач, по­лу­чив­ший назв. сим­плекс­но­го ме­то­да. Этот и др. ме­то­ды ре­ше­ния за­дач Л. п. тре­бу­ют боль­шо­го объ­ё­ма вы­чис­ле­ний; они ста­ли эф­фек­тив­но реа­ли­зо­вы­вать­ся толь­ко с по­яв­ле­ни­ем бы­ст­ро­дей­ст­вую­щих ЭВМ в нач. 1950-х гг.

Лит.: Кан­то­ро­вич Л. В. Ма­те­ма­ти­че­ские ме­то­ды ор­га­ни­за­ции пла­ни­ро­ва­ния про­из­вод­ст­ва. М., 1939; Дан­циг Дж. Ли­ней­ное про­грам­ми­ро­ва­ние, его при­ме­не­ния и обоб­ще­ния. М., 1966; Юдин Д. Б., Голь­штейн Е. Г. Ли­ней­ное про­грам­ми­ро­ва­ние. М., 1969; Ва­силь­ев Ф. П., Ива­ниц­кий А. Ю. Ли­ней­ное про­грам­ми­ро­ва­ние. 3-е изд. М., 2008; Кар­ма­нов В. Г. Ма­тема­ти­че­ское про­грам­ми­ро­ва­ние. 6-е изд. М., 2008.

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