Linear Programming Duality 8a: Farkas' Lemma

Farkas' lemma guarantees that every infeasible linear program has a 'certificate' vector y that proves the LP is infeasible. This fact is a consequence of Strong Duality. (In fact, it is equivalent to Strong Duality, although this is not obvious at first glance, nor do we prove so in this video.)