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

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

Заявление

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

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

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

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

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

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

и

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 }.

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

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 }).

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

Ссылки