单纯形法

问题概述

待求解的问题具有如下的一般形式：

$$\begin{aligned} &\mathop{\min}\limits_{x \in \mathbb{R}^n} c^T x\\ &\text{s.t. } Ax = b, \\ &\quad \;\;\;x \geq 0. \end{aligned}$$

单纯形算法

\begin{algorithm}\caption{单纯形法}
    \begin{algorithmic}
	    \Input{$c; A,b$}
	    \Output{$x = [x_B,x_N]$, 请注意按下标排列}
	    \Procedure{单纯形法}{$c;A,b$}
	    \State{随机给定基本指标集 $\mathcal{B} \subset [n]$ 与非基本指标集合 $\mathcal{N} = [n] -  \mathcal{B}$.}
        \While{1}
        \State{Set $B = [a_{i},\cdots](i\in\mathcal{B}, a_{i}\in A), N = A - B$.}
	    \State{Set $c_B = [c_{i},\cdots]^T(i\in\mathcal{B}, c_{i}\in c),c_N = c - c_B$}
	    \State{Solve $x_B$ for $Bx_{B}= b$ and Set $x_N = \vec{0}$}
	    \State{Solve $\lambda$ for $B^T \lambda = c_B$ and Set $s_{N} = c_N - N^T \lambda$}
        \IF{$s_N \geq \vec{0}$}
          \STATE{找到了最优解为 $[x_B, x_N]$ }
          \Break
		\Else
		  \State{choose $q\in \mathcal{N}$ randomly s.t. $s_q < 0$}
		  \State{Solve $d$: $Bd = A_q$}
		  \If{$d\leq \vec{0}$}
		    \State{问题无解}
		    \Break
		  \Else
		    \State{choose $p = \mathop{\min}\limits_{i\;| \; d_i >0} \frac{(x_B)_i}{d_i}$ $\quad$ (where $p\in \mathcal{B}$)}
		    \State{add $q \rightarrow\mathcal{B}$ and add $p\rightarrow\mathcal{N}$}
          \EndIf		  
        \ENDIF
	\EndWhile
	\EndProcedure
  \end{algorithmic}
\end{algorithm}

Example

$$\begin{aligned} &\min -5x_1 - x_2 \\ \text{st.} \quad & x_1 + x_2 \leq 5 \\ & 2x_1 + x_2 = 8 \\ & x_1, x_2 \geq 0 \end{aligned}$$

(1) 增加非限制变量，使成为标准型
(2) 利用单纯型法求解

解：(1) 原问题可转化为

$$\begin{aligned} \min &\quad c^T x \\ \text{st.} \quad & A x = b, x \geq 0 \end{aligned}$$

其中

$$\begin{aligned} &c = [-5, -1, 0, 0]^T, \quad x = [x_1, x_2, x_3, x_4]^T, \\ &A = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{bmatrix}, \quad b = \begin{bmatrix} 5 \\ 8 \end{bmatrix} \end{aligned}$$

(2) 采用单纯形法求解上述问题如下

a. 初始时，选取$B = \{ 3, 4 \} \Rightarrow N = \{ 1, 2 \}$.

$$\begin{aligned} &\Rightarrow x_B = [5, 8]^T, \; x_N = [0, 0]^T \\ &\Rightarrow 初始可行解 x = [0, 0, 5, 8]^T, 且此时目标函数值为0 \end{aligned}$$

又有$\lambda = B^{-T} c_B = [0, 0]^T, \; s_N = c_N - N^T \lambda = [-5, -1]^T < 0$

b. 选取 $q = 1\in\mathcal{N}$，此时 $A_1 = [1, 2]^T$，计算 $Bd = A_1$，得 $d = [1, 2]^T$。通过计算 $\frac{(x_B)_1}{d_1} = 5, \; \frac{(x_B)_2}{d_2} = 4$，则 $p = 4\in \mathcal{B}$。此时 $\mathcal{B} = \{1, 3\}, \; \mathcal{N} = \{2, 4\}.$ 对应矩阵 $B = \begin{bmatrix} 1 & 1 \\ 2 & 0 \end{bmatrix}, \; N = \begin{bmatrix} 1 & 0 \\ \frac{1}{2} & 1 \end{bmatrix}$，且$c_B = [-5, 0]^T, \; c_N = [-1, 0]^T$

计算得

$$\begin{aligned} & x_B = B^{-1} b = [4, 1]^T \; \Rightarrow x_N = [0, 0]^T \\ & \lambda = B^{-T} c_B = [0, -\frac{5}{2}]^T \\ & s_N = c_N - N^T \lambda = [\frac{1}{4}, \frac{5}{2}]^T \Rightarrow \text{stop} \end{aligned}$$

此时目标函数值为

$$c^T [4, 0, 1, 0] = -20.$$

$\blacksquare$