A szimplex módszer variánsai és fejlesztései - Mathepedia

A forgó elem kiválasztása

a forgóoszlop pozitív csökkentett költségekkel rendelkezik, és
a forgásvonal ismét egy megengedett alapmegoldáshoz vezet.

Oszlop kiválasztása

Válassza ki az első megfelelő oszlopot. Ez a legegyszerűbb változat, de gyakran nagyszámú ismétléshez vezet, ezért a gyakorlatban nem használják.
Az eredetileg Dantzig által javasolt módszer a legnagyobb csökkentett költségértékű oszlopok egyikét választja. Ez a változat sok változóval rengeteg számítási időt vehet igénybe.
A legmeredekebb árképzés oszlop- és sorválasztás kombinációja, amelyek együttesen hozzák a legnagyobb haladást a célfüggvényhez. Ez a változat nagyon összetett minden egyes iterációban, de gyakran kevés ismétléshez vezet.
A devex árképzés Paula Harris által 1974 - ben javasolt legmeredekebb árképzés és a mai LP megoldók egyik szokásos eljárása. A mátrix oszlopait és a csökkentett költségeket a kiválasztás előtt egységes szintre méretezzük a csökkentett költségek tájékoztató értékének növelése érdekében.
A részleges árképzés felosztja a változók halmazát blokkokra, és az előző módszerek egyikét alkalmazza egy blokkra. A következő blokkot csak akkor vesszük figyelembe, ha nincs megfelelő változó.
A többszörös árképzés egyszer megkeresi a megfelelő változók halmazát, amelyeket aztán előnyösen jelöltnek tekintenek a következő iterációkban. Csak akkor vesszük figyelembe a többi változót, ha egyik jelölt egyikének sincs pozitívan csökkent költsége.
A részleges többszörös árképzés az utolsó két változat kombinációja, amely mindig csak az összes rendelkezésre álló változó egy részéből határoz meg új jelölteket. Ez a stratégia a következő devex árképzés ma a szokásos stratégiákhoz.
A hibrid árképzés több stratégiát alkalmaznak felváltva a helyzettől függően. Egyes LP megoldók numerikus kritériumokat is alkalmaznak az oszlopok kiválasztásakor, hogy korlátozzák a kerekítési hibák okozta problémákat.

Vonalválasztás

Válassza ki az első megfelelő sort. Bár ez a változat nagyon gyors iterációnként, gyakran sok ismétléshez vezet, és számszerűen instabil.
A lexikográfiai kiválasztási szabály kiválasztja az összes lehetséges sor közül a (egyértelmű) lexikográfiailag legkisebb sort. Ez a szabály a sebesség szempontjából nem különösebben jó, de megakadályozza a táblák többszöri felkeresését és az algoritmus kerékpározását. Emiatt például néhány iterációnál el lehet térni az alapmegoldástól, mielőtt visszaváltanának más kiválasztási módszerekre.
Azt, amelyet Paula Harris javasolt 1973-ban Harris hányados teszt, amely ma a szokásos eljárások egyike, lehetővé teszi, hogy az új megoldás kissé elfogadhatatlan legyen numerikus stabilitás miatt.

Változtatható határok

Kettős szimplex módszer

A vágási sík módszerek vagy az elágazás és vágás módszerek során egy változó határértéket nagyon gyakran megváltoztatnak egy éppen megoldott LP-ben, vagy hozzáadnak egy egyenlőtlenséget, amelyet a régi megoldás nem elégít ki, majd az LP újra megoldódik. Mivel a régi alapmegoldás már nem megengedett, a primál szimplex tábla egyik alapfeltételét megsértették, így az új LP megoldásához újra kell indítani a primál szimplex módszert. Ha a célfüggvényben semmi sem változott, akkor a régi kettős megoldás továbbra is megengedett, így a régi kiindulási alaptól számított néhány kettős szimplex lépéssel néhány modellezés után általában megtalálható a módosított LP optimális megoldása. Nagy LP-k esetén ez a különbség gyakran nagyon egyértelműen tükröződik a teljes futási időben.
Ha numerikus nehézségek merülnek fel az algoritmus során, vagy nagyon hosszú ideig nincs előrelépés a célfüggvényben, akkor hasznos lehet ideiglenesen engedélyezni a változó határok enyhe megsértését annak érdekében, hogy kimozdulhassunk a politop kritikus sarkából. Ezt aztán néhány kettős szimplex lépéssel orvosolni lehet.
Ha a lineáris programnak vannak bizonyos struktúrái, akkor közvetlenül meghatározhat egy elsődlegesen megengedhetetlen, de kettős megengedett kiindulási alapot anélkül, hogy azt ki kellene számolnia. Ilyen esetben a II. Fázist kettős szimplex lépéssel indíthatja el közvetlenül erről az alapról, és megmentheti magát az I. fázissal.

Felülvizsgált szimplex módszer

LR lebontások

Előfeldolgozás

Ha egy vonal lineárisan függ más vonalaktól, akkor felesleges és eltávolítható. Azon eltekintve azonban, hogy egy vonal egy másik vonal skaláris többszöröse, ezt ésszerű erőfeszítésekkel általában nehéz felismerni.
Nagyon gyakran a változók egy bizonyos értéktartományra korlátozódnak a feltételek miatt, vagy más változók adják meg őket. Például az x 1 + x 2 = 1 x_ + x_ = 1 x 1 + x 2 = 1 egyenlet és a nemnegativitási feltételek mindkét változót a [0, 1] [0,1] [0, 1] tartományra korlátozzák. . Ennek a határnak az ismerete felgyorsíthatja a megoldás folyamatát. Ezenkívül az x 2 x_ x 2 értékét az x 1 x_ x 1 értéke határozza meg. Ez azt jelenti, hogy minden olyan körülmények között, ahol x 2 x_ x 2 előfordul, ezt a változót 1 - x 1 1 - x_ 1 - x 1 helyettesítheti, és x 2 x_ x 2 eltávolítható az LP-ből.
Ha egy bizonyos értéktartományhoz több változó van rögzítve, akkor lehetséges, hogy egyes egyenlőtlenségek mindig teljesülnek, vagy már nem teljesíthetők. Az első esetben az egyenlőtlenség megszüntethető, a második esetben az LP elfogadhatatlansága azonnal megmutatkozik, és le lehet állni.

futási idő

sztori

A jó Isten megalkotta az egész számokat, minden más emberi munka.