Linear Programming Duality 4: Weak Duality

In this video, we discuss the concept of Weak Duality in linear programming. The statement of weak duality is that when we are given a primal-dual pair of linear programs with feasible solutions, the value for the maximization problem will be smaller than the value for the minimization problem. This is by construction of the dual linear program (we have shown how this is true in earlier videos on duality). Further, this means that if the objective values are equal for the primal-dual pair of feasible solutions which are used, this must mean that those solutions are actually optimal solutions for their respective linear programs. We discuss this property, and show how it plays out in the context of an example linear program.

We conclude by seeing what conclusions we can draw from Weak Duality. Specifically, we fill out a chart of the possible feasibility combinations for the primal and dual (e.g. if the primal is unbounded, then this must mean the dual is infeasible, etc.), given that Weak Duality implies that not all combinations are possible.