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 a , pak právě jedno z následujících tvrzení je pravdivé

  1. Existuje takové že a zároveň .
  2. Existuje takové že a zároveň


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

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

Soustava má nezáporné řešení tehdy a jen tehdy, když pro každé , které splňuje , platí .

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 . Tvrzení je ekvivalentní s 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



a


.


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 a 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 , platí . Čímž je dokázaná požadovaná ekvivalence.


Příklad

Mějme m, n = 2, , . Farkasova věta říká, že právě jedno z následujících je pravda (v závislosti na b1,, b2)

  1. Existuje x1 ≥ 0, x2 ≥ 0 takové že: 6 x1 + 4 x2 = b1 a 3 x1 = b2, nebo
  2. Existuje y1, y2 takové že: 6 y1 + 3 y2 ≥ 0, 4 y1 ≥ 0, a b1 y1 + b2 y2 < 0.

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

  • Pokud b2 ≥ 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 y2b2 (2 y1 + y2) = b2 (6 y1 + 3 y2) / 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ž b2 < 0, pak můžeme vzít. y1 = 0 a y2 = 1.
    • Když b1 − 2b2 < 0, pak pro nějaké číslo B > 0, b1 = 2b2 − B, takže: b1 y1 + b2 y2 = 2 b2 y1 + b2 y2B y1 = b2 (6 y1 + 3 y2) / 3 − B y1. Proto můžeme například vzít: y1 = 1, y2 = −2.

Reference

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

  1. Journal für die reine und angewandte Mathematik. [s.l.]: de Gruyter Dostupné online. 
  2. GALE, David; KUHN, Harold; TUCKER, Albert W. Activity Analysis of Production and Allocation. Příprava vydání Koopmans. [s.l.]: Wiley, 1951. Kapitola Linear Programming and the Theory of Games - Chapter XII. . Viz Lemma 1 na straně 318.
  3. DUPAČOVÁ, Jitka; LACHOUT, Petr. Úvod do optimalizace. Praha: Matfyzpress, 2011. ISBN 978-80-7378-176-7. S. 36, Věta 3.30.