На главную   ::   Содержание



Теорема о существовании оптимального базисного решения задачи линейного программирования. Критерий оптимальности

Определение 1.   Задача математического программирования:

\begin{displaymath}
\begin{array}{l}
f(x)\to\min\\
g_i(x)\leqslant 0\quad i=...
...ots,k\\
g_i(x)=0\quad i=k+1,\dots,m\\
x\in P
\end{array}
\end{displaymath}

Пусть

$\displaystyle X=\{x\in P:  g_i(x)\leq 0,  i=1,\dots,k, g_i(x)=0, 
i=k+1,\dots,m\}$

$\displaystyle Q=\{y\in \mathbb{R}^m:  y_i\geq 0,
i=1,\dots,k\}.$

Полагаем, что $ X\neq\varnothing$. Пусть $ f^\ast=\inf_{x\in X}f(x)$. Если $ x^\ast$--решение, то $ f(x^\ast)=f^\ast$, но решение не всегда существует.

Определение 2.   $ y^\ast\in Q$ называется вектором Куна--Таккера, если верно

$\displaystyle f^\ast\leqslant f(x)+\sum\limits_{i=1}^m y_i^\ast
g_i(x)\stackrel{def}{=}L(x,y^\ast)$ (регулярная функция Лагранжа)$\displaystyle .
$

Теорема 1.   Пусть $ P$ -- выпуклое $ f,g_1,\dots,g_k$ -- выпуклые на $ P$, $ g_{k+1},\dots,g_m$ -- линейные. Пусть хоть одно из следующих двух условий выполнено:
  1. $ k=m;   \exists  \overline x\in P:  g_i(\overline x)<0,\quad
i=1,\dots,m$.
  2. $ P$ -- полиэдр, $ f,g_1,\dots,g_k$ -- линейны, $ X\neq\varnothing$.
Тогда существует вектор Куна--Таккера.

Определение 3.   Двойственной называется задача следующего вида:

\begin{displaymath}
\begin{array}{l}
\varphi(y)\stackrel{def}{=}\inf_{x\in P}L...
...\max\\
y\in Y=\{y\in Q:  \varphi(y)>-\infty\}
\end{array}
\end{displaymath}

Теорема 2.   Пусть существует вектор Куна--Таккера и $ X\neq\varnothing$. Если $ f^\ast>-\infty$, то $ f^\ast=\varphi^\ast=\sup_{y\in Y}\varphi(y)$ и множество решений $ Y^\ast\neq\varnothing$ и совпадает с множеством векторов Куна--Таккера.

Определение 4.   Общая задача линейного программирования:

\begin{displaymath}
\begin{array}{ll}
\sum\limits_{j=1}^n c_jx_j\to\min& \\
...
...i,&i=k+1,\dots,m\\
x_j\geqslant 0б&j=1,\dots,s
\end{array}
\end{displaymath}

Пусть $ P=\{x\in \mathbb{R}^n:  x_j\geq 0,  j=1,\dots,s\}$, $ Q=\{y\in\mathbb{R}^m:  y_i\geq 0,  i=1,\dots,k\}$,

$\displaystyle L(x,y)=\sum\limits_{j=1}^n c_j x_j+\sum\limits_{i=1}^m y_i
\bigg...
...1}^m b_i
y_i+\sum\limits_{j=1}^n x_j\biggl(c_j-\sum_{i=1}^m a_{ij}y_i\biggr)
$

$\displaystyle \varphi(y)=\inf_{x\in P} L(x,y)=\begin{cases}\sum_{i=1}^m b_i y_i, &
y\in Y -\infty, & y\in Q\setminus Y\end{cases}
$

$\displaystyle Y=\left\{y\in Q:  \sum a_{ij}y_i \leq c_j,  j=1,\dots,s, \sum
a_{ij}y_i=c_j,  j=s+1,\dots,m\right\}.
$

Получили двойственную задачу:

\begin{displaymath}
\begin{array}{ll}
\sum\limits_{i=1}^m b_iy_i\to\min& \\
...
..._j&j=s+1,\dots,n\\
y_i\geqslant 0б&i=1,\dots,k
\end{array}
\end{displaymath}

Теорема 3.   Двойственная к двойственной совпадает с исходной.

Теорема 4. (критерий разрешимости задачи ЛП)   Пусть $ X\neq\varnothing$ и целевая функция ограничена снизу на допустимом множестве ( $ f^\ast>-\infty$). Тогда задача ЛП имеет решение.

Доказательство. По теореме 2. существует решение двойственной задачи. А по теореме 3. существует решение прямой задачи. $ \blacksquare$

Определение 5.   $ U$-- выпуклое множество, $ v\in U$ называется угловой точкой этого множества, если представление этой точки в следующем виде $ v=tv_1+(1-t)v_2,\quad v_1,v_2\in U, t\in (0,1)$ возможно только в одном случае: $ v_1=v_2=v$.

Поставим задачу ЛП в канонической форме:

\begin{displaymath}
\begin{array}{l}
<c,x>\to\max\\
Ax=b\\
x\geqslant\mathbb{O}
\end{array}
\end{displaymath}

Очевидно, что допустимое множество $ X=\{x\in \mathbb{R}^n: 
Ax=b, x\geq 0\}$ выпуклое. Будем считать, что $ \rank A=m$. Мы можем выбрать $ B=\left(A_{i_1}\vert\dots\vert A_{i_m}\right)$ ЛНЗ, а все остальные столбцы будем обозначать $ D=\left(A_{i_{m+1}}\vert\dots\vert A_{i_n}\right)$. Обозначим

$\displaystyle x_B=\begin{pmatrix}
x_{i_1} \\
\vdots \\
x_{i_m} \\
\en...
...D=\begin{pmatrix}
x_{i_{m+1}} \\
\vdots \\
x_{i_n} \\
\end{pmatrix}
$

$\displaystyle Ax=b\Leftrightarrow Bx_B+Dx_D=b\Leftrightarrow
x_B=B^{-1}b-B^{-1}Dx_D
$

Определение 6.   Переменные в $ x_B$ называются базисными, а в $ x_D$ -- не базисными.

Определение 7.   Решение системы $ Ax=b$ называется базисным, если $ x_D=\mathbb{O}$, т.е. $ x_B=B^{-1}b$.

Определение 8.   Базисом базисного решения называется совокупность столбцов $ A$, входящих в $ B$.

Определение 9.   Базисное решение называется допустимым, если $ x_B=B^{-1}b\geqslant \mathbb{O}$.

Определение 10.   Допустимое базисное решение называется невырожденным, если значения базисных переменных $ x_B>\mathbb{O}$, иначе оно вырождено.

Определение 11.   $ x\in X$ называют допустимым базисным решением, если столбцы матрицы $ A$, соответствующие ненулевым координатам вектора $ x$, линейно независимы.

Базис однозначно определяет допустимое базисное решение, обратное неверно.

Теорема 5.   Если $ X\neq\varnothing$, то существует допустимое базисное решение.

Теорема 6.   Любое допустимое базисное решение является угловой точкой множества $ X$ и наоборот.

Симплекс метод представляет собой вычислительную процедуру, осуществляющую перебор допустимых базисных решений задачи до нахождения оптимального допустимого решения. При этом на каждой итерации симплекс метода в зависимости от значений некоторых параметров делается один из трех следующих выводов:
  1. рассматриваемое ДБР является решением задачи;
  2. целевая функция неограниченно возрастает;
  3. осуществляется переход к новому допустимому базисному решению с нехудшим значением целевой функции.
Описание одной итерации симплекс метода. Пусть известно некоторое ДБР. $ v=(v_1,\dots,v_n)^T$. $ A_{i_1},\dots,A_{i_m}$ образуют базис точки $ v$. Будем рассматривать матрицу $ B$ базисных столбцов и соответствующие $ x_B, v_B, c_B, c_D$, введенные по аналогии.

$\displaystyle x_B=B^{-1}b-B^{-1}Dx_D=v_B-B^{-1}Dx_D,$    т.к. $\displaystyle v_B=B^{-1}b.$

\begin{displaymath}
\begin{array}{c}
\displaystyle f(x)=c^Tx=c_B^T x_B+c_D^T ...
...le= c^Tv-\sum_{k=m+1}^n x_{i_k}\Delta_{i_k}. \\
\end{array}
\end{displaymath}

Для $ k=1,\dots,m$ имеем $ \Delta_{i_k}=c_B^Te_k-c_{i_k}=0$.

Задача переписывается в следующем виде:

\begin{displaymath}
\begin{array}{l}
f(x)=c^Tv-\sum_{k=m+1}^n \Delta_{i_k} x_{...
... x_{i_k} B^{-1}A_{i_k}\\
x\geqslant \mathbb{O}
\end{array}
\end{displaymath}

Пусть $ \lambda_{sk}=(B^{-1}A_k)_s$.

Всю информацию о коэффициентах принято записывать в виде симплекс таблицы.

$\displaystyle \begin{tabular}{\vert l\vert l\vert l\vert l\vert l\vert l\vert l...
...elta$ & $\Delta_1$ & $\dots$ & $\Delta_m$ & f\\
\cline{1-5}
\end{tabular}
$

Как меняются переменные? Рассмотрим $ m+1\leq i_p\leq n$. $ x_{i_p}(\alpha)=\alpha,  x_{i_k}(\alpha)=v_{i_k}-\alpha \lambda_{k
i_p},  k...
...,   x_{i_k}(\alpha)=0,  k=m+1,\dots,n, 
f(x,\alpha)=f(v)-\Delta_{i_p}\alpha$. Мы хотим выбрать номер небазисной переменной $ i_p$ и ее значение $ \alpha$ так, чтобы точки, получающиеся по этим формулам, удовлетворяли всем ограничениям задачи и при этом $ f(w)\geq f(v)$. Возможны три случая:

1) $ \Delta_{i_k}\geq 0,   k=m+1,\dots,n$. Покажем, что в этом случае точка $ v$ -- решение. Рассмотрим $ x\in X$.

$\displaystyle f(x)=c^Tx=c_B^Tx_B+c_D^Tx_D\leq c_B^Tx_B+\sum_{k=m+1}^n (c_B^T)_k
B^{-1}A_{i_k}x_{i_k}\textcircled =
$

Это неравенство следует из неотрицательности $ \Delta_{i_k}=c_B^TB^{-1}A_{i_k}-c_{i_k}$.

$\displaystyle \textcircled = c_B^Tv_B-\sum_{k=m+1}^n (c_B^T)_k
B^{-1}A_{i_k}x_{i_k}+\sum_{k=m+1}^n (c_B^T)_k
B^{-1}A_{i_k}x_{i_k}=c_B^Tv_B=c^Tv=f(v),
$

т.е. $ v$ -- решение.

2) $ \exists   \Delta_{i_p}<0:  \lambda_{j i_p}\leq 0\quad \forall 
j$. Тогда задача не имеет решения.

Рассмотрим $ w(\alpha):  w_{i_p}(\alpha)=\alpha>0,
w_{i_k}(\alpha)=v_{i_k}-\alpha \lambda_{k i_p},  k=1,\dots,m, 
w_{i_k}(\alpha)=0,  k=m+1,\dots,n$. $ w(\alpha)\geq 0, Aw(\alpha)=b$ (т.к. мы пользовались формулами перехода), т.е. $ w\in X$. $ f(w)=f(v)-\alpha\Delta_{i_p}\to\infty$.

3) $ \forall  i_p:  \Delta_{i_p}<0\quad B^{-1}A_{i_p}\not\leq
\mathbb{O}$. Можем перейти к новому ДБР с нехудшим значением целевой функции.

$\displaystyle I=\{j:  j\in 1,\dots,m,  \lambda_{j i_p}>0\}\neq\varnothing
$

$\displaystyle \alpha=\min_{l\in I} \frac{v_{i_l}}{\lambda_{l i_p}}\geq 0
$

Пусть $ \alpha$ достигается на $ l=s$. Построим новую точку $ w$ по формулам пересчета. $ w_{i_p}=\alpha,  w_{i_k}=v_{i_k}-\alpha
\lambda_{k i_p},  k=1,\dots,m,  w_{i_k}=0,  k=m+1,\dots,n$. $ w\geq 0, Aw=b$. $ f(w)=f(v)-\alpha\Delta_{i_p}\geq f(v)$.

Теорема 7.   Точка $ w$ является допустимым базисным решением, базисом будут столбцы $ A_{i_k}, k=1,\dots,m,k\neq s$ и $ A_{i_p}$.



На главную   ::   Содержание