Pokus o lepší vysvětlení Lineárního programování než od 🅱urdíka

Co je lineární programování?

Lineární programování, příhodněji také zvané lineární optimalizace, je teorie řešení optimalizačních úloh, které mají lineární charakter, tedy jsou zadané v podobě lineárních rovnic a nerovnic. Název „programování“ je historický a nemá nic společného se současným použitím tohoto slova.

Nejpoužívanějším postupem k řešení základních úloh lineárního programování je simplexová metoda (viz níže), také zvaná simplexový algoritmus. Název odpovídá geometrické představě, kde se pohybujeme po vrcholech nějakého konvexního mnohostěnu a snažíme se najít ten, který „trčí nejdál“ do nějakého směru. Účetní se dříve učili počítat velké simplexové tabulky (aniž by znali teorii za nimi), dnes už k tomu naštěstí máme počítače.

Značení

Na rozdíl od ostatních materiálů jasně značím, co je vektor (šipkou) a co matice (tučně). Symbol $∴$ znamená „proto“ a $∵$ znamená „protože“. Jinak by tu asi nemělo být nic překvapivého.

Simplexová metoda

Jelikož chceme optimalizovat něco s vektory, asi by mohl být dobrý nápad si nejprve zavést, jak se porovnávají. Uděláme to naprosto zřejmým způsobem:

Definice. Nechť

n \in ℕ^{+}

. Nerovnost vektorů z

ℝ^{n}

definujeme takto:

\vec{x} ⋚ \vec{y} \overset{\overset{}{def}}{\Leftrightarrow} (\forall i \in \hat{n}) (x_{i} ⋚ y_{i})

Poznámka. Takto definované uspořádání je částečné uspořádání, ale pro

n > 1

není úplné uspořádání, protože například vektory

{\vec{e}}_{1}

{\vec{e}}_{2}

jsou neporovnatelné.

Poznámka. Relace

\geq

v tomto případě neznamená doslova „větší nebo rovno“. Například platí

{\vec{e}}_{2} \geq \vec{0}

, ale neplatí

{\vec{e}}_{2} > \vec{0} \lor {\vec{e}}_{2} = \vec{0}

Tato nerovnost se v určitých ohledech chová jako nerovnost čísel. Asi není potřeba dokazovat reflexivitu, antisymetrii, tranzitivitu, přičítání nuly a podobné věci. Něco, co by nemuselo být úplně zřejmé, je násobení:

Věta (násobení nerovnosti vektorem). Nechť

\vec{u}, \vec{v}, \vec{w} \in ℝ^{n}, \vec{u} \geq \vec{v}, \vec{w} \geq \vec{0}

. Potom

{\vec{u}}^{T} \vec{w} \geq {\vec{v}}^{T} \vec{w}

Důkaz. Jelikož pro všechna

i \in \hat{n}

platí

u_{i} \geq v_{i} \land w_{i} \geq 0

, máme

u_{i} w_{i} \geq v_{i} w_{i}

. Z toho plyne

{\vec{u}}^{T} \vec{w} = \sum_{i = 1}^{n} u_{i} w_{i} \geq \sum_{i = 1}^{n} v_{i} w_{i} = {\vec{v}}^{T} \vec{w} ■

Nyní už přejděme k lineárnímu programování. Problémy, je kterými se v něm setkáme, můžou mít rozličné tvary, takže podrobně analyzujeme jeden, se kterým se dobře pracuje, a následně si ukážeme, že spousta ostatních se na něj dá převést.

Definice. Mějme

m, n \in ℕ^{+}, 𝐀 \in ℝ^{m \times n}, \vec{b} \in ℝ^{m}, \vec{c} \in ℝ^{n}

. Primární úloha lineárního programování je následující optimalizační úloha:

\min {{\vec{c}}^{T} \vec{x} | \vec{x} \in ℝ^{n}, 𝐀 \vec{x} = \vec{b}, \vec{x} \geq \vec{0}}

Funkce

\vec{x} \mapsto {\vec{c}}^{T} \vec{x}

, kterou chceme optimalizovat, se nazývá účelová funkce.

Poznámka. Písmeno

b

je čteno důrazně [ˈbɞ]. Jakákoli jiná výslovnost je špatně a budete za ni okamžitě vyhozeni od zkoušky.

Definice. Přípustné řešení primární úlohy lineárního programování je jakýkoli vektor

\vec{x} \in ℝ^{n}

splňující

𝐀 \vec{x} = \vec{b} \land \vec{x} \geq \vec{0}

Definice. Optimální řešení primární úlohy lineárního programování je přípustné řešení, pro které je

{\vec{c}}^{T} \vec{x}

minimální.

Možných přípustných řešení může být celkem hodně (konkrétně nespočetně mnoho), takže zkoušet postupně všechny by asi nebyl úplně nejlepší přístup. Naštěstí se ukazuje, že se stačí zajímat o tzv. bazická řešení:

Definice. Bazické řešení primární úlohy lineárního programování je přípustné řešení, pro které jsou sloupce

{{\vec{A}}_{\circ j} | x_{j} > 0}

lineárně nezávislé.

Věta (Rohn 1). Pokud má primární úloha lineárního programování optimální řešení, potom má bazické optimální řešení.

Důkaz. Předpokládejme, že úloha má optimální řešení

\vec{x}

, které není bazické. Nechť

J ≔ {j \in \hat{n} | x_{j} > 0}

. Z definice nebazického řešení a lineární závislosti existují taková

y_{j}, j \in J

, že alespoň jedno

y_{j_{0}}

je nenulové a

\sum_{j \in J} y_{j} {\vec{A}}_{\circ j} = 0

Předpokládejme bez újmy na obecnosti, že

y_{j_{0}} > 0

, a pro

j \in \hat{n} ∖ J

(tedy

x_{j} = 0

) dodefinujme

y_{j} ≔ 0

. Zřejmě potom

𝐀 \vec{y} = \vec{0}

. Nyní dokážeme sporem, že

{\vec{c}}^{T} \vec{y} = 0

Nechť ${\vec{c}}^{T} \vec{y} < 0$ . Jelikož všechny složky $\vec{x}$ odpovídající nenulovým složkám $y$ jsou kladné, pro nějaké dostatečně malé $α \in ℝ^{+}$ bude platit $\vec{x} + α \vec{y} \geq 0$ . Máme: $𝐀 (\vec{x} + α \vec{y}) = 𝐀 \vec{x} + α 𝐀 \vec{y} = \vec{b} + \vec{0} = \vec{b}$ ${\vec{c}}^{T} (\vec{x} + α \vec{y}) = {\vec{c}}^{T} \vec{x} + α {\vec{c}}^{T} \vec{y} \overset{p o d l e p \overset{ˇ}{r} e d p o k l a d u}{<} {\vec{c}}^{T} \vec{x}$ Tedy $\vec{x} + α \vec{y}$ je přípustné řešení lepší než $\vec{x}$ , což se spor s optimalitou $\vec{x}$ .
Pro ${\vec{c}}^{T} \vec{x} > 0$ analogicky, akorát zvolíme $α \in ℝ^{-}$ .

Nyní definujme

ε^{*} ≔ \min {- \frac{x_{j}}{y_{j}} | y_{j} < 0}

{\vec{x}}^{'} ≔ \vec{x} + ε^{*} \vec{y}

Snadno ověříme, že jde také o optimální řešení. (Při důkazu optimality využijeme předchozí výsledek

{\vec{c}}^{T} \vec{y} = 0

.) Zároveň z definice

ε^{*}

existuje takové

k

, že

ε^{*} = - \frac{x_{k}}{y_{k}}

. To znamená, že

x_{k}^{'} = 0

, tedy jsme z

\vec{x}

odstranili jednu nenulovou složku. To můžeme opakovat, až se z

\vec{x}

stane bazické řešení. ■

Nyní zavedeme značení, které nám z matice umožní vybírat pouze některé sloupce. Toto značení se ukáže jako velmi užitečné v dalších větách.

Definice. Nechť

B \in {\hat{n}}^{m}

obsahuje vzájemně různá čísla. Potom značíme

𝐀_{B} ≔ (\begin{array}{ccc} {\vec{A}}_{\circ B_{1}} & \dots & {\vec{A}}_{\circ B_{m}} \end{array})

{\vec{x}}_{B} ≔ (\begin{array}{c} x_{B_{1}} \\ ⋮ \\ x_{B_{m}} \end{array})

Důsledek.

(\forall j \in \hat{m}) ({(𝐀_{B})}_{\circ j} = {\vec{A}}_{\circ B_{j}})

(\forall j \in \hat{m}) ({({\vec{x}}_{B})}_{j} = x_{B_{j}})

Poznámka. Písmeno

B

je čteno důrazně [ˈbɞ] (tedy stejně jako

b

). Jakákoli jiná výslovnost je špatně a budete za ni okamžitě vyhozeni od zkoušky.

Poznámka. Občas budeme tak trochu zaměňovat, jestli je

B

uspořádaná

m

-tice, nebo množina, ale vždy by mělo být jasné, co se tím myslí.

Definice. Pro

N ≔ \hat{n} ∖ B

analogicky definujeme

𝐀_{N}, {\vec{x}}_{N}

Nyní ukážeme, že mezi bazickými řešeními a $B$ existuje jednoduchý vztah. To je dobrá zpráva, protože možných $B$ je pouze konečně mnoho (i když na řešení hrubou silou jich pořád může být celkem hodně).

Věta (Rohn 2). Nechť

m \leq n

a řádky

𝐀

jsou lineárně nezávislé. Potom

\vec{x}

je bazické řešení právě tehdy, pokud pro nějaké

B

platí:

$𝐀_{B}$ je regulární
$𝐀_{B} {\vec{x}}_{B} = \vec{b}$
${\vec{x}}_{B} \geq \vec{0}$
${\vec{x}}_{N} = \vec{0}$

Důkaz.

(\Rightarrow)

Nechť

\vec{x}

je bazické řešení. To znamená, že sloupce

{{\vec{A}}_{\circ j} | j \in ℕ, x_{j} > 0}

jsou lineárně nezávislé. Také víme, že hodnost matice

𝐀

m

, protože má lineárně nezávislé řádky. Zmíněné sloupce tedy můžeme doplnit na bázi dalšími sloupci, aby jich bylo celkem

m

, a zvolíme

B

jako indexy těchto sloupců. Potom zřejmě platí všechny body. ◧

(\Leftarrow)

Z posledních tří bodů plyne, že řešení je přípustné. Zároveň ze čtvrtého plyne, že

{j \in \hat{n} | x_{j} > 0} \subseteq B

, tedy řešení je podle prvního bodu i bazické. ◨

Definice. Nechť

𝐀_{B}

je regulární a

y ≔ 𝐀_{B}^{- 1} \vec{b} \geq 0

. Potom definujeme

{\vec{x}}^{B}

předpisem

{\vec{x}}_{B}^{B} ≔ \vec{y}

{\vec{x}}_{N}^{B} ≔ \vec{0}

Dobře, můžeme tedy vzít nějaké $B$ a dostaneme bazické řešení ${\vec{x}}^{B}$ , které je kandidátem na optimální řešení. Ale jak poznáme, jestli je to to pravé? Celkem jednoduše:

Věta (Rohn 3, kritérium optimality). Nechť pro nějaké

B

𝐀_{B}

regulární a platí

{\vec{c}}^{T} \geq {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} 𝐀

Potom

{\vec{x}}^{B}

je optimální řešení primární úlohy.

Důkaz. Nechť

\vec{x}

je libovolné přípustné řešení (tedy mimo jiné

\vec{x} \geq \vec{0}

). Přenásobme předpoklad zprava

\vec{x}

{\vec{c}}^{T} \vec{x} \geq {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} 𝐀 \vec{x} \overset{\overset{}{p \overset{ˇ}{r} \overset{ˊ}{ı} p u s t n o s t \vec{x}}}{=} {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} \vec{b} \overset{\overset{}{definice {\vec{x}}^{B}}}{=} {\vec{c}}_{B}^{T} {\vec{x}}_{B}^{B} \overset{\overset{}{{\vec{x}}_{N}^{B} = 0}}{=} {\vec{c}}^{T} {\vec{x}}^{B}

Dokázali jsme, že

{\vec{x}}^{B}

má menší hodnotu účelové funkce než libovolné

\vec{x}

, tedy je optimální. ■

Teď zavedeme taková divná písmena s čarami, jejichž význam je zatím dost nejasný, ale později z nich sestavíme simplexovou tabulku, která bude výrazně ulehčovat hledání správného $B$ a jeho bazického řešení ${\vec{x}}^{B}$ .

Definice. Mějme

B

takové, že

𝐀_{B}

je regulární. Potom definujeme

𝐀 ≔ 𝐀_{B}^{- 1} 𝐀

\vec{\overline{b}} ≔ {\vec{x}}_{B}^{B} = 𝐀_{B}^{- 1} \vec{b}

\vec{\overline{c}} ≔ {\vec{c}}^{T} - {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} 𝐀

\overline{h} ≔ - {\vec{c}}_{B}^{T} {\vec{x}}_{B}^{B} = - {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} \vec{b}

Poznámka. Kritérium optimality se dá přeformulovat jako

\vec{\overline{c}} \geq {\vec{0}}^{T}

Věta.

𝐀_{B} = 𝐈

Důkaz.

𝐀_{B} = 𝐀_{B}^{- 1} 𝐀_{B} = 𝐈 ■

Věta.

{\vec{\overline{c}}}_{B} = {\vec{0}}^{T}

Důkaz.

{\vec{\overline{c}}}_{B} = {\vec{c}}_{B}^{T} - {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} 𝐀_{B} = {\vec{c}}_{B}^{T} - {\vec{c}}_{B}^{T} = {\vec{0}}^{T} ■

Ještě by ale bylo dobré umět poznat, kdy úloha žádné optimální řešení nemá, protože se s účelovou funkcí dokážeme dostat libovolně nízko.

Věta (Rohn 4, kritérium neomezenosti). Nechť pro nějaké

B

existuje

s \in \hat{n}

takové, že

{\overline{c}}_{s} < 0

\vec{z} ≔ {\vec{\overline{A}}}_{\circ s} \leq \vec{0}

. Potom účelová funkce není zdola omezená (a úloha tedy nemá optimální řešení), to znamená

\inf {{\vec{c}}^{T} \vec{x} | \vec{x} \in ℝ^{n}, 𝐀 \vec{x} = \vec{b}, \vec{x} \geq \vec{0}} = - \infty

Důkaz. Již máme dokázáno, že

{\vec{\overline{c}}}_{B} = {\vec{0}}^{T}

, tedy z předpokladu

{\overline{c}}_{s} < 0

plyne

s \notin B

. Definujme

\vec{y} \in ℝ^{n}

\begin{aligned} {\vec{y}}_{B} & ≔ - \vec{z} \\ y_{s} & ≔ 1 \\ {\vec{y}}_{N ∖ {s}} & ≔ 0 \end{aligned}

Pro tento vektor platí

𝐀 \vec{y} = 𝐀_{B} {\vec{y}}_{B} + 𝐀_{N} {\vec{y}}_{N} = - 𝐀_{B} \vec{z} + {\vec{A}}_{\circ s} = - 𝐀_{B} 𝐀_{B}^{- 1} {\vec{A}}_{\circ s} + {\vec{A}}_{\circ s} = 0

Vezměme libovolné

α \in ℝ^{+}

. Dokážeme, že

{\vec{x}}^{B} + α \vec{y}

je přípustné řešení:

𝐀 ({\vec{x}}^{B} + α \vec{y}) = 𝐀 {\vec{x}}^{B} + α 𝐀 \vec{y} = \vec{b} + \vec{0} = \vec{b}

{\vec{x}}^{B} + α \vec{y} \geq α \vec{y} \geq \vec{0} ∵ {\vec{y}}_{B} = - \vec{z} \geq \vec{0}

Nyní zbývá dokázat, že pro dostatečně vysokou hodnotu

α

dokážeme učinit hodnotu

{\vec{c}}^{T} ({\vec{x}}^{B} + α \vec{y})

libovolně nízkou:

\begin{aligned} {\vec{c}}^{T} ({\vec{x}}^{B} + α \vec{y}) \overset{\overset{}{linearita}}{=} & {\vec{c}}^{T} {\vec{x}}^{B} + α {\vec{c}}^{T} \vec{y} \\ \overset{\overset{}{N = \hat{n} ∖ B}}{=} & {\vec{c}}^{T} {\vec{x}}^{B} + α ({\vec{c}}_{B}^{T} {\vec{y}}_{B} + {\vec{c}}_{N}^{T} {\vec{y}}_{N}) \\ \overset{\overset{}{definice \vec{y}}}{=} & {\vec{c}}^{T} {\vec{x}}^{B} + α (- {\vec{c}}_{B}^{T} \vec{z} + c_{s}) \\ \overset{\overset{}{definice \vec{z}}}{=} & {\vec{c}}^{T} {\vec{x}}^{B} + α (c_{s} - {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} {\vec{A}}_{\circ s}) \\ \overset{\overset{}{definice \vec{\overline{c}}}}{=} & {\vec{c}}^{T} {\vec{x}}^{B} + α {\overline{c}}_{s} \end{aligned}

Podle předpokladu je

{\overline{c}}_{s} < 0

, tedy výraz pro

α \to \infty

skutečně jde do

- \infty

. ■

Nyní již přejděme k simplexové tabulce:

Definice. Mějme primární úlohu lineárního programování a nějaké

B

. Simplexová tabulka je tabulka

(m + 1) \times (n + 1)

ve tvaru

(\begin{array}{cc} 𝐀 & \vec{\overline{b}} \\ \vec{\overline{c}} & \overline{h} \end{array})

Poznámka. Jelikož

𝐀_{B} = 𝐈

, platná simplexová tabulka musí v levé horní části obsahovat všechny sloupce jednotkové matice (ne nutně v postupném pořadí); z indexů těchto sloupců pak lze vyčíst

B

. Jelikož

{\vec{\overline{c}}}_{B} = {\vec{0}}^{T}

, pod těmito sloupci budou samé nuly.

Poznámka. Kritérium optimality říká, že pokud v levé dolní části tabulky není žádné záporné číslo, řešení v tabulce je optimální.

Poznámka. Kritérium neomezenosti říká, že pokud nad záporným číslem v levé dolní části není žádné kladné číslo, úloha je neomezená.

Proč takovouto tabulku zavádíme? Ukazuje se, že provádění určitých řádkových úprav v simplexové tabulce odpovídá zkoušení různých $B$ , a již víme, že pokud existuje optimální řešení, potom ho pro nějaké $B$ v tabulce najdeme. Zároveň v pravém dolním rohu najdeme minimální hodnotu účelové funkce (akorát bez mínusu).

Věta (Rohn 5). Mějme nějaké

B

. Upravme původní tabulku

(\begin{array}{cc} 𝐀 & \vec{b} \\ {\vec{c}}^{T} & 0 \end{array})

pomocí řádkových úprav (násobení řádku konstantou a přičtení násobku řádku k jinému) do takové podoby, že pro každé

j \in \hat{m}

se z

B_{j}

-tého sloupce stane

{\vec{e}}_{j}

. Přitom nikdy nebudeme násobit poslední řádek nebo přičítat jeho násobek k jinému. Potom těmito úpravami vznikne simplexová tabulka pro dané

B

Důkaz. Nejprve budeme tvrdit, že vznikne tabulka ve tvaru

(\begin{array}{cc} 𝐏 𝐀 & 𝐏 \vec{b} \\ {\vec{y}}^{T} 𝐀 + {\vec{c}}^{T} & {\vec{y}}^{T} \vec{b} \end{array})

pro nějaká

𝐏 \in ℝ^{m \times m}, \vec{y} \in ℝ^{m}

. To se dá nějak hnusně dokázat přes matice úprav, ale popravdě je to celkem zřejmé, když se nad tím člověk zamyslí. Když to nyní srovnáme s definicí simplexové tabulky, tak vlastně chceme dokázat, že

𝐏 = 𝐀_{B}^{- 1}, \vec{y} = - {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1}

. Tak pojďme na to.

{(𝐏 𝐀)}_{\circ B_{j}} = 𝐏 {\vec{A}}_{\circ B_{j}} = 𝐏 {(𝐀_{B})}_{\circ j} = {(𝐏 𝐀_{B})}_{\circ j} \overset{\overset{}{p \overset{ˇ}{r} e d p o k l a d}}{=} {\vec{e}}_{j} = 𝐈_{\circ j} ∴ 𝐏 𝐀_{B} = 𝐈 ∴ 𝐏 = 𝐀_{B}^{- 1}

{\vec{0}}_{B}^{T} \overset{\overset{}{p \overset{ˇ}{r} e d p o k l a d}}{=} {({\vec{y}}^{T} 𝐀 + {\vec{c}}^{T})}_{B} = {\vec{y}}^{T} 𝐀_{B} + {\vec{c}}_{B}^{T} ∴ {\vec{y}}^{T} 𝐀_{B} = - {\vec{c}}_{B}^{T} ∴ \vec{y} = - {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1}

■

Teď už můžeme přejít k samotnému algoritmu. Myšlenka je taková, že máme simplexovou tabulku s nějakým $B$ a snažíme se ji upravit tak, aby vzniklo jiné $B$ vyhovující podmínce optimality. Budeme to provádět postupně: vždy vybereme jednu složku $B$ , která se nám nelíbí, a nahradíme ji jinou složkou.

Jelikož chceme, aby na spodním řádku nebyla žádná záporná čísla, vybereme jeden sloupec $s$ , který tam má záporné číslo, a nacpeme ho do $B$ , což způsobí, že tam bude mít nulu. Zároveň musíme vybrat řádek $r$ , jehož odpovídající $B_{r}$ z báze vyřadíme. Následně provedeme řádkové úpravy tak, aby bylo ${\vec{A}}_{\circ s} = {\vec{e}}_{r}, c_{s} = 0$ , čímž dostaneme opět platnou simplexovou tabulku s novým $B$ .

Jak vybrat správné $r$ ? Chceme, aby se zvýšilo $\overline{h}$ , protože $- \overline{h}$ je hodnota účelové funkce, kterou chceme minimalizovat. Snadno spočteme, že $\overline{h}$ se po úpravě zvýší o $- \frac{{\overline{b}}_{r} {\overline{c}}_{s}}{{\overline{A}}_{r s}}$ . Víme, že ${\overline{b}}_{r} \geq 0, {\overline{c}}_{s} < 0$ , takže aby přičtený výraz byl nezáporný, potřebujeme ${\overline{A}}_{r s} > 0$ . Ale co když žádné takové $r$ neexistuje? V takovém případě máme dole záporné číslo, nad kterým není žádné kladné číslo, takže úloha je neomezená.

Zároveň si musíme dávat pozor, aby složky $\vec{\overline{b}}$ zůstaly nezáporné. Toho docílíme tím, že si zvolíme takové $r$ , aby $\frac{{\overline{b}}_{r}}{{\overline{A}}_{r s}}$ bylo minimální (důkaz jde snadno rozmyslet).

Tímhle způsobem tedy dokážeme zajistit, aby hodnota účelové funkce po provedení krohu byla větší nebo rovna. Ale jak zajistíme, že se nedostaneme do nekonečné smyčky? Ještě máme určitou volnost ve volbě $s, r$ , a té právě vyuzijeme.

Definice. Cyklus je konečná posloupnost kroků simplexového algoritmu, které začínají i končí stejným

B

Věta. V přůběhu cyklu zůstává poslední sloupec beze změny a v každém kroku platí

{\overline{b}}_{r} = 0

Důkaz.

\overline{h}

se nikdy nemůže snížit, takže během cyklu musí zůstat stejné. Jelikož se snižuje o

\frac{{\overline{b}}_{r} {\overline{c}}_{s}}{{\overline{A}}_{r s}}

, musí být

{\overline{b}}_{r} {\overline{c}}_{s} = 0

, tedy

{\overline{b}}_{r} = 0

. A díky tomu se nezmění ani ostatní složky

\overline{b}

. ■

Věta (Rohn 6, Blandovo pravidlo). Při provádění simplexového algoritmu:

vybereme nejmenší $s$ takové, aby ${\overline{c}}_{s} < 0$ .
vybereme $r$ tak, aby ${\overline{A}}_{r s} > 0$ , z takových $r$ bylo $\frac{{\overline{b}}_{s}}{{\overline{A}}_{r s}}$ minimální a z takových $r$ bylo $B_{r}$ minimální.

Potom se algoritmus nedostane do cyklu.

Důkaz. Nechť

T

je množina všech

s

vstupujících do báze během cyklu (což jsou zároveň všechna

B_{r}

vystupující z báze). Nechť

q ≔ \max (T)

q

bude v nějaké chvíli vstupovat do báze, označme bázi předtím

B_{0}

, s cenovým vektorem

\vec{y}

(tedy

y_{q} < 0

q

bude taky někdy vystupovat z báze, tu označíme

B

, přičemž

q ≕ B_{r}

, a části odpovídající tabulky budeme značit obvyklými písmeny. Nechť v dalším kroku do báze vstupuje sloupec

s

. Definujme

\vec{z} \in ℝ^{n}

podobně jako

\vec{y}

v důkazu kritéria neomezenosti:

\begin{aligned} {\vec{z}}_{B} & ≔ {\vec{\overline{A}}}_{\circ s} \\ z_{s} & ≔ - 1 \\ {\vec{z}}_{N ∖ {s}} & ≔ 0 \end{aligned}

Máme:

𝐀 \vec{z} = 𝐀_{B} {\vec{z}}_{B} - {\vec{A}}_{\circ s} = 𝐀_{B} 𝐀_{B}^{- 1} {\vec{A}}_{\circ s} - {\vec{A}}_{\circ s} = \vec{0}

\begin{aligned} \vec{y} \vec{z} \overset{\overset{}{definice \vec{y}}}{=} & ({\vec{c}}^{T} - {\vec{c}}_{B_{0}} 𝐀_{B_{0}}^{- 1} 𝐀) \vec{z} \\ \overset{\overset{}{𝐀 \vec{z} = \vec{0}}}{=} & {\vec{c}}^{T} \vec{z} \\ \overset{\overset{}{definice \vec{z}}}{=} & {\vec{c}}_{B}^{T} {\vec{\overline{A}}}_{\circ s} - c_{s} \\ \overset{\overset{}{definice \overline{\vec{c}}}}{=} & - {\overline{c}}_{s} > 0 \end{aligned}

Jelikož skalární součin

\vec{y} \vec{z}

je kladný, musí být

(\exists k \in \hat{n}) (y_{k} z_{k} > 0)

. Z

y_{k} \neq 0

plyne

k \notin B_{0}

. Ze

z_{k} \neq 0

plyne

k \in B \lor k = s

. Každopádně

k \in T

. Dále

y_{q} z_{q} = y_{q} {\overline{A}}_{r s} < 0

, protože podle simplexového algoritmu je

y_{q} < 0, A_{r s} > 0

. Z toho plyne

k \neq q

. Rozlišíme dva případy:

Pokud $y_{k} < 0$ , měli jsme podle Blandova pravidla pro vstup místo $q$ vybrat $k$ , protože z definice $q$ je $k < q$ . To je spor. ◧
Pokud $y_{k} > 0$ , potom také $0 < z_{k} ≕ z_{B_{p}} \overset{\overset{}{definice \vec{z}}}{=} A_{p s}$ . Jelikož $y_{s}$ je z definice záporné, nemůže být $k = s$ , tedy $k \in B$ . Protože zároveň $k \notin B_{0}$ , muselo $k$ někdy v průběhu cyklu vstoupit do báze, tedy podle předchozí věty je ${\overline{b}}_{p} = 0$ . Tedy $p$ -tý řádek má minimální $\frac{{\overline{b}}_{j}}{{\overline{A}}_{j s}}$ ze všech řádků, kde ${\overline{A}}_{j s} > 0$ , což ho kvalifikuje pro výběr pivota. Podle předpokladu je $k < q$ , tedy podle Blandova pravidla jsme pro výstup neměli vybrat $q$ , nýbrž $k$ , což je spor. ◨

Pokud $𝐀$ obsahuje jednotkovou matici, můžeme rovnou použít simplexovou metodu a úlohu vyřešit. Ale co když ne? V takovém případě použijeme dvoufázovou simplexovou metodu. Nejprve si zavedeme $m$ umělých proměnných, abychom do tabulky jednotkovou matici dostali. Chceme ovšem, aby ve výsledku měly všechny hodnotu $0$ . To zajistíme tak, že nejprve budeme (pomocí simplexové metody) minimalizovat součet těchto umělých proměnných. Tedy vytvoříme pomocné $\vec{c}$ , od kterého musíme ještě odečíst všechny řádky matice, aby na správných místech obsahovalo nuly. Pokud se nám podaří pomocnou účelovou funkci dostat na nulu, dostali jsme přípustné řešení, které neobsahuje umělé proměnné, takže je můžeme odstranit a pokračovat (akorát musíme přepočítat spodní řádek). Pokud se nepodaří umělou účelovou funkci dostat na nulu, znamená to, že úloha žádné přípustné řešení nemá.

Věta (Rohn 7). Pokud má primární úloha lineárního programování přípustné řešení, potom buď má optimální řešení, nebo je zdola neomezená.

Důkaz. Simplexový algoritmus s použitím Blandova pravidla se vždy zastaví a buď nahlásí, že úloha je neomezená, nebo vrátí optimální řešení. ■

Věta (Rohn 8, množina optimálních řešení). Je-li v simplexové tabulce

\vec{\overline{c}} \geq 0

, potom nějaké

{\vec{x}}^{*} \in ℝ^{n}

je optimální řešení právě tehdy, pokud

$𝐀 {\vec{x}}^{*} = \vec{\overline{b}}$
$\vec{\overline{c}} {\vec{x}}^{*} = 0$
${\vec{x}}^{*} \geq 0$

Důkaz.

(\Rightarrow)

𝐀 {\vec{x}}^{*} = 𝐀_{B}^{- 1} 𝐀 {\vec{x}}^{*} \overset{\overset{}{p \overset{ˇ}{r} \overset{ˊ}{ı} p u s t n o s t}}{=} 𝐀_{B}^{- 1} \vec{b} = \vec{\overline{b}}

\vec{\overline{c}} {\vec{x}}^{*} = ({\vec{c}}^{T} - {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} 𝐀) {\vec{x}}^{*} \overset{\overset{}{p \overset{ˇ}{r} \overset{ˊ}{ı} p u s t n o s t}}{=} {\vec{c}}^{T} {\vec{x}}^{*} - {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} \vec{b} = \overline{h} - \overline{h} = 0

◧

(\Leftarrow)

Přípustnost:

𝐀 {\vec{x}}^{*} = 𝐀_{B} 𝐀 {\vec{x}}^{*} \overset{\overset{}{p \overset{ˇ}{r} e d p o k l a d}}{=} 𝐀_{B} \vec{\overline{b}} = \vec{b}

, optimalita:

0 = \vec{\overline{c}} {\vec{x}}^{*} \overset{\overset{}{n \overset{ˇ}{e} k o l i k d e f i n i c}}{=} {\vec{c}}^{T} {\vec{x}}^{*} - {\vec{c}}_{B}^{T} {\vec{x}}_{B}^{B} = {\vec{c}}^{T} {\vec{x}}^{*} - \overline{h}

◨

Věta (Rohn 9). Je-li v simplexové tabulce

\vec{{\overline{c}}_{N}} > 0

, potom má úloha právě jedno optimální řešení (a to

{\vec{x}}^{B}

Důkaz. Nechť

{\vec{x}}^{*}

je optimální řešení. Potom

0 = \vec{\overline{c}} {\vec{x}}^{*} \overset{\overset{}{? ? ?}}{=} {\vec{c}}_{N}^{T} {\vec{x}}_{N}^{*}

. Aby to mohlo zároveň s predpokladem platit, musí být

{\vec{x}}_{N}^{*} = \vec{0}

. Z toho plyne

\vec{b} = 𝐀 {\vec{x}}^{*} = 𝐀_{B} {\vec{x}}_{B}^{*} + 𝐀_{N} {\vec{x}}_{N}^{*} = 𝐀_{B} {\vec{x}}_{B}^{*}

Z toho plyne

{\vec{x}}_{B}^{*} = 𝐀_{B}^{- 1} \vec{b}, {\vec{x}}_{N}^{*} = \vec{0}

, tedy

{\vec{x}}^{*} = {\vec{x}}^{B}

. ■

Teorie duality

Definice. Duální úloha lineárního programování je následující optimalizační úloha:

\max {{\vec{b}}^{T} \vec{y} | \vec{y} \in ℝ^{m}, 𝐀^{T} \vec{y} \leq \vec{c}}

Poznámka. Povšimněme si, že jde o jakousi „transponovanou“ verzi primární úlohy, kde se navíc nepožaduje nezápornost a z rovnosti se stává nerovnost.

Věta (Rohn 10, o slabé dualitě). Nechť

\vec{x}, \vec{y}

jsou přípustná řešení primární a duální úlohy. Potom

{\vec{c}}^{T} \vec{x} \geq {\vec{b}}^{T} \vec{y}

. Navíc pokud

{\vec{c}}^{T} \vec{x} = {\vec{b}}^{T} \vec{y}

, potom jde o optimální řešení.

Důkaz.

{\vec{c}}^{T} \vec{x} = {\vec{x}}^{T} \vec{c} \overset{p \overset{ˇ}{r} \overset{ˊ}{ı} p u s t n o s t}{\geq} {\vec{x}}^{T} 𝐀^{T} \vec{y} = {(𝐀 \vec{x})}^{T} \vec{y} \overset{\overset{}{p \overset{ˇ}{r} \overset{ˊ}{ı} p u s t n o s t}}{=} {\vec{b}}^{T} \vec{y}

Tím je hotová první část. Nechť nyní pro nějaká

{\vec{x}}^{*}, {\vec{y}}^{*}

platí rovnost. Dokážeme, že jsou lepší než libovolná přípustná řešení

\vec{x}, \vec{y}

{\vec{c}}^{T} \vec{x} \geq {\vec{b}}^{T} {\vec{y}}^{*} \overset{\overset{}{p \overset{ˇ}{r} e d p o k l a d}}{=} {\vec{c}}^{T} {\vec{x}}^{*}

{\vec{b}}^{T} \vec{y} \leq {\vec{c}}^{T} {\vec{x}}^{*} \overset{\overset{}{p \overset{ˇ}{r} e d p o k l a d}}{=} {\vec{b}}^{T} {\vec{y}}^{*}

■

Věta (Rohn 11). Je-li

{\vec{x}}^{B}

optimální řešení primární úlohy nalezené simplexovým algoritmem, potom

{\vec{y}}^{*} ≔ {(𝐀_{B}^{T})}^{- 1} {\vec{c}}_{B}

je optimální řešení duální úlohy a platí

{\vec{c}}^{T} {\vec{x}}^{B} = {\vec{b}}^{T} {\vec{y}}^{*}

Důkaz. Podle kritéria optimality:

\vec{0} \leq \vec{\overline{c}} = {\vec{c}}^{T} - {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} 𝐀 = {\vec{c}}^{T} - {({(𝐀_{B}^{T})}^{- 1} {\vec{c}}_{B})}^{T} 𝐀 = {\vec{c}}^{T} - {\vec{y}}^{* T} 𝐀 = {(\vec{c} - 𝐀^{T} {\vec{y}}^{*})}^{T} ∴ 𝐀^{T} {\vec{y}}^{*} \leq \vec{c}

To znamená, že

{\vec{y}}^{*}

je přípustné řešení duální úlohy. Nyní stačí dokázat

{\vec{c}}^{T} {\vec{x}}^{B} = {\vec{b}}^{T} {\vec{y}}^{*}

, jelikož podle slabé věty o dualitě už bude jasné, že jde o optimální hodnotu.

{\vec{c}}^{T} {\vec{x}}^{B} \overset{\overset{}{definice x^{B}}}{=} {\vec{c}}_{B}^{T} {\vec{x}}_{B}^{B} = {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} \vec{b} \overset{\overset{}{v i z v \overset{ˊ}{y} \overset{ˇ}{s} e}}{=} {\vec{y}}^{* T} \vec{b} = {\vec{b}}^{T} {\vec{y}}^{*} ■

Věta (Rohn 12, o dualitě). Primární úloha lineárního programování má optimální řešení právě tehdy, pokud ho má duální úloha. V tom případě jsou optimální hodnoty stejné.

Důkaz.

(\Rightarrow)

Pokud má primární úloha optimální řešení, najdeme ho pomocí simplexové metody a podle předchozí věty k němu najdeme optimální řešení duální úlohy. ◧

(\Leftarrow)

Nechť má duální úloha optimální řešení. Sestavíme pomocnou primární úlohu:

\min {(\begin{array}{ccc} - {\vec{b}}^{T} & {\vec{b}}^{T} & {\vec{0}}^{T} \end{array}) {\vec{y}}^{'} | {\vec{y}}^{'} \in ℝ^{2 m + n}, (\begin{array}{ccc} 𝐀^{T} & - 𝐀^{T} & 𝐈 \end{array}) {\vec{y}}^{'} = \vec{c}, {\vec{y}}^{'} \geq 0}

Dá se rozmyslet, že takováto úloha má optimální řešení

(\begin{array}{c} {\vec{y}}_{+} \\ - {\vec{y}}_{-} \\ \vec{c} - 𝐀^{T} {\vec{y}}_{+} - 𝐀^{T} {\vec{y}}_{-} \end{array})

, kde

{\vec{y}}_{+}

\vec{y}

se zápornými složkami nahrazenými nulou a analogicky

{\vec{y}}_{-}

. To znamená, že optimální řešení má i pomocná duální úloha:

\max {{\vec{c}}^{T} x^{'} | {\vec{x}}^{'} \in ℝ^{n}, (\begin{array}{c} 𝐀 \\ - 𝐀 \\ 𝐈 \end{array}) {\vec{x}}^{'} \leq (\begin{array}{c} - \vec{b} \\ \vec{b} \\ \vec{0} \end{array})}

Když vezmeme

\vec{x} ≔ - {\vec{x}}^{'}

, vidíme, že vlastně jde o primární úlohu. ◨

Věta (Rohn 13). Pokud jsou primární i duální úloha přípustné, potom obě mají optimální řešení a stejnou optimální hodnotu.

Důkaz. Nechť

\vec{y}

je nějaké přípustné řešení duální úlohy. Potom podle slabé věty o dualitě pro všechna přípustná řešení

\vec{x}

primární úlohy platí

{\vec{c}}^{T} \vec{x} \geq {\vec{b}}^{T} \vec{y}

, tedy primární úloha je zdola omezená a pomocí simplexové metody můžeme najít optimální řešení. Podle věty o dualitě má optimální řešení i duální úloha a jejich hodnoty se rovnají. ■

Věta (Rohn 14). Vektory

\vec{x}, \vec{y}

jsou optimální řešení primární a duální úlohy právě tehdy, pokud platí:

$𝐀 \vec{x} = \vec{b}$
$\vec{x} \geq \vec{0}$
$𝐀^{T} \vec{y} \leq \vec{c}$
${\vec{c}}^{T} \vec{x} = {\vec{b}}^{T} \vec{y}$

Důkaz.

(\Rightarrow)

Jelikož jsou přípustné, platí první tři body. Podle věty o dualitě platí čtvrtý bod. ◧

(\Leftarrow)

Podle prvních tří bodů jsou to přípustná řešení. Podle slabé věty o dualitě jsou i optimální. ◨

Věta (Rohn 15). Jestliže použitím simplexové metody dostaneme optimální řešení

{\vec{x}}^{B}

primární úlohy a platí

{\vec{x}}_{B}^{B} > 0

, potom duální úloha má jediné optimální řešení

{\vec{y}}^{*} ≔ {(𝐀_{B}^{T})}^{- 1} {\vec{c}}_{B}

Důkaz. Již víme, že je to optimální řešení, takže stačí dokázat, že je jediné. Nechť

\vec{y}

je libovolné optimální řešení; ukážeme, že

\vec{y} = {\vec{y}}^{*}

{\vec{x}}^{B T} \vec{c} = {\vec{c}}^{T} {\vec{x}}^{B} \overset{\overset{}{v \overset{ˇ}{e} t a o d u a l i t \overset{ˇ}{e}}}{=} {\vec{b}}^{T} \vec{y} \overset{\overset{}{p \overset{ˇ}{r} \overset{ˊ}{ı} p u s t n o s t}}{=} {(𝐀 {\vec{x}}^{B})}^{T} \vec{y} = {\vec{x}}^{B T} 𝐀^{T} \vec{y}

{\vec{x}}^{B T} (\vec{c} - 𝐀^{T} \vec{y}) = \vec{0}

Zjistili jsme, že skalární součin dvou vektorů je nulový, a ten levý má podle předpokladu všechny složky v

B

kladné, takže ten pravý musí mít všechny složky v

B

nulové.

\vec{0} = {(\vec{c} - 𝐀^{T} \vec{y})}_{B} = {\vec{c}}_{B} - {(𝐀^{T} \vec{y})}_{B}

{\vec{c}}_{B} = {(𝐀^{T} \vec{y})}_{B} = {({\vec{y}}^{T} 𝐀)}_{B}^{T} = {({\vec{y}}_{T} 𝐀_{B})}^{T} = 𝐀_{B}^{T} \vec{y}

\vec{y} = {(𝐀_{B}^{T})}^{- 1} {\vec{c}}_{B} = {\vec{y}}^{*} ■

Úlohy s nerovnostmi

Definice. Primární úloha s nerovnostmi je následující optimalizační úloha:

\min {{\vec{c}}^{T} \vec{x} | \vec{x} \in ℝ^{n}, 𝐀 \vec{x} \geq \vec{b}, \vec{x} \geq \vec{0}}

Poznámka. Od primární úlohy lineárního programování se liší pouze nerovnítkem.

Definice. Duální úloha s nerovnostmi je následující optimalizační úloha:

\max {{\vec{b}}^{T} \vec{y} | \vec{y} \in ℝ^{m}, 𝐀^{T} \vec{y} \leq \vec{c}, \vec{y} \geq \vec{0}}

Poznámka. Oproti duální úloze lineárního programování je podobnější své primární verzi.

Věta (Rohn 16, o slabé dualitě pro nerovnosti). Nechť

\vec{x}, \vec{y}

jsou přípustná řešení primární a duální úlohy s nerovnostmi. Potom

{\vec{c}}^{T} \vec{x} \geq {\vec{b}}^{T} \vec{y}

. Navíc pokud

{\vec{c}}^{T} \vec{x} = {\vec{b}}^{T} \vec{y}

, potom jde o optimální řešení.

Poznámka. Znění věty je úplně stejné jako předtím, akorát s jinými úlohami. Důkaz je také úplně stejný, akorát se poslední rovnítko v první části změní na nerovnítko.

Důkaz.

{\vec{c}}^{T} \vec{x} = {\vec{x}}^{T} \vec{c} \overset{p \overset{ˇ}{r} \overset{ˊ}{ı} p u s t n o s t}{\geq} {\vec{x}}^{T} 𝐀^{T} \vec{y} = {(𝐀 \vec{x})}^{T} \vec{y} \overset{p \overset{ˇ}{r} \overset{ˊ}{ı} p u s t n o s t}{\geq} {\vec{b}}^{T} \vec{y}

Tím je hotová první část. Nechť nyní pro nějaká

{\vec{x}}^{*}, {\vec{y}}^{*}

platí rovnost. Dokážeme, že jsou lepší než libovolná přípustná řešení

\vec{x}, \vec{y}

{\vec{c}}^{T} \vec{x} \geq {\vec{b}}^{T} {\vec{y}}^{*} \overset{\overset{}{p \overset{ˇ}{r} e d p o k l a d}}{=} {\vec{c}}^{T} {\vec{x}}^{*}

{\vec{b}}^{T} \vec{y} \leq {\vec{c}}^{T} {\vec{x}}^{*} \overset{\overset{}{p \overset{ˇ}{r} e d p o k l a d}}{=} {\vec{b}}^{T} {\vec{y}}^{*}

■

Věta (Rohn 17, o dualitě pro nerovnosti). Primární úloha s nerovnostmi má optimální řešení právě tehdy, pokud ho má duální úloha. V tom případě jsou optimální hodnoty stejné.

Poznámka. Znění věty je úplně stejné jako předtím, akorát s jinými úlohami. Důkaz je docela podobný.

Důkaz. Sestavíme primární a duální úlohu lineárního programování, které mají celkem zřejmě optimální řešení právě tehdy, pokud ho mají odpovídající úlohy s nerovnostmi. Podle normální věty o dualitě pak bude všechno ekvivalentní.

\min {(\begin{array}{cc} {\vec{c}}^{T} & {\vec{0}}^{T} \end{array}) {\vec{x}}^{'} | {\vec{x}}^{'} \in ℝ^{m + n}, (\begin{array}{cc} 𝐀 & - 𝐈 \end{array}) {\vec{x}}^{'} = \vec{b}, {\vec{x}}^{'} \geq 0}

\max {{\vec{b}}^{T} \vec{y} | \vec{y} \in ℝ^{m}, (\begin{array}{c} 𝐀^{T} \\ - 𝐈 \end{array}) \vec{y} \leq (\begin{array}{c} \vec{c} \\ \vec{0} \end{array})}

■

Věta (Rohn 18, podmínky optimality pro nerovnosti). Přípustná řešení úloh s nerovnostmi jsou optimální, právě pokud platí

${\vec{x}}^{T} (\vec{c} - 𝐀^{T} \vec{y}) = \vec{0}$
${\vec{y}}^{T} (𝐀 x - \vec{b}) = \vec{0}$

Důkaz.

(\Rightarrow)

Jsou-li optimální, potom podle věty o dualitě je

{\vec{c}}^{T} \vec{x} = {\vec{b}}^{T} \vec{y} = {(𝐀 \vec{x})}^{T} \vec{y}

. Z toho jednoduše plynou oba body. ◧

(\Leftarrow)

Nechť oba body platí. Potom

{\vec{c}}^{T} \vec{x} = {\vec{x}}^{T} \vec{c} = {\vec{x}}^{T} 𝐀^{T} \vec{y} = {\vec{y}}^{T} 𝐀 \vec{x} = {\vec{b}}^{T} \vec{y}

, tedy podle slabé věty o dualitě jsou optimální. ◨

Farkasova věta

Čteno „farkašova“, je to Maďar.

Věta (Rohn 19, Farkasova). Nechť

𝐀 \in ℝ^{m \times n}, \vec{b} \in ℝ^{m}

. Soustava

𝐀 \vec{x} = \vec{b}

\vec{x} \geq \vec{0}

má řešení právě tehdy, pokud

(\forall \vec{y} \in ℝ^{m}) (𝐀^{T} \vec{y} \geq 0 ⟹ {\vec{b}}^{T} \vec{y} \geq \vec{0})

Důkaz.

(\Rightarrow)

{\vec{b}}^{T} \vec{y} = {\vec{y}}^{T} \vec{b} = {\vec{y}}^{T} 𝐀 \vec{x} = {(𝐀^{T} \vec{y})}^{T} \vec{x} \geq \vec{0}

◧

(\Leftarrow)

Uvažujme primární a duální úlohu lineárního programování v normálním znění, akorát s

\vec{c} ≔ \vec{0}

\min {{\vec{0}}^{T} \vec{x} | \vec{x} \in ℝ^{n}, 𝐀 \vec{x} = \vec{b}, \vec{x} \geq \vec{0}}

\max {{\vec{b}}^{T} \vec{y} | \vec{y} \in ℝ^{m}, 𝐀^{T} \vec{y} \leq \vec{0}}

Duální úloha je přípustná, protože má alespoň řešení

\vec{y} = \vec{0}

. Zároveň pro každé její přípustné řešení podle předpokladu (s mínusem) platí

{\vec{b}}^{T} \vec{y} \leq 0

, takže je i omezená a tudíž má optimální řešení. Podle věty o dualitě má potom primární úloha optimální, tedy i přípustné, řešení, což mělo být dokázáno. ◨

Důsledek (negace). Primární úloha lineárního programování nemá přípustné řešení právě tehdy, pokud

(\exists \vec{y} \in ℝ^{m}) (𝐀^{T} \vec{y} \geq 0 \land {\vec{b}}^{T} \vec{y} < \vec{0})

Věta (Rohn 20). Je-li primární úloha lineárního programování přípustná, potom má optimální řešení právě tehdy, pokud

(\forall \vec{x} \in ℝ^{n}, \vec{x} \geq \vec{0}) (𝐀 \vec{x} = \vec{0} ⟹ {\vec{c}}^{T} \vec{x} \geq 0)

Von Neumann a teorie her

Definice. Mějme výplatní matici

𝐀 \in ℝ^{m \times n}

. Potom maticovou hrou nazveme takovouto hru: První hráč zvolí

i \in \hat{m}

, druhý nezávisle na něm zvolí

j \in \hat{n}

. Následně první hráč získá

A_{i j}

bodů a druhý získá

- A_{i j}

bodů.

Příklad. Hra „Kámen, nůžky, papír“ se dá formulovat jako maticová hra s maticí

𝐀 = (\begin{array}{ccc} 0 & 1 & - 1 \\ - 1 & 0 & 1 \\ 1 & - 1 & 0 \end{array})

Definice. Smíšená strategie je dvojice vektorů

(\vec{x} \in ℝ^{m}, \vec{y} \in ℝ^{n}), \sum_{i = 1}^{m} x_{i} = \sum_{j = 1}^{n} y_{i} = 1

reprezentující pravděpodobnost, s jakou každý hráč zvolí jednotlivé řádky/sloupce.

Poznámka. Očekávaná hodnota zisku pro prvního hráče při použití smíšené strategie

(\vec{x}, \vec{y})

{\vec{x}}^{T} 𝐀 \vec{y}

, pro druhého hráče

- {\vec{x}}^{T} 𝐀 \vec{y}

Definice. Optimální smíšená strategie je smíšená strategie

({\vec{x}}^{*}, {\vec{y}}^{*})

taková, že pro každou smíšenou strategií

(\vec{x}, \vec{y})

{\vec{x}}^{T} 𝐀 {\vec{y}}^{*} \leq {\vec{x}}^{* T} 𝐀 {\vec{y}}^{*} \leq {\vec{x}}^{* T} 𝐀 \vec{y}

Tedy pokud si kterýkoli hráč zvolí libovolnou jinou strategii, bude na tom stejně nebo hůř.

Věta. Všechny optimální smíšené strategie jsou stejně dobré, tedy existuje nějaká cena hry

ω

, která se rovná hodnotám všech optimálních smíšených strategií.

Důkaz. Nechť

({\vec{x}}^{*}, {\vec{y}}^{*}), (\vec{\tilde{x}}, \vec{\tilde{y}})

jsou dvě smíšené strategie. Z definice máme:

{\vec{x}}^{* T} 𝐀 \vec{\tilde{y}} \leq {\vec{\tilde{x}}}^{T} 𝐀 \vec{\tilde{y}} \leq {\vec{\tilde{x}}}^{T} 𝐀 {\vec{y}}^{*} \leq {\vec{x}}^{* T} 𝐀 {\vec{y}}^{*} \leq {\vec{x}}^{* T} 𝐀 \vec{\tilde{y}}

V tomto řetězci zřejmě musí být všude rovnost, tedy speciálně

{\vec{\tilde{x}}}^{T} 𝐀 \vec{\tilde{y}} = {\vec{x}}^{* T} 𝐀 {\vec{y}}^{*} ≕ ω

, což mělo být dokázáno. ■

Definice.

\vec{e} ≔ (\begin{array}{c} 1 \\ ⋮ \\ 1 \end{array})

𝐄 ≔ (\begin{array}{ccc} 1 & \dots & 1 \\ ⋮ & ⋱ & ⋮ \\ 1 & \dots & 1 \end{array})

Věta (Rohn 22). Nechť

α \in ℝ, α > \max_{i, j} (- A_{i j})

. Nechť

𝐀 ≔ 𝐀 + α 𝐄

. Potom dvojice úloh s nerovnostmi

\begin{matrix} \min {{\vec{e}}^{T} \vec{x} | 𝐀^{T} \vec{x} \geq \vec{e} \land \vec{x} \geq 0} & (p r i m \overset{ˊ}{a} r n \overset{ˊ}{ı}) \end{matrix}

\begin{matrix} \max {{\vec{e}}^{T} \vec{y} | 𝐀 \vec{y} \leq \vec{e} \land \vec{y} \geq 0} & (d u \overset{ˊ}{a} l n \overset{ˊ}{ı}) \end{matrix}

má optimální řešení

({\vec{x}}_{0}, {\vec{y}}_{0})

. Nechť dále

x^{*} ≔ \frac{{\vec{x}}_{0}}{{\vec{e}}^{T} {\vec{x}}_{0}}, y^{*} ≔ \frac{{\vec{y}}_{0}}{{\vec{e}}^{T} {\vec{y}}_{0}}

. Potom

(x^{*}, y^{*})

je optimální smíšená strategie, podle které můžeme spočítat cenu hry

ω

, a daná smíšená strategie

(\vec{x}, \vec{y})

je optimální právě tehdy, pokud

𝐀^{T} \vec{x} \geq ω \vec{e} \land 𝐀 \vec{y} \leq ω \vec{e}

Důkaz. Z definice

𝐀

plyne, že všechny její prvky jsou kladné. Duální úloha je přípustná, protože má přípustné řešení

\vec{0}

. Nechť

\vec{y}

je nějaké její přípustné řešení. Potom pro každá

i, j

musí platit

1 \geq {(𝐀 \vec{y})}_{j} \geq {\overline{A}}_{i j} y_{j}

, tedy

y_{j} \leq \frac{1}{{\overline{A}}_{i j}}

, tedy úloha je omezená. Jelikož je přípustná a omezená, musí mít optimální řešení

{\vec{y}}_{0}

, tedy podle věty o dualitě i primární úloha má optimální řešení

{\vec{x}}_{0}

a platí

{\vec{e}}^{T} {\vec{x}}_{0} = {\vec{e}}^{T} {\vec{y}}_{0}

. Z přípustnosti

{\vec{x}}_{0}

plyne

𝐀^{T} {\vec{x}}_{0} \geq \vec{e} ∴ {\vec{x}}_{0} \neq \vec{0} ∴ {\vec{e}}^{T} {\vec{x}}_{0} > 0

. Vektory tedy můžeme normalizovat (viz znění věty) a tím dostaneme smíšenou strategii. Nyní musíme dokázat, že je optimální. Vezměme jinou smíšenou strategii

(\vec{x}, \vec{y})

. Opět využijeme přípustnosti:

{\vec{x}}^{T} 𝐀 {\vec{y}}_{0} \leq {\vec{x}}^{T} \vec{e} = {\vec{e}}^{T} \vec{x} = 1 ∴ {\vec{x}}^{T} 𝐀 {\vec{y}}^{*} \leq \frac{1}{{\vec{e}}^{T} {\vec{x}}_{0}}

{\vec{y}}^{T} 𝐀^{T} {\vec{x}}_{0} \geq {\vec{y}}^{T} \vec{e} = {\vec{e}}^{T} \vec{y} = 1 ∴ {\vec{x}}^{* T} 𝐀 \vec{y} \geq \frac{1}{{\vec{e}}^{T} {\vec{x}}_{0}}

Zřejmě pro libovolná

\vec{u}, \vec{v}

platí

{\vec{u}}^{T} 𝐀 \vec{v} = {\vec{u}}^{T} 𝐀 \vec{v} + α

. Z tohoto a předchozích dvou nerovností máme

{\vec{x}}^{T} 𝐀 {\vec{y}}^{*} \leq {\vec{x}}^{* T} 𝐀 \vec{y}

. To platí pro libovolná

\vec{x}, \vec{y}

, takže speciálně můžeme říct

{\vec{x}}^{T} 𝐀 {\vec{y}}^{*} \leq {\vec{x}}^{* T} 𝐀 {\vec{y}}^{*} \leq {\vec{x}}^{* T} 𝐀 \vec{y}

. To znamená, že skutečně jde o optimální strategii. Nyní již zbývá jen dokázat poslední ekvivalenci.

(\Rightarrow)

Mějme libovolnou strategii

\vec{\tilde{y}}

druhého hráče. Z definice optimální strategie pro libovolné

\vec{x}

platí

{\vec{x}}^{T} 𝐀 \vec{\tilde{y}} \leq ω

. Vybereme-li speciálně

\vec{x} ≔ {\vec{e}}_{i}

, dostaneme

(\forall i) (𝐀 \vec{\tilde{y}} \leq ω)

, tedy

𝐀 \vec{\tilde{y}} \leq ω \vec{e}

. Analogicky pro prvního hráče. ◧

(\Leftarrow)

Nechť

\vec{\tilde{y}}

je strategie druhého hráče splňující

𝐀 \vec{\tilde{y}} \leq ω \vec{e}

. Potom pro každou strategii

\vec{x}

prvního hráče máme

{\vec{x}}^{T} 𝐀 \vec{\tilde{y}} \leq {\vec{x}}^{T} ω \vec{e} = ω

Zároveň již víme, že pro libovolné

\vec{y}

{\vec{x}}^{* T} 𝐀 \vec{y} \geq ω

Pokud v těchto nerovnostech zvolíme

\vec{x} ≔ {\vec{x}}^{*}, \vec{y} ≔ \vec{\tilde{y}}

, dostáváme

ω = {\vec{x}}^{* T} 𝐀 \vec{\tilde{y}}

. Pokud to do těch samých nerovností (s obecnými

\vec{x}, \vec{y}

) dosadíme, dostaneme definici optimální strategie. Analogicky pro prvního hráče. ◨

Cvičení. Dokažte podle této věty, že pro hru „Kámen, nůžky, papír“ je optimální smíšená strategie

\vec{x} = \vec{y} = \frac{1}{3} \vec{e}

Věta (Rohn 23, von Neumannova). Každá konečná maticová hra má optimální smíšenou strategii.

Důkaz. Na základě předchozí věty triviální (stačí vzít třeba

α ≔ \max_{i, j} (- A_{i j}) + 1

). ■

Dopravní problém

Definice. Mějme

m, n \in ℕ^{+}, \vec{a} \in ℝ^{m}, \vec{b} \in ℝ^{n}, 𝐂 \in ℝ^{m \times n}

. Dopravní problém je následující optimalizační úloha:

\min {\sum_{i = 1}^{m} \sum_{j = 1}^{n} C_{i j} X_{i j} | 𝐗 \in ℝ^{m \times n}, (\forall i \in \hat{m}) (\sum_{j = 1}^{n} X_{i j} = a_{i}), (\forall j \in \hat{n}) (\sum_{i = 1}^{m} X_{i j} = b_{i}), (\forall i \in \hat{m}, j \in \hat{n}) (X_{i j} \geq 0)}

Věta (Rohn 24). Dopravní problém je přípustný právě tehdy, pokud

\sum_{i = 1}^{m} a_{i} = \sum_{j = 1}^{n} b_{j}

. V takovém případě má optimální řešení a nějaké

𝐗

je optimální řešení právě tehdy, pokud existují

\vec{p} \in ℝ^{m}, \vec{q} \in ℝ^{n}

taková, že

$(\forall i \in \hat{m}, j \in \hat{n}) (p_{i} + q_{j} \leq C_{i j})$
$(\forall i \in \hat{m}, j \in \hat{n}) (X_{i j} (C_{i j} - p_{i} - q_{j}) = 0)$

Důkaz. Nejprve ukážeme první ekvivalenci:

(\Rightarrow)

Pokud má dopravní problém přípustné řešení

𝐗

, potom

\sum_{i = 1}^{m} a_{i} = \sum_{i = 1}^{m} \sum_{j = 1}^{n} X_{i j} = \sum_{j = 1}^{n} b_{j}

(\Leftarrow)

Nechť

\sum_{i = 1}^{m} a_{i} = \sum_{j = 1}^{n} b_{j} ≕ s

. Nechť

X_{i j} ≔ \frac{a_{i} b_{j}}{s}

. Potom se dá snadno ukázat, že

𝐗

je přípustné.

Nyní ukážeme, že problém je poté omezený a tedy má optimální řešení:

(\forall i \in \hat{m}, j \in \hat{n}) (X_{i j} \leq \sum_{k = 1}^{n} X_{i k} = a_{i} \leq s)

Zbývá poslední ekvivalence. Soustava se dá reprezentovat jako primární úloha lineárního programování s maticí:

𝐌 ≔ (\begin{array}{ccccccccccccc} 1 & 0 & \dots & 0 & 1 & 0 & \dots & 0 & \dots & 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 & 0 & 1 & \dots & 0 & \dots & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & \dots & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 1 & 0 & 0 & \dots & 1 & \dots & 0 & 0 & \dots & 1 \\ 1 & 1 & \dots & 1 & 0 & 0 & \dots & 0 & \dots & 0 & 0 & \dots & 0 \\ 0 & 0 & \dots & 0 & 1 & 1 & \dots & 1 & \dots & 0 & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & \dots & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 0 & 0 & 0 & \dots & 0 & \dots & 1 & 1 & \dots & 1 \end{array})

(Vypadá to děsivě, ale jsou to prostě jednotkové matice vedle sebe a pod nimi „roztažená“ jednotková matice.) Nechť

\vec{y} ≔ (\begin{array}{c} \vec{p} \\ \vec{q} \end{array})

. Potom duální úloha a podmínka optimality bude přesně odpovídat znění věty. ■

Analýza citlivosti

Tahle sekce pochází z prezentace Mgr. Jany Sekničkové, Ph.D., takže je psána takovým fyzikálnějším stylem: místo vět a důkazů je postupné odvozování. Taky používá úplně jiné značení než Rohn; pokusím se to trochu zkonzistentnit, ale přesto hodně štěstí.

Mějme nějakou simplexovou tabulku s optimálním řešením. Zajímá nás, jak moc se můžou změnit parametry úlohy, aby se nezměnilo optimální $B$ .

Aby řešení stále bylo přípustné, musí být ${\vec{x}}_{B}^{B} = 𝐀_{B}^{- 1} \vec{b} \geq 0$ . Zkusíme najít, jak moc se může změnit $b_{p}$ pro nějaké $p \in \hat{m}$ .

{\vec{b}}^{*} ≔ \vec{b} + Δ \vec{b} ≔ \vec{b} + (\begin{array}{c} 0 \\ ⋮ \\ 0 \\ Δ b_{p} \\ 0 \\ ⋮ \\ 0 \end{array})

Chceme, aby bylo:

0 \leq 𝐀_{B}^{- 1} {\vec{b}}^{*} = 𝐀_{B}^{- 1} \vec{b} + 𝐀_{B}^{- 1} Δ \vec{b}

𝐀_{B}^{- 1} Δ \vec{b} \geq - 𝐀_{B}^{- 1} \vec{b}

Pro maximální zmatení budeme značit $𝐁 ≔ 𝐀_{B}^{- 1}$ :

{\vec{B}}_{\circ p} Δ b_{p} \geq - \vec{\overline{b}}

Rozepíšeme to po složkách, tedy pro všechna $i \in \hat{m}$ :

B_{i p} Δ b_{p} \geq - {\overline{b}}_{i}

Z toho dostaneme podmínku:

\max {\frac{- {\overline{b}}_{i}}{B_{i p}} | i \in \hat{m}, B_{i p} > 0} \leq Δ b_{p} \leq \min {\frac{- {\overline{b}}_{i}}{B_{i p}} | i \in \hat{m}, B_{i p} < 0}

Pokud bychom nedělali ty šaškárny s $Δ$ , ale rovnou rozepsali po složkách vztah $𝐀_{B}^{- 1} {\vec{b}}^{*} \geq \vec{0}$ , vyšly by nám nerovnosti udávající omezení přímo pro ${\vec{b}}^{*}$ .

Pokud tedy takovéto nerovnosti splníme, $B$ zůstane stejné, ovšem stále se může změnit ${\vec{x}}_{B}^{B}$ a hodnota účelové funkce.

Tím jsme zjistili, jak optimální řešení reaguje na změny $\vec{b}$ . Co takhle změny $\vec{c}$ ? Řešení musí stále splňovat podmínku optimality ${\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} 𝐀 - c^{T} \geq 0$ . Zároveň z nějakého důvodu musí být ${\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} \geq 0$ . Jelikož ve vzorcích máme ${\vec{c}}_{B}$ , musíme rozlišovat změnu bazické a nebazické části. Nejdříve změníme nebazickou.

Nechť $c_{k}^{*} ≔ c_{k} + Δ c_{k}$ , kde $k \in N$ . Potom se změní jedna složka $\vec{c}$ , zatímco ${\vec{c}}_{B}$ se nezmění. Z vektoru $\vec{\overline{c}}$ se také změní $k$ -tá složka:

{\overline{c}}_{k}^{*} = {\vec{c}}_{B}^{T} 𝐀_{B}^{- 1} {\vec{A}}_{\circ k} - {\vec{c}}_{k}^{*} = {\overline{c}}_{k} - Δ c_{k}

Chceme, aby to pořád bylo nezáporné, tedy řešení zůstává optimální, pokud $Δ c_{k} \leq {\overline{c}}_{k}$ . Žádné dolní omezení není, nebazická proměnná se může libovolně snížit.

Dobře, to bylo jednoduché. Co takhle změna bazické proměnné? Teď už se změní všechny koeficienty $\vec{\overline{c}}$ :

{\overline{c}}_{j} = {\vec{c}}_{B}^{* T} 𝐀_{B}^{- 1} {\vec{A}}_{\circ j} - c_{j}

Teď prostě zase budeme řešit, kdy je to nezáporné. Nemá cenu to rozepisovat. Ještě navíc musí být ${\vec{c}}_{B}^{* T} 𝐀_{B}^{- 1}$ nezáporné. Jelikož máme rádi písmenka, označíme si $q$ číslo řádku, v němž je $x_{k}$ bazická proměnná (tedy $k = B_{q}$ ), a máme

\max {\frac{- {\overline{c}}_{j}}{{\overline{A}}_{q j}} | j \in \hat{n}, {\overline{A}}_{q j} > 0} \leq Δ c_{k} \leq \min {\frac{- {\overline{c}}_{j}}{{\overline{A}}_{q j}} | j \in \hat{n}, {\overline{A}}_{q j} < 0}