Farkas, lemma di

Farkas, lemma di

Farkas, lemma di noto anche come teorema di Farkas-Minkowski, stabilisce che se A è una matrice m × n a elementi reali, b un vettore a m componenti reali (b ∈ R^m) e x un vettore a n componenti reali (x ∈ Rⁿ), allora il sistema A ⋅ x = b (con x ≥ 0, nel senso che ogni componente di x è maggiore o uguale a zero) ha una soluzione se e solo se esiste y ∈ R^m tale che il sistema A^T ⋅ y ≥ 0, b^T ⋅ y < 0 non ammette soluzioni. Il teorema può avere altre equivalenti formulazioni. Per esempio: per ogni assegnata matrice A_mn e per ogni assegnato vettore b ∈ R^m, uno e uno solo dei due seguenti sistemi lineari ammette soluzione:

a) A ⋅ x = b, x ≥ 0

b) y ⋅ A ≥ 0, y ⋅ b < 0

Il teorema è utilizzato in diversi contesti, quali per esempio la programmazione, lineare e non, la teoria dei giochi, la rappresentazione di problemi con sistemi di disequazioni. Anche le tecniche di dimostrazione utilizzate variano da metodi algebrici a geometrici, algoritmici o metodi che utilizzano risultati di distanza minima.