Farkas Proof

Considere o Lema de Farkas, que afirma que dado um sistema linear, apenas uma das duas situações é válida:

1. Existe tal que e .
2. Existe tal que e .

Multiplicando por , temos:

Logo:

Como , e , concluímos que .

Ou seja, por contradição, concluímos que o Lema de Farkas é correto (ignorando os transpostos).

Agora, dado um problema primal:

E seu dual:

Pela dualidade fraca, temos:

Se é a solução ótima de para , por Farkas sabemos que caso a opção (1) tenha solução, a opção (2), que rege sobre com , não tem solução.

Qualquer que satisfaça deve satisfazer pela dualidade fraca.

Agora, considere e a possibilidade de:

com .

Então:

Para esse sistema de inequações ser infactível (dado na forma ), existiria então:

pelo Lema de Farkas (perceba que este é o Lema de Farkas considerando a slack na primeira condição).

Temos então que:

Caso , temos e .

Considere . Como , é satisfeita no primal. Mas como , isso contradiz o fato de ser a solução ótima.

Caso :

Se e , considere . Então , o que também contradiz o fato de ser a solução ótima.

Concluímos então que o sistema (1) é factível, então . Logo, a única solução factível é .