Линейное программирование: Учебное пособие

Л и н ейн ое п р огр а м м и р ов а н и е

§1. О бщ аяп о ст ан о в к а задачи лин ейн о го п ро грам м иро в ан ия Граф ическ о е реш ен ие задач лин ейн о го п ро грам м иро в ан ия За да чей ли н ейн ого п р огр а м м и р ов а н и я (ЗЛ П ) н а зы в а ет с я за да ча н а хоn ж ден и я в в ект ор н ом п р ос т р а н с т в е R т а когов ект ор а x * , кот ор ы йобес п ечи в а ет оп т и м а льн ое (м а кс и м а льн ое и ли м и н и м а льн ое) зн а чен и е ли н ейн ой фун кци и

n

L( x ) = ∑ c j x j

и

при

эт ом

п р и н а длеж и т

н екот ор ой обла с т и

j =1

Ω ⊆ R n , за да н н ойли н ейн ы м и огр а н и чен и ям и n

∑ aij x j ≤ ( ≥, =) bi , j =1

i = 1,..., m

x j ≥ 0 (≤, н ет т р ебов а н и я н а зн а к), j = 1,..., n . Ф у нкцию L(x) на зы в а ю т целев ой ф у нкцией ЗЛ П , ее оп т има льное зна чение обозна ча ю т L* . М нож ест в о Ω ⊆ R n на зы в а ю т доп у ст имы м множ ест в ом, его элемент ы - доп у ст имы мив ект ор а ми, а в ект ор x * - р еш ением за да чи(оп т има льной т очкой). П р еж де чем р а с с м а т р и в а т ь м ет оды р еш ен и я общ ей за да чи ли н ейн ого n п р огр а м м и р ов а н и я в R , р а с с м от р и м а лгор и т м гр а фи чес когом ет ода , кот ор ы йи с п ользует с я в

R2 для р еш

ен и я за да чи с ледующ егов и да : c1x1 + c2 x 2 → max( min )

ai1x 1 + ai 2 x 2 ≤ ( ≥, = ) bi , i = 1,..., m x1 , x 2 ≥ 0 (≤, нет т р ебов а ния на зна к ) . 1. П ос т р оен и е доп ус т и м огом н ож ес т в а . За м ет и м , чт о каж дое огр а н и чен и е за да чи оп р еделяет н екот ор ую п олуп лос кос т ь (в с луча е н ер а в ен с т в а ) и ли п р ям ую (в с луча е р а в ен с т в а ). Доп ус т и м ы м м н ож ес т в ом яв ляет с я п ер ес ечен и е эт и х п олуп лос кос т ейи п р ям ы х. Та ки м обр а зом , для п ос т р оен и я доп ус т и м огом н ож ес т в а н уж н о: а ) для каж догоогр а н и чен и я н а р и с ов а т ь п р ям ую, с оот в ет с т в ующ ую р а в ен с т в у ai1x1 + ai2 x 2 = bi , i = 1,..., m ; б) ес ли огр а н и чен и е за да ет с я н ер а в ен с т в ом в и да ai1x 1 + ai2 x 2 ≤ bi и ли ai1x 1 + ai2 x 2 ≥ bi , т о оп р едели т ь п олуп лос кос т ь, за да в а ем ую да н н ы м н ер а в ен с т в ом . Эт о легко с дела т ь, ес ли п одс т а в и т ь в н его коор ди н а т ы т очки , н е р а с п олож ен н ой н а с оот в ет с т в ующ ей п р ям ой. Ес ли н ер а в ен с т в о ока зы в а ет с я с п р а в едли в ы м , т ов ы бр а т ь п олуп лос кос т ь, с одер ж а щ ую да н н ую т очку, в п р от и в н ом с луча е - в ы бр а т ь п р от и в оп олож н ую п олуп лос кос т ь. в ) н а йт и п ер ес ечен и е п олучен н ы х п олуп лос кос т ейи п р ям ы х. 2. Реш ен и е за да чи п ут ем а н а ли за доп ус т и м огом н ож ес т в а и п ов еден и я целев ойфун кци и н а эт ом м н ож ес т в е. 3

Л и н ейн ое п р огр а м м и р ов а н и е

а ) П ус т ь доп ус т и м ое м н ож ес т в о ока за лос ь п ус т ы м . Дела ет с я в ы в од: за да ча р еш ен и йн е и м еет , п ос кольку н ет н и одн ойдоп ус т и м ойт очки . б) П ус т ь доп ус т и м ое м н ож ес т в о оказа лос ь н е п ус т ы м . Вы бр а т ь дв а п р ои зв ольн ы х чи с ла d1 и d2 , d1 > d2 . На р и с ов а т ь ли н и и ур ов н я целев ой фун кци и , с оот в ет с т в ующ и е в ы бр а н н ы м кон с т а н т а м , т .е. п р ям ы е в и да c1x 1 + c2 x 2 = d1 и c1x 1 + c2 x 2 = d2 (эт о п а р а ллельн ы е п р ям ы е, в с е т очки кот ор ы х обес п ечи в а ют зн а чен и я целев ой фун кци и , р а в н ы е с оот в ет с т в ен н о d1 и d2 ). За фи кс и р ов а т ь н а п р а в лен и е ув ели чен и я зн а чен и й целев ой фун кци и от п р ям ой с п р а в ой ча с т ью, р а в н ой d2 , кп р ям ой с п р а в ой ча с т ью, р а в н ой d1 . П ер едв и га т ь п р ям ую c1x 1 + c2 x 2 = d п а р а ллельн о с а м ойс ебе п о доп ус т и м ом у м н ож ес т в у в обозн а чен н ом н а п р а в лен и и (в п р от и в оп олож н ом н а п р а в лен и и ) до п олучен и я м а кс и м а льн ого зн а чен и я d * (м и н и м а льн ого зн а чен и я d * ), п р и кот ор ом п р ям а я c1x 1 + c2 x 2 = d п ер ес ека ет доп ус т и м ое м н ож ес т в о. За фи кси р ов а т ь н а гр а фи ке т очки доп ус т и м ого м н ож ес т в а , обес п ечи в а ющ и е м а кси м а льн ое (м и н и м а льн ое) зн а чен и е целев ой фун кци и и ли убеди т ьс я, чт о т а ки х т очекн ет . Ес ли доп ус т и м ое м н ож ес т в о огр а н и чен о (яв ляет с я м н огоугольн и ком ), т о в озм ож н ы дв а р а зли чн ы х от в ет а : р еш ен и е еди н с т в ен н ои ли р еш ен и й бес чи с лен н ое м н ож ес т в о. П р и еди н с т в ен н ом р еш ен и и н а гр а фи ке за фи кс и р ов а н а еди н с т в ен н а я т очка (в ер ш и н а м н огоугольн и ка ), яв ляющ а яс я п ер ес ечен и ем н екот ор ы х п р ям ы х. Необходи м о в ы п и с а т ь с оот в ет с т в ующ и е ур а в н ен и я п р ям ы х и , р еш и в с и с т ем у п олучен н ы х ур а в н ен и й, н а йт и т очку р еш ен и е за да чи . В с луча е бес чи с лен н ого м н ож ес т в а р еш ен и й п олучен от р езокп р ям ой, в с е т очки кот ор ого обес п ечи в а ют м а кс и м а льн ое зн а чен и е целев ой фун кци и . Ср еди эт и х т очекес т ь в ер ш и н ы м н огоугольн и ка . К оор ди н а т ы в ер ш и н от ы с ки в а ют с я т а к, ка куказа н о в п р еды дущ ем с луча е. Ес ли доп ус т и м ое м н ож ес т в о н е огр а н и чен о, т о в озм ож н ы т е ж е дв е с и т уа ци и , чт о и в с луча е огр а н и чен н ого м н ож ес т в а , и , кр ом е т ого, в озм ож ен с луча йот с ут с т в и я р еш ен и йи з-за н еогр а н и чен н ос т и зн а чен и йцелев ойфун кци и н а доп ус т и м ом м н ож ес т в е. И з а н а ли за гр а фи чес кого м ет ода р еш ен и я м ож н о с дела т ь в ы в оды , коn т ор ы е яв ляют с я с п р а в едли в ы м и и для за да ч и з R . 1. Доп ус т и м ое м н ож ес т в о за да чи ли н ейн ого п р огр а м м и р ов а н и я, ес ли он о н е п ус т о, яв ляет с я м н огогр а н н ы м огр а н и чен н ы м и ли н еогр а н и чен н ы м в ы п уклы м м н ож ес т в ом . 2. Ес ли в за да че ес т ь р еш ен и е (оп т и м а льн а я т очка ), т о с р еди в ер ш и н доп ус т и м ого м н ож ес т в а т а кж е ес т ь р еш ен и е. Ч а с т ь оп т и м а льн ы х т очек м ож н ои с ка т ь, п ер еби р а я т ольков ер ш и н ы доп ус т и м огом н ож ес т в а . П р ои ллюс т р и р уем р а с с м от р ен н ы йгр а фи чес ки йм ет од н а п р и м ер а х. П р и м ер 1. Реш и т ь гр а фи чес ки с ледующ ую за да чу ли н ейн ого п р огр а м м и р ов а н и я 4 x 1 + 2x 2 → max 4

Л и н ейн ое п р огр а м м и р ов а н и е

(1) 2x 1 + 3x 2 ≤ 18 − x 1 + 3x 2 ≤ 9 (2) 2x 1 − x 2 ≤ 10 (3) x1 ≥ 0, x 2 ≥ 0 . Реш ен и е. Ст р ои м обла с т ь доп ус т и м ы х р еш ен и й в с оот в ет с т в и и с ш а гом 1 оп и с а н н ого в ы ш е а лгор и т м а . В р езульт а т е п олучи м в ы п уклы й м н огоугольн и к (р и с 1.)

1

2 d=28

X2

.

3 X*max

X1 X1 d=0

Ри с .1

Следуя п ун кту 2 р а с с м от р ен н ого а лгор и т м а , с т р ои м ли н и и ур ов н я целев ой фун кци и 4 x 1 + 2x 2 = d и фи кси р уем н а п р а в лен и е ув ели чен и я зн а чен и я целев ойфун кци и п р и п ер еходе от одн ойли н и и ур ов н я кдр угой. П ер ем ещ а я п р ям ую 4 x 1 + 2x 2 = d п а р а ллельн о с а м ой с ебе в н а йден н ом н а п р а в лен и и , п ока он а будет с охр а н ят ь общ и е т очки с доп ус т и м ой обла с т ью, н а йдем , чт о в * кр а йн ем в озм ож н ом п олож ен и и ли н и я ур ов н я п р ойдет чер ез т очку x max . Эт ом у п олож ен и ю ли н и и ур ов н я и с оот в ет с т в ует d = dmax . Для н а хож ден и я * коор ди н а т т очки x max н еобходи м ор еш и т ь с и с т ем у ур а в н ен и й: 2x1 + 3x 2 = 18 .  2x1 − x 2 = 10

* В р езульт а т е п олучи м и с ком ое оп т и м а льн ое р еш ен и е X max = ( 6,2) с

зн а чен и ем целев ойфун кци и L*max = 28 . П р и м ер 2. Реш и т ь гр а фи чес ки с ледующ ую за да чу: 5

Л и н ейн ое п р огр а м м и р ов а н и е

2 x 1 + 4 x 2 → max 3 x 1 + 2x 2 ≥ 11 (1) − 2x1 + x 2 ≤ 2 (2) x1 − 3x 2 ≤ 0 (3) x 1 ≥ 0, x 2 ≥ 0 . Реш ен и е. П ер в ы й эт а п - п ос т р оен и е доп ус т и м ойобла с т и - в ы п олн яет с я т а кж е ка к и в п р еды дущ ей за да че. В р езульт а т е п олуча ем н еогр а н и чен н ую м н огогр а н н ую обла с т ь.

1

Z*max= +

2

d=22

3 X2

. X min *

X1 d=0

Ри с . 2.

На в т ор ом эт а п е р еш ен и я - п а р а ллельн ом п ер ем ещ ен и и ли н и и ур ов н я в н а п р а в лен и и в озр а с т а н и я целев ой фун кци и ус т а н а в ли в а ем , чт о т а кое п ер ем ещ ен и е м ож н о п р ои зв оди т ь н еогр а н и чен н о. Следов а т ельн о, целев а я фун кци я н еогр а н и чен н а с в ер ху, т .е. Lmax = ∞ , а с а м а за да ча ли н ейн ого п р огр а м м и р ов а н и я н ер а зр еш и м а . За м ет и м , чт оес ли п р и т ех ж е и с ходн ы х да н н ы х т р ебов а лос ь бы целев ую фун кци ю м и н и м и зи р ов а т ь, т о п олучи ли бы оп т и м а льн ое * р еш ен и е в т очке x min = (3,1) с L*min = 10 . П р и м ер 3. Реш и т ь за да чу

Реш ен и е.

− x 1 + x 2 → max − x 1 + x 2 ≤ 3 (1) x 1 − 2x 2 ≤ 3 (2) x 1 ≥ 0, x 2 ≥ 0 . Доп ус т и м а я обла с т ь в да н н ойза да че и м еет в и д

6

Л и н ейн ое п р огр а м м и р ов а н и е

Z*max=3

.

X2max X2 X1max 1

.

d=1

d=0 X1

2

р и с 3. И з р и с ун ка в и дн о, чт одоп ус т и м ое м н ож ес т в он еогр а н и чен н о. Л и н и и ур ов н я целев ойфун кци и п а р а ллельн ы п р ям ой − x1 + x 2 = 3 , с оот в ет с т в ующ ей п ер в ом у огр а н и чен и ю. П ер ем ещ а я ли н и и ур ов н я в н а п р а в лен и и в озр а с т а н и я целев ой фун кци и , п олуча ем , чт о ли н и я ур ов н я с м а кси м а льн о в озм ож н ы м зн а чен и ем целев ой фун кци и с ов п а да ет с п р ям ой − x1 + x 2 = 3 . Та ки м обр а зом , целев а я фун кци я дос т и га ет с в оегом а кси м а льн огозн а чен и я L*max = 3 в о

в с ех т очка х луча , в ы ходящ его и з т очки x1max = (0,3) . За да ча и м еет бес чи с лен н ое м н ож ес т в о р еш ен и й. Для т ого чт обы в ы п и с а т ь р еш ен и е в общ ем в и 2 де, в озьм ем н а луче ещ е одн у т очку x max = (1,4 ) . У р а в н ен и е луча за п и с ы в а ет с я с ледующ и м обр а зом : * 2 x max = (1 − λ )x1max + λx max ,λ ∈ [0, ∞ ) . Та ки м обр а зом , любое р еш ен и е да н н ой за да чи за п и с ы в а ет с я в в и де * x max = (λ ,3 + λ ),λ ∈ [0,∞ ) . П р и м ер 4. Реш и т ь гр а фи чес ки за да чу 3x 1 + 3x 2 → min x1 + x 2 ≥ 2 (1) − 2 x1 + x 2 ≥ 2 (2) x1 − x 2 ≥ 0 (3) Реш ен и е. Доп ус т и м ое м н ож ес т в о да н н ойза да чи п ус т о. Эт о в и дн о и з с ледующ егор и с ун ка

7

Л и н ейн ое п р огр а м м и р ов а н и е

1

X2 X2

2

3

X1 X1

Ри с 4. П оэт ом у да н н а я за да ча н ер а зр еш и м а . П р и м ер 5. Реш и т ь гр а фи чес ки за да чу x 1 + 2x 2 → max − x1 + x 2 ≤ 2 (1) x1 + 2 x 2 ≤ 7 (2) 0 ≤ x1 ≤ 3, x 2 ≥ 0 Реш ен и е. Доп ус т и м ы м м н ож ес т в ом в да н н ой за да че яв ляет с я в ы п уклы йм н огогр а н н и к(р и с . 5). X1max

.

. X max

X2

2

d=4 X1 d=0

Ри с .5 Л и н и и ур ов н я целев ой фун кци и п а р а ллельн ы п р ям ой, с оот в ет с т в ующ ей огр а н и чен и ю (2). П р ов одя р а с с уж ден и я, а н а логи чн ы е р а с с уж ден и ям в п р и м ер е 3, п олучи м , чт о целев а я фун кци я дос т и га ет с в оего м а кси м а льн ого зн а чен и я L*max = 7 в о в с ех т очка х от р езка, с оеди н яющ егот очки x1max = (1,3) и

8

Л и н ейн ое п р огр а м м и р ов а н и е 2 x max = (3,2) . За да ча и м еет бес чи с лен н ое м н ож ес т в о р еш ен и й, кот ор ое за п и с ы в а ет с я с ледующ и м обр а зом * 2 x max = (1 − λ )x 1max + λx max , λ ∈ [0,1]. Та ки м обр а зом , любое р еш ен и е да н н ой за да чи * x max = (1 + 2λ ,3 − λ ), λ ∈ [0,1] .

и м еет

вид

Задачи длясам о ст о ят ельн о го реш ен ия 1.Реш и т ь гр а фи чес ки : 1) x 1 − 2x 2 → max x1 + x 2 ≥ 2 x1 − x 2 ≤ 1 x 1 − 2x 2 ≤ 0 x 1 ≥ 0, x 2 ≥ 0 . 3) 5x 1 + 3x 2 → max 3x1 + 5x 2 ≤ 15 5x 1 + x 2 ≤ 10 x 1 ≥ 0, x 2 ≥ 0 5) 2 x 1 + 3x 2 → min 3 x 1 + 2x 2 ≥ 6 x1 + 4x 2 ≥ 4 x 1 ≥ 0, x 2 ≤ 0

2) x 1 + 3x 2 → max x1 − x 2 ≥ 0 2x1 + x 2 ≤ 2 x1 − x 2 ≤ 1 x 1 ≥ 0, x 2 ≥ 0 4) 2 x 1 + 3x 2 → max 3x1 + 2x 2 ≤ 6 x1 + x 2 ≥ 6 x 1 ≥ 0, x 2 ≥ 0 6) x 1 + x 2 → max x1 + 2x 2 ≤ 10 x1 + 2x 2 ≥ 2 2 x 1 + x 2 ≤ 10 x1 ≥ 0 .

2. О п р едели т ь п р ом еж ут ки зн а чен и й λ , п р и кот ор ы х р еш ен и е будет с ов п а да т ь с одн ойи т ойж е в ер ш и н ойобла с т и доп ус т и м ы х р еш ен и й. В каки х п р ом еж ут ка х за да ча н е и м еет р еш ен и й? П р и ка ки х зн а чен и ях λ будет бес чи с лен н ое м н ож ес т в ор еш ен и й? 1) 2x 1 + λx 2 → max 2) − x 1 + λx 2 → max − x1 + x 2 ≤ 3 − x1 + x 2 ≤ 2 x 1 + 2x 2 ≤ 12 x 1 − 2x 2 ≤ 3 3x 1 − x 2 ≤ 15 x 1 ≥ 0, x 2 ≤ 0 x 1 ≥ 0, x 2 ≤ 0 3) 2x1 + x 2 → max 3) x1 + 2x 2 → max x 1 − 2x 2 ≤ 4 2x 1 + x 2 ≥ 9 x1 − x 2 ≤ 6 x 1 − 3x 2 ≤ 1

9

Л и н ейн ое п р огр а м м и р ов а н и е

λx 1 + x 2 ≤ 3 λx 1 − x 2 ≤ −2 x 1 ≥ 0, x 2 ≤ 0 x 1 ≥ 0, x 2 ≤ 0 . 3. П р и в ес т и п р и м ер гр а фи чес кой и н т ер п р ет а ци и и с ос т а в и т ь н а ос н ов а н и и п олучен н ого чер т еж а м а т ем а т и чес кую за п и с ь за да чи , обла да ющ ей с ледующ и м и с в ойс т в а м и : 1) и м еет с я еди н с т в ен н ое оп т и м а льн ое р еш ен и е для за да чи н а м и н и м ум и для за да чи н а м а кс и м ум ; 2) м а кси м а льн ое зн а чен и е целев а я фун кци я дос т и га ет в бес чи с лен н ом м н ож ес т в е т очек, а м и н и м а льн ое зн а чен и е в еди н с т в ен н ойт очке; 3) н а м и н и м ум за да ча н ер а зр еш и м а и з-за н еогр а н и чен н ос т и целев ой фун кци и , а м а кс и м а льн ое зн а чен и е дос т и га ет с я в еди н с т в ен н ойт очке; 4) н а м а кс и м ум и н а м и н и м ум за да ча н ер а зр еш и м а и з-за н еогр а н и чен н ос т и целев ойфун кци и ; 5) м и н и м а льн ое зн а чен и е целев ой фун кци и дос т и га ет с я в бес чи с лен н ом м н ож ес т в е т очек, и з кот ор ы х т олькоодн а яв ляет с я в ер ш и н ой. §2. Разн ы е ф о рм ы зап иси задачи лин ейн о го п ро грам м иро в ан ия В §1 п р и в еден а общ а я п ос т а н ов ка за да чи ли н ейн огоп р огр а м м и р ов а н и я (ЗЛ П ). Ч а с т о для удобс т в а и с с ледов а н и я и п р и п ос т р оен и и м ет ода р еш ен и я фи кс и р ует с я т а и ли и н а я за п и с ь за да чи . Та к, ча с т ои с п ользует с я за да ча в с ледующ ейфор м е: n

∑ c j x j → max j =1

n

∑ aij x j j =1

≤ bi , i = 1,..., m

x j ≥ 0,

j = 1,..., n .

Та кая фор м а за п и с и ЗЛ П н а зы в а ет с я с т а н да р т н ойи ли с и м м ет р и чн ойфор м ой за да чи ли н ейн ого п р огр а м м и р ов а н и я. К р ом е т ого, в ы деляют ка н он и чес кую фор м у за п и с и ЗЛ П : n

∑ c j x j → max j =1

n

∑ aij x j j =1

= bi , bi ≥ 0, i = 1,..., m

x j ≥ 0, j = 1,..., n . Вн е за в и с и м ос т и от т ого, ка кза п и с а н а и с ходн а я за да ча , он а м ож ет бы т ь п ер еп и с а н а в любойж ела т ельн ойфор м е. П р и эт ом с ущ ес т в уют п р а в и ла , п озв оляющ и е эт ос дела т ь экв и в а лен т н ы м обр а зом . С эт ойцелью обс уди м 10

Л и н ейн ое п р огр а м м и р ов а н и е

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

n

∑ aij x j j =1

= bi м ож н оза п и с а т ь в в и де с и с т ем ы

дв ух н ер а в ен с т в n

∑ a ij x j j =1

≤ bi

n

∑ aij x j ≥ bi . j =1

4. О т огр а н и чен и й н ер а в ен с т в м ож н о п ер ейт и кр а в ен с т в а м , доба в ляя и ли от н и м а я н еот р и ца т ельн ы е н ов ы е п ер ем ен н ы е, кот ор ы е в да льн ейш ем будут н а зы в а т ьс я доп олнит ельны ми п ер ем ен н ы м и . Та к, н ер а в ен с т в о n

∑ a ij x j j =1

n

∑ aij x j

≤ bi экв и в а лен т н о с и с т ем е

j =1

n

+ u i = bi , u i ≥ 0 . А н а логи чн о

н ер а в ен с т в о ∑ aij x j ≥ bi экв и в а лен т н ос и с т ем е j =1

n

∑ aij x j j =1

− u i = bi , u i ≥ 0 .

5. О бес п ечи т ь ус лов и е н еот р и ца т ельн ос т и п ер ем ен н ойм ож н о, и с п ользуя очев и дн ы йфа кт : любое чи с ло м ож ет бы т ь п р едс т а в лен о в в и де р а зн ос т и дв ух н еот р и ца т ельн ы х чи с ел: x = x ′ − x ′′, x ′ ≥ 0, x ′′ ≥ 0 . Ес ли в за да че п р и с ут с т в ов а лот р ебов а н и е x j ≤ 0 , ос ущ ес т в ляет с я за м ен а x j = − x ′j , x ′j ≥ 0 . В ка чес т в е п р и м ер а с фор м ули р уем фа кт экв и в а лен т н ос т и дв ух с ледующ и х за да ч ли н ейн огоп р огр а м м и р ов а н и я: n

n

∑ c j x j → min

− ∑ c j x j → max

j =1 n

∑ aij x j ≤ bi , j =1

x j ≥ 0,

j =1

i = 1, m

n

∑ aij x j

(1)

j =1

j = 1, n

+ u i = bi , i = 1, m (2)

x j ≥ 0, j = 1, n, u i ≥ 0, i = 1, m

11

Л и н ейн ое п р огр а м м и р ов а н и е

У т в ер ж ден и е Ес ли x * яв ляет с я р еш ен и ем за да чи (1), т о н а йдет с я т а кое u * ≥ 0 , чт о x * , u * яв ляет с я р еш ен и ем за да чи (2). С др угойс т ор он ы , ес ли ( x€, u€) яв ляет с я р еш ен и ем за да чи (2), т о x€ яв ляет с я р еш ен и ем за да чи (1).

(

)

В с в язи с т ем , чт о ос н ов н ойм ет од р еш ен и я ЗЛ П - с и м п лексн ы йм ет од п р едн а зн а чен для р еш ен и я за да ч в ка н он и чес койфор м е, м ы п р ои ллюс т р и р уем р а бот у оп и с а н н ы х в ы ш е п р а в и л н а п р и м ер е п р и в еден и я за да чи кка н он и чес койфор м е. П р и м ер 1. П ус т ь и с ходн а я за да ча за да н а в в и де 3 x1 + 2 x 2 − x 3 → min п р и огр а н и чен и ях 2 x1 − x 2 + 3 x 3 ≥ 4 − x1 + x 2 − x 3 ≤ 2 − x 2 − x3 = −20 x 2 ≥ 0, x 3 ≤ 0 . П р и в ес т и да н н ую за да чу кка н он и чес койфор м е. Реш ен и е. 1. У м н ож и м целев ую фун кци ю н а -1. В р езульт а т е п олучи м − 3 x1 − 2 x 2 + x 3 → max . 2. И з лев ойча с т и п ер в огон ер а в ен с т в а в ы чт ем н еот р и ца т ельн ую п ер ем ен н ую u1 и п ер ейдем когр а н и чен и ям 2 x1 − x 2 + 3 x 3 − u1 = 4, u1 ≥ 0 . 3. К лев ойча с т и в т ор огон ер а в ен с т в а доба в и м н еот р и ца т ельн ую п ер ем ен н ую u 2 и п ер ейдем когр а н и чен и ям − x1 + x 2 − x 3 + u 2 = 2, u 2 ≥ 0 . 4. У м н ож и м обе ча с т и т р ет ьегор а в ен с т в а н а -1 x 2 + x 3 = 20 . 5. О с ущ ес т в и м за м ен у п ер ем ен н ы х x1 = x1' − x1'' , x1' ≥ 0, x1'' ≥ 0.

x3 = − x3′ , x3' ≥ 0 В р езульт а т е за да ча п р и н и м а ет ка н он и чес ки йв и д − 3 x1' + 3 x1'' − 2 x 2 − x 3' → max 2 x1' − 2 x1'' − x 2 − 3x 3' − u1 = 4 − x1' + x1'' + x 2 + x3' + u 2 = 2 x 2 − x3' = 20 x1' ≥ 0, x1'' ≥ 0, x 2 ≥ 0, x 3' ≥ 0, u1 ≥ 0, u 2 ≥ 0 . За м ет и м , чт оп ос ледов а т ельн ос т ь п р и м ен ен и я п р а в и л п р и в еден и я кка н он и чес койфор м е н е с ущ ес т в ен н а и м ож ет бы т ь любой. 12

Л и н ейн ое п р огр а м м и р ов а н и е

В за ключен и е от м ет и м , чт о за м ен а п ер ем ен н ы х п ор ож да ет н ееди н с т в ен н ос т ь р еш ен и я п олучен н ой ка н он и чес кой за да чи да ж е, ес ли и с ходн а я и м ела еди н с т в ен н ое р еш ен и е. Эт от фа кт долж ен бы т ь в ы делен п р и фи кс и р ов а н и и от в ет а . Си м п лексн ы йм ет од п озв оляет эт ос дела т ь, чт обудет от м ечен о в да льн ейш ем п р и оп и с а н и и с оот в ет с т в ующ егоа лгор и т м а . Задачи длясам о ст о ят ельн о го реш ен ия 1. П р и в ес т и кка н он и чес койфор м е с ледующ и е за да чи ли н ейн огоп р огр а м м и р ов а н и я: а ) x 1 − x 2 + 3x 3 → min б) 2 x 1 + x 2 − x 3 → max 2 x 1 − x 2 + 3x 3 ≤ 5 x 1 − 2x 2 + x 3 ≥ 4 x1 + 2x 3 = 8 x 1 + x 2 − 3x 3 ≤ 9 − x 1 − 2x 2 ≥1 x 1 + 3x 2 + 2x 3 = 10 x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0 ; x 1 ≥ 0, x 3 ≥ 0 ; в ) 2 x 1 − x 2 + 3x 3 + x 4 − 2 x 5 → min x 1 + 2x 2 − x 3 − 2x 4 + x 5 = − 5 − 2x 2 + 4 x 3 + x 4 ≤4 x 2 ≥ 0, x 3 ≥ 0, x 5 ≥ 0 ; г) x 1 + 2x 2 + 3 x 3 + 2x 4 + x 5 → max − 3 x1 + x 2 + 4 x3 − 2 x 4 + x5 ≥ 6 x1 − 2 x 2 + 3x3 + x 4 + x5 = 2 x 1 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≤ 0 ; 2. П р и в ес т и кс и м м ет р и чн ой фор м е с ледующ и е за да чи ли н ейн ого п р огр а м м и р ов а н и я: а ) 2 x 1 − x 2 + 3x 3 + x 4 − 2 x 5 → min 2 x 1 − x 2 − 3x 3 + x 4 − x 5 = 4 x 1 + 2x 2 + 3x 3 + 3x 4 + x 5 = 15 2x 1 − 2x 2 − x 3 − 6x 4 + 2x 5 = 8 x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0 ; б) x 1 − 2x 2 + 2x 3 + x 4 + 2x 5 → max x 1 − x 2 + 2x 3 − 3x 4 + x 5 = − 2 − x 1 + 2x 2 − x 3 + 2x 4 + 7x 5 = 3 2x 1 + 3x 2 − 4 x 3 + x 4 − x 5 ≤ 6 x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0

13

Л и н ейн ое п р огр а м м и р ов а н и е

§3. А лго рит м п еребо ра базисн ы хреш ен ий сист ем лин ейн ы хурав н ен ий В § 2 бы ла в в еден а кан он и чес ка я фор м а ЗЛ П , кот ор а я в м а т р и чн ом в и де м ож ет бы т ь п ер еп и с а н а с ледующ и м обр а зом : z ( x) = c T x → max (1) Ax = b , (b ≥ 0) (2) x ≥ 0, (3) T T T где c = ( c1 ,..., c n ), x = ( x1 ,...., x n ), b = (b1 ,...., bm ), A = ( a ij ) , i = 1, m, j = 1, n О чев и дн о, чт о р еш ен и я за да чи Л П (1) - (3) н а ходят с я с р еди р еш ен и йс и с т ем ы ли н ейн ы х ур а в н ен и йAx = b. Ра с с м от р и м с п ос об п ер ебор а р еш ен и йда н н ойс и с т ем ы для с луча я, когда р а н г м а т р и цы r(A) = m. И з кур с а ли н ейн ойа лгебр ы и зв ес т н о, чт о с и с т ем а (2) с п ом ощ ью п р еобр а зов а н и йЖ ор да н а - Г а ус с а м ож ет бы т ь п р и в еден а кв и ду ~ E x + A~ x =b, (4) ~ где E - еди н и чн а я м а т р и ца р а зм ер а m× m , м а т р и ца A и м еет р а зм ер ы m×(n-m) и элем ен т ы a~ , п олучен н ы е в р езульт а т е п р еобр а зов а н и й Ж ор да н а -Г а ус с а , ij

b - в ект ор р а зм ер а m, п олучен н ы йи з в ект ор а b в с ледс т в и е п р еобр а зов а н и й. Си с т ем а ур а в н ен и й (4) м ож ет бы т ь п ер еп и с а н а в коор ди н а т н ой фор м е с ледующ и м обр а зом : (5) xi = bi − ∑ a~ij ~ x j , i ∈ I , I ∪ J = {1,..., n}, j∈ J

где I - м н ож ес т в о и н дексов за в и с и м ы х п ер ем ен н ы х , J - м н ож ес т в ои н декс ов x с в ободн ы х п ер ем ен н ы х, x =  ~  ∈ R n . Ф ор м ула (5) п р едс т а в ляет с обойфор x м улу общ его р еш ен и я с и с т ем ы (2). На п ом н и м , чт о любое ча с т н ое р еш ен и е с и с т ем ы м ож ет бы т ь п олучен о и з фор м улы общ его р еш ен и я п ут ем фи кс и р ов а н и я любы х зн а чен и йс в ободн ы х п ер ем ен н ы х с п ос ледующ и м в ы чи с лен и ем п о фор м уле (5) зн а чен и й за в и с и м ы х п ер ем ен н ы х. В да льн ейш ем н а с будут и н т ер ес ов а т ь ча с т н ы е р еш ен и я в и да ( xi = bi , i ∈ I , x j = 0, j ∈ J ) , т .е. в ектор ы , с в ободн ы е п ер ем ен н ы е кот ор ы х п олож ен ы р а в н ы м и 0. Та ки е в ектор ы н а зы в а ют с я ба зи с н ы м и р еш ен и ям и с и с т ем ы ли н ейн ы х ур а в н ен и й (2). М а кс и м а льн ое коли чес т в о ба зи с н ы х р еш ен и йн е п р ев ос ходи т в ели чи н ы C nm . П ер ебр а т ь в с е ба зи с н ы е р еш ен и я с и с т ем ы ли н ейн ы х ур а в н ен и йм ож н о, ор га н и зов а в п ер ебор фор м ул общ его р еш ен и я. О чев и дн о, чт о эт о м ож н о ос ущ ес т в и т ь с и с п ользов а н и ем м ет ода Ж ор да н а -Г а ус с а , н а п р и м ер , п о с ледующ ей с хем е. А лго рит м п еребо ра 1. П олучи т ь м ет одом Ж ор да н а -Г а ус с а п р ои зв ольн ую фор м улу общ егор еш ен и я в и да (5). П олож и т ь N=1. 14

Л и н ейн ое п р огр а м м и р ов а н и е

2. За п ом н и т ь м н ож ес т в о I N . П олож и т ь I = I N , J = J N . 3. Вы бр а т ь н ом ер k и з м н ож ес т в а J. За м ен и т ь J н а J\{k}. 4. Вы бр а т ь l ∈ I т а кой, чт о a lk ≠ 0 . Ес ли т а ки х н ом ер ов l в I н ет , т оп ер ейт и к п .7. 5. Ес ли м н ож ес т в о I N \ {l} ∪ {k} уж е р а с с м от р ен о, т о за м ен и т ь I н а I \ {l} и п ер ейт и кп .6, и н а че п ер ейт и кп .8. 6. Ес ли I= Ø т оп олож и т ь I N и п ер ейт и кп .7, и н а че п ер ейт и кп .4. 7. Ес ли J=Ø , т о о ст ан о в - п олучен ы в с е в озм ож н ы е фор м улы общ его р еш ен и я, и н а че п ер ейт и кп .3. 8. О с ущ ес т в и т ь п р еобр а зов а н и я Ж ор да н а -Г а ус с а с н а п р а в ляющ и м элем ен т ом alk до п олучен и я в k-м с т олбце еди н и чн огов ект ор а . За м ен и т ь N н а N+1. П олож и т ь I N = I N \ {l} ∪ {k} . П ер ейт и кп .2 . П р и м ер 1. На йт и ба зи с н ы е р еш ен и я с и с т ем ы ур а в н ен и й.  x1 = 2 − 2 x 2   x 3 = 4 + x2 Реш ен и е. Здес ь I={1,3},J={2}. О фор м и т ь п р оцедур у р еш ен и я удобн о в в и де с ледующ ей т а бли цы , где чер ез Aj обозн а чен ы в ект ор ы -с т олбцы м а т р и цы (с т олбцы коэффи ци ен т ов п р и п ер ем ен н ойxj). I 1 3 2 3

B 2 4 1 5

A1 1 0 1/2 1/2

2 1

-4 10

0 1

A2

A3 2 -1 1 0

0 1 0 1

1 0

-1 2

alk k=2 a12 =2 k=1 a21 -нет * a31 =1/2 a23 -нет * a13 -нет *

коммент . J1={2} J2 ={1} О СТА НО В

* (в ы бор эт огоэлем ен т а п ор ож да ет "с т а р ое" м н ож ес т в оI) На да н н ы х т р ех и т ер а ци ях п олучен ы ба зи с н ы е р еш ен и я с и с т ем ы с оот в ет с т в ен н оx1=(2,0,4), x2=(0,1,5), x3=(10,-4,0). К а кв и дн о и з р а с с м от р ен н огоп р и м ер а , н е в с е п олучен н ы е в р езульт а т е п ер ебор а ба зи с н ы е р еш ен и я с и с т ем ы ли н ейн ы х ур а в н ен и йяв ляют с я доп ус т и м ы м и т очка м и в с оот в ет с т в ующ ейза да че ли н ейн огоп р огр а м м и р ов а н и я (1) - (3), т а кка кн е удов лет в ор яют ус лов и ю н еот р и ца т ельн ос т и (3). П р оцедур у п ер ебор а м ож н ом оди фи ци р ов а т ь т а ки м обр а зом , чт обы п ер еби р а т ь т олько н еот р и ца т ельн ы е ба зи с н ы е р еш ен и я. И зм ен ен и я н еобходи м о в н ес т и в 1, 3 и 4 п ун кт ы с фор м ули р ов а н н ого а лгор и т м а , кот ор ы е п р и обр ет а ют с ледующ и й в и д.

15

Л и н ейн ое п р огр а м м и р ов а н и е

1а . П олучи т ь п р ои зв ольн ое н еот р и ца т ельн ое ба зи с н ое р еш ен и е. П олож и т ь N=1. 3а . Вы бр а т ь k ∈ J т а кое, чт о ∃a ik > 0 . За м ен и т ь J н а J\{k}. b b 4а . Вы бр а т ь l ∈ I т а кое, чт о l = min i . Ес ли т а ки х н ом ер ов l в I н ет , т о alk i:aik > 0 aik п ер ейт и кп .7. П р и м ер 2. На йт и н еот р и ца т ельн ы е ба зи с н ы е р еш ен и я с и с т ем ы ур а в н ен и й. 4 x1 + 5 x 2 + x3 − x 4 = 2  2 x1 + x 2 + x3 + 3x 4 = 5 Реш ен и е. П ос ле экв и в а лен т н ы х п р еобр а зов а н и йда н н а я с и с т ем а м ож ет бы т ь п ер еп и с а н а с ледующ и м обр а зом : 11 7  x = − x1 − 4 x2 3  4 2  x = 3 + 1 x + x 2  4 4 2 1 П олож и м N=1. Тогда I 1={3,4},J 1={1,2}.. К а ки в п р и м ер е 1, офор м и м р еш ен и е в в и де в т а бли цы . Доба в и м с т олбец Θ , в кот ор ы йбудем п ом ещ а т ь от н ош ен и е bi /aik для aik >0 I 3 4 2 4 1 4

b 11/4 3/4 11/16 23/16 11/14 8/7

A1 7/2 -1/2 7/8 3/8 1 0

A2 4 -1 1 0 8/7 -3/7

A3 1 0 1/4 1/4 2/7 1/7

A4 0 1 0 1 0 1

Θ 11/16 11/14 23/6

alk k=2,l=3 a 32 =4 k=1,l=2 a21 =7/8 k=2 a12 -нет k=3 a13 -нет

коммент . J1={1,2} J2 ={1,3} О СТА НО В

На да н н ы х и т ер а ци ях п олучен ы ба зи с н ы е р еш ен и я с и с т ем ы с оот в ет с т в ен н о 11 11 x 1 = (0,0, 11 , 3 ), x 2 = (0, 16 ,0, 43 ),x 3 = ( 14 ,0,0, 78 ) . 4 4 Задачи длясам о ст о ят ельн о го реш ен ия 1. На йт и в с е ба зи с н ы е р еш ен и я с ледующ и х с и с т ем ур а в н ен и й: а ) x 1 − 2x 2 + 4 x 3 − x 4 = 1 2 x 1 + 3x 2 + x 3 + 2x 4 = 3 ; б) x 1 + x 2 + x 3 + x 4 = 3 2 x 1 − x 2 + x 3 − 2x 4 = 2 ; 16

Л и н ейн ое п р огр а м м и р ов а н и е

2. На йт и в с е н еот р и ца т ельн ы е ба зи с н ы е р еш ен и я с ледующ ей с и с т ем ы ур а в н ен и й: ax 1 + x 2 + x 3 + x 4 = 1 x 1 + bx 2 + cx 3 + x 4 = 1

1 2 3 4 5

а

в

с

3 2 5 6 5

6 3 4 2 3

-2 0 -1 -3 -4

6 7 8 9 10

а

в

с

2 3 3 2 6

4 5 4 5 3

-4 -2 -1 0 -3

11 12 13 14 15

а

в

с

3 4 5 4 6

2 5 2 3 4

0 -3 -1 -4 -2

16 17 18 19 20

а

в

с

6 2 4 5 4

5 6 2 6 6

-3 -1 -4 0 -2

§4. А лго рит м сим п лек сн о го м ет о да Доп у ст има я т очка ЗЛ П x = ( x1 , x 2 ,..., x n ) на зы в а ет ся ба зисной, если в ект ор ы -ст олбцы ма т р ицы A: Ai ,..., Ai , k ≤ n , соот в ет ст в у ю щ ие ее нену 1 k лев ы м коор дина т а м, яв ляю т ся линейно неза в исимы ми. П ока ж ем , ка к п р ов ер яет с я, яв ляет с я ли за да н н а я т очка ба зи с н ой, н а п р и м ер е. П р и м ер 1. П ус т ь ус лов и я (2) н екот ор ойза да чи ли н ейн огоп р огр а м м и р ов а н и я и м еют в и д 2 x1 − x 2 + 2 x3 + x 4 = 3   x1 − x 3 + 2 x 4 = 3 П р ов ер и т ь, яв ляет с я ли т очка x=(1,0 ,0,1)Т ба зи с н ой. Реш ен и е. Та кка ккоор ди н а т ы т очки н еот р и ца т ельн ы и удов лет в ор яют за да н н ой с и с т ем е ур а в н ен и й, т о он а п о оп р еделен и ю яв ляет с я доп ус т и м ой. Вв едем в р а с с м от р ен и е в ект ор ы A1 , A2 , A3 , A4 - с т олбцы м а т р и цы огр а н и чен и й:  − 1  2  2 1  A1 =  , A2 =  , A3 =  , A4 =   . Тогда с и с т ем а ур а в н ен и йп ос ле п од 0  − 1  2 1  с т а н ов ки в н ее коор ди н а т п р ов ер яем ойт очки п р и м ет в и д: A1 x1 + A4 x 4 = b В с оот в ет с т в и и с оп р еделен и ем ба зи с н ойт очки , в ект ор ы A1 и A4 с ледует п р ов ер и т ь н а ли н ейн ую н еза в и с и м ос т ь. И з кур с а ли н ейн ойа лгебр ы и зв ес т н о, чт о в ект ор ы яв ляют с я ли н ейн о н еза в и с и м ы м и , ес ли р а н г м а т р и цы , с ос т а в лен н ойи з эт и х в ект ор ов , р а в ен и х коли чес т в у. 2 1 Та кка к оп р едели т ель м а т р и цы ≠ 0 , т оее р а н г р а в ен 2, и в ектор ы 1 2 ли н ейн он еза в и с и м ы . Следов а т ельн о, т очка (1,0,0,1)Т яв ляет с я ба зи с н ой. 17

Л и н ейн ое п р огр а м м и р ов а н и е

И з оп р еделен и я с ледует , чт очи с лоп олож и т ельн ы х коор ди н а т ба зи с н ой т очки н е м ож ет бы т ь более чем m. Если ба зисна я т очка содер ж ит р ов но m п олож ит ельны хкоор дина т , т о она на зы в а ет ся нев ы р ож денной, в п р от ив ном слу ча е - в ы р ож денной. За да ча на зы в а ет ся нев ы р ож денной, если доп у ст имое множ ест в о не имеет в ы р ож денны хба зисны хт очек. К а кс ледует и з с оот в ет с т в ующ и х оп р еделен и й, ба зи с н ы е т очки доп ус т и м ого м н ож ес т в а ЗЛ П (1) - (3) с ов п а да ют с н еот р и ца т ельн ы м и ба зи с н ы м и р еш ен и ям и с и с т ем ы ли н ейн ы х ур а в н ен и й (2). Та ки м обр а зом , а лгор и т м п ер ебор а н еот р и ца т ельн ы х ба зи с н ы х р еш ен и й с и с т ем ы с ов п а да ет с а лгор и т м ом п ер ебор а ба зи с н ы х т очек с оот в ет с т в ующ его доп ус т и м ого м н ож ес т в а . Следует от м ет и т ь, чт ов н а ча ле п ер ебор а долж н а бы т ь и зв ес т н а и с ходн а я ба зи с н а я т очка . И т а к, п ус т ь и м еет с я ба зи с н а я т очка доп ус т и м ого м н ож ес т в а ЗЛ П x TB = ( xi , i ∈ I ; x j = 0, j ∈ J ). Коор дина т ы x i , i ∈ I , бу дем в да льнейш ем на зы в а т ь ба зисны ми, x j = 0, j ∈ J - неба зисны ми. С оот в ет ст в енно множ ест в о I - множ ест в ом ба зисны хиндексов , J - множ ест в ом неба зисны хиндексов . В с луча е н ев ы р ож ден н ойза да чи п ока ж дойба зи с н ойт очке в ос с т а н а в ли в а ет с я с оот в ет с т в ующ и й ба зи с , с ос т оящ и й и з в ектор ов Ai , i ∈ I . О бозн а чи м его чер ез B. За м ет и м да лее, чт ока ж да я и т ер а ци я м ет ода Ж ор да н а -Г а ус с а с оот в ет с т в ует п ер еходу от одн ой ба зи с н ой т очки кдр угой п р и за м ен е одн ой ба зи с н ой (за в и с и м ой) п ер ем ен н ой н а одн у н еба зи с н ую (с в ободн ую). П р и эт ом в ы бор у п одлеж и т н ом ер н еба зи с н ойп ер ем ен н ойk и ж ес т кооп р еделяет с я н ом ер ба зи с н ойп ер ем ен н ойl (с м от р и п ун кты 3а и 4а а лгор и т м а ). К оор ди н а т ы н ов ойба зи с н ойт очки в ы чи с ляют с я с ледующ и м обр а зом : x x x BH = ( xi − l a ik , i ∈ I ; x k = l ; x j = 0, j ∈ J , j ≠ k ). (8) a lk a lk Та ки м обр а зом , р а н ее п олучен а лгор и т м , п озв оляющ и йп ер ебр а т ь в с е ба зи с н ы е т очки ЗЛ П . О дн а ко п р и п ои с ке м а кси м ум а н е и м еет с м ы с ла р а с с м а т р и в а т ь т е т очки , кот ор ы е обес п ечи в а ют м ен ьш ее зн а чен и е целев ой фун кци и , чем уж е и зв ес т н ы е. С целью в н ес ен и я т а когоуп ор ядочен и я в а лгор и т м п ер ебор а в ы чи с ли м зн а чен и е целев ой фун кци и в т очке x BH , п р едс т а в лен н ойв в и де (8). x x О бозн а чи м Θ = l = min i . Тогда a lk aik > 0 a ik

L( x BH ) = ∑ ( xi − Θ aik )ci + c k Θ = ∑ ci xi − Θ( ∑ ci aik − c k ) i∈I

i∈I

i∈I

Н а зов ем оценкой в ект ор а Ak в еличину ∆ k = ∑ c i aik − c k ( в ма т р ичной i∈I

c TB B −1 Ak

ф ор ме ∆k = − c k , c B - в ект ор коэф ф ициент ов целев ой ф у нкциип р и ба зисны хп ер еменны х). В да н н ы х обозн а чен и ях L( x BH ) = L( x B ) − Θ ∆ k . (9) 18

Л и н ейн ое п р огр а м м и р ов а н и е

Эт а фор м ула п озв оляет ув и дет ь, чт оес ли в ы бр а н оk т а кое, чт оΔ k<0, т о н а с ледующ ейи т ер а ци и будет п олучен а т очка с больш и м зн а чен и ем целев ой фун кци и (т . к. Θ ≥0). Ес ли Δ k>0, т о п р ои зойдет ум ен ьш ен и е целев ой фун кци и , п р и Δ k=0 зн а чен и е целев ой фун кци и н е и зм ен и т с я. Eс ли Δ k<0, н о в с е a ik ≤ 0 , т о, в ы би р а я любое п олож и т ельн ое чи с ло в качес т в е Θ , будем п олуча т ь доп ус т и м ую, н о н е ба зи с н ую т очку(с м . ф-лу (8)). Зн а чен и е целев ой фун кци и в эт ой т очке и зм ен яет с я в с оот в ет с т в и и с фор м улой (9), п оэт ом у ес ли Θ в ы би р а т ь ка кугодн о больш и м , т о зн а чен и е фун кци и цели будет н еогр а н и чен н о ув ели чи в а т ьс я. Следов а т ельн о, в т а ком с луча е м ож н о с дела т ь в ы в од он еогр а н и чен н ос т и целев ойфун кци и н а доп ус т и м ом м н ож ес т в е. Тео рем а 1. Если в се оценки, соот в ет ст в у ю щ ие некот ор ой ба зисной т очке x B , неот р ица т ельны , т о ест ь ∆ j = ∑ ci a ij − c j ≥ 0, ∀j = 1, n , т о т а i∈I

ка я т очка яв ляет ся оп т има льной в за да че (1)-(3). Сфор м ули р ов а н н ы е фа кт ы п озв оляют с кон с т р уи р ов а т ь а лгор и т м ба зов огос и м п лекс н огом ет ода . А лго рит м базо в о го сим п лек сн о го м ет о да На ча ло. За да н а и с ходн а я ба зи с н а я т очка x B : x TB = ( x i , i ∈ I ; x j = 0, j ∈ J ).

Вы чи с ли т ь оцен ки п офор м уле ∆ j = ∑ c i a ij − c j , j ∈ J . i∈I

2. П р ов ер и т ь, ес ли в с е Δ j ≥0, т оп ер ейт и кп .8. 3. П р ов ер и т ь, ес ли ∃k ∈ J : ∆k < 0 и в с е a ik ≤ 0, т оп ер ейт и кп .10. 4. Вы бр а т ь k: Δ k<0 и в ект ор Ak и м еет хот я бы одн у с т р ого п олож и т ельн ую коор ди н а т у(в озм ож ен п р ои зв ольн ы йв ы бор т а когон ом ер а k, н а п р и м ер ,

max ∆ j = ∆k j:Δ <0 j

)

xl x = min i alk i:aik > 0 aik 6. О с ущ ес т в и т ь п ер еход кн ов ойба зи с н ойт очке с п ом ощ ью м ет ода Ж ор да н а -Г а ус с а с н а п р а в ляющ и м элем ен т ом alk. 7. И зм ен и т ь и с ходн ую и н фор м а ци ю: x x x B ← x BH = ( xi − l aik , i ∈ I ; x k = l ; x j = 0, j ∈ J , j ≠ k ). a lk a lk I ← I \ {l} ∪ {k }; J ← J \ {l} ∪ {k } П ер ейт и кп .1. 8. Ес ли с ущ ес т в ует н ом ер s ∈ J : ∆ s = 0 ,т ов ы п и с а т ь от в ет : x B - оп т и м а льн а я т очка , в за да че и м еет с я бес чи с лен н ое м н ож ес т в ор еш ен и й. 9. Ес ли для в с ех j ∈ J , ∆ j > 0 , т ов ы п и с а т ь от в ет : 5. Вы чи с ли т ь п а р а м ет р Θ п офор м уле Θ =

19

Л и н ейн ое п р огр а м м и р ов а н и е

x B - еди н с т в ен н ое р еш ен и е за да чи . 10. Вы п и с а т ь от в ет : за да ча р еш ен и й н е и м еет и з-за н еогр а н и чен н ос т и целев ойфун кци и н а доп ус т и м ом м н ож ес т в е: sup z ( x) = +∞ Ω

П р и м ер 2. Реш и т ь за да чу 2 x1 − x 2 + 3 x 3 − 2 x 4 + x5 → max

=1 − x1 + x 2 + x3   x1 − x 2 + x 4 = 1  x +x + x5 = 2 2  1 xi ≥ 0, i = 1,5 Реш ен и е. О фор м и м р еш ен и е за да чи в в и де т а бли цы . В п ер в ом с т олбце п ом ес т и м т екущ и е ба зи с н ы е п ер ем ен н ы е, в о в т ор ом - и х коэффи ци ен т ы в целев ой фун кци и , в т р ет ьем - ба зи с н ы е коор ди н а т ы т екущ ей т очки x B . Да лее п ер еп и с ы в а ем элем ен т ы м а т р и цы aij , п ом ещ а я н а д ка ж ды м с т олбцом коэффи ци ен т с оот в ет с т в ующ ей п ер ем ен н ой в целев ой фун кци и . П ос ледн и й с т олбец п р едн а зн а ча ет с я для оп р еделен и я зн а чен и я Θ . В от дельн ой с т р оке в ы чи с ляют с я оцен ки в ект ор ов Aj. В ячейке, н а ходящ ейс я н а п ер ес ечен и и оцен очн ой с т р оки и с т олбца x , п ом ещ а ем зн а чен и е целев ой фун кци и в т екущ ейба зи с н ойт очке.

B x3 x4 x5

CB 3 -2 1 ∆j

x 1 1 2 3

2 A1 -1 1 1 -6

x3 x1 x5

3 2 1 ∆j

2 1 1 9

0 1 0 0

-1 A2 1 -1 1 7

3 A3 1 0 0 0

-2 A4 0 1 0 0

1 A5 0 0 1 0

0 -1 2 1

1 0 0 0

1 1 -1 6

0 0 1 0

Θ ― 1 2

П ос кольку н а п ер в ойи т ер а ци и Δ 1 <0, в ба зи с в в оди т с я в ектор A1. Θ = min{11 , 12} = 1 , т .е. в ка чес т в е н а п р а в ляющ егоэлем ен т а в ы би р а ет с я a 21 . Та кка кн а в т ор ойи т ер а ци и в с е Δ j ≥0, т оос т а н ов , п олучен а оп т и м а льн а я т очка x * = (1,0,2,0,1) . П ос кольку н а н еба зи с н ы х в ект ор а х ∆ j > 0 , т ор еш ен и е в за да че еди н с т в ен н о. П р и м ер 3. Реш и т ь за да чу

20

Л и н ейн ое п р огр а м м и р ов а н и е

2 x1 − x 2 + x3 + 3 x 4 − 2 x5 + x 6 → max =1 − x1 + x 2 − x3 + x 4  x5 = 1  x1 − x 2 +  x − 3x + x x6 = 2 2 3  1 xi ≥ 0, i = 1,6 Реш ен и е. B x4 x5 x6 x4 x1 x6

∆j

∆j

CB 3 -2 1

x 1 1 2 3

2 A1 -1 1 1 -6

3 2 1

2 1 1 9

0 1 0 0

-1 A2 1 -1 -3 3

1 A3 -1 0 1 -3

3 A4 1 0 0 0

-2 A5 0 1 0 0

1 A6 0 0 1 0

0 -1 -2 -3

-1 0 1 -3

1 0 0 0

1 1 -1 6

0 0 1 0

Θ ― 1 2

На в т ор ойи т ер а ци и п олуча ем , чт ооцен ка Δ 2 <0, н ов с т олбце A2 н ет п олож и т ельн ы х элем ен т ов . Эт оозн а ча ет , чт оцелев а я фун кци я н е огр а н и чен а н а доп ус т и м ом м н ож ес т в е, т .е. sup z ( x) = +∞ . Ω

Задачи длясам о ст о ят ельн о го реш ен ия 1. Реш и т ь с и м п лекс - м ет одом за да чу Л П , п р едв а р и т ельн оп р и в едя ее кка н он и чес ком у в и ду. x1 − x 2 − x3 + ax 4 → max − x1 + 2 x 2 − x 3 + x 4 ≤ 2 bx1 + x 2 + x 3 − 2 x 4 ≤ 12

2 x1 + cx 2 + 4 x 3 + 2 x 4 ≤ 6 ; x j ≥ 0, j = 1,4 1 2 3 4 5

а 2 3 4 7 8

в 3 1 2 2 3

с -1 1 -1 3 4

6 7 8 9 10

а 5 4 6 2 5

в 2 3 1 2 3

с 3 6 5 2 7

11 12 13 14 15

21

а 2 3 5 7 6

в 1 3 2 1 3

с 2 4 -1 5 8

16 17 18 19 20

а 3 4 3 4 5

в 3 1 1 1 2

с 1 2 0 3 6

Л и н ейн ое п р огр а м м и р ов а н и е

2. П р ов ер и т ь, яв ляет с я ли т очка x 0 р еш ен и ем за да чи Л П : a) 2 x1 − 4 x 2 + x3 − x 4 + 3 x5 → max

− 5 x1 + 6 x 2 − 7 x3 + x 4 +14 x5 = −7 x1 − 5 x 2 − 10 x3 − 4 x 4 + 20 x5 = −10 x j ≥ 0, j = 1,5 x 0 = (2,0,0,3,0) b) x1 − 3x 2 + 4 x 3 − 2 x 4 − 3 x5 → min − x1 + x 2 − x 3 + x 4

= −1

2 x1 − 2 x3 − 6 x 4 + 2 x5 = 4 x j ≥ 0, j = 1,5 x 0 = (2,1,0,0,0) 3. И с п ользуя т еор и ю с и м п лекс - м ет ода , н а йт и в с е зн а чен и я к, п р и кот ор ы х т очка x * = (1,2,0,1,0) яв ляет с я р еш ен и ем за да чи 3 x1 + 12 x 2 + kx 3 − 5 x 4 − 2kx 5 → max − x1 + x 2 + 3x3 − x 4 + 2 x5 = 0 3x1 − x3 + 2 x 4 − x5 = 5 − x1 − 3 x 2 + x3

+

x5 = −7 ;

x j ≥ 0, j = 1,5 §5. М ет о д иск усст в ен н о го базиса и M-м ет о д реш ен ия п ро изв о льн о й задачи лин ейн о го п ро грам м иро в ан ия В с луча е, ес ли за да ча ли н ейн ого п р огр а м м и р ов а н и я за да н а в п р ои зв ольн ойфор м е, т о от с ут с т в ует н еобходи м а я и н фор м а ци я для и с п ользов а н и я ба зов ого с и м п лекс н ого м ет ода , т о ес т ь и с ходн ы й ба зи с . Для от ы с кан и я н а ча льн ой ба зи с н ой т очки м ож ет бы т ь и с п ользов а н п р и ем , за ключа ющ и йс я в с озда н и и с п еци а льн ой за да чи , с в яза н н ой с и с ходн ой с ледующ и м обр а зом : п р и р еш ен и и с озда н н ой за да чи с и м п лекс н ы м м ет одом ли бо будет п олучен а и с ком а я ба зи с н а я т очка , ли бо будет обн а р уж ен а п ус т от а доп ус т и м ого м н ож ес т в а и с ходн ойза да чи . П ус т ь ЗЛ П за да н а в кан он и чес ком в и де (1)-(3). Вв едем н ов ы е (и с кус с т в ен н ы е) п ер ем ен н ы е в огр а н и чен и я за да чи т а к, чт обы в р езульт а т е обр а зов а лс я еди н и чн ы й ба зи с (п ояв и ла с ь в озм ож н ос т ь в ы п и с а т ь и с ходн ую ба зи с н ую т очку): Ax + Ez=b (b≥ 0) x ≥0, z ≥0.

22

Л и н ейн ое п р огр а м м и р ов а н и е

О чев и дн о, чт о н а ча льн а я ба зи с н а я т очка м ож ет бы т ь в ы п и с а н а в в и де ( x j = 0, j = 1, n; z i = bi , i = 1, m) . Та кое п р еобр а зов а н и е и с ходн ой за да чи н е

 x  x яв ляет с я экв и в а лен т н ы м . О дн а ко, каклегко за м ет и т ь, т очка м   =   , где  z  0  в с е z i = 0 с оот в ет с т в уют т очки x , яв ляющ и ес я доп ус т и м ы м и в и с ходн ой за да че. Следов а т ельн о, ж ела т ельн о с ос т а в и т ь н ов ую за да чу т а ки м обр а зом , чт обы ее р еш ен и ям и яв ляли с ь в ект ор ы в и да ( x1 ,.., xn ,0,..,0) Эт а цель м ож ет бы т ь дос т и гн ут а за с чет с озда н и я с п еци а льн ой целев ой фун кци и , н а п р и м ер , m

∑ zi → min .

И т а к, с в яж ем с и с ходн ой за да чей н ов ую (и с кус с т в ен н ую) z-

i =1

за да чу в и да m

∑ zi → min i =1

Ax + Ez=b (b≥ 0) x ≥0, z ≥0. Та кка кв эт ойза да че и м еет с я и с ходн а я ба зи с н а я т очка, т оза да ча м ож ет бы т ь р еш ен а ба зов ы м с и м п лекс н ы м м ет одом . П ус т ь п олучен о р еш ен и е m

( x10 ,.., xn0 , z10 ,.., zm0 ) с озн а чен и ем целев ойфун кци и р а в н ы м µ 0 = ∑ zi0 i =1

Тео рем а 1. Ес ли п р и р еш ен и и z-за да чи п олучен о оп т и м а льн ое зн а чен и е целев ойфун кци и µ 0 = 0 , т о т очка ( x10 ,.., xn0 ) яв ляет с я ба зи с н ойв и с ходн ойза да че. Ес ли µ 0 > 0 , т одоп ус т и м ое м н ож ес т в ои с ходн ойза да чи п ус т о. Та ки м обр а зом м ож ет бы т ь р еш ен а п р облем а от ы с ка н и я и с ходн ой ба зи с н ойт очки , одн а кон еп ос р едс т в ен н ое и с п ользов а н и е т а когоп р и ем а п р и р еш ен и и ЗЛ П н е яв ляет с я р а ци он а льн ы м , т а кка кт р ебует р еш ен и я фа кт и чес ки дв ух за да ч: с н а ча ла z-за да чи , а за т ем - и с ходн ой. Сущ ес т в ует м ет од, п озв оляющ и йобъеди н и т ь эт и дв а эт а п а . M-м ет о д. П оус лов и ю и с ходн ойза да чи с ос т а в ляет с я в с п ом ога т ельн а я М -за да ча в и да n

∑cjxj

J =1

m

− M ∑ z i → max i =1

Ax + Ez=b (b≥ 0) x ≥0, z ≥0. Здес ь z - и с кус с т в ен н ы е п ер ем ен н ы е, в в еден н ы е в ус лов и е за да чи с целью обес п ечен и я и с ходн ойба зи с н ойт очки , с и м в олом M обозн а чен о - н екот ор ое п олож и т ельн ое чи с ло. Ес ли М дос т а т очн о в ели ко, т о с ла га ем ы е с п олож и т ельн ы м и zi ум ен ьш а ют зн а чен и е целев ой фун кци и , чт о н ев ы годн о с т очки зр ен и я м а кс и м и за ци и . П р ои с ходи т какбы "ш т р а фов а н и е" целев ой фун кци и за т о, чт ов ы бр а н а т очка с п олож и т ельн ы м и коор ди н а т а м и zi . В с в язи с эт и м 23

Л и н ейн ое п р огр а м м и р ов а н и е

с ледует ож и да т ь, чт о в оп т и м а льн ой т очке п р и дос т а т очн о больш ом M в с е зн а чен и я zi будут р а в н ы н улю. О дн а ко эт о в озм ож н о т олько в с луча е, ес ли в и с ходн ой за да че доп ус т и м ое м н ож ес т в о н е п ус т о. И м еет м ес т о с ледующ а я т еор ем а . Тео рем а 2. Ес ли и с ходн а я за да ча и м еет р еш ен и е, т о с ущ ес т в ует т а кое чи с ло M0, чт о п р и в с ех M>M0 в с п ом ога т ельн а я М -за да ча т ож е и м еет р еш е x*  н и е, и в любом ее р еш ен и и   т очка z*=0, а x* будет р еш ен и ем и с ходн ой  z*    за да чи . С ледст в ие 1. Ес ли п р и р еш ен и и п р ои зв ольн ойза да чи ли н ейн огоп р огр а м м и р ов а н и я М -м ет одом будет п олучен а т а кая оп т и м а льн а я т очка, чт о z*≠ 0, т ов и с ходн ойза да че доп ус т и м ое м н ож ес т в оп ус т о. И з т еор ем ы с ледует , чт о р еш ен и е м ож н о ос ущ ес т в лят ь, фи кс и р уя н екот ор ое больш ое чи с лоM, одн а кообы чн оп ос т уп а ют и н а че, и с п ользуя п р и н ци п м ет ода и с кус с т в ен н огоба зи с а . Ч и с лоM п р и эт ом н е фи кс и р ует с я, ос т а в ляет с я в за да че в ка чес т в е п а р а м ет р а , кот ор ы й п озв оляет ос ущ ес т в лят ь н еп р ер ы в н ое дв ухэт а п н ое р еш ен и е за да чи . На п ер в ом эт а п е а лгор и т м а ос ущ еm

с т в ляет с я м а кси м и за ци я в т ор ой гр уп п ы с ла га ем ы х β 0 = − M ∑ z i → max , а i =1

п ос ле дос т и ж ен и я м а кс и м ум а н еп р ер ы в н о п ер еходят коп т и м и за ци и и с ходн ойцелев ойфун кци и , ли бо дела ют в ы в од о н ер а зр еш и м ос т и и с ходн ойза да чи . До т ех п ор п ока п ер ем ен н ы е zi>0, т .е. яв ляют с я ба зи с н ы м и , и зн а чен и е целев ойфун кци и , и оцен ки ∆ j м ож н о п р едс т а в и т ь в в и де α j + Mβ j , j = 1, n . Следов а т ельн о, ес ли в в оди т ь в ба зи с т а кой в ект ор Aj, чт о с оот в ет с т в ующ ее зн а чен и е β j <0, т о эт о п р и в едет кув ели чен и ю зн а чен и я β 0 . М а кс и м а льн ое зн а чен и е будет п олучен о, когда в с е β j будут н еот р и ца т ельн ы м и . О чев и дн о, чт о п р и эт ом в озм ож н ы дв е с и т уа ци и : β 0 < 0 и β 0 = 0 . Ра с с м от р и м оба эт и с луча я. 1. О п т и м а льн ое зн а чен и е β 0 < 0 . На ли чи е т а койс и т уа ци и н а одн ойи з и т ер а ци йозн а ча ет , чт одоп ус т и м ое м н ож ес т в ои с ходн ойза да чи п ус т о, т .к. оп т и м а льн а я т очка и м еет коор ди н а т ы zi >0. 2. О п т и м а льн ое зн а чен и е β 0 = 0 . Та койв а р и а н т в озм ож ен , в с в ою очер едь, в дв ух с и т уа ци ях: а ) Вс е и с кус с т в ен н ы е п ер ем ен н ы е в ы в еден ы и з ба зи с а и р а в н ы , ка кн еба зи с н ы е п ер ем ен н ы е, н улю. В эт ом с луча е п олучен а ба зи с н а я т очка и с ходн ой за да чи и п р одолж а ет с я оп т и м и за ци я и с ходн ойцелев ойфун кци и п оба зов ом у а лгор и т м у с и м п лекс н огом ет ода . б) И с кус с т в ен н ы е п ер ем ен н ы е zi н е в ы в еден ы и з ба зи с а , н о и х зн а чен и я р а в н ы н улю. В эт ом с луча е м ы и м еем дело с в ы р ож ден н ой с и т уа ци ей, и ба зи с н а я т очка , п олучен н а я н а эт ой и т ер а ци и , яв ляет с я в ы р ож ден н ой ба зи с н ой 24

Л и н ейн ое п р огр а м м и р ов а н и е

т очкойи с ходн ойза да чи . О н а , ка ки в п р еды дущ ем с луча е, в ообщ е гов ор я, н е яв ляет с я оп т и м а льн ой. Следов а т ельн о, н еобходи м о п р одолж и т ь п ои с к, н е ум ен ьш а я п р и эт ом п олучен н ое оп т и м а льн ое зн а чен и е β 0 = 0 . П о оцен ка м α j < 0 (ес ли т а ки е ес т ь) оп р еделяет с я в ект ор для в в еден и я в ба зи с н а да н н ой и т ер а ци и . П р оцес с п р одолж а ет с я до т ех п ор , п ока н е и с чезн ут т а ки е j, чт о α j < 0, β j = 0, с оот в ет с т в ующ и йс т олбец Aj и м еет элем ен т ы aij>0. И т а к, с фор м ули р уем окон ча т ельн ы й алго рит м реш ен ияп ро изв о льн о й задачи лин ейн о го п ро грам м иро в ан ия. 1. П р и в ес т и за да чу кка н он и чес ком у в и ду. 2. П р ов ер и т ь н а ли чи е еди н и чн огоба зи с а с р еди с т олбцов м а т р и цы огр а н и чен и й. Ес ли еди н и чн ы йба зи с и м еет с я, т оп ер ейт и кп .5. 3. Вв ес т и в за да чу и с кус с т в ен н ы е п ер ем ен н ы е т а к, чт обы с р еди с т олбцов п олучен н ойм а т р и цы п ояв и лс я еди н и чн ы йба зи с в п р ос т р а н с т в е Rm , где m - чи с лоогр а н и чен и йза да чи . 4. Сос т а в и т ь М - за да чу: в в ес т и и с кус с т в ен н ы е п ер ем ен н ы е в целев ую фун кци ю с коэффи ци ен т а м и , р а в н ы м и - М . 5. Сос т а в и т ь и с ходн ую т а бли цу для офор м лен и я р еш ен и я за да чи . Ес ли да н н ы йп ун кт в ы п олн яет с я п ос ле п ун кт а 2, т офр а гм ен т т а бли цы за в ер ш а ет с я одн ой оцен очн ой с т р окой, ес ли п ос ле п ун кта 4, т о дв ум я с т р ока м и для оцен ок∆ j = α j + Mβ j (п ер в а я - для чи с ел α j , в т ор а я - для β j ). 6. Вы чи с ли т ь оцен ки в с ех в ект ор ов -огр а н и чен и й за да чи п о фор м ула м ∆ j = ∑ ci aij − c j П р и н а ли чи и и с кус с т в ен н ы х в ектор ов в ба зи с е п олучи м i∈I

в ы р а ж ен и я в и да α j + M β j . П ом ес т и т ь α j в п ер в ую оцен очн ую с т р оку,

β j - в ов т ор ую (н и ж н юю). 7. П р и н а ли чи и дв ух оцен очн ы х с т р окп р ов ер и т ь, ес ли в с е β j ≥ 0, т оп ер ейт и кп .11, и н а че - кп .9 с чи с ла м и β j . Ес ли ос т а ла с ь одн а оцен очн а я с т р ока, т о п р ов ер и т ь ус лов и е ∆ j ≥ 0 . Ес ли эт о ус лов и е в ы п олн яет с я, т о п ер ейт и кп .12. 8. П р ос м от р ет ь в ектор ы -с т олбцы Aj, для кот ор ы х α j <0. Ес ли с р еди н и х с ущ ес т в ует т а кой, чт о в с е его коор ди н а т ы aij ≤ 0, т о п ер ейт и кп .13, и н а че кп .9 с чи с ла м и ∆ j = α j . 9. О п р едели т ь н а п р а в ляющ и й элем ен т для в ы п олн ен и я и т ер а ци и п о м ет одуЖ ор да н а -Г а ус с а . Ном ер с т олбца k м ож ет бы т ь в ы бр а н любы м с р еди т ех j, для кот ор ы х ∆ j < 0. Ном ер с т р оки l оп р еделяет с я с ледующ и м обр а зом : xl x = min i , где xi - ба зи с н ы е коор ди н а т ы п р ов ер яем ой ба зи с н ой т очки , alk aik >0 a ik a lk - н а п р а в ляющ и йэлем ен т . 25

Л и н ейн ое п р огр а м м и р ов а н и е

10.П ер ейт и кн ов ойба зи с н ойт очке. О с ущ ес т в и т ь п р еобр а зов а н и я Ж ор да н а Г а ус с а с н а п р а в ляющ и м элем ен т ом a lk. Вы бр ос и т ь и з р а с с м от р ен и я и с кус с т в ен н ы йв ект ор , ес ли он н а да н н ойи т ер а ци и с т а л н еба зи с н ы м . П ер ейт и к п .6. 11.П р оа н а ли зи р ов а т ь зн а чен и е целев ой фун кци и в да н н ой ба зи с н ой т очке z ( x B ) = α 0 + Mβ 0 . Ес ли β 0 = 0 , т о п р ов ер и т ь н а ли чи е и с кус с т в ен н ы х в ектор ов в ба зи с е. Ес ли и с кус с т в ен н ы х в ектор ов в ба зи с е н ет , т о в ы чер кн ут ь в т ор ую оцен очн ую с т р оку и п ер ейт и кв ы п олн ен и ю п .7. Ес ли и с кус с т в ен н ы е п ер ем ен н ы е и м еют с я с р еди ба зи с н ы х (он и п р и эт ом р а в н ы н улю), т о п р ов ер и т ь н ер а в ен с т в о α j ≥ 0 для т ех н ом ер ов j , для кот ор ы х

β j = 0 .Ес ли н ер а в ен с т в а в ы п олн яют с я, т о п олучен о р еш ен и е за да чи . П ер ейт и кп .15. Ес ли с р еди α j , т а ки х чт о β j = 0 с ущ ес т в уют т а ки е, чт о α j < 0 , т о п ер ейт и кп .8, где п р ов ер ке будут п одв ер га т ьс я т олько т е в ект ор ы A j , для кот ор ы х α j < 0 , β j = 0 . Ес ли в в ы р а ж ен и и α 0 + Mβ 0 и м еет м ес т он ер а в ен с т в о β 0 < 0 , т оп ер ейт и кп .14. 12.П р ов ер ка еди н с т в ен н ос т и р еш ен и я. Ес ли с р еди н еба зи с н ы х в ект ор ов ес т ь т а ки е, чт о ∆ j = 0, т ов за да че и м еет с я бес чи с лен н ое м н ож ес т в ор еш ен и й. И с ключен и е с ос т а в ляет с луча й, когда бы ла с дела н а за м ен а п ер ем ен н ы х xs=xs'-xs''. В эт ом с луча е, ес ли одн а и з п ер ем ен н ы х xs' и ли xs'' яв ляет с я ба зи с н ой, т ооцен ка в т ор ойобяза т ельн ор а в н а н улю. Эт от фа кт озн а ча ет бес чи с лен н ое м н ож ес т в оп а р , с п ом ощ ью кот ор ы х м ож ет бы т ь п олучен озн а чен и е п ер ем ен н ойxs. Ес ли с р еди н еба зи с н ы х в ектор ов , кр ом е т ех, окот ор ы х с каза н ов ы ш е, н ет т а ки х, кот ор ы е и м еют н улев ы е оцен ки , т ов за да че с ущ ес т в ует еди н с т в ен н ое р еш ен и е. Ес ли и м еет м ес т ос луча й, когда для в с ех н еба зи с н ы х в ект ор ов ∆ j ≥ 0,т оза да ча и м еет еди н с т в ен н ое р еш ен и е. П ер ейт и кп .15. 13.О с т а н ов . За да ча н е и м еет р еш ен и я и з-за н еогр а н и чен н ос т и целев ойфун кци и н а доп ус т и м ом м н ож ес т в е. П ер ейт и кп .15. 14. О с т а н ов . За да ча н е и м еет р еш ен и я и з-за п ус т от ы и с ходн огодоп ус т и м ого м н ож ес т в а . 15. Вы п и с а т ь от в ет . П р и м ер 1. Реш и т ь ЗЛ П . 3 x1 +7 x3 − x4 → max x1 + x 2 + 2 x 3 + x 4 = 4 x1 − 2 x2 + 3x3 = 5 3 x1 +7 x3 + 2 x 4 = 13

x j ≥ 0, j = 1,4 Реш ен и е. 26

Л и н ейн ое п р огр а м м и р ов а н и е

Та кка кв за да че н ет н а ча льн огоба зи с а , с ос т а в и м М -за да чу. 3 x1 + 7 x3 − x 4 − Mz1 − Mz 2 − Mz 3 → max x1 + x 2 + 2 x 3 + x 4 + z1 = 4 x1 − 2 x2 + 3x3 + z 2 = 5 3 x1 +7 x3 + 2 x 4 + z 3 = 13

x j ≥ 0, j = 1,4 За п и ш ем да н н ы е в т а бли цу.

B z1 z2 z3

CB -M -M -M

x 4 5 13

α β

0 -21 x1 3 4 z2 -M 1 z3 -M 1 α 12 β -2 x1 3 2 x3 7 1 z3 -M 0 α 13

3 A1 1 1 3

0 A2 1 -2 0

7 A3 2 3 7

-1 A4 1 0 2

-M z1 1 0 0

-M z2 0 1 0

-M z3 0 0 1

-3

0

1

-5 1 0 0 0 0 1 0 0 0

1 1 -3 -3

-7 -12

0 0

0 0 0 1 0 0 0

0 0 0 0 1 0 0 0 0 1 0

2 1 1

-3 1 -1 -1

3 6

-1 -2

4 2

7 -3 0 0

0 1 0 0

3 -1 0 3

Θ 4 5 4 13

2 1 1

На да н н ойи т ер а ци и п олучен о, чт от р ет ье ур а в н ен и е в с и с т ем е, оп р еделяющ ейх, яв ляет с я ли ш н и м . И с ключа я его, п олуча ем экв и в а лен т н ую с и с т ем у. Та кка кв с е Δ j = α j ≥ 0, т оос т а н ов , н а йден а оп т и м а льн а я т очка x * = (2,0,1,0) . L( x*) = 13 . П ос кольку н а н еба зи с н ом в ект ор е оцен ка ∆ 2 = 0 , т ов за да че и м еет с я бес чи с лен н ое м н ож ес т в ор еш ен и й. П р и м ер 2. Реш и т ь ЗЛ П .

x1 +3 x3 − x 4 → max 2 x1 + 4 x 2 − x 4 = 9 − 3 x1 + 2 x 2 + 3x 4 = 3 x1 +5 x 2 + x 3 + 2 x 4 = 4

x j ≥ 0, j = 1,4 Реш ен и е.

27

Л и н ейн ое п р огр а м м и р ов а н и е

Та кка кв за да че п р и с ут с т в ует т олькооди н ба зи с н ы йв ект ор A3, с ос т а в и м М за да чу, доба в и в и с кус с т в ен н ы е п ер ем ен н ы е в 1 и 2 огр а н и чен и е. x1 + 3 x 3 − x 4 − Mz1 − Mz 2 → max 2 x1 + 4 x 2 − x 4 + z1 = 9 − 3 x1 + 2 x 2 + 3 x 4 + z 2 = 3 x1 +5 x 2 + x 3 + 2 x 4 = 4

x j ≥ 0, j = 1,4 . За п и ш ем да н н ы е в т а бли цу.

B z1 z2 x3

CB -M -M 3 α β

z1 z2 x2

-M -M 0 α β

x 9 3 4 12 -12 4 7/5 4/5 0 -36/5

1 A1 2 -3 1

0 A2 4 2 5

3 A3 0 0 1

-1 A4 -1 3 2

2

15

7

1 1 -17/5 1/5 -1 11/5

-6 0 0 1

0 0

2 -2/5 1/5

-2 1 11/5 2/5

0 0

-3 6/5

1 2/5

-M z1 1 0 0 0 0 1 0 0 0 0

-M z2 0 1 0 0 0 0 1 0 0 0

Θ 9/4 3/2 4/5

К а кв и дн ои з да н н ойт а бли цы , да льн ейш ее улучш ен и е р еш ен и я н ев озм ож н о, т а ккакв о2-йоцен очн ойс т р оке н е ока за лос ь от р и ца т ельн ы х элем ен т ов . Следов а т ельн о, дос т и гн ут ооп т и м а льн ое р еш ен и е М - за да чи . Нои с кус с т в ен н ы е п ер ем ен н ы е z1 , z 2 н е в ы в еден ы и з ба зи с а и н е р а в н ы н улю, с ледов а т ельн ои с ходн а я за да ча н е и м еет р еш ен и я, т а кка кее доп ус т и м ое м н ож ес т в о п ус т о. Задачи длясам о ст о ят ельн о го реш ен ия 1. Реш и т ь М - м ет одом за да чу Л П , п р едв а р и т ельн о п р и в едя ее ккан он и чес ком у в и ду. x1 + x 2 − x3 − 2 x 5 → min x1 − 2 x 2 + x 4 = −3 3x 2 − x 4 + x5 ≤ 5

x2 +

x5 ≥ 3

x3 − 2 x4 = 2 x j ≥ 0, j = 1,5 28

Л и н ейн ое п р огр а м м и р ов а н и е

2. Реш и т ь М - м ет одом за да чу Л П . x1 − x 2 + x3 − 3 x5 → max − 2 x1 + x 2 + x 4 − x5 = a b 2 x1 − x2 + x3 − x 4 − x5 = 1 b +1 c − x1 + x2 − x3 + x 4 + x5 = 8 ; c +1 x j ≥ 0, j = 1,5.

1 2 3 4 5

а

в

с

1 2 3 4 5

1 1 1 1 2

2 2 2 2 2

6 7 8 9 10

а

в

с

6 7 2 4 6

2 2 1 1 1

2 2 3 3 3

11 12 13 14 15

а

в

с

2 4 6 3 6

2 2 2 1 1

3 3 3 4 4

16 17 18 19 20

а

в

с

3 6 3 6 3

2 2 3 3 4

4 4 4 4 4

§5. Дв о йст в ен н ы е задачи лин ейн о го п ро грам м иро в ан ия Ра с с м от р и м за да чу ли н ейн огоп р огр а м м и р ов а н и я, за п и с а н н ую в п р ои зв ольн ой фор м е: n

∑ c j x j → max (min) j =1

n

∑ aij x j ≤ (≥, =) bi , j =1

i = 1, m .

x j ≥ 0 (≤, нет т р ебов а ний на зна к) , j = 1, n . Да н н ую за да чу будем н а зы в а т ь и с ходн ой. П од дв ойс т в ен н ой за да чей (ДЗ) к и с ходн ойп он и м а ет с я за да ча ли н ейн огоп р огр а м м и р ов а н и я, кот ор а я с т р ои т с я п ос ледующ и м п р а в и ла м , п р и в еден н ы м в т а бли це. И с ходн а я за да ча n

∑cjxj j =1

Дв ойс т в ен н а я за да ча m

∑ bi y i → min

→ max

i =1

yi ≥ 0

n

∑ aij x j ≤ bi j =1

yi ≤ 0

n

∑ aij x j ≥ bi j =1

29

Л и н ейн ое п р огр а м м и р ов а н и е n

∑ aij x j j =1

y i − лю бого зна ка

= bi

xj ≥ 0

m

∑ a ij y i ≥ c j i =1 m

xj ≤ 0

∑ a ij y i ≤ c j i =1 m

x j − лю бого зна ка

∑ a ij y i i =1

=cj

За м еча н и е. К огда целев а я фун кци я в и с ходн ой за да че м и н и м и зи р ует с я, т а бли ца п р очи т ы в а ет с я с п р а в а н а лев о. Да н н а я т а бли ца п озв оляет с фор м ули р ов а т ь н ес колько общ и х п р а в и л п ос т р оен и я дв ойс т в ен н ы х за да ч. • К а ж дом у i-м у огр а н и чен и ю и с ходн ой за да чи с оот в ет с т в ует п ер ем ен н а я yi в ДЗ и , н а обор от , каж дом у k-м у огр а н и чен и ю ДЗ с оот в ет с т в ует п ер ем ен н а я xk и с ходн ойза да чи . • М а т р и цы огр а н и чен и йв и с ходн ойи дв ойс т в ен н ойза да ча х в за и м н о т р а н с п он и р ов а н ы . • П р а в ы е ча с т и огр а н и чен и йи с ходн ойза да чи с т а н ов ят с я коэффи ци ен т а м и целев ой фун кци и в ДЗ, а коэффи ци ен т ы целев ой фун кци и и с ходн ойза да чи - п р а в ы м и ча с т ям и огр а н и чен и йв ДЗ. • Ес ли целев а я фун кци я в и с ходн ой за да че м а кси м и зи р ов а ла с ь (м и н и м и зи р ов а ла с ь), т о в ДЗ целев а я фун кци я м и н и м и зи р ует с я (м а кс и м и зи р ует с я); И с п ользуя да н н ое п р а в и ло п ос т р ои м ДЗ кЗЛ П , за п и с а н н ойв с и м м ет р и чн ойфор м е. В ДЗ целев а я фун кци я м и н и м и зи р ует с я :

m

∑ bi y i → min . i =1

Вс е огр а н и чен и я в с и м м ет р и чн ойфор м е за да чи и м еют в и д

n

∑ aij x j ≤ bi , п оj =1

эт ом у н а в с е п ер ем ен н ы е ДЗ будет п р и с ут с т в ов а т ь т р ебов а н и е н еот р и ца т ельн ос т и y i ≥ 0, i = 1, m . На в с е п ер ем ен н ы е в с и м м ет р и чн ой фор м е п р и с ут с т в ует т р ебов а н и е н еот р и ца т ельн ос т и , п оэт ом у огр а н и чен и я ДЗ будут и м ет ь вид

m

∑ a ij y i ≥ c j , j = 1, n .

И т а к, м ы п олучи ли за да чу

i =1

m

∑ bi y i → min i =1

m

∑ a ij y i ≥ c j , j = 1, n i =1

y i ≥ 0, i = 1,..., m . 30

Л и н ейн ое п р огр а м м и р ов а н и е

Ес ли п р ов ес т и а н а логи чн ы е р а с с уж ден и я для п ос т р оен и я ДЗ для ЗЛ П , за п и с а н н ойв кан он и чес койфор м е, т ом ы п олучи м за да чу в и да : m

∑ bi y i → min i =1

m

∑ a ij y i ≥ c j , i =1

j = 1,..., n .

П р и м ер 1. П ос т р ои т ь ДЗ к с ледующ ейза да че 4 x1 + 5 x 2 − x 3 − 6 x 4 → min 4 x1 − x 2 − x3 − 3x 4 ≤ 7 − x1 + x 2 − x 3 − x 4 ≥ 6 − x1 + 2 x 2 − x 3 = −1 x1 ≥ 0, x 2 ≤ 0 Реш ен и е. В ДЗ ки с ходн ойза да че будет 3 п ер ем ен н ы х (в и с ходн ойза да че 3 огр а н и чен и я) и 4 огр а н и чен и я (в и с ходн ой за да че 4 п ер ем ен н ы х). П ос кольку в и с ходн ойза да че целев а я фун кци я м и н и м и зи р ует с я, в ос п ользуем с я т а бли цей с лев а н а п р а в о. Для и ллюс т р а ци и п ос т р ои м а н а логи чн ую т а бли цу для да н н ой кон кр ет н ойза да чи . И с ходн а я за да ча 4 x1 + 5 x 2 − x 3 − 6 x 4 → min 4 x1 − x 2 − x 3 − 3 x 4 ≤ 7 − x1 + x 2 − x 3 − x 4 ≥ 6 − x1 + 2 x 2 − x 3 = −1 x1 ≥ 0 x2 ≤ 0 x 3 − лю бого зна ка x 4 − лю бого зна ка

Дв ойс т в ен н а я за да ча 7 y1 + 6 y 2 − y 3 → max y1 ≤ 0 y2 ≥ 0 y 3 − лю бого зна ка 4 y1 − y 2 − y 3 ≤ 4 − y1 + y 2 + 2 y 3 ≥ 5 − y 1 − y 2 − y 3 = −1 − 3 y1 − y 2 = − 6

За м ет и м , чт оп р еж де чем с т р ои т ь дв ойс т в ен н ую за да чу, и с ходн ую м ож н ов н а ча ле п р и в ес т и кс и м м ет р и чн ойи ли ка н он и чес койфор м е, а за т ем п ош а блон у кп олучен н ойфор м е за да чи п ос т р ои т ь дв ойс т в ен н ую. П р и эт ом п олучен н ы е р а зн ы м и с п ос оба м и дв ойс т в ен н ы е за да чи будут экв и в а лен т н ы м и. Вы п и ш ем ос н ов н ы е п р а кт и чес ки зн а чи м ы е с в ойс т в а , кот ор ы е с п р а в едли в ы для п а р ы дв ойс т в ен н ы х за да ч. Ра с с м от р и м , н а п р и м ер , в ка чес т в е п а р ы дв ойс т в ен н ы х за да ч с и м м ет р и чн ую и дв ойс т в ен н ую к н ей. В м а т р и чн ой фор м е он и за п и с ы в а ют с я с ледующ и м обр а зом : c T x → max b T y → min 31

Л и н ейн ое п р огр а м м и р ов а н и е

Ax ≤ b AT y ≥ c y≥0 x≥0 С в о йст в о 1. За да ча дв ойс т в ен н а я кдв ойс т в ен н ойяв ляет с я и с ходн ой. С в о йст в о 2. Для любы х x доп ус т и м ы х в и с ходн ой за да че и y доп ус т и м ы х в дв ойс т в ен н ойс п р а в едли в он ер а в ен с т в о cT x ≤ bT y С в о йст в о 3. Ес ли и с ходн а я за да ча н е и м еет р еш ен и я и з-за н еогр а н и чен н ос т и целев ой фун кци и н а доп ус т и м ом м н ож ес т в е, т о доп ус т и м ое м н ож ес т в одв ойс т в ен н ойза да чи п ус т о. С в о йст в о 4. Возм ож ен в а р и а н т , когда доп ус т и м ы е м н ож ес т в а и с ходн ойи дв ойс т в ен н ойза да ч одн ов р ем ен н оп ус т ы . В ка чес т в е п р и м ер а р а с с м от р и м с ледующ ую дв ойс т в ен н ую п а р у x1 + 2 x 2 → max − 4 y1 + y 2 → min − 3 x1 − x 2 ≤ −4 − 3 y1 + 3 y 2 = 1 3 x1 + x 2 ≤ 1 − y1 + y 2 = 2 y1 ≥ 0, y 2 ≥ 0 С в о йст в о 5. Ес ли с ущ ес т в ует т очка x 0 , доп ус т и м а я в и с ходн ойза да че и т очка y 0 , доп ус т и м а я в дв ойс т в ен н ой за да че, т а ки е, чт о c T x 0 = b T y 0 , т о x 0 - р еш ен и е и с ходн ой, а y 0 - р еш ен и е дв ойс т в ен н ойза да чи . Тео рем а 1. (П ер в а я т еор ем а дв ойс т в ен н ос т и ). Если одна из за да ч (дв ойст в енна я илиисходна я) имеет р еш ение, т о идв ойст в енна я к ней имеет р еш ение, п р ичем оп т има льны е зна чения целев ы хф у нкций сов п а да ю т . Тео рем а 2. (Вт ор а я т еор ем а дв ойс т в ен н ос т и ) Для т ого, чт обы доп у ст има я в исходной за да че т очка x 0 и доп у ст има я в дв ойст в енной за да че т очка y 0 яв лялисьсоот в ет ст в енно р еш ениямиисходной идв ойст в енной за да ч, необходимо и дост а т очно, чт обы в ы п олнялись р а в енст в а (у слов ия доп олняю щ ей неж ест кост и): m T   x 0j  c j − ∑ a ij y i0  = 0, j = 1, n и ли x 0 c − AT y 0 = 0 i =1   n   T y i0  bi − ∑ a ij x 0j  = 0, i = 1, m и ли y 0 b − Ax 0 = 0 . j =1   За м еча н и е 1.В с и м п лекс - п р оцедур е ос ущ ес т в ляет с я п ер ебор ба зи с ов B (н ев ы р ож ден н ы х) п одм а т р и ц и с ходн ойм а т р и цы A т а ки м обр а зом , чт о  x 1. На ка ж дойи т ер а ци и м ет ода в ектор x B =   , где x = B −1b яв ляет с я 0   доп ус т и м ы м в и с ходн ойза да че, т .е. Ax B = b, x B ≥ 0 ;

( )(

( )(

32

)

)

Л и н ейн ое п р огр а м м и р ов а н и е

2. На за ключи т ельн ойи т ер а ци и , кр ом е т ого, когда п олучен а оп т и м а льн а я т очка , оцен ки в с ех в ектор ов A j н еот р и ца т ельн ы

∆ j = c TB B −1 A j − c j ≥ 0,

j = 1, n

и ли

c TB B −1 A = y T A = AT y ≥ c, т .е. в ект ор y = c TB B −1 яв ляет с я доп ус т и м ы м в дв ойс т в ен н ойза да че, кр ом е т ого, он яв ляет с я р еш ен и ем дв ойс т в ен н ойза да чи . П р и эт ом за м ет и м , чт оча с т ь огр а н и чен и й дв ойс т в ен н ой за да чи в ы п олн яет с я в в и де р а в ен с т в AT y j = c j , j ∈ I , где I - м н ож ес т в о ба зи с н ы х и н декс ов (т а кка коцен ки ба зи с н ы х в ект ор ов в с егда р а в н ы н улю ∆ j = 0, j ∈ I ). Та ки е т очки y н а зы в а ют -

(

)

с я ба зи с н ы м и в дв ойс т в ен н ойза да че. Ра с с м от р и м п р и м ер ы п р и м ен ен и я и злож ен н ой т еор и и дв ойс т в ен н ос т и кр еш ен и ю за да ч ли н ейн огоп р огр а м м и р ов а н и я. П р и м ер 3. На ос н ов а н и и гр а фи чес кого а н а ли за дв ойс т в ен н ой за да чи и с с ледов а т ь р а зр еш и м ос т ь с ледующ и х за да ч и в с луча е р а зр еш и м ос т и н а йт и оп т и м а льн ое зн а чен и е целев ойфун кци и . а ) 6 x1 + 9 x 2 + 3 x 3 → min − x1 + 2 x 2 + x 3 ≥ 3 3x1 + x 2 − x 3 ≥ 1 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0

б) 2 x1 + x 2 + 2 x 3 → min − x1 + x2 + x3 = 2 x1 − 3x 2 − 2 x3 = 1 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0

Реш ен и е. Дв ойс т в ен н ы е кп р едлож ен н ы м за да ча м от н ос ят с я кза да ча м ли н ейн ого п р огр а м м и р ов а н и я в R 2 и п оэт ом у и х м ож н о р еш а т ь оп и с а н н ы м в §1 гр а фи чес ки м м ет одом . Дв ойс т в ен н а я кза да че а ) и м еет в и д: 3 y1 + y 2 → max − y1 + 3 y 2 ≤ 6 2 y1 + y 2 ≤ 9 y1 − y 2 ≤ 3 y1, y2≥0

33

Л и н ейн ое п р огр а м м и р ов а н и е

2 1

d=12

Y 2

. Y*

3

max

Y1 Y1 d=0

Ри с .6 * = (4,1) с Г р а фи чес кое р еш ен и е да н н ойза да чи (Ри с . 6) п оказы в а ет , чт о Ymax * z max = 13 . В с и лу п ер в ойт еор ем ы дв ойс т в ен н ос т и и с ходн а я за да ча т а кж е и м еет р еш ен и е, п р и чем оп т и м а льн ое зн а чен и е р а в н о13. Дв ойс т в ен н а я за да ча кза да че б) и м еет в и д: 2 y1 + y 2 → max − y1 + y 2 ≤ 2 y1 − 3 y 2 ≤ 1 y1 − 2 y 2 ≤ 2

Y 2

Y1 3 2

1

d=0

Ри с .7 34

d=5

Л и н ейн ое п р огр а м м и р ов а н и е

Г р а фи чес ки йа н а ли з п ока зы в а ет , чт одв ойс т в ен н а я за да ча н ер а зр еш и м а и з-за н еогр а н и чен н ос т и целев ой фун кци и , п оэт ом у п о с в ойс т в у 3 и с ходн а я за да ча н ер а зр еш и м а и з-за п ус т от ы доп ус т и м огом н ож ес т в а . П р и м ер 4. О п р едели т ь, яв ляют с я ли да н н ы е в ектор ы x и y оп т и м а льн ы м и р еш ен и ям и да н н ойза да чи и дв ойс т в ен н ойкн ей: x1 + 10 x 2 + 8 x 3 → max x1 + 4 x 2 + x 3 = 2 x1 + 2 x 2 − x3 = 0 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0 9 7 x = (1,0,1), y =  ,−   2 2 Реш ен и е. Реш ен и е да н н ойза да чи ос ущ ес т в ляет с я в н ес колькоэт а п ов : 1) п одс т а в и м т очку x = (1,0,1) в огр а н и чен и я и с ходн ойза да чи ; т а кка кт очка удов лет в ор яет огр а н и чен и ям , п ер еходи м кс ледующ ем у эт а п у; 2) п ос т р ои м дв ойс т в ен н ую за да чу 2 y1 → min y1 + y 2 ≥ 1 4 y1 + 2 y 2 ≥ 10 y1 − y 2 ≥ 8 ; 9 7 3) п одс т а в и м т очку y =  ,−  в огр а н и чен и я дв ойс т в ен н ой за да чи ; т очка 2 2 удов лет в ор яет огр а н и чен и ям , п ер еходи м кс ледующ ем у эт а п у; 4) п одс т а в и м т очку x = (1,0,1) в целев ую фун кци ю и с ходн ойза да чи , а т очку 9 7 y =  ,−  - в целев ую фун кци ю дв ойс т в ен н ой за да чи ; п олучен н ы е зн а 2 2 чен и я с ов п а да ют , п оэт ом у п о с в ойс т в у 4 да н н ы е т очки яв ляют с я с оот в ет с т в ен н ор еш ен и ем и с ходн ойи дв ойс т в ен н ы х за да ч. П р и м ер 5. На йт и р еш ен и е с ледующ ейЗЛ П п ут ем гр а фи чес когоа н а ли за дв ойс т в ен н ойза да чи : 5 x1 + x 2 + x3 + x 4 → max 4 x1 + x 3 + x 4 = 16 6 x1 − 4 x 2 − x 3 + x 4 = 4 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 . Реш ен и е. Дв ойс т в ен н а я за да ча за п и ш ет с я в в и де 16 y1 + 4 y 2 → min 4 y1 + 6 y 2 ≥ 5 − 4y2 ≥ 1 35

Л и н ейн ое п р огр а м м и р ов а н и е

y1 − y 2 ≥ 1 y1 + y 2 ≥ 1 y1, y2≥0 Г р а фи чес ки йа н а ли з эт ойза да чи п ока за н н а с ледующ ем р и с ун ке.

Y2 Y1

. Y*min d=9 d=0

Ри с . 8

 13 1  * * О п т и м а льн ы м р еш ен и ем яв ляет с я в ект ор Ymin = 25 . На ос =  ,−  , z min  8 4 н ов а н и и в т ор ойт еор ем ы дв ойс т в ен н ос т и для в ектор а x*,яв ляющ егос я р еш ен и ем и с ходн ойза да чи долж н ы , в ы п олн ят ьс я р а в ен с т в а x1* (4 y1* + 6 y 2* − 5) = 0 x3* ( y1* − y 2* − 1) = 0 x 2* ( −4 y 2* − 1) = 0

x 4* ( y1* + y 2* − 1) = 0 .

* , п олуча ем , чт о п ер ем ен н ы е x 3 и x 4 П одс т а в ляя коор ди н а т ы в ектор а Ymin и с ходн ойза да чи долж н ы обр а щ а т ьс я в н уль. Тогда и з и с ходн ойс и с т ем ы п олуча ем 4 x1 = 16 , от куда x1 = 4 , и 6 x1 − 4 x 2 = 4 , от куда x 2 = 5 . Следов а т ель* н о, р еш ен и ем и с ходн ойза да чи яв ляет с я в ектор X max = ( 4,5,0,0) . П р и эт ом * zmax = 5 * 4 + 5 =25. П р и м ер 6. О п р едели т ь р еш ен и е дв ойс т в ен н ойза да чи кза да че и з п р и м ер а 1 § 4, и с п ользуя р еш ен и е и с ходн ойза да чи . Реш ен и е. В с оот в ет с т в и и с за м еча н и ем 1 оп т и м а льн ы м р еш ен и ем дв ойс т в ен н ой 1 1 0 3     T −1 за да чи яв ляет с я в ект ор y = c B B = (3, 2,1) 0 1 0  =  4  , где м а т р и ца B −1  0 − 1 1  1     

36

Л и н ейн ое п р огр а м м и р ов а н и е

яв ляет с я

м а т р и цей 1 −1  B = [ A3 A1 A5 ] =  0 1 0 1 

обр а т н ой 0  0 . 1 

к оп т и м а льн ой

ба зи с н ой

м а т р и це

Задачи длясам о ст о ят ельн о го реш ен ия 1. Сос т а в и т ь дв ойс т в ен н ы е за да чи кс ледующ и м и с ходн ы м и п р ов ер и т ь с в ойс т в о1 дв ойс т в ен н ы х за да ч: 1) x1 − 2 x 2 + 3 x 3 − x 4 → max 2 x1 − x 2 + 2 x 3 − 3 x 4 ≤ 5 3) 2 x1 − x 2 + x 3 − 3 x 4 + x 5 → min x1 + 2 x 2 − x3 + x 4 ≤ 3 2 x1 − x 2 + x 3 − 3 x 4 − x 5 = 10 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 ; x1 + 2 x 2 − x 3 + 2 x 4 + x5 ≥ 8 2) 3 x 3 − x 4 → max 2 x1 − x 2 + 3 x 3 − x 4 + 2 x 5 ≤ 4 x1 − 2 x 2 + x4 = 8 x1 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 . x 2 + x3 − 3x 4 = 6 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 2. На ос н ов а н и и гр а фи чес когоа н а ли за дв ойс т в ен н ойза да чи и с с ледов а т ь р а зр еш и м ос т ь с ледующ и х за да ч и в с луча е р а зр еш и м ос т и н а йт и оп т и м а льн ое зн а чен и е целев ойфун кци и : 1) 2 x1 − x 2 + 4 x 3 − 2 x 4 → max x1 + 3 x 2 + x 3 ≤ −2 2 x1 − x 2 + 2 x 3 − x 4 ≤ 5 x1 − 4 x 2 + 4 x 3 ≥ 1 x1 − 2 x 2 + 2 x3 − x 4 ≥ 4 x1 ≥ 0, x 2 ≥ 0 ; 4) 2 x1 + x 2 + 2 x 3 → min 2) x1 − x 2 + 2 x3 − 6 x 4 → min − x1 + x 2 + x 3 = 2 x1 + 2 x3 − x 4 = 4 x1 − 3 x 2 − 2 x 3 = 1 x1 − x 2 + x 3 − 3 x 4 ≥ 8 x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0 . x1 ≥ 0, x 3 ≤ 0, x 4 ≥ 0 ; 3) 3x1 − 12 x 2 + 4 x 3 → min 3. Для ка ж дой и з п а р ы дв ойс т в ен н ы х за да ч в озм ож н ы т р и в а р и а н т а от в ет а : за да ча р а зр еш и м а (Р), фун кци я н е огр а н и чен а (Н), обла с т ь п ус т а я (П ). Эт о п озв оляет , в ообщ е гов ор я, р а с с м от р ет ь 9 с и т уа ци й: РР (обе за да чи р а зр еш и м ы ), РН (п ер в а я р а зр еш и м а , в ов т ор ойцелев а я фун кци я н е огр а н и чен а ) и т .д. У ка за т ь в с е в озм ож н ы е с и т уа ци и . 4. П р и в ес т и п р и м ер ы дв ойс т в ен н ы х п а р , обла да ющ и х с ледующ и м и с в ойс т вам и. 1) обе за да чи и м еют оп т и м а льн ы е р еш ен и я; 2) одн а за да ча и м еет н еогр а н и чен н ую доп ус т и м ую обла с т ь, в т ор а я - п ус т ую обла с т ь; 37

Л и н ейн ое п р огр а м м и р ов а н и е

3) доп ус т и м ы е обла с т и обеи х за да ч п ус т ы е; 4) доп ус т и м ы е обла с т и обеи х за да ч н еогр а н и чен н ы е. 5. О п р едели т ь, яв ляют с я ли да н н ы е в ектор ы x и y р еш ен и ям и да н н ойза да чи и дв ойс т в ен н ойкн ей: x1 + 4 x 2 + x 3 → max 5 x1 + 12 x 2 + 2 x 3 = 9 3x1 + 10 x 2 + 4 x3 = 11 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0 3 1 x = (1,0,2), y =  ,  .  14 14  6. Реш и т ь дв ойс т в ен н ы е за да чи , и с п ользуя р еш ен и е и с ходн ы х за да ч с и м п лекс н ы м м ет одом : 1) x1 + 3 x 2 + 2 x 3 → max 2) x1 + x 2 + x 3 + x 4 → min 3x1 − 2 x 2 + x3 ≥ 5 x1 − x 2 − 2 x 3 + x 4 ≤ 6 x1 + x 2 + 2 x 3 ≥ 10 − x1 + x3 ≤2 − x1 + 3 x 2 − x 3 ≥ 2 2 x 2 − 3x 3 + 2 x 4 ≤ 8 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 3) 2 x1 − x 2 + 3 x 3 + x 4 → max 2 x1 + x 2 − 3 x 3 = 10 x1 + x3 + x 4 = 7 − 3 x1 + 2 x3 + x5 = 4 x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0, x 4 ≥ 0, x5 ≥ 0 § 7. Тран сп о рт н аязадача Тр а н с п ор т н а я за да ча фор м ули р ует с я с ледующ и м обр а зом . И м еет с я m п ун кт ов п р ои зв одс т в а A1 , A2 ,..., A m одн ор одн ого п р одукт а и n п ун кт ов п от р еблен и я B1 , B 2 ,..., B n . За да н ы объем ы п р ои зв одс т в а ai , i = 1, m ка ж дого п ун кт а A i и р а зм ер ы с п р ос а каж дого п ун кт а b j , j = 1, n в одн и х и т ех ж е еди н и ца х и зм ер ен и я . И зв ес т н а т а кж е м а т р и ца C = (cij ), i = 1, m, j = 1, n р а с ходов c ij , с в яза н н ы х с п ер ев озкойеди н и цы п р одукци и и з п ун кт а A i в п ун кт

B j . Тр ебует с я с ос т а в и т ь п ла н п ер ев озок, обес п ечи в а ющ и йп р и м и н и м а льн ы х с ум м а р н ы х р а с хода х удов лет в ор ен и е в с ех п ун кт ов п от р еблен и я за с чет и м еющ егос я в п ун кт а х п р ои зв одс т в а п р одукта . П р и в еден н а я фор м ули р ов ка п р едп ола га ет н а ли чи е р а в ен с т в а (ус лов и я ба ла н с а )

38

Л и н ейн ое п р огр а м м и р ов а н и е m

∑ ai = i =1

n

∑ bj . j =1

Та кая за да ча н а зы в а ет с я за кр ы т ойт р а н с п ор т н ойза да чей. М а т ем а т и чес кая п ос т а н ов ка эт ойза да чи и м еет с ледующ и йв и д m

n

∑ ∑ cij xij i =1 j =1

→ min

(1)

п р и огр а н и чен и ях n

∑ x ij j =1

m

∑ x ij i =1

= ai

= bj

i = 1, m

(2)

j = 1, n

x ij ≥ 0 i = 1, m,

(3)

j = 1, n ,

где x ij - коли чес т в оп р одукт а , п ер ев ози м ое и з п ун кт а

(4)

A i в п ун кт B j .

Без огр а н и чен и я общ н ос т и в с егда м ож н о с чи т а т ь, чт о ai > 0, i = 1, m и

b j > 0, j = 1, n . За да ча (1)-(4) яв ляет с я за да чейли н ейн ого п р огр а м м и р ов а н и я, за п и с а н н ойв ка н он и чес койфор м е. О н а и м еет mn п ер ем ен н ы х и m + n огр а н и чен и й. Л юба я доп ус т и м а я т очка за да чи м ож ет бы т ь за п и с а н а в в и де м а т р и цы  x 11 ... x 1n    X = x ij =  ... ... ...  . x   m1 ... x mn  К а ки зв ес т н о, н е люба я за да ча ли н ейн огоп р огр а м м и р ов а н и я и м еет р еш ен и е. У с лов и я р а зр еш и м ос т и т р а н с п ор т н ой за да чи фор м ули р уют с я в с ледующ ейт еор ем е. Тео рем а 1. Для р а зр еш имост и т р а нсп ор т ной за да чи необходимо и дост а т очно в ы п олнение следу ю щ его у слов ия ба ла нса

( )

m

n

i =1

j =1

∑ ai = ∑ bj . М ож н о п ока за т ь, чт о чи с ло н еза в и с и м ы х ур а в н ен и й с и с т ем ы (2)-(3) р а в н о m + n − 1. О т с юда , в ча с т н ос т и , с ледует , чт о люба я доп ус т и м а я ба зи с н а я т очка т р а н с п ор т н ойза да чи с одер ж и т н е более m + n − 1 п олож и т ельн ы х коор ди н а т . Ра с с м от р и м дв а м ет ода н а хож ден и я и с ходн ой ба зи с н ой т очки для т р а н с п ор т н ой за да чи : м ет од "с ев ер о-за п а дн ого угла " и м ет од м и н и м а льн ого элем ен т а .

39

Л и н ейн ое п р огр а м м и р ов а н и е

М ет о д "сев еро -зап адн о го угла" А лгор и т м п ос т р оен и я и с ходн ойба зи с н ойт очки с кла ды в а ет с я и з н ес кольки х ш а гов , н а каж дом и з кот ор ы х оп р еделяет с я в ер хн и йлев ы йэлем ен т м а т р и цы X . Сфор м ули р уем а лгор и т м м ет ода "с ев ер о-за п а дн огоугла ". Ш а г 0. П ола га ем i 0 = 1, j 0 = 1, a i′ = a i , b ′j = b j

(

i = 1, m, j = 1, n .

)

Ш а г 1. П ола га ем x i0 j0 = min a i′0 , b ′j0 . Ес ли x i0 j0 = a i′0 , т оп ер еходи м кш а гу2, в п р от и в н ом с луча е - кш а гу 4. Ш а г 2. П ола га ем b ′j0 = b ′j0 − xi0 j0 . И н декс у i 0 п р и с в а и в а ем зн а чен и е i 0 + 1 .

Ес ли i 0 = m , т оп ер еходи м кш а гу 3, в п р от и в н ом с луча е кш а гу 1. Ш а г 3. П ола га ем xi0 j = b ′j для в с ех j ≥ j 0 . Реш ен и е за кон чен о. Ш а г 4. П ола га ем

a i′0 = ai′0 − xi0 j0 . И н декс у j 0 п р и с в а и в а ем зн а чен и е j 0 + 1 .

Ес ли j 0 = n , т оп ер еходи м кш а гу5, в п р от и в н ом с луча е п ер еходи м кш а гу1. Ш а г 5. П ола га ем xij0 = a i′ для в с ех i ≥ i 0 . Реш ен и е за кон чен о. Ра с с м от р и м п р и м ер и с п ользов а н и я да н н огоа лгор и т м а . П р и м ер 1. И с ходн ы е да н н ы е:

bj 30

36

36

22

56

ai 45 70 15 50

3 30

4

2

4

5

1

4

2

4

15 3 21 4

36 3

13 5

3 9

2

4

3

6 6

6

8 50

В в ер хн ем п р а в ом углу в ка ж дой ячейке с т оят коэффи ци ен т ы c ij , i = 1,4, j = 1,5 . Да н н а я за да ча яв ляет с я за кр ы т ойт р а н с п ор т н ойза да чей, т а к ка кс ум м а п от р ебн ос т ейв п р одукт е р а в н а с ум м е и м еющ егос я п р одукт а 45+70+15+50=30+36+36+22+56. Результ а т ы р а бот ы а лгор и т м а за п и с а н ы в в н и ж н ем лев ом углу ячейки . П олучен а и с ходн а я ба зи с н а я т очка

40

Л и н ейн ое п р огр а м м и р ов а н и е

 30 15 0 0 0     0 21 36 13 0  X = 0 0 0 9 6    0 0 0 0 50  с o зн а чен и ем целев ойфун кци и р а в н ы м 804. М ет од "с ев ер о-за п а дн ого угла " м ож ет ока за т ьс я очен ь "да леки м " от оп т и м а льн ого, т а кка кп р и п ос т р оен и и н а ча льн ойба зи с н ойт очки эт и м м ет одом м ы с ов с ем н е р еа ги р уем н а коэффи ци ен т ы целев ойфун кци и cij . Ва ж н о и м ет ь п р ос т ой м ет од, п озв оляющ и й с т р ои т ь н а ча льн ую ба зи с н ую т очку в о м н оги х с луча ях бли зкую коп т и м а льн ой. Та ки м м ет одом яв ляет с я н екот ор а я м оди фи ка ци я м ет ода "с ев ер о-за п а дн огоугла " - м ет од м и н и м а льн огоэлем ен та. А лго рит м м ет о да м ин им альн о го элем ен т а

{

}

ai′ = a i , b ′j = b j (i, j ) ∈ Ω , где Ω = (i, j ) : i = 1, m, j = 1, n . Ш а г 1. О п р еделяем п а р у и н декс ов (i 0 , j 0 ) и з ус лов и я min cij = ci0 j0 .

Ш а г 0. П ола га ем

Ш а г 2. П ола га ем

(

)

( i , j )∈Ω

xi0 j0 = min ai′0 , b ′j0 . Ес ли xi0 j0 = ai′0 , т о п ер еходи м кш а гу

3, в п р от и в н ом с луча е - кш а гу 6. Ш а г 3. П ола га ем b ′j0 = b ′j0 − xi0 j0 .

{

}

Ш а г 4. Ω = Ω \ (i 0 , j ) : j = 1, n . Ш а г 5. Ес ли м н ож ес т в о Ω с ос т ои т и з элем ен т ов одн ойс т р оки i k , т оп ола га -

xik j = b ′j для в с ех (i k , j ) ∈ Ω . Реш ен и е за кон чен о. В п р от и в н ом с луча е п ер еходи м кш а гу 1. Ш а г 6. П ола га ем a i′0 = ai′0 − xi0 j0 . ем

{

}

Ш а г 7. Ω = Ω \ (i, j 0 ) : i = 1, m . Ш а г 8. Ес ли м н ож ес т в о Ω с ос т ои т и з элем ен т ов одн ого с т олбца j k , т о п ола га ем xijk = a i′ для в с ех (i, j k ) ∈ Ω . Реш ен и е за кон чен о. В п р от и в н ом с луча е п ер еходи м кш а гу 1. Да н н ы м м ет одом н а йдем и с ходн ую ба зи с н ую т очку для п р и м ер а 1.

41

Л и н ейн ое п р огр а м м и р ов а н и е

П р и м ер 2.

bj 30

36

36

22

56

ai 3

45

2

4

36(2) 3

70

1 36

4

2 22

3

5 9(5)

(1)

4

15 50

4

5

(3)

4 12

3

6 15

2

4

3

30 (4)

(5)

(5)

6

8 20(5)

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

 0 0 36 0 9     0 36 0 22 12  X = 0 0 0 0 15    30 0 0 0 20   с о зн а чен и ем целев ой фун кци и , р а в н ы м 545. Да н н ое зн а чен и е яв н о м ен ьш е, чем зн а чен и е целев ойфун кци и н а ба зи с н ойт очке, п олучен н ойм ет одом "с ев ер о-за п а дн огоугла ". Зам ечан ие 1. П р и зн а ком в ы р ож ден н ос т и т р а н с п ор т н ойза да чи яв ляет с я с ущ ес т в ов а н и е r < m, s < n , для кот ор ы х в ы п олн яет с я р а в ен с т в о r

s

k =1

l =1

∑ a ik = ∑ b jl .

В эт ом с луча е п р и и с п ользов а н и и п р и в еден н ы х а лгор и т м ов м ож ет ока за т ьс я, чт ос р еди n + m − 1 ба зи с н ы х коор ди н а т ес т ь н улев ы е. П р и м ер 3. П ос т р ои м м ет одом "с ев ер о-за п а дн ого угла " и с ходн ую ба зи с н ую т очку для с ледующ ейза да чи

42

Л и н ейн ое п р огр а м м и р ов а н и е

bj 10

4

9

6

ai 6 8 10 5

3

4

2

4

3

1

4

2

3

5

3

6 4

4 4 0

*

2

9 4

1 3

6 5

Здес ь п р и в ы чи с лен и и элем ен т а x 22 ока за лос ь a 2′ = b2′ = 4 . П оэт ом у, н а п р и м ер , за п олн яет с я т олько в т ор а я с т р ока и п ола га ет с я b2′ = 0 . П ос ле чего x32 = 0 . Зв ездочкойп ом ечен ба зи с н ы йэлем ен т , р а в н ы йн улю. Зн а я и с ходн ую ба зи с н ую т очку, м ы м ож ем п р одолж и т ь р еш ен и е т р а н с п ор т н ойза да чи м ет одом п от ен ци а лов , кот ор ы йяв ляет с я н ес колькои н ойфор м ой и злож ен и я с и м п лекс н ого м ет ода , с в яза н н ой с о с п еци фи кой т р а н с п ор т н ой за да чи . В п ер в ую очер едь за м ет и м , чт о целев а я фун кци я в т р а н с п ор т н ойза да че м и н и м и зи р ует с я, п оэт ом у п р и в ы бор е в ект ор а , кот ор ы йбудет в в оди т с я в ба зи с н а очер едн ой и т ер а ци и , будет в ы би р а т ьс я в ект ор с от р и ца т ельн ой оцен кой. Для оп р еделен и я в и да оцен окв т р а н с п ор т н ойза да че в ос п ользуем с я за м еча н и ем 1 к §6, в с оот в ет с т в и и с кот ор ы м оцен ка j -й п ер ем ен н ой п р едс т а в ляет с обойр а зн ос т ь м еж ду лев ойи п р а в ойча с т ям и j -го огр а н и чен и я дв ойс т в ен н ойза да чи ∆ j = y T A j − c j , п р и п одс т а н ов ке в н егов ектор а y , кот ор ы йм ож н он а йт и и з ус лов и я ∆k = y T Ak − c k = 0, k ∈ J B . За да ча , дв ойс т в ен н а я кт р а н с п ор т н ойза да че и м еет в и д m

n

i =1

j =1

∑ a i u i + ∑ b j v j → min u i + v j ≤ cij

i = 1, m, j = 1, n ,

где u i , i = 1, m - п ер ем ен н ы е дв ойс т в ен н ойза да чи , с оот в ет с т в ующ и е огр а н и чен и ям (2), а v j , j = 1, n - п ер ем ен н ы е дв ойс т в ен н ойза да чи , от в еча ющ и е огр а н и чен и ям (3). В с оот в ет с т в и и с да н н ы м в и дом дв ойс т в ен н ойза да чи оцен ки в т р а н с п ор т н ойза да че будут и м ет ь в и д ∆ij = u i − v j − cij i = 1, m, j = 1, n , п р и чем п ер ем ен н ы е u i , i = 1, m и v j , j = 1, n п р едс т а в ляют с обойп р ои зв ольн ое р еш ен и е с и с т ем ы ур а в н ен и й

43

Л и н ейн ое п р огр а м м и р ов а н и е

u i + v j = cij , (i, j ) ∈ Ω B , (5) где Ω B - м н ож ес т в о ба зи с н ы х п а р и н декс ов . За м ет и м , чт ос и с т ем а (5) и м еет n + m п ер ем ен н ы х и m + n − 1 ур а в н ен и е. Ра н г с и с т ем ы р а в ен m + n − 1 . О т с юда с ледует , чт о одн у и з п ер ем ен н ы х м ож н о в ы бр а т ь п р ои зв ольн о, н а п р и м ер , u1 = 0 , а в с е ос т а льн ы е п ер ем ен н ы е н а йт и п оцеп очке. Сфор м ули р уем т еп ер ь кр и т ер и й оп т и м а льн ос т и для т р а н с п ор т н ой за да чи . П ус т ь X = ( xij0 ), i = 1, m, j = 1, n - н екот ор ое ба зи с н ое р еш ен и е т р а н с п ор т н ой за да чи , Ω B - м н ож ес т в оба зи с н ы х п а р и н декс ов да н н огоба зи с н огор еш ен и я, u i0 , i = 1, m и v 0j , j = 1, n - п р ои зв ольн ое р еш ен и е с и с т ем ы u i + v j = cij , (i, j ) ∈ Ω B .

Ес ли с ущ ес т в ует п а р а и н декс ов (i , j ) ∉ Ω B , для кот ор ой

u i0 + v 0j > cij , т ос ущ ес т в ует ба зи с н ое р еш ен и е X = (x ij ), для кот ор ого m

m

i =1 j =1

i =1 j =1

∑ ∑ cij xij ≤ ∑ ∑ cij xij0 , ес ли

для в с ех п а р

и н декс ов

(i, j ) ∉ Ω B

в ы п олн ен о

(6)

u i0 + v 0j ≤ cij , т о

X = ( xij0 ), i = 1, m, j = 1, n - р еш ен и е за да чи . За м ет и м , чт одля т р а н с п ор т н ойза да чи га р а н т и р ует с я п ос т р оен и е н ов ойба зи с н ойт очки , т а кка кэт а за да ча п р и с облюден и и ба ла н с а в с егда р а зр еш и м а . О т м ет и м т а кж е, чт о н ер а в ен с т в о (6) яв ляет с я н ес т р оги м в с в язи с в озм ож н ос т ью в ы р ож ден н ос т и ба зи с н ы х т очек. К а к с ледует и з а лгор и т м а с и м п лекс н ого м ет ода , ес ли с ущ ес т в ует в ект ор Ai0 j0 с п олож и т ельн ой оцен кой, т о в ект ор Ai0 j0 долж ен бы т ь в в еден в ба зи с . Для в в еден и я в ект ор а в ба зи с н уж н озн а т ь егот екущ и е коор ди н а т ы . За м ет и м , чт оэт и коор ди н а т ы яв ляют с я коэффи ци ен т а м и р а злож ен и я в ектор а Ai0 j0 п о т екущ ем у ба зи с у. В т р а н с п ор т н ойза да чи для оп р еделен и я коор ди н а т и с п ользует с я п он ят и е ци кла . О п ределен ие. Гов ор ят , чт о множ ест в о п а р индексов (i, j ) обр а зу ет цикл, еслиихмож но р а сп олож ит ь, на п р имер , в следу ю щ ей п оследов а т ельност и: (i 0 , j 0 ) → (i 0 , j1 ) → (i1 , j1 ) → ... → (i k , j k ) → (i k , j 0 ) → (i 0 , j 0 ) . О т мет им, чт о ка ж ды е дв е р ядом ст оящ ие п а р ы индексов долж ны имет ь одина ков ы е номер а ст р ок илиодина ков ы е номер а ст олбцов . С а мип а р ы , в ходящ ие в цикл, на зы в а ю т ся элемент а мицикла .. Ра с с м от р и м п р и м ер ци кла .

44

Л и н ейн ое п р огр а м м и р ов а н и е

*

* *

* *

*

* *

*

Ц и кл, кот ор ы й и с п ользует с я в а лгор и т м е р еш ен и я т р а н с п ор т н ойза да чи , с т р ои т с я с ледующ и м обр а зом . Ст а в ят с я (*) в клет ка х и з м н ож ес т в а Ω B и в клет ке (i 0 , j 0 ) , кот ор а я будет в в оди т ьс я в ба зи с . П р ос м а т р и в а ют с я в с е с т р оки т а бли цы и в ы чер ки в а ют с я т е с т р оки , в кот ор ы х и м еет с я н е более одн ой(*). За т ем в ы чер ки в а ем т е с т олбцы , в кот ор ы х с одер ж и т с я н е более одн огоэлем ен т а . За т ем с н ов а п р ос м а т р и в а ют с я с т р оки и т .д. О с т а в ш и ес я элем ен т ы обр а зуют ци кл. К огда ци кл п ос т р оен , м ож н ос ледующ и м обр а зом н а йт и коэффи ци ен т ы в в оди м ого в ект ор а : п ер ен ум ер ов а т ь в с е элем ен т ы ци кла , п р и с в ои в в в оди м ом у элем ен т у 0, с ледующ ем у - 1 и т .д.; коэффи ци ен т ы р а злож ен и я в ект ор а Ai0 j0 р а в н ы +1 п о в ект ор а м и з ци кла с н ечет н ы м и н ом ер а м и , -1 - п о элем ен т а м ци кла с чет н ы м и н ом ер а м и и 0 п о в ектор а м , н е в ходящ и м в ци кл. О бозн а чи м чер ез Ω + м н ож ес т в ои н декс ов (i, j ) с чет н ы м и н ом ер а м и , чер ез Ω − - м н ож ес т в ои н декс ов (i, j ) с н ечет н ы м и н ом ер а м и . Зн а я коор ди н а т ы в ект ор а Ai0 j0 , его м ож н о в в ес т и в ба зи с п о п р а в и ла м с и м п лекс н ого м ет ода . П ос кольку коор ди н а т ы в в оди м ого в ект ор а р а в н ы +1 и ли -1, т о зн а чен и е θ = min x ij0 = xi0* j* . Вектор с i * , j * ∈ Ω B , н а кот ор ом

(

( i , j )∈Ω −

)

дос т и га ет с я эт от м и н и м ум , с чи т а ет с я в да льн ейш ем н еба зи с н ы м . О с т а льн ы е ба зи с н ы е коор ди н а т ы н ов ойба зи с н ойт очки п ер ес чи т ы в а ют с я п офор м уле: xijH = x ij0 + θ , (i , j ) ∈ Ω + ;

xijH = x ij0 − θ , (i, j ) ∈ Ω − ; xijH = xij п оэлем ен т а м , н е в ходящ и м в ци кл. Вы чи с лен и е н ов огозн а чен и я фун кци и цели м ож ет бы т ь п р ои зв еден оп о LH = L − θ∆i0 j0 . фор м уле М ож ет ока за т ьс я, чт о

θ = min − xij0 ( i , j )∈Ω

дос т и га ет с я в н ес кольки х н ечет н ы х

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

45

Л и н ейн ое п р огр а м м и р ов а н и е

А лго рит м м ет о да п о т ен циало в И т ер а ци я 0. 0.1. О п р еделяет с я н а ча льн ы йба зи с с п ом ощ ью любогои з а лгор и т м ов п ос т р оен и я н а ча льн ойба зи с н ойт очки . 0.2. Вы чи с ляет с я зн а чен и е фун кци и цели L( x 0 ) = ∑ c ij xij0 , Ω - м н ож ес т в о i , j∈Ω

ба зи с н ы х и н декс ов . 0.3. П ола га ем к=0. И т ер а ци я к+1. П ус т ь н а к-т ойи т ер а ци и п олучен а ба зи с н а я т очка x k с озн а чен и ем целев ой фун кци и L( x k ) . k+1.1. П ола га ют u1 = 0 и оп р еделяют v j = c1j − u1 , (i , j ) ∈ Ω . Ес ли н екот ор ое v s в ы чи с лен о, т ооп р еделяют u i = c is − v s , (i, s ) ∈ Ω , и т .д., п ока н е будут в ы чи с лен ы в с е u i , i = 1, m и v j , j = 1, n . k+1.2. Вы чи с ляют оцен ки н еба зи с н ы х в ектор ов . ∆ij = u i + v j − cij k+1.3. Вы би р а ют ∆i0 j 0 = max ∆ij . i, j

k+1.4. Ес ли ∆i0 j 0 ≤ 0, т оос т а н ов , x k - р еш ен и е за да чи . k+1.5. П оп р а в и лу в ы чер ки в а н и я оп р еделяют ци кл, обр а зов а н н ы йп а р ой (i 0 , j 0 ) в м ес т е с ба зи с н ы м и п а р а м и и н декс ов . П ус т ь Ω + -м н ож ес т в очет н ы х элем ен т ов ци кла , Ω − - м н ож ес т в он ечет н ы х элем ен т ов ци кла без (i 0 , j 0 ) . k+1.6. О п р еделяют Θ =

min xijk .

(i , j )∈Ω −

x ki +1j = Θ ,

k+1.7. П ола га ют

0 0

x kij+1

= x ijk − Θ , (i, j ) ∈ Ω − ,

x kij+1 = x ijk + Θ , (i, j ) ∈ Ω + , x kij+1 = x ijk , (i, j ) ∈ Ω \ (Ω − ∪ Ω + ) . k+1.8. О п р еделяют cil jl =

max

(i, j )∈Ω − , xij = 0

cij и элем ен т cil jl с чи т а ют н еба зи с н ы м .

k+1.9. Вы чи с ляют L( x k +1 ) = L( x k ) − Θ∆i0 j 0 . k+1.10. П ола га ют к=к+1. П р и м ер . 3 46

Л и н ейн ое п р огр а м м и р ов а н и е

И т ер а ци я 0. О п р еделяем н а ча льн ы йба зи с м ет одом м и н и м а льн огоэлем ен т а .

bj 12

8

7

7

6

ai 7

6 8 12

4

3

2

5

6 3

4

3

0

5

2

1 6

0

4

2

3

6

7

1

8

4

5

12

14

8

5

1

L( x 0 ) = 0 * 12 + 1 * 8 + 1 * 6 + 2 * 6 + 3 * 0 + 3 * 2 + 8 * 5 + 4 * 1 = 76 Ω = {(1,4), (2,1), ( 2,3), ( 2,5), (3,1), ( 4,2), ( 4,3), ( 4,4)} И т ер а ци я 1. 1.1 П ом еча ем зв ездочка м и м ес т а , за н и м а ем ы е ба зи с н ы м и элем ен т а м и . П ола га ем u1 = 0 . v 4 = c14 − u1 = 2, u 4 = c 44 − v 4 = 2, v 2 = c 42 − u 4 = −1, v3 = c 43 − u 4 = 6,

u 2 = c 23 − v3 = −3

v1 = c 21 − u 2 = 6,

v1 = c 21 − u 2 = 6, v 5 = c 25 − u 2 = 4, u 3 = c31 − v1 = −6. 1.2 О цен ки ∆ij за п и с ы в а ем н а с в ободн ы е м ес т а т а бли цы . vj 6 -1 6 2 4 ui 0 -1 -5 3 * -1 -3 * -8 * -6 * -6 * -11 -2 -7 -8 2 -3 * * * 1 1.3 (i0,j0)=(1,3). 1.4. ∆13 = 3 > 0. 1.5. О т м еча ем зв ездочкой элем ен т (1,3) и п о п р а в и лу в ы чер ки в а н и я оп р еделяем ци кл. + * * – * * * * * – * * + 47

Л и н ейн ое п р огр а м м и р ов а н и е

Ц и кл обр а зуют элем ен т ы (1,3)→ (1,4) → (4,4) → (4,3). Ω + = {(4,4)}, Ω − = {(1,4), ( 4,3)}. 1.6 Θ = min(6,5) = 5. 0 1 = Θ = 5, x14 = 6 − 5 = 1, x143 = 5 − 5 = 0, x144 = 1 + 5 = 6, 1.7 x13 0 1 x 21 = 0, x123 = 2, x125 = 6, x31 = 12, x142 = 8.

0 = 0 . П оэт ом у 1.8 И м еет с я т олькооди н элем ен т (4,3) и з Ω , для кот ор ого x 43 он с т а н ов и т с я н еба зи с н ы м . Нов а я ба зи с н а я т очка и м еет вид 0 0 5 1 0    0 0 2 0 6  1 x = 12 0 0 0 0    0 8 0 6 0   1 0 1 1.9 L( x ) = L( x ) − x13 ∆13 = 76 − 5 * 3 = 61 И т ер а ци я 2. 2.1, 2.2 3 -1 3 2 1 vj ui 0 -4 -5 * * -4 0 * -5 * -3 * -3 * -8 -2 -4 -8 2 -2 * -3 * -2 2.3 , 2.4. ∆i0 j0 = max ∆ij = −2 < 0.

Реш ен и е за кон чен о. x * = x1 , L( x * ) = 61. О т к ры т аят ран сп о рт н аязадача О т кр ы т ойт р а н с п ор т н ойза да чейн а зы в а ет с я т р а н с п ор т н а я за да ча , в кот ор ой н е в ы п олн ен оус лов и е ба ла н с а . П р и эт ом в озм ож н ы дв а с луча я. Случа й1.

m

n

i =1

j =1

∑ a i < ∑ b j . В эт ом с луча е м а т ем а т и чес ка я п ос т а н ов ка за да чи

и м еет в и д. m

∑ ∑ cij x ij → min

(7)

i =1 j =1

n

∑ xij j =1 m

∑ xij i =1

= a i , i = 1, m

(8)

≤ bj ,

(9)

48

j = 1, n

Л и н ейн ое п р огр а м м и р ов а н и е

x ij ≥ 0 i = 1, m, Случа й2.

m

n

i =1

j =1

j = 1, n

∑ a i > ∑ b j . В эт ом с луча е м а т ем а т и чес ка я п ос т а н ов ка за да чи

и м еет в и д: m

∑ ∑ cij x ij → min

(10)

i =1 j =1

n

∑ xij j =1

m

∑ x ij i =1

≤ a i , i = 1, m = bj,

(11)

j = 1, n

(12)

x ij ≥ 0 i = 1, m, j = 1, n Ра с с м от р и м р еш ен и е за да чи (7)-(9). В огр а н и чен и ях (8) в в едем доп олн и т ельн ы е п ер ем ен н ы е x m +1, j , j = 1, n . m

∑ xij i =1

+ x m +1, j =

m +1

∑ x ij i =1

= bj ,

j = 1, n

(13)

Ес ли с лож и т ь в с е огр а н и чен и я (13) и в ы чес т ь и з н и х с ум м у огр а н и чен и й(7), т оп олучи м р а в ен с т в о n

n

m

j =1

j =1

i =1

∑ x m +1, j =a m +1 , i = 1, m, где a m +1 = ∑ b j − ∑ a i > 0. В р езульт а т е за да ча м ож ет бы т ь за п и с а н а в в и де m

∑ ∑ cij x ij → min i =1 j =1

n

∑ x ij j =1

m +1

≤ a i , i = 1, m + 1

∑ x ij i =1

= bj ,

j = 1, n

xij ≥ 0, i = 1, m + 1, j = 1, n . Та кка ккоэффи ци ен т ы фун кци и цели п р и доп олн и т ельн ы х п ер ем ен н ы х р а в н ы н улю, т о c m +1, j = 0, j = 1, n . Та ки м обр а зом , от кр ы т а я т р а н с п ор т н а я за да ча (7)- (9) с в оди т с я кза кр ы т ойт р а н с п ор т н ойза да че доба в лен и ем одн ого огр а н и чен и я, п р и эт ом ус лов и е ба ла н с а в ы п олн яет с я. Следов а т ельн о, н ов а я за да ча р а зр еш и м а . Та ки м ж е с п ос обом м ож ет бы т ь с в еден а кза кр ы т ойи за да ча (10) - (12). П р и м ер 2. a1 = 3, a 2 = 6, a3 = 4, b1 = 8, b2 = 15, b3 = 20, b4 = 7.

49

Л и н ейн ое п р огр а м м и р ов а н и е

3 4 2 5   C = 6 3 1 2  . 4 0 3 1    Здес ь ∑ a i = 13, i

∑bj

= 15. Доба в ляем в м а т р и це чет в ер т ую с т р оку с коэф-

j

фи ци ен т а м и c 4 j = 0 и п ола га ем a 4 = 50 − 13 = 37. Эт а за да ча м ож ет бы т ь р еш ен а м ет одом п от ен ци а лов . П р и м ер 2. a1 = 20, a 2 = 10, a 3 = 10, b1 = 8, b2 = 7, b3 = 8, b4 = 7. 3 4 2 5   C = 6 3 1 2  . 4 0 3 1    Здес ь ∑ a i = 40, ∑ b j = 30. Доба в ляем км а т р и це п ят ы йс т олбец с коэффи i

j

ци ен т а м и c j 5 = 0 и п ола га ем b5 = 10. Эт а за да ча м ож ет бы т ь р еш ен а м ет одом п от ен ци а лов . Задачи длясам о ст о ят ельн о го реш ен ия Реш и т ь м ет одом п от ен ци а лов с ледующ и е за да чи . 1) a1 = 22, a 2 = 10, a 3 = 8, 2) a1 = 25, a 2 = 15, a 3 = 5, b1 = 10, b2 = 7, b3 = 8, b4 = 15. b1 = 10, b2 = 7, b3 = 8, b4 = 5. 1 4 2 5    3 4 2 4 C =  6 3 3 2 .   4 1 3 1  C = 9 5 1 7  .   1 0 3 1   

50

Л и н ейн ое п р огр а м м и р ов а н и е

Реш ен ие задач лин ейн о го п ро грам м иро в ан ия средст в ам и EXCEL Реш ен и е за да чи ли н ейн ого п р огр а м м и р ов а н и я в с р еде EXCEL ос ущ ес т в ляет с я в с оот в ет с т в и и с ос ледующ и м а лгор и т м ом 1.В в од у слов ий за да чи 1.1. С озда ние ф ор мы для в в ода у слов ий за да чи. Ф ор м а для в в ода ус лов и йза да чи

c1 x 1 + c2 x 2 + ... + cn x n → max (min) a11 x 1 + a12 x 2 + ... + a1n x n ≤ ( ≥, = ) b1 a21 x 1 + a22 x 2 + ... + a2 n x n ≤ ( ≥, = ) b2 … . a m1 x 1 + a m 2 x 2 + ... + a mn x n ≤ ( ≥, = ) b m l1 ≤ x 1 ≤ d1 , l 2 ≤ x 2 ≤ d 2 , … , l n ≤ x n ≤ d n и м еет с ледующ и йв и д им я знач е ни е ни ж н. г р в е р х. г р

коэф .в Ц Ф

им я 1

им я 2

…

l1 d1

l2 d2

… …

с1

с2

…

вид

П ЕР ЕМ ЕННЫ Е им я n ln dn Ф ункци я , р е ал и зующ ая це ле в ую ф ункци ю cn О ГР АНИЧЕНИ Я ле в ая ч ас ть

назв ани е ог р ани ч е ни я 1

a11

a12

…

a1n

назв ани е ог р ани ч е ни я 2

a21

a22

…

a2n

…

…

…

…

…

назв ани е ог р ани ч е ни я m

a31

a32

…

a3n

напр ав ле ни е опти м и заци и (m ax, m in)

знак

Ф ункци я , р е ал и зующ ая ле в ую ч ас ть 1-г о ог р ани ч е ни я Ф ункци я , р е ал и зующ ая ле в ую ч ас ть 2-г о ог р ани ч е ни я … Ф ункци я , р е ал и зующ ая ле в ую ч ас ть m -г о ог р ани ч е ни я

51

пр ав ая ч ас ть

b1

b2 …

… .

bm

Л и н ейн ое п р огр а м м и р ов а н и е

2. В в од исходны хда нны х. За п олн яют с я ячейки , с одер ж а щ и е: н и ж н и е и в ер хн и е гр а н и цы п ер ем ен н ы х, коэффи ци ен т ы целев ойфун кци и , коэффи ци ен т ы огр а н и чен и й, зн а ки огр а н и чен и й, н а п р а в лен и е оп т и м и за ци и целев ой фун кци и . 3. В в од за в исимост ей из ма т ема т ической модели. За п олн яют с я ячейки с одер ж а щ и е: фун кци ю, р еа ли зующ ую целев ую фун кци ю за да чи , фун кци и , р еа ли зующ и е лев ы е ча с т и огр а н и чен и йза да чи . 3.1. В в од за в исимост идля целев ой ф у нкции. 3.1.1. П омест ит ь ку р сор в ячейку , от в еденну ю п од зна чение целев ой ф у нкции. 3.1.2. В ы бр а т ь кноп ку М аст ер ф у нкций. 3.1.3. В ы бр а т ь в окне К ат егор ия ка т егор ию м ат ем ат ические 3.1.4. В ы бр а т ь ф у нкцию С УМ М П РОИ ЗВ.

3.1.5. За п олнит ь диа логов ое окно ф у нкцииСУМ М П РОИ ЗВ.

52

Л и н ейн ое п р огр а м м и р ов а н и е

В м а с с и в 1 н уж н о за н ес т и ди а п а зон ячеек, с одер ж а щ и х зн а чен и я п ер ем ен н ы х. В м а с с и в 2 – ди а п а зон ячеек, с одер ж а щ и х коэффи ци ен т ы целев ойфун кци и . 3.2. В в од за в исимост ей для лев ы хча ст ей огр а ничений. 3.2.1. П омест ит ь ку р сор в ячейку , от в еденну ю п од лев у ю ча ст ь огр а ничения. 3.2.2. В ы бр а т ь кноп ку М а ст ер ф у нкций. 3.2.3. В ы бр а т ь окне К ат егор ия ка т егор ию м ат ем ат ические 3.1.6. В ы бр а т ь ф у нкцию С УМ М П РОИ ЗВ. 3.1.7. За п олнит ь диа логов ое окно для ф у нкции СУМ М П РОИ ЗВ. За н ес т и в м а с с и в 1 ди а п а зон ячеек, с одер ж а щ и х зн а чен и я п ер ем ен н ы х (и с п ользов а т ь п р и эт ом а бс олют н ы е с с ы лки ), в м а с с и в 2 – ди а п а зон ячеекс одер ж а щ и х коэффи ци ен т ы да н н огоогр а н и чен и я. 3.1.8. Коп ир ов а т ь содер ж имое ячейкив бу ф ер , 3.1.9. В ст а в ит ь содер ж имое бу ф ер а в ячейки, от в еденны е п од лев ы е ча ст иост а льны хогр а ничений.. 4. В в од основ ны хп а р а мет р ов моделив диа логов ом окне П оиск р еш ения . 4.3. В ойт ив меню С ер висив ы бр а т ь п у нкт П оиск р еш ения . 4.4. За п олнит ь п а р а мет р ы диа логов ого окна П оиск р еш ения .

4.4.1. В п у нкт е Уст ановит ь целеву ю у казат ь ячейку , от в еденну ю п од целев у ю ф у нкцию . 4.4.2. В соот в ет ст в ии с р еш а емой за да чей в ы бр а т ь на п р а в ление целев ой ф у нкции.

53

Л и н ейн ое п р огр а м м и р ов а н и е

4.4.3. Н а ж а т ь кноп ку Добавит ь. П ояв и т с я ди а логов ое окн одля п ос т р оен и я 4.4.4. огр а н и чен и йза да чи .В лев ойча с т и ука зы в а ет с я ячейка (гр уп п а ячеек), в кот ор ой с одер ж и т с я лев а я ча с т ь огр а н и чен и я, в цен т р е - зн а когр а н и чен и я, в п р а в ойча с т и - ячейка (гр уп п а ячеек) с п р а в ойча с т ью огр а н и чен и я. П ос ле в в ода ка ж дого огр а н и чен и я н уж н о н а ж и м а т ь н а кн оп ку До бав ит ь. К огда в с е огр а н и чен и я за да чи п ос т р оен ы , н уж н о н а ж а т ь н а кн оп ку О т м ен а и в ер н ут ьс я в ди а логов ое окн оПо иск реш ен ия. 4.4.5. Н а ж а т ь кноп ку П а р а мет р ы диа логов ого окна П оиск р еш ения . П ояв и т с я ди а логов ое окн оПарам ет ры п о иск а реш ен ия.

С п ом ощ ью ком а н д, н а ходящ и хс я в эт ом ди а логов ом окн е, м ож н о в в оди т ь ус лов и я для р еш ен и я за да ч оп т и м и за ци и в с ех кла с с ов . В р яде п ун кт ов да н н ого окн а за п и с а н ы зн а чен и я, и с п ользуем ы е п о ум олча н и ю. К ом а н ды , и с п ользуем ы е п о ум олча н и ю, п одходят для больш ей ча с т и п р а кт и чес ки х за да ч. К ом а н да М ак сим альн о е в рем я с луж и т для н а зн а чен и я в р ем ен и в с екун да х, в ы деляем ого н а п ои с кр еш ен и я за да чи . В эт о п оле м ож н о в в ес т и зн а чен и е, н е п р ев ы ш а ющ ее 32767 с (более 9 ча с ов ). Зн а чен и е 100, и с п ользуем ое п оум олча н и ю, п одходи т для р еш ен и я больш и н с т в а за да ч. К ом а н да Предельн о е число ит ераций с луж и т для н а зн а чен и я чи с ла и т ер а ци й… 4.4.5. У ст а нов ит ь ф ла ж ок Линейная м одель. Эт ообес п ечи т п р и м ен ен и е с и м п лекс – м ет ода . 54

Л и н ейн ое п р огр а м м и р ов а н и е

4.4.6. Н а ж а т ь на кноп ку Выполнит ь. На чн ет с я р еш ен и е с ос т а в лен н ой м а т ем а т и чес кой м одели за да чи . Ч ер ез ка кое т о в р ем я п ояв и т с я ди а логов ое окн оРезульт ат ы п о иск а реш ен ия.

Нуж н о в ы бр а т ь и н т ер ес ующ и е в и ды от чет ов п о р еш ен и ю за да чи и п р оа н а ли зи р ов а т ь п олучен н ое р еш ен и е. К а ж ды й и з в ы бр а н н ы х т и п ов от чет а с озда ет с я н а от дельн ом ли с т е. О т чет п о результ ат ам с ос т ои т и з т р ех т а бли ц. Таблица 1 п р и в оди т с в еден и я о целев ойфун кци и . В с т олбце Исхо дн о п р и в еден ы зн а чен и я целев ойфун кци и до н а ча ла в ы чи с лен и й. Таблица 2 п р и в оди т зн а чен и я и с ком ы х п ер ем ен н ы х, п олучен н ы е в р езульт а т е р еш ен и я за да чи . Таблица 3 п ока зы в а ет р езульт а т ы оп т и м а льн ого р еш ен и я для огр а н и чен и й и для гр а н и чн ы х ус лов и й. О т чет п о уст о йчив о ст и с ос т ои т и з дв ух т а бли ц. В Таблице 1 п р и в одят с я с ледующ и е зн а чен и я п ер ем ен н ы х: р езульт а т р еш ен и я за да чи ; р едуци р ов а н н а я с т ои м ос т ь, т .е. доп олн и т ельн ы е дв ойс т в ен н ы е п ер ем ен н ы е, кот ор ы е п ока зы в а ют , н а с колько и зм ен и т с я целев а я фун кци я п р и п р и н уди т ельн ом в ключен и и еди н и цы эт ой п р одукци и в оп т и м а льн ое р еш ен и е; коэффи ци ен т ы целев ой фун кци и ; п р едельн ы е зн а чен и я п р и р а щ ен и я ка ж дого коэффи ци ен т а целев ой фун кци и , п р и кот ор ы х с охр а н яет с я н а бор ба зи с н ы х п ер ем ен н ы х в оп т и м а льн ом р еш ен и и . В Таблице 2 п р и в одят с я а н а логи чн ы е зн а чен и я для огр а н и чен и й: в ели чи н а и с п ользов а н н ы х р ес ур с ов ; т ен ев а я цен а , т .е. дв ойс т в ен н ы е оцен ки , кот ор ы е п ока зы в а ют , ка ки зм ен и т с я целев а я фун кци я п р и и зм ен ен и и р ес ур с ов н а еди н и цу; зн а чен и я п р и р а щ ен и я ка ж дого р ес ур с а , п р и кот ор ы х с охр а н яет с я оп т и м а льн ы йн а бор п ер ем ен н ы х, в ходящ и х в оп т и м а льн ое р еш ен и е. О т чет п о п ределам п ока зы в а ет , в каки х п р едела х м ож ет и зм ен ят ьс я в ы п ус кп р одукци и , в ош едш ей в оп т и м а льн ое р еш ен и е, п р и с охр а н ен и и с т р укт ур ы оп т и м а льн огор еш ен и я. В ка чес т в е п р и м ер а р а с с м от р и м р еш ен и е с ледующ ей за да чи п р ои зв одс т в ен н огоп ла н и р ов а н и я Прим ер 1. П р едп р и ят и е в ы п ус ка ет т р и в и да п р одукци и : П р од1, П р од2, П р од3, П р од4. Тр ебует с я оп р едели т ь, в ка ком коли чес т в е н а дов ы п ус кат ьэт и п р одукт ы , чт обы п олучи т ь м а кс и м а льн ую п р и бы ль. И зв ес т н о, чт о для и згот ов лен и я да н н ы х п р одукт ов т р ебуют с я р ес ур с ы т р ех в и дов : т р удов ы е, с ы р ьев ы е, фи н а н с ы . Нор м ы р а с хода (коли чес т в о р ес ур с а ка ж дого в и да , н еобхо55

Л и н ейн ое п р огр а м м и р ов а н и е

ди м ое для в ы п ус ка еди н и цы п р одукци и ка ж догот и п а ), а т а кж е п р и бы ль, п олуча ем а я от р еа ли за ци и еди н и цы ка ж дого т и п а п р одукци и п р и в еден ы в с ледующ ейт а бли цы . ресурс Тр удов ы е Сы р ье Ф и на нсы П р и бы ль

Про д1 60 1 6 4

Про д2 70 1 5 6

Про д3 120 1 4 10

Про д4 130 1 3 13

М а т ем а т и чес ка я м одель да н н ойза да чи и м еет в и д

60x 1 + 70x 2 + 120x 3 + 130x 4 → max x 1 + x 2 + x 3 + x 4 ≤ 16 6 x 1 + 5 x 2 + 4 x 3 + 3x 4 ≤ 110 4 x 1 + 6x 2 + 10x 3 + 13x 4 ≤ 100 x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 1. С ост а в им ф ор му для да нной за да чилинейного п р огр а ммир ов а ния П ЕР ЕМ ЕННЫ Е и м я пр о д1 пр о д2 пр о д3 пр о д4 знач е ни е ни ж н. г р в е р х. г р ко эф .в Ц Ф 60 70 120 130 О ГР А НИ Ч ЕНИ Я ви д тр удо в ы е с ы р ье ф и нанс ы

л е в ая ч ас ть 1 6 4

1 5 6

1 4 10

1 3 13

2. В в едем за в исимост иизма т ема т ической модели

56

м акс пр ав ая знак ч ас ть <= 16 <= 110 <= 150

Л и н ейн ое п р огр а м м и р ов а н и е ПЕР ЕМЕННЫЕ им я знач е ни е ни жн. гр в е р х. гр коэф .в ЦФ

вид тр удов ые с ыр ье ф и нанс ы

пр од1 пр од2 0 0

пр од3 пр од4 0 0

60 70 120 ОГР АНИЧЕНИЯ

1 6 4

1 5 6

1 4 10

130

=СУ ММПР ОИЗ В (B4:E4;B7:E7)

м акс

1 3 13

ле в ая ч ас ть =СУ ММПР ОИЗ В ($B$4:$E$4;B10:E10) =СУ ММПР ОИЗ В ($B$4:$E$4;B11:E11) =СУ ММПР ОИЗ В ($B$4:$E$4;B12:E12)

знак <= <= <=

пр ав ая ч ас ть 16 110 100

3. В ы зов ем диа логов ое окно П оиск р еш ения. В н ем ус т а н а в ли в а ет с я целев а я ячейка (F7), и зм ен яем ы е ячейки (B3:E3), ука зы в а ет с я н а п р а в лен и е п ои с ка (м а кс и м и за ци я) . Да лее в ы би р а ет с я ком а н да До бав ит ь и в п ояв и в ш ем с я ди а логов ом окн е До бав лен ие о гран ичен ия в в одят с я огр а н и чен и я: F10<=H10, F11<=H11, F12<=H12.

У с лов и я н еот р и ца т ельн ос т и п ер ем ен н ы х м ож н о в в ес т и в ди а логов ом окн е Парам ет ры п о иск а реш ен ия. В окн е Парам ет ры п о иск а реш ен ия ус т а н а в ли в а ет с я т а кж е фла ж окЛин ейн аям о дель.

57

Л и н ейн ое п р огр а м м и р ов а н и е

4. За п у ст им п р огр а мму на в ы п олнение из окна п оиск р еш ения. На экр а н е п ояв и т с я ди а логов ое окн оРезульт ат ы п о иск а реш ен ия. В да н н ом ди а логов ом окн е с дела н в ы в од от ом , чт о н а йден ооп т и м а льн ое р еш ен и е.

Результ а т р еш ен и я за да чи п р и в еден в т а бли це ПЕР ЕМЕННЫЕ им я значение нижн. гр верх. гр коэф.в ЦФ ви д трудовые сырье фи нансы

дет

прод1 прод2 прод3 прод4 10 0 6

60 70 120 ОГР АНИЧЕНИЯ

0

1320 м акс

130

лев ая часть 1 6 4

1 5 6

1 4 10

1 3 13

знак 16 <= 84 <= 100 <=

прав ая часть 16 110 100

Да н н а я т а бли ца п ока зы в а ет , чт ом а кс и м а льн а я п р и бы ль (F7=1320) будос т и гн ут а п р едп р и ят и ем п р и с ледующ ем в ы п ус ке п р одукци и : 58

Л и н ейн ое п р огр а м м и р ов а н и е

п р од1=B4=10, п р од2=C4=0, п р од3=D4=6, п р од2=E4=0. В с п еци а льн о от в еден н ы х ячейка х т а бли цы от р а ж а ет с я коли чес т в о и с п ользов а н н ы х р ес ур с ов : т р удов ы х=F10=16, с ы р ья=F11=84, фи н а н с ов =F12=100. 5. П р едст а в им р езу льт а т ы р еш ения за да чигр а ф ически. о птим ал ь ны й вы пу скпр о ду кц ии 12 10 8 6 4 2 0

пр од1

пр од2

пр од3

пр од4

6. П р ов едем а на лиз п олу ченного р еш ения. А н а ли з р еш ен и я ос ущ ес т в ляет с я н а ос н ов а н и и т р ех в и дов от чет ов , п р едс т а в лен н ы х в окн е Результ ат ы п о иск а реш ен ия: р езульт а т ы , ус т ойчи в ос т ь, п р еделы . На чн ем с О т чет а п о результ ат ам . Да н н ы йот чет н а ходи т с я н а от дельн ом ли с т е Microsoft Excel 8.0a О тчет по р езу л ь татам Рабо чий л ист: [Л ист в F: metod exel_lab1.doc]Л ист1 О тчет со здан: 03.08.00 15:20:32

Це ле в ая я ч е й ка (Макс и м ум ) Ячейк а Имя $F$7 коэф .в ЦФ B5

Изм е ня е м ые я ч е й ки Ячейк а Имя $B$4 знач е ни е пр од1 $C$4 знач е ни е пр од2 $D$4 знач е ни е пр од3 $E$4 знач е ни е пр од4

Огр ани ч е ни я Ячейк а Имя $F$10 тр удов ые B5 $F$11 с ыр ье B5 $F$12 ф и нанс ы B5

Исхо дно 0

Исхо дно

Резу л ь тат 1320

Резу л ь тат 0 0 0 0

10 0 6 0

Значение ф о р му л а Стату с Разниц а 16 $F$10<=$H$10 с в я занное 0 84 $F$11<=$H$11 не с в я зан. 26 100 $F$12<=$H$12 с в я занное 0

О т чет с ос т ои т и з т р ех т а бли ц. Та бли ца 1 п р и в оди т с в еден и я оцелев ойфун к59

Л и н ейн ое п р огр а м м и р ов а н и е

ци и . В с т олбце Исхо дн о п р и в еден ы зн а чен и я целев ой фун кци и до н а ча ла в ы чи с лен и й – 0,а в с т олбце Результ ат – зн а чен и е целев ой фун кци и в оп т и м а льн ом р еш ен и и - 1320. Та бли ца 2 п р и в оди т зн а чен и я и с ком ы х п ер ем ен н ы х, п олучен н ы е в р езульт а т е р еш ен и я за да чи . Та бли ца 3 п оказы в а ет р езульт а т ы оп т и м а льн ого р еш ен и я для огр а н и чен и й за да чи : т р удов ы е, с ы р ье, фи н а н с ы . В с т олбце Ф о рм ула п р и в еден ы огр а н и чен и я в т ом в и де, в кот ор ом он и бы ли в в еден ы в ди а логов ом окн е По иск реш ен ия, в с т олбце Зн ачен ие п р и в еден ы в ели чи н ы и с п ользов а н н ого р ес ур с а . Тр удов ы е р ес ур с ы и с п ользов а н ы в коли чес т в е 16, с ы р ье – 84, фи н а н с ы – 100. В гр а фе Разн ица п ока за н о коли чес т в о н еи с п ользов а н н ого р ес ур с а . Тр удов ы е р ес ур с ы и с п ользов а н ы п олн ос т ью, ос т а т окс ы р ья с ос т а в ляет 26, фи н а н с ы и с п ользов а н ы п олн ос т ью. Ес ли р ес ур с и с п ользует с я п олн ос т ью, т о в с т олбце С о ст о ян ие ука зы в а ет с я св язан н о е; п р и н еп олн ом и с п ользов а н и и р ес ур с а в эт ом с т олбце ука зы в а ет с я н есв язан н о е. Вт ор ойт и п от чет а – О т чет п о уст о йчив о ст и. Да н н ы йот чет н а ходи т с я н а от дельн ом ли с т е и с ос т ои т и з дв ух т а бли ц. Microsoft Excel 8.0a О тчет по у сто йчиво сти Рабо чий л ист: [Л ист в F: metod exel_lab1.doc]Л ист1 О тчет со здан: 03.08.00 15:20:33

Изм е ня е м ые я ч е й ки Ячейк а $B$4 $C$4 $D$4 $E$4

Имя знач е ни е пр од1 знач е ни е пр од2 знач е ни е пр од3 знач е ни е пр од4

Резу л ь т. Но р мир . Цел ево й До пу стимо е До пу стимо е значение сто имо сть Ко эф ф иц иент Увел ичение Умень шение 10 0 60 40 12 0 -10 70 10 1E+30 6 0 120 30 13,33333333 0 -20 130 20 1E+30

Огр ани ч е ни я Ячейк а Имя $F$10 тр удов ые B5 $F$11 с ыр ье B5 $F$12 ф и нанс ы B5

Резу л ь т. Теневая О гр аничение До пу стимо е До пу стимо е значение Цена Пр аваячасть Увел ичение Умень шение 16 20 16 3,545454545 6 84 0 110 1E+30 26 100 10 100 60 36

В с т олбце Результ ирую щ ее зн ачен ие т а бли цы 1 п р и в оди т с я оп и с а н н ы й р а н ее р езульт а т р еш ен и я за да чи . Ст олбец Н о рм иро в ан н ая ст о им о ст ь п оказы в а ет , чт оп р и п р и н уди т ельн ом в ключен и и еди н и цы п р од1 в оп т и м а льн ое р еш ен и е целев а я фун кци я н е и зм ен и т с я, п р од2 – ум ен ьш и т с я н а 10, п р од3 – н е и зм ен и т с я, п р од4 – ум ен ьш и т с я н а 20. Ст олбцы До п уст им о е ув еличен ие и До п уст им о е ум ен ьш ен ие п ока зы в а ют , чт о ес ли п р и бы ль от р еа ли за ци и п р од1 будет и зм ен ят ьс я в п р едела х от 60-40 до60+12 , т ооп т и м а ль60

Л и н ейн ое п р огр а м м и р ов а н и е

н ое р еш ен и е за да чи н е и зм ен и т с я, а н а логи чн о для п р од2 – от 70-10 до 70+(1Е+30), п р од3 – от 120-30 до 120+13,33333333, п р од4 – 130-20 до 130+(1Е+30). В с т олбце Результ ирую щ ее зн ачен ие т а бли цы 2 п р и в одят с я в ели чи н ы и с п ользов а н н ы х р ес ур с ов . Ст олбец Тен ев ая цен а п ока зы в а ет , чт о п р и ув ели чен и и т р удов ы х р ес ур с ов н а еди н и цу оп т и м а льн ое зн а чен и е целев ой фун кци и ув ели чи т с я н а 20, п р и ув ели чен и и с ы р ья н а еди н и цу целев а я фун кци я н е и зм ен и т с я, п р и ув ели чен и и н а еди н и цу фи н а н с ов оп т и м а льн ое зн а чен и е целев ой фун кци я в озр а с т ет н а 10. Тен ев а я цен а п озв оляет оп р едели т ь м а кси м а льн ую цен у п окот ор ойс т ои т п окуп а т ь доп олн и т ельн ы е еди н и цы р ес ур с ов . Ст олбцы До п уст им о е ув еличен ие и До п уст им о е ум ен ьш ен ие п оказы в а ют , чт ои зм ен ен и е т р удов ы х р ес ур с ов в п р едела х от 16-3,545454 до16+6 н е п р и в оди т ки зм ен ен и ю оп т и м а льн ого н а бор а в ы п ус каем ы х п р одукт ов , а н а логи чн о для с ы р ья – от 110-(1Е+30) до110+26, для фи н а н с ов – от 100-60 до100+36. Тр ет и йт и п от чет а – О т чет п о п ределам . Да н н ы йот чет с ос т ои т и з одн ойт а бли цы . Цел ево е Я чейка Им я значение $F$7 коэф .в Ц Ф 1320 Изм еняеНижВер хний мо е ний Я чейка Им я значение пр е- р езу л ь - пр едел р езу л ь дел тат тат $B$4 $C$4 $D$4 $E$4

знач е ни е пр од1 знач е ни е пр од2 знач е ни е пр од3 знач е ни е пр од4

10

0

720

10

1320

0

0

1320

0

1320

6

0

600

6

1320

0

0

1320

0

1320

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

61

Л и н ейн ое п р огр а м м и р ов а н и е

ЛИТЕ РА ТУ РА 1. 2. 3. 4. 5. 6. 7. 8. 9.

А кули ч И . Л . М а т ем а т и чес кое п р огр а м м и р ов а н и е в п р и м ер а х и за да ча х.М : Вы с ш . ш к, 1986.-320 с . А с н и н а А . Я ., Ба ев а Н. Б., Ч ер н ы ш ов а Г . Д. Вы чи с ли т ельн ы е м ет оды ли н ейн ойоп т и м и за ци и А ш м а н ов С. А . Л и н ейн ое п р огр а м м и р ов а н и е. - М : На ука, 1981.-304 с . А ш м а н ов С.А ., Ти м охов А .В. Теор и я оп т и м и за ци и в за да ча х и уп р а ж н ен и ях.- М .: На ука , 1991.- 448 с . Ба н ди Б. О с н ов ы ли н ейн огоп р огр а м м и р ов а н и я. – М : Ра ди ои с в язь, 1989.-176 с . К а ли хм а н И . Л . Сбор н и кза да ч п ом а т ем а т и чес ком уп р огр а м м и р ов а н и ю.М : Вы с ш . ш к, 1975.-261 с . К ур и цки йБ.Я . П ои с коп т и м а льн ы х р еш ен и йс р едс т в а м и EXCEL 7.0. – СП б.: BHV-Са н кт -П ет ер бур г,1997.- 280 с . Ю ди н Д.Б., Г ольш т ейн Е.Г . Л и н ейн ое п р огр а м м и р ов а н и е. Теор и я, м ет оды и п р и лож ен и я. –М .: На ука, 1969.- 384 с . Ю ди н Д.Б., Г ольш т ейн Е.Г . За да чи ли н ейн огоп р огр а м м и р ов а н и я т р а н с п ор т н огот и п а .- М : На ука, 1969.- 304 с .

А в т ор ы :

А за р н ов а Та т ьян а Ва с и льев н а К а ш и р и н а И р и н а Л еон и дов н а Ч ер н ы ш ов а Г а ли н а Дм и т р и ев н а

Реда кт ор Ти хом и р ов а О .А .

62