Lineární programování v kostce

Pavel Popela

21. prosince 1995

Tento text je mezivýsledkem práce na kapitole zahrnující optimalizační metody a modely pro využití v inženýrských disciplínách. Text je průběžně aktualizován. Předkládaná verze se soustřeďuje na stručný výčet podstatných poznatků. Prvním čtenářům se omlouvám za překlepy a případné další chyby v této nulté verzi a prosím je o zaslání upozornění na adresu

ppopela@kinf.fme.vutbr.cz

Podotýkám, že hledání chyb v cizích učebních textech je ideální metodou pro osvojení problematiky.

1 Základní pojmy

1.1 Prostor IR^{n}

Seriózní zájemce o studium optimalizace by měl znát základní pojmy Euklidovského prostoru IR^{n}. Vhodný úvod do problematiky poskytuje kniha: Kufner, Úvod do geometrie Hilbertova prostoru.

Uveďme pouze výčet potřebných pojmů:

1. Vektorový prostor IR^{n}, jeho prvky u, v a vlastnosti operací u + v, a.u, kde a ∈ IR.

2. Lineární nezávislost a závislost. Dimenze prostoru n, báze e_{1}, …, e_{n}.

3. Skalární součin u^{⊤}v a jeho vlastnosti. Úhel vektorů a ortogonalita vektorů u^{⊤}v = 0.

4. Norma ∥ u ∥= \sqrt{u^{⊤}u} a její vlastnosti. Ortonormalita ∥ u ∥= 1.

5. Metrika ρ(u, v) =∥ u − v ∥ a její vlastnosti. Konvergence.

Úkol: Zopakujte si definice a význam pojmů, jejich vlastnosti ilustrujte také graficky.

1.2 Matice a vektory

Jakákoliv skripta nebo učebnice VŠ matematiky pro 1.ročník dá vhodný přehled pro n-tice a tabulky reálných čísel. Autor je zvyklý používat knihu: Jirásek, Krigelstein, Tichý, Sbírka řešených příkladů z matematiky.

Uveďme podstatné pojmy:

1. n-tice reálných čísel jako vektory u, v.

2. Matice A, B, typu m × n, operace A^{⊤}, A + B, −A, aA, AB a vlastnosti. Determinanty |A|, výpočet a vlastnosti.

3. Speciální matice (nulová 0, čtvercová, jednotková I). Hodnost matice h(A). Regulární, singulární matice.

4. Inverzní matice A^{−1} a její výpočet.

5. Soustava lineárních rovnic Ax = b, její vlastnosti, řešitelnost, metody řešení, Gaussova eliminační metoda, včetně úplné eliminace, zkracujeme GEM.

Úkol: Zopakujte si definice a význam pojmů. Přesvědčte se, že vám maticové výpočty nečiní žádné problémy.

1.3 Relace uspořádání

Dostatečný přehled dávají například skripta: Novák, Diferenciální počet. Uveďme výčet pojmů:

1. Relace ekvivalence ∼ (reflexivní, symetrická, tranzitivní relace) na množině A a její vlastnosti.

2. Relace uspořádání ≤ (reflexivní, antisymetrická, tranzitivní relace) na množině A a její vlastnosti. Lineární uspořádání.

3. Označení množin: ∀B ⊂ A značíme

minB = {a ∈ B|∀b ∈ B : a ≤ b},

maxB = {a ∈ B|∀b ∈ B : a ≥ b},

infB = {a|a ∈ max{c|(c ∈ A) ∧ (∀b ∈ B : c ≤ b)}} a

supB = {a|a ∈ min{c|(c ∈ A) ∧ (∀b ∈ B : c ≥ b)}}.

Úkol: Zopakujte si definice a význam pojmů. Osvojte si uvedenou symboliku.

1.4 Extrémy funkcí

Zavádíme následující stručné označení:

1. Zobrazení a funkce značíme f : IR ⟶ IR, f : IR^{n} ⟶ IR, g : IR^{n} ⟶ IR^{m}, respektive x ⟼ f(x), x ⟼ f(x), x ⟼ g(x).

2. Definiční obor funkce f značíme D(f), obor funkčních hodnot značíme H(f).

3. Budeme často používat lineární funkce y = f(x) = c^{⊤}x a y = g(x) = Ax.

4. Pro funkci f : C ⟶ IR definujeme: Bod x_{opt} je bodem

\{ \begin{matrix}lokálního \\ globálního \end{matrix} \} × \{ \begin{matrix}ostrého \\ neostrého \end{matrix} \} × \{ \begin{matrix}minima \\ maxima \end{matrix} \}
⇔

\{ \begin{matrix}∃O(x_{opt}) : ∀x ∈ O(x_{opt}) \\ ∀x ∈ C \end{matrix} \} × ^{\{ \\{x_{opt}\} \}} × f(x_{opt}) \{ \begin{matrix}< & ≤ \\ > & ≥ \end{matrix} \} f(x)

Pro účely numerických výpočtů se dále zavádí pojem izolovaného minima.

5. Dále označujeme množinu optimálních hodnot účelové funkce min_{x}{f(x)|x ∈ C} respektive max_{x}{f(x)|x ∈ C} a z kontextu rozlišujeme, zda hovoříme o lokálních nebo globálních extrémech.

6. Podobně:

argmin_{x}{f(x)|x ∈ C} := {x ∈ C|f(x) ∈ min_{x}{f(x)|x ∈ C}} a

argmax_{x}{f(x)|x ∈ C} := {x ∈ C|f(x) ∈ max_{x}{f(x)|x ∈ C}}.

7. Pro globální extrémy a definiční obor C ⊂ IR^{n} a funkci f : C ⟶ IR platí

min_{x}{f(x)|x ∈ C} = minH(f) a analogicky

max_{x}{f(x)|x ∈ C} = maxH(f).

Úkol: Zopakujte si definice a význam pojmů. Zkuste sami definovat různé typy extrémů. Ilustrujte graficky.

1.5 Podmnožiny IR^{n}

Přehled důležitých množin a jejich vlastností:

1. Podprostor IR^{m} ⊂ IR^{n}, kde m < n (například rovina a prostor).

2. Nadrovina H = {x|c^{⊤}x = α} ⊂ IR^{n}, kde c ∈ IR^{n} a α ∈ IR.

3. Poloprostory H^{+} = {x|c^{⊤}x ≥ α} ⊂ IR^{n} a H^{−} = {x|c^{⊤}x ≤ α} ⊂ IR^{n}.

4. Okolí O(x_{0}) a ryzí okolí O(x_{0}) \ {x_{0}}.

5. Otevřená množina, vnitřek množiny intS.

6. Uzavřená množina, uzávěr množiny clS.

7. Hranice ∂S množiny S.

Úkol: Zopakujte si definice a význam pojmů. Ilustrujte graficky.

2 Konvexní množiny

2.1 Pojem a jeho vlastnosti

Pojem: S ⊂ IR^{n} je konvexní množina ⇔ ∀x_{1}, x_{2} ∈ S, ∀λ ∈< 0; 1 > platí λx_{1} + (1 − λ)x_{2} ∈ S.

Poznámky: Poznamenejme, že v konvexní množině s každými dvěma body leží i úsečka, která je spojuje. Mezi každými dvěma body existuje přímá viditelnost a konvexní množina je v jistém smyslu fádní množina, protože v ní nelze hrát na schovávanou. Tak jako linearita usnadňuje řešení obyčejných diferenciálních rovnic, tak linearita usnadňuje řešení optimalizačních úloh.

Konvexní kombinace: Řekneme, že x je konvexní kombinací bodů x_{1}, …, x_{n} ⇔ ∃λ_{i} ≥ 0, i = 1, …, n, taková, že ∑_{i=1}^{n} λ_{i} = 1 a platí, že x = ∑_{i=1}^{n} λ_{i}x_{i}.

Vlastnosti: Průnik konvexních množin je konvexní množina, sjednocení konvexních množin nemusí být konvexní množina. cl(intS) = clS, int(clS) = intS.

Příklad: Ověřte z definice a vlastností, zda množina vymezená nerovnicemi x_{2}^{2} + 3x_{3}^{2} ≤ 5, 4x_{1}^{2} + 3x_{4}^{2} ≤ 3, 3x_{1} + x_{2} − 4x_{3} + x_{4} ≤ 4 je konvexní.

Příklad: Ukažte, že poloprostor H^{−} je konvexní množina. Zvolme x_{1}, x_{2} ∈ H^{−} libovolné. Zvolme libovolné λ ∈< 0; 1 >. Definujme y = λx_{1} + (1 − λ)x_{2}. Platí c^{⊤}y = c^{⊤}(λx_{1} + (1 − λ)x_{2}) = c^{⊤}λx_{1} + c^{⊤}(1 − λ)x_{2} = λc^{⊤}x_{1} + (1 − λ)c^{⊤}x_{2} ≤ λα + (1 − λ)α = α. A tedy y ∈ H^{−}.

Úkol: Zkuste pro různé množiny ukázat, zda jsou nebo nejsou konvexní.

Vlastnosti úseček: Je dána konvexní množina S. intS ≠ {}, x_{1} ∈ clS, x_{2} ∈ intS, λ ∈ (0; 1) pak λx_{1} + (1 − λ)x_{2} ∈ intS.

Konvexní obal množiny: convS je nejmenší konvexní množina, která obsahuje S. Konvexní obal S je dán průnikem všech konvexních množin obsahujících S. Konvexní obal S je roven množině všech konvexních kombinací bodů z S.

2.2 Věty o oddělitelnosti

Věta o nejbližším bodu: {} ≠ S ⊂ IR^{n}, uzavřená, konvexní. y ∈ IR^{n} ⇒ ∃!x̂ ∈ S, ∀x ∈ S: ∥ y − x̂ ∥≤∥ y − x ∥ a platí (y − x̂)^{⊤}(x − x̂) ≤ 0.

Oddělitelnost množin: S_{1} a S_{2} jsou neprázdné podmnožiny IR^{n}. Nadrovina H = {x : p^{⊤}x = α} se nazývá:

1. oddělující pro množiny S_{1} a S_{2} ⇔ ∀x ∈ S_{1} : p^{⊤}x ≥ α a současně ∀x ∈ S_{2} : p^{⊤}x ≤ α. Jestliže navíc S_{1} ∪ S_{2} ⊄H, říkáme, že H vlastně odděluje S_{1} a S_{2}.

2. ryze oddělující pro množiny S_{1} a S_{2} ⇔ ∀x ∈ S_{1} : p^{⊤}x > α a současně ∀x ∈ S_{2} : p^{⊤}x < α.

3. silně oddělující pro množiny S_{1} a S_{2} ⇔ ∀x ∈ S_{1} : p^{⊤}x ≥ α + ϵ a současně ∀x ∈ S_{2} : p^{⊤}x ≤ α pro ϵ > 0.

Oddělení bodu a množiny: Nechť {} ≠ S ⊂ IR^{n} je uzavřená konvexní množina a y ∉S. Pak existuje vektor p a skalár α takový, že p^{⊤}y > α a zároveň ∀x ∈ S : p^{⊤}x ≤ α. Důsledkem je, že každá konvexní uzavřená množina je průnikem všech uzavřených poloprostorů, které ji obsahují.

Věta o opěrné nadrovině: Nadrovinu H nazýváme opěrnou nadrovinou k S ⇔ ((S ⊂ H^{+}) ∨ (S ⊂ H^{−})) ∧ (clS ∩ H ≠ {}).

Je-li S konvexní a x ∈ ∂S ⇒ ∃H opěrná pro S a x ∈ H.

Věta o silné oddělitelnosti: S_{1}, S_{2} ⊂ IR^{n} uzavřené, konvexní, S_{1} ∩ S_{2} ≠ {} a dále S_{1} omezená ⇒ ∃H silně oddělující S_{1} a S_{2}.

Úkol: Zdůvodněte předpoklad omezenosti pomocí příkladu. Ilustrujte oddělitelnost na grafických příkladech.

3 Polyedrické množiny

3.1 Polyedr a jeho vlastnosti

Polyedr a simplex: P ⊂ IR^{n} je konvexní polyedr ⇔ ∃S ⊂ IR^{n} taková, že |S| < ℵ_{0} a zároveň convS = P.

Simplex je konvexní polyedr, kde S = {v_{0}, …, v_{m}} a vektory v_{m}−v_{0}, …, v_{1}−v_{0} jsou lineárně nezávislé.

Úkol: Uveďte příklady polyedrů a simplexů v rovině. Ilustrujte graficky.

Caratheodoryho věta: Mějme S ⊂ IR^{n}. Potom ∀x ∈ convS, ∃x_{i} ∈ S, ∃λ_{i} > 0, i = 1, …, m, ∑_{i=1}^{m} λ_{i} = 1 tak, že platí x = ∑_{i=1}^{m} λ_{i}x_{i} a m ≤ n + 1.

Úkol: Vysvětlete tvrzení věty pomocí příkladu.

Krajní body: Mějme S konvexní neprázdnou podmnožinu IR^{n}. x ∈ S je krajní bod ⇔ ∀y_{1}, y_{2} ∈ S, ∀λ ∈ (0; 1) taková, že x = λy_{1}+(1−λ)y_{2} pak platí y_{1} = y_{2} = x.

S omezená konvexní uzavřená množina je konvexní m obalem svých krajních bodů. Konvexní polyedr má konečný počet krajních bodů. Konvexní polyedr je vždy průnikem konečného počtu poloprostorů.

Úkol: Uveďte příklady konvexních množin a jejich krajních bodů. Je průnik konečného počtu uzavřených poloprostorů vždy polyedr?

3.2 Polyedrické množiny a jejich vlastnosti

Polyedrická množina: je průnikem konečného počtu poloprostorů.

Každý polyedr je polyedrickou množinou, ale opak neplatí. Omezená polyedrická množina je polyedr. Polyedrická množina má konečný počet krajních bodů.

Důležité je předeslat, že jak množina přípustných řešení, tak množina optimálních řešení úlohy lineárního programování je polyedrická množina.

Stěna polyedrické množiny je neprázdným průnikem polyedrické množiny a některých nadrovin, které ji vytvářejí.

Hrana je jednorozměrná stěna. Sousední krajní body mají společnou hranu.

Úkol: Uveďte příklady polyedrických množin a polyedrů, nalezněte základní odlišnosti.

Konvexní kužel: Neprázdná množina K ⊂ IR^{n} se nazývá kužel s vrcholem v počátku, pokud ∀α ≥ 0 : x ∈ K ⇒ αx ∈ K. Je-li K konvexní, potom K nazýváme konvexní kužel.

Kužel generovaný S má prvky x = ∑_{i=1}^{m} α_{i}ξ, kde α_{i} ≥ 0 a x_{i} ∈ S. Označujeme jej posS.

Polární kužel: Pro neprázdnou množinu S ⊂ IR^{n} definujeme polární kužel k S, označený S^{∗} := {p|∀x ∈ S : p^{⊤}x ≤ 0}. Je-li S = {}, klademe S^{∗} = IR^{n}.

Úkol: Uveďte příklady kuželů a polárních kuželů. Ukažte, že platí: S^{∗} je uzavřený konvexní kužel. Pro neprázdný konvexní uzavřený kužel K platí K = (K^{∗})^{∗}.

Farkasova věta: Nechť A je matice typu m × n a c je n rozměrný vektor. Potom právě jedna z následujících množin je neprázdná:

1. {x ∈ IR^{n} : Ax ≤ 0 ∧ c^{⊤}x > 0}

2. {y ∈ IR^{m} : A^{⊤}y = c ∧ y ≥ 0}

Úkol: Vysvětlete na obrázku význam Farkasovy věty.

4 Úvod do lineárního programování

4.1 Historie

Starověk: V antice byly formulovány a pomocí geometrie řešeny některé izoperimetrické úlohy. Například: Najděte rovnoběžník největšího obsahu při konstantním obvodu.

Středověk: Později byly formulovány zejména úlohy založené na rozkladu čísel na součet a součin tak, aby určité kritérium mělo optimální hodnotu.

Novověk: S rozvojem infinitesimálního počtu se objevily nyní klasické metody pro analytické hledání extrémů (průběh funkce, úloha o brachystochroně aj.). Následovalo postupné rozpracování teoretických poznatků, které připravilo nástroje pro 20.století.

20.století: Koncem třicátých letech Kantorovič formuloval ekonomickou úlohu pomocí lineárních omezení. Během druhé světové války byly rozpracovány základy matematických metod organizace vojenských operací. V roce 1941 Hitchcock formuloval dopravní úlohu, v roce 1945 formuloval Stiegler dietní problém. V roce 1947 Dantzig formuloval úlohu později nazvanou Koopmansem úlohou lineárního programování. Navrhl algoritmus nazvaný simplexová metoda pro její řešení. V diskusi Dantziga a Von Neumanna byl zaveden pojem duality a následovala desetiletí bouřlivého rozvoje optimalizačních modelů a metod a jejich aplikací.

4.2 Úloha lineárního programování

Zavedení: Úlohou lineárního programování rozumíme hledání optimálního řešení, což je prvek množiny:

? ∈ argmin_{x}{c^{⊤}x|Ax ∘ b}  (1)

kde ∘ ∈ {≤, =, ≥}^{n}.

Prvky úlohy: z = c^{⊤}x nazýváme účelovou funkcí, Ax ∘ b omezeními.

Grafické řešení: Pokud lze úlohu lineárního programování převést na úlohu se dvěma (třemi) neznámými, lze ji řešit graficky.

Úkol: Řešte příklad graficky:

max x_{1} − x_{2}
x_{1} + x_{2} ≥ 0
2x_{1} − x_{2} ≤ 2
x_{1}  ≥ 0

4.3 Typické aplikace

Následující úlohy lze formulovat jako úlohy lineárního programování:

Výrobní plán: Cílem je určit, kolik vyrábět kterého výrobku tak, abychom maximalizovali zisk. Víme, kolik které suroviny potřebujeme na jednotlivé výrobky. Známe množství surovin, která máme k dispozici.

Dopravní plán: Cílem je určit kolik kterých výrobků přepravovat po jednotlivých trasách od výrobců ke spotřebitelům tak, abychom měli co nejnižší náklady.

Směšovací problém: Chceme vyrobit slitinu předepsaného složení ze surovin se známým složením tak, abychom dodrželi metalurgické předpisy a minimalizovali náklady.

Řízení zásob: Cílem je plánovat nákupy tak, abychom uspokojili poptávku a přitom minimalizovali náklady na uskladnění.

Regresní analýza: Cílem je proložit naměřenými hodnotami přímku tak, abychom minimalizovali maximální absolutní odchylku.

Další aplikace: Lineární programování má aplikace především v technologii (řízení výroby), ekonomice (finanční modely) a konstruování (návrh struktury).

Úkol: Vyhledejte konkrétní aplikace. Slovní zadání formulujte matematicky.

4.4 Modelování

Obvyklý postup při modelování je:

1. Zjištění cíle modelu, sběr informací a dat.

2. Volba proměnných, vymezení vstupních dat. Ověření předpokladů určitosti dat, dělitelnosti hodnot proměnných, linearity.

3. Určení účelové funkce.

4. Volba omezení, rozlišení "hard" a "soft" omezení.

5. Sestavení a testování jednoduchého malého modelu.

6. Postupné přibližování modelu realitě, jeho úpravy.

Úkol: Vytvořte několik variant modelu složitějšího příkladu. Najděte vlastní užitečná pravidla pro tvorbu modelů.

4.5 Software

Knihovny podprogramů: Většina knihoven numerických podprogramů obsahuje obvykle implementaci simplexové metody (Numerical Recipes, NAG Library aj.)

Tabulkové procesory: Zahrnují řešiče LP většinou do 200 proměnných.

Matematické programy: Statgraphics, MatLab, Mathematica, Maple obsahují příkazy pro řešení úloh LP.

Řešiče: Specializované programy schopné řešit rozsáhlé problémy (CPLEX, LAMPS, OSL, XA, X-PRESS). Vstupem data v MPS formátu. Více prameny autorů Shardy a Morého.

Modelovací jazyky: Programovací jazyky pro optimalizační úlohy (GAMS, AMPL). Viz český manuál GAMS.

Uživatelská rozhraní: Usnadňují vstup dat a vyhodnocení výstupu z modelovacích jazyků (AIMMS).

Úkol: Navržené modely implementujte a řešte s použitím systému GAMS.

5 Teoretické základy lineárního programování

5.1 Transformace úlohy lineárního programování

Standardní tvar: Následující úlohu lineárního programování nazýváme úlohou ve standardním tvaru:

? ∈ argmin_{x}{c^{⊤}x|Ax = b, x ≥ 0}  (2)

Poznamenejme, že vhodným násobením jednotlivých omezení −1 můžeme docílit, aby navíc b ≥ 0.

Úlohu převádíme na standardní tvar, abychom mohli s rovnicemi pracovat jednodušeji než s nerovnicemi. Dále S = {x|Ax = b, x ≥ 0} je polyedrická množina, a toho rovněž využijeme.

Obecnou úlohu LP řešíme tak, že ji převedeme na standardní tvar, tu potom vyřešíme a získané řešení zpět transformujeme na řešení obecné úlohy.

Úkol: Kdy lze převést úlohu LP na standardní tvar? Převeďte na standardní tvar úlohu:

min x_{1} − x_{2}
x_{1} + x_{2} ≥ 0
2x_{1} − x_{2} ≤ 2
x_{1}  ≥ 0

Změna účelové funkce: Platí: max_{x}{f(x)|x ∈ C} = −min_{x}{−f(x)|x ∈ C}. Dále

argmax_{x}{f(x)|x ∈ C} = argmin_{x}{−f(x)|x ∈ C}. Pak max x_{1} − x_{2} nahradíme min −x_{1} + x_{2}.

Podmínky nezápornosti: Každé reálné číslo můžeme vyjádřit nejednoznačně jako rozdíl dvou nezáporných čísel, např. −3 = 0 − 3 = 2 − 5. Proto je-li x_{j} ∈ IR, použijeme substituci x_{j} = x_{j}^{+}−x_{j}^{−}, kde x_{j}^{+}, x_{j}^{−} ≥ 0. Tedy x_{2} = x_{2}^{+}−x_{2}^{−}. Po dosazení dostáváme:

min −x_{1} + x_{2}^{+} − x_{2}^{−}
x_{1} + x_{2}^{+} − x_{2}^{−} ≥ 0
2x_{1} − x_{2}^{+} + x_{2}^{−} ≤ 2
x_{1}, x_{2}^{+}, x_{2}^{−}  ≥ 0

Získání rovnic: Rozdíly mezi levou a pravou stranou nerovnic vyjádříme pomocí doplňkových proměnných (slack variable) a tím získáme omezení ve tvaru rovnic. A tedy pro náš příklad máme:

min −x_{1} + x_{2}^{+} − x_{2}^{−}
x_{1} + x_{2}^{+} − x_{2}^{−} − x_{3} = 0
2x_{1} − x_{2}^{+} + x_{2}^{−} + x_{4} = 2
x_{1}, x_{2}^{+}, x_{2}^{−}, x_{3}, x_{4} ≥ 0

A maticově:

min( −1 1 −1 0 0 ) x

( \begin{matrix}1 & 1 & −1 & −1 & 0 \\ 2 & −1 & 1 & 0 & 1 \end{matrix} ) x = ( \begin{matrix}0 \\ 2 \end{matrix} )
x  ≥ 0

5.2 Množina přípustných řešení

Existence optima: Nechť je dána úloha lineárního programování ve standardním tvaru a dále S ≠ {} a ∃γ ∈ IR, ∀x ∈ S : c^{⊤}x ≥ γ ⇒ ∃x_{min} ∈ argmin{c^{⊤}x|Ax = b, x ≥ 0}. Uvedené minimum je globální.

Krajní směry: Nechť {} ≠ M ⊂ IR^{n} je uzavřená konvexní množina. 0 ≠ d ∈ IR^{n} nazýváme směr v M ⇔ ∀x ∈ M, ∀α ≥ 0 : x + αd ∈ M.

Dva směry d_{1}, d_{2} v M nazýváme vzájemně různé ⇔ ∀α > 0 : d_{1} ≠ αd_{2}.

Směr d ∈ M se nazývá krajní směr M ⇔ když jej nelze vyjádřit jako kladnou lineární kombinaci dvou vzájemně různých směrů v M. Tj. je-li d = α_{1}d_{1} + α_{2}d_{2}, kde α_{1}, α_{2} ⇒ d_{1} = αd_{2}, kde α > 0.

Charakteristika krajních bodů: Nechť S = {x|Ax = b, x ≥ 0}, h(A) = m, kde m je počet řádků matice A. x je krajní bod S ⇔ po přeskládání sloupců matice A (a odpovídajících složek vektoru x) lze matici A vyjádřit jako A = (B, N) tak, že platí:

x = ( \begin{matrix}x_{B} \\ x_{N} \end{matrix} ) ( \begin{matrix}B^{−1}b \\ 0 \end{matrix} )

kde B je regulární a splňuje B^{−1}b ≥ 0.

Podrobný příklad:

max 4x_{1} − 3x_{2}
x_{1} + x_{2} ≤ 40
2x_{1} + x_{2} ≤ 60
x_{1}, x_{2} ≥ 0

Vyřešte si také graficky. Převedeme na standardní tvar:

min( −4 −3 0 0 ) x

( \begin{matrix}1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{matrix} ) x = ( \begin{matrix}40 \\ 60 \end{matrix} )
x  ≥ 0

Následující tabulka uvádí přehled bázických proměnných x_{B} a nebázických proměnných x_{N}, bázickou matici B a odpovídající bázické řešení x. Dále je uvedeno, zda bázické řešení je přípustné (tj. splňuje x ≥ 0). Zkratka BFS značí basic feasible solution. Dále uvádíme body definované na grafu bázickými řešeními, je uvedeno, zda body jsou krajní, a kterými aktivními omezeními jsou určeny.

x_{B}  x_{N}  B  x  BFS graf krajní? omezení
x_{1}, x_{2} x_{3}, x_{4} ( \begin{matrix}1 & 1 \\ 2 & 1 \end{matrix} ) (20, 20, 0, 0) ano E  ano AEB, CED
x_{1}, x_{3} x_{2}, x_{4} ( \begin{matrix}1 & 1 \\ 2 & 0 \end{matrix} ) (30, 0, 10, 0) ano C  ano CED, ACF
x_{1}, x_{4} x_{2}, x_{3} ( \begin{matrix}1 & 0 \\ 2 & 1 \end{matrix} ) (40, 0, 0, −10) ne A  ne  ABD, ACF
x_{2}, x_{3} x_{1}, x_{4} ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) (0, 60, −20, 0) ne D  ne  CED, DBF
x_{2}, x_{4} x_{1}, x_{3} ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) (0, 40, 0, 20) ano B  ano AEB, DBF
x_{3}, x_{4} x_{1}, x_{2} ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) (0, 0, 40, 60) ano F  ano DBF, ACF

Úkol: Vypočtěte některá bázická řešení uvedená v tabulce. Sestavte podobnou tabulku pro příklad:

max 5x_{1} + 2x_{2}
x_{1} + x_{2} ≤ 6
x_{1} − x_{2} ≤ 0
x_{1}, x_{2} ≥ 0

Všimněte si odlišností mezi tabulkami.

Poznámky:

1. Bázické proměnné jednoznačně určují submatici B.

2. B^{−1}b může dát stejné výsledky pro B určené různými bázickými proměnnými.

3. Jsou-li stejná bázická řešení pro různé bázické proměnné hovoříme o degeneraci úlohy LP. Je-li složka odpovídající bázické proměnné nulová, pak je úloha LP degenerovaná.

4. Bázickému řešení odpovídá průsečík nadrovin určených aktivními omezeními.

5. Bázickému přípustnému řešení odpovídá krajní bod .

Počet krajních bodů: Množina S má nejvýše (m^{n}) krajních bodů.

Existence krajních bodů: Nechť S ≠ {}, h(A) = m, pak S má alespoň 1 krajní bod.

Charakteristika krajních směrů: S ≠ {}, h(A) = m. d je krajní směr S ⇔ Po přeskládání sloupců matice A a odpovídajících složek d lze A vyjádřit ve tvaru A = (B, N) tak, že B^{−1}a_{j} ≤ 0 pro některý sloupec a_{j} matice IN a platí:

d = α ( \begin{matrix}−B^{−1}a_{j} \\ e_{j} \end{matrix} )

kde α > 0 a e_{j} = (e_{j,1}, …, e_{j,n−m}) a dále e_{j,j} = 1 a e_{j,i} = 0 pro i ≠ j.

Počet krajních směrů: Množina S má nejvýše (m^{n}).(n − m) krajních směrů.

Existence krajních směrů: S ≠ {} je neomezená ⇔ obsahuje alespoň 1 krajní směr.

5.3 Základní věty lineárního programování

Věta o reprezentaci: S ≠ {}, h(A) = m, nechť x_{1}, …, x_{k} jsou všechny krajní body S a d_{1}, …, d_{l} všechny krajní směry S. Pak platí x ∈ S ⇔ ∃λ_{i} ≥ 0, ∑_{i=1}^{k} λ_{i} = 1, ∃μ ≥ 0 tak, že

x = ∑_{i=1}^{k} λ_{i}x_{i} + ∑_{j=1}^{l} μ_{j}d_{j}  (3)

Základní věta lineárního programování: Mějme úlohu lineárního programování ve standardním tvaru, h(A) = m, S ≠ {}. Nechť x_{1}, …, x_{k} jsou všechny krajní body S a d_{1}, …, d_{l} všechny krajní směry S.

Pak existuje optimální řešení x_{min} ∈ S ⇔ ∀j = 1, …, k : c^{⊤}d_{j} ≥ 0.

Jestliže existují optimální řešení, pak existuje mezi nimi alespoň jeden krajní bod.

Úplná enumerace: Je-li S omezená, stačí vyčíslit a porovnat c^{⊤}x pro všechny krajní body. Je-li S neomezená, musíme uvažovat i všechny krajní směry pro jednotlivé body. Tato metoda je nerealizovatelná i pro malé úlohy (pro 20 proměnných a 10 omezení máme horní odhad počtu krajních bodů 184756).