Jednostranný algoritmus - Simplex algorithm

V matematické optimalizace , Dantzig ‚s simplex algoritmus (nebo simplex metoda ) je populární algoritmus pro lineární programování .

Název algoritmu je odvozen z konceptu simplexu a navrhl ho TS Motzkin . V této metodě se ve skutečnosti nepoužívají zjednodušení, ale jedna její interpretace spočívá v tom, že funguje na zjednodušovacích kuželech , a ty se stávají vlastními zjednodušeními s dalším omezením. Zjednodušenými kužely, o které jde, jsou rohy (tj. Sousedství vrcholů) geometrického objektu nazývaného polytop . Tvar tohoto mnohostěnu je definován omezeními použitými 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 roce 1946 ho jeho kolega vyzval, aby mechanizoval proces plánování, aby ho odvrátil od nástupu do jiné práce. Dantzig formuloval problém jako lineární nerovnosti inspirované dílem Wassily Leontief , nicméně v té době nezahrnoval jako součást své formulace 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 „základní pravidla“ specifikovaná armádou, která popisují, jak lze cílů dosáhnout, na rozdíl od upřesnění cíle samotného. Dantzigovým základním vhledem bylo uvědomit si, že většinu takových základních pravidel lze přeložit do lineární objektivní funkce, kterou je třeba maximalizovat. Vývoj simplexové metody byl evoluční a trval zhruba rok.

Poté, co Dantzig zahrnul objektivní funkci jako součást své formulace v polovině roku 1947, byl problém matematicky lépe řešitelný. Dantzig si uvědomil, že jeden z nevyřešených problémů, které si spletl jako domácí úkol ve třídě svého profesora Jerzyho Neymana (a ve skutečnosti byl později vyřešen), byl použitelný při hledání algoritmu pro lineární programy. Tento problém zahrnoval nalezení existence Lagrangeových multiplikátorů pro obecné lineární programy na kontinuu proměnných, z nichž každá byla mezi nulou a jednou, a uspokojení lineárních omezení vyjádřených formou Lebesgueových integrálů . Dantzig později publikoval své „domácí úkoly“ jako tezi, aby získal doktorát. Geometrie sloupu použitá v této práci poskytla Dantzigovi vhled, díky kterému věřil, že metoda Simplex bude velmi účinná.

Přehled

Soustava lineárních nerovnic definuje polytop jako proveditelné oblasti. Algoritmus simplex začíná na počátečním vrcholu a pohybuje se podél okrajů mnohostěnu, dokud nedosáhne vrcholu optimálního řešení.
Mnohostěn simplexového algoritmu ve 3D

Algoritmus simplex pracuje na lineárních programech v kanonické formě

maximalizovat
podléhá a

s koeficienty objektivní funkce, je matice transponovaná a jsou proměnné problému, je matice p × n a . Existuje přímočarý proces převodu libovolného lineárního programu na jeden ve standardní formě, takže použití této formy lineárních programů nevede ke ztrátě obecnosti.

V geometrických termínech je proveditelná oblast definována všemi hodnotami tak, že a je (možná neomezeným) konvexním polytopem . Extrémní bod nebo vrchol tohoto mnohostěnu je znám jako základní proveditelné řešení (BFS).

Lze ukázat, že pro lineární program ve standardní formě, pokud má objektivní funkce maximální hodnotu v proveditelné oblasti, pak má tuto hodnotu (alespoň) v jednom z extrémních bodů. To samo o sobě redukuje problém na konečný výpočet, protože existuje konečný počet extrémních bodů, ale počet extrémních bodů je pro všechny kromě nejmenších lineárních programů nezvladatelně velký.

Lze také ukázat, že pokud extrémní bod není maximálním bodem objektivní funkce, pak existuje hrana obsahující bod, takže hodnota objektivní funkce se na hraně vzdalující se od bodu přísně zvyšuje. Pokud je hrana konečná, spojí se hrana s jiným extrémním bodem, kde má objektivní funkce větší hodnotu, jinak je objektivní funkce na okraji bez ohraničení a lineární program nemá řešení. Algoritmus simplex tento pohled aplikuje chůzí po okrajích mnohostěnu do extrémních bodů s většími a většími objektivními hodnotami. Toto pokračuje, dokud není dosaženo maximální hodnoty, nebo dokud není navštíven neomezený okraj (se závěrem, ž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 (jako u objektivní funkce), doufáme, že počet navštívených vrcholů bude malý.

Řešení lineárního programu se provádí ve dvou krocích. V prvním kroku, známém jako fáze I, je nalezen výchozí extrémní bod. V závislosti na povaze programu to může být triviální, ale obecně to lze vyřešit aplikací simplexové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 lineární program nazývá neproveditelný . Ve druhém kroku, Fáze II, je simplexový algoritmus aplikován s použitím základního proveditelného řešení nalezeného ve fázi I jako výchozího bodu. Možné výsledky z fáze II jsou buď optimálním základním proveditelným řešením, nebo nekonečným okrajem, na kterém je objektivní funkce výše neomezená.

Standardní forma

Transformaci lineárního programu na jeden ve standardní formě lze provést následujícím způsobem. Nejprve je pro každou proměnnou s dolní hranicí jinou než 0 zavedena nová proměnná představující rozdíl mezi proměnnou a vázanou. Původní proměnnou pak lze eliminovat substitucí. Například vzhledem k omezení

nová proměnná , je představena pomocí

Druhou rovnici lze použít k vyloučení z lineárního programu. Tímto způsobem lze všechna omezení dolní hranice změnit na omezení bez negativity.

Za druhé, pro každé zbývající omezení nerovnosti je zavedena nová proměnná, nazývaná proměnná vůle , aby se toto omezení změnilo na omezení rovnosti. Tato proměnná představuje rozdíl mezi oběma stranami nerovnosti a předpokládá se, že není záporná. Například nerovnosti

jsou nahrazeny

Je mnohem jednodušší provádět algebraické manipulace s nerovnostmi v této formě. U nerovností, kde se objevuje ≥ jako u druhého, někteří autoři označují proměnnou zavedenou jako apřebytečná proměnná .

Za třetí, každá neomezená proměnná je vyřazena z lineárního programu. To lze provést dvěma způsoby, jedním je vyřešením proměnné v jedné z rovnic, ve kterých se vyskytuje, a následným vyloučením proměnné substitucí. Druhým je nahradit proměnnou rozdílem dvou omezených proměnných. Pokud je například neomezené, napište

Rovnici lze použít k odstranění z lineárního programu.

Po dokončení tohoto procesu bude proveditelná oblast ve formuláři

Je také užitečné předpokládat, že pozice je počet řádků. To nemá za následek ztrátu obecnosti, protože jinak buď má systém nadbytečné rovnice, které lze vynechat, nebo je systém nekonzistentní a lineární program nemá řešení.

Jednostranné tablo

Lineární program ve standardní formě může být reprezentován jako tablo formuláře

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 matici identity řádu p (počet řádků v A), pak je tablo údajně v kanonické formě . Proměnné odpovídající sloupcům matice identity se nazývají základní proměnné, zatímco zbývající proměnné se nazývají nebázické nebo volné proměnné . Pokud jsou hodnoty nebázický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ý výklad je, že koeficienty lineární rovnice představované každé řadě jsou buď , nebo jiné číslo. Každý řádek bude mít sloupec s hodnotou , sloupce s koeficienty a zbývající sloupce s některými dalšími koeficienty (tyto další proměnné představují naše nebázické proměnné). Nastavením hodnot nebázických proměnných na nulu zajistíme v každém řádku, aby se hodnota proměnné reprezentované a v jejím sloupci rovnala hodnotě 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 nesingulární matici. Pokud je odpovídající tablo vynásobeno inverzí této matice, pak je výsledkem tablo v kanonické formě.

Nechat

být tablo v kanonické formě. K odebrání koeficientů lze použít další transformace přidávání řádků cT
B
 
z objektivní funkce. Tento proces se nazývá stanovení cen a jeho výsledkem je kanonické tablo

kde z B je hodnota objektivní funkce při odpovídajícím základním proveditelném řešení. Aktualizované koeficienty, známé také jako koeficienty relativních nákladů , jsou mírou změny objektivní funkce s ohledem na nezákladní proměnné.

Otočné operace

Geometrická operace přechodu ze základního proveditelného řešení do sousedního základního proveditelného řešení je implementována jako otočná operace . Nejprve je v nenulovém sloupci vybrán nenulový kontingenční prvek . Řádek obsahující tento prvek se vynásobí jeho vzájemností, aby se tento prvek změnil 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ým prvkem v řádku r se pak sloupec stane r -tým sloupcem matice identity. Proměnná pro tento sloupec je nyní základní proměnnou, která nahrazuje proměnnou, která před operací odpovídala r -tému sloupci matice identity. Ve skutečnosti proměnná odpovídající sloupci pivot vstupuje do sady základních proměnných a nazývá se zadávající proměnná a nahrazovaná proměnná opouští sadu základních proměnných a nazývá se odcházející proměnná . Tablo je stále v kanonické podobě, ale se sadou základních proměnných změněných o jeden prvek.

Algoritmus

Nechť je lineární program dán kanonickým tablo. Algoritmus simplex pokračuje prováděním po sobě jdoucích pivotní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 čep zlepšil řešení.

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

Protože se zadaná proměnná obecně zvýší z 0 na kladné číslo, hodnota objektivní funkce se sníží, pokud je derivace objektivní funkce vzhledem k této proměnné záporná. Ekvivalentně se hodnota funkce objektivu zvýší, pokud je pivotní sloupec vybrán tak, aby byl odpovídající záznam v řádku objektivu tabla kladný.

Pokud existuje více než jeden sloupec, takže položka v řádku cíle je kladná, pak volba, kterou přidat do sady základních proměnných, je poněkud libovolná a bylo vyvinuto několik pravidel pro výběr proměnných, jako je algoritmus Devex .

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

Změnou pravidla pro výběr proměnné zadávání tak, že vybere sloupec, kde je záznam v řádku cíle záporný, se algoritmus změní tak, aby našel maximum funkce cíle spíše než minimum.

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

Jakmile byl vybrán otočný sloupek, je výběr otočného řádku do značné míry určen požadavkem, aby bylo výsledné řešení 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 může vstupní proměnná nabývat libovolných nezáporných hodnot, přičemž řešení zůstane proveditelné. V tomto případě je objektivní funkce níže neomezená a neexistuje žádné minimum.

Dále musí být vybrána řada pivotů, aby všechny ostatní základní proměnné zůstaly kladné. Výpočet ukazuje, že k tomu dojde, když je výsledná hodnota zadané proměnné na minimu. Jinými slovy, pokud je kontingenční sloupec c , pak je otočný řádek r zvolen tak, že

je minimum ze všech r, takže a rc > 0. Tomu se říká test minimálního poměru . Pokud existuje více než jeden řádek, pro který je dosaženo minima, pak lze k určení použít pravidlo pro výběr proměnné .

Příklad

Zvažte lineární program

Minimalizovat
S výhradou

Sečtením proměnných slack s a t to reprezentuje kanonické tablo

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

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

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

Pro další krok ve skutečnosti neexistují žádné pozitivní položky v řadě cílů

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

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

Lineární program obecně nebude uveden v kanonické formě a před spuštěním simplexového algoritmu musí být nalezeno ekvivalentní kanonické tablo. Toho lze dosáhnout zavedením umělých proměnných . Sloupce matice identity jsou přidány jako sloupcové vektory pro tyto proměnné. Pokud je hodnota b pro rovnici omezení záporná, je rovnice před přidáním sloupců matice identity negována. To nemění sadu proveditelných řešení ani optimální řešení a zajišťuje, že proměnné vůle 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 k nalezení minima se použije simplexový algoritmus; upravený lineární program se nazývá problém fáze I.

Simplex algoritmus aplikovaný na problém fáze I musí končit minimální hodnotou pro novou objektivní funkci, protože jako součet nezáporných proměnných je jeho hodnota ohraničena níže 0. Pokud je minimum 0, pak umělé proměnné lze z výsledné kanonické tablo produkující kanonické tablo ekvivalentní původnímu problému. Poté lze použít simplexový algoritmus k nalezení řešení; tento krok se nazývá fáze II . Pokud je minimum kladné, pak neexistuje žádné proveditelné řešení pro problém fáze I, kde jsou všechny umělé proměnné nulové. To znamená, že proveditelná oblast původního problému je prázdná, a proto původní problém nemá řešení.

Příklad

Zvažte lineární program

Minimalizovat
S výhradou

To představuje (nekanonické) tablo

Zaveďte umělé proměnné u a v a objektivní funkci W  =  u  +  v , čímž získáte nové tablo

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

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

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

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

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

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 se hodí k okamžité implementaci, ve které je tablo udržováno jako obdélníkové ( m  + 1) -by- ( m  +  n  + 1) pole. Je snadné vyhnout se ukládání m explicitních sloupců matice identity, ke kterým dojde v tablo, protože B je podmnožinou sloupců [ AI ]. Tato implementace je označována jako „ standardní simplexový algoritmus“. Úložná a výpočetní režie je taková, že standardní simplexová metoda je neúměrně nákladný přístup k řešení velkých problémů s lineárním programováním.

V každé iteraci simplexu jsou jediným požadovaným údajem první řádek tabla, (pivotní) sloupec tabla odpovídající vstupní 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é. Obě tyčové sloupec a tyčové řádek může být vypočítán přímo pomocí řešení soustav lineárních rovnic, které zahrnují matice B a matice-vektor produktu pomocí A . Tato pozorování motivovat „ revidovaný simplex algoritmus “, pro které jsou implementace Vyznačuje se nezvratné reprezentace  B .

Při velkých problémech s lineárním programováním je A typicky řídká matice a když je výsledná řídkost B využita při zachování jeho invertibilní reprezentace, je revidovaný simplexový algoritmus mnohem efektivnější než standardní simplexová metoda. Komerční simplexová řešení jsou založena na revidovaném simplexním algoritmu.

Degenerace: zastavení a jízda na kole

Pokud jsou hodnoty všech základních proměnných přísně kladné, pak musí pivot vést ke zlepšení objektivní hodnoty. Když je tomu tak vždy, žádná sada základních proměnných se nevyskytuje dvakrát a simplexový algoritmus se musí ukončit po konečném počtu kroků. Základní proveditelná řešení, kde je alespoň jedna ze základních proměnných nulová, se nazývají degenerovaná a mohou mít za následek otočné čepy, u nichž nedochází ke zlepšení objektivní hodnoty. V tomto případě neexistuje žádná skutečná změna v řešení, ale pouze změna v sadě základních proměnných. Když se několik takových otočných čepů objeví postupně, nedojde ke zlepšení; ve velkých průmyslových aplikacích je degenerace běžná a takové „ zastavení “ je pozoruhodné. Horší než zastavení je možnost, že se stejná sada základních proměnných vyskytne dvakrát. V takovém případě deterministická pravidla otáčení simplexového algoritmu vytvoří nekonečnou smyčku neboli „cyklus“. Zatímco v praxi je degenerace pravidlem a zdržování se je běžné, jízda na kole je v praxi vzácná. V Padbergu probíhá diskuse o příkladu praktické cyklistiky . Blandovo pravidlo brání cyklování a zaručuje tak, že simplexní algoritmus vždy skončí. Další otočný algoritmus, křížový algoritmus, nikdy necykluje na lineárních programech.

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

Účinnost

Metoda simplex je v praxi pozoruhodně účinná a byla velkým zlepšením oproti dřívějším metodám, jako je Fourierova -Motzkinova eliminace . V roce 1972 však Klee a Minty uvedli příklad Klee – Mintyho kostky , který ukazuje, že nejhorší složitost simplexové metody, kterou formuloval Dantzig, je exponenciální čas . Od té doby se u téměř každé variace metody ukázalo, že existuje rodina lineárních programů, pro které funguje špatně. Je otevřenou otázkou, zda existuje variace s polynomiálním časem , přestože jsou známa pravidla subexponenciálního pivotování.

V roce 2014 bylo prokázáno, že konkrétní varianta simplexové metody je NP-silná , tj. Lze ji použít k řešení polynomického režie jakéhokoli problému v NP implicitně během provádění algoritmu. Navíc rozhodnutí, zda daná proměnná někdy zadá základ 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 oba NP-tvrdé problémy. Přibližně ve stejnou dobu bylo ukázáno, že existuje umělé kontingenční pravidlo, pro které je výpočet jeho výstupu kompletní pro PSPACE . V roce 2015 to bylo posíleno, aby se ukázalo, že výpočet výstupu Dantzigova kontingenčního pravidla je PSPACE-Complete .

Analýza a kvantifikace pozorování, že simplexní algoritmus je v praxi účinný navzdory exponenciální složitosti nejhoršího případu, vedl k vývoji dalších měřítek složitosti. Simplexový algoritmus má polynomiálně-časovou složitost průměrného případu v různých rozděleních pravděpodobnosti , přičemž přesný průměrný výkon simplexového algoritmu závisí na volbě rozdělení pravděpodobnosti pro náhodné matice . Další přístup ke studiu „ typických jevů “ využívá teorii Bairových kategorií z obecné topologie a ukazuje, že (topologicky) „většinu“ matic lze vyřešit simplexovým algoritmem v polynomiálním počtu kroků. Další metoda k analýze výkonu simplexového algoritmu studuje chování nejhorších scénářů při malé poruše-jsou scénáře nejhorších případů při malé změně stabilní (ve smyslu strukturální stability ), nebo se stanou traktovatelnými? Tato oblast výzkumu, nazývaná vyhlazená analýza , byla zavedena konkrétně ke studiu simplexové metody. Doba běhu simplexové metody na vstupu s hlukem je skutečně polynomická v počtu proměnných a velikosti poruch.

Jiné algoritmy

Další algoritmy pro řešení problémů s lineárním programováním jsou popsány v článku o lineárním programování . Dalším algoritmem otáčení na bázi výměny základů je křížový algoritmus . Existuje polynomiální algoritmy pro lineární programování, které používají metody vnitřního bodu: mezi ně patří Khachiyan ‚s eliptickou algoritmus , Karmarkar ‘ s projektivní algoritmus a sledování dráhy algoritmy .

Lineární zlomkové programování

Lineární frakční programování (LFP) je zobecněním lineárního programování (LP). V LP je objektivní funkcí lineární funkce , zatímco objektivní funkcí lineárně -zlomkového programu je poměr dvou lineárních funkcí. Jinými slovy, lineární program je zlomkový -lineární program, ve kterém je jmenovatelem konstantní funkce, která má všude hodnotu jedna. Lineárně-zlomkový program lze vyřešit variantou simplexového algoritmu nebo křížovým algoritmem .

Viz také

Poznámky

Reference

Další čtení

Tyto úvody jsou určeny studentům informatiky a operačního výzkumu :

externí odkazy