Simplexní algoritmus - Simplex algorithm

v matematická optimalizace, Dantzig je simplexní algoritmus (nebo simplexní metoda) je populární algoritmus pro lineární programování.^[1]

Název algoritmu je odvozen z konceptu a simplexní a navrhl T. S. Motzkin.^[2] Simplice se ve skutečnosti nepoužívají v metodě, ale jednou z jejích interpretací je to, že funguje na simpliciálu šišky, a tyto se stávají správnými jednoduchostmi s dalším omezením.^[3][4][5][6] Jedná se o zjednodušené kužele, které jsou rohy (tj. Sousedství vrcholů) geometrického objektu zvaného a polytop. Tvar tohoto mnohostěnu je definován znakem omezení aplikován na objektivní funkci.

Dějiny

George Dantzig pracoval na metodách plánování pro americké vojenské letectvo během druhé světové války pomocí stolní kalkulačky. V průběhu roku 1946 ho jeho kolega vyzval, aby mechanizoval proces plánování, aby ho odvrátil od přijetí jiné práce. Dantzig formuloval problém jako lineární nerovnosti inspirované prací Vasilij Leontief v té době však do své formulace nezahrnul cíl. Bez cíle může být proveditelné obrovské množství řešení, a proto k nalezení „nejlepšího“ proveditelného řešení je třeba použít vojensky specifikovaná „základní pravidla“, která popisují, jak lze dosáhnout cílů, na rozdíl od samotného určení cíle. Dantzigovým základním poznatkem bylo uvědomit si, že většinu takových základních pravidel lze převést na lineární objektivní funkci, kterou je třeba maximalizovat.^[7] Vývoj simplexové metody byl evoluční a probíhal přibližně po dobu jednoho roku.^[8]

Poté, co Dantzig v polovině roku 1947 zahrnul do své formulace objektivní funkci, byl problém matematicky přijatelnější. Dantzig si uvědomil, že jedním z nevyřešených problémů je to spletl se jako domácí úkol u svého profesora Jerzy Neyman Třída (a ve skutečnosti později vyřešena), byla použitelná pro nalezení algoritmu pro lineární programy. Tento problém zahrnoval zjištění existence Lagrangeovy multiplikátory pro obecné lineární programy přes kontinuum proměnných, z nichž každá je ohraničena mezi nulou a jednou, a splňující lineární omezení vyjádřená ve formě Lebesgueovy integrály. Dantzig později publikoval své „domácí úkoly“ jako diplomovou práci, aby získal doktorát. Geometrie sloupu použitá v této práci poskytla Dantzigovi pohled, díky němuž věřil, že metoda Simplex bude velmi efektivní.^[9]

Přehled

A soustava lineárních nerovností definuje a polytop jako proveditelný region. Simplexový algoritmus začíná na začátku vrchol a pohybuje se po okrajích mnohostěnu, dokud nedosáhne vrcholu optimálního řešení.

Mnohostěn simplexního algoritmu ve 3D

Simplex algoritmus pracuje na lineárních programech v kanonická forma

maximalizovat ${ textstyle mathbf {c ^ {T}} mathbf {x}}$

podléhá ${ displaystyle A mathbf {x} leq mathbf {b}}$ a ${ displaystyle mathbf {x} geq 0}$

s ${ displaystyle mathbf {c} = (c_ {1}, , tečky, , c_ {n})}$ koeficienty objektivní funkce, ${ displaystyle ( cdot) ^ { mathrm {T}}}$ je maticová transpozice, a ${ displaystyle mathbf {x} = (x_ {1}, , tečky, , x_ {n})}$ jsou proměnné problému, ${ displaystyle A}$ je p × n matice a ${ displaystyle mathbf {b} = (b_ {1}, , tečky, , b_ {p})}$ jsou nezáporné konstanty (${ displaystyle forall j, b_ {j} geq 0 }$). Existuje přímý proces převodu libovolného lineárního programu do jednoho ve standardní formě, takže použití této formy lineárních programů nevede ke ztrátě obecnosti.

Z geometrického hlediska proveditelný region definované všemi hodnotami ${ displaystyle mathbf {x}}$ takhle ${ textstyle A mathbf {x} leq mathbf {b}}$ a ${ displaystyle forall já, x_ {i} geq 0}$ je (možná neomezený) konvexní mnohostěn. Extrémní bod nebo vrchol tohoto mnohostoru je známý jako základní proveditelné řešení (BFS).

Je možné ukázat, že u lineárního programu ve standardní formě, pokud má objektivní funkce maximální hodnotu na proveditelné oblasti, má tuto hodnotu na (alespoň) jednom z krajních bodů.^[10] To samo o sobě snižuje problém na konečný výpočet, protože existuje konečný počet krajních bodů, ale počet krajních bodů je nespravedlivě velký pro všechny kromě nejmenších lineárních programů.^[11]

Lze také ukázat, že pokud extrémní bod není maximálním bodem objektivní funkce, pak existuje hrana obsahující bod, takže objektivní funkce se přísně zvyšuje na hraně pohybující se od bodu.^[12] Pokud je hrana konečná, pak se hrana připojí k jinému krajnímu bodu, kde má objektivní funkce větší hodnotu, jinak je objektivní funkce neohraničená výše na hraně a lineární program nemá řešení. Simplexový algoritmus aplikuje tento pohled procházením podél hran polytopu do extrémních bodů se stále většími objektivními hodnotami. To pokračuje, dokud není dosaženo maximální hodnoty nebo je navštívena neomezená hrana (k závěru, že problém nemá řešení). Algoritmus vždy končí, protože počet vrcholů v mnohostěnu je konečný; navíc, protože skáčeme mezi vrcholy vždy ve stejném směru (směr objektivní funkce), doufáme, že počet navštívených vrcholů bude malý.^[12]

Řešení lineárního programu je provedeno ve dvou krocích. V prvním kroku, známém jako Fáze I, je nalezen počáteční extrémní bod. V závislosti na povaze programu to může být triviální, ale obecně to lze vyřešit použitím simplexního algoritmu na upravenou verzi původního programu. Možné výsledky fáze I spočívají buď v nalezení základního proveditelného řešení, nebo v tom, že proveditelná oblast je prázdná. V druhém případě se volá lineární program nemožné. Ve druhém kroku, fázi II, je použit simplexní algoritmus, který jako výchozí bod používá základní proveditelné řešení nalezené ve fázi I. Možné výsledky z Fáze II jsou buď optimální základní proveditelné řešení, nebo nekonečná hrana, na které je výše objektivní funkce neomezená.^[13][14][15]

Standardní forma

Transformaci lineárního programu na program ve standardní formě lze provést následujícím způsobem.^[16] Nejprve se pro každou proměnnou se spodní mezí jinou než 0 zavádí nová proměnná představující rozdíl mezi proměnnou a mezí. Původní proměnnou lze poté eliminovat substitucí. Například vzhledem k omezení

${ displaystyle x_ {1} geq 5}$

nová proměnná, ${ displaystyle y_ {1}}$, je představen s

${ displaystyle { begin {aligned} y_ {1} = x_ {1} -5 x_ {1} = y_ {1} +5 end {aligned}}}$

Druhá rovnice může být použita k eliminaci ${ displaystyle x_ {1}}$ z lineárního programu. Tímto způsobem mohou být všechna omezení dolní hranice změněna na nezáporná omezení.

Zadruhé, pro každé zbývající omezení nerovnosti byla vytvořena nová proměnná nazvaná a volná proměnná, je zaveden pro změnu omezení na omezení rovnosti. Tato proměnná představuje rozdíl mezi dvěma stranami nerovnosti a je považována za nezápornou. Například nerovnosti

${ displaystyle { begin {zarovnáno} x_ {2} + 2x_ {3} & leq 3 - x_ {4} + 3x_ {5} & geq 2 end {zarovnáno}}}$

jsou nahrazeny

${ displaystyle { begin {aligned} x_ {2} + 2x_ {3} + s_ {1} & = 3 - x_ {4} + 3x_ {5} -s_ {2} & = 2 s_ { 1}, , s_ {2} & geq 0 end {zarovnáno}}}$

Je mnohem snazší provádět algebraickou manipulaci s nerovnostmi v této podobě. U nerovností, kde se objeví ≥, jako je ta druhá, někteří autoři odkazují na proměnnou zavedenou jako a nadbytečná proměnná.

Za třetí, každá neomezená proměnná je vyloučena z lineárního programu. To lze provést dvěma způsoby, jedním z nich je řešení proměnné v jedné z rovnic, ve kterých se objeví, a následná eliminace proměnné substitucí. Druhým je nahrazení proměnné rozdílem dvou omezených proměnných. Například pokud ${ displaystyle z_ {1}}$ je neomezený, pak napište

${ displaystyle { begin {aligned} & z_ {1} = z_ {1} ^ {+} - z_ {1} ^ {-} & z_ {1} ^ {+}, , z_ {1} ^ { -} geq 0 end {zarovnáno}}}$

Rovnici lze použít k eliminaci ${ displaystyle z_ {1}}$ z lineárního programu.

Po dokončení tohoto procesu bude proveditelná oblast ve formě

${ displaystyle mathbf {A} mathbf {x} = mathbf {b}, , forall i x_ {i} geq 0}$

Je také užitečné předpokládat, že hodnost ${ displaystyle mathbf {A}}$ je počet řádků. To nemá za následek žádnou ztrátu obecnosti, protože jinak buď systém ${ displaystyle mathbf {A} mathbf {x} = mathbf {b}}$ má redundantní rovnice, které lze vynechat, nebo je systém nekonzistentní a lineární program nemá řešení.^[17]

Simplexní tablo

Lineární program ve standardní formě lze reprezentovat jako a živý obraz formuláře

${ displaystyle { begin {bmatrix} 1 & - mathbf {c} ^ {T} & 0 0 & mathbf {A} & mathbf {b} end {bmatrix}}}$

První řádek definuje objektivní funkci a zbývající řádky určují omezení. Nula v prvním sloupci představuje nulový vektor stejné dimenze jako vektor b. (Různí autoři používají různé konvence, pokud jde o přesné rozložení). Pokud lze sloupce A přeskupit tak, aby obsahovaly matice identity řádu p (počet řádků v A), pak se říká, že tablo je v kanonická forma.^[18] Proměnné odpovídající sloupcům matice identity se nazývají základní proměnné zatímco zbývající proměnné jsou volány nezákladní nebo volné proměnné. Pokud jsou hodnoty základních proměnných nastaveny na 0, pak hodnoty základních proměnných lze snadno získat jako položky v b a toto řešení je základním proveditelným řešením. Algebraická interpretace zde spočívá v tom, že koeficienty lineární rovnice představované každým řádkem jsou buď ${ displaystyle 0}$, ${ displaystyle 1}$nebo jiné číslo. Každý řádek bude mít ${ displaystyle 1}$ sloupec s hodnotou ${ displaystyle 1}$, ${ displaystyle p-1}$ sloupce s koeficienty ${ displaystyle 0}$a zbývající sloupce s některými dalšími koeficienty (tyto další proměnné představují naše jiné než základní proměnné). Nastavením hodnot základních proměnných na nulu zajistíme v každém řádku, aby hodnota proměnné představovaná a ${ displaystyle 1}$ ve svém sloupci se rovná ${ displaystyle b}$ hodnota v tomto řádku.

Naopak, vzhledem k základnímu proveditelnému řešení lze sloupce odpovídající nenulovým proměnným rozšířit na nonsingulární matici. Pokud je odpovídající tablo vynásobeno inverzí této matice, pak je výsledkem tablo v kanonické formě.^[19]

Nechat

${ displaystyle { begin {bmatrix} 1 & - mathbf {c} _ {B} ^ {T} & - mathbf {c} _ {D} ^ {T} & 0 0 & I & mathbf {D} & mathbf {b} end {bmatrix}}}$

být tablo v kanonické podobě. Další transformace přidávání řádků lze použít k odstranění koeficientů CT
B  z objektivní funkce. Tento proces se nazývá stanovení ceny a má za následek kanonické tablo

${ displaystyle { begin {bmatrix} 1 & 0 & - { bar { mathbf {c}}} _ {D} ^ {T} & z_ {B} 0 & I & mathbf {D} & mathbf {b} end {bmatrix}}}$

kde z_B je hodnota objektivní funkce u odpovídajícího základního proveditelného řešení. Aktualizované koeficienty, známé také jako relativní nákladové koeficienty, jsou rychlosti změny objektivní funkce s ohledem na základní proměnné.^[14]

Pivotní operace

Geometrická operace přechodu ze základního proveditelného řešení na sousední základní proveditelné řešení je implementována jako a otočná operace. Nejprve nenulovou otočný prvek je vybrán v základním sloupci. Řádek obsahující tento prvek je znásobeno jeho reciproční změnou tohoto prvku na 1 a poté se do ostatních řádků přidají násobky řádku, aby se ostatní položky ve sloupci změnily na 0. Výsledkem je, že pokud je otočný prvek v řádku r, pak se sloupec stane r-tý sloupec matice identity. Proměnná pro tento sloupec je nyní základní proměnnou, která nahrazuje proměnnou, která odpovídala r-tý sloupec matice identity před operací. Proměnná odpovídající kontingenčnímu sloupci ve skutečnosti vstupuje do sady základních proměnných a nazývá se zadání proměnnéa nahrazovaná proměnná opouští sadu základních proměnných a nazývá se ponechávající proměnnou. Tablo je stále v kanonické podobě, ale se sadou základních proměnných změněných o jeden prvek.^[13][14]

Algoritmus

Nechť je lineární program dán kanonickým obrazem. Simplex algoritmus pokračuje prováděním po sobě jdoucích otočných operací, z nichž každá poskytuje vylepšené základní proveditelné řešení; výběr otočného prvku v každém kroku je do značné míry určen požadavkem, aby tento otočný prvek vylepšil řešení.

Zadání výběru proměnné

Vzhledem k tomu, že se zadaná proměnná obecně zvýší z 0 na kladné číslo, hodnota objektivní funkce se sníží, pokud je derivace objektivní funkce s ohledem na tuto proměnnou záporná. Ekvivalentně se hodnota objektivní funkce sníží, pokud je vybrán kontingenční sloupec, takže odpovídající položka v řádce cíle v tabulce je kladná.

Pokud existuje více než jeden sloupec, takže položka v řádku cíle je kladná, pak je výběr, který z nich přidat do sady základních proměnných, poněkud libovolný a několik zadávání pravidel pro výběr proměnných^[20] jako Algoritmus Devex^[21] byly vyvinuty.

Pokud jsou všechny položky v řádku cíle menší nebo rovny 0, nelze provést žádnou volbu zadání proměnné a řešení je ve skutečnosti optimální. Je to snadno považováno za optimální, protože objektivní řada nyní odpovídá rovnici tvaru

${ displaystyle z ( mathbf {x}) = z_ {B} + { text {nezáporné výrazy odpovídající nezákladním proměnným}}}$

Změnou pravidla pro zadávání proměnné tak, aby vybral sloupec, kde je položka v řádku cíle záporná, se algoritmus změní tak, že najde maximum objektivní funkce spíše než minimum.

Opuštění výběru proměnné

Jakmile byl vybrán kontingenční sloupec, je výběr kontingenčního řádku do značné míry určen požadavkem, aby výsledné řešení bylo proveditelné. Nejprve se berou v úvahu pouze kladné položky v kontingenčním sloupci, protože to zaručuje, že hodnota zadané proměnné bude nezáporná. Pokud v kontingenčním sloupci nejsou žádné kladné položky, pak zadaná proměnná může mít jakoukoli nezápornou hodnotu, přičemž řešení zůstane proveditelné. V tomto případě je objektivní funkce níže neomezená a neexistuje žádné minimum.

Dále je třeba vybrat kontingenční řádek, aby všechny ostatní základní proměnné zůstaly kladné. Výpočet ukazuje, že k tomu dochází, když je výsledná hodnota zadané proměnné minimálně. Jinými slovy, pokud je kontingenční sloupec C, pak otočný řádek r je vybrán tak, aby

${ displaystyle b_ {r} / a_ {rc} ,}$

je minimum ze všech r aby A_rc > 0. Tomu se říká test minimálního poměru.^[20] Pokud existuje více než jeden řádek, pro který je dosaženo minima, pak a zrušit pravidlo volby proměnné^[22] lze použít k určení.

Příklad

Zvažte lineární program

Minimalizovat

${ displaystyle Z = -2x-3y-4z ,}$

S výhradou

${ displaystyle { begin {zarovnáno} 3x + 2y + z & leq 10 2x + 5y + 3z & leq 15 x, , y, , z & geq 0 end {zarovnáno}}}$

S přidáním uvolněných proměnných s a t, toto představuje kanonické tablo

${ displaystyle { begin {bmatrix} 1 & -2 & -3 & -4 & 0 & 0 & 0 0 & 3 & 2 & 1 & 1 & 0 & 10 0 & 2 & 5 & 3 & 0 & 1 & 15 end {bmatrix}}}$

kde sloupce 5 a 6 představují základní proměnné s a t a odpovídající základní proveditelné řešení je

${ displaystyle x = y = z = 0, , s = 10, , t = 15.}$

Sloupce 2, 3 a 4 lze vybrat jako otočné sloupce, pro tento příklad je vybrán sloupec 4. Hodnoty z výsledkem výběru řádků 2 a 3 jako kontingenčních řádků je 10/1 = 10 a 15/3 = 5. Z nich je minimum 5, takže řada 3 musí být otočnou řadou. Provedení otočení produkuje

${ displaystyle { begin {bmatrix} 3 & -2 & -11 & 0 & 0 & -4 & -60 0 & 7 & 1 & 0 & 3 & -1 & 15 0 & 2 & 5 & 3 & 0 & 1 & 15 end {bmatrix}}}$

Nyní sloupce 4 a 5 představují základní proměnné z a s a odpovídající základní proveditelné řešení je

${ displaystyle x = y = t = 0, , z = 5, , s = 5.}$

V dalším kroku ve skutečnosti nejsou žádné kladné položky v řádku cíle

${ displaystyle Z = { tfrac {-60 + 2x + 11y + 4t} {3}} = - 20 + { tfrac {2x + 11y + 4t} {3}}}$

takže minimální hodnota Z je -20.

Nalezení počátečního kanonického tabla

Obecně nebude lineární program uveden v kanonické formě a před spuštěním simplexního algoritmu je nutné najít ekvivalentní kanonické tablo. Toho lze dosáhnout zavedením umělé proměnné. Sloupce matice identity jsou přidány jako vektory sloupců pro tyto proměnné. Pokud je hodnota b pro rovnici omezení záporná, je rovnice negována před přidáním sloupců matice identity. To nemění sadu proveditelných řešení ani optimální řešení a zajišťuje, že proměnné slack budou představovat počáteční proveditelné řešení. Nové tablo je v kanonické podobě, ale není ekvivalentní původnímu problému. Zavádí se tedy nová objektivní funkce, která se rovná součtu umělých proměnných, a použije se simplexní algoritmus k nalezení minima; upravený lineární program se nazývá Fáze I problém.^[23]

Simplexový algoritmus aplikovaný na problém Fáze I musí být ukončen minimální hodnotou pro novou objektivní funkci, protože je součtem nezáporných proměnných, jeho hodnota je omezena níže 0. Pokud je minimum 0, pak umělé proměnné mohou být vyloučeny z výsledné kanonické tablo produkující kanonické tablo ekvivalentní původnímu problému. K nalezení řešení lze použít simplexní algoritmus; tento krok se nazývá Fáze II. Pokud je minimum kladné, pak neexistuje řešení pro problém fáze I, kde jsou umělé proměnné nulové. To znamená, že proveditelná oblast pro původní problém je prázdná, a proto původní problém nemá řešení.^[13][14][24]

Příklad

Zvažte lineární program

Minimalizovat

${ displaystyle Z = -2x-3y-4z ,}$

S výhradou

${ displaystyle { begin {zarovnáno} 3x + 2y + z & = 10 2x + 5y + 3z & = 15 x, , y, , z & geq 0 end {zarovnáno}}}$

To představuje (nekanonické) tablo

${ displaystyle { begin {bmatrix} 1 & 2 & 3 & 4 & 0 0 & 3 & 2 & 1 & 10 0 & 2 & 5 & 3 & 15 end {bmatrix}}}$

Představte umělé proměnné u a proti a objektivní funkce Ž = u + proti, což dává nové tablo

${ displaystyle { begin {bmatrix} 1 & 0 & 0 & 0 & 0 & -1 & -1 & 0 0 & 1 & 2 & 3 & 4 & 0 & 0 & 0 0 & 0 & 3 & 2 & 1 & 1 & 0 & 10 0 & 0 & 2 & 5 & 3 & 0 & 1 & 15 end {bmatrix}}}$

Rovnice definující původní objektivní funkci je zachována v očekávání fáze II.

Podle konstrukce, u a proti jsou obě základní proměnné, protože jsou součástí počáteční matice identity. Objektivní funkce však Ž v současné době to předpokládá u a proti jsou oba 0. Aby bylo možné upravit objektivní funkci na správnou hodnotu, kde u = 10 a proti = 15, přidejte třetí a čtvrtý řádek k prvnímu řádku

${ displaystyle { begin {bmatrix} 1 & 0 & 5 & 7 & 4 & 0 & 0 & 25 0 & 1 & 2 & 3 & 4 & 0 & 0 & 0 0 & 0 & 3 & 2 & 1 & 1 & 0 & 10 0 & 0 & 2 & 5 & 3 & 0 & 1 & 15 end {bmatrix}}}$

Vyberte sloupec 5 jako kontingenční sloupec, takže kontingenční řádek musí být řádek 4 a aktualizované tablo je

${ displaystyle { begin {bmatrix} 3 & 0 & 7 & 1 & 0 & 0 & -4 & 15 0 & 3 & -2 & -11 & 0 & 0 & -4 & -60 0 & 0 & 7 & 1 & 0 & 3 & -1 & 15 0 & 0 & 2 & 5 & 3 & 0 & 1 & 15 end {bmatrix}}}$

Nyní vyberte sloupec 3 jako kontingenční sloupec, pro který musí být řádek 3 kontingenčním řádkem

${ displaystyle { begin {bmatrix} 1 & 0 & 0 & 0 & 0 & -1 & -1 & 0 0 & 7 & 0 & -25 & 0 & 2 & -10 & -130 0 & 0 & 7 & 1 & 0 & 3 & -1 & 15 0 & 0 & 0 & 11 & 7 & -2 & 3 & 25 end {bmatrix}}}$

Umělé proměnné jsou nyní 0 a mohou být zrušeny, což dává kanonické tablo ekvivalentní původnímu problému:

${ displaystyle { begin {bmatrix} 7 & 0 & -25 & 0 & -130 0 & 7 & 1 & 0 & 15 0 & 0 & 11 & 7 & 25 end {bmatrix}}}$

To je, naštěstí, již optimální a optimální hodnota pro původní lineární program je -130/7.

Pokročilá témata

Implementace

Forma tabla použitá výše k popisu algoritmu je vhodná k okamžité implementaci, ve které je tablo udržováno jako obdélník (m + 1) -by- (m + n + 1) pole. Je jednoduché vyhnout se ukládání m explicitních sloupců matice identity, ke kterým dojde v rámci na základě B být podmnožinou sloupců [A, Já]. Tato implementace se označuje jako „Standard simplexový algoritmus ". Skladovací a výpočetní režie jsou takové, že standardní simplexní metoda je neúměrně nákladným přístupem k řešení velkých problémů lineárního programování."

V každé simplexní iteraci jsou jedinými požadovanými daty první řádek tabla, (klíčový) sloupec tabla odpovídající zadávací proměnné a pravá strana. Ten lze aktualizovat pomocí pivotního sloupce a první řádek tabla lze aktualizovat pomocí (pivotního) řádku odpovídajícího opouštějící proměnné. Pivotní sloupec i pivotní řádek lze vypočítat přímo pomocí řešení lineárních systémů rovnic zahrnujících matici B a produkt matice-vektor pomocí A. Tato pozorování motivují „revidováno simplexní algoritmus ", pro které se implementace odlišují podle jejich invertibilního zastoupeníB.^[25]

Ve velkých problémech s lineárním programováním A je obvykle a řídká matice a když výsledná řídkost B je využíván při zachování své invertibilní reprezentace, revidovaný simplexní algoritmus je mnohem efektivnější než standardní simplexní metoda. Komerční simplexní řešitelé jsou založeni na revidovaném simplexním algoritmu.^{[24][25][26][27][28]}

Degenerace: pozastavení a jízda na kole

Pokud jsou hodnoty všech základních proměnných přísně kladné, musí mít pivot za následek zlepšení objektivní hodnoty. Pokud tomu tak je vždy, žádná sada základních proměnných se neobjeví dvakrát a simplexní algoritmus musí být ukončen po konečném počtu kroků. Základní proveditelná řešení, kde alespoň jedno z základní proměnné je nula se nazývají degenerovat a může mít za následek otočné čepy, u nichž nedochází ke zlepšení objektivní hodnoty. V tomto případě nedojde k žádné skutečné změně v řešení, ale pouze ke změně v souboru základních proměnných. Pokud se několik takových otočných čepů vyskytne za sebou, nedojde k žádnému zlepšení; ve velkých průmyslových aplikacích je degenerace běžná a taková “pozastavení„Je pozoruhodné. Horší než pozastavení je možnost, že ke stejné sadě základních proměnných dojde dvakrát, v takovém případě deterministická otočná pravidla simplexního algoritmu vytvoří nekonečnou smyčku neboli„ cyklus “. Zatímco degenerace je v praxi pravidlem a pozastavení je běžné, jízda na kole je v praxi vzácná. Diskuse o příkladu praktické jízdy na kole probíhá v Padberg.^[24] Blandovo pravidlo zabraňuje cyklování a zaručuje tak, že simplexní algoritmus vždy skončí.^[24][29][30] Další otočný algoritmus, křížový algoritmus nikdy cykluje na lineárních programech.^[31]

Pivotní pravidla založená na historii, jako je Zadehovo pravidlo a Cunninghamovo pravidlo také se pokuste obejít problém zastavování a cyklování sledováním toho, jak často se konkrétní proměnné používají, a poté upřednostňujte takové proměnné, které byly používány nejméně často.

Účinnost

Metoda simplex je v praxi pozoruhodně efektivní a byla velkým zlepšením oproti dřívějším metodám, jako je Vyřazení Fourier-Motzkin. V roce 1972 však Klee a Minty^[32] uvedla příklad Klee – Minty kostka, což ukazuje, že nejhorší případ složitosti simplexové metody formulované Dantzigem je exponenciální čas. Od té doby se téměř pro každou variantu metody ukázalo, že existuje řada lineárních programů, u kterých funguje špatně. Je to otevřená otázka, pokud existuje variace s polynomiální čas, i když jsou známa subexponenciální pravidla otáčení.^[33]

V roce 2014 bylo prokázáno, že konkrétní varianta simplexové metody je NP-mocný, tj. může být použit k řešení, s polynomiální režií, jakýkoli problém v NP implicitně během provádění algoritmu. Kromě toho, rozhodování o tom, zda daná proměnná někdy vstoupí do základu během provádění algoritmu na daném vstupu, a určení počtu iterací potřebných pro řešení daného problému, jsou obojí NP-tvrdé problémy.^[34] Přibližně ve stejnou dobu se ukázalo, že existuje umělé pivotové pravidlo, pro které je výpočet jeho výstupu PSPACE - kompletní^[35]. V roce 2015 to bylo posíleno, aby se ukázalo, že výpočet výstupu Dantzigova pivotního pravidla je PSPACE - kompletní.^[36]

Analýza a kvantifikace pozorování, že simplexní algoritmus je v praxi efektivní i přes jeho exponenciální nejhorší možnou složitost, vedla k vývoji dalších měr složitosti. Simplexový algoritmus má polynomiální čas průměrná složitost pod různými rozdělení pravděpodobnosti, s přesným průměrným výkonem simplexního algoritmu v závislosti na volbě rozdělení pravděpodobnosti pro náhodné matice.^[37][38] Jiný přístup ke studiu “typické jevy "používá Teorie kategorie Baire z obecná topologie „a ukázat, že (topologicky)„ většinu “matic lze vyřešit simplexním algoritmem v polynomiálním počtu kroků.^{[Citace je zapotřebí ]} Další metoda pro analýzu výkonu simplexního algoritmu studuje chování nejhorších scénářů při malém rušení - jsou nejhorší scénáře stabilní při malé změně (ve smyslu strukturální stabilita ), nebo se stanou přitažlivými? Tato oblast výzkumu, tzv uhlazená analýza, byl představen konkrétně ke studiu simplexní metody. Ve skutečnosti je doba provozu simplexní metody na vstupu se šumem polynomická v počtu proměnných a velikosti poruch.^[39]

Další algoritmy

Další algoritmy pro řešení problémů lineárního programování jsou popsány v lineární programování článek. Dalším algoritmem otáčení základny směny je křížový algoritmus.^[40][41] Existují algoritmy polynomiálního času pro lineární programování, které používají metody vnitřních bodů: mezi ně patří Khachiyan je elipsoidní algoritmus, Karmarkar je projektivní algoritmus, a algoritmy sledování cesty.^[15]

Lineární-zlomkové programování

Lineární - zlomkové programování (LFP) je zobecněním lineární programování (LP). V LP je objektivní funkce a lineární funkce, zatímco objektivní funkce lineárně-zlomkového programu je poměr dvou lineárních funkcí. Jinými slovy, lineární program je frakčně-lineární program, ve kterém je jmenovatelem konstantní funkce, která má všude hodnotu. Lineárně-zlomkový program lze vyřešit variantou simplexního algoritmu^{[42][43][44][45]} nebo křížový algoritmus.^[46]

Viz také

Poznámky

Reference

• Murty, Katta G. (1983). Lineární programování. New York: John Wiley & Sons, Inc., str. Xix + 482. ISBN  978-0-471-09725-9. PAN  0720547.

Další čtení

Tyto úvody jsou psány pro studenty počítačová věda a operační výzkum:

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein. Úvod do algoritmů, Druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN  0-262-03293-7. Oddíl 29.3: Simplexový algoritmus, s. 790–804.
• Frederick S. Hillier a Gerald J. Lieberman: Úvod do operačního výzkumu, 8. vydání. McGraw-Hill. ISBN  0-07-123828-X
• Rardin, Ronald L. (1997). Optimalizace v operačním výzkumu. Prentice Hall. str. 919. ISBN  978-0-02-398415-0.

externí odkazy

• Úvod do lineárního programování a simplexního algoritmu autor: Spyros Reveliotis z Gruzínského technologického institutu.
• Greenberg, Harvey J., Klee – Minty Polytop ukazuje exponenciální časovou složitost Simplex metody University of Colorado v Denveru (1997) PDF ke stažení
• Simplexní metoda Výukový program pro Simplex Method s příklady (také dvoufázový a M-method).
• Matematické stoličky Simplexní kalkulačka z www.mathstools.com
• Příklad zjednodušeného postupu pro standardní problém lineárního programování Thomas McFarland z University of Wisconsin-Whitewater.
• PHPSimplex: online nástroj k řešení problémů s lineárním programováním Daniel Izquierdo a Juan José Ruiz z University of Málaga (UMA, Španělsko)
• simplex-m Online řešení Simplex