Fundamental theorem of linear programming: Difference between revisions

Revision as of 02:04, 1 August 2015

Latest revision as of 03:07, 20 April 2025

(9 intermediate revisions by 9 users not shown)

Line 1:

{{short description|Extremes of a linear function over a convex polygonal region occur at the region's corners}}

In [[mathematical optimization]], the '''fundamental theorem of [[linear programming]]''' states, in a weak formulation, that the [[maxima and minima]] of a [[linear function]] over a [[convex polygon]]al region occur at the region's corners. Further, if an extreme value occurs at two corners, then it must also occur everywhere on the [[line segment]] between them.

Line 15 ⟶ 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 22:

==References==

* http://demonstrations.wolfram.com/TheFundamentalTheoremOfLinearProgramming/

* {{cite book |last=Bertsekas |first=Dimitri P. |title=Nonlinear Programming |year=1995 |edition=1st |publisher=Athena Scientific |___location=Belmont, Massachusetts |page=Proposition B.21(c) |isbn=1-886529-14-0}}

{{Fundamental theorems}}

* {{cite web |title=The Fundamental Theorem of Linear Programming |url=http://demonstrations.wolfram.com/TheFundamentalTheoremOfLinearProgramming/ |website=WOLFRAM Demonstrations Project |access-date=25 September 2024}}

[[Category:Fundamental theorems]]

{{mathapplied-stub}}

{{comp-sci-stub}}

[[Category:Linear programming]]

[[Category:Theorems in mathematical analysis]]