Lineární programování - Linear programming

Obrázkové znázornění jednoduchého lineárního programu se dvěma proměnnými a šesti nerovnostmi. Sada proveditelných řešení je zobrazena žlutě a tvoří a polygon, 2-dimenzionální polytop. Funkci lineárních nákladů představuje červená čára a šipka: Červená čára je a nastavena úroveň nákladové funkce a šipka označuje směr, kterým optimalizujeme.

Uzavřená proveditelná oblast problému se třemi proměnnými je konvexní mnohostěn. Plochy poskytující pevnou hodnotu objektivní funkce jsou letadla (nezobrazeno). Problémem lineárního programování je najít bod na mnohostěnu, který je v rovině s nejvyšší možnou hodnotou.

Lineární programování (LP, také zvaný lineární optimalizace) je metoda k dosažení nejlepšího výsledku (jako je maximální zisk nebo nejnižší cena) v a matematický model jejichž požadavky jsou reprezentovány lineární vztahy. Lineární programování je speciální případ matematického programování (také známý jako matematická optimalizace ).

Formálně je lineární programování technikou pro optimalizace a lineární Objektivní funkce, s výhradou lineární rovnost a lineární nerovnost omezení. Své proveditelný region je konvexní mnohostěn, což je sada definovaná jako průsečík konečně mnoha poloviční mezery, z nichž každý je definován lineární nerovností. Jeho objektivní funkcí je a nemovitý -hodnota afinní (lineární) funkce definované na tomto mnohostěnu. Lineární programování algoritmus najde bod v polytop kde tato funkce má nejmenší (nebo největší) hodnotu, pokud takový bod existuje.

Lineární programy jsou problémy, které lze vyjádřit kanonická forma tak jako

${ displaystyle { begin {aligned} & { text {Maximize}} && mathbf {c} ^ { mathrm {T}} mathbf {x} & { text {předmět}} && A mathbf {x} leq mathbf {b} & { text {and}} && mathbf {x} geq mathbf {0} end {zarovnáno}}}$

kde X představuje vektor proměnných (bude určen), C a b jsou vektory (známých) koeficientů, A je (známý) matice koeficientů a ${ displaystyle ( cdot) ^ { mathrm {T}}}$ je maticová transpozice. Výraz, který má být maximalizován nebo minimalizován, se nazývá Objektivní funkce (C^TX v tomto případě). Nerovnosti AX ≤ b a X ≥ 0 jsou omezení, která specifikují a konvexní mnohostěn nad kterou má být optimalizována objektivní funkce. V tomto kontextu jsou dva vektory srovnatelný když mají stejné rozměry. Pokud je každá položka v první menší nebo rovna odpovídající položce ve druhé, pak lze říci, že první vektor je menší nebo roven druhému vektoru.

Lineární programování lze aplikovat na různé studijní obory. Je široce používán v matematice a v menší míře v podnikání, ekonomika a pro některé technické problémy. Odvětví, která používají modely lineárního programování, zahrnují dopravu, energetiku, telekomunikace a výrobu. Ukázalo se užitečné při modelování různých typů problémů v systému Windows plánování, směrování, plánování, úkol a design.

Dějiny

Leonid Kantorovič

John von Neumann

Problém řešení systému lineárních nerovností sahá přinejmenším tak daleko Fourier, který v roce 1827 zveřejnil metodu jejich řešení,^[1] a po kom metoda Vyřazení Fourier-Motzkin je pojmenován.

V roce 1939 dala formulace lineárního programování problému, který je ekvivalentní obecnému problému lineárního programování, sovětský matematik a ekonom Leonid Kantorovič, který také navrhl způsob jeho řešení.^[2] Je to způsob, jakým se vyvinul během druhá světová válka, plánovat výdaje a výnosy za účelem snížení nákladů na armádu a zvýšení ztrát uvalených na nepřítele.^{[Citace je zapotřebí ]} Kantorovichova práce byla původně v SSSR.^[3] Přibližně ve stejné době jako Kantorovich, holandsko-americký ekonom T. C. Koopmans formuloval klasické ekonomické problémy jako lineární programy. Kantorovich a Koopmans později sdíleli 1975 Nobelova cena za ekonomii.^[1] V roce 1941 Frank Lauren Hitchcock také formuloval dopravní problémy jako lineární programy a poskytl řešení velmi podobné pozdějšímu simplexní metoda.^[2] Hitchcock zemřel v roce 1957 a Nobelova cena není udělována posmrtně.

V letech 1946–1947 George B. Dantzig nezávisle vyvinul obecnou formulaci lineárního programování pro použití při plánování problémů v US Air Force.^[4] V roce 1947 Dantzig také vynalezl simplexní metoda že poprvé ve většině případů efektivně řešilo problém lineárního programování.^[4] Když Dantzig domluvil schůzku s John von Neumann aby diskutoval o své simplexní metodě, Neumann si okamžitě vymyslel teorii dualita tím, že si uvědomil, že problém, ve kterém pracoval herní teorie byl ekvivalentní.^[4] Dantzig poskytl formální důkaz v nepublikované zprávě „Věta o lineárních nerovnostech“ 5. ledna 1948.^[3] Dantzigova práce byla zpřístupněna veřejnosti v roce 1951. V poválečných letech ji mnoho průmyslových odvětví uplatnilo při každodenním plánování.

Dantzigovým původním příkladem bylo najít nejlepší úkol 70 lidí na 70 pracovních míst. Výpočetní výkon potřebný k testování všech permutací k výběru nejlepšího přiřazení je obrovský; počet možných konfigurací překračuje počet částic v pozorovatelný vesmír. Hledání optimálního řešení však trvá jen chvilku, když se problém zobrazí jako lineární program a použije se simplexní algoritmus. Teorie lineárního programování drasticky snižuje počet možných řešení, která je třeba zkontrolovat.

Problém lineárního programování se poprvé ukázal jako řešitelný v polynomiálním čase pomocí Leonid Khachiyan v roce 1979,^[5] ale větší teoretický a praktický průlom v této oblasti přišel v roce 1984, kdy Narendra Karmarkar představil nový metoda vnitřního bodu pro řešení problémů lineárního programování.^[6]

Použití

Lineární programování je široce používaným polem optimalizace z několika důvodů. Mnoho praktických problémů v operační výzkum lze vyjádřit jako problémy lineárního programování.^[3] Určité zvláštní případy lineárního programování, jako např tok sítě problémy a tok více akomodit problémy jsou považovány za dostatečně důležité na to, aby vygenerovaly mnoho výzkumů specializovaných algoritmů pro jejich řešení. Řada algoritmů pro jiné typy optimalizačních problémů funguje tak, že LP problémy řeší jako dílčí problémy. Historicky nápady z lineárního programování inspirovaly mnoho ústředních konceptů teorie optimalizace, jako například dualita, rozklad, a důležitost konvexnost a jeho zobecnění. Rovněž lineární programování bylo těžce používáno v rané tvorbě mikroekonomie a v současné době se používá ve vedení společnosti, jako je plánování, výroba, doprava, technologie a další záležitosti. Ačkoli se moderní problémy s řízením neustále mění, většina společností by chtěla maximalizovat zisky a minimalizovat náklady s omezenými zdroji. Mnoho problémů lze tedy charakterizovat jako problémy lineárního programování.

Standardní forma

Standardní forma je obvyklá a nejintuitivnější forma popisu problému lineárního programování. Skládá se z následujících tří částí:

• A lineární funkce, která má být maximalizována

např. ${ displaystyle f (x_ {1}, x_ {2}) = c_ {1} x_ {1} + c_ {2} x_ {2}}$

• Omezení problému následujícího formuláře

např.

${ displaystyle { begin {matrix} a_ {11} x_ {1} + a_ {12} x_ {2} & leq b_ {1} a_ {21} x_ {1} + a_ {22} x_ { 2} & leq b_ {2} a_ {31} x_ {1} + a_ {32} x_ {2} & leq b_ {3} end {matrix}}}$

• Nezáporné proměnné

např.

${ displaystyle { begin {matrix} x_ {1} geq 0 x_ {2} geq 0 end {matrix}}}$

Problém je obvykle vyjádřen v matice formulář, a poté se stane:

${ displaystyle max { mathbf {c} ^ { mathrm {T}} mathbf {x} ; | ; A mathbf {x} leq mathbf {b} land mathbf {x} geq 0 }}$

Jiné formy, jako jsou problémy s minimalizací, problémy s omezeními alternativních forem, stejně jako problémy zahrnující negativní proměnné lze vždy přepsat na ekvivalentní problém ve standardní formě.

Příklad

Řekněme, že zemědělec má kus zemědělské půdy L km², které mají být osázeny pšenicí nebo ječmenem nebo kombinací obou. Zemědělec má omezené množství hnojiv, F kilogramů a pesticidů, P kilogramů. Každý kilometr čtvereční pšenice vyžaduje F₁ kilogramů hnojiva a P₁ kilogramů pesticidů, zatímco každý kilometr čtvereční ječmene vyžaduje F₂ kilogramů hnojiva a P₂ kilogramů pesticidů. Pojďme₁ být prodejní cena pšenice za kilometr čtvereční a S.₂ být prodejní cenou ječmene. Pokud bychom označili plochu půdy osázené pšenicí a ječmenem X₁ a X₂ respektive pak lze zisk maximalizovat výběrem optimálních hodnot pro X₁ a X₂. Tento problém lze vyjádřit následujícím problémem lineárního programování ve standardní podobě:

Maximalizovat: ${ displaystyle S_ {1} cdot x_ {1} + S_ {2} cdot x_ {2}}$		(maximalizovat výnos - příjem je „objektivní funkce“)
Předmět:	${ displaystyle x_ {1} + x_ {2} leq L}$	(limit na celkovou plochu)
	${ displaystyle F_ {1} cdot x_ {1} + F_ {2} cdot x_ {2} leq F}$	(limit na hnojivo)
	${ displaystyle P_ {1} cdot x_ {1} + P_ {2} cdot x_ {2} leq P}$	(limit na pesticidy)
	${ displaystyle x_ {1} geq 0, x_ {2} geq 0}$	(nelze zasadit negativní plochu).

V maticové formě se stává:

maximalizovat ${ displaystyle { begin {bmatrix} S_ {1} & S_ {2} end {bmatrix}} { begin {bmatrix} x_ {1} x_ {2} end {bmatrix}}}$

podléhá ${ displaystyle { begin {bmatrix} 1 & 1 F_ {1} & F_ {2} P_ {1} & P_ {2} end {bmatrix}} { begin {bmatrix} x_ {1} x_ { 2} end {bmatrix}} leq { begin {bmatrix} L F P end {bmatrix}}, , { begin {bmatrix} x_ {1} x_ {2} end {bmatrix}} geq { begin {bmatrix} 0 0 end {bmatrix}}.}$

Rozšířená forma (uvolněná forma)

Problémy s lineárním programováním lze převést na rozšířená forma za účelem použití společné formy simplexní algoritmus. Tento formulář zavádí nezáporné uvolněné proměnné nahradit nerovnosti rovnostmi v omezeních. Problémy lze potom zapsat do následujícího textu bloková matice formulář:

Maximalizovat ${ displaystyle z}$:

${ displaystyle { begin {bmatrix} 1 & - mathbf {c} ^ {T} & 0 0 & mathbf {A} & mathbf {I} end {bmatrix}} { begin {bmatrix} z ​​ mathbf {x} mathbf {s} end {bmatrix}} = { begin {bmatrix} 0 mathbf {b} end {bmatrix}}}$

${ displaystyle mathbf {x} geq 0, mathbf {s} geq 0}$

kde ${ displaystyle mathbf {s}}$ jsou nově zavedené proměnné slack, ${ displaystyle mathbf {x}}$ jsou rozhodovací proměnné a ${ displaystyle z}$ je proměnná, která má být maximalizována.

Příklad

Výše uvedený příklad je převeden do následující rozšířené formy:

Maximalizovat: ${ displaystyle S_ {1} cdot x_ {1} + S_ {2} cdot x_ {2}}$		(Objektivní funkce)
podléhá:	${ displaystyle x_ {1} + x_ {2} + x_ {3} = L}$	(rozšířené omezení)
	${ displaystyle F_ {1} cdot x_ {1} + F_ {2} cdot x_ {2} + x_ {4} = F}$	(rozšířené omezení)
	${ displaystyle P_ {1} cdot x_ {1} + P_ {2} cdot x_ {2} + x_ {5} = P}$	(rozšířené omezení)
	${ displaystyle x_ {1}, x_ {2}, x_ {3}, x_ {4}, x_ {5} geq 0.}$

kde ${ displaystyle x_ {3}, x_ {4}, x_ {5}}$ jsou (nezáporné) uvolněné proměnné, které v tomto příkladu představují nevyužitou plochu, množství nepoužitého hnojiva a množství nepoužitého pesticidu.

V maticové formě se stává:

Maximalizovat ${ displaystyle z}$:

${ displaystyle { begin {bmatrix} 1 & -S_ {1} & - S_ {2} & 0 & 0 & 0 0 & 1 & 1 & 1 & 0 & 0 0 & F_ {1} & F_ {2} & 0 & 1 & 0 0 & P_ {1} & P_ {2} & 0 & 0 & 1 end {bmatrix}} { begin {bmatrix} z ​​ x_ {1} x_ {2} x_ {3} x_ {4} x_ {5} end {bmatrix}} = { begin {bmatrix} 0 L F P end {bmatrix}}, , { begin {bmatrix} x_ {1} x_ {2} x_ {3} x_ { 4} x_ {5} end {bmatrix}} geq 0.}$

Dualita

Každý problém lineárního programování, označovaný jako a původní problém, lze převést na a dvojí problém, který poskytuje horní hranici optimální hodnoty primárního problému. V maticové formě můžeme vyjádřit původní problém jako:

Maximalizovat C^TX podléhá AX ≤ b, X ≥ 0;

s odpovídajícím symetrický dvojí problém,

Minimalizovat b^Ty podléhá A^Ty ≥ C, y ≥ 0.

Alternativní primární formulace je:

Maximalizovat C^TX podléhá AX ≤ b;

s odpovídajícím asymetrický dvojí problém,

Minimalizovat b^Ty podléhá A^Ty = C, y ≥ 0.

Teorie duality má zásadní význam. Jedním z nich je skutečnost, že (pro symetrický duální) je duální dvojitý lineární program původním prvotním lineárním programem. Každé proveditelné řešení pro lineární program navíc poskytuje hranici optimální hodnoty objektivní funkce jeho duálního programu. The slabá dualita věta říká, že hodnota objektivní funkce duálu v jakémkoli proveditelném řešení je vždy větší nebo rovna hodnotě objektivní funkce primálu v jakémkoli proveditelném řešení. The silná dualita věta říká, že pokud má primál optimální řešení, X^*, pak má duální také optimální řešení, y^*, a C^TX^*=b^Ty^*.

Lineární program může být také neomezený nebo neproveditelný. Teorie duality nám říká, že pokud je primal neomezený, pak je duální pomocí slabé věty o dualitě nemožné. Stejně tak je-li dvojník neomezený, musí být primál neproveditelný. Je však možné, aby duál i primál byli neproveditelní. Vidět duální lineární program pro podrobnosti a několik dalších příkladů.

Variace

Krycí / balicí duality

A krycí LP je lineární program ve tvaru:

Minimalizovat: b^Ty,

podléhá: A^Ty ≥ C, y ≥ 0,

tak, že matice A a vektory b a C jsou nezáporné.

Duál krycího LP je a balení LP, lineární program ve tvaru:

Maximalizovat: C^TX,

podléhá: AX ≤ b, X ≥ 0,

tak, že matice A a vektory b a C jsou nezáporné.

Příklady

Krytí a balení LP obvykle vznikají jako relaxace lineárního programování kombinatorického problému a jsou důležité při studiu aproximační algoritmy.^[7] Například LP relaxace nastavit problém s balením, problém nezávislé množiny a problém se shodou balí LP. LP relaxace nastavit problém s krytem, problém s vrcholovým krytem a dominující množinový problém pokrývají také LP.

Hledání a frakční zbarvení a graf je dalším příkladem krycího LP. V tomto případě existuje jedno omezení pro každý vrchol grafu a jedna proměnná pro každý nezávislá sada grafu.

Doplňková ochablost

Je možné získat optimální řešení duálu, když je známo pouze optimální řešení primalu pomocí věty o komplementární slabosti. Věta říká:

Předpokládejme to X = (X₁, X₂, ... , X_n) je prvotní proveditelné a to y = (y₁, y₂, ... , y_m) je dvojí proveditelné. Nechť (w₁, w₂, ..., w_m) označí odpovídající proměnné počátečního uvolnění a necháme (z₁, z₂, ... , z_n) označují odpovídající proměnné s dvojitým uvolněním. Pak X a y jsou optimální pro jejich příslušné problémy právě tehdy

• X_j z_j = 0, pro j = 1, 2, ... , n, a
• w_i y_i = 0, pro i = 1, 2, ... , m.

Takže pokud i-tá proměnná uvolnění primalu není nula, pak i-tá proměnná duálu se rovná nule. Stejně tak, pokud j-tá volná proměnná duálu není nula, pak j-tá proměnná primalu se rovná nule.

Tato nezbytná podmínka optimality vyjadřuje poměrně jednoduchý ekonomický princip. Ve standardní formě (při maximalizaci), pokud je v omezeném primárním zdroji volno (tj. Existují „zbytky“), pak další množství tohoto zdroje nesmí mít žádnou hodnotu. Podobně, pokud je v požadavku omezení negativity dvojí (stínové) cenové negativity nedostatek, tj. Cena není nula, pak musí existovat omezené zásoby (žádné „zbytky“).

Teorie

Existence optimálních řešení

Geometricky lineární vazby definují proveditelný region, což je konvexní mnohostěn. A lineární funkce je konvexní funkce, což znamená, že každý místní minimum je globální minimum; podobně je lineární funkce a konkávní funkce, což znamená, že každý místní maximum je globální maximum.

Optimální řešení nemusí existovat, a to ze dvou důvodů. Nejprve, pokud jsou omezení nekonzistentní, neexistuje žádné proveditelné řešení: Například omezení X ≥ 2 a X ≤ 1 nelze společně uspokojit; v tomto případě říkáme, že LP je nemožné. Zadruhé, když polytop je neomezený ve směru gradientu objektivní funkce (kde gradient objektivní funkce je vektorem koeficientů objektivní funkce), pak není dosaženo optimální hodnoty, protože je vždy možné udělat lépe než jakoukoli konečnou hodnotu objektivní funkce.

Optimální vrcholy (a paprsky) mnohostěnů

V opačném případě, pokud existuje proveditelné řešení a pokud je sada omezení omezena, pak je optimální hodnoty vždy dosaženo na hranici sady omezení pomocí maximální princip pro konvexní funkce (alternativně, minimální princip pro konkávní funkce ) protože lineární funkce jsou konvexní i konkávní. Některé problémy však mají zřetelná optimální řešení; například problém nalezení proveditelného řešení systému lineárních nerovností je problém lineárního programování, ve kterém je objektivní funkcí funkce nula (tj. konstantní funkce všude s nulovou hodnotou). Pro tento problém proveditelnosti s nulovou funkcí pro jeho objektivní funkci, pokud existují dvě odlišná řešení, je řešení každá konvexní kombinace řešení.

Také se nazývají vrcholy mnohostěnu základní proveditelná řešení. Důvod této volby jména je následující. Nechat d označte počet proměnných. Potom ze základní věty o lineárních nerovnostech vyplývá (pro proveditelné problémy), že pro každý vrchol X^* proveditelné oblasti LP existuje sada d (nebo méně) omezení nerovnosti z LP taková, že když s nimi zacházíme d omezení jako rovnost, jedinečné řešení je X^*. Tímto způsobem můžeme tyto vrcholy studovat pomocí pohledu na určité podmnožiny množiny všech omezení (diskrétní množina), spíše než na kontinuum LP řešení. Tento princip je základem simplexní algoritmus pro řešení lineárních programů.

Algoritmy

V problému lineárního programování vytváří řada lineárních omezení a konvexní proveditelný region možných hodnot pro tyto proměnné. V případě dvou proměnných má tato oblast tvar konvexní jednoduchý mnohoúhelník.

Algoritmy výměny základů

Simplexní Dantzigův algoritmus

The simplexní algoritmus, vyvinutý společností George Dantzig v roce 1947 řeší problémy s LP konstrukcí proveditelného řešení na vrcholu polytop a poté kráčet po cestě na okrajích mnohostěnu k vrcholům s neklesajícími hodnotami objektivní funkce, dokud nebude jistě dosaženo optima. V mnoha praktických problémech, “pozastavení "dochází: mnoho čepů je vyrobeno bez zvýšení objektivní funkce.^[8][9] Ve vzácných praktických problémech mohou obvyklé verze simplexního algoritmu skutečně „cyklovat“.^[9] Aby se zabránilo cyklům, vyvinuli vědci nová pravidla otáčení.^{[10][11][8][9][12][13]}

V praxi simplex algoritmus je docela efektivní a lze mu zaručit nalezení globálního optima, pokud budou dodržena určitá preventivní opatření cyklistika jsou převzaty. Ukázalo se, že simplexní algoritmus řeší „náhodné“ problémy efektivně, tj. V kubickém počtu kroků,^[14] což je podobné jeho chování při praktických problémech.^[8][15]

Algoritmus simplexu má však špatné chování v nejhorším případě: Klee a Minty zkonstruovali rodinu problémů lineárního programování, u nichž simplexová metoda vyžaduje řadu kroků exponenciálních ve velikosti problému.^[8][11][12] Ve skutečnosti po nějakou dobu nebylo známo, zda je problém lineárního programování řešitelný polynomiální čas, tj třída složitosti P.

Křížový algoritmus

Stejně jako Dantzigův simplexní algoritmus, i křížový algoritmus je algoritmus výměny báze, který se otáčí mezi základnami. Algoritmus křížového přechodu však nemusí udržovat proveditelnost, ale může se otáčet spíše od proveditelného základu k neproveditelnému základu. Křížový algoritmus nemá polynomiální časová složitost pro lineární programování. Oba algoritmy navštíví všechny 2^D rohy (rozrušený) krychle v rozměruD, Klee – Minty kostka, v nejhorší případ.^[13][16]

Vnitřní bod

Na rozdíl od simplexního algoritmu, který najde optimální řešení procházením hran mezi vrcholy na mnohostěnné sadě, se metody vnitřních bodů pohybují vnitřkem proveditelné oblasti.

Allipsoidní algoritmus, sledující Khachiyana

Toto je první nejhorší případ polynomiální čas algoritmus, který byl kdy nalezen pro lineární programování. Vyřešit problém, který má n proměnné a lze je zakódovat do L vstupních bitů, tento algoritmus běží ${ displaystyle O (n ^ {6} L)}$ čas.^[5] Leonid Khachiyan vyřešil tento dlouhodobý problém složitosti v roce 1979 zavedením elipsoidní metoda. Konvergenční analýza má předchůdce (v reálném počtu), zejména iterační metody vyvinutý uživatelem Naum Z. Shor a aproximační algoritmy Arkadi Nemirovski a D. Yudin.

Projektivní algoritmus Karmarkaru

Khachiyanův algoritmus měl zásadní význam pro stanovení polynomiálně-časové řešitelnosti lineárních programů. Algoritmus nebyl výpočtovým průlomem, protože simplexní metoda je efektivnější pro všechny, ale speciálně konstruované rodiny lineárních programů.

Khachiyanův algoritmus však inspiroval nové linie výzkumu lineárního programování. V roce 1984 N. Karmarkar navrhl a projektivní metoda pro lineární programování. Karmarkarův algoritmus^[6] vylepšil Khachiyan^[5] nejhorší polynomiální vazba (dávající ${ displaystyle O (n ^ {3,5} L)}$). Karmarkar tvrdil, že jeho algoritmus byl mnohem rychlejší v praktickém LP než simplexní metoda, což je tvrzení, které vyvolalo velký zájem o metody vnitřních bodů.^[17] Od objevu Karmarkara bylo navrženo a analyzováno mnoho metod vnitřních bodů.

Algoritmus Vaidya 87

V roce 1987 Vaidya navrhl algoritmus, který běží dovnitř ${ displaystyle O (n ^ {3})}$ čas.^[18]

Algoritmus Vaidya 89

V roce 1989 vyvinula Vaidya algoritmus, který funguje ${ displaystyle O (n ^ {2.5})}$ čas.^[19] Formálně vzato, algoritmus trvá ${ displaystyle O ((n + d) ^ {1,5} nL)}$ v nejhorším případě aritmetické operace, kde ${ displaystyle d}$ je počet omezení, ${ displaystyle n}$ je počet proměnných a ${ displaystyle L}$ je počet bitů.

Algoritmy časových vstupů

V roce 2015 Lee a Sidford ukázali, že to lze vyřešit v ${ displaystyle O ((nnz (A) + n ^ {2}) { sqrt {n}} L)}$ čas,^[20] kde ${ displaystyle nnz (A)}$ představuje počet nenulových prvků a stále trvá ${ displaystyle O (n ^ {2.5} L)}$ v nejhorším případě.

Algoritmus násobení aktuální matice

V roce 2019 Cohen, Lee a Song vylepšili provozní dobu ${ displaystyle { tilde {O}} ((n ^ { omega} + n ^ {2,5- alpha / 2} + n ^ {2 + 1/6}) L)}$ čas, ${ displaystyle omega}$ je exponent násobení matic a ${ displaystyle alpha}$ je dvojitý exponent násobení matic.^[21] ${ displaystyle alpha}$ je (zhruba) definován jako největší číslo tak, že lze znásobit ${ displaystyle n krát n}$ matice a ${ displaystyle n krát n ^ { alpha}}$ matice v ${ displaystyle O (n ^ {2})}$ čas. V následné práci Lee, Songa a Zhanga reprodukují stejný výsledek jinou metodou.^[22] Tyto dva algoritmy zůstávají ${ displaystyle { tilde {O}} (n ^ {2 + 1/6} L)}$ když ${ displaystyle omega = 2}$ a ${ displaystyle alpha = 1}$. Výsledek díky Jiangovi, Songovi, Weinsteinovi a Zhangovi se zlepšil ${ displaystyle { tilde {O}} (n ^ {2 + 1/6} L)}$ na ${ displaystyle { tilde {O}} (n ^ {2 + 1/18} L)}$.^[23]

Porovnání vnitřních bodových metod a simplexních algoritmů

Současný názor je, že efektivita dobrých implementací metod založených na simplexu a metod vnitřních bodů je u rutinních aplikací lineárního programování podobná. U konkrétních typů problémů s LP však může dojít k tomu, že jeden typ řešiče je lepší než jiný (někdy mnohem lepší) a že struktura řešení generovaných metodami vnitřních bodů oproti metodám založeným na simplexu se výrazně liší s podporou sada aktivních proměnných, která je u druhé obvykle menší.^[24]

Otevřené problémy a nedávná práce

Nevyřešený problém v informatice: Připouští lineární programování algoritmus silně polynomiálního času? (více nevyřešených problémů v informatice)

V teorii lineárního programování existuje několik otevřených problémů, jejichž řešení by představovalo zásadní průlom v matematice a potenciálně významný pokrok v naší schopnosti řešit rozsáhlé lineární programy.

• Připouští LP a silně polynomický -časový algoritmus?
• Připouští LP algoritmus silně polynomiálního času, aby našel striktně komplementární řešení?
• Připouští LP algoritmus polynomiálního času ve výpočetním modelu reálného počtu (jednotkových nákladů)?

Tento úzce související soubor problémů byl citován Stephen Smale jako mezi 18 největších nevyřešených problémů 21. století. Podle Smaleových slov je třetí verze problému „hlavním nevyřešeným problémem teorie lineárního programování“. Zatímco existují algoritmy pro řešení lineárního programování ve slabě polynomiálním čase, jako je elipsoidní metody a techniky vnitřních bodů, dosud nebyly nalezeny žádné algoritmy, které by umožňovaly silně polynomiálně-časový výkon v počtu omezení a počtu proměnných. Vývoj takových algoritmů by byl velkým teoretickým zájmem a možná by umožnil praktické zisky také při řešení velkých LP.

Ačkoliv Hirschova domněnka byl nedávno vyvrácen pro vyšší dimenze, ponechává otevřené následující otázky.

• Existují pravidla pivot, která vedou k simplexním variantám v polynomiálním čase?
• Mají všechny polytopální grafy polynomiálně ohraničený průměr?

Tyto otázky se týkají analýzy výkonu a vývoje simplexních metod. Obrovská účinnost simplexního algoritmu v praxi navzdory jeho teoretickému výkonu v exponenciálním čase naznačuje, že mohou existovat variace simplexu, které běží v polynomiálním nebo dokonce silně polynomiálním čase. Bylo by velmi praktické a teoreticky důležité vědět, zda takové varianty existují, zejména jako přístup k rozhodnutí, zda lze LP vyřešit v silně polynomiálním čase.

Simplexový algoritmus a jeho varianty spadají do rodiny algoritmů sledujících hrany, tak pojmenovaných, protože řeší problémy lineárního programování pohybem od vrcholu k vrcholu po hranách mnohostěnu. To znamená, že jejich teoretický výkon je omezen maximálním počtem hran mezi libovolnými dvěma vrcholy na polytopu LP. Výsledkem je, že máme zájem znát maximum graficko-teoretický průměr polytopalu grafy. Bylo prokázáno, že všechny polytopy mají subexponenciální průměr. Nedávné vyvrácení Hirschova domněnky je prvním krokem k prokázání, zda má jakýkoli polytop superpolynomiální průměr. Pokud takové polytopy existují, nemůže v polynomiálním čase běžet žádná varianta sledující hrany. Otázky týkající se průměru mnohostěn jsou předmětem nezávislého matematického zájmu.

Simplexní pivotní metody zachovávají prvotní (nebo dvojí) proveditelnost. Na druhé straně metody křížového otočení nezachovávají (prvotní nebo dvojí) proveditelnost - mohou navštěvovat základní proveditelné, duální proveditelné nebo primární a duální neproveditelné základny v jakémkoli pořadí. Pivotní metody tohoto typu byly studovány od 70. let.^{[Citace je zapotřebí ]} Tyto metody se v zásadě pokoušejí najít nejkratší cestu otočení na uspořádání mnohostěn pod problém lineárního programování. Na rozdíl od polytopálních grafů je známo, že grafy uspořádání polytopů mají malý průměr, což umožňuje možnost silně polynomiálně-časově zkříženého pivotního algoritmu bez řešení otázek o průměru obecných polytopů.^[13]

Celé číslo neznámé

Pokud se požaduje, aby všechna neznámá proměnná byla celá čísla, problém se nazývá an celočíselné programování (IP) nebo celočíselné lineární programování (ILP) problém. Na rozdíl od lineárního programování, které lze v nejhorším případě efektivně vyřešit, jsou problémy s celočíselným programováním v mnoha praktických situacích (ty s omezenými proměnnými) NP-tvrdé. Programování celého čísla 0–1 nebo binární celočíselné programování (BIP) je speciální případ celočíselného programování, kde se vyžaduje, aby proměnné byly 0 nebo 1 (namísto libovolných celých čísel). Tento problém je také klasifikován jako NP-hard a ve skutečnosti byla rozhodovací verze jednou z Karpových 21 NP-úplných problémů.

Pokud se vyžaduje, aby celá čísla byla pouze některá z neznámých proměnných, problém se nazývá a smíšené celočíselné programování (MIP) problém. Ty jsou obecně také NP-tvrdé, protože jsou ještě obecnější než programy ILP.

Existují však některé důležité podtřídy problémů s IP a MIP, které jsou efektivně řešitelné, zejména problémy, kde je matice omezení naprosto unimodulární a pravá strana omezení jsou celá čísla nebo - obecněji - kde systém má úplná duální integrita (TDI) vlastnost.

Mezi pokročilé algoritmy pro řešení celočíselných lineárních programů patří:

• metoda roviny řezu
• Větvené a svázané
• Větve a řez
• Pobočka a cena
• pokud má problém nějakou zvláštní strukturu, je možné jej použít generování zpožděného sloupce.

O takových celočíselných programovacích algoritmech pojednává Padberg a v Beasley.

Integrované lineární programy

Lineární program v reálných proměnných je považován za integrální pokud má alespoň jedno optimální řešení, které je integrální. Podobně mnohostěn ${ displaystyle P = {x střední sekera geq 0 }}$ se říká, že je integrální pokud pro všechny ohraničené proveditelné objektivní funkce Clineární program ${ displaystyle { max cx mid x v P }}$ má optimum ${ displaystyle x ^ {*}}$ s celočíselnými souřadnicemi. Jak pozorovali Edmonds a Giles v roce 1977, lze rovnocenně říci, že mnohostěn ${ displaystyle P}$ je integrální, pokud pro každou omezenou proveditelnou integrální objektivní funkci C, optimální hodnota lineárního programu ${ displaystyle { max cx mid x v P }}$ je celé číslo.

Integrální lineární programy mají v polyedrickém aspektu ústřední význam kombinatorická optimalizace protože poskytují alternativní charakterizaci problému. Konkrétně pro jakýkoli problém je konvexní trup řešení integrální mnohostěn; pokud má tento mnohostěn pěkný / kompaktní popis, můžeme efektivně najít optimální proveditelné řešení pod jakýmkoli lineárním cílem. Naopak, pokud dokážeme, že a relaxace lineárního programování je integrální, pak je to požadovaný popis konvexního trupu proveditelných (integrálních) řešení.

Terminologie není v literatuře jednotná, proto je třeba rozlišovat následující dva pojmy,

• v celočíselný lineární program, popsané v předchozí části, proměnné jsou násilně omezeny na celá čísla a tento problém je obecně NP-těžký,
• v integrální lineární program, popsané v této části, proměnné nejsou omezeny na celá čísla, ale spíše se nějak dokázalo, že spojitý problém má vždy integrální optimální hodnotu (za předpokladu C je integrální) a tuto optimální hodnotu lze najít efektivně, protože všechny lineární programy o velikosti polynomu lze vyřešit v polynomiálním čase.

Jedním z běžných způsobů, jak dokázat, že mnohostěn je nedílnou součástí, je ukázat, že je naprosto unimodulární. Existují i ​​další obecné metody, včetně vlastnost rozkladu celého čísla a úplná duální integrita. Mezi další specifické známé integrální LP patří odpovídající polytop, mřížkový mnohostěn, submodulární tok mnohostěnů a průsečík dvou zobecněných polymatroidů /G-polymatroidy - např. viz Schrijver 2003.

Řešiče a skriptovací (programovací) jazyky

Tolerantní licence:

Copyleft (reciproční) licence:

MINTO (Mixed Integer Optimizer, an celočíselné programování řešitel, který používá algoritmus větvení a vázanosti) má veřejně dostupný zdrojový kód^[25] ale není open source.

Proprietární licence:

Viz také

Poznámky

Reference

Další čtení

externí odkazy

• Guidance On Formulating LP Problems
• Glosář matematického programování
• The Linear Programming FAQ
• Benchmarks For Optimisation Software