MIT 6.854 Spring 2016 Lecture 10: Introduction to Linear Programming

[@aleksagordic9593]

00:00 - 10:55 intro, recap and "homework" (if u r Dantzig xD) 10:55 - 15:50 what is LP? "Canonical" Form 15:50 - 21:30 weak duality lemma 22:45 - 38:30 applying weak duality lemma to the max flow problem 41:00 - 47:40 geometrical abstraction (convex polyhedron) 48:10 - 54:30 projection theorem 55:40 - 1:06:35 Farkas's lemma and proof 1:06:35 - 1:11:10 claim 1 1:11:10 - 1:13:40 claim 2 1:13:40 - 1:15:50 wrap up of the proof

[@venkatakarthikbandaru8326]

Farkas lemma could've been geometrically motivated too. For instance if we pick 4 vectors A_1 , A_2 , A_3 , b in R^3, then either i) b is a non negative linear combination of A_i s or ii) there is a plane that separates A_i s and b {ie A_i s lie on one corresponding halfspace and b lies in (interior of) other halfspace}]. Now the projection argument in proof makes a lot of sense geometrically.

[@igormorgado]

Nice try with the open conjecture as homework.