Лема Фаркаша

Нехай ${\displaystyle A'}$ це матриця ${\displaystyle A':=[A\quad -A\quad I]}$, де ${\displaystyle I}$ це одинична матриця. Розмірність цієї матриці є рівною m × (2n+m).

Система нерівностей ${\displaystyle Ax\leq b}$ має розв'язок ${\displaystyle x}$ тоді і тільки тоді, коли система рівнянь ${\displaystyle A'x'=b}$ має невід'ємний розв'язок ${\displaystyle x'\in \mathbb {R} ^{2n+m}}$. Справді, якщо система рівнянь має такий розв'язок то позначивши ${\displaystyle x_{i}=x'_{i}-x'_{n+i}}$ одержуємо ${\displaystyle Ax+x''=b,}$ де ${\displaystyle x''\in \mathbb {R} ^{m}}$ позначає вектор елементами якого є ${\displaystyle x''_{i}=x'_{2n+i}.}$ Оскільки усі ${\displaystyle x''_{i}\geq 0,}$ то звідси одержуємо ${\displaystyle Ax\leq b.}$

Якщо ж ${\displaystyle Ax\leq b}$ має розв'язок ${\displaystyle x\in \mathbb {R} ^{n},}$ то можна знайти розв'язок системи рівнянь ${\displaystyle A'x'=b}$. Для цього для кожного індексу i, якщо ${\displaystyle x_{i}\geq 0,}$ то нехай ${\displaystyle x'_{i}:=x_{i},\ x'_{n+i}:=0.}$ Якщо ${\displaystyle x_{i}<0,}$ то нехай ${\displaystyle x'_{i}:=0,\ x'_{n+i}:=-x_{i}.}$ Значеннями ${\displaystyle x'_{2n+i}}$ визначимо різницю ${\displaystyle b_{i}}$ і добутку i-го рядка матриці A і вектора x. Тоді так визначений вектор ${\displaystyle x'\in \mathbb {R} ^{2n+m}}$ є розв'язком системи рівнянь ${\displaystyle A'x'=b.}$

Застосовуючи лему Фаркаша до системи ${\displaystyle A'x'=b}$ отримуємо твердження наслідку.

Навпаки із теореми Гейла можна довести лему Фаркаша. Як і вище доводиться, що система ${\displaystyle y^{\top }A\leq 0,\quad y\in \mathbb {R} ^{m}}$ (яку транспонувавши зручніше розглядати у виді ${\displaystyle A^{\top }y\leq 0}$) має розв'язок тоді і тільки тоді коли має розв'язок невід'ємний розв'язок система ${\displaystyle A'y'=0,}$ де

${\displaystyle A':=[A^{\top }\quad -A^{\top }\quad I]}$ є матрицею розмірності n × (2m + n). Додаткова умова ${\displaystyle \langle y,b\rangle >0}$ при цьому виконується тоді і лише тоді коли для відповідного вектора ${\displaystyle y'}$ (що одержується із ${\displaystyle y}$, як ${\displaystyle x'}$ із ${\displaystyle x}$ вище) виконується умова ${\displaystyle \langle y',b'\rangle <0,}$ де ${\displaystyle b'}$ є вектором перші m координат якого є рівні відповідним координатам вектора ${\displaystyle b}$ помноженим на -1, наступні m координат є рівні відповідним координатам вектора ${\displaystyle b}$, а останні n координат є рівні 0.

Відповідно якщо друга система у твердженні леми Фаркаша не має розв'язків то система ${\displaystyle A'y'=0}$ не має невід'ємних розв'язків, що задовольняють нерівність ${\displaystyle \langle y',b'\rangle <0.}$ Тоді із теореми Гейла випливає існування ${\displaystyle x'\in \mathbb {R} ^{n}}$ для якого ${\displaystyle Ax'\leq -b,\quad -Ax'\leq b,\quad x'\leq 0.}$ Тоді ${\displaystyle x=x'}$ є розв'язком першої системи в умові леми Фаркаша.