Linear Programming Duality 8b: Algorithmic aspects of Farkas Lemma

The previous video discussed how every infeasible linear program has a certificate of infeasibility, but did not discuss how we could actually find such a certificate. In this video, we discuss a method of algorithmically finding it. Namely, we construct the auxiliary linear program and run the Simplex algorithm on it. The vector 'y' which appears in the canonical form of the objective function for the optimal basis that Simplex finds will indeed be a certificate of infeasibility.