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é

1. Existuje $\mathbf {x} \in \mathbb {R} ^{n}$ takové že $\mathbf {Ax} =\mathbf {b}$ a zároveň $\mathbf {x} \geq 0$.
2. 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} <0$

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.) je pravdivé, to je ekvivalentní s tvrzením, že (1.) je ekvivalentní s negací (2.) Tedy $(\exists \mathbf {x} \in \mathbb {R} ^{n},\,\mathbf {x} \geq \mathbf {0} \,\And \,\mathbf {A} \mathbf {x} =0)\Leftrightarrow \neg (\exists \mathbf {y} \in \mathbb {R} ^{m},\,\mathbf {b} ^{\mathsf {T}}\mathbf {y} <0\,\And \,\mathbf {A} ^{\mathsf {T}}\mathbf {y} \geq 0)$. Tvrzení $\neg (\exists \mathbf {y} \in \mathbb {R} ^{m},\,\mathbf {b} ^{\mathsf {T}}\mathbf {y} <0\,\And \,\mathbf {A} ^{\mathsf {T}}\mathbf {y} \geq 0)$ je ekvivalentní s $\forall \mathbf {u} \in \mathbb {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í. 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 b_1,, b₂)

1. Existuje x₁ ≥ 0, x₂ ≥ 0 takové že: 6 x₁ + 4 x₂ = b₁ a 3 x₁ = b₂, nebo
2. Existuje y₁, y₂ takové že: 6 y₁ + 3 y₂ ≥ 0, 4 y₁ ≥ 0, a b₁ y₁ + b₂ y₂ < 0.

Uveďme důkaz pro tento speciální případ:

• Pokud b₂ ≥ 0 a b₁ − 2b₂ ≥ 0, pak možnost 1 je pravdivá, protože řešení soustavy je x₁ = b₂/3 a x₂ = b₁ − 2b₂. Možnost 2 není pravdivá, jelikož b₁ y₁ + b₂ y₂ ≥ b₂ (2 y₁ + y₂) = b₂ (6 y₁ + 3 y₂) / 3, když pravá strana je kladná, levá strana musí být také kladná.
• 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ž b₂ < 0, pak můžeme vzít. y₁ = 0 a y₂ = 1.
  • Když b₁ − 2b₂ < 0, pak pro nějaké číslo B > 0, b₁ = 2b₂ − B, takže: b₁ y₁ + b₂ y₂ = 2 b₂ y₁ + b₂ y₂ − B y₁ = b₂ (6 y₁ + 3 y₂) / 3 − B y₁. Proto můžeme například vzít: y₁ = 1, y₂ = −2.

Reference

V tomto článku byl použit překlad textu z článku Farkas' lemma na anglické Wikipedii.