Content deleted Content added
(1) Properly formated reference to Wolfram site. (2) Removed obsolete link "* http://www.linearprogramming.info/fundamental-theorem-of-linear-programming-and-its-properties/". (3) Added a reference to a book. |
m Moving Category:Theorems in analysis to Category:Theorems in mathematical analysis per Wikipedia:Categories for discussion/Log/2025 April 12#Category:Theorems in analysis |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 16:
:<math>c^T\left( x^\ast - \frac{\epsilon}{2} \frac{c}{||c||}\right) = c^T x^\ast - \frac{\epsilon}{2} \frac{c^T c}{||c||} = c^T x^\ast - \frac{\epsilon}{2} ||c|| < c^T x^\ast.</math>
Hence <math>x^\ast</math> is not an optimal solution, a contradiction. 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>, say <math>x_1, ..., x_t</math>. Then <math>x^\ast = \sum_{i=1}^t \lambda_i x_i</math> with <math>\lambda_i \geq 0</math> and <math>\sum_{i=1}^t \lambda_i = 1</math>. Observe that
:<math>0=c^{T}\left(\left(\sum_{i=1}^{t}\lambda_{i}x_{i}\right)-x^{\ast}\right)=c^{T}\left(\sum_{i=1}^{t}\lambda_{i}(x_{i}-x^{\ast})\right)=\sum_{i=1}^{t}\lambda_{i}(c^{T}x_{i}-c^{T}x^{\ast}).</math>
Line 29 ⟶ 28:
[[Category:Linear programming]]
[[Category:Theorems in mathematical analysis]]
| |||