Dual linear program
The dual of a given linear program (LP) is another LP that is derived from the original (the primal) LP in the following schematic way: Each variable in the primal LP becomes a constraint in the dual LP; Each constraint in the primal LP becomes a variable in the dual LP; The objective direction is inversed – maximum in the primal becomes minimum in the dual and vice versa. The weak duality theorem states that the objective value of the dual LP at any feasible solution is always a bound on the objective of the primal LP at any feasible solution (upper or lower bound, depending on whether it is a maximization or minimization problem).