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.^[1]

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).^[2]

Farkasova věta (Gale, Kuhn a Tucker)

Pokud ${\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n}}$ a ${\displaystyle \mathbf {b} \in \mathbb {R} ^{m}}$, pak právě jedno z následujících tvrzení je pravdivé

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

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

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

Soustava ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$ má nezáporné řešení tehdy a jen tehdy, když pro každé ${\displaystyle \mathbf {u} }$, které splňuje ${\displaystyle \mathbf {A} ^{\mathsf {T}}\mathbf {u} \geq \mathbf {0} }$, platí ${\displaystyle \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 ${\displaystyle (\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í ${\displaystyle \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 ${\displaystyle \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

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

a

${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \mathbf {0} \in M=\{\mathbf {y} :\mathbf {A} ^{\mathsf {T}}\mathbf {y} \geq \mathbf {0} \}}$ a ${\displaystyle 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é ${\displaystyle \mathbf {u} }$, které splňuje ${\displaystyle \mathbf {A} ^{\mathsf {T}}\mathbf {u} \geq \mathbf {0} }$, platí ${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {u} \geq \mathbf {0} }$. Čímž je dokázaná požadovaná ekvivalence.

Příklad

Mějme m, n = 2, ${\displaystyle \mathbf {A} ={\begin{pmatrix}6&4\\3&0\end{pmatrix}}}$, ${\displaystyle \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.