Every linear programming problem, referred to as a primal problem, can be converted in a dual problem, which provides an upper bound to the optimal value of the primal problem. In matrix form, we express the primal problem as:

Maximize $ c^Tx $

Subject to $ Ax \geq b, x\geq 0 $

The corresponding dual problem is:

Minimize $ b^Ty $

Subject to $ A^Ty\geq c, y\geq 0 $

Where y is used instead of x as the variable vector.

There are two ideas fundamental to duality theory. One is the fact that the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual.

Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood