Cape. 4: Lineárne programovanie
1 kap. 4: Lineárne programovanie profesor Dr. Petra Mutzel Predsedníčka algoritmického inžinierstva, LS11 Fakulta informatiky, TU Dortmund 13./14. VO A&D ZS 08// Petra Mutzel Alg. A dátum ZS 08/09 1
2 Literatúra k tomuto VO V. Chvatal: Lineárne programovanie D. Bertsimas: Lineárne programovanie B. Vöcking: Crash Course Lineárne programovanie, Algoritmy pre prednášku na univerzite v Dortmunde SS2003 (pozri web) P. Mutzel: Optimalizácia skriptových častí (pozri web ) Petra Mutzel Alg. A dátum ZS 08/09 2
3 3.1 Úvod Príklad Prehľad ropných rafinérií Príklad Strava Problém Geometrická interpretácia Štandardné formuláre Simplexný algoritmus Motivácia duality 3.2 VO Simplexný algoritmus vo štvrtok je vynechaný z dôvodu Pohrebná služba pre prof. Wegenera Petra Mutzela Alg. A dátum. ZS 08/09 3
4 Problémy s lineárnou optimalizáciou Definícia problému s lineárnou optimalizáciou (LP): Problém hľadania vektora, ktorý za všetkých vektorov, ktoré spĺňajú podmienky Ax 5 Príklad ropnej rafinérie 2 Proces krakovania ropy s nasledujúcimi výnosmi a nákladmi: Proces krakovania 1: 2S, 2M, 1L, náklady 3 EUR Proces prasknutia 2: 1S, 2M, 4L, náklady 5 EUR Ciele: vyrobiť najmenej 3S, 5M, 4L (dodacie podmienky) vyrobiť čo najlacnejšie Petra Mutzel Alg. & Dat. WS 08/09 5
6 Príklad ropnej rafinérie Cieľová funkcia podliehajúca obmedzeniam definuje priestor riešenia Maticový zápis: (tabuľa) Petra Mutzel Alg. & Dat. WS 08/09 6
7 r (0,6) Geometrická interpretácia objektívna funkcia = 0,9 * * 0,706 = 13,1 milióna NB1 Maximalizácia 0,90 xy predmetu Na NB1: 0,42 xy = 0 NB5: y> = 0 (0,1,5) (0,1) (0,882,0,706 ) (0,0) Prípustné riešenia (1,0) NB2 (2,0) (3,0) x
8 Geometrická interpretácia LP Príklad: Ropná rafinéria Petra Mutzel Alg. A dát. WS 08/09 8
9 Príklad problému s diétou Cieľ: Nakúpiť čo najlacnejšie, aby najmenej 2 000 kcal, 55 g bielkovín, 800 g vápnika Podmienky nákupu: Ovsené vločky v 28 g balení, 110 kcal, 4 g bielkoviny, 2 mg vápnika v 3 centoch kuracie mäso v 100 g balení, s 205 kcal, 32 g bielkovín, 12 mg vápnika na 24 centov vajcia v dvojitom balení po 160 kcal, 13 g bielkovín, 54 mg vápnika na 13 centov mlieko na balenie 237 ml, 160 kcal, 8 g bielkovín, 285 g vápnika na 9 centov čerešňový koláč v 179 g Balenie s 420 kcal, 4 g bielkovín, 22 mg vápnika pri 20 centoch fazule v 260 g balení s 19 centami, 260 kcal, 14 g bielkovín, 80 mg vápnika pri 19 centoch
10 LP pre samotný problém s diétou Dodatočná sekundárna podmienka: Ovsené vločky by sa nemali jesť bez mlieka: Na jedno balenie ovsených vločiek je potrebných pol balenia mlieka: 0,5 x 4 x 1 Petra Mutzel Alg. & Dat. WS 08/09 10
11 Problémy s lineárnou optimalizáciou Problémy s lineárnou optimalizáciou sa vyskytujú v rôznych formuláciách a je ich možné všetky previesť do iného: max alebo min c T x: Ax b min c T x: Ax b a x 0 min c T x: Ax = b a x 0 Považujeme Štandardný formulár: max c T x: Ax = ba x 0 Petra Mutzel Alg. & Dat. ZS 08/09 11
12 Problémy s lineárnou optimalizáciou LP v jeho najvšeobecnejšej podobe: Každý vektor (x, y), ktorý spĺňa všetky obmedzenia, sa nazýva uskutočniteľné riešenie LP. Petra Mutzel Alg. A dátum ZS 08/09 12
13 Geometrické znázornenie: priestor riešenia Premenná alokácia x = (x j) zodpovedá bodu v n-rozmernom priestore R n. Každé obmedzenie a it x b i definuje polpriestor. Hranicou tohto polopriestoru je nadrovina a it x = b i. Polopriestor sa skladá z bodov na jednej strane tejto nadroviny vrátane bodov na samotnej nadrovine. Priesečník polopriestorov cez všetky obmedzenia predstavuje priestor prípustných riešení. Priestor riešenia tvorí mnohosten. Ohraničené mnohosteny sa nazývajú polytopy. Množina bodov opísaná mnohostenom je konvexná, to znamená, že pre každú dvojicu bodov x, y P sú všetky body na spojovacej čiare medzi x a y v P. Výňatok z Vöckinga (pozri vyššie)
14 Geometrické znázornenie: objektívna funkcia Objektívna funkcia z (x) = c T x označuje smer v R n. Tento smer môžeme vizualizovať lúčom začínajúcim od začiatku a prechádzajúcim bodom c. Nech H je hyperplán, ktorý je kolmý na lúč objektívnej funkcie, to znamená, že existuje hodnota z R taká, že H =. Všetky body na H majú rovnakú hodnotu objektívnej funkcie z, ktorú nazývame z (h). LP, ktorého hodnota objektívnej funkcie z (x) je ohraničená obmedzeniami smerom hore (pri max z (x)), sa nazýva ohraničený LP. Inak je LP neobmedzený. Výňatok z Vöcking (pozri vyššie)
15 Geometrické znázornenie: rohové riešenia Každých n lineárne nezávislých hyperplánov sa pretína v priesečníku. Priesečníky obsiahnuté v roztoku mnohostenu P sa nazývajú vrcholy P. Dva rohy susedia, ak sa líšia presne v jednej nadrovine. Susedné rohy sú navzájom spojené hranou. Okraj zodpovedá priesečníku n-1 bežných hyperplánov týchto rohov. Výňatok z Vöcking (pozri vyššie)
16 Geometrické znázornenie: optimálne riešenie Obmedzený LP vo forme max c T x s.t. Ax b, x 0 s objektívnou funkciou z a riešenie mnohostenu P. H a hyperplán ortogonálny k z, ktorý pretína P. Predstavujeme si, že H je posunutá smerom hore (t.j. v smere objektívnej funkcie). Vo výsledku sa z (h) kontinuálne zvyšuje. Presunieme H presne tak, aby nad H už nebol žiadny bod. Nech H * je takto získaná nadrovina. Potom H * P obsahuje optimálne riešenia LP. Kvôli konvexite je aspoň jeden z týchto bodov rohom P. Takže vždy existuje roh s optimálnou cieľovou hodnotou. Buďte výňatkom z Vöcking (pozri vyššie)
17 Geometrické znázornenie: Optimálny roh Nech v je ľubovoľný roh mnohostena P. Nech H v je nadrovina ortogonálna k z, ktorá vedie cez v. Nech e je jeden z okrajov, ktoré majú byť v incidente. Ak e beží nad H v, cieľová hodnota sa zlepší, ak jeden začne z v a beží pozdĺž e. Takáto hrana sa nazýva zlepšujúca sa hrana. Ak v nemá zlepšujúcu sa hranu, nemôžeme H v posunúť nahor bez toho, aby sme opustili P (kvôli konvexnosti). Takže H v = H * a teda v je optimálne. Tu platí: Globálne optimum zodpovedá lokálne optimálnemu rohu. Výňatok z Vöcking (pozri vyššie)
18 Súhrnná veta: Pre každú ohraničenú LP formy max c T x s.t. Ax b, x 0 s riešením mnohosten P je najmenej jeden vrchol P, ktorý nadobúda optimálnu hodnotu objektívnej funkcie (optimálny roh). Kút bez zlepšenia dopadajúcej hrany je optimálny.
19 Lineárne programovanie Pre rozsah prípustnosti P lineárneho programu existujú tri rôzne možnosti: P = neexistuje jediné prípustné riešenie LP je neriešiteľné P a inf neexistuje (napr. 0x -1) LP je riešiteľný, ale neexistuje optimálne riešenie P a min existuje LP je riešiteľný a má konečné riešenie x * s c T x * = min Petra Mutzel Alg. & Dat. ZS 08/09 19
20 Dualita lineárneho programovania Je výhodné vedieť určiť hranice pre lineárne programy Bod, ktorý spĺňa (2) - (4), taktiež vyhovuje nerovnosti: 2 (2) + (3) Hľadáme najlepšie hranice: Dualita Petra Mutzel Alg. & Date WS 08/09 20
21 Dualita lineárneho programovania Primárny program: Duálny program: Petra Mutzel Alg. & Dat. WS 08/09 21
22 Dualita lineárneho programovania Primálny program (P): Duálny program (D): Veta o slabosti: Nech x je platný bod pre (P) a y pre (D). Potom: y T b c T x Dodatok: Ak (P) je neobmedzené, potom (D) je neriešiteľné. Petra Mutzel Alg. A dátum ZS 08/09 22
23 Dualita lineárneho programovania Primálny program (P): Duálny program (D): Veta o silnej dualite: Nech x * je prípustný bod pre (P) a y * prípustné pre (D). Potom: y * T b = c T x * obe riešenia x * a y * sú optimálne Podrobnosti: neskôr v prednáške Petra Mutzel Alg. & Dat. ZS 08/09 23
24 3.2 Simplexov algoritmus V praxi sú lineárne programy riešené pomocou simplexného algoritmu [Dantzig 1955]. Max 3x 1 + 2x 2 + 2x 3 Podlieha x 1 + x 3 8 x 1 + x 2 7 x 1 + 2x 2 12 x 1, x 2, x 3 0 Petra Mutzel Alg. & Dat. WS 08/09 24
25 Vizualizácia simplexného algoritmu Max z = 3x 1 + 2x 2 + 2x 3 x 3 (0,0,8) (0,6,8) Optimálne! (2,5,6) z = 28 z = 0 (0,6,0) x 2 (7,0,1) z = 23 (2,5,0) x 1 (7,0,0) z = 21. deň
26 Simplexný algoritmus Zadané: LP s riešením mnohosten P (1) Nájdite ľubovoľný roh (počiatočný roh) v z P. (2) Ak nedôjde k zlepšeniu dopadu hrany na v stop: v je optimálne. (3) Poradie každej zlepšujúcej sa hrany e v. Ak e je neobmedzené, t. J. Nemá žiadny iný koncový bod zastavenia: LP je neobmedzené. (4) Nech u je druhý koncový bod napr. Nastaviť v = u. Prejsť na (2)
27 Otvorené otázky o simplexnom algoritme Ako nájdete počiatočný roh v P? Pre prípustné LP v štandardnej forme s nezápornými a ij a bi je počiatok (bod 0) vždy uzlom P. Inak sa použije predspracovanie (fáza 1), ktoré môže začať na križovatke mimo P a podobnými základnými výmennými krokmi. beží do kúta v P. Ako sa šetrí mnohosten? Systém rovníc opísaný obmedzeniami je uložený vo forme tabla. V každom kroku simplexu sa zmení tablo a z tabla sa dajú vypočítať odchádzajúce okraje aktuálneho rohu. Vyskúšajte, či je súčasný roh optimálny? Ak nie, aký vylepšujúci okraj si vyberiete? Končí sa algoritmus? pozri prednáška: rovnaká
28 Definície Nechajte uviesť sústavu rovníc Ax = b s A R m n, m. 29 Definície Ak je A B regulárne (= invertovateľné), A B sa nazýva bázová matica alebo báza A a B sa nazýva vektor bázového indexu alebo báza A; analogický k A N, N vektoru bázického indexu. Vektor x R n s x N = 0, x B = AB -1 b sa nazýva základné riešenie Ax = b k báze A B. Ak AB je báza, premenné sa nazývajú xj, j B, základné premenné a xj, j N Nezákladné premenné. Ak A B je báza a platí A B -1 b 0, potom A B, B a zodpovedajúce bázické riešenie x sa nazývajú prípustné, inak nie sú prípustné. Realizovateľné základné riešenie x pre základ A B sa nazýva nedegenerované, ak (x B) i = (A B -1 b) i> 0 pre všetky i B, inak degenerované.
30 Schéma Simplexovej rovnice a Simplex tablo max c T x s.t. Sekera = b, x 0 max c B c N T x B x N s.t. (AB, AN) x B = b, x B 0 x N x NAB x B + AN x N = bx B = AB 1 b AB 1 AN x N Objektívna funkčná hodnota: z = c BT x B + c NT x N = c BT (AB 1 b AB 1 AN x N) + c NT x N = = c TBA 1 B b + (c TN c TBA 1 BAN) x N Zjednodušená rovnica: x B = A 1 B b A 1 BAN x N z = c TBA 1 B b + (c TN c TBA 1 BAN) x N
31 Schéma jednoduchej rovnice a schéma Simplexovej schémy Simplexná rovnica: x B = AB 1 b AB 1 AN x N z = c BTAB 1 b + (c NT c BTAB 1 AN) x N Hodnota objektívnej funkcie Simplexná tabuľka: hodnoty základných premenných - c BTAB 1 b AB 1 bc NT c BTAB 1 ANAB 1 AN znížené náklady
32 Schéma Simplexovej rovnice a Simplexova tabloová veta: Nech A B je uskutočniteľný základ so základným riešením x, A = A 1 B A N, b = A 1 B b a c T = c T N c T B A 1 B A N so zníženými nákladmi. (a) Ak c T x 0, potom x je optimálne (b) Nech q s N s c s> 0. (b1) Ak A s 0, potom c T x na P = (A, b): = neobmedzené. (b2) Ak A S 0, potom nech λ 0 = min b i i = 1,2. m, a je> 0 a je a r < 1,2. m>takže b r = λ 0, a rs> 0 a rs potom A B s B = (p 1. p r-1, q s, p r + 1. p m) je uskutočniteľný základ so základným riešením x a c T x c T x. (b3) Ak platia predpoklady z (b2) a A B nie je zdegenerovaný, potom platí c T x> c T x. Dôkaz: ďalší príklad VO Di, pozri tabuľku