Varianty a vylepšenia simplexovej metódy

Výber otočného prvku

otočný stĺpec má kladné zníženie nákladov a
otočná čiara vedie opäť k prípustnému základnému riešeniu.

Výber stĺpca

Vyberte prvý vhodný stĺpec. Toto je najjednoduchší variant, ktorý však často vedie k veľkému počtu iterácií, a preto sa v praxi nepoužíva.
Metóda pôvodne navrhnutá Dantzigom vyberá jeden zo stĺpcov s najväčšou hodnotou znížených nákladov. Tento variant môže trvať veľa času na výpočet s mnohými premennými.
The najstrmšie ceny je kombináciou výberu stĺpcov a riadkov, ktoré spoločne prinášajú najväčší pokrok v objektívnej funkcii. Tento variant je v každej iterácii veľmi zložitý, ale často vedie k niekoľkým iteráciám.
The tvorba cien devex je aproximácia jazyka. navrhnutá Paulou Harrisovou v roku 1974 najstrmšie ceny a jeden zo štandardných postupov v dnešných riešeniach LP. Stĺpce matice a znížené náklady sú pred výberom zmenšené na jednotný štandard, aby sa zvýšila informatívna hodnota znížených nákladov.
Na čiastočné ceny rozdelí množinu premenných na bloky a na blok použije jednu z predchádzajúcich metód. O ďalšom bloku sa uvažuje, iba ak sa nenájde vhodná premenná.
The viacnásobné ceny raz hľadá množinu vhodných premenných, ktoré sa potom v ďalších iteráciách prednostne považujú za kandidátov. O ďalších premenných sa uvažuje, až keď žiadny z týchto kandidátov nemá kladné zníženie nákladov.
The čiastočné viacnásobné oceňovanie je kombináciou posledných dvoch variantov, ktorá iba niekedy určuje nových kandidátov z časti všetkých dostupných premenných. Táto stratégia patrí ďalej tvorba cien devex dnes k štandardným stratégiám.
Na hybridné ceny niekoľko stratégií sa používa striedavo v závislosti od situácie. Niektorí riešitelia LP používajú pri výbere stĺpcov aj numerické kritériá, aby obmedzili problémy spôsobené chybami zaokrúhľovania.

Výber riadku

Vyberte prvý vhodný riadok. Aj keď je tento variant na iteráciu veľmi rýchly, často vedie k mnohým iteráciám a je numericky nestabilný.
The lexikografické pravidlo výberu vyberie (jednoznačne) lexikograficky najmenší riadok zo všetkých možných riadkov. Toto pravidlo nie je z hľadiska rýchlosti nijako zvlášť dobré, ale bráni tomu, aby boli tabuľky opakovane navštívené a algoritmus nebol cyklovaný. Z tohto dôvodu ho možno použiť na niekoľko iterácií, napríklad na prekonanie základného riešenia pred prechodom späť na iné metódy výberu.
Ten, ktorý navrhla Paula Harris v roku 1973 Harrisov kvocient testu, ktorý je dnes jedným zo štandardných postupov, umožňuje nové riešenie byť mierne neprípustným z dôvodu numerickej stability.

Variabilné hranice

Duálne simplexné metódy

V priebehu metód rezania roviny alebo metód vetvenia a rezania sa variabilná hranica veľmi často mení v LP, ktorý bol práve vyriešený, alebo je pridaná nerovnosť, ktorá nie je uspokojená starým riešením, a LP je potom vyriešený znova. Pretože staré základné riešenie už nie je prípustné, bola porušená jedna zo základných podmienok tabuľky primal simplex, takže je potrebné reštartovať metódu primal simplex, aby sa vyriešil nový LP. Pokiaľ sa v cieľovej funkcii nič nezmenilo, staré duálne riešenie je stále prípustné, takže s niekoľkými duálnymi simplexnými krokmi zo starého východiskového základu sa optimálne riešenie pre modifikovanú LP zvyčajne nájde po niekoľkých iteráciách. Pri veľkých LP sa tento rozdiel často veľmi zreteľne odráža v celkovej dobe chodu.
Ak v priebehu algoritmu nastanú početné ťažkosti alebo ak v objektívnej funkcii veľmi dlho nedôjde k žiadnemu pokroku, môže byť užitočné dočasne povoliť mierne narušenie variabilných hraníc, aby ste sa dostali z kritického rohu polytopu. To je potom možné napraviť pomocou niekoľkých dvojitých simplexných krokov.
Ak má lineárny program určité štruktúry, môžete priamo určiť primárne neprípustný, ale duálne prípustný východiskový základ bez toho, aby ste ho museli vypočítať. V takom prípade môžete začať fázu II dvojitým simplexným krokom priamo z tejto základne a fázu I si môžete uložiť.

Revidovaná simplexná metóda

LR rozklady

Predbežné spracovanie

Ak je čiara lineárne závislá od iných čiar, je nadbytočná a dá sa odstrániť. Avšak okrem špeciálneho prípadu, že čiara je skalárnym násobkom inej čiary, je to pri primeranom úsilí všeobecne ťažké odhaliť.
Premenné sú veľmi často obmedzené na určitý rozsah hodnôt v dôsledku podmienok alebo špecifikované inými premennými. Napríklad rovnica x 1 + x 2 = 1 x_ + x_ = 1 x 1 + x 2 = 1 a podmienky nezápornosti obmedzujú obe premenné na rozsah [0, 1] [0,1] [0, 1] . Poznanie tohto limitu môže urýchliť proces riešenia. Okrem toho je hodnota x 2 x_ x 2 určená hodnotou x 1 x_ x 1. To znamená, že za každých podmienok, v ktorých sa vyskytujú x 2 x_ x 2, je možné túto premennú nahradiť 1 - x 1 1 - x_ 1 - x 1 a x 2 x_ x 2 je možné z LP odstrániť.
Ak bolo niekoľko premenných fixovaných na určitý rozsah hodnôt, je možné, že niektoré nerovnosti sú vždy splnené alebo už nemôžu byť splnené. V prvom prípade je možné nerovnosť odstrániť, v druhom prípade sa okamžite prejaví neprípustnosť LP a možno sa zastaviť.

doba chodu

príbeh

Boh stvoril celé čísla, všetko ostatné je ľudská práca.