24. LP duality and the simplex algorithm - Illinois Media Space

24. LP duality and the simplex algorithm

From Jeff Erickson

views comments

LP duality: swap roles of matrix constraints and variables
Weak duality theorem: cx ≤ yAx ≤ yb
Physical interpretation of optimal dual solution
Vocabulary: basis, location, value, feasible, locally optimal
Another primal-dual dictionary
Primal simplex: falling marble
Dual simplex: rising bubble
Starting primal simplex with dual simplex: rotate objective
Starting dual simplex with primal simplex: translate constraints
Open question: How many pivots?

…Read more Less…

Tags