Úvod do optimalizace

´ Pˇredn´ aˇska U-Opt, February 19, 2006:1324

Petr Lachout

´ Uvod do optimalizace

Prof. RNDr. Jitka Dupaˇ cov´ a, DrSc. Doc. RNDr. Petr Lachout, CSc.

KPMS MFF UK Verze 19. u ńora 2006

1

2

Obsah ´ 1 Uvod 2 Optimalizace jako matematick´ au ´ loha 2.1 Funkce jedné promˇenné . . . . . . . . . 2.2 Funkce v´ıce promˇenn´ ych . . . . . . . . . 2.3 Konvexn´ı mnoˇziny . . . . . . . . . . . . 2.4 Konvexn´ı funkce . . . . . . . . . . . . . 2.5 Obecná formulace optimalizaˇcn´ıch u ´loh 2.6 Optimalizace kolem nás . . . . . . . . .

5 . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

7 7 8 9 10 11 12

3 Line´ arn´ı programov´ an´ı ´ 3.1 Uloha LP a jej´ı grafické ˇreˇsen´ı . . . . . . . 3.2 Formulace a zápis u ´lohy LP . . . . . . . . 3.3 Vlastnosti u ´lohy LP ve standardn´ım tvaru 3.4 Základy simplexové metody . . . . . . . . 3.5 Dualita a jej´ı interpretace . . . . . . . . . 3.6 Farkasova vˇeta . . . . . . . . . . . . . . . 3.7 Ekonomická interpretace duality . . . . . 3.8 Poznámky . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

13 13 15 16 18 21 25 25 26

4 Symetrick´ au ´ loha NLP 4.1 Podm´ınky optimality pro symetrické u ´lohy NLP 4.2 Podm´ınky regularity . . . . . . . . . . . . . . . . 4.3 Citlivost u ´lohy NLP . . . . . . . . . . . . . . . . ´ 4.4 Uloha kvadratického programován´ı . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

27 27 28 29 30

5 Dopravn´ı probl´ em

31

6 V´ ypoˇ cetn´ı algoritmy pro optimalizaˇ cn´ı u ´ lohy 6.1 Struˇcn´ y pˇrehled algoritm˚ u pro NLP . . . . . . . . . . 6.2 Metoda seˇcné (opˇerné) nadroviny . . . . . . . . . . . . 6.3 Zobecnˇen´ı gradientn´ıch metod na u ´lohy s omezen´ımi . 6.4 Pˇreveden´ı u ´loh NLP na u ´lohy hledán´ı volného minima

. . . .

33 33 34 36 38

7 Teorie her 7.1 Maticové hry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41 43

Literatura Index

47 48

3

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

4

Kapitola 1

´ Uvod V této pˇrednáˇsce se budeme vˇenovat hledán´ı extrém˚ u dané funkce na zadané mnoˇzinˇe. Jde nám o charakterizaci bod˚ u maxima a minima (matematická anal´ yza) a také o jejich urˇcen´ı (numerická matematika). Uved’me si nˇekolik pˇr´ıklad˚ u z praxe na optimalizaˇcn´ı u ´lohu. Pˇr´ıklad 1: Lyˇzaˇrská oblast ”m´ısa” má hezk´ y terén, ale jsou tam ˇcasto mlhy. Chata je v dol´ıku a chataˇr pouˇst´ı pˇri mlze hlasitˇe hudbu, aby lyˇzaˇri nezabloudili. Hluchému lyˇzaˇri to nepom˚ uˇze. Rozhodl se k návratu do chaty vˇzdy po nejstrmˇejˇs´ım svahu. Vyjde mu jeho strategie? 4 Pˇr´ıklad 2: Horolezec se pohybuje v pro nˇeho neznámém pohoˇr´ı. Chtˇel by vystoupit na jeho nejvyˇsˇs´ı horu. Staˇc´ı mu k tomu lézti vzh˚ uru ve smˇeru nejvˇetˇs´ıho spádu? 4 Pˇr´ıklad 3: Mˇeˇren´ı a hledán´ı nejvˇetˇs´ı hloubky v jezeˇre. 4 Pˇr´ıklad 4: Podnikatel chce maximalizovat sv˚ uj zisk. 4 ˇ Casto je vˇsak tˇreba optimalizovat v´ıce ukazatel˚ u najednou. Pˇr´ıklad 5: Podnikatel chce maximalizovat sv˚ uj v´ ynos a minimalizovat své náklady. 4 Pˇri optimalizaˇcn´ıch u ´lohách se m˚ uˇzeme také setkat s v´ yznamn´ ym vlivem náhody. ´ Pˇr´ıklad 6: Optimalizace portfolia na burze pˇri zadaném objemu poˇcáteˇcn´ıho kapitálu. Ukolem je maximalizovat v´ ynos a minimalizovat riziko. 4 V pˇrednáˇsce se budeme zab´ yvat v´ yhradnˇe optimalizac´ı deterministick´ ych u ´loh, které jsou základn´ım kamenem celé teorie optimalizace. Pokud jsou v u ´loze pˇr´ıtomny i jiné vlivy, jako je náhodnost, neurˇcitost, riziko, nebo je zapotˇreb´ı optimalizovat v´ıce ukazatel˚ u naráz, pak existuj´ı postupy, jak takové u ´lohy ˇreˇsit ˇreˇsen´ım vhodnˇe pˇriˇrazen´ ych deterministick´ ych u ´loh. To je vˇsak jiˇz pˇredmˇetem jin´ ych specializovan´ ych pˇrednáˇsek.

5

6

Kapitola 2

Optimalizace jako matematick´ a u ´ loha U reáln´ ych funkc´ı rozliˇsujeme dva typy extrém˚ u. Jsou to minimum a maximum. Pˇriˇcemˇz kaˇzd´ y z nich m˚ uˇze m´ıt povahu lokáln´ı nebo globáln´ı. Uved’me si pˇresné definice. ˇ Definice 1: Necht’ f : X → R, kde ∅ 6∈ X ⊂ Rn . Rekneme, ˇze funkce f má v bodˇe x∗ ∈ X • lok´ aln´ı minimum, jestliˇze existuje δ > 0: ∀x ∈ X , 0 < |x − x∗ | < δ

⇒

f (x) ≥ f (x∗ ),

(2.1)

⇒

f (x) > f (x∗ ),

(2.2)

⇒

f (x) ≤ f (x∗ ),

(2.3)

⇒

f (x) < f (x∗ ),

(2.4)

• ostr´ e lok´ aln´ı minimum, jestliˇze existuje δ > 0: ∀x ∈ X , 0 < |x − x∗ | < δ • lok´ aln´ı maximum, jestliˇze existuje δ > 0: ∀x ∈ X , 0 < |x − x∗ | < δ • ostr´ e lok´ aln´ı maximum, jestliˇze existuje δ > 0: ∀x ∈ X , 0 < |x − x∗ | < δ • glob´ aln´ı minimum, jestliˇze: ∀x ∈ X

⇒

f (x) ≥ f (x∗ ),

(2.5)

⇒

f (x) > f (x∗ ),

(2.6)

• ostr´ e glob´ aln´ı minimum, jestliˇze: ∀x ∈ X • glob´ aln´ı maximum, jestliˇze: ∀x ∈ X ⇒

f (x) ≤ f (x∗ ),

(2.7)

• ostr´ e glob´ aln´ı maximum, jestliˇze: ∀x ∈ X

2.1

⇒

f (x) < f (x∗ ),

(2.8)

Funkce jedn´ e promˇ enn´ e

Hledáme extrémy funkce jedné promˇenné na celé reálné pˇr´ımce nebo na dané mnoˇzinˇe. Jde nám o charakterizaci bod˚ u maxima a minima (matematická anal´ yza) a také o jejich urˇcen´ı (numerická matematika). Pˇripomeˇ nme si známou vˇetu. 7

8 Vˇ eta 1: Necht’ f : D → R, kde D ⊂ R. Jestliˇze v bodˇe x∗ ∈ int (D) existuje derivace f 0 (x∗ ) a je r˚ uzná od nuly, pak funkce f nemá v bodˇe x∗ ani lokáln´ı maximum ani lokáln´ı minimum. Jin´ ymi slovy, pro funkci, která má vˇsude derivace, je podm´ınka f 0 (x∗ ) = 0 nutn´ a proto, aby mohla m´ıt v bodˇe x∗ ∈ int (D) lokáln´ı extrém. Tento fakt m˚ uˇzeme vyuˇz´ıt pˇri hledán´ı lokáln´ıch i globáln´ıch extrém˚ u, jak ukazuje následuj´ıc´ı pˇr´ıklad. Pˇr´ıklad 7: Hledáme globáln´ı a lokáln´ı extrémy funkce f (x) = 1/4x4 − 5x3 + 27x2 − 40x na celé reálné pˇr´ımce. Nejdˇr´ıve si uvˇedomme, ˇze f 0 (x) = x3 − 15x2 + 54x − 40 = (x − 1)(x − 4)(x − 10). Podle vˇety 1 jen body 1, 4 a 10 mohou b´ yt body lokáln´ıch nebo globáln´ıch extrém˚ u. Pouze v nich je totiˇz derivace uvaˇzované funkce nulová. Pod´ıvejme se nyn´ı na znaménko derivace. V intervalu (−∞, 1) je záporná, v intervalu (1, 4) je kladná, v intervalu (4, 10) je záporná a v intervalu (10, +∞) je kladná. Pro uvaˇzovanou funkci to znamená, ˇze je klesaj´ıc´ı na (−∞, 1), rostouc´ı na (1, 4), klesaj´ıc´ı na (4, 10) a rostouc´ı na (10, +∞). To znamená, ˇze body 1 a 10 jsou body lokáln´ıch minim a bod 4 je bod lokáln´ıho maxima. S globáln´ımi extrémy je to následnˇe. Bod 10 je globáln´ım minimem nebot’ f (1) = −17 − 3/4 a f (10) = −200. Globáln´ı maximum funkce na celé reálné pˇr´ımce nemá. Je to proto, ˇze pˇri velk´ ych i mal´ ych hodnotách funkˇcn´ı hodnoty rostou nad vˇsechny meze. 4 Pˇr´ıklad 8: Hledáme globáln´ı a lokáln´ı extrémy funkce f (x) = 1/4x4 − 5x3 + 27x2 − 40x na intervalu [0, 20]. Pouˇzijeme-li v´ ysledky z pˇredchoz´ıho pˇr´ıkladu a spoˇcteme-li, ˇze f (4) = 16 a f (20) = 40800, pak zjiˇst’ujeme, ˇze funkce má lokáln´ı minima v bodech 1 a 10, lokáln´ı maxima v bodech 4 a 20. Globáln´ı minimum má opˇet v bodˇe 10 a globáln´ı maximum je v bodˇe 20. 4 Pˇr´ıklad 9: Hledáme globáln´ı a lokáln´ı extrémy funkce f (x) = 1/4x4 − 5x3 + 27x2 − 40x na intervalu (0, 20). Pouˇzijeme-li v´ ysledky z pˇredchoz´ıho pˇr´ıkladu, pak zjiˇst’ujeme, ˇze funkce má lokáln´ı minima v bodech 1 a 10, lokáln´ı maximum v bodˇe 4. Globáln´ı minimum má opˇet v bodˇe 10 a globáln´ı maximum funkce nemá nebot’ funkˇcn´ı hodnoty bl´ızko bodu 20 jsou vˇetˇs´ı neˇzli v bodˇe 4. 4 Pˇripomeˇ nme si jeˇstˇe jednu vˇetu z matematické anal´ yzy. Vˇ eta 2: Spojitá funkce jedné promˇenné má na omezeném uzavˇreném intervalu globáln´ı maximum i globáln´ı minimum.

2.2

Funkce v´ıce promˇ enn´ ych

Podobnˇe lze postupovat pro funkce v´ıce promˇenn´ ych, zpravidla funkce na Rn . Podle potˇreby budeme pouˇz´ıvat tuˇcná p´ısmena na oznaˇcen´ı n-tice promˇenn´ ych, tj. x = (x1 , . . . , xn ) nebo sloupcov´ eho vektoru o sloˇzkách x1 , . . . , xn . Vˇ eta 3: Necht’ f : D → R, kde D ⊂ Rn . Jestliˇze v bodˇe x∗ = (x∗1 , . . . , x∗n ) ∈ int (D) aspoˇ n pro jeden ∂f ∗ ∗ index j, 1 ≤ j ≤ n, existuje nenulová parciáln´ı derivace ∂x (x ), pak f v bodˇ e x nenab´ y v´ a ani lokáln´ıho j maxima ani lokáln´ıho minima. Uved’me si jeˇstˇe obecn´ y tvar vˇety 2. Vˇ eta 4: Spojitá funkce f : D → R, kde D ⊂ Rn je omezená uzavˇrená mnoˇzina, nab´ yvá na mnoˇzinˇe D svého globáln´ıho maxima i globáln´ıho minima. Omez´ıme se vˇetˇsinou na funkce, které maj´ı derivace a pro které jsou lokáln´ı minima (maxima) globáln´ı. Posledn´ı vlastnost maj´ı konvexn´ı (konkávn´ı) funkce.


2.3

9

Petr Lachout

Konvexn´ı mnoˇ ziny

Nejdˇr´ıve se mus´ıme seznámit s konvexn´ımi mnoˇzinami v koneˇcnˇe dimenzionáln´ım Eukleidovském prostoru. Pozdˇeji vyuˇzijeme ˇradu jejich vlastnost´ı. Definice 2: Mnoˇzina X ⊂ Rn se naz´ yvá konvexn´ı, jestliˇze s kaˇzd´ ymi dvˇema body obsahuje také vˇsechny jejich konvexn´ı line´ arn´ı kombinace, tj. pro kaˇzdé x, y ∈ X a λ ∈ (0, 1) je také λx + (1 − λ)y ∈ X . Poznamenejme, ˇze prázdná mnoˇzina je z definice také konvexn´ı. Jako pˇr´ıklad konvexn´ı mnoˇziny si m˚ uˇzeme uvést kruh, ˇctverec, obdéln´ık, pˇr´ımku, polopˇr´ımku, u ´seˇcku, atd. Nekonvexn´ımi mnoˇzinami jsou kruˇznice, obvod ˇctverce, doplnˇek ˇctverce, doplnˇek kruhu, atd. Pro speciáln´ı konvexn´ı mnoˇziny budeme pouˇz´ıvat následuj´ıc´ı názvoslov´ı. Definice 3: Pro speciáln´ı konvexn´ı mnoˇziny budeme pouˇz´ıvat: ¯ © ª • nadrovina, lze-li ji zapsat jako x ∈ Rn ¯ a> x = c ; ¯ © ª • uzavˇ ren´ y poloprostor, lze-li ji zapsat jako x ∈ Rn ¯ a> x ≥ c ; ¯ © ª • otevˇ ren´ y poloprostor, lze-li ji zapsat jako x ∈ Rn ¯ a> x > c ; • konvexn´ı polyedrick´ a mnoˇ zina, je-li pr˚ unikem koneˇcnˇe mnoha uzavˇren´ ych poloprostor˚ u; • konvexn´ı polyedr, je-li omezenou konvexn´ı polyedrickou mnoˇzinou; • kuˇ zel je mnoˇzina K ⊂ Rn , která obsahuje poˇcátek, tj. 0 ∈ K, a nezáporné násobky sv´ ych prvk˚ u, tj. ∀ x ∈ K, α ≥ 0 je také αx ∈ K; • konvexn´ı kuˇ zel je mnoˇzina K ⊂ Rn , která obsahuje poˇcátek, tj. 0 ∈ K, a s kaˇzd´ ymi dvˇema body obsahuje také vˇsechny jejich pozitivn´ı line´ arn´ı kombinace, tj. ∀x, y ∈ K, α ≥ 0, β ≥ 0 je také αx + βy ∈ K; • konvexn´ı polyedrick´ y kuˇ zel, je-li konvexn´ı kuˇzel a souˇcasnˇe i konvexn´ı polyedrická mnoˇzina. Nˇekteré mnoˇzinové operace zachovávaj´ı konvexitu mnoˇzin. Lemma 1: Necht’ A ⊂ Rn je konvexn´ı mnoˇzina. Pak také clo (A), int (A), rint (A) jsou konvexn´ı mnoˇziny. Lemma 2: Necht’ A ⊂ Rn je konvexn´ı mnoˇzina a α ∈ R. Pak také αA = {αa | a ∈ A } je konvexn´ı mnoˇzina. Lemma 3: Necht’ A, B ⊂ Rn jsou konvexn´ı mnoˇziny. Pak také A + B = {a + b | a ∈ A, b ∈ B } ,

A − B = {a − b | a ∈ A, b ∈ B }

jsou konvexn´ı mnoˇziny. n Lemma 4: Necht’ I je nˇejaká nepr´ T azdná indexová mnoˇzina a Xα ⊂ R jsou konvexn´ı mnoˇziny pro kaˇzdé α ∈ I. Potom také jejich pr˚ unik α∈I Xα je konvexn´ı mnoˇzina.

Sjednocen´ı mnoˇzin vˇsak konvexitu nezachovává. Pˇredstavme si sjednocen´ı dvou kruh˚ u o stejn´ ych polomˇerech ale r˚ uzn´ ych stˇredech. Zavád´ıme dvˇe nové mnoˇzinové operace. Definice 4: Pro mnoˇzinu A ⊂ Rn zavád´ıme ¯ ( k ) k ¯ X X ¯ conv (A) = αi ai ¯ α1 ≥ 0, . . . , αk ≥ 0, αi = 1, a1 ∈ A, . . . , ak ∈ A, k ∈ N , (2.9) ¯ i=1 i=1 ¯ ( k ) ¯ X ¯ pos (A) = {0} ∪ (2.10) αi ai ¯ α1 ≥ 0, . . . , αk ≥ 0, a1 ∈ A, . . . , ak ∈ A, k ∈ N . ¯ i=1

Mnoˇzina conv (A) se naz´ yvá konvexn´ı obal mnoˇ ziny A a pos (A) je nejmenˇ s´ı konvexn´ı kuˇ zel obsahuj´ıc´ı mnoˇ zinu A.

10 Uvˇedomme si, ˇze z definice conv (∅) = ∅ a pos (∅) = {0}. Vˇ eta 5: Mnoˇzina conv (A) je nejmenˇs´ı konvexn´ı mnoˇzina obsahuj´ıc´ı mnoˇzinu A a pos (A) je nejmenˇs´ı konvexn´ı kuˇzel obsahuj´ıc´ı mnoˇzinu A. Mezi hraniˇcn´ımi body mnoˇziny jsou nˇekteré body a smˇery v´ yznaˇcné. Definice 5: Necht’ A ⊂ Rn je neprázdná mnoˇzina. Pak bod a ∈ A naz´ yváme krajn´ı bod mnoˇ ziny A, pokud neexistuje dvojice bod˚ u x, y ∈ A, x 6= y a 0 < α < 1 tak, aby a = αx + (1 − α)y. Definice 6: Necht’ K ⊂ Rn je kuˇzel. Pak smˇer a ∈ K, a 6= 0 naz´ yváme krajn´ım smˇ erem kuˇ zelu K, pokud neexistuje dvojice bod˚ u x, y ∈ A, x, y ∈ / pos (a) a α > 0, β > 0 tak, aby a = αx + βy. Krajn´ı body m˚ uˇzeme charakterizovat i jinak. Lemma 5: Necht’ A ⊂ Rn je neprázdná mnoˇzina. Pak bod a ∈ A je krajn´ım bodem mnoˇziny A, pokud v kaˇzdém smˇeru h ∈ Rn , h 6= 0 bud’ a + αh 6∈ A, ∀α > 0 a nebo a − αh 6∈ A, ∀α > 0. Krajn´ı body plnˇe charakterizuj´ı konvexn´ı polyedry. Vˇ eta 6: Neprázdn´ y konvexn´ı polyedr má koneˇcnˇe mnoho krajn´ıch bod˚ u a je jejich konvexn´ım obalem. Vˇ eta 7: Konvexn´ı polyedrick´ y kuˇzel má koneˇcnˇe mnoho krajn´ıch smˇer˚ u a je nejmenˇs´ım konvexn´ım kuˇzelem, kter´ y je obsahuje.

2.4

Konvexn´ı funkce

ˇ Definice 7: Necht’ je X ⊂ Rn konvexn´ı. Rekneme, ˇze je funkce f : X → R konvexn´ı, jestliˇze plat´ı ³ ´ x(1) , x(2) ∈ X , λ ∈ (0, 1) ⇒ f (λx(1) + (1 − λ)x(2) ) ≤ λf (x(1) ) + (1 − λ)f (x(2) ). ˇ Rekneme, ˇze funkce f : X → R je konk´ avn´ı, jestliˇze −f je konvexn´ı funkce. Lemma 6: Necht’ I ⊂ R je otevˇren´ y interval a funkce f : I → R je diferencovatelná v kaˇzdém bodˇe I, pak f je konvexn´ı funkce tehdy a jen tehdy, kdyˇz f 0 je neklesaj´ıc´ı funkce na I. Kdyˇz má funkce druhé parciáln´ı derivace, pak o jej´ı konvexnosti rozhoduje matice druh´ ych derivac´ı. Lemma 7: Necht’ X ⊂ Rn je otevˇrená mnoˇzina a funkce f : X → R má druhé parciáln´ı derivace v kaˇzdém bodˇe X . Pak ı funkce tehdy a jen tehdy, kdyˇz jej´ı matice druh´ ych parciáln´ıch ´ ³ f2 je konvexn´ f (x) je pozitivnˇ e semidefinitn´ ı v kaˇ z d´ e m bodˇ e x ∈ X . derivac´ı ∇2x,x f (x) = ∂x∂i ∂x j Speciálnˇe, kdyˇz I ⊂ R je otevˇren´ y interval a funkce f : I → R je dvakrát diferencovatelná v kaˇzdém bodˇe I, pak f je konvexn´ı funkce tehdy a jen tehdy, kdyˇz f 00 (x) ≥ 0 v kaˇzdém bodˇe x ∈ I. Pro ovˇeˇren´ı, ˇze daná symetrická matice A je pozitivnˇe semidefinitn´ı m˚ uˇzeme vyuˇz´ıt známá tvrzen´ı z lineárn´ı algebry. Lemma 8: Symetrická matice A je pozitivnˇe semidefinitn´ı tehdy a jen tehdy, kdyˇz determinanty vˇsech hlavn´ıch podmatic matice A jsou nezáporné.

Lemma 9: Symetrická matice A je pozitivnˇe definitn´ı tehdy a jen tehdy, kdyˇz determinanty vˇsech hlavn´ıch rohov´ ych podmatic matice A jsou kladné.


11

Petr Lachout

Konvexn´ı funkce jsou charakterizovány následuj´ıc´ı vlastnost´ı. Lemma 10: Necht’ f : Rn → R má gradient na Rn . Pak f je konvexn´ı, právˇe kdyˇz pro kaˇzdé x ∈ Rn plat´ı f (y) ≥ f (x) + (y − x)> ∇x f (x) ∀y ∈ Rn . (2.11) D˚ ukaz: 1. Nutnost. Zvolme x, y ∈ Rn , oznaˇcme h = y − x, ϕ(µ) = f (x + µh). Pak ϕ je konvexn´ı diferencovatelná funkce jedné promˇenné a jej´ı derivace je ϕ0 (µ) = h> ∇x f (x + µh). Podle vˇety o stˇredn´ı hodnotˇe existuje θ ∈ (0, 1) tak, ˇze f (y) − f (x) = ϕ(1) − ϕ(0) = ϕ0 (θ) ≥ ϕ0 (0) = h> ∇x f (x) plat´ı tedy (2.11). (Pouˇzili jsme skuteˇcnost, ˇze derivace konvexn´ı diferencovatelné funkce je neklesaj´ıc´ı funkce.) 2. Postaˇcitelnost. Zvolme y, z ∈ Rn , plat´ı (2.11):

λ ∈ (0, 1) a oznaˇcme x = λy + (1 − λ)z. Podle pˇredpokladu f (y) − f (x) ≥ (y − x)> ∇x f (x) f (z) − f (x) ≥ (z − x)> ∇x f (x)

Odtud >

λf (y) + (1 − λ)f (z) ≥ f (x) + [λ(y − x) + (1 − λ)(z − x)] ∇x f (x) = f (x) = f (λy + (1 − λ)z). Podle definice 7 je f konvexn´ı. Q.E.D. Konvexn´ı funkce maj´ı vzhledem k minimalizaci jednu uˇziteˇcnou vlastnost. Vˇ eta 8: Necht’ je X ⊂ Rn konvexn´ı a necht’ f : X → R je konvexn´ı funkce. Pak kaˇzdé jej´ı lokáln´ı minimum je minimem globáln´ım. ¯ lokáln´ı minimum funkce f na X . To znamená, ˇze x ¯ ∈ X a existuje ² > 0 tak, D˚ ukaz: Necht’ je v bodˇe x ˇze plat´ı ¯ | < ². f (¯ x) ≤ f (x) ∀x ∈ X , |x − x Necht’ ale nejde o globáln´ı minimum, tj. necht’ existuje x∗ ∈ X , f (¯ x) > f (x∗ ). Uvaˇzujme body y na u ´seˇcce ∗ ∗ ¯ spojuj´ıc´ı x a x . Jsou tedy tvaru y = λ¯ x + (1 − λ)x pro nˇejaké λ ∈ [0, 1]. Vˇsechny tyto body leˇz´ı v mnoˇzinˇe X , nebot’ mnoˇzina X je konvexn´ı. Pro body y, které nejsou krajn´ımi body této u ´seˇcky plat´ı f (y) = f (λ¯ x + (1 − λ)x∗ ) ≤ λf (¯ x) + (1 − λ)f (x∗ ) < f (¯ x)

∀λ ∈ (0, 1)

(2.12)

Necht’ bod y leˇz´ı v pr˚ useˇc´ıku okol´ı U(¯ x, ²) a této u ´seˇcky. Leˇz´ı tedy v okol´ı U(¯ x, ²) bodu lokáln´ıho minima ¯ a pˇritom i pro nˇej plat´ı (2.12), coˇz je spor. x Q.E.D. Pro hledán´ı extrém˚ u na uzavˇ ren´ e mnoˇzinˇe X ∈ Rn nestaˇc´ı vˇety 1 nebo 3. Je tˇreba zvláˇst’ oˇsetˇrit hranici mnoˇziny X , jak ukazuj´ı pˇr´ıklady v kapitole 2.1.

2.5

Obecn´ a formulace optimalizaˇ cn´ıch u ´ loh

Matematická formulace a specifikace c´ıle daného zadavatelem, omezen´ı dan´ ych systémem, diskuse alternativn´ıch zadán´ı vede k sestaven´ı obecného matematického modelu. ´ neline´ arn´ıho programov´ an´ı (NLP) (ˇcasto se téˇz pouˇz´ıvá term´ın u ´loha matematick´ eho Uloha programov´ an´ı (MP)) je u ´loha minimalizovat (maximalizovat) funkci f (x1 , . . . , xn )

12 na mnoˇzinˇe ˇreˇsen´ı soustavy rovnic a nerovnost´ı gk (x1 , . . . , xn ) ≤ 0,

k = 1, . . . , m

(2.13)

hj (x1 , . . . , xn ) = 0,

j = 1, . . . , p.

(2.14)

Rozeznáváme nˇekolik základn´ıch typ˚ uu ´lohy (NLP). • Pokud jsou vˇsechny funkce f, gk , hj lineárn´ı, jde o u ´lohu line´ arn´ıho programov´ an´ı (LP). • Mluv´ıme o u ´loze konvexn´ıho programov´ an´ı, pokud se bud’ jedná o minimalizaci a f, gk jsou konvexn´ı a hj jsou lineárn´ı, nebo se jedná o maximalizaci a f je konkávn´ı, gk jsou konvexn´ı a hj jsou lineárn´ı. • Mluv´ıme o u ´loze kvadratick´ eho programov´ an´ı, pokud f je kvadratická a gk , hj jsou lineárn´ı. ´ Uloha konvexn´ıho programován´ı má pˇr´ıjemné vlastnosti. Vˇ eta 9: Necht’ jsou funkce gk , ∀k konvexn´ı a funkce hj , ∀j lineárn´ı. Pak je mnoˇzina vˇsech ˇreˇsen´ı soustavy (2.13), (2.14) konvexn´ı. D˚ ukaz: Z definic 2 a 7. (!! Prázdná mnoˇzina je konvexn´ı!!) Q.E.D. Vˇ eta 10: Necht’ je dána u ´loha konvexn´ıho programován´ı pro minimalizaci. Pak kaˇzdé jej´ı lokáln´ı minimum je zároveˇ n globáln´ım minimem. D˚ ukaz: Z vˇety 9 v´ıme, ˇze minimalizujeme konvexn´ı funkci na konvexn´ı mnoˇzinˇe. Proto bezprostˇrednˇe z vˇety 8 dostáváme, ˇze lokáln´ı minimum je minimem globáln´ım. Q.E.D.

2.6

Optimalizace kolem n´ as

Optimalizaˇcn´ı u ´lohy pˇrirozenˇe vznikaj´ı pˇri ˇr´ızen´ı sloˇzit´ ych systém˚ u pˇri hledán´ı optimáln´ıho rozhodnut´ı. Jako pˇr´ıklady si m˚ uˇzeme uvést: dopravn´ı problém; pˇridˇelovac´ı problém; smˇeˇsovac´ı u ´lohy; sestavován´ı rozvrhu ve ˇskole; rozhodován´ı o investic´ıch; sestavován´ı optimáln´ıho v´ yrobn´ıho programu; prokládán´ı regresn´ı funkce namˇeˇren´ ymi hodnotami; atd. Uved’me si struˇcn´ y historick´ y pˇrehled v´ yvoje této problematiky. • teoretická mechanika (Laplace, Fourier) - 1888; • soustavy nerovnost´ı (Farkas)- 1902; • lineárn´ı programován´ı (Kantoroviˇc, Koopmans, Dantzig) - 2. svˇetová válka; • nelineárn´ı programován´ı (Kuhn, Tucker, ...) - 1956; Souˇcasn´ ym trendem je studium sloˇzitˇejˇs´ıch typ˚ u rozhodovac´ıch u ´loh - stochastická a vektorová optimalizace, celoˇc´ıselné a dynamické programován´ı.

Kapitola 3

Line´ arn´ı programov´ an´ı V této kapitole vyloˇz´ıme teorii lineárn´ıho programován´ı.

3.1

´ Uloha LP a jej´ı grafick´ eˇ reˇ sen´ı

Pˇr´ıklad 10: Uvaˇzujme u ´lohu minimalizovat

x1 − x2 ,

za podm´ınek

2x1 + x2

≥ 2,

−3x1 + 2x2

≤ 6,

x1 + x2 ≤ 4, x1 ≥ 0, x2 ≥ 0. Mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı je mnoˇzina M = {(x1 , x2 ) | 2x1 + x2 ≥ 2, −3x1 + 2x2 ≤ 6, x1 + x2 ≥ 4, x1 ≥ 0, x2 ≥ 0 } . Jedná se o konvexn´ı pˇeti´ uheln´ık s vrcholy

¡ 1¢ ¡ 4¢ ¡ 2 ¢ ¡ 0¢ ¡ 0¢ 5 azek ˇc.3.1. 0 , 0 , 18 , 3 , 2 ; viz obr´ 5

6 5 4 3 2

M

1 0 −1 −1

0

1

2

3

4

5

6

Obrázek 3.1: Mnoˇzina M z pˇr´ıkladu 10 Vyneseme-li si rovnobˇeˇzky x1 − x2 = k pro k = 0, −1, −2, zjist´ıme, ˇze funkce f (x1 , x2 ) = x1 − x2 ¡2¢ 5 nab´ yvá svého minima na mnoˇzinˇe M v bodˇe 18 . 5

13

14 Optimáln´ı ˇreˇsen´ı dané u ´lohy je tedy x ˆ1 = 25 , x ˆ2 = x ˆ1 − x ˆ2 =

18 5

a optimáln´ı hodnota u ´ˇcelové funkce je

2 18 16 − =− . 5 5 5 4


x1 − x2 ,

za podm´ınek

2x1 + x2

≥

2,

−3x1 + 2x2

≤

6,

x1 + x2 ≤ −1, x1 ≥ 0, x2 ≥ 0. Mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı je mnoˇzina M = {(x1 , x2 ) | 2x1 + x2 ≥ 2, −3x1 + 2x2 ≤ 6, x1 + x2 ≤ −1, x1 ≥ 0, x2 ≥ 0 } = ∅. ´ Uloha tedy nemá ˇzádné pˇr´ıpustné ˇreˇsen´ı a t´ım pádem nemá ani ˇzádné optimáln´ı ˇreˇsen´ı. 4 Pˇr´ıklad 12: Uvaˇzujme u ´lohu minimalizovat

x1 − x2 ,

za podm´ınek

2x1 + x2

≥ 2,

−3x1 + 2x2 ≤ 6, x1 ≥ 0, x2 ≥ 0. Mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı M = {(x1 , x2 ) | 2x1 + x2 ≥ 2, −3x1 + 2x2 ≤ 6, x1 ≥ 0, x2 ≥ 0 } je neomezená. Vˇsechny rovnobˇeˇzky x1 − x2 = k pro k = 1, −1, −2, −3, . . . . maj´ı s M neprázdn´ y pr˚ unik. To znamená, ˇze funkˇcn´ı hodnoty u ´ˇcelové funkce na M neomezenˇe klesaj´ı. Proto u ´loha nemá optimáln´ı ˇreˇsen´ı. 4 Pˇr´ıklad 13: Uvaˇzujme u ´lohu minimalizovat

2x1 − x2 ,

za podm´ınek

2x1 + x2

≥ 2,

−3x1 + 2x2 ≤ 6, x1 ≥ 0, x2 ≥ 0. V´ıme, ˇze mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı M = {(x1 , x2 ) | 2x1 + x2 ≥ 2, −3x1 + 2x2 ≤ 6, x1 ≥ 0, x2 ≥ 0 } je neomezená. Z obrázku pak zjist´ıme, ˇze u ´loha má optimáln´ı ˇreˇsen´ı x ˆ1 = 0, x ˆ2 = 3 a optimáln´ı hodnota u ´ˇcelové funkce −3. 4


15

Petr Lachout


3x1 − 2x2 ,

za podm´ınek

2x1 + x2

≥ 2,

−3x1 + 2x2 ≤ 6, x1 ≥ 0, x2 ≥ 0. Z grafického znázornˇen´ı u ´lohy zjist´ıme, ˇze optimáln´ı hodnota u ´ˇcelové funkce −6 a nab´ yvá se j´ı ve vˇsech bodech tvaru x ˆ1 = 25 λ, x ˆ2 = 3 + 35 λ pro λ ≥ 0. 4 Pˇr´ıklad 15: Uvaˇzujme u ´lohu minimalizovat

3x1 − 2x2 ,

za podm´ınek

2x1 + x2

≥ 2,

−3x1 + 2x2

≤ 6,

x1 + x2 ≤ 4, x1 ≥ 0, x2 ≥ 0. Z grafického znázornˇen´ı u ´lohy zjist´ıme, ˇze optimáln´ı hodnota u ´ˇcelové funkce −6 a nab´ yvá se j´ı ve vˇsech ˆ2 = 3 + 35 λ pro 0 ≤ λ ≤ 1. bodech tvaru x ˆ1 = 25 λ, x 4

3.2

Formulace a z´ apis u ´ lohy LP

´ sen´ em tvaru Uloha LP ve sm´ıˇ minimalizovat (maximalizovat)

c> x

za podm´ınek a> j x

≥ bj

pro kaˇzdé j ∈ J≥ ,

a> j x a> j x

≤ bj

pro kaˇzdé j ∈ J≤ ,

= bj

pro kaˇzdé j ∈ J= ,

xi

≥ 0

pro kaˇzdé i ∈ I≥ ,

xi

≤ 0

pro kaˇzdé i ∈ I≤ ,

xi

∈

pro kaˇzdé i ∈ I∈ ,

R

(3.1)

kde I≥ ∪ I≤ ∪ I∈ = {1, 2, . . . , n}, J≥ ∪ J≤ ∪ J= = {1, 2, . . . , m} jsou disjunktn´ı rozklady index˚ u. Pro v´ ypoˇcetn´ı algoritmus a pro teoretické u ´vahy jsou d˚ uleˇzité u ´lohy ve speciáln´ıch tvarech. ´ Uloha LP ve standardn´ım tvaru minimalizovat

c> x


= bj

pro kaˇzdé j = 1, 2, . . . , m,

xi

≥ 0

pro kaˇzdé i = 1, 2, . . . , n.

(3.2)

´ Uloha LP je ve tvaru nerovnost´ı, jsou-li vˇsechny promˇenné nezáporné a omezen´ı jsou pouze ve tvaru nerovnost´ı. Napˇr´ıklad minimalizovat

c> x


≥ bj

pro kaˇzdé j = 1, 2, . . . , m,

xi

≥ 0

pro kaˇzdé i = 1, 2, . . . , n.

(3.3)

16 ´ Ulohu LP ve sm´ıˇseném tvaru lze vˇzdy pˇrevést na u ´lohu LP ve standardn´ım tvaru. Vˇzdy ji také lze pˇrevést na u ´lohu LP ve tvaru nerovnost´ı. K pˇrevodu se pouˇz´ıvaj´ı následuj´ıc´ı u ´pravy: • min f (x) = − max −f (x). x∈M

x∈M

• Nerovnost aj,1 x1 + aj,2 x2 + . . . + aj,n xn ≤ bj pˇrevedeme na rovnost pˇridán´ım skluzov´ e promˇ enn´ e vj ≥ 0 tak, ˇze aj,1 x1 + aj,2 x2 + . . . + aj,n xn + vj = bj . • Nerovnost aj,1 x1 + aj,2 x2 + . . . + aj,n xn ≥ bj pˇrevedeme na rovnost pˇridán´ım skluzov´ e promˇ enn´ e vj ≥ 0 tak, ˇze aj,1 x1 + aj,2 x2 + . . . + aj,n xn − vj = bj . • Rovnost aj,1 x1 + aj,2 x2 + . . . + aj,n xn = bj pˇrevedeme na dvˇe nerovnosti aj,1 x1 + aj,2 x2 + . . . + aj,n xn ≤ bj , aj,1 x1 + aj,2 x2 + . . . + aj,n xn ≥ bj . • Promˇennou bez omezen´ı xi ∈ R rozdˇel´ıme na dvˇe promˇenné xi = xi+ − xi− , kde xi+ ≥ 0, xi− ≥ 0. (Zde je tˇreba poznamenat, ˇze tyto promˇenné nejsou kladnou a zápornou ˇcást´ı promˇenné xi . Mohou b´ yt obˇe zároveˇ n kladné!!)

3.3

Vlastnosti u ´ lohy LP ve standardn´ım tvaru

V tomto odstavci se budeme zab´ yvat u ´lohou LP ve standardn´ım tvaru, tj. u ´lohou (3.2). Tato u ´loha má mnoˇ zinu pˇ r´ıpustn´ ych ˇ reˇ sen´ı M = {x ∈ Rn | Ax = b, x ≥ 0 } ,

(3.4)

kde A je matice dimenze (m, n), m < n a hodnost A je m. (T´ım jsou jiˇz urˇceny dimenze vektor˚ u b, x.) Vˇ eta 11: Mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı u ´lohy LP ve standardn´ım tvaru (3.4) je konvexn´ı polyedrická mnoˇzina; speciálnˇe je konvexn´ı a uzavˇren´ a. D˚ ukaz: D˚ ukaz je snadn´ y. Tato mnoˇzina je evidentnˇe pr˚ unikem koneˇcného poˇctu uzavˇren´ ych poloprostor˚ u. Q.E.D. Vˇ eta 12: Mnoˇzina (3.4) je bud’ prázdná nebo je tvaru algebraického souˇctu M=P +K

(3.5)

kde P je konvexn´ı polyedr a mnoˇzina K = {y ∈ Rn | Ay = 0, y ≥ 0 }

je konvexn´ı polyedrick´ y kuˇzel.

(3.6)

Definice 8: Oznaˇcme si sloupce matice A jménem promˇenné, ke které pˇr´ısluˇsej´ı, tj. A = (Ax1 , Ax2 , . . . , Axn ). Vyberme nyn´ı mnoˇzinu jmen promˇenn´ ych L ⊂ {x1 , x2 , . . . , xn } tak, aby obsahovala právˇe m poloˇzek. Vezmˇeme pˇr´ısluˇsné sloupce matice A a sestavme z nich ˇctvercovou matici AL = (Axj , xj ∈ L). • Pokud je matice AL regulárn´ı, pak ˇr´ıkáme, ˇze L je b´ aze u ´lohy (3.2). • Kdyˇz L je báze, pak k n´ı pˇr´ısluˇs´ı x(L) ∈ Rn jednoznaˇcnˇe urˇcené podm´ınkami Ax(L) = b a x(L)i = 0 pro vˇsechna xi 6∈ L. x(L) naz´ yváme bazick´ eˇ reˇ sen´ı pˇr´ısluˇsné k bázi L. • Necht’ L je báze a pˇr´ısluˇsné bazické ˇreˇsen´ı x(L) je nezáporné. Pak mluv´ıme a pˇ r´ıpustn´ e b´ azi L, r´ıpustn´ em bazick´ em ˇ reˇ sen´ı x(L). pˇr´ıpadnˇe o pˇ Poznámka. Konvexn´ı polyedr P z vˇety je konvexn´ım obalem pˇr´ıpustn´ ych bazick´ ych ˇreˇsen´ı. M´ısto ”pˇr´ıpustné bazické ˇreˇsen´ı” se také pouˇz´ıvá název ”základn´ı ˇreˇsen´ı”; tak je to také v [2]. Mnoˇzina M je neprázdná a omezená, právˇe kdyˇz je K = {0}.

√

D˚ usledek 1: Bazická pˇr´ıpustná ˇreˇsen´ı maj´ı nejv´ yˇse m sloˇzek kladn´ ych a pro M 6= ∅ má u ´loha (3.2) koneˇcn´ y poˇcet bazick´ ych pˇr´ıpustn´ ych ˇreˇsen´ı. ˇ ıkáme, ˇze pˇr´ıpustné bazické ˇreˇsen´ı je degenerovan´ Definice 9: R´ e, jestliˇze má ménˇe neˇz m kladn´ ych sloˇzek.


17

Petr Lachout

´ Vˇ eta 13 (Existence optim´ aln´ıho ˇreˇsen´ı): Uloha (3.2) má optimáln´ı ˇreˇsen´ı tehdy a jen tehdy, kdyˇz 1. M 6= ∅, 2. c> y ≥ 0 pro vˇsechna y ∈ {x ∈ Rn | Ax = 0, x ≥ 0 }. Má-li u ´loha optimáln´ı ˇreˇsen´ı, pak u ´ˇcelová funkce c> x nab´ yvá svého minima na M pro nˇekteré bazické základn´ı ˇreˇsen´ı. D˚ ukaz: Podle vˇety 12 v´ıme, ˇze M = conv (B) + K, kde B = {x(1) , x(2) , . . . , xr } ⊂ Rn je mnoˇzina vˇsech pˇr´ıpustn´ ych bazick´ ych ˇreˇsen´ı. r r P P Tedy kaˇzdé x ∈ M lze zapsat ve tvaru x = λj xj + y, pˇriˇcemˇz λj ≥ 0, λj = 1 a y ∈ K. j=1

j=1

Hodnota u ´ˇcelové funkce v tomto bodˇe je >

c x=

r X

λj c> xj + c> y.

(3.7)

j=1

1. Je-li c> y < 0, pak pro kaˇzdé α > 0 je αy ∈ K. Odtud z =

r P j=1

λj xj + αy ∈ M s hodnotou u ´ˇcelové

funkce c> z =

r X

λj c> xj + αc> y.

j=1

Tud´ıˇz ve smˇeru y u ´ˇcelová funkce neomezenˇe klesá. Nenab´ yvá tedy svého minima. 2. Je-li c> y ≥ 0 pro vˇsechna y ∈ K, pak z (3.7) dostáváme c> z =

r X

λj c> xj + c> y ≥

j=1

r X

λj c> xj ≥ min{c> x(1) , c> x(2) , . . . , c> xr }.

j=1

Tud´ıˇz u ´loha (3.2) nab´ yvá svého minima v nˇekterém pˇr´ıpustném bazickém ˇreˇsen´ı. Q.E.D. Mnoˇzinu vˇsech optimáln´ıch ˇreˇsen´ı u ´lohy (3.2) budeme znaˇcit ¯ ½ ¾ ¯ > ∗ > > ¯ M = argmax c x = z ∈ M ¯ c z = max c x . x∈M

x∈M

(3.8)

V´ ysledky shrnuje následuj´ıc´ı vˇeta. Vˇ eta 14 (Z´ akladn´ı vˇ eta line´ arn´ıho programov´ an´ı): Pro u ´lohu lineárn´ıho programován´ı ve standardn´ım tvaru, t.j. (3.2), nastává pouze jedna ze tˇr´ı moˇznost´ı: a) M = ∅, b) M 6= ∅ a inf x∈M c> x = −∞ (tj. M∗ = ∅), c) M∗ 6= ∅. Nav´ıc pak • je-li M 6= ∅, existuje bazické pˇr´ıpustné ˇreˇsen´ı, • je-li M∗ 6= ∅, existuje bazické optimáln´ı ˇreˇsen´ı. Má-li u ´loha (3.2) optimáln´ı ˇreˇsen´ı, pak jej vˇzdy m˚ uˇzeme naj´ıt mezi pˇr´ıpustn´ ymi bazick´ ymi ˇreˇsen´ımi. Tato myˇslenka vede k pˇr´ımé metodˇe ˇreˇsen´ı u ´loh LP.

Pˇ r´ım´ a metoda

18 Projdi vˇsechny pˇr´ıpustná bazická ˇreˇsen´ı u ´lohy (3.2) a zjisti pro které z nich u ´ˇcelová funkce u ´lohy nab´ yvá ˆ. minimáln´ı hodnotu. Oznaˇcme si toto pˇr´ıpustné bazické ˇreˇsen´ı x • Pokud neexistuje ˇzádné pˇr´ıpustné bazické ˇreˇsen´ı u ´lohy (3.2), pak u ´loha nemá pˇr´ıpustné ˇreˇsen´ı. • Kdyˇz má u ´loha (3.2) optimáln´ı ˇreˇsen´ı (to m˚ uˇzeme vˇedˇet napˇr´ıklad na základˇe vˇety 13), pak nalezené ˆ je optimáln´ım ˇreˇsen´ım zadané u pˇr´ıpustné bazické ˇreˇsen´ı x ´lohy. √ Tato metoda je ale numericky sch˚ udná jen pro velice malé u ´lohy a nav´ıc nemá jednoduché kritérium pro existenci optimáln´ıho ˇreˇsen´ı. Pro nalezen´ı optimáln´ıho ˇreˇsen´ı u ´lohy (3.2) se nejˇcastˇeji pouˇz´ıvá simplexová metoda, zaloˇzená na hledán´ı optimáln´ıho bazického pˇr´ıpustného ˇreˇsen´ı. Je to vlastnˇe Gauss˚ uv eliminaˇcn´ı algoritmus pro ˇreˇsen´ı soustavy rovnic Ax = b doplnˇen´ y pravidlem pro zachován´ı nezápornosti ˇreˇsen´ı a pravidlem, které dbá na to, aby hodnoty u ´ˇcelové funkce klesaly. S touto metodou se seznám´ıme v dalˇs´ı kapitole.

3.4

Z´ aklady simplexov´ e metody

ˇ s´ıme u Reˇ ´lohu LP pˇrevedenou na minimalizaˇcn´ı u ´lohu ve tvaru rovnic, tj. © > ª min c x | Ax = b, x ≥ 0

(3.9)

kde A je matice dimenze (m, n) se sloupci Ax1 , . . . , Axn . Pˇredpokládáme, ˇze hodnost matice A je m. Poznamenejme zde, ˇze kdyˇz by matice A mˇela hodnost menˇs´ı neˇzli m, pak jsou uvaˇzované rovnice závislé. M˚ uˇzeme proto nˇekteré z nich vynechat tak, ˇze mnoˇzina ˇreˇsen´ı soustavy se nezmˇen´ı a matice redukované soustavy bude m´ıt plnou ˇrádkovou hodnost.

Simplexov´ y algoritmus Krok 1. Urˇci pˇr´ıpustnou bázi J ⊂ {x1 , x2 , . . . , xn } a oznaˇc AJ = (Axj , xj ∈ J), cJ = (cj , xj ∈ J). Krok 2. Simplexov´ e krit´ erium – test optimality. Je-li

−1 > > c> J AJ A − c ≤ 0

v´ ypoˇcet konˇc´ı. Nenulové sloˇzky optimáln´ıho ˇreˇsen´ı jsou dány vzorcem

(3.10) A−1 J b.

V opaˇcném pˇr´ıpadˇe jdi ke kroku 3. Krok 3. Zmˇ ena b´ aze. Do báze zaˇrad’ promˇennou h ∈ / J, pro kterou je poruˇseno simplexové kritérium (3.10), tj. −1 h c> J AJ a − ch > 0.

(3.11)

Pokud jich je v´ıce m˚ uˇzeˇs vz´ıt kteroukoli z nich. Napˇr´ıklad tu, pro kterou je (3.11) poruˇseno nejv´ıce. Nyn´ı jsou moˇzné dva pˇr´ıpady. h a) Kdyˇz vektor A−1 a alespoˇ n jednu sloˇzku kladnou, pak nalezneme promˇennou r ∈ J tak, J A m´ aby ¯ ½ ¾ ¯ (A−1 (A−1 −1 h h J b)j ¯ J b)r = min j ∈ J, (A (3.12) A ) > 0 . (A−1 A ) > 0 a j r J J ¯ h h (A−1 (A−1 J A )r J A )j

Proved’ jednu iteraci Gaussova eliminaˇcn´ıho algoritmu odpov´ıdaj´ıc´ı zmˇenˇe báze J := J ∪ {h} \ {r} a pro novou bázi se vrat’ ke kroku 2. h b) Kdyˇz vektor A−1 a ˇzádnou sloˇzku kladnou, pak v´ ypoˇcet konˇc´ı zjiˇstˇen´ım, ˇze u ´loha (3.9) J A nem´ nemá optimáln´ı ˇreˇsen´ı a jej´ı u ´ˇcelová funkce neomezenˇe klesá do −∞. √


19

Petr Lachout

Vˇ eta 15: Kdyˇz je u ´loha (3.9) nedegenerovaná, pak simplexov´ y algoritmus vˇzdy skonˇc´ı po koneˇcnˇe kroc´ıch zjiˇstˇen´ım, ˇze u ´loha (3.9) bud’ nemá ˇzádné pˇr´ıpustné ˇreˇsen´ı nebo najde jej´ı optimáln´ı ˇreˇsen´ı nebo jej´ı u ´ˇcelová funkce neomezenˇe klesá na mnoˇzinˇe pˇr´ıpustn´ ych ˇreˇsen´ı. Pokud je u ´loha degenerovaná, pak index r v (3.12) nemus´ı b´ yt urˇcen jednoznaˇcnˇe. Kdyˇz je v´ıce kandidát˚ u je tˇreba mezi nimi vyb´ırat opatrnˇe. Bud’ vyb´ırat náhodnˇe nebo pouˇz´ıt postup vysvˇetlen´ y napˇr´ıklad v [2], odst. 4.5. Jinak by se mohlo stát, ˇze se algoritmus zacykl´ı. Rozhodovac´ı pravidla pro zmˇenu báze zaruˇcuj´ı, ˇze jsou novˇe konstruované báze stále pˇr´ıpustné. Jeli u ´loha (3.9) nedegenerovaná, pak je simplexov´ y algoritmus finitn´ı (konˇc´ı po koneˇcném poˇctu iterac´ı), hodnoty u ´ˇcelové funkce rostou. Je-li u ´loha (3.9) degenerovaná a pouˇz´ıváme-li postup vysvˇetlen´ y napˇr´ıklad v [2], odst. 4.5, pak je simplexov´ y algoritmus opˇet finitn´ı, hodnoty u ´ˇcelové funkce jsou neklesaj´ıc´ı, ale mohou b´ yt po nˇekolik krok˚ u stejné. Simplexov´ y algoritmus má celou ˇradu variant, napˇr. revidovanou simplexovou metodu, kterou vyuˇz´ıvá GAMS. Simplexov´ y algoritmus m˚ uˇzeme realizovat v tabulce, viz tabulka 3.1. c> x1 cL

L

x2

...

xn

(AL )−1 b

(AL )−1 A

−1 c> b L (AL )

−1 c> b − c> L (AL )

Tabulka 3.1: Simplexová tabulka Pro pouˇzit´ı simplexového algoritmu je tˇreba jeˇstˇe vyˇreˇsit posledn´ı problém. Jak nalézt v´ ychoz´ı bazické pˇr´ıpustné ˇreˇsen´ı. Jednou z moˇznost´ı je pouˇz´ıt dvouf´ azov´ y simplexov´ y algoritmus.

Dvouf´ azov´ y simplexov´ y algoritmus 1.f´ aze: Nejdˇr´ıve ˇreˇs´ıme pomocnou u ´lohu (K ) ¯ X ¯ n K min zk ¯ Ax + Qz = b, x ≥ 0, z ≥ 0, x ∈ R , z ∈ R .

(3.13)

k=1

Pomocné promˇenné z a matice Q jsou pˇridány tak, aby vznikla báze V = {v1 , v2 , . . . , vm } ⊂ {x1 , x2 , . . . , xn , z1 , z2 , . . . , zK } s vlastnost´ı, ˇze pro kaˇzdé i ∈ {1, 2, . . . , m} je (A|Q)•,vi = sgn (bi ) ei . ´ Ulohu (3.13) vyˇreˇs´ıme simplexov´ ym algoritmem. Jako poˇcáteˇcn´ı bázi pouˇzijeme bázi V . V´ıme, ˇze u ´loha (3.13) má pˇr´ıpustné ˇreˇsen´ı a hodnota jej´ı u ´ˇcelové funkce je nezáporná pro vˇsechna pˇr´ıpustná ˇreˇsen´ı. Proto podle vˇety 14 má u ´loha (3.13) optimáln´ı ˇreˇsen´ı. Simplexov´ y algoritmus proto nalezne optimáln´ı bázi u ´lohy (3.13). Nyn´ı jsou dvˇe moˇznosti. Bud’ je optimáln´ı hodnota kladná nebo nulová. Kdyˇz je optimáln´ı hodnota kladná, tak to znamená, ˇze u ´loha (3.9) nemá pˇr´ıpustné ˇreˇsen´ı a algoritmus konˇc´ı t´ımto zjiˇstˇen´ım. Kdyˇz je optimáln´ı hodnota nulová, tak to znamená, ˇze u ´loha (3.9) má pˇr´ıpustné ˇreˇsen´ı a algoritmus pokraˇcuje druhou f´ az´ı. 2.f´ aze: Pokud u ´loha (3.13) má nulovou optimáln´ı hodnotu a u ´loha (3.9) je nedegenerovaná, pak simplexov´ y algoritmus v prvn´ı f´ azi nalezl optimáln´ı bázi W , která neobsahuje ˇzádnou pomocnou promˇennou zk . Pokud by totiˇz nˇekterá pomocná promˇenná z˚ ustala v optimáln´ı bázi, pak by mˇela nulovou hodnotu. Promˇenné xj zaˇrazené do optimáln´ı báze by tvoˇrily nenulové sloˇzky pˇr´ıpustného ˇreˇsen´ı u ´lohy (3.9). Toto ˇreˇsen´ı by vˇsak mˇelo ménˇe neˇzli m nenulov´ ych sloˇzek. Bylo by tedy degenerované, ale to nen´ı moˇzné, nebot’ u ´loha (3.9) je nedegenerovaná.

20 Pokud u ´loha (3.13) má nulovou optimáln´ı hodnotu a u ´loha (3.9) je degenerovaná, pak simplexov´ y algoritmus v prvn´ı f´ azi nalezl optimáln´ı bázi, která m˚ uˇze obsahovat nˇekterou z pomocn´ ych ych je vˇsak nutnˇe nulová. Pak d´ıky pˇredpokladu o plné promˇenn´ ych zk . Hodnota tˇechto promˇenn´ sloupcové hodnosti matice A lze pro kaˇzdou takovou promˇennou zk vˇzdy naj´ıt promˇennou xj , která má v ˇrádku pˇr´ısluˇsej´ıc´ım zk nenulové ˇc´ıslo. Tuto promˇennou zaˇrad´ıme do báze m´ısto zk a pˇrepoˇcteme tabulku. Opakován´ım tohoto postupu vyˇrad´ıme z báze vˇsechny pomocné promˇenné a z´ıskáme optimáln´ı bázi W u ´lohy (3.13), která jiˇz ˇzádnou pomocnou promˇennou neobsahuje. Nyn´ı simplexov´ ym algoritmem vyˇreˇs´ıme u ´lohu (3.9). Jako poˇcáteˇcn´ı bázi pouˇzijeme bázi W . Uvˇedomme si, ˇze prakticky zaˇc´ınáme s tabulkou, kterou jsme z´ıskali v prvn´ı fázi algoritmu. Pouze jsme vyˇskrtli sloupce pˇr´ısluˇsej´ıc´ı pomocn´ ym promˇenn´ ym a koeficienty v u ´ˇcelové funkci pomocné u ´lohy jsme nahradili koeficienty v u ´ˇcelové funkci u ´lohy (3.9). √ Pro ilustraci si spoˇctˇeme pˇr´ıklad. ˇ sme dvoufázov´ Pˇr´ıklad 16: Reˇ ym simplexov´ ym algoritmem u ´lohu minimalizovat −x1 za podm´ınek

−

3x3

+ x4

x1

+

2x2

+ 3x3

=

15

2x1

+

x2

+ 5x3

=

20

x1

+

2x2

+

=

10

x3

+ x4

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.

(3.14)

V prvn´ı fázi ˇreˇs´ıme pomocnou u ´lohu minimalizovat

z1

+

z2

za podm´ınek

x1

+ 2x2

+

3x3

2x1

+

x2

+

5x3

x1

+ 2x2

+

x3

+ z1

= 15 +

+

z2

= 20

x4

= 10

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, z1 ≥ 0, z2 ≥ 0.

(3.15) Do báze zaˇrad´ıme promˇenné z1 , z2 , x4 . Sestavme tabulku a poˇc´ıtejme. Zvolen´ y prvek v rozhodovac´ım ˇrádku je oznaˇcen zelen´ ym obdéln´ıkem. Zvolen´ y kl´ıˇcov´ y prvek ˇcerven´ ym obdéln´ıkem.

0

0

0

0

1

1

x1

x2

x3

x4

z1

z2

1

z1

15

1

2

3

0

1

0

1

z2

20

2

1

5

0

0

1

0

x4

10

1

2

1

1

0

0

35

3

3

8

0

0

0

0

0

0

0

1

1

x1

x2

x3

x4

z1

z2

1

z1

3

− 15

7 5

0

0

1

− 53

0

x3

4

0

0

x4

6

1 5 9 5

1

0

2 5 3 5

0

1

0

1 5 − 51

3

− 15

7 5

0

0

0

− 58


21

Petr Lachout

0

x2

0

x3

0

x4

0

0

0

0

1

1

x1

x2

x3

x4

z1

z2 − 73

−1

15 7 25 7 15 7

− 17 3 7 6 7

1

0

0

0

1

0

0

0

1

5 7 − 17 − 97

0

0

0

0

0

−1

2 7 4 7

Zjistili jsme, ˇze optimáln´ı hodnota pomocné u ´lohy je nulová. Prvn´ı fáze dvoufázového simplexového algoritmu skonˇcila nalezen´ım pˇr´ıpustného ˇreˇsen´ı p˚ uvodn´ı u ´lohy. V nalezené optimáln´ı bázi pomocné u ´lohy se nevyskytuj´ı ˇzádné pomocné promˇenné z. Máme tedy pˇr´ıpustnou bázi p˚ uvodn´ı u ´lohy a m˚ uˇzeme pokraˇcovat druhou fáz´ı algoritmu.

−1

0

−3

1

x1

x2

x3

x4

− 17 3 7

1

0

0

0

x2

−3

x3

15 7 25 7

0

1

0

x4

15 7

6 7

0

0

1

− 60 7

4 7

0

0

0

1

0

x2

−3

x3

−1

x1

−1

0

−3

1

x1

x2

x3

x4

5 2 5 2 5 2

0

1

0

0

0

1

1

0

0

−10

0

0

0

1 6 − 21 7 6 − 32

Optimáln´ım ˇreˇsen´ım zadané u ´lohy je vektor 127.

¡5

5 5 2 2 2

¢>

0

. V´ ypoˇcet je uveden ve skriptech [2], str.1264

3.5

Dualita a jej´ı interpretace

Dualita se t´ yká dvojice u ´loh lineárn´ıho programován´ı, která je dána spoleˇcn´ ymi vstupn´ımi daty, tj. matic´ı A dimenze (m, n), m-rozmˇern´ ym vektorem b a n-rozmˇern´ ym vektorem c. Kromˇe dan´ ych koeficient˚ u je kaˇzdá u ´loha LP urˇcena také druhem optimalizace (minimalizace, maximalizace), tvarem omezen´ı (rovnice, nerovnosti) a pˇr´ıtomnost´ı ˇci absenc´ı podm´ınek nezápornosti. Tak vznikaj´ı r˚ uzné dvojice duáln´ıch u ´loh, napˇr. duáln´ı k minimalizaˇcn´ı u ´loze v rovnicovém tvaru, kterou jsme se aˇz dosud zab´ yvali,

je u ´loha

© ª min c> x | Ax = b, x ≥ 0

(3.16)

¯ © ª max b> y ¯ A> y ≤ c

(3.17)

Obecná dvojice duáln´ıch u ´loh vypadá následovnˇe. Definice 10: Necht’ je dána matice A dimenze (m, n), m-rozmˇern´ ym vektorem b, n-rozmˇern´ ym vektorem c a disjunktn´ı rozklady index˚ u I≥ ∪ I≤ ∪ I∈ = {1, 2, . . . , n}, J≥ ∪ J≤ ∪ J= = {1, 2, . . . , m}. Pak dvojice

22 u ´loh lineárn´ıho programován´ı minimalizovat za podm´ınek

Pn

i=1 ci xi

Pn i=1

Aj,i xi

≥

bj

pro kaˇzdé j ∈ J≥ ,

i=1

Aj,i xi

≤

bj

pro kaˇzdé j ∈ J≤ ,

i=1

Aj,i xi

=

bj

pro kaˇzdé j ∈ J= ,

xi

≥

0

pro kaˇzdé i ∈ I≥ ,

xi

≤

0


xi

∈

R

pro kaˇzdé i ∈ I∈ ,

Pn

Pn

maximalizovat za podm´ınek

(3.18)

Pm

j=1 bj yj

Pm j=1

Aj,i yj

≤

ci

pro kaˇzdé j ∈ I≥ ,

j=1

Aj,i yj

≥

ci

pro kaˇzdé j ∈ I≤ ,

j=1

Aj,i yj

=

ci

pro kaˇzdé j ∈ I∈ ,

yj

≥

0

pro kaˇzdé i ∈ J≥ ,

yj

≤

0

pro kaˇzdé i ∈ J≤ ,

yj

∈

R

pro kaˇzdé i ∈ J= ,

Pm Pm

(3.19)

se naz´ yvá dvojice du´ aln´ıch u ´ loh LP. Mnoˇzinu pˇr´ıpustn´ ych ˇreˇsen´ı u ´lohy (3.18) oznaˇc´ıme jako M, tj. mnoˇzinu vˇsech x ∈ Rn , které splˇ nuj´ı podm´ınky Pn pro kaˇzdé j ∈ J≥ , i=1 Aj,i xi ≥ bj Pn pro kaˇzdé j ∈ J≤ , i=1 Aj,i xi ≤ bj Pn pro kaˇzdé j ∈ J= , i=1 Aj,i xi = bj (3.20) xi ≥ 0 pro kaˇzdé i ∈ I≥ , xi

≤

0


xi

∈

R

pro kaˇzdé i ∈ I∈ .

Mnoˇzinu pˇr´ıpustn´ ych ˇreˇsen´ı u ´lohy (3.19) podm´ınky Pm j=1 Aj,i yj Pm j=1 Aj,i yj Pm j=1 Aj,i yj

oznaˇc´ıme jako N , tj. mnoˇzinu vˇsech y ∈ Rm , které splˇ nuj´ı ≤

ci

pro kaˇzdé j ∈ I≥ ,

≥

ci

pro kaˇzdé j ∈ I≤ ,

=

ci

pro kaˇzdé j ∈ I∈ ,

yj

≥

0

pro kaˇzdé i ∈ J≥ ,

yj

≤

0

pro kaˇzdé i ∈ J≤ ,

yj

∈

R

pro kaˇzdé i ∈ J= .

(3.21)

Nˇekdy také hovoˇr´ıme o u ´loze prim´ arn´ı a k n´ı u ´loze du´ aln´ı. Jako primárn´ı oznaˇcujeme tu u ´lohu z u ´loh (3.18), (3.19), která vznikla na základˇe ˇreˇseného problému. Zbylou u ´lohu, pak naz´ yváme u ´lohou k n´ı duáln´ı. Sestaven´ı pˇr´ısluˇsné duáln´ı u ´lohy k zadané u ´loze lze dˇelat zcela mechanicky. Vhodnou pom˚ uckou k tomu m˚ uˇze b´ yt sestaven´ı tabulky“, jak je ukázáno v následuj´ıc´ım pˇr´ıkladˇe. ”


23

Petr Lachout

Pˇr´ıklad 17: K dané u ´loze lineárn´ıho programován´ı m˚ uˇzeme pˇriˇradit pˇr´ısluˇsnou u ´lohu do duáln´ı dvojice pomoc´ı tabulky. Uvaˇzujme u ´lohu minimalizovat 2x1

−

x2

+

3x3 ,

za podm´ınek

3x1

+ 6x2

−

x3

≥ 4,

2x1

− 3x2

+

2x3

≤ 3,

x1 − 2x2 + 4x3 x1 ≥ 0, x2 ≥ 0, x3 ∈ R.

= 2,

(3.22)

Sestav´ıme tabulku 3.2 x1

x2

x3

≥0

≥0

∈R

3

6

−1

≥

4

2

−3

2

≤

3

1

−2

4

=

2 max

2

−1

3

min

Tabulka 3.2: Dualita A Do ˇrádk˚ u omezen´ı pˇridáme duáln´ı promˇenné a pomoc´ı pravidla, ˇze pˇri min“ pˇrevád´ıme ≥ ↔ ≥, ≤ ↔ ≤, ” = ↔ ∈ R, a pˇri max“ pˇrevád´ıme ≤ ↔ ≥, ≥ ↔ ≤, ∈ R ↔ =, tabulku 3.2 dopln´ıme na tabulku 3.3 ” x1

x2

x3

≥0

≥0

∈R

y1

≥0

3

6

−1

≥

4

y2

≤0

2

−3

2

≤

3

y3

∈R

1

−2

4

=

2

≤

≤

=

2

−1

3

max min

Tabulka 3.3: Dualita B ˇ Cteme-li tabulku 3.3 po sloupc´ıch dostáváme u ´lohu maximalizovat

4y1

+

3y2

+ 2y3 ,

za podm´ınek

3y1

+

2y2

+

y3

≤

2,

6y1

−

3y2

−

2y3

≤

−1,

−y1 + 2y2 + 4y3 y1 ≥ 0, y2 ≤ 0, y3 ∈ R,

=

3,

(3.23)

která je duáln´ı u ´lohou k u ´loze (3.22). 4 V´ıme, ˇze lze u ´lohy LP pˇrevádˇet na zvolen´ y tvar. Staˇc´ı se proto zab´ yvat pouze jednou dvojic´ı duáln´ıch u ´loh. Dokázaná tvrzen´ı jsou potom platná i pro libovolnou jinou dvojici duáln´ıch u ´loh. Vhodnou dvojic´ı pro tento u ´ˇcel je dvojice symetrick´ ych duáln´ıch u ´loh. Definice 11: Necht’ A je daná matice dimenze (m, n), b dan´ y m-rozmˇern´ y vektor a c dan´ y n-rozmˇern´ y vektor. Pak následuj´ıc´ı dvˇe u ´lohy nazveme dvojice symetrick´ ych du´ aln´ıch u ´ loh LP: © ª min c> x | Ax ≥ b, x ≥ 0 , (3.24) © > ¯ > ª max b y ¯ A y ≤ c, y ≥ 0 . (3.25)

24 Vˇ eta 16 (Slab´ a vˇ eta o dualitˇ e): Pro dvojici duáln´ıch u ´loh (3.18), (3.19) plat´ı ∀x ∈ M ∀y ∈ N : c> x ≥ b> y.

(3.26)

Rovnost ve vztahu (3.26) nastane, právˇe kdyˇz plat´ı podm´ınky komplementarity: • Pro kaˇzdé i ∈ {1, . . . , m} plat´ı bud’ yi = 0

nebo

n X

ai,j xj = bi .

(3.27)

ai,j yi = cj .

(3.28)

j=1

• Pro kaˇzdé j ∈ {1, . . . , n} plat´ı bud’ xj = 0

nebo

m X i=1

D˚ ukaz: Tvrzen´ı staˇc´ı ukázat pro dvojici symetrick´ ych duáln´ıch u ´loh. D˚ ukaz je pak snadn´ y, nebot’ pro x pˇr´ıpustné ˇreˇsen´ı (3.24) a y pˇr´ıpustné ˇreˇsen´ı (3.25), tj. x ∈ M, y ∈ N , plat´ı ¡ ¢> c> x ≥ A> y x = y> Ax ≥ y> b = b> y. Tvrzen´ı vˇety i komplementarita plynou okamˇzitˇe z této nerovnosti. Q.E.D. ´ Vˇ eta 17 (Siln´ a vˇ eta o dualitˇ e): Uloha (3.18) má optimáln´ı ˇreˇsen´ı tehdy a jen tehdy, má-li u ´loha (3.19) optimáln´ı ˇreˇsen´ı. V takovém pˇr´ıpadˇe nav´ıc plat´ı, ˇze min c> x = max b> y.

x∈M

(3.29)

y∈N

D˚ ukaz: Tvrzen´ı staˇc´ı ukázat pro dvojici symetrick´ ych duáln´ıch u ´loh. Pˇredpokládejme, ˇze má u ´loha (3.24) optimáln´ı ˇreˇsen´ı a ˇze jsme jej naˇsli pomoc´ı simplexové metody. To znamená: 1. Pouˇzili jsme doplˇ nkové promˇenné z1 , z2 , . . . , zm , ˇc´ımˇz jsme dostali soustavu m rovnic o n + m promˇenn´ ych Ax − Iz = b, x ≥ 0, z ≥ 0 a u ´ˇcelová funkce se nezmˇenila (tj. doplˇ nkové promˇenné v n´ı maj´ı koeficienty 0). ¡ ¢ ˜ = 0c L . 2. Naˇsli jsme optimáln´ı bázi L ⊂ {x1 , x2 , . . . , xn , z1 , z2 , . . . , zm }. Oznaˇcme B = [A, −I]L a c B´ aze L je optimáln´ı, splˇ nuje proto podm´ınky: (a) Pˇr´ıpustnost B−1 b ≥ 0. (b) Optimalita (rozepsáno pro obˇe ˇcásti rozˇs´ıˇrené soustavy zvláˇst’): ˜> B−1 A − c> c −˜ c> B−1 I − 0>

≤ 0> ≤ 0> .

(3.30) (3.31)

¢> ¡ ˜ je pˇr´ıpustné ˇreˇsen´ı u ´lohy (3.25). Podm´ınky optimality (3.30), (3.31) vˇsak znamenaj´ı, ˇze y∗ := B−1 c Spoˇc´ıtejme odpov´ıdaj´ıc´ı hodnotu u ´ˇcelové funkce duáln´ı u ´lohy: © ª ¡ ¢> ˜=c ˜> B−1 b = max c> x | Ax − Iz = b, x ≥ 0, z ≥ 0 = max c> x. b> y∗ = b> B−1 c x∈M

Podle slabé vˇety o dualitˇe, vˇeta 16, to znamená, ˇze y∗ je optimáln´ı ˇreˇsen´ı u ´lohy (3.25) a plat´ı rovnost (3.29). Q.E.D. Uvedené vztahy mezi u ´lohami, které tvoˇr´ı dvojici duáln´ıch u ´loh LP, lze zapsat sumárnˇe v jedné vˇetˇe.


25

Petr Lachout

Vˇ eta 18 (Shrnut´ı): Pro danou dvojici duáln´ıch u ´loh LP (3.18), (3.19) nastává právˇe jedna ze ˇctyˇr moˇznost´ı: ˇadná z tˇechto u (i) Z´ ´loh nemá pˇr´ıpustné ˇreˇsen´ı, tj. M = ∅,

N = ∅.

(ii) M = ∅, N 6= ∅, ale u ´loha (3.19) nemá optimáln´ı ˇreˇsen´ı. (iii) M 6= ∅, N = ∅, ale u ´loha (3.18) nemá optimáln´ı ˇreˇsen´ı. (iv) Obˇe u ´lohy maj´ı optimáln´ı ˇreˇsen´ı a plat´ı max c> x = min b> y.

x∈M

y∈N

Nav´ıc kaˇzdá dvojice optimáln´ıch ˇreˇsen´ı u ´lohy (3.18) a (3.19) splˇ nuje podm´ınky komplementarity (3.27), (3.28).

3.6

Farkasova vˇ eta

Ze silné vˇety o dualitˇe lze jednoduˇse dokázat i klasickou Farkasovu vˇetu, která ˇreˇs´ı teoreticky otázku existence pˇr´ıpustného ˇreˇsen´ı; neboli existenci nezáporného ˇreˇsen´ı soustavy rovnic. Vˇ eta 19 (Farkasova vˇ eta): Soustava Ax = b má nezáporné ˇreˇsen´ı tehdy a jen tehdy, kdyˇz pro kaˇzdé u, které splˇ nuje A> u ≥ 0, plat´ı b> u ≥ 0. D˚ ukaz: Farkasovu vˇetu lze chápat jako pˇrepis dvojice duáln´ıch u ´loh ¯ © ª © ª max 0> x | Ax = b, x ≥ 0 ←→ min b> y ¯ A> y ≥ 0 . Ukazuje to tento ˇretˇezec ekvivalenc´ı Soustava Ax = b má nezáporné ˇreˇsen´ı m ©

u ´loha max 0> x | Ax = b, x ≥ 0

ª

má optimáln´ı ˇreˇsen´ı

m ¯ ª u ´loha min b> y ¯ A> y ≥ 0 má optimáln´ı ˇreˇsen´ı ©

m £¡ ¢ ¤ u : A> u ≥ 0 =⇒ b> u ≥ 0 Farkasova vˇeta je s touto dvojic´ı duáln´ıch u ´loh ekvivalentn´ı nebot’ druhá u ´loha má vˇzdy pˇr´ıpustné ˇreˇs´ı, tj. 0 ∈ N . Q.E.D. Zaj´ımá-li nás existence ˇreˇsen´ı soustavy rovnic a nerovnic, která má pˇredepsané sloˇzky kladné a jiné pˇredepsané sloˇzky záporné, pak máme dvˇe moˇznosti, jak odvodit pˇr´ısluˇsnou Farkasovu vˇetu. Prvn´ı moˇznost´ı je pˇrevést povolen´ ymi u ´pravami u ´lohu na existenci nezáporného ˇreˇsen´ı soustavy rovnic. Podm´ınky z´ıskáme z vˇety 19 a jejich diskuz´ı nalezneme podm´ınky pro existenci ˇreˇsen´ı p˚ uvodn´ı soustavy. Druhou moˇznost´ı je postupovat tak, jak je naznaˇceno v d˚ ukaze vˇety 19. Sestavit vhodnou dvojici duáln´ıch u ´loh a Farkasovu vˇetu odvodit z principu duality pro tuto dvojici.

3.7

Ekonomick´ a interpretace duality

Dvojici duáln´ıch u ´loh lze sestavit na základˇe ekonomické u ´vahy. Ukaˇzme si to na pˇr´ıkladˇe podniku, kter´ y vyráb´ı m-druh˚ u v´ yrobk˚ u a pouˇz´ıvá k tomu n v´ yrobn´ıch postup˚ u. V duáln´ım vztahu jsou zde dvˇe základn´ı ekonomické u ´lohy.

26 ´ Uloha I: Minimalizovat v´ yrobn´ı náklady pˇri splnˇen´ı podm´ınek na minimáln´ı mnoˇzstv´ı vyroben´ ych v´ yrobk˚ u. ´ Uloha II: Stanovit v´ yrobn´ı ceny vyrábˇen´ ych v´ yrobk˚ u pˇri splnˇen´ı podm´ınek na minimáln´ı mnoˇzstv´ı vyroben´ ych v´ yrobk˚ u. Druhou u ´lohu m˚ uˇzeme pˇreformulovat následovnˇe. ´ Uloha II’: Maximalizovat celkovou cenu minimáln´ı v´ yroby za podm´ınky, ˇze ohodnocen´ı ˇzádného z v´ yrobn´ıch postup˚ u na základˇe jednotkov´ ych cen v´ yrobk˚ u nepˇrev´ yˇs´ı jeho jednotkovou cenu. ´ Uloha I má matematick´ y zápis minimalizovat za podm´ınek

Pn

j=1 cj xj ,

Pn

j=1

Ai,j xj ≥ bi

xj ≥ 0

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

´ Uloha II’, a tedy i u ´loha II, má matematick´ y zápis Pm maximalizovat i=1 bi yi , Pm za podm´ınek i=1 Ai,j yi ≤ cj yi ≥ 0

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

Vid´ıme, ˇze se jedná o dvojici duáln´ıch u ´loh LP. V ekonomické literatuˇre b´ yvá optimáln´ı ˇreˇsen´ı u ´ lohy II naz´ yváno st´ınov´ e ceny nebo du´ aln´ı ceny.

3.8

Pozn´ amky

1. Dualita se vztahuje k matematickému zápisu u ´loh lineárn´ıho programován´ı. 2. Vyˇreˇs´ıme-li primárn´ı u ´lohu LP simplexovou metodou, z´ıskáme zároveˇ n ˇreˇsen´ı duáln´ı u ´lohy. Pˇreˇcteme ho v kriteriáln´ım ˇrádku ve sloupc´ıch, které odpov´ıdaly v´ ychoz´ı jednotkov´ e b´ azi. 3. Pro optimáln´ı ˇreˇsen´ı dvojice duáln´ıch u ´loh plat´ı komplementarita. To má zaj´ımavou ekonomickou interpretaci; hovoˇr´ıme o duáln´ıch, st´ınov´ ych cenách. 4. Obˇe duáln´ı u ´lohy maj´ı optimáln´ı ˇreˇsen´ı, právˇe kdyˇz maj´ı neprázdné mnoˇziny pˇr´ıpustn´ ych ˇreˇsen´ı. 5. Zp˚ usob vytváˇren´ı duáln´ıch u ´loh um´ıme znázornit tabulkou. Pˇripomeˇ nme si tento postup jeˇstˇe na pˇr´ıkladu dvojice symetrick´ ych duáln´ıch u ´loh: promˇenné y1 ≥ 0 ... ym ≥ 0 nerovnosti pravé strany/koef.

x1 ≥ 0 a11 ... am1 ≤ c1

... ... ... ... ...

xn ≥ 0 nerovnosti pravé str./koef. a1n ≥ b1 ... ... ... amn ≥ bm ≤ max cn min

Primárn´ı u ´lohu ˇcteme po ˇrádc´ıch a duáln´ı u ´lohu po sloupc´ıch. Podobnˇe pro dvojici duáln´ıch u ´loh (3.16), (3.17) má tabulka tvar promˇenné y1 ∈ R ... ym ∈ R nerovnosti pravé strany/koef.

x1 ≥ 0 a11 ... am1 ≤ c1

... ... ... ... ...

xn ≥ 0 rovnosti pravé str./koef. a1n = b1 ... ... ... amn = bm ≤ max cn min

Kapitola 4

Symetrick´ au ´ loha NLP 4.1

Podm´ınky optimality pro symetrick´ eu ´ lohy NLP

V této kapitole se budeme zab´ yvat symetrickou u ´ lohou neline´ arn´ıho programov´ an´ı minimalizovat f (x), za podm´ınek

(4.1)

gk (x) ≤ 0 ∀ k = 1, . . . , m, xj ≥ 0

∀ j = 1, . . . , n.

´ Uloha je speciáln´ım pˇr´ıpadem obecné u ´lohy NLP. ´ Uloze (4.1) pˇriˇrad´ıme Lagrangeovu funkci L (x; y) := f (x) +

m X

yk gk (x).

(4.2)

k=1

ˇ Definice 12: Rekneme, ˇze pro x∗ ∈ Rn , y∗ ∈ Rm jsou splnˇeny glob´ aln´ı podm´ınky optimality, zkrácenˇe (GPO), pro u ´lohu (4.1), jestliˇze dvojice (x∗ , y∗ ) je sedlov´ y bod Lagrangeovy funkce (4.2) pro x ≥ 0, y ≥ 0. To znamená, ˇze x∗ ≥ 0, y∗ ≥ 0 n

m

∗

∗

∗

∗

∀ x ∈ R ∀ y ∈ R , x ≥ 0, y ≥ 0 plat´ı L (x; y ) ≥ L (x ; y ) ≥ L (x ; y) .

(4.3) (4.4)

Vˇ eta 20: Necht’ jsou pro x∗ ∈ Rn , y∗ ∈ Rm splnˇeny globáln´ı podm´ınky optimality pro u ´lohu NLP (4.1). Pak je x∗ optimáln´ı ˇreˇsen´ı zm´ınˇené u ´lohy a je splnˇena podm´ınka komplementarity pro kaˇzdé k = 1, . . . , m

je bud’

yk∗ = 0

nebo

gk (x∗ ) = 0.

(4.5)

D˚ ukaz: Podle pˇredpokladu je x∗ ≥ 0. Dosazen´ım tvaru Lagrangeovy funkce (4.2) do (4.4) dostáváme f (x) +

m X

yk∗ gk (x) ≥ f (x∗ ) +

k=1

m X

yk∗ gk (x∗ ) ≥ f (x∗ ) +

k=1

m X

yk gk (x∗ ).

(4.6)

k=1

Nerovnosti (4.6) podle pˇredpokladu plat´ı pro nˇejaké y∗ ≥ 0 a pro vˇsechna x ≥ 0, y ≥ 0. Pouˇzijeme nejprve pravou vˇetev (4.6), tj. nerovnost m X

yk∗ gk (x∗ ) ≥

k=1

m X

yk gk (x∗ ) ∀y ≥ 0.

(4.7)

k=1

Uvˇedom´ıme si, ˇze gk (x∗ ) jsou pevné koeficienty a ˇze y∗ ≥ 0 je z hlediska uvaˇzované nerovnosti také pevn´ y vektor. Odtud pˇr´ımo vypl´ yvá, ˇze (4.7) m˚ uˇze platit jen kdyˇz gk (x∗ ) ≤ 0 ∀k a m X

yk∗ gk (x∗ ) = 0.

k=1

27

(4.8)

28 Tato podm´ınka je ekvivalentn´ı s podm´ınkou komplementarity (4.5). To znamená, ˇze x∗ je pˇr´ıpustné ˇreˇsen´ı u ´lohy (4.1) a ˇze se levá vˇetev nerovnost´ı (4.6) redukuje na f (x) +

m X

yk∗ gk (x) ≥ f (x∗ )

∀x ≥ 0

(4.9)

k=1

Omezme se jen na pˇr´ıpustná x. Pro nˇe je gk (x) ≤ 0 Tedy x∗ je optimáln´ı ˇreˇsen´ı u ´lohy (4.1).

∀k a z nerovnosti (4.9) plyne f (x) ≥ f (x∗ ). Q.E.D.

4.2

Podm´ınky regularity

Vˇeta 20 plat´ı bez jak´ ychkoli pˇredpoklad˚ u na funkce f, gk . Avˇsak pro ovˇeˇrován´ı optimality ˇreˇsen´ı nebo pro nalezen´ı optimáln´ıho ˇreˇsen´ı je nepraktická. Jako vedlejˇs´ı v´ ysledek jsme dostali podm´ınku komplementarity (4.5). (Porovnejte s podm´ınkami komplementarity v LP (3.27), (3.28).) Vˇeta 20 dává postaˇcuj´ıc´ı podm´ınku pro bod globáln´ıho minima funkce f na mnoˇzinˇe popsané nerovnostmi (4.1). Otázkou je, kdy bude globáln´ı podm´ınka (4.6) nutná. Snadno najdeme pˇr´ıklad, kdy k optimáln´ımu ˇreˇsen´ı x∗ u ´lohy (4.1) neexistuje vektor Lagrangeov´ ych multiplikátor˚ u y∗ tak, aby platilo (4.6). ¯ © ª ˇ sme u Pˇr´ıklad 18: Reˇ ´lohu min −x ¯ x2 ≤ 0, x ≥ 0, x ∈ R , tj. f (x) = −x, g(x) = x2 pro kaˇzdé x ≥ 0. Existuje jediné pˇr´ıpustné a tedy i optimáln´ı ˇreˇsen´ı u ´lohy. Je to x∗ = 0. 2 Lagrangeova funkce má tvar L (x; y) = −x + yx . 1. V bodˇe (0, 0) nemá sedlov´ y bod nebot’ funkce x 7→ L (x; 0) = −x nemá na x ≥ 0 minimum v x∗ = 0. 2. Pro y > 0, v bodˇe (0, y) také nen´ı sedlov´ y bod Lagrangeovy funkce, nebot’ x 7→ L (x; y) = −x + yx2 1 má na x ≥ 0 minimum v x ¯ = 2y a nikoli v x∗ = 0. K bodu x∗ = 0 tedy neexistuje ˇzádné y ∗ ∈ R tak, aby dvojice (x∗ , y ∗ ) splˇ novala GPO. 4 Je tedy zapotˇreb´ı dalˇs´ıch pˇredpoklad˚ u tzv. podm´ınek regularity, které vylouˇc´ı podobné degenerované pˇr´ıpady. Z pˇr´ıkladu vid´ıme, ˇze samotn´ y pˇredpoklad konvexnosti funkc´ı f, gk ∀k nestaˇc´ı. Definice 13: Pro u ´lohu (4.1) zavád´ıme mnoˇ zina index˚ u aktivn´ıch omezen´ı v bodˇe x B (x) = {k = 1, . . . , m | gk (x) = 0 } . Uvedeme si dvˇe podm´ınky, které spolu s konvexnost´ı funkc´ı f, gk splnˇen´ım (4.4) a existenc´ı optimáln´ıho ˇreˇsen´ı (4.1). Jsou to

(4.10) ∀k zaruˇcuj´ı ekvivalenci mezi

(i) Podm´ınka line´ arn´ı nez´ avislosti je splnˇena pro pˇr´ıpustné ˇreˇsen´ı x(0) u ´lohy (4.1), jsou-li v bodˇe (0) x lineárnˇe nezávislé gradienty aktivn´ıch omezen´ı, tj. matice ´´ ´ ³ ³ ³ ∇x gk x(0) , k ∈ B x(0) má plnou sloupcovou hodnost. ˜ ≥ 0, pro které je gk (˜ (ii) Slaterova podm´ınka plat´ı pro u ´lohu (4.1), jestliˇze existuje x x) < 0

∀k.

Plat´ı následuj´ıc´ı vˇety. Vˇ eta 21: Necht’ f, gk ∀k jsou konvexn´ı funkce a v bodˇe x∗ ∈ Rn je splnˇena podm´ınka lineárn´ı nezávislosti. Pak x∗ je optimáln´ı ˇreˇsen´ı u ´lohy (4.1) tehdy a jen tehdy, kdyˇz existuje y∗ ∈ Rm tak, ˇze dvojice (x∗ , y∗ ) splˇ nuje GPO. Vˇ eta 22: Necht’ f, gk ∀k jsou konvexn´ı funkce a je splnˇena Slaterova podm´ınka. Pak x∗ ∈ Rn je optimáln´ı ˇreˇsen´ı u ´lohy (4.1) tehdy a jen tehdy, kdyˇz existuje y∗ ∈ Rm tak, ˇze dvojice (x∗ , y∗ ) splˇ nuje GPO.


29

Petr Lachout

Vˇ eta 23: Necht’ f jsou konvexn´ı funkce a gk ∀k jsou lineárn´ı funkce. Pak x∗ ∈ Rn je optimáln´ı ˇreˇsen´ı u ´lohy (4.1) tehdy a jen tehdy, kdyˇz existuje y∗ ∈ Rm tak, ˇze dvojice (x∗ , y∗ ) splˇ nuje GPO. D˚ ukazy tˇechto tvrzen´ı lze nalézt napˇr´ıklad v [3] nebo [4]. Povˇsimnˇete si, ˇze podm´ınka (i) je obdobou podm´ınky pouˇz´ıvané ve vˇetˇe o vázaném extrémech z matematické anal´ yzy. Odvod´ıme dále nutné a postaˇcuj´ıc´ı podm´ınky k tomu, aby dvojice x∗ , y∗ byla sedlov´ ym bodem funkce L (x; y) v nezáporném oboru. K tomu c´ıli budeme pˇredpokládat diferencovatelnost a konvexnost funkc´ı f, gk ∀k. Vˇ eta 24: Necht’ f, gk

∀k jsou diferencovatelné. Pak podm´ınky ∇x L (x∗ ; y∗ ) ≥ 0, ∗

∗

∇y L (x ; y ) ≤ 0,

x∗ > ∇x L (x∗ ; y∗ ) = 0, y

∗>

∗

∗

∇y L (x ; y ) = 0,

x∗ ≥ 0,

(4.11)

∗

y ≥0

(4.12)

jsou nutné k tomu, aby dvojice x∗ , y∗ byla sedlov´ ym bodem L (x; y) v nezáporném oboru. Jsou-li nav´ıc funkce f, gk ∀k konvexn´ı, jsou podm´ınky (4.11), (4.12) nutné a postaˇcuj´ıc´ı. D˚ ukaz: 1. Podm´ınky (4.11) jsou nutné k tomu, aby funkce L (•; y∗ ) nab´ yvala svého minima na mnoˇzinˇe Rn+ n ∗ v bodˇe x . Pro vnitˇrn´ı body nezáporného kvadrantu R+ se redukuj´ı na známou nutnou podm´ınku pro voln´ y extrém, pro hraniˇcn´ı body (tj. v pˇr´ıpadˇe, ˇze je nˇekterá sloˇzka x∗ nulová). Jejich poruˇsen´ı by umoˇznilo konstrukci smˇeru dovnitˇr mnoˇziny Rn+ , ve kterém by L (•; y∗ ) z bodu x∗ rostla. Podobnˇe jsou podm´ınky (4.12) nutné k tomu, aby funkce L (x∗ ; •) nab´ yvala svého maxima na ∗ mnoˇzinˇe Rm v bodˇ e y . + 2. S pouˇzit´ım (2.11) ukáˇzeme, ˇze pro konvexn´ı funkce jsou tyto podm´ınky postaˇcuj´ıc´ı. Pˇredevˇs´ım je pro y∗ ≥ 0 funkce L (•; y∗ ) konvexn´ı na Rn . Podle (2.11) a (4.11) upravujeme postupnˇe L (x; y∗ ) ≥ ≥

L (x∗ ; y∗ ) + (x − x∗ )> ∇x L (x∗ ; y∗ ) L (x∗ ; y∗ ) + x> ∇x L (x∗ ; y∗ ) ≥ L (x∗ ; y∗ )

∀x ≥ 0

Jako funkce y je L (x∗ ; •) lineárn´ı, tedy L (x∗ ; y)

= L (x∗ ; y∗ ) + (y − y∗ )> ∇y L (x∗ ; y∗ ) = L (x∗ ; y∗ ) + y> ∇y L (x∗ ; y∗ ) ≤ L (x∗ ; y∗ )

∀y ≥ 0

podle (4.12). Q.E.D. Podm´ınky (4.11), (4.12) se naz´ yvaj´ı lok´ aln´ı podm´ınky optimality, zkrácenˇe LPO, pro u ´lohu (4.1). Poznamenejme, ˇze nerovnost ∇y L (x∗ ; y∗ ) ≤ 0 v (4.12) je shodná s omezen´ımi gk (x∗ ) ≤ 0 ∀k. Pro symetrickou u ´lohu NLP pouˇz´ıváme Lagrangeovu funkci ve tvaru (4.2), GPO vyjádˇrené jako (4.4) a LPO zapsané v podm´ınkách (4.11), (4.12). Lagrangeovu funkci, GPO a LPO lze vyuˇz´ıt i pro pozmˇenˇen´ y tvar u ´lohy NLP. Avˇsak, Lagrangeova funkce a následnˇe i podm´ınky budou m´ıt pozmˇenˇen´ y tvar. Budou podstatnˇe záviset na tvaru u ´lohy NLP. Uved’me si v následuj´ıc´ı tabulce nˇekteré z pouˇz´ıvan´ ych moˇznost´ı: omezen´ı gk (x) ≤ 0 ∀k x ≥ 0 gk (x) = 0 ∀k, x ≥ 0

4.3

Lagrangeova P funkce f (x) + k yk gk (x) f (x) P f (x) + k yk gk (x)

lokáln´ı podm´ınky optimality ∇x L (x∗ ; y∗ ) = 0 a (4.12) ∇x f (x∗ ) ≥ 0, x∗ ≥ 0, x∗ > ∇x f (x∗ ) = 0 (4.11) a gk (x∗ ) = 0 ∀k

Citlivost u ´ lohy NLP

Podobnˇe jako optimáln´ı hodnoty duáln´ıch promˇenn´ ych souvis´ı i optimáln´ı hodnoty Lagrangeov´ ych multiplikátor˚ u s citlivost´ı optimáln´ı hodnoty u ´ˇcelové funkce na zmˇeny prav´ ych stran.

30 Vˇ eta 25: Uvaˇzujme dvˇe u ´lohy NLP © min f (x) © min f (x)

¯ ¯ gk (x) ≥ bA k , 1 ≤ k ≤ m, ¯ ¯ gk (x) ≥ bB k , 1 ≤ k ≤ m,

x≥0 x≥0

ª ª

(4.13) (4.14)

a necht’ xA , xB jsou jejich optimáln´ı ˇreˇsen´ı splˇ nuj´ıc´ı GPO s Lagrangeov´ ymi multiplikátory yA , yB . Pak plat´ı X X A A A B A B (bB (bB (4.15) k − bk )yk ≥ f (x ) − f (x ) ≥ k − bk )yk k

k

D˚ ukaz: Staˇc´ı si pouze napsat GPO pro obˇe u ´lohy a pro jejich optimáln´ı body. X X A A f (xB ) + ykA (gk (xB ) − bA ykB (gk (xA ) − bA k ) ≥ f (x ) ≥ f (x ) + k ), k

A

f (x ) +

X

k

ykB (gk (xA )

−

bB k)

B

B

≥ f (x ) ≥ f (x ) +

k

X

ykA (gk (xB ) − bB k ).

k

Odeˇcten´ım tˇechto nerovnost´ı dostaneme nerovnost (4.15). Q.E.D.

4.4

´ Uloha kvadratick´ eho programov´ an´ı

´ Uloha kvadratického programován´ı má tvar 1 minimalizovat f (x) := p> x + x> Cx na konvexn´ı polyedrické mnoˇzinˇe M. (4.16) 2 Pˇredpokládá se pˇri tom, ˇze C je pozitivnˇe definitn´ı (nebo pozitivnˇe semidefinitn´ı) matice ˇrádu n a mnoˇzina M 6= ∅. To znamená, ˇze je u ´ˇcelová funkce konvexn´ı, omezen´ı lineárn´ı a lokáln´ı podm´ınky optimality jsou nutné a postaˇcuj´ıc´ı pro optimáln´ı ˇreˇsen´ı u ´lohy (4.16), viz vˇeta 23. Odvod´ıme si jejich tvar pro jednu z moˇzn´ ych voleb zápisu mnoˇziny M: Lok´ aln´ı podm´ınky optimality pro u ´lohu (4.16) pˇri mnoˇzinˇe pˇr´ıpustn´ ych ˇreˇsen´ı M = {x ∈ Rn | Ax ≤ b, Lagrangeova funkce:

x ≥ 0} ,

1 L (x; y) = p> x + x> Cx + y> (Ax − b) . 2

(4.17) (4.18)

Tvar podm´ınek (4.11): p + Cx + A> y ≥ 0,

x ≥ 0,

Tvar podm´ınek (4.12): Ax − bx ≤ 0,

y ≥ 0,

x> (p + Cx + A> y) = 0 .

(4.19)

y> (Ax − b) = 0 .

(4.20)

Uvedené podm´ınky jsou skoro lineárn´ı, aˇz na podm´ınky komplementarity. To umoˇzn ˇuje zaloˇzit postup pro ˇreˇsen´ı u ´lohy kvadratického programován´ı na vyˇreˇsen´ı tˇechto podm´ınek na simplexovém algoritmu. Tento algoritmus se naz´ yvá Wolfeho algoritmus (viz [3] nebo [4]). Jin´ y postup m˚ uˇze b´ yt zaloˇzen na skuteˇcnosti, ˇze pro pozitivnˇe definitn´ı matici C je u ´loha (4.16) ekvivalentn´ı, co do polohy optimáln´ıho ˇreˇsen´ı, u ´loze o projekci bodu volného minima funkce p> x+ 12 x> Cx na mnoˇzinu M. Pˇresnˇeji je ekvivalentn´ı u ´loze minimalizovat (x + C−1 p)> C(x + C−1 p) na konvexn´ı polyedrické mnoˇzinˇe M .

(4.21)

Z obecné vˇety o projekci pak také vypl´ yvá, ˇze pro M 6= ∅ a pro C pozitivnˇe definitn´ı má u ´loha kvadratického programován´ı vˇzdy optimáln´ı ˇreˇsen´ı. ´ Uloha kvadratického programován´ı si zachovává nˇekteré uˇziteˇcné rysy u ´loh LP (napˇr. speciáln´ı a numericky sch˚ udné postupy ˇreˇsen´ı) a podobnˇe jako u ´lohy NLP m˚ uˇze m´ıt optimáln´ı ˇreˇsen´ı v libovolném bodˇe mnoˇziny M. Mezi nejˇza´danˇejˇs´ı aplikace patˇr´ı r˚ uzné postupy pro optimalizaci portfolia cenn´ ych pap´ır˚ u s náhodn´ ym v´ ynosem, zejména Markowitz˚ uv model a modely zaloˇzené na maximalizaci stˇredn´ıho uˇzitku pˇri normáln´ım rozdˇelen´ı v´ ynos˚ u. Ve statistice a v ekonometrii se kvadratické programován´ı vyskytuje napˇr. v souvislosti s metodou nejmenˇs´ıch ˇctverc˚ u.

Kapitola 5

Dopravn´ı probl´ em Vyv´ aˇ zen´ y dopravn´ı probl´ em (pro

Pm i=1

ai =

Pn

j=1 bj )

má tvar:

m X n X

minimalizovat

ci,j xi,j

i=1 j=1

na mnoˇzinˇe nezáporn´ ych ˇreˇsen´ı soustavy n X

xi,j = ai ,

i = 1, . . . , m

xi,j = bj ,

j = 1, . . . , n

j=1 m X i=1

Tvar duáln´ı u ´lohy maximalizovat

m P i=1

za podm´ınek

ai ui +

n P j=1

bj vj

ui + vj ≤ ci,j

(5.1) ∀i, j

D˚ uleˇzité poznatky: • Hodnost matice soustavy pro dopravn´ı problém je m + n − 1, nedegenerovaná bazická ˇreˇsen´ı maj´ı tedy m + n − 1 nenulov´ ych sloˇzek. • Pro celoˇc´ıselné hodnoty prav´ ych stran jsou vˇsechna bazická ˇreˇsen´ı celoˇc´ıselná. • Vˇzdy existuje optimáln´ı ˇreˇsen´ı. Celoˇc´ıselné optimáln´ı ˇreˇsen´ı lze tedy v tomto pˇr´ıpadˇe naj´ıt pomoc´ı simplexové metody. Kterou jde nav´ıc podstatnˇe zjednoduˇsit s vyuˇzit´ım speciáln´ı struktury omezen´ı. V´ ysledn´ y postup je naz´ yván metoda ˇ r´ adkov´ ych a sloupcov´ ych ˇ c´ısel. Prob´ıhá v tˇechto kroc´ıch: Krok 1. Nalezen´ı v´ ychoz´ıho pˇ r´ıpustn´ eho bazick´ eho ˇ reˇ sen´ı Napˇr. metodou severozápadn´ıho rohu nebo indexovou metodou. Krok 2. Test optimality Pro vˇsechna xi,j > 0 vyˇreˇs´ıme odpov´ıdaj´ıc´ı soustavu rovnic ui + vj = ci,j . V´ ysledkem jsou ˇ r´ adkov´ aˇ c´ısla u∗i , i = 1, . . . , m a sloupcov´ aˇ c´ısla vj∗ , j = 1, . . . , n. Pokud u∗i +vj∗ ≤ ci,j ∀i, j (viz (5.1)), je z´ıskané ˇreˇsen´ı optimáln´ı a v´ ypoˇcet konˇc´ı. V opaˇcném pˇr´ıpadˇe pokraˇcujeme krokem 3. Krok 3. Zmˇ ena b´ aze, nov´ eˇ reˇ sen´ı, pokraˇcuje krok 2. Podobnˇe lze odvodit i algoritmus pro r˚ uzné varianty u ´ lohy o toku s´ıt´ı. I zde jsou známé podm´ınky na vstupn´ı data, pˇri kter´ ych jsou bazická pˇr´ıpustná ˇreˇsen´ı celoˇc´ıselná. Vˇeta o dualitˇe má speciáln´ı tvar znám´ y jako vˇ eta Fordova - Fulkersonova, pro algoritmus se vˇzil název out-of-kilter. V obecném pˇr´ıpadˇe simplexová metoda nevede na celoˇc´ıselné optimáln´ı ˇreˇsen´ı. Celoˇc´ıselné ˇreˇsen´ı lze nalézt za cenu numericky dosti nároˇcn´ ych dodateˇcn´ ych postup˚ u. Jedn´ım z nich je metoda vˇ etven´ı a mez´ı, kterou pouˇz´ıvá GAMS. Podm´ınky celoˇc´ıselnosti se vyskytuj´ı napˇr. v investiˇcn´ıch problémech. 31

32

Kapitola 6

V´ ypoˇ cetn´ı algoritmy pro optimalizaˇ cn´ı u ´ lohy Minimalizaˇcn´ı a maximalizaˇcn´ı u ´lohy ˇreˇs´ıme pomoc´ı v´ ypoˇ cetn´ıch algoritm˚ u. Zat´ım známe 1. Simplexová metoda; 2. Wolfeho algoritmus; 3. Gradientn´ı (Newtonova) metoda na pˇr´ımce bez omezen´ı. Algoritmy dˇel´ıme podle nˇekolika hledisek. I) Podle toho, zda vyuˇz´ıvaj´ı náhodného rozhodován´ı: deterministick´ e a stochastick´ e. II) Podle toho, zda konstruuj´ı posloupnost pˇribliˇzn´ ych ˇreˇsen´ı, která jsou pˇr´ıpustn´ ymi ˇreˇsen´ımi dané u ´lohy, ˇci nikoli: vnitˇ rn´ıho bodu (x∗ ∈ M) a vnˇ ejˇ s´ıho bodu (x∗ ∈ / M ). III) Podle toho jak´ y ˇrád derivace algoritmus vyuˇz´ıvá: pˇ r´ım´ e (funkˇcn´ı hodnoty), gradientn´ı (gradienty) a newtonovsk´ e (matice druh´ ych derivac´ı). V´ ybˇer a sestavován´ı algoritmu pro konkrétn´ı optimalizaˇcn´ı u ´lohu by mˇel brát v u ´vahu typ u ´lohy, heuristiku, tvar algoritmu a vlastnosti konvergence algoritmu. Základn´ı pozorován´ı: • Potˇrebujeme naj´ıt bod lokáln´ıho minima, v´ yhodou je konvexnost a polyedrická mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı. • Podstatná je struktura u ´lohy.

6.1

Struˇ cn´ y pˇ rehled algoritm˚ u pro NLP

Uvaˇzujeme u ´lohu min {f (x) : x ∈ M}. Idee k zjednoduˇsen´ı u ´lohy a pro urychlen´ı v´ ypoˇctu. 1. Nahradit funkci f lineárn´ı funkc´ı a mnoˇzinu M nahradit konvexn´ı polyedrickou mnoˇzinou. Pak m˚ uˇzeme pouˇz´ıt simplexovou metodu nebo nˇekter´ y jin´ y algoritmus pro ˇreˇsen´ı lineárn´ıho programován´ı. 2. Upravit gradientn´ı metodu na u ´lohu s omezen´ımi dan´ ymi mnoˇzinou M. 3. Pˇrevést u ´lohu na voln´ y extrém. Budeme si vˇs´ımat typu u ´lohy, heuristiky, nástinu algoritmu a jeho vlastnost´ı. Rozebereme si struˇcnˇe základn´ı typy algoritm˚ u. 33

34

6.2

Metoda seˇ cn´ e (opˇ ern´ e) nadroviny

Máme u ´lohu NLP: minimalizovat f (x) na mnoˇzinˇe M = {x ∈ Rn : gk (x) ≤ 0, k = 1, . . . , m},

(6.1)

kde f, gk , ∀k jsou konvexn´ı, spojitˇe diferencovatelné, existuje konstanta C s vlastnost´ı ||∇f (x)|| ≤ C, ||∇gk (x)|| < C pro vˇsechny x a M je kompakt. n

Máme M kompakt, proto m˚ uˇzeme naj´ıt M0 konvexn´ı polyedr - napˇr´ıklad M0 = X [Lj , Uj ] , kter´ y j=1

obsahuje M. Zaˇcneme minimalizac´ı funkce f na mnoˇzinˇe M0 . Dostaneme optimáln´ı ˇreˇsen´ı x0 . • Jestli x0 ∈ M, pak máme ˇreˇsen´ı zadané u ´lohy NLP. • Jestli x0 ∈ / M, pak ho podle vˇety o oddˇelitelnosti bodu a konvexn´ı mnoˇziny m˚ uˇzeme od M oddˇelit nadrovinou. Dostaneme tak konvexn´ı polyedr M1 ⊂ M0 tak ˇze M1 6= M0 , M1 ⊃ M , x0 ∈ / M1 . Minimalizujeme funkci f na mnoˇzinˇe M1 a pokraˇcujeme rekurentnˇe dále. Formulujme algoritmus zaloˇzen´ y na této myˇslence. Metoda seˇcné nadroviny KROK 1: Urˇci M0 konvexn´ı polyedr M0 ⊃ M. KROK 2: Je urˇcen konvexn´ı polyedr Mt takov´ y, ˇze Mt ⊃ M. Urˇci ˇreˇsen´ı x(t) u ´lohy: minimalizovat f na Mt . • Pokud x(t) ∈ M, pak x(t) ∈ argminx∈M f a je optimáln´ım ˇreˇsen´ım u ´lohy. • Pokud x(t) ∈ / M, jdi na KROK 3. KROK 3: Protoˇze x(t) ∈ / M je alespoˇ n jedna podm´ınka gk (x(t) ) > 0. (t) Vezmi nejvˇetˇs´ı poruˇsen´ı gkt (x ) = maxk gk (x(t) ). Poloˇz ½ ³ ´ n

(t)

(t)

Mt+1 = Mt ∩ x ∈ R : gkt (x ) + ∇gkt (x )

>

¾ (t)

(x − x ) ≤ 0 ,

(6.2)

t := t + 1 a vrat’ se na KROK 2. ♦ Mus´ıme jeˇstˇe ovˇeˇrit, ˇze v kroku 3 zachováme podm´ınku M ⊂ Mt+1 a x(t) ∈ / Mt+1 . • x(t) nepatˇr´ı do Mt+1 , protoˇze nesplˇ nuje pˇridanou podm´ınku v (6.2), jelikoˇz gkt (x(t) ) > 0. • Necht’ x ∈ M, pak gkt (x) ≤ 0. Funkce gkt je konvexn´ı a tak plat´ı ³ ´> gkt (x(t) ) + ∇gkt (x(t) ) (x − x(t) ) ≤ gkt (x) ≤ 0. Tedy x ∈ Mt+1 . Algoritmus nám dává posloupnost do sebe zaˇrazen´ ych mnoˇzin M0 ⊃ M1 ⊃ M2 ⊃ . . . ⊃ M. Na kaˇzdé z nich poˇc´ıtám minx∈Mt f a minimum monotónnˇe roste pro t → ∞. Jde o metodu vnˇejˇs´ıho bodu. Pokud algoritmus neskonˇc´ı v nˇekterém opakován´ı kroku 2, tak dostaneme x(t) ∈ / M a posloupnost f (x(t) ) = min f (x) % min f (x). x∈Mt

x∈M

Lze dokázat, ˇze kaˇzdá konvergentn´ı podposloupnost posloupnosti {x(t) } má limitu v mnoˇzinˇe optimáln´ıch ˇreˇsen´ı argminx∈M f (x).


35

Petr Lachout

V praxi vˇsak nem˚ uˇzeme udˇelat nekoneˇcnˇe mnoho krok˚ u tohoto algoritmu. Pokud nenalezneme optimáln´ı ˇreˇsen´ı, mus´ıme v´ ypoˇcet ukonˇcit nˇejak´ ym jin´ ym pravidlem; napˇr. omezen´ım poˇctu opakován´ı, ˇcasem v´ ypoˇctu, atd. Kdyˇz bude f lineárn´ı, pak v kroku 2 ˇreˇs´ıme u ´lohu lineárn´ıho programován´ı. Pˇredpoklad lineárn´ı f neznamená ˇzádnou ztrátu na obecnosti nebot’ obecnou u ´lohu (6.1) lze jednoduˇse pˇrevést na u ´lohu s lineárn´ı u ´ˇcelovou funkc´ı. Staˇc´ı pˇridat novou promˇennou xn+1 a ˇreˇsit u ´lohu min {xn+1 : g k (x1 , . . . , xn+1 ) ≤ 0, k = 1, . . . , m + 1} , kde g k (x1 , . . . , xn+1 ) = gk (x1 , . . . , xn ), k = 1, . . . , m,

g m+1 (x1 , . . . , xn+1 ) = f (x1 , . . . , xn ) − xn+1 .

Pˇr´ıklad 19: Maximalizujte x1 + x2 na mnoˇzinˇe ½µ ¶ ¾ x1 2 2 2 M= ∈ R : x1 + x2 ≤ 1, x1 ≥ 0, x2 ≥ 0 . x2 Nejdˇr´ıve u ´lohu pˇrep´ıˇseme na tvar, pro kter´ y byla metoda vyloˇzena © ª min −x1 − x2 : x21 + x22 − 1 ≤ 0, x1 ≥ 0, x2 ≥ 0 . Oznaˇcme g(x) = x21 + x22 − 1. Tato funkce má gradient ∇g(x) =

¡2x1 ¢ 2x2

.

0. Jako startovn´ı mnoˇzinu vezmeme ˇctverec M0 = [0, 1] × [0, 1]. 1. Minimalizujeme −x1 − x2 na M0 . Minimáln´ı hodnota u ´ˇcelové funkce je −2 a minimum nastává v bodˇe x0 = [1, 1], kter´ y nepatˇr´ı do M. 2. Podm´ınky nezápornosti splnˇeny jsou, ale podm´ınka g(x0 ) ≤ 0 nen´ı splnˇená, nebot’ g(x0 ) = 1 > 0. ˇ bude Rez µ ¶ x1 − 1 0 g(x ) + (2 2) ≤0 x2 − 1 tedy 1 + 2x1 − 2 + 2x2 − 2 ≤ 0 ⇒ x1 + x2 ≤ Tud´ıˇz M1 =

3 . 2

½µ ¶ ¾ x1 3 ∈ R2 : x1 + x2 ≤ , 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1 . x2 2

3. Minimalizujeme −x1 − x2 na M1 . Jak je vidˇet na obrázku, na u ´seˇcce (ˇrezu) si m˚ uˇzeme vybrat libovoln´ y bod. Vˇsechny budou body minima −x1 − x2 na dané mnoˇzinˇe M1 . Vybereme napˇr´ıklad ¡ ¢> bod x1 = 1, 21 . Minimáln´ı hodnota u ´ˇcelové funkce je f (x1 ) = − 23 . Tento bod opˇet splˇ nuje podm´ınky nezápornosti, ale nesplˇ nuje omezen´ı, protoˇze g(x1 ) = 1 + 14 − 1 = 1 4 > 0. ¡¢ Gradient je ∇g(x1 ) = 21 , proto pˇridáme omezen´ı µ g(x1 ) + (2 1)

x1 − 1 x2 − 12

¶ ≤ 0,

coˇz dává podm´ınku 2x1 + x2 ≤ Tud´ıˇz

½ M2 =

9 . 4

¾ 3 9 x ∈ R : x1 + x2 ≤ , 2x1 + x2 ≤ , 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1 . 2 4 2

36 4. Minimalizujeme −x1 − x2 na M2 . Minimáln´ı hodnota u ´ˇcelové funkce se nezmˇenila. Z˚ ustává − 32 a ¡ 3 3 ¢> ¡ 1 ¢> nab´ yv´ a se ji v kaˇzdém bodˇe u ´seˇcky s koncov´ ymi body 4 , 4 a 2, 1 . ¢ ¡ > Zvolme bod x2 = 43 , 34 . Bod nen´ı pˇr´ıpustn´ ym ˇreˇsen´ım naˇs´ı u ´lohy. Odˇr´ızneme jej ˇrezem µ 2

g(x ) +

3 3 2 2

¶µ

x1 − x2 −

coˇz dává podm´ınku x1 + x2 ≤

3¶ 4 3 4

≤ 0,

17 . 12

Tud´ıˇz ¾

½ M3

= =

9 17 3 , 2x1 + x2 ≤ , x1 + x2 ≤ , 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1 2 4 12 ½ ¾ 17 9 x ∈ R2 : x1 + x2 ≤ , 2x1 + x2 ≤ , 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1 . 12 4 x ∈ R2 : x1 + x2 ≤

17 e opˇet nen´ı pˇr´ıpustn´ ym 5. Bod minima opˇet nen´ı jednoznaˇcnˇe urˇcen. Vybereme x3 = [ 17 24 , 24 ], kter´ ˇreˇsen´ım naˇs´ı u ´lohy, a pokraˇcujeme dalˇs´ım krokem algoritmu. ³ √ √ ´> Takto zkonstruovaná posloupnost bude konvergovat k bodu x∗ = 22 , 22 , kter´ y je optimáln´ım ˇreˇsen´ım dané u ´lohy. 4

6.3

Zobecnˇ en´ı gradientn´ıch metod na u ´ lohy s omezen´ımi

Gradientn´ı metody jsou urˇceny pro u ´lohu min {f (x) : x ∈ M} , kde funkce f , která je spojitˇe diferencovatelná. Uvˇedomme si, ˇze pro obecn´ y smˇer s ∈ Rn plat´ı následuj´ıc´ı. Definujme funkci ϕ(λ) = f (x + λs) pro λ ≥ 0.

(6.3)

ϕ0 (λ) = s> ∇f (x + λs).

(6.4)

ϕ0 (0) = s> ∇f (x).

(6.5)

Funkce je diferencovatelná a plat´ı Speciálnˇe >

Tedy funkce ϕ klesá v bodˇe 0, pokud s ∇f (x) < 0. To znamená, ˇze funkce f klesá ve smˇeru s. ˇ ˜ ∈ M pro u Definice 6.1 Rekneme, ˇze s ∈ Rn je pˇ r´ıpustn´ y smˇ er z bodu x ´lohu min {f (x) : x ∈ M}, kdyˇz plat´ı 1. s> ∇f (x) < 0. 2. ∃ ε > 0 : x + λs ∈ M pro 0 ≤ λ ≤ ε Prvn´ı podm´ınka zaruˇcuje pokles funkce f pˇri pohybu z bodu x ve smˇeru s a druhá, ˇze pˇri malém pohybu v tomto smˇeru z˚ ustáváme v mnoˇzinˇe M. Pro nalezen´ı minima pouˇzijeme následuj´ıc´ı algoritmus. Gradientn´ı metoda KROK 1: Zvol x0 ∈ M. KROK 2: Urˇci pˇr´ıpustn´ y smˇer st z bodu xt .


37

Petr Lachout

• Jestli pˇr´ıpustn´ y smˇer neexistuje, pak jdi na KROK 4. • Jestli existuje, jdi na KROK 3 KROK 3: Generuj nové ˇreˇsen´ı xt+1 = xt + λt st , kde λt (napˇr.) ˇreˇs´ı jednorozmˇernou u ´lohu min{f (xt + λst ) : xt + λst ∈ M, λ ≥ 0}.

(6.6)

Poloˇz t := t + 1 a jdi na KROK 2. KROK 4: Je-li funkce konvexn´ı a M konvexn´ı, pak je xt optimáln´ı ˇreˇsen´ı. ♦ Jedná se o metodu vnitˇrn´ıho bodu. Pro u ´lohu konvexn´ıho programován´ı plat´ı, ˇze kdyˇz se algoritmus zastav´ı, pak nalezl optimáln´ı ˇreˇsen´ı. Tvrzen´ı 6.2 Necht’ je f konvexn´ı, M je konvexn´ı mnoˇzina a v bodˇe x∗ ∈ M neexistuje ˇza ´dný pˇr´ıpustný smˇer. Pak x∗ ∈ argminx∈M f (x). D˚ ukaz:

T

f (x) ≥ f (x∗ ) + ∇f (x∗ ) (x − x∗ ), ∀ x ∈ M.

Smˇer x − x∗ splˇ nuje vlastnost 2) z definice 6.1, nebot’ x∗ + λ(x − x∗ ) ∈ M pro kaˇzdé λ ∈ [0, 1] (tady jsme pouˇzili konvexnost M). Podle pˇredpokladu vˇsak nem˚ uˇze b´ yt smˇerem pˇr´ıpustn´ ym. Proto nutnˇe ∇f (x∗ )T s ≥ 0 a plat´ı f (x) ≥ f (x∗ ) + ∇f (x∗ )T s ≥ f (x∗ ), ∀ x ∈ M. Tud´ıˇz bod x∗ je optimáln´ım ˇreˇsen´ım u ´lohy. Q.E.D. Pro nekonvexn´ı funkce existuj´ı postupy jak hledat optimáln´ı ˇreˇsen´ı v pˇr´ıpadˇe, ˇze neexistuje pˇr´ıpustn´ y smˇer. Doporuˇcuje se napˇr´ıklad opakovaná volba startovac´ıho bodu x0 . ´ Ulohu (6.6) ˇreˇs´ıme numericky, napˇr´ıklad p˚ ulen´ım intervalu (0 ≤ λ ≤ ε). Problémem m˚ uˇze b´ yt volba smˇeru st , kde je pˇr´ıliˇs mnoho v˚ ule. V pˇr´ıpadˇe ˇspatné volby v˚ ubec nemus´ı algoritmus konvergovat k optimáln´ımu ˇreˇsen´ı (zigg-zagging), viz následuj´ıc´ı pˇr´ıklad: ˇ s´ıme u Pˇr´ıklad 20: Reˇ ´lohu maximalizovat f (x) = −x1 − x2 za podm´ınek x1 + x2 ≤ 2, x1 ≥ 0, x2 ≥ 0. Zvol´ıme x1 =

¡2¢ 0

, f (x1 ) = −2. Smˇer vol´ıme µ sk =

k

s =

−1 − k1 1 1 + k+1

µ 1+ −1

¶

1 ¶ k+1 − k1

(6.7)

(6.8)

1 Podm´ınky pˇr´ıpustného smˇeru: (−1, −1)sk = k1 − k+1 > 0, ∀k je splnˇena a taky mus´ıme ovˇeˇrit, ˇze jsme neopustili M. ¶ µ ¶ µ −2 2 − λ2 . s1 = 3 , x2 = x1 + λs1 = 3 2 2λ

x2 ∈ M kdyˇz 2 ≥ 2λ a 32 λ ≥ 0 ⇒ 0 ≤ λ ≤ 1. λ vol´ıme tak, aby ϕ rostla co nejv´ıce: 3 1 max −2 + 2λ − λ = max −2 + λ 2 2 λ∈[0,1] λ∈[0,1] tedy λ = 1. Dále

3 3 x2 = [0, ], f (x2 ) = − 2 2 ¡ ¡ 4¢ 4 ¢ + λ ˇ s´ıme a vol´ıme následuj´ıc´ı smˇer s2 = − 33 . Pak x2 + λs2 = 3 −33 λ a λ ∈ [0, 1]. Reˇ 2

2

2

3 3 4 max − λ + λ − 3 2 2 λ∈[0,1]

38 kde maximum bude opˇet pro λ = 1. Optimáln´ı bod je x3 = [ 43 , 0]. Hodnota f (x3 ) = − 34 . Problém je, ˇze tahle posloupnost neklesne pod spojnici bod˚ u [1, 0], [0, 1]. Pak ale f (xk ) −→ −1, kdeˇzto maximum nastává v [0, 0], kde f (x) = 0. 4 Pro rozumnou volbu pˇr´ıpustn´ ych smˇer˚ u je potˇrebné modifikovat 2.krok algoritmu. Existuje celá ˇrada moˇznost´ı, viz napˇr [1]. Metoda projekce gradientu, ´ho gradientu, optimáln´ı volba smˇeru. Uvedeme speciáln´ı pˇr´ıpad. Metoda redukovane Pˇr´ıklad 21: Necht’ M je omezená konvexn´ı polyedrická mnoˇzina. V bodˇe xt ˇreˇs´ıme u ´lohu LP, v které chceme doc´ılit miny∈M y> ∇f (xt ) a bod ve kterém nastane maximum pomocné u ´lohy oznaˇc´ıme yt . T

• Pokud (yt ) ∇f (xt ) = (xt )T ∇f (xt ), pak je xt optimáln´ı ˇreˇsen´ı a neexistuje s = yt − xt 6= 0 a s> ∇f (xt ) < 0, tedy ˇzádn´ y pˇr´ıpustn´ y smˇer z bodu xt . T

• Pokud (yt ) ∇f (xt ) < (xt )T ∇f (xt ) pak dostáváme pˇr´ıpustn´ y smˇer st = yt − xt , protoˇze T (yt − xt ) ∇f (xt ) < 0 a xt + λ(yt − xt ) ∈ M pro kaˇzdé λ ∈ [0, 1]. 4

6.4

Pˇ reveden´ı u ´ loh NLP na u ´ lohy hled´ an´ı voln´ eho minima

ˇn´ımi a barie ´rovy ´ mi metodami. Budeme se zab´ yvat penalizac ˇn´ı metoda: Penalizac Je urˇcena pro u ´lohy typu min {f (x) : x ∈ M} , kde M ⊂ X ⊂ Rn , M je uzavˇrená a X je otevˇrená mnoˇzina. Dále máme k dispozici vhodnou penalizaˇcn´ı funkci Ψ : X → R, která splˇ nuje Ψ(x) = 0 pro kaˇzdé x ∈ M a roste se vzdálenost´ı od mnoˇziny M. Pˇr´ıklad 22: Pro u ´lohu min {f (x) : hi (x) = 0, i = 1, . . . , p, gk (x) ≤ 0, k = 1, . . . , m, x ∈ Rn } m˚ uˇzeme penalizaˇcn´ı funkci volit napˇr´ıklad jako Ψ(x) =

p X

ρi (hi (x)) +

i=1

m X

φj (gj (x)),

j=1

kde • ρi je spojitá funkce, ρi (0) = 0, klesaj´ıc´ı na (−∞, 0) a rostouc´ı na (0, +∞); napˇr. |t|, t2 . • φj je spojitá funkce, φj (y) = 0 pro y ≤ 0 a rostouc´ı na (0, +∞); napˇr. 2 t+ = max{t, 0}, t2+ = (max{t, 0}) . 4 Metoda je zaloˇzena na aproximaci zadané u ´lohy u ´lohou min {f (x) + µΨ(x) : x ∈ X }. Penalizaˇcn´ı metoda KROK 1: ε > 0, x1 libovolnˇe, µ1 > 0, β > 1, k := 1. KROK 2: Hlavn´ı krok: Nalezneme xk+1 optimáln´ı ˇreˇsen´ı u ´lohy min {f (x) + µk Ψ(x) : x ∈ X } .


39

Petr Lachout

KROK 3: Pokud

µk Ψ(xk+1 ) < ε

pak algoritmus konˇc´ı. Jinak µk+1 = βµk a s k := k + 1 jdeme na KROK 2. ♦ Jedná se o metodu vnˇejˇs´ıho bodu. ´ metoda: Barierova Je urˇcena pro u ´lohy typu min {f (x) : x ∈ M} , n

kde M ⊂ R je uzavˇrená mnoˇzina a clo (int (M)) = M. Dále máme k dispozici vhodnou barierovou funkci Φ : M → R∗ , která splˇ nuje Φ(x) = +∞ pro kaˇzdé x ∈ ∂(M) a roste t´ım, ˇc´ım bl´ıˇze je k hranici mnoˇziny M. Jedná se o metodu vnitˇrn´ıho bodu. Metoda vyˇzaduje, aby mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı u ´lohy mˇela neprázdn´ y vnitˇrek. Hod´ı se proto pouze pro nerovnosti gk (x) ≤ 0, ∀ k a nen´ı vhodná pro u ´lohy s rovnicemi. Mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı u ´lohy s rovnost´ı má totiˇz prázdn´ y vnitˇrek. Pˇr´ıklad 23: Pro u ´lohu

min {f (x) : gk (x) ≤ 0, k = 1, . . . , m, x ∈ Rn } Pm m˚ uˇzeme barierovou funkci volit napˇr´ıklad jako Φ(x) = j=1 φj (gj (x)), kde funkce φj je spojitá, φj (y) roste do nekoneˇcna na (−∞, 0) a na [0, +∞) nen´ı definovaná (nebo je +∞). Hod´ı se funkce konvexn´ı; napˇr´ıklad − y1 nebo − log(−y) uvaˇzované pouze na (−∞, 0). 4 Metoda je zaloˇzena na aproximaci zadané u ´lohy u ´lohou min {f (x) + νΦ(x) : x ∈ int (M)}. Velikost´ı ν ˇr´ıd´ıme vliv bariérové funkce. Jestli Φ % ∞, pak pˇres ν tlum´ıme jej´ı r˚ ust, aby jejich souˇcin z˚ ustal u nuly. Funkce Φ vytváˇr´ı bariéru, pˇres kterou se nedostaneme - jde o metodu vnitˇrn´ıho bodu. Barierová metoda 1

KROK 1: ε > 0, x ∈ int (M) (jinak by algoritmus nefungoval), 0 < β < 1, k := 1. KROK 2: Hlavn´ı krok: Nalezneme xk+1 optimáln´ı ˇreˇsen´ı u ´lohy min {f (x) + νk Φ(x) : x ∈ int (M)} . KROK 3: Pokud plat´ı tolerance

νk Φ(xk+1 ) < ε

pak algoritmus konˇc´ı. Jinak klademe νk+1 = βνk , k := k + 1; a jdeme na KROK 2. ♦ Oba postupy m˚ uˇzeme kombinovat a pouˇz´ıt tzv. transformaˇ cn´ı funkce, které obsahuj´ı parametry µ & 0, ν & 0 X 1X Ψj (hj (x)) + ν Φk (gk (x)). µ j k

Pˇr´ıklad 24: Minimalizujte x za podm´ınek x ≥ 0. Jako bariérové funkce pouˇzije funkce x1 , − log x a jako penalizaˇcn´ı funkci pouˇzijeme 1r (x− )2 . Pak dostáváme u ´lohy: ª © 1 • min x + r x : x > 0 , kde r & 0, r > 0 je parametr. √ Diferencován´ım vyˇreˇs´ıme 1 − xr2 = 0 a tedy x = r. • min {x − r log x : x > 0}, r & 0, r > 0 parametr. Diferencován´ım vyˇreˇs´ıme 1 − xr = 0 a tedy x = r. ª © • min x + 1r (x− )2 : x ∈ R , r & 0 r > 0 je parametr. Minimum nastává v záporném oboru. Hledáme tedy x < 0 tak, aby 1 − 2r x = 0. Tud´ıˇz ˇreˇsen´ı je x = − 2r . 4

40

Kapitola 7

Teorie her V této kapitole se budeme zab´ yvat teori´ı her dvou hráˇc˚ u s nulov´ ym souˇctem. Definice 7.1 Trojici {X, Y; K} nazveme hrou dvou hr´ aˇ c˚ u s nulov´ ym souˇ ctem, kdyˇz X jsou strategie I. hr´ aˇce, Y jsou strategie II. hr´ aˇce a K : X × Y → R je výplata I. hr´ aˇce. To znamen´ a, ˇze kdyˇz I. hr´ aˇc zvol´ı strategii x ∈ X a II. hr´ aˇc zvol´ı strategii y ∈ Y, pak výplata I. hr´ aˇce je K(x, y) a výplata II. hr´ aˇce je −K(x, y). Hra je hr´ ana tak, ˇze ani jeden z hr´ aˇc˚ u pˇri volbˇe své strategie nem´ a k dispozici ˇz´ adnou informaci o volbˇe protihr´ aˇce. Oba hr´ aˇci zahraj´ı své zvolené strategie a výplatn´ı funkce urˇc´ı výhru ˇci prohru hr´ aˇce. Jako pˇr´ıklad her dvou hráˇc˚ u s nulov´ ym souˇctem si m˚ uˇzeme uvést ˇsachy, dámu, hru kámen-n˚ uˇzky” pap´ır“, atd. Jako hru m˚ uˇzeme také chápat p˚ usoben´ı lidské spoleˇcnosti na pˇr´ırodu, ekonomicko-politick´ y vztah dvou sousedn´ıch stát˚ u, sestaven´ı v´ yrobn´ıho plánu podniku (zde je protihráˇcem okoln´ı ekonomické prostˇred´ı), atd. Definice 7.2 Pro {X, Y; K} hru dvou hr´ aˇc˚ u s nulovým souˇctem definujeme horn´ı ocenˇ en´ı hry

v∗ = inf sup K(x, y),

(7.1)

doln´ı ocenˇ en´ı hry

v∗ = sup inf K(x, y),

(7.2)

horn´ı cenu hry

v = min sup K(x, y),

(7.3)

doln´ı cenu hry

v = max inf K(x, y).

(7.4)

y∈Y x∈X x∈X y∈Y

y∈Y x∈X

x∈X y∈Y

Pokud doln´ı a horn´ı cena hry existuje a plat´ı v = v, pak ˇr´ık´ ame, ˇze hra m´ a cenu v = v = v. ˇ Rekneme, ˇze x b ∈ X je optim´ aln´ı strategie I. hr´ aˇ ce, pokud yb ∈ Y je optim´ aln´ı strategie II. hr´ aˇ ce, pokud

∀ y ∈ Y : K(b x, y) ≥ v∗ , ∀ x ∈ X : K(x, yb) ≤ v∗ .

(7.5) (7.6)

Uvˇedomme si v´ yznam a d˚ uleˇzité vztahy mezi zaveden´ ymi pojmy. Nejprve si povˇsimnˇeme, ˇze horn´ı ocenˇen´ı hry je vlastnˇe nejniˇzˇs´ı zaruˇcená v´ yhra I. hráˇce, pokud by pˇred volbou své strategie znal pˇresnˇe strategii zvolenou II. hráˇcem. Obdobnˇe doln´ı ocenˇen´ı hry je vlastnˇe nejvyˇsˇs´ı zaruˇcená prohra II. hráˇce, pokud by pˇred volbou své strategie znal pˇresnˇe strategii zvolenou I. hráˇcem. Nyn´ı jiˇz ke vztah˚ um mezi zaveden´ ymi pojmy. Lemma 7.3 Pro kaˇzdou {X, Y; K} hru dvou hr´ aˇc˚ u s nulovým souˇctem vˇzdy existuje jej´ı doln´ı i horn´ı ocenˇen´ı. Nav´ıc plat´ı v∗ ≤ v∗ . D˚ ukaz: Pro kaˇzdé x ˜ ∈ X, y˜ ∈ Y plat´ı odhady inf K(˜ x, y) ≤

y∈Y

sup inf K(x, y) ≤ x∈X y∈Y

K(˜ x, y˜), sup K(x, y˜), x∈X

v∗ = sup inf K(x, y) ≤ x∈X y∈Y

41

inf sup K(x, y) = v∗ .

y∈Y x∈X

42 Q.E.D. Lemma 7.4 Necht’ {X, Y; K} je hra dvou hr´ aˇc˚ u s nulovým souˇctem. Pak plat´ı. (i) Existuje alespoˇ n jedna optim´ aln´ı strategie I. hr´ aˇce tehdy a jen tehdy, kdyˇz existuje doln´ı cena hry. (ii) Existuje alespoˇ n jedna optim´ aln´ı strategie II. hr´ aˇce tehdy a jen tehdy, kdyˇz existuje horn´ı cena hry. D˚ ukaz: 1. Necht’ x b ∈ X je optimáln´ı strategie prvého hráˇce. Pak plat´ı v∗ ≤ inf K(b x, y) ≤ sup inf K(x, y) = v∗ . y∈Y

x∈X y∈Y

Tud´ıˇz hra má doln´ı cenu a plat´ı x, y) = max inf K(x, y) = v. v∗ = inf K(b y∈Y

x∈X y∈Y

2. Necht’ má hra doln´ı cenu. Pak existuje x b ∈ X takové, ˇze plat´ı v∗ = max inf K(x, y) = inf K(b x, y). x∈X y∈Y

y∈Y

Tud´ıˇz plat´ı v∗ ≤ inf K(b x, y) y∈Y

a to znamená, ˇze x b je optimáln´ı strategie I. hráˇce. Ekvivalentn´ı vyjádˇren´ı existence optimáln´ı strategie II. hráˇce se ukáˇze obdobnˇe. Q.E.D. Vˇ eta 7.5: Necht’ {X, Y; K} je hra dvou hr´ aˇc˚ u s nulovým souˇctem. Kdyˇz X, Y jsou kompaktn´ı metrické prostory a K je spojit´ a funkce, pak existuje doln´ı i horn´ı cena hry. Nav´ıc plat´ı pro kaˇzdé x ∈ X existuje y ∗ (x) ∈ Y tak, ˇze K(x, y ∗ (x)) = min K(x, y) ∈ R,

(7.7)

pro kaˇzdé y ∈ Y existuje x∗ (y) ∈ X tak, ˇze K(x∗ (y), y) = max K(x, y) ∈ R,

(7.8)

v = max min K(x, y) ∈ R,

(7.9)

v = min max K(x, y) ∈ R.

(7.10)

y∈Y

x∈X

x∈X y∈Y

y∈Y x∈X

Vˇ eta 7.6: Hra {X, Y; K} m´ a cenu tehdy a jen tehdy, kdyˇz jej´ı výplatn´ı funkce K m´ a sedlový bod, tj. existuje x b ∈ X a yb ∈ Y takové, ˇze ∀ x ∈ X, ∀ y ∈ Y

plat´ı K(x, yb) ≤ K(b x, yb) ≤ K(b x, y).

Pak x b je optim´ aln´ı strategie I. hr´ aˇce, yb je optim´ aln´ı strategie II. hr´ aˇce a cena hry je v = K(b x, yb). D˚ ukaz: 1. Necht’ má hra cenu. Pak v´ıme, ˇze pro oba hráˇce existuj´ı optimáln´ı strategie x b ∈ X, yb ∈ Y a ∀ x ∈ X, ∀ y ∈ Y

plat´ı K(x, yb) ≤ v ≤ K(b x, y).

Odtud K(b x, yb) ≤ v ≤ K(b x, yb) neboli v = K(b x, yb). Jinak ˇreˇceno, bod (b x, yb) je sedlov´ y bod v´ yplatn´ı funkce K.

(7.11)


43

Petr Lachout

2. Necht’ bod (b x, yb) je sedlov´ y bod v´ yplatn´ı funkce K. Pak plat´ı K(b x, yb) = min K(b x, y) ≤ sup inf K(x, y) = v∗ , y∈Y

x∈X y∈Y

K(b x, yb) = max K(x, yb) ≥ inf sup K(x, y) = v∗ . x∈X

y∈Y x∈X

Vzhledem k tomu, ˇze vˇzdy v∗ ≤ v∗ , jsme zjistili, ˇze K(b x, yb) = max inf K(x, y) = min sup K(x, y) = v∗ = v∗ = v = v = v. x∈X y∈Y

y∈Y x∈X

Hra má tedy cenu v = K(b x, yb), x b je optimáln´ı strategie I. hráˇce a yb je optimáln´ı strategie II. hráˇce. Q.E.D. Vˇ eta 7.7 (O minimaxu): Necht’ {X, Y; K} je hra dvou hr´ aˇc˚ u s nulovým souˇctem. Kdyˇz X ⊂ Rn , Y ⊂ Rm jsou kompaktn´ı konvexn´ı mnoˇziny a K je spojit´ a funkce, konk´ avn´ı v x a konvexn´ı v y, pak existuje cena hry. D˚ ukaz: Viz [5]. Q.E.D. Povˇsimnˇeme si, ˇze postup pro ˇreˇsen´ı u ´lohy (4.1) pˇredstaven´ y v kapitole 4 je vlastnˇe speciáln´ım pˇr´ıpadem teorie her. Strategiemi I. hráˇce jsou pˇr´ıpustná ˇreˇsen´ı u ´lohy (4.1) a strategiemi II. hráˇce jsou Lagrangeovy multiplikátory. Lagrangeova funkce je pak v´ yplatn´ı funkc´ı. Tud´ıˇz vˇeta 7.7 a vztah mezi GPO, LPO a existenc´ı optimáln´ıho ˇreˇsen´ı u ´lohy (4.1) si jsou velmi bl´ızko. Nejsou vˇsak jedna zvláˇstn´ım pˇr´ıpadem druhé, nebot’ maj´ı r˚ uzné pˇredpoklady. Vˇeta 7.7 vyˇzaduje kompaktnost mnoˇzin pˇr´ıpustn´ ych strategi´ı, coˇz by byl omezuj´ıc´ı pˇredpoklad na u ´lohu (4.1).

7.1

Maticov´ e hry

Speciáln´ım typem her dvou hráˇc˚ u s nulov´ ym souˇctem jsou hry maticové. Definice 7.8 Budeme ˇr´ıkat, ˇze {X, Y; A} je maticov´ a hra, jestliˇze A ∈ Rn×m je matice, ( ) n X n X = x∈R : xi = 1, xi ≥ 0, i = 1, 2, . . . , n ,   Y

=



i=1

y ∈ Rm :

n X

(7.12)

  yj = 1, yj ≥ 0, j = 1, 2, . . . , m

j=1

,



(7.13)

jestliˇze {X, Y; K} je hra dvou hr´ aˇc˚ u s nulovým souˇctem, kde K(x, y) = x> Ay. Definice 7.9 K maticové hˇre {X, Y; A} budeme uvaˇzovat maticovou hru v ˇ cist´ ych strategi´ıch n o ˜ Y; ˜ A , kde X, ( ˜ = X ˜ Y

n

x∈R :  

=



n X

) xi = 1, xi ∈ {0, 1}, i = 1, 2, . . . , n ,

i=1

y ∈ Rm :

n X j=1

(7.14)

  yj = 1, yj ∈ {0, 1}, j = 1, 2, . . . , m



.

(7.15)

˜ y∈Y ˜ nazýv´ Strategie x ∈ X, ame ˇ cist´ e strategie. ˇ R´ık´ ame, ˇze hra {X, Y; A} m´ a cenu v ˇ cist´ ych strategi´ıch, pokud oba hr´ aˇci maj´ı ˇcisté optim´ aln´ı strategie.

44 Lemma 7.10 Mnoˇziny X, Y jsou konvexn´ımi polyedry a jsou tedy kompaktn´ı konvexn´ı mnoˇziny. D˚ ukaz: Mnoˇziny strategi´ı jsou evidentnˇe konvexn´ı polyedry. Q.E.D. Vˇ eta 7.11: Maticov´ a hra m´ a vˇzdy cenu a oba hr´ aˇci maj´ı optim´ aln´ı strategie. D˚ ukaz: Jde o speciáln´ı pˇr´ıpad vˇety 7.7. Q.E.D. Vˇ eta 7.12: Hra {X, Y; A} m´ a cenu v ˇcistých strategi´ıch tehdy a jen tehdy, kdyˇz hra

n o ˜ Y; ˜ A m´ X, a cenu.

D˚ ukaz: Staˇc´ı si pouze uvˇedomit definici optimáln´ıch strategi´ı. Q.E.D. Lemma 7.13 Necht’ {X, Y; A} je maticov´ a hra a m´ a cenu v. Necht’ x∗ ∈ X a y ∗ ∈ Y. >

(i) Pak x∗ je optim´ aln´ı strategie I. hr´ aˇce tehdy a jen tehdy, kdyˇz (x∗ ) A ≥ (v, v, . . . , v). (ii) Pak y ∗ je optim´ aln´ı strategie II. hr´ aˇce tehdy a jen tehdy, kdyˇz Ay ∗ ≤ (v, v, . . . , v)> . D˚ ukaz: K d˚ ukazu tvrzen´ı si staˇc´ı pouze uvˇedomit, ˇze >

>

(x∗ ) A ≥ (v, v, . . . , v) ⇐⇒ ∀ y ∈ Y : (x∗ ) Ay ≥ v, Ay ∗ ≤ (v, v, . . . , v)> ⇐⇒ ∀ x ∈ X : xAy ∗ ≤ v. Q.E.D. Lemma 7.14 Necht’ {X, Y; A} je maticov´ a hra, kter´ a m´ a cenu v a x b ∈ X, yb ∈ Y jsou optim´ aln´ı strategie I. a II. hr´ aˇce. (i) Kdyˇz x bi > 0, pak (Ab y )i = v. (ii) Kdyˇz ybj > 0, pak (b x> A)j = v. >

D˚ ukaz:PPlyne okamˇzitˇe z toho, ˇze x bAb y = v, Ab y ≤ (v, v, . . . , v)> , (b x) A ≥ (v, v, . . . , v)> , m x b ≥ 0, j=1 ybj = 1, yb ≥ 0.

Pn i=1

x bi = 1,

Q.E.D.

Vˇ eta 7.15: Maticov´ a hra {X, Y; A} m´ a cenu v ˇcistých strategi´ıch tehdy a jen tehdy, kdyˇz matice A m´ a sedlový bod; tj. existuj´ı indexy k, l takové, ˇze Ak,l = max {Ak,j : j = 1, 2, . . . , m} = min {Ai,l : i = 1, 2, . . . , n} .

(7.16)

D˚ ukaz: e[k : n] je optimáln´ı strategie I. hráˇce a e[l : m] je optimáln´ı strategie II. hráˇce m ∀ j = 1, 2, . . . , m : (e[k : n]> A)j = Ak,j ≥ v, ∀ i = 1, 2, . . . , n : (Ae[l : m])i = Ai,l ≤ v m Ak,l = max {Ak,j : j = 1, 2, . . . , m} = min {Ai,l : i = 1, 2, . . . , n} . Q.E.D. ˇ ık´ Definice 7.16 R´ ame, ˇze maticov´ a hra {X, Y; A} je spravedliv´ a, jestliˇze m´ a nulovou cenu, tj. v = 0.


45

Petr Lachout

ˇ ık´ Definice 7.17 R´ ame, ˇze maticov´ a hra {X, Y; A} je symetrick´ a, jestliˇze X = Y a A = −A> . Vˇ eta 7.18: Symetrick´ a maticov´ a hra {X, Y; A} je spravedliv´ a a oba hr´ aˇci maj´ı shodnou mnoˇzinu optim´ aln´ıch strategi´ı. D˚ ukaz: Uvˇedomme si, ˇze pro x ∈ X = Y plat´ı x> Ax = −x> A> x = −x> Ax. A tud´ıˇz x> Ax = 0. Jde tedy o spravedlivou hru, nebot’ cena hry je nulová. Necht’ x b ∈ X = Y je To je ekvivalentn´ı s To je ekvivalentn´ı s To je ekvivalentn´ı s

optimáln´ı strategie I. hráˇce. > t´ım, ˇze (b x) A ≥ 0> . t´ım, ˇze Ab x = −A> x b ≤ 0. t´ım, ˇze x b je optimáln´ı strategie II. hráˇce. Q.E.D.

Definice 7.19 Necht’ a, b ∈ Rn . Budeme ˇr´ıkat, ˇze a ostˇ re dominuje b pokud ai > bi pro kaˇzdé i = 1, 2, . . . , n. Vˇ eta 7.20: Necht’ {X, Y; A} je maticov´ a hra. • Kdyˇz ˇr´ adek matice Ak,• je ostˇre dominov´ an nˇejakou konvexn´ı line´ arn´ı kombinac´ı ostatn´ıch ˇr´ adk˚ u, pak kaˇzd´ a optim´ aln´ı strategie I. hr´ aˇce x b ∈ X m´ ax bk = 0. • Kdyˇz sloupec matice A•,k ostˇre dominuje nˇejakou konvexn´ı line´ arn´ı kombinaci ostatn´ıch sloupc˚ u, pak kaˇzd´ a optim´ aln´ı strategie II. hr´ aˇce yb ∈ Y m´ a ybk = 0. D˚ ukaz: Q.E.D. Speciálnˇe: • Kdyˇz ˇrádek matice Ak,• je ostˇre dominován ˇrádkem Al,• , pak kaˇzdá optimáln´ı strategie I. hráˇce x b ∈ X má x bk = 0. • Kdyˇz sloupec matice A•,k ostˇre dominuje sloupec A•,l , pak kaˇzdá optimáln´ı strategie II. hráˇce yb ∈ Y má ybk = 0. Pˇr´ıklad 25: 

3

  3   6  1

2

4

4

2

5

5

4

0



 3   3   −→  6  1   1 7 0

 4

2

5

5

4

0

3

 1   −→ 7

Ã

6

5

5

1

1

4

0

7

!

Ã −→

>

5 1 0 7

! .

>

>

Tud´ıˇz optimáln´ı strategie staˇc´ı hledat ve tvaru x b = (0, 0, x3 , x4 ) ,Ãyb = (0, 0, !y3 , y4 ) a strategie (x3 , x4 ) , 5 1 > (y3 , y4 ) jsou optimáln´ımi strategiemi pro hru s v´ yplatn´ı matic´ı . 0 7 Pro optimáln´ı strategie plat´ı 5x3 ≥ v, x3 + 7x4 ≥ v, 5y3 + y4 ≤ v, 7y4 ≤ v. Coˇz vede k tomu, ˇze min{5x3 , x3 + 7x4 } = v = max{5y3 + y4 , 7y4 }. Dostaneme rovnici 5x3 = x3 + 7x4 a odtud x3 = 74 x4 . 7 4 Odtud 1 = x3 + x4 = 74 x4 + x4 = 11 4 x4 . Tedy x3 = 11 , x4 = 11 a v = Obdobn´ ym zp˚ usobem nebo z komplementarity dopoˇcteme Tedy y3 =

35 11 . 6 11 ,

y4 =

5 11 .

¡ ¡ ¢ ¢ 6 7 4 > 5 > pro I. hráˇce, 0, 0, 11 pro II. hráˇce a cena hry je v = Optimáln´ı strategie jsou 0, 0, 11 , 11 , 11

35 11 .

4

46 ˇ ste graficky maticovou hru s v´ Pˇr´ıklad 26: Reˇ yplatn´ı matic´ı Ã ! 1 0 4 −1 A= . −1 1 −2 5 Optimáln´ı strategie jsou

¡2

¢ 1 > 3, 3

pro I. hráˇce,

¡1

¢> 2 3 , 3 , 0.0

pro II. hráˇce a cena hry je v = 13 .

4

Maticovou hry m˚ uˇzeme pˇrevést na dvojici duáln´ıch u ´loh lineárn´ıho programován´ı. Jejich vyˇreˇsen´ım zjist´ıme cenu hry i optimáln´ı strategie obou hráˇc˚ u. Vˇ eta 7.21: Maticové hˇre {X, Y; A} odpov´ıd´ a dvojice du´ aln´ıch u ´loh line´ arn´ıho programov´ an´ı       v   n   X  .  > ..  ≥ 0, max v : A x −  x = 1, x ≥ 0 , i       i=1   v       v   m   X  .    min v : Ay +  ..  ≥ 0, − yj = 1, y ≤ 0 .     j=1   v

(7.17)

(7.18)

Literatura [1] Bazara, M.S.; Sherali, H.D.; Shetty, C.M.: Nonlinear Programming. Theory and Algorithms. 2nd edition, Wiley, New York, 1993. [2] J. Dupaˇcová: Line´ arn´ı programov´ an´ı. Skripta MFF UK, Praha, 1982. [3] M. Hamala: Neline´ arne programovanie. Alfa, Bratislava, 1972. [4] M. Maˇ nas: Optimalizaˇcn´ı metody. SNTL, Praha, 1979. [5] T. Rockafellar: Convex Analysis. Springer-Verlag, Berlin, 1975.

47

Index u ´loha duáln´ı, 22 konvexn´ıho programován´ı, 12 LP, 12 NLP, 11 primárn´ı, 22 ve sm´ıˇseném tvaru, 15 ve standardn´ım tvaru, 15 ve tvaru nerovnost´ı, 15 algoritmus dvoufázov´ y simplexov´ y, 19 gradientn´ı, 33 newtonovsk´ y, 33 pˇr´ım´ y, 33 simplexov´ y, 18 vnˇejˇs´ıho bodu, 33 vnitˇrn´ıho bodu, 33 algoritmy, 33 deterministické, 33 stochastické, 33 báze, 16 bazické ˇreˇsen´ı, 16 degenerované bazické ˇreˇsen´ı, 16 pˇr´ıpustná, 16 pˇr´ıpustné bazické ˇreˇsen´ı, 16 ceny duáln´ı, 26 st´ınové, 26 dopravn´ı problém vyváˇzen´ y, 31 dvojice duáln´ıch u ´loh LP, 22 symetrick´ ych, 23 funkce konkávn´ı, 10 konvexn´ı, 10 globáln´ı podm´ınky optimality, 27

dvou hráˇc˚ u, 41 horn´ı cena, 41 horn´ı ocenˇen´ı, 41 maticová, 43 optimáln´ı strategie, 41 konvexn´ı obal mnoˇziny, 9 krajn´ı bod mnoˇziny, 10 kuˇzel, 9 konvexn´ı, 9 nejmenˇs´ı obsahuj´ıc´ı mnoˇzinu, 9 konvexn´ı polyedrick´ y, 9 krajn´ı smˇer, 10 kvadratického programován´ı, 12 lokáln´ı podm´ınky optimality, 29, 30 maximum globáln´ı, 7 lokáln´ı, 7 ostré globáln´ı, 7 ostré lokáln´ı, 7 metoda bariérová, 39 penalizaˇcn´ı, 38 vnˇejˇs´ıho bodu, 34, 39 vnitˇrn´ıho bodu, 37, 39 metoda ˇrádkov´ ych a sloupcov´ ych ˇc´ısel, 31 minimum globáln´ı, 7 lokáln´ı, 7 ostré globáln´ı, 7 ostré lokáln´ı, 7 mnoˇzina index˚ u aktivn´ıch omezen´ı, 28 konvexn´ı, 9 konvexn´ı polyedr, 9 konvexn´ı polyedrická, 9 pˇr´ıpustn´ ych ˇreˇsen´ı, 16 nadrovina, 9 ostrá dominance, 45

hra ˇcist´ a strategie, 43 cena, 41 cena v ˇcist´ ych strategi´ıch, 43 doln´ı cena, 41 doln´ı ocenˇen´ı, 41

pˇr´ıpustn´ y smˇer, 36 podm´ınka lineárn´ı nezávislosti, 28 Slaterova, 28 podm´ınka komplementarity 48


NLP, 27 podm´ınka regularity, 28 podm´ınky komplementarity, 24 poloprostor, 9 promˇenné skluzové, 16 prostor, 9 symetrická u ´loha NLP, 27 vˇeta siln´ a o dualitˇe, 24 slabá o dualitˇe, 24

Petr Lachout

49

Úvod do optimalizace

Recommend Documents