Fundamental theorem of linear programming: Difference between revisions

Content deleted Content added
Line 19:
Therefore, <math>x^\ast</math> must live on the boundary of <math>P</math>. If <math>x^\ast</math> is not a vertex itself, it must be the convex combination of vertices of <math>P</math>. That is that <math>x^\ast = \sum_{i=1}^t \lambda_i x_i</math> with <math>\lambda_i > 0</math> and <math>\sum_{i=1}^t \lambda_i = 1</math>. Then we must have
 
:<math>0 = c^{T}\left(x^{\ast}-\left(\sum_{i=1}^{t }\lambda_i x_ilambda_{i}x_{i}\right)-x^\ast\right) = c^{T}\left(\sum_{i=1}^{t }\lambda_i lambda_{i}(x_i - x^{\ast}-x_{i})\right) = \sum_{i=1}^{t }\lambda_i lambda_{i}(c^Tx_i - c^Tx{T}x^{\ast}-c^{T}x_{i})</math>
 
Since all terms in the sum are nonpositivenonnegative and the sum is equal to zero, we must have that each individual term is equal to zero. Hence, every <math>x_i</math> is also optimal, and therefore all points on the face whose vertices are <math>x_1, ..., x_t</math>, are all optimal solutions.
 
==References==