Farkasova věta

Farkasova věta, někdy též Farkasovo lemma, vypovídá o řešitelnosti konečné soustavy lineárních rovnic, případně nerovnic, existuje několik modifikací. Věta je jedním z důsledků silné věty o dualitě v lineárním programování. Jako první tuto větu dokázal maďarský matematik Gyula Farkas v roce 1902.

Formulace

Jak bylo již výše zmíněno, v literatuře se objevuje několik formulací Farkasovy věty, první zde uvedená formulace, byla převzatá z knihy Gale, Kuhn and Tucker (1951).

==== Farkasova věta (Gale, Kuhn a Tucker) ==== Pokud \mathbf{A} \in \mathbb{R}^{m\times n} a \mathbf{b} \in \mathbb{R}^{m}, pak právě jedno z následujících tvrzení je pravdivé

# Existuje \mathbf{x} \in \mathbb{R}^{n} takové že \mathbf{Ax} = \mathbf{b} a zároveň \mathbf{x} \geq 0. # Existuje \mathbf{y} \in \mathbb{R}^{m} takové že \mathbf{A}^{\mathsf{T}}\mathbf{y} \geq 0 a zároveň \mathbf{b}^{\mathsf{T}}\mathbf{y}

Jinou, ekvivalentní formulaci můžeme najít v knize Dupačová, Lachout.

==== Farkasova věta (Dupačová a Lachout) ==== Soustava \mathbf{A} \mathbf{x}=\mathbf{b} má nezáporné řešení tehdy a jen tehdy, když pro každé \mathbf{u}, které splňuje \mathbf{A}^{\mathsf{T}} \mathbf{u} \geq \mathbf{0}, platí \mathbf{b}^{\mathsf{T}}\mathbf{u}\geq\mathbf{0}.

Ekvivalence formulací

První formulace nám říká, že právě jedno z tvrzení (1. ) a (2. +more) je pravdivé, to je ekvivalentní s tvrzením, že (1. ) je ekvivalentní s negací (2. ) Tedy (\exist \mathbf x \in \R^n, \, \mathbf x \geq \mathbf 0 \, \And \, \mathbf A \mathbf x = 0) \Leftrightarrow \neg (\exists \mathbf y \in \R^m, \, \mathbf{b}^{\mathsf{T}}\mathbf{y} . Tvrzení \neg (\exists \mathbf y \in \R^m, \, \mathbf{b}^{\mathsf{T}}\mathbf{y} je ekvivalentní s \forall \mathbf u \in \R^m, \, \mathbf{A}^{\mathsf{T}}\mathbf{u} \geq 0\Rightarrow \mathbf{b}^{\mathsf{T}}\mathbf{u} \geq \mathbf 0 z čehož plyne druhá formulace věty.

Důkaz věty

Důkaz Farkasovy věty vychází ze silné věty o dualitě v lineárním programování aplikované na dvojici duálních úloh

\max\{ \mathbf{0}^{\mathsf{T}}}\mathbf{x}:\, \mathbf{A}\mathbf{x} = \mathbf{b},\,\mathbf{x}\geq\mathbf{0} \

a

\min \{ \mathbf{b}^{\mathsf{T}} \mathbf{y}:\, \mathbf{A}^{\mathsf{T}} \mathbf{y} \geq \mathbf{0} \}.

Maximalizační problém je triviální a má optimální řešení právě tehdy, když je množina přípustných řešení neprázdná, což je ekvivalentní s tím, že soustava \mathbf{A} \mathbf{x}=\mathbf{b} má nezáporné řešení. Podle silné věty o dualitě má maximalizační problém optimální řešení tehdy a jen tehdy, když má duální minimalizační problém optimální řešení. +more Protože \mathbf 0 \in M = \{ \mathbf y : \mathbf{A}^{\mathsf{T}} \mathbf y \geq \mathbf 0 \} a M je zároveň množinou všech svých směrů, tak minimalizační problém má optimální řešení právě tehdy, když pro každé \mathbf{u}, které splňuje \mathbf{A}^{\mathsf{T}} \mathbf{u} \geq \mathbf{0}, platí \mathbf{b}^{\mathsf{T}}\mathbf{u}\geq\mathbf{0}. Čímž je dokázaná požadovaná ekvivalence.

Příklad

Mějme m, n = 2, \mathbf{A} = \begin{pmatrix}6 & 4 \\3 & 0\end{pmatrix}, \mathbf{b} = \begin{pmatrix}b_1 \\b_2\end{pmatrix}. Farkasova věta říká, že právě jedno z následujících je pravda (v závislosti na b1,, b2)

# Existuje x1 ≥ 0, x2 ≥ 0 takové že: 6 x1 + 4 x2 = b1 a 3 x1 = b2, nebo # Existuje y1, y2 takové že: 6 y1 + 3 y2 ≥ 0, 4 y1 ≥ 0, a b1 y1 + b2 y2 2 ≥ 0 a b1 − 2b2 ≥ 0, pak možnost 1 je pravdivá, protože řešení soustavy je x1 = b2/3 a x2 = b1 − 2b2. Možnost 2 není pravdivá, jelikož b1 y1 + b2 y2 ≥ b2 (2 y1 + y2) = b2 (6 y1 + 3 y2) / 3, když pravá strana je kladná, levá strana musí být také kladná. +more * Jinak, možnost 1 je nepravdivá, protože řešení rovnice nemůže mít všechny složky nezáporné. Avšak možnost 2 je pravdivá: ** Když b2 1 = 0 a y2 = 1. ** Když b1 − 2b2 0, b1 = 2b2 − B, takže: b1 y1 + b2 y2 = 2 b2 y1 + b2 y2 − B y1 = b2 (6 y1 + 3 y2) / 3 − B y1. Proto můžeme například vzít: y1 = 1, y2 = −2.

Reference

Kategorie:Matematické věty a důkazy