Основная теорема линейного программирования

В математической оптимизации фундаментальная теорема линейного программирования утверждает в слабой формулировке, что максимумы и минимумы линейной функции в выпуклой многоугольной области происходят в углах области. Далее, если экстремальное значение встречается в двух углах, то оно должно встречаться и везде на отрезке между ними.

Где . Если является ограниченным многогранником (и, следовательно, многогранником) и является оптимальным решением задачи, то является либо крайней точкой (вершиной) , либо лежит на грани оптимальных решений. ${\ displaystyle P = \ {x \ in \ mathbb {R} ^ {n}: Ax \ leq b \}}$ ${\ Displaystyle Р}$ ${\ Displaystyle х ^ {\ аст}}$ ${\ Displaystyle х ^ {\ аст}}$ ${\ Displaystyle Р}$ ${\ Displaystyle F \ подмножество P}$

Предположим, ради противоречия, что . Тогда существует такой, что шар радиуса с центром в содержится в , то есть . Следовательно, ${\ displaystyle x ^ {\ ast} \ in \ mathrm {int} (P)}$ ${\ Displaystyle \ эпсилон > 0}$ ${\ Displaystyle \ эпсилон}$ ${\ Displaystyle х ^ {\ аст}}$ ${\ Displaystyle Р}$ ${\ displaystyle B _ {\ epsilon} (x ^ {\ ast}) \ подмножество P}$