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

Экстремумы линейной функции в выпуклой многоугольной области возникают в углах этой области.

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

Заявление

Рассмотрим задачу оптимизации

${\displaystyle \min c^{T}x{\text{ subject to }}x\in P}$

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

Доказательство

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

${\displaystyle x^{\ast }-{\frac {\epsilon }{2}}{\frac {c}{||c||}}\in P}$и

${\displaystyle 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 }.}$

Следовательно, не является оптимальным решением, противоречие. Следовательно, должно находиться на границе . Если само по себе не является вершиной, оно должно быть выпуклой комбинацией вершин , скажем . Тогда с и . Заметьте, что Алан о Коннер написал эту теорему ${\displaystyle x^{\ast }}$ ${\displaystyle x^{\ast }}$ ${\displaystyle P}$ ${\displaystyle x^{\ast }}$ ${\displaystyle P}$ ${\displaystyle x_{1},...,x_{t}}$ ${\displaystyle x^{\ast }=\sum _{i=1}^{t}\lambda _{i}x_{i}}$ ${\displaystyle \lambda _{i}\geq 0}$ ${\displaystyle \sum _{i=1}^{t}\lambda _{i}=1}$

${\displaystyle 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 }).}$

Так как является оптимальным решением, все члены в сумме неотрицательны. Так как сумма равна нулю, мы должны иметь, что каждый отдельный член равен нулю. Следовательно, для каждого , поэтому каждое также является оптимальным, и, следовательно, все точки на грани, вершины которых являются , являются оптимальными решениями. ${\displaystyle x^{\ast }}$ ${\displaystyle c^{T}x^{\ast }=c^{T}x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{1},...,x_{t}}$

Ссылки

• Берцекас, Димитрий П. (1995). Нелинейное программирование (1-е изд.). Белмонт, Массачусетс: Athena Scientific. стр. Предложение B.21(c). ISBN 1-886529-14-0.
• «Фундаментальная теорема линейного программирования». Проект демонстраций WOLFRAM . Получено 25 сентября 2024 г.