Köpeny. 4.2: Simplex algoritmus
Köpeny. 4.: Simplex algoritmus professzor Dr. Petra Mutzel Algoritmusmérnöki tanszék, LS Számítástechnikai Kar, TU Dortmund Irodalom ehhez a VO-hoz V. Chvatal: Lineáris programozás D. ertsimas: Lineáris programozás 4.-7. VO A&D WS 08/09 .- 6.008 Áttekintés 3. A szimplex algoritmus 4. A szimplex algoritmus Az alap árfolyam bevezetése Tableau módszer Normál szimplex Felülvizsgált szimplex módszer faktorizálással Oszlop- és sorválasztási szabályok A futásidejének elemzése A gyakorlatban a lineáris programokat a szimplex algoritmus segítségével oldják meg [Dantzig 955]. Max 3x + x + x 3 Az x + x 3 figyelembevételével 8 x + x 7 x + xx, x, x 3 0 3 4 A szimplex algoritmus megjelenítése Simplex algoritmus 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ális! x Megadva: LP a P est oldat polihedronral megegyezik egy tetszőleges P sarok v kezdeti sarokkal. Ha nincs javuló élesés a v stophoz: v optimális. 3 A v bármelyik javuló élének szekvenciája. Ha e nincs korlátozva, azaz nincs más végpont-megállója: Az LP nincs korlátozva. 4 Legyen e másik végpontja u. Set vu. Menjen az x 7,0,0 z ponthoz
anyajuh: a b b A A-ból származik, ha az r-edik oszlopot A qs-re cseréljük. Van AAF, ahol F 0 0 ā s. 0 0 ā r, s ā rs ā r +, s 0 0. ā ms 0 0 Mert: Van A s A, és ezért az A qs s-edik oszlopa egyenlő A Ā s AAA s A qs és az összes többi oszlop megmarad, mint A-ban. Árs> 0, tehát F szabályos, ezért A asis. 4 5 Továbbá x A b F A b F x F b 0 0 ās-szal. 0 0 ār, s F Tehát i-re. m: r -edik oszlop Ha ā> 0: xb pi i āis br bi āis bi 0 āis különösen az ir: xb pr r br 0 új nem alapváltozó esetén, ha ā 0: xb pi i āis br bi 0 és x br 0 qs új bázisváltozó Tehát az x egy megvalósítható bázis megoldás a bázisra. ār +, s. āms 0 0. 0 0 b3 nem degenerált eset: λ 0> 0: 6 7 szimplex algoritmus tabló módszer megengedett aszissal indul A mondat ismételt alkalmazása: a STOP, optimalitás b STOP, korlátlan alapváltozás: pivot s elforduló oszloppal és r pivot line bázisváltozók objektív függvényértékértékei - c TA b A bc NT c TAANAAN t 00 t 0. t 0n csökkentett költségek Változatok: Tableau módszer Standard szimplex Felülvizsgált módszer t 0 t. t n. t m0 t m. t mn A tabló akkor megengedett, ha t i0 0 minden i-re. A tabló akkor optimális, ha t 0j 0 minden j esetén. 3
Számítási szabályok az Á A A N alapárfolyam-számításából: A A N A F A N F A A N A N csak abban különbözik A N-től, hogy az r-edik oszlop a p r indexű változóhoz tartozik. Számítási szabályok az alapárfolyamból Az Ā újraszámításához Ā-t lényegében F-vel kell szorozni; Kivételt képez az r-edik oszlop és az s-edik sor. Ugyanez vonatkozik a b és c kiszámítására. Az ārs elemet pivot elemnek nevezzük. Ennek eredményeként a következő számítási szabályok jönnek létre: 0 ff fff megfigyelés a szimplex algoritmuson Minden egyes iterációban az egyik alapvető megoldást egy másikra cseréljük. A tábla csak egy nagyon kis részét használják az új x alapmegoldás kiszámításához: szükség van A -, bx és c, valamint A. s-edik oszlopára. Ötlet: A teljes mátrix kiszámítása helyett csak azt a részt kell kiszámítani, amelyik valóban szükség van rá, és ez a 4 szimplex módszer közvetlenül az eredeti adatok alapján került átdolgozásra
Felülvizsgált szimplex módszer 6 7 Ugyanaz, mint korábban 4, 5, N, 3, c 3, 5, 4, 0, 0, 0 x4 3 0 A, x 0, A x 5 5 4 0. Iteráció: y TA c T: y TF rx a csökkentett költségek x bekövetkezik cy T 0 0 0 0 y 0 0 c 5. Apa Ez megadja nekünk az új alap és alap megoldást: x 3 x: x4 x 5, 5 N, 4, 3 3 x: A következő érvényes: AA régi F 3 3 5 0 0 0 0 0 t 3 és x4 ki. 9. Iteráció Csökkentett költségek: 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 in t 3 és 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 Az alábbiak érvényesek: A A régi F 0 3 4 30 3 5
A tabló futási idejű összehasonlítása a felülvizsgált szimplex módszerrel Futásidejű iteráció ritkán lakott mátrixok esetében: Becslés Chvatal-uch szerint: Feltételezés: a táblák oszlopai és vonalai m/vagy n/nulla elemet tartalmaznak; K: m nulla nulla elem faktorizációs mátrixai; Eta oszlopok: kb. 5% -50% sűrű FTRAN: kb. 0m, TRAN: kb. 0m A bemeneti változók kiválasztása: A kimeneti változók kiszámítása: m Az x és a frissítése: m A felülvizsgált szimplex teljes ideje: 3m + 0n A panel módszer teljes ideje: mn/4 8