Fundamental theorem of linear programming: Difference between revisions

Revision as of 18:09, 18 March 2011

Revision as of 12:51, 27 August 2011

Line 6:

:<math>\min c^T x \text{ subject to } x \in P</math>

Where <math>P = \{x \in \mathbb{R}^n : Ax \leq b\}</math>. If <math>P</math> is a bounded polyhedron (and thus a polytope) and <math>x^*</math> is an optimal solution to the problem, then <math>x^*</math> lies is either an extreme point (vertex) of <math>P</math>, or lies on a face <math>F \subset P</math> of optimal solutions.

==Proof==