Lemat Farkasa

Ten artykuł od 2010-10 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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

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

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

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

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

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

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

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

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

Lemat Farkasa służy do pokazania twierdzenia o dualności w programowaniu liniowym, a w szerszym ujęciu nieliniowym w dowodzie twierdzenia Karusha-Kuhna-Tuckera.

• Skrypt dra Łukasza Kowalika z MIMUW