Simplexní metoda

Nezaměňovat s "simplexní metodou" - metodou pro optimalizaci libovolné funkce. Viz metoda Nelder-Mead

Simplexová metoda je algoritmus pro řešení optimalizačního problému lineárního programování výčtem vrcholů konvexního mnohostěnu ve vícerozměrném prostoru.

Podstata metody: konstrukce základních řešení, na kterých lineární funkcionál monotónně klesá, až do situace, kdy jsou splněny nezbytné podmínky lokální optimality.

V díle L. V. Kantoroviče „Matematické metody organizace a plánování výroby“ (1939) byly poprvé uvedeny principy nového oboru matematiky, který později vešel ve známost jako lineární programování. [jeden]

Historicky byl obecný problém lineárního programování poprvé nastolen v roce 1947 Georgem Bernardem Dantzigem , Marshallem Woodem a jejich spolupracovníky na ministerstvu vzdušných sil USA. V té době tato skupina zkoumala možnost využití matematických a příbuzných metod pro vojenské a plánovací problémy. Později byla v letectvu zorganizována výzkumná skupina s názvem Project SCOOP, která měla tyto myšlenky rozvíjet. První úspěšné řešení úlohy lineárního programování na počítači SEAC bylo provedeno v lednu 1952 [2] .

Popis

Problém lineárního programování je ten, že je nutné maximalizovat nebo minimalizovat nějaký lineární funkcionál na vícerozměrném prostoru za daných lineárních omezení.

Všimněte si, že každá z lineárních nerovností na proměnných ohraničuje poloviční prostor v odpovídajícím lineárním prostoru. V důsledku toho všechny nerovnosti omezují nějaký konvexní mnohostěn (možná nekonečný), nazývaný také mnohostěnný komplex . Rovnice W ( x ) = c , kde W ( x ) je maximalizovaný (nebo minimalizovaný) lineární funkcionál, generuje nadrovinu L(c) . Závislost na c generuje rodinu paralelních nadrovin. Extrémní úloha pak dostává následující formulaci: je třeba najít největší c takové, aby nadrovina L(c) protínala mnohostěn alespoň v jednom bodě. Všimněte si, že průsečík optimální nadroviny a mnohostěnu bude obsahovat alespoň jeden vrchol a bude jich více, pokud průsečík obsahuje hranu nebo k - rozměrnou plochu. Proto lze maximum funkcionálu hledat ve vrcholech mnohostěnu. Princip simplexové metody spočívá v tom, že se zvolí jeden z vrcholů mnohostěnu, načež začíná pohyb po jeho hranách od vrcholu k vrcholu ve směru zvyšování hodnoty funkcionálu. Když je přechod podél hrany z aktuálního vrcholu do jiného vrcholu s vyšší hodnotou funkcionálu nemožný, má se za to, že optimální hodnota c byla nalezena.

Posloupnost výpočtů simplexovou metodou lze rozdělit do dvou hlavních fází :

nalezení počátečního vrcholu množiny proveditelných řešení,
sekvenční přechod z jednoho vrcholu do druhého, což vede k optimalizaci hodnoty účelové funkce.

Navíc v některých případech je počáteční řešení zřejmé nebo jeho definice nevyžaduje složité výpočty, například když jsou všechna omezení reprezentována nerovnostmi ve tvaru „menší nebo rovno“ (pak je nulový vektor rozhodně proveditelné řešení , i když s největší pravděpodobností není zdaleka nejoptimálnější) . V takových problémech lze první fázi simplexové metody zcela vynechat. Simplexová metoda se dělí na jednofázovou a dvoufázovou .

Algoritmus simplexové metody

Posílené prohlášení o problému

Zvažte následující problém lineárního programování :

c^{T}x\to \max ,Ax\leqslant b,x\geqslant 0,b\geqslant 0.

Položme nyní tento problém v ekvivalentní rozšířené podobě. Je nutné maximalizovat Z , kde:

{\begin{bmatrix}1&-c^{T}&0\\0&A&E\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{ bmatrix}0\\b\end{bmatrix}},x,x_{s}\geqslant 0

Zde x jsou proměnné z původního lineárního funkcionálu, x s jsou nové proměnné, které doplňují staré tak, že nerovnost přechází v rovnost, c jsou koeficienty původního lineárního funkcionálu, Z je proměnná, která má být maximalizována. Poloprostory a průsečík tvoří mnohostěn představující množinu možných řešení. Rozdíl mezi počtem proměnných a rovnic nám udává počet stupňů volnosti. Jednoduše řečeno, vezmeme-li v úvahu vrchol mnohostěnu, pak je to počet hran, po kterých se můžeme dále pohybovat. Potom můžeme tomuto počtu proměnných přiřadit hodnotu 0 a nazývat je „nezákladní“ . V tomto případě budou zbývající proměnné vypočteny jednoznačně a budou nazývány „základní“ . Stejný soubor těchto proměnných se nazývá báze . Výsledným bodem bude vrchol v průsečíku nadrovin odpovídajících nebázickým proměnným. Aby bylo možné najít tzv. počáteční přípustné řešení (vrchol, od kterého se začneme pohybovat), všem počátečním proměnným x přiřadíme hodnotu 0 a budeme je považovat za nezákladní a všechny nové budeme považovat za základní. V tomto případě se počáteční přípustné řešení počítá jednoznačně: . $x\geqslant 0$ $x_{s}\geqslant 0$ ${\mathbf {x}}_{{si}}={\mathbf {b}}_{i}$

Algoritmus

Nyní představíme kroky algoritmu. V každém kroku změníme množiny základních a nebázických vektorů (pohybujeme se po okrajích) a matice bude vypadat takto:

{\begin{bmatrix}1&c_{B}^{T}B^{{-1}}Ac^{T}&c_{B}^{T}B^{{-1}}\\0&B^{{- 1}}A&B^{{-1}}\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{bmatrix}c_{B} ^{T}B^{{-1}}b\\B^{{-1}}b\end{bmatrix}},

kde jsou koeficienty vektoru odpovídající základním proměnným (proměnné odpovídají 0), jsou sloupce odpovídající základním proměnným. Matice tvořená zbývajícími sloupci je označena . Proč bude mít matice tento tvar, bude vysvětleno v popisu kroků algoritmu. $c_{B}$ $C$ $x_{s}$ $B$ $[{\mathbf {A}}{\mathbf {E}}]$ $D$

První krok .

Zvolíme počáteční platnou hodnotu, jak je uvedeno výše. V prvním kroku je matice identity, protože základní proměnné jsou . je ze stejných důvodů nulový vektor. $B$ $x_{s}$ $c_{B}$

Druhý krok

Ukažme, že ve výrazu mají nenulový koeficient pouze nebázické proměnné. Všimněte si, že z výrazu jsou základní proměnné jednoznačně vyjádřeny jako nebázické, protože počet základních proměnných je roven počtu rovnic. Nechť být základní a být nezákladní proměnné v dané iteraci. Rovnici lze přepsat jako . Vynásobme to vlevo: . Základní proměnné jsme tedy vyjádřili pomocí nebázických proměnných a ve výrazu ekvivalentním levé straně rovnosti mají všechny základní proměnné jednotkové koeficienty. Pokud tedy k rovnosti přidáme rovnost , pak ve výsledné rovnosti budou mít všechny základní proměnné nulový koeficient - všechny základní proměnné tvaru x se zredukují a základní proměnné tvaru x s nebudou zahrnuty do výrazu . $(c_{B}^{T}B^{{-1}}Ac^{T})x+(c_{B}^{T}B^{{-1}})x_{s}$ $Ax+x_{s}=b$ $X'$ $X''$ $Ax+x_{s}=b$ $Bx'+Dx''=b$ $B^{{-1}}$ $x'+B^{{-1}}Dx''=B^{{-1}}b$ $B^{{-1}}Ax+B^{{-1}}x_{s}$ $Zc^{T}x=0$ $c_{B}^{T}B^{{-1}}Ax+c_{B}^{T}B^{{-1}}x_{s}$ $c_{B}^{T}B^{{-1}}x_{s}$

Zvolme si hranu, po které se budeme pohybovat. Protože chceme maximalizovat Z , je nutné zvolit proměnnou, která výraz nejvíce sníží

$(c_{B}^{T}B^{{-1}}Ac^{T})x+(c_{B}^{T}B^{{-1}})x_{s}$ .

K tomu zvolíme proměnnou, která má největší záporný koeficient v modulu [3] . Pokud takové proměnné neexistují, to znamená, že všechny koeficienty tohoto výrazu jsou nezáporné, pak jsme došli k požadovanému vrcholu a našli jsme optimální řešení. V opačném případě začneme tuto nezákladní proměnnou zvyšovat, to znamená pohybovat se po hraně, která jí odpovídá. Říkejme tomu proměnný vstup .

Třetí krok

Nyní musíme porozumět tomu, která základní proměnná se dostane na nulu jako první, když se vstupní proměnná zvýší. K tomu stačí zvážit systém:

{\begin{bmatrix}B^{-1}A&B^{-1}\end{bmatrix}}{\begin{bmatrix}x\\x_{s}\end{bmatrix}}=B^{ -1}b

Pro pevné hodnoty nezákladních proměnných je systém jednoznačně řešitelný vzhledem k základním proměnným, takže můžeme určit, která ze základních proměnných bude první, která dosáhne nuly, když se vstup zvýší. Nazvěme tuto proměnnou výstup . To bude znamenat, že jsme dosáhli nového vrcholu. Nyní si prohodíme příchozí a odchozí proměnné – příchozí „vstoupí“ do základní a odchozí proměnná „opustí“ nezákladní. Nyní přepíšeme matici B a vektor c B v souladu s novými množinami základních a nebázických proměnných, poté se vrátíme ke druhému kroku. X''

Protože počet vrcholů je konečný, algoritmus jednoho dne skončí. Nalezený vrchol bude optimálním řešením.

Dvoufázová simplexová metoda

Důvody pro použití

Pokud v podmínce problému lineárního programování nejsou všechna omezení reprezentována nerovnostmi typu „≤“, pak nulový vektor nebude vždy platným řešením. Každá iterace simplexové metody je však přechodem z jednoho vrcholu do druhého, a pokud není znám žádný vrchol, nelze algoritmus vůbec spustit.

Proces nalezení počátečního vrcholu se příliš neliší od jednofázové simplexové metody, ale může být nakonec obtížnější než další optimalizace.

Úpravy omezení

Všechna omezení úlohy se upravují podle následujících pravidel:

omezení typu "≤" se převedou na rovnosti vytvořením další proměnné s koeficientem "+1". Tato úprava se provádí i v jednofázové simplexové metodě, jako výchozí základ se dále používají další proměnné.
omezení typu "≥" jsou doplněna jednou proměnnou s koeficientem " −1 ". Protože takovou proměnnou nelze v původním základu použít kvůli zápornému koeficientu, je nutné vytvořit ještě jednu pomocnou proměnnou. Pomocné proměnné jsou vždy vytvářeny s faktorem "+1".
omezení typu "=" jsou doplněna jednou pomocnou proměnnou.

Podle toho bude vytvořena řada dalších a pomocných proměnných. V počátečním základu jsou vybrány další proměnné s koeficientem "+1" a všechny pomocné. Pozor: řešení, kterému tento základ odpovídá, není přípustné.

Rozdíly mezi doplňkovými a pomocnými proměnnými

Navzdory skutečnosti, že dodatečné i pomocné proměnné jsou vytvořeny uměle a použity k vytvoření počátečního základu, jejich hodnoty v řešení jsou velmi odlišné:

další proměnné hlásí, jak "nedostatečně" je jejich odpovídající omezení. Hodnota dodatečné proměnné, rovna nule, odpovídá rovnosti hodnot pravé a levé části omezení.
pomocné proměnné říkají, jak daleko je daná podmínka od přijatelné (vzhledem k určitému omezení). Pokud je hodnota pomocné proměnné větší než nula, pak toto řešení nesplňuje určité omezení, a proto není platné.

To znamená, že nenulová hodnota doplňkové proměnné může (ale neměla by) signalizovat, že řešení není optimální . Nenulová hodnota pomocné proměnné znamená, že řešení je neplatné .

Rozhodovací fáze

Po úpravě podmínky se vytvoří pomocná účelová funkce . Pokud byly pomocné proměnné označeny jako , , pak pomocnou funkci definujeme jako $y_{i}$ $i\in \left\{1,\tečky ,k\right\}$

z'=\součet _{{i=1}}^{k}y_{i}\do min

Poté se provede běžná simplexová metoda s ohledem na pomocnou účelovou funkci. Protože všechny pomocné proměnné zvyšují hodnotu , budou v průběhu algoritmu jedna po druhé odvozovány od základu a po každém přechodu se nové řešení bude přibližovat množině proveditelných řešení. $z'$

Když je nalezena optimální hodnota funkce pomocného cíle, mohou nastat dvě situace:

optimální hodnota je větší než nula. To znamená, že alespoň jedna z pomocných proměnných zůstala v základu. V tomto případě můžeme dojít k závěru, že neexistují žádná proveditelná řešení tohoto problému lineárního programování. $z'$
optimální hodnota je nula. To znamená, že všechny pomocné proměnné byly vyjmuty ze základu a aktuální řešení je platné. $z'$

Ve druhém případě máme přípustný základ, nebo jinými slovy počáteční přípustné řešení. Je možné provádět další optimalizaci s přihlédnutím k původní účelové funkci, přičemž se nevěnuje pozornost pomocným proměnným. Toto je druhá fáze řešení.

Upravená simplexová metoda

V upravené metodě matice

${\begin{bmatrix}1&c_{B}^{T}B^{{-1}}Ac^{T}&c_{B}^{T}B^{{-1}}\\0&B^{{- 1}}A&B^{{-1}}\end{bmatrix}}$

nepřepočítává se, pouze se uloží a přepočítá matice . Zbytek algoritmu je podobný výše popsanému. $B^{{-1}}$

1. Vypočítejte duální proměnné $d=c_{B}^{T}B^{{-1}}$

2. Kontrola optimálnosti. je převeden na . $c_{B}^{T}B^{{-1}}Ac^{T}$ $d^{T}Ac^{T}$

Kontrola spočívá ve výpočtu pro všechny sloupce . Do základu lze zadat sloupec s hodnotou < 0. $d^{T}A_{n}-c_{n}$ $n\v N$

Často volte minimální hodnotu, ale k tomu musíte iterovat přes všechny sloupce.

Častěji zvolte hodnotu nižší, než je nějaká daná hodnota $-\varepsilon$

Pokud takový sloupec není nalezen, považuje se za nalezenou maximální nalezená absolutní hodnota a do základu se zanese odpovídající sloupec. $\varepsilon$ $AJ}$

3. Definice výstupu.

Nechť je vstupní sloupec odpovídající proměnné Základní plán je řešení systému Zvýšení . $AJ}$ $x_{J}$ $A_{B}p=b$ $A_{B}p+\vartheta A_{J}=b$

Vynásobte vlevo číslem , tj . $B^{{-1}}$ $B^{{-1}}A_{B}p+\vartheta B^{{-1}}A_{J}=B^{{-1}}b$

Zde je základní plán, je rozšíření vstupního sloupce, pokud jde o základ. $B^{{-1}}b$ $q=B^{{-1}}A_{J}$

Najděte maximální hodnotu , pro kterou jsou všechny hodnoty nezáporné. Pokud lze vzít libovolně velké, řešení je neomezené. V opačném případě se jeden z prvků vynuluje. Odpovídající sloupec odvodíme ze základu. $\vartheta$ $\vartheta$

4. Přepočet referenčního (základního) plánu.

Vypočítáme nový referenční plán pomocí již uvedeného vzorce s nalezenou hodnotou . $x=p+\vartheta B^{{-1}}A_{J}$ $\vartheta$

5. Přepočítáme inverzi k základu . $B^{{-1}}$

Nechť je výstupní sloupec. $B^{{-1}}A_{F}$

Matici B lze reprezentovat jako $[B_{G}A_{F}]$

kde je základní matice bez výstupního sloupce. $B_{G}$

Po změně sloupce bude základní matice vypadat takto $[B_{G}A_{J}]$

Musíme najít takovou matici $B_1$

$[B_{G},A_{J}]B_{1}^{{-1}}=E$ => => => $[B^{{-1}}B_{G}B_{1}^{{-1}},B^{{-1}}A_{J}]=B^{{-1}}$ $[B^{{-1}}B_{G},q]B_{1}^{{-1}}=B^{{-1}}$

${\begin{bmatrix}E&q'\\0&q_{f}\end{bmatrix}}B_{1}^{{-1}}=B^{{-1}}$

Kde $B_{1}^{{-1}}={\begin{bmatrix}E&-q'/q_{f}\\0&1/q_{f}\end{bmatrix}}B^{{-1}}$

Komentář.

Přepočet matice shromažďuje zaokrouhlovací chyby. Aby se předešlo velkým chybám, matice se čas od času kompletně přepočítává. Tento proces se nazývá „opakování“. $B^{{-1}}$

Multiplikativní verze simplexové metody

V multiplikativní verzi se matice neukládá, ukládají se pouze faktory $B^{{-1}}$ ${\begin{bmatrix}E&-q'/q_{f}\\0&1/q_{f}\end{bmatrix))$

Při řešení ekonomických problémů je matice omezení často řídká , v takovém případě má multiplikativní možnost další výhody - můžete ukládat multiplikátory v komprimované podobě (neukládat nuly).

Další varianty simplexové metody

Aby se zabránilo hromadění chyb zaokrouhlování, lze použít rozklad LU matice .

Při obrovském počtu omezení typu „nerovnost“ lze použít metodu proměnné báze . [čtyři]

Metoda je založena na skutečnosti, že základní matici lze reprezentovat jako

${\begin{bmatrix}A_{B}&0\\A_{E}&E\end{bmatrix}}$

Jeho inverzní má tvar

${\begin{bmatrix}A_{B}^{{-1}}&0\\-A_{B}^{{-1}}A_{E}&E\end{bmatrix}}$

Při relativně malých velikostech matrice nemusí být zbytek matrice uložen. $A_{B}^{{-1}}$

Tento přístup může vyřešit problémy s desítkami milionů řetězců omezení (například z teorie her).

Duální simplexová metoda

Pro implementaci duální metody je nutné přejít od problému k minimu k problému k maximu (nebo naopak) transpozicí matice koeficientů. Při přechodu z úkolu na minimum bude mít účelová funkce tvar:

$g=\součet _{{i=1}}^{n}b_{i}y_{i}\do max.$

pod omezeními

$\sum _{i=1}^{n}a_{ij}y_{i}\leq c_{j}$ .

Věta o dualitě . Pokud má jeden z dvojice duálních problémů optimální plán, pak druhý má řešení a extrémní hodnoty lineárních funkcí těchto problémů jsou stejné.

Pokud lineární funkce jednoho z problémů není omezena, pak druhý nemá řešení.

Výpočetní účinnost

Simplexová metoda je v praxi překvapivě účinná, ale v roce 1972 Klee a Minty [5] uvedli příklad, ve kterém simplexová metoda iterovala přes všechny vrcholy simplexu, přičemž v nejhorším případě ukázala exponenciální konvergenci metody. Od té doby se pro každou variantu metody našel příklad, na kterém se metoda chovala výjimečně špatně.

Pozorování a analýza účinnosti metody v praktických aplikacích vedla k vývoji dalších způsobů měření účinnosti.

Simplexová metoda má průměrnou polynomickou konvergenci se širokým výběrem distribuce hodnot v náhodných maticích. [6] [7]

Výpočetní účinnost se obvykle odhaduje pomocí dvou parametrů:

počet iterací potřebných k získání řešení;
náklady na strojový čas.

Jako výsledek numerických experimentů byly získány následující výsledky.

Počet iterací při řešení problémů lineárního programování ve standardním tvaru s omezeními a proměnnými je mezi a . Průměrný počet iterací . Horní hranice počtu iterací je . $m$ $n$ $m$ $3m$ $2m$ $2m+n$
Požadovaný strojní čas je úměrný . $m^{3}$

Počet omezení ovlivňuje výpočetní efektivitu více než počet proměnných, proto při formulování problémů lineárního programování je třeba usilovat o snížení počtu omezení, i když zvýšením počtu proměnných.

Metody pro zlepšení účinnosti

Jedním z časově nejnáročnějších postupů v simplexové metodě je hledání sloupce zavedeného do základu. Pro lepší konvergenci by se zdálo, že musíte vybrat proměnnou s nejlepším zbytkem, ale to vyžaduje úplné skenování, to znamená, že musíte vynásobit sloupec duálních proměnných (někdy nazývaných stínové ceny) všemi sloupci matice. [8] . Tento přístup funguje dobře pro malé problémy, které se řeší ručně. Navíc se striktní dodržování pravidla pro volbu maximálního reziduálního modulu může ukázat jako suboptimální z hlediska celkového počtu iterací potřebných k získání extrému. Maximální zisk při jedné iteraci může vést k pomalému poklesu hodnoty účelové funkce v následujících krocích a tím zpomalit proces řešení problému [9] .

S velkými maticemi omezení začíná procedura hledání vstupní proměnné zabírat hodně času a často dochází k pokusům vyhnout se prohlížení všech sloupců matice, k čemuž lze použít následující metody:

Bariéra . Jakmile je diskrepance proměnné dostatečně odlišná od nuly (překročí určitou hodnotu zvanou bariéra), je proměnná zavedena do báze. Pokud se ukázalo, že všechny rezidua jsou menší než bariéra, je jako vstup vybrána proměnná s nejmenším reziduem, zatímco samotná bariéra je podle nějakého pravidla redukována (například polovina nejmenšího rezidua). Bariéra se často používá s následující technikou. Podobný přístup je popsán v Murtaughově knize, viz oddíl 3.6.2. Dílčí hodnocení knihy [10] . Pohled na kolo . Hledání vstupní proměnné začíná od pozice následující za proměnnou zavedenou v předchozí iteraci. Skupinový výběr (V Murtaughově knize se tato technika nazývá vícenásobné vyhodnocení . Viz část 3.6.3. Vícenásobné vyhodnocení [11] .) Při hledání vstupní proměnné se nevybírá jedna proměnná, ale několik kandidátů. Při dalších iteracích je prohlížení prováděno pouze mezi vybranými kandidáty, přičemž kandidáta lze ze seznamu vymazat. Účel vah . Proměnným jsou přiřazeny váhy. Viz část 3.6.4 DEVEX skórovací metoda od Murtafy [12] . Hledejte nejstrmější žebro Goldfarba a Reeda. Viz část 3.6.5 Metoda odhadu nejstrmější hrany v Murtaughově knize [13] .

Možné jsou i jiné triky, jako například Zadehovo pravidlo .

Poznámky

↑ Kantorovich L. V. Matematické metody pro organizaci plánování výroby // Edice Leningradské státní univerzity. - Leningrad, 1939.
↑ S. Gass. Lineární programování (metody a aplikace). - Moskva: Státní nakladatelství fyzikální a matematické literatury, 1961. - (Inženýrská fyzikální a matematická knihovna).
↑ Toto doporučení se často vyskytuje v učebnicích, ale není vždy správné. Viz #Metody pro zlepšení efektivity
↑ V.I. Muravyov. Metoda sekvenčního zlepšování s proměnnou velikostí základny pro problémy lineárního programování. — Sbírka „Výzkum operací a metod statistického modelování“. - Leningrad: Leningradská státní univerzita, 1972.
↑ Klee, Victor; Minty, George J. Jak dobrý je simplexní algoritmus? // Nerovnosti III (Sborník příspěvků ze třetího sympozia o nerovnostech konaného na Kalifornské univerzitě, Los Angeles, Kalifornie, 1.–9. září 1969, věnované památce Theodora S. Motzkina) (anglicky) / Shisha, Oved . - New York-London: Academic Press , 1972. - S. 159-175.
↑ Alexander Schrijver, Teorie lineárního a celočíselného programování . John Wiley & sons, 1998, ISBN 0-471-98232-6 (matematické)
↑ Simplexní algoritmus trvá v průměru D kroků pro kostku. Borgwardt, Karl-Heinz. Simplexová metoda : pravděpodobnostní analýza . - Berlin: Springer-Verlag , 1987. - Sv. 1. - P.xii+268. - (Algoritmy a kombinatorika (studijní a výzkumné texty)). - ISBN 3-540-17096-0 .
↑ Doporučení zvolit maximální modulo hodnotu rezidua lze často nalézt v popisech simplexové metody, například v článcích Algoritmus pro simplexovou metodu Archivováno 17. března 2018 na Wayback Machine a SIMPLEX LINEÁRNÍ PROGRAMOVÁ METODA Archivováno 17. března 2018 na Wayback Machine
↑ Shamray, 2009 , str. 44.
↑ Murtaf, 1984 .
↑ Murtaf, 1984 , str. 61.
↑ Murtaf, 1984 , str. 62.
↑ Murtaf, 1984 , str. 63.

Literatura

Hemdy A. Taha. Kapitola 3. Simplexní metoda // Úvod do operačního výzkumu = Operační výzkum: Úvod. - 7. vyd. - M .: "Williams" , 2007. - S. 95-141. — ISBN 0-13-032374-8 .
Akulich I.L. Kapitola 1. Problémy lineárního programování // Matematické programování v příkladech a úlohách. - M . : Vyšší škola , 1986. - 319 s. — ISBN 5-06-002663-9 .
Thomas H. Kormen a kol., Kapitola 29 Lineární programování // Algoritmy: Konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
V. N. Ševčenko, N. Yu. Zolotykh. Lineární a celočíselné lineární programování . - Nižnij Novgorod: Vydavatelství Nižnij Novgorodské státní univerzity. N.I. Lobachevsky, 2004. - S. 63 -66 (část 2.8. Poznámky ke složitosti řešení CŽV). — ISBN 5-85746-761-6 .
Shamray Natalya Borisovna. Praktické lineární programování pro ekonomy . - Vladivostok: Publishing House of the Far Eastern University, 2009. - S. 44. - ISBN 978-5-7444-2215-8 . Archivováno 17. března 2018 na Wayback Machine
Murtaf B. Moderní lineární programování. - Moskva: Mir, 1984.

Odkazy

Slovníky a encyklopedie	Britannica (online)
V bibliografických katalozích	GND : 4181488-5 J9U : 987007546249105171 LCCN : sh85122745

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování