Lemat Farkasa, alternatywa Farkasa – twierdzenie z algebry liniowej, według którego w przestrzeni albo punkt należy do stożka, albo można go oddzielić od stożka płaszczyzną.
Wypowiedź Jeżeli jest macierzą rzeczywistą o wierszach i kolumnach oraz jest wektorem zapisywanym w kolumnie, zachodzi alternatywa wykluczająca: albo równanie ma rozwiązanie albo układ nierówności:
ma rozwiązanie ze względu na
Interpretacja Jeżeli równanie ma rozwiązanie wtedy istnieje kombinacja stożkowa kolumn macierzy dająca wektor czyli punkt należy do stożka wyznaczonego przez kolumny macierzy
Jeżeli układ nierówności:
ma rozwiązanie wtedy wektor tworzy z każdą z kolumn macierzy kąt mniejszy bądź równy od (bo wszystkie iloczyny skalarne są większe od 0), a z wektorem kąt rozwarty. Zatem płaszczyzna prostopadła do wektora oddziela stożek od punktu
Zastosowanie 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.
Linki zewnętrzne Skrypt dra Łukasza Kowalika z MIMUW
Kategoria:Twierdzenia algebry liniowej Kategoria:Metody optymalizacji Kategoria:Programowanie liniowe F