Pelerină. 4.2: Algoritm Simplex

Pelerină. 4.: Algoritm Simplex Profesor Dr. Petra Mutzel Catedra pentru Ingineria Algoritmului, LS Facultatea de Informatică, TU Dortmund Literatura pentru acest VO V. Chvatal: Linear Programming D. ertsimas: Linear Programming 4.-7. VO A&D WS 08/09 .- 6.008 Prezentare generală 3. Algoritmul Simplex 4. Algoritmul Simplex Introducerea ratei de schimb de bază Metoda tabloului Simplex standard Metoda revizuită simplex cu factorizare Reguli de selecție a coloanei și rândurilor Terminare Analiza timpului de rulare În practică, programele liniare sunt rezolvate cu ajutorul algoritmului simplex [Dantzig 955]. Max 3x + x + x 3 Sub rezerva x + x 3 8 x + x 7 x + xx, x, x 3 0 3 4 Vizualizarea algoritmului simplex Algoritmul simplex Max z 3x + x + x 3 x 3 0,0, 8 0,6,8,5,6 z 8 0,6,0 z 0,5,0 7,0, z 3 Optim! x Având în vedere: LP cu poliedru soluție P est de acord un colț arbitrar inițial colț v al lui P. Dacă nu există nici o margine de îmbunătățire incidentă la oprire v: 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. Set vu. Mergeți la x 7,0,0 z

algoritm

eweis: a b b A rezultă din A prin înlocuirea coloanei a-a cu A qs. Se aplică A A F, unde F 0 0 ā s. 0 0 ā r, s ā rs ā r +, s 0 0. ā ms 0 0 Deoarece: Avem Ā s A și, prin urmare, A qs s-th coloana AF este A Ā s AAA s A qs și toate celelalte coloane rămâneți ca în A. Acesta ține rs> 0, deci F este regulat și astfel A este un asis. 4 5 În plus, x A b F A b F x F b cu 0 0 ās. 0 0 ār, s F Deci pentru i. m: r-th column Dacă ā este> 0: xb pi i āis br bi āis bi 0 āis în special pentru ir: xb pr r br 0 nouă variabilă non-bază Dacă ā este 0: xb pi i āis br bi 0 și x br 0 qs noua variabilă de bază Deci x este o soluție de bază fezabilă la bază. ār +, s. āms 0 0. 0 0 b3 caz nedegenerat: λ 0> 0: 6 7 algoritmul simplex Metoda tabloului începe cu o asis admisibilă Aplicarea iterată a propoziției: a STOP, optimitate b STOP, schimbare nelimitată a bazei: pivot cu coloana pivot s și linia pivot r valori ale funcției obiective ale variabilelor de bază - c TA b A bc NT c TAANAAN t 00 t 0. t 0n costuri reduse Variante: Metoda tabloului Simplex standard Metoda revizuită t 0 t. t n. t m0 t m. t mn Tabloul este permis dacă t i0 0 pentru toate i. Tabloul este optim dacă t 0j 0 pentru toate j. 3

Regulile de calcul din calculul ratei de schimb de bază a lui Ā A A N: A A N A F A N F A A N A N diferă de A N doar prin faptul că coloana a r-a aparține variabilei cu indicele p r. Reguli de calcul de la rata de schimb de bază Pentru a recalcula Ā, Ā trebuie în esență înmulțit cu F; Excepție fac coloana a-a și rândul a. Același lucru este valabil și pentru calculul lui b și c. Elementul ārs este numit element pivot. Acest lucru are ca rezultat următoarele reguli de calcul: 0 ff fff Observații asupra algoritmului Simplex În fiecare iterație, o soluție de bază este înlocuită cu alta. Doar o parte foarte mică a tabloului este utilizată pentru a calcula noua soluție de bază x: aveți nevoie de A -, bx și c, precum și a s-a coloană a lui A. Ideea: În loc să calculați întreaga matrice de fiecare dată, calculați doar partea care este într-adevăr necesar, iar această metodă simplex 4 revizuită direct din datele originale

Metoda simplex revizuită 6 7 La fel ca înainte cu 4, 5, N, 3, c 3, 5, 4, 0, 0, 0 x4 3 0 A, x 0, A x 5 5 4 0. Iterare: y TA c T: y TF rx sunt costurile reduse x apare cy T 0 0 0 0 y 0 0 c 5. O tată Aceasta ne oferă noua soluție de bază și de bază: x 3 x: x4 x 5, 5 N, 4, 3 3 x: Se aplică următoarele: AA vechi F 3 3 5 0 0 0 0 0 t 3 și x4 afară. 9. Iterare Costuri reduse: y T 0 5 5, 0 y 0 x: 3 5, 0 0 x 4: 0 5, 0 5 0 0 x 3: 4 5, 0 3 4 x 3 în t 3 și x 5 out . A d a: x 3 3 x: 0 d d 4 3 x x 5 3 7 6 3 3 0, 3, N, 4, 5 7 6 x: 3 0 Se aplică următoarele: A A vechi F 0 3 4 30 3 5

Compararea timpului de execuție a tabloului și a metodei simplex revizuite Timpul de execuție pe iterație pentru matricele slab populate: Estimarea în funcție de Chvatal-uch: Presupunere: coloanele și liniile tabloului conțin elemente m/sau n/non-zero Matrici de factorizare a k: m elemente nenule; Coloane Eta: aproximativ 5% -50% dens FTRAN: aproximativ 0m, TRAN: aproximativ 0m Selecția variabilelor de intrare: Calculul variabilelor de ieșire: m Actualizarea lui x și: m Timp total revizuit simplex: 3m + 0n timp total Metoda tabloului: mn/4 8