Pelerină. 4: Programare liniară
1 cap. 4: Programare liniară Profesor Dr. Petra Mutzel Catedra de Inginerie Algoritmică, LS11 Facultatea de Informatică, TU Dortmund 13./14. VO A&D WS 08// Petra Mutzel Alg. & Dat. WS 08/09 1
2 Literatură pentru acest VO V. Chvatal: Programare liniară D. Bertsimas: Programare liniară B. Vöcking: Crash Course Linear Programming, Lecture Efficient Algorithms at the University of Dortmund SS2003 (see Web) P. Mutzel: Script Part Optimization (see Web ) Petra Mutzel Alg. & Date. WS 08/09 2
3 3.1 Introducere Exemplu de rafinărie de petrol Prezentare generală Exemplu Dieta Problemă Interpretare geometrică Forme standard Algoritmul Simplex Motivația dualității 3.2 Algoritmul Simplex VO de joi este omis din cauza Serviciu funerar pentru prof. Wegener Petra Mutzel Alg. & Dat. WS 08/09 3
4 Probleme de optimizare liniară Definiția unei probleme de optimizare liniară (LP): Problema găsirii unui vector care, sub toți vectorii care îndeplinesc condițiile Ax 5 Exemplu de rafinărie de petrol 2 Proces de cracare pentru țiței cu următorul randament și costuri: Proces de cracare 1: 2S, 2M, 1L, cost 3 EUR Proces de cracare 2: 1S, 2M, 4L, costă 5 EUR Obiective: produce cel puțin 3S, 5M, 4L (condiții de livrare) produc cât mai ieftin posibil Petra Mutzel Alg. & Dat. WS 08/09 5
6 Exemplu de rafinărie de petrol Funcția obiectivă supusă restricțiilor definește spațiul soluției Notarea matricei: (tablă) Petra Mutzel Alg. & Dat. WS 08/09 6
7 y (0,6) Funcția obiectivă de interpretare geometrică = 0,9 * * 0,706 = 13,1 milioane NB1 Maximizați 0,90 xy subiect La NB1: 0,42 xy = 0 NB5: y> = 0 (0,1,5) (0,1) (0,882,0.706 ) (0,0) Soluții admisibile (1,0) NB2 (2,0) (3,0) x
8 Interpretare geometrică LP Exemplu: Rafinărie de petrol Petra Mutzel Alg. & Dat. WS 08/09 8
9 Exemplu de problemă dietetică Obiectiv: Cumpărați cât mai ieftin posibil, astfel încât cel puțin 2000 kcal, 55g proteine, 800 g calciu Condiții de cumpărare: Fulgi de ovăz în pachete de 28 g, 110 kcal, 4 g proteine, 2 mg calciu în 3 cenți pui în pachete de 100 g, cu 205kcal, 32 g proteine, 12 mg calciu până la 24 cenți ouă în pachete duble de 160 kcal, 13 g proteine, 54 mg calciu până la 13 cenți lapte pe ambalaj 237 ml, 160 kcal, 8 g proteine, 285 g calciu până la 9 cenți tort de cireșe în 179 g Pachet cu 420 kcal, 4 g proteine, 22 mg calciu la 20 cenți fasole în 260 g pachet cu 19 cenți, 260 kcal, 14 g proteine, 80 mg calciu la 19 cenți
10 LP pentru problema dietei în sine Condiție secundară suplimentară: Fulgi de ovăz nu trebuie consumați fără lapte: O jumătate de pachet de lapte este necesar pentru un pachet de fulgi de ovăz: 0,5 x 4 x 1 Petra Mutzel Alg. & Dat. WS 08/09 10
11 Probleme de optimizare liniară Problemele de optimizare liniară apar în diferite formulări și pot fi toate transformate una în alta: max sau min c T x: Ax b min c T x: Ax b și x 0 min c T x: Ax = b și x 0 Considerăm că Forma standard: max c T x: Ax = b și x 0 Petra Mutzel Alg. & Dat. WS 08/09 11
12 Probleme de optimizare liniară LP în forma sa cea mai generală: Fiecare vector (x, y) care îndeplinește toate constrângerile este numit o soluție fezabilă a LP. Petra Mutzel Alg. & Date. WS 08/09 12
13 Reprezentare geometrică: spațiu de soluție O alocare variabilă x = (x j) corespunde unui punct din spațiul n-dimensional R n. Fiecare restricție a it x b i definește un jumătate de spațiu. Limita acestui jumătate de spațiu este hiperplanul a it x = b i. Demi-spațiul constă din punctele de pe o parte a acestui hiperplan, inclusiv punctele de pe hiperplanul propriu-zis. Intersecția jumătăților de spațiu peste toate restricțiile este spațiul soluțiilor admisibile. Spațiul soluției formează un poliedru. Poliedrele delimitate se numesc politopi. Setul de puncte descris de un poliedru este convex, adică pentru fiecare pereche de puncte x, y P, toate punctele de pe linia de legătură dintre x și y sunt în P. Extras din Vöcking (vezi mai sus)
14 Reprezentare geometrică: funcție obiectivă Funcția obiectivă z (x) = c T x indică o direcție în R n. Putem vizualiza această direcție printr-o rază care începe de la origine și trece prin punctul c. Fie H un hiperplan ortogonal la raza funcției obiective, adică există o valoare z R astfel încât H =. Toate punctele de pe H au aceeași valoare a funcției obiective z, pe care o numim z (h). Un LP a cărui valoare a funcției obiective z (x) este delimitată de constrângeri în sus (la max z (x)) se numește LP delimitat. În caz contrar, LP este nelimitat. Extras din Vöcking (vezi mai sus)
15 Reprezentare geometrică: soluții de colț N hiperplane liniar independente se intersectează într-un punct de intersecție. Punctele de intersecție conținute în poliedrul soluției P se numesc vârfurile lui P. Două colțuri sunt adiacente dacă diferă exact într-un singur hiperplan. Colțurile adiacente sunt conectate între ele printr-o margine. Marginea corespunde intersecției hip-planurilor comune n-1 ale acestor colțuri. Extras din Vöcking (vezi mai sus)
16 Reprezentare geometrică: soluție optimă Un LP limitat sub forma max c T x s.t. Ax b, x 0 cu funcție obiectivă z și poliedru soluție P. H un hiperplan ortogonal la z care intersectează P. Ne imaginăm că H este deplasat în sus (adică în direcția funcției obiective). Ca rezultat, z (h) crește continuu. Mutați H exact astfel încât să nu mai existe niciun punct deasupra lui H. Fie H * hiperplanul obținut în acest fel. Apoi H * P conține soluțiile optime ale LP. Datorită convexității, cel puțin unul dintre aceste puncte este un colț al lui P. Deci, există întotdeauna un colț cu o valoare țintă optimă. Fii un extras din Vöcking (vezi mai sus)
17 Reprezentare geometrică: colț optim Fie v un colț arbitrar al poliedrului P. Fie H v hiperplanul ortogonal la z care trece prin v. Fie e una dintre muchiile care trebuie să fie v incident. Dacă e rulează peste H v, valoarea țintă se îmbunătățește dacă unul începe de la v și rulează de-a lungul lui e. O astfel de margine se numește o margine de îmbunătățire. Dacă v nu are margine de îmbunătățire, nu putem muta H v în sus fără a părăsi P (din cauza convexității). Deci H v = H * și astfel v este optim. Aici se aplică următoarele: Optimul global corespunde unui colț optim local. Extras din Vöcking (vezi mai sus)
18 Teorema rezumativă: Pentru fiecare LP delimitat de forma max c T x s.t. Ax b, x 0 cu poliedru soluție P există cel puțin un vârf al lui P care preia valoarea funcției obiectivului optim (colțul optim). Un colț fără margine de incident îmbunătățit este un colț optim.
19 Programare liniară Există trei posibilități diferite pentru intervalul de admisibilitate P al unui program liniar: P = nu există o singură soluție admisibilă LP este nerezolvabilă P și inf nu există (de ex. 0x -1) LP este rezolvabilă, dar nu există o soluție optimă P și min există LP este rezolvabil și are o soluție finită x * cu c T x * = min Petra Mutzel Alg. & Dat. WS 08/09 19
20 Dualitatea programării liniare Este avantajos să puteți specifica limite pentru programele liniare. Un punct care satisface (2) - (4) satisface și inegalitatea: 2 (2) + (3) Căutăm cele mai bune limite: Dualitatea Petra Mutzel Alg. & Data. WS 08/09 20
21 Dualitatea programării liniare Programul principal: Programul dual: Petra Mutzel Alg. & Dat. WS 08/09 21
22 Dualitatea programării liniare Programul primar (P): Programul dual (D): Teorema slabă a dualității: Fie x un punct valid pentru (P) și y valid pentru (D). Apoi: y T b c T x Corolar: Dacă (P) este nelimitat, atunci (D) este de nerezolvat. Petra Mutzel Alg. & Date. WS 08/09 22
23 Dualitatea programării liniare Programul primar (P): Programul dual (D): Teorema puternică a dualității: Fie x * un punct permis pentru (P) și y * permis pentru (D). Apoi: y * T b = c T x * ambele soluții x * și y * sunt optime Detalii: mai târziu în prelegerea Petra Mutzel Alg. & Dat. WS 08/09 23
24 3.2 Algoritmul Simplex În practică, programele liniare sunt rezolvate folosind algoritmul Simplex [Dantzig 1955]. Max 3x 1 + 2x 2 + 2x 3 Sub rezerva 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 Vizualizarea algoritmului simplex Max z = 3x 1 + 2x 2 + 2x 3 x 3 (0,0,8) (0,6,8) Optim! (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
26 Algoritm Simplex Dat: LP cu poliedru soluție P (1) Găsiți un colț arbitrar (colț inițial) v al lui P. (2) Dacă nu există nici o margine de îmbunătățire incidentă la v oprire: v este optim. (3) Secvența oricărei margini de îmbunătățire e a v. Dacă e este nelimitat, adică stop nu are alt punct final: LP este nelimitat. (4) Fie u celălalt punct final al lui e. Setați v = u. Accesați (2)
27 Întrebări deschise despre algoritmul simplex Cum găsiți un colț v inițial al lui P? Pentru LP-urile admisibile în formă standard cu a ij și bi non-negative, originea (punctul 0) este întotdeauna un nod al lui P. În caz contrar, se folosește preprocesarea (faza 1), care poate începe la o intersecție în afara lui P și prin pași de schimb de bază similari aleargă într-un colț din P. Cum se salvează poliedrul? Sistemul de ecuații descris de restricții este salvat sub forma unui tablou. În fiecare pas simplex tabloul se schimbă și marginile de ieșire ale colțului curent pot fi calculate din tablou. Testați dacă colțul actual este optim? Dacă nu, ce margine de îmbunătățire alegeți? Se termină algoritmul? s. Prelegere: la fel
28 Definiții Să se dea un sistem de ecuații Ax = b cu A R m n, m. 29 Definiții Dacă A B este regulat (= inversabil), A B se numește matricea de bază sau baza lui A și B se numește vectorul indexului de bază sau baza lui A; analog cu A N, N vector non-bază index. Vectorul x R n cu x N = 0, x B = AB -1 b se numește soluția de bază a lui Ax = b la baza A B. Dacă AB este o bază, variabilele se numesc xj, j B, variabile de bază și xj, j N Variabile non-de bază. Dacă A B este baza și se aplică A B -1 b 0, atunci A B, B și soluția de bază corespunzătoare x sunt numite admisibile, altfel nepermise. O soluție de bază fezabilă x pentru baza A B se numește nedegenerată dacă (x B) i = (A B -1 b) i> 0 pentru tot i B, altfel degenerează.
30 Schema de ecuații Simplex și tabloul Simplex max c T x s.t. Ax = 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 Valoarea funcției obiective: 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 Schema de ecuație simplă: 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 Schema de ecuație Simplex și Tabloul Simplex Schema de ecuație Simplex: x B = AB 1 b AB 1 AN x N z = c BTAB 1 b + (c NT c BTAB 1 AN) x N Valoarea funcției țintă Tabel Simplex: valorile variabilelor de bază - c BTAB 1 b AB 1 bc NT c BTAB 1 ANAB 1 AN costuri reduse
32 Schema de ecuație Simplex și teorema Simplex Tableau: Fie A B o bază fezabilă cu soluția de bază x, A = A 1 B A N, b = A 1 B b și c T = c T N c T B A 1 B A N costurile reduse. (a) Dacă c T x 0, atunci x este optim (b) Fie q s N cu c s> 0. (b1) Dacă A s 0, atunci c T x pe P = (A, b): = nelimitat. (b2) Dacă A S 0, atunci să fie λ 0 = min b i i = 1,2. m, a este> 0 a este și r < 1,2. m>astfel încât b r = λ 0, a rs> 0 a rs apoi A B cu B = (p 1. p r-1, q s, p r + 1. p m) este o bază fezabilă cu soluția de bază x și c T x c T x. (b3) Dacă se aplică cerințele de la (b2) și A B nu este degenerat, atunci se aplică c T x> c T x. Dovadă: următorul exemplu VO Di, s. tabla de scris