Lemat Farkasa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Lemat Farkasa, alternatywa Farkasa - twierdzenie z algebry liniowej, według którego w przestrzeni \mathbb{R}^{n} albo punkt należy do stożka, albo można go oddzielić od stożka płaszczyzną.

Wypowiedź[edytuj | edytuj kod]

Jeżeli A jest macierzą rzeczywistą o n wierszach i m kolumnach oraz b\in\mathbb{R}^{n} jest wektorem zapisywanym w kolumnie, zachodzi alternatywa wykluczająca:

  • albo równanie A x = b ma rozwiązanie x \geqslant 0,
  • albo układ nierówności:

\left\{ {y^{T} A \geqslant 0 \atop y^{T} b < 0} \right.

ma rozwiązanie ze względu na y\in\mathbb{R}^{n}.

Interpretacja[edytuj | edytuj kod]

Jeżeli równanie A x = b ma rozwiązanie x \geqslant 0, wtedy istnieje kombinacja stożkowa kolumn macierzy A dająca wektor b, czyli punkt b należy do stożka wyznaczonego przez kolumny macierzy A.

Jeżeli układ nierówności:

\left\{ {y^{T} A \geqslant 0 \atop y^{T} b < 0} \right.

ma rozwiązanie y\in\mathbb{R}^{n}, wtedy wektor y tworzy z każdą z kolumn macierzy A kąt mniejszy bądź równy od 90^{o} (bo wszystkie iloczyny skalarne są większe od 0), a z wektorem b kąt rozwarty. Zatem płaszczyzna prostopadła do wektora y oddziela stożek od punktu b.

Zastosowanie[edytuj | edytuj kod]

Lemat Farkasa służy do pokazania twierdzenia o dualności w programowaniu liniowym.

Linki zewnętrzne[edytuj | edytuj kod]