Farkasova věta: Porovnání verzí

← Přejít na předchozí porovnání Přejít na další porovnání →

Smazaný obsah Přidaný obsah

V textu

Verze z 16. 2. 2021, 10:30

Farkasova věta, někdy též Farkasovo lemma, vypovídá o řešitelnosti konečného systému lineárních rovnic, případně nerovnice, existuje několik modifikací.

Formulace

Jak bylo již výše zmíně, v literatuře se objevuje několik formulací farkasovy věty, zde je podána formulace, která je převzatá od Gale, Kuhn a Tucker (1951)

Gale, Kuhn and Tucker (1951).^[1]

Farkas' lemma — 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 x an takové že: a
Existuje y an takové že: a

There exists an $\mathbf {x} \in \mathbb {R} ^{n}$ such that $\mathbf {Ax} =\mathbf {b}$ and $\mathbf {x} \geq 0$ .
There exists a $\mathbf {y} \in \mathbb {R} ^{m}$ such that $\mathbf {A} ^{\mathsf {T}}\mathbf {y} \geq 0$ and Nelze pochopit (syntaktická chyba): {\displaystyle \mathbf{b}^{\mathsf{T}} \mathbf{y} < == Příklad == Mějme ''m'', ''n'' = 2, <math>\mathbf{A} = \begin{bmatrix}6 & 4 \\3 & 0\end{bmatrix}} , a $\mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\end{bmatrix}}$ . Farkasova věta říká, že právě jedno z následujících je pravda (v závislosti na b_1,, b₂)

Existuje x₁ ≥ 0, x₂ ≥ 0 takové že: 6 x₁ + 4 x₂ = b₁ a 3 x₁ = b₂, nebo
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 rež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í rovnicce nemůže mít všechny složky nezáporné. Avšak možnost 2 je pradivá:
- 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ůžem 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.

↑ GALE, David; KUHN, Harold; TUCKER, Albert W. Activity Analysis of Production and Allocation. Redakce Koopmans. [s.l.]: Wiley, 1951. Kapitola Linear Programming and the Theory of Games - Chapter XII. . See Lemma 1 on page 318.

[1] GALE, David; KUHN, Harold; TUCKER, Albert W. Activity Analysis of Production and Allocation. Redakce Koopmans. [s.l.]: Wiley, 1951. Kapitola Linear Programming and the Theory of Games - Chapter XII. . See Lemma 1 on page 318.

[1]

@@ Řádek 12: / Řádek 12: @@
 # Existuje '''y''' an takové že: a
-{{math_theorem|name=Farkas' lemma| Let <math>\mathbf{A} \in \mathbb{R}^{m\times n}</math>  and <math>\mathbf{b} \in \mathbb{R}^{m}</math> . Then exactly one of the following two assertions is true:
 # There exists an <math>\mathbf{x} \in \mathbb{R}^{n}</math> such that <math>\mathbf{Ax} = \mathbf{b}</math> and <math>\mathbf{x} \geq 0</math>.
-# There exists a <math>\mathbf{y} \in \mathbb{R}^{m}</math> such that <math>\mathbf{A}^{\mathsf{T}}\mathbf{y} \geq 0</math> and <math>\mathbf{b}^{\mathsf{T}} \mathbf{y}  < 0</math>. }}
+# There exists a <math>\mathbf{y} \in \mathbb{R}^{m}</math> such that <math>\mathbf{A}^{\mathsf{T}}\mathbf{y} \geq 0</math> and <math>\mathbf{b}^{\mathsf{T}} \mathbf{y}  <
 == Příklad ==