ABSTRACT
Linear programming (LP) has the form of a general optimization problem that has a linear objective function and linear constraint functions. Let denote a minimization primal LP and let denote its maximization dual. Then the objective function value of any feasible solution to is greater than or equal to the objective function value of any feasible solution to. Slack variables convert general linear inequalities to simple nonnegativity constraints. They are so useful they deserve consistent notation. The heart of the duality here is the reason why dual infeasibility means primal suboptimality. The plane is a set of points orthogonal to the objective function vector. A vertex of a three-dimensional polyhedron is at the intersection of three planes, rather than at the intersection of two lines. As before, it is visually evident that if there is an optimum solution there is an optimum solution at a vertex.
