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 $𝐀\in {ℝ}^{m\times n}$ a $𝐛\in {ℝ}^m$, pak právě jedno z následujících tvrzení je pravdivé

1. Existuje $𝐱\in {ℝ}^n$ takové že $𝐀𝐱=𝐛$ a zároveň $𝐱\ge 0$.
2. Existuje $𝐲\in {ℝ}^m$ takové že ${𝐀}^{𝖳}𝐲\ge 0$ a zároveň ${𝐛}^{𝖳}𝐲<0$

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

Farkasova věta (Dupačová a Lachout)

Soustava $𝐀𝐱=𝐛$ má nezáporné řešení tehdy a jen tehdy, když pro každé $𝐮$, které splňuje ${𝐀}^{𝖳}𝐮\ge \mathrm{𝟎}$, platí ${𝐛}^{𝖳}𝐮\ge \mathrm{𝟎}$.

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 $(\mathrm{\exists }𝐱\in {ℝ}^n,𝐱\ge \mathrm{𝟎}\mathrm{\&}𝐀𝐱=0)\iff \mathrm{\neg }(\mathrm{\exists }𝐲\in {ℝ}^m,{𝐛}^{𝖳}𝐲<0\mathrm{\&}{𝐀}^{𝖳}𝐲\ge 0)$. Tvrzení $\mathrm{\neg }(\mathrm{\exists }𝐲\in {ℝ}^m,{𝐛}^{𝖳}𝐲<0\mathrm{\&}{𝐀}^{𝖳}𝐲\ge 0)$ je ekvivalentní s $\mathrm{\forall }𝐮\in {ℝ}^m,{𝐀}^{𝖳}𝐮\ge 0\Rightarrow {𝐛}^{𝖳}𝐮\ge \mathrm{𝟎}$ 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 \{{\mathrm{𝟎}}^{𝖳}𝐱:𝐀𝐱=𝐛,𝐱\ge \mathrm{𝟎}\}$

a

$\min \{{𝐛}^{𝖳}𝐲:{𝐀}^{𝖳}𝐲\ge \mathrm{𝟎}\}$.

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 $𝐀𝐱=𝐛$ 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 $\mathrm{𝟎}\in M=\{𝐲:{𝐀}^{𝖳}𝐲\ge \mathrm{𝟎}\}$ 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é $𝐮$, které splňuje ${𝐀}^{𝖳}𝐮\ge \mathrm{𝟎}$, platí ${𝐛}^{𝖳}𝐮\ge \mathrm{𝟎}$. Čímž je dokázaná požadovaná ekvivalence.

Příklad

Mějme m, n = 2, $𝐀=\left(\begin{array}{cc}6& 4\\ 3& 0\end{array}\right)$, $𝐛=\left(\begin{array}{c}{b}_1\\ b_2\end{array}\right)$. 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.