[学习笔记] - 线性规划

线性规划（LP）

$\begin{aligned} min &\qquad c_1x_1 + \cdot + c_nx_n & \\ s.t. &\qquad a_{11}x_1 + \cdots + a_{1n}x_n \leq b_1 \\ &\qquad a_{m1}x_1 + \cdot + a_{mm}x_n \leq b_{m} \\ &\qquad x_1, \cdots, x_n \geq 0 \end{aligned}$

形式化定义

$\begin{aligned} min &\qquad \mathbf{c}^T\mathbf{x} & \\ s.t. &\qquad A\mathbf{x} \leq \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}$

最优化基本概念参照([学习笔记] - 非线性规划)

标准LP问题

从实际中总结出来的LP形式不完全一样

• 目标函数是最大值或最小值
• 约束条件是等式约束或不等式约束
• 变量有上界或下界或无界

$\begin{aligned} min &\qquad z = \mathbf{c}^T\mathbf{x} & \\ s.t. &\qquad A\mathbf{x} = \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}$

标准化

• 目标函数的转换：$\max z \rightarrow \min (-z)$
• 约束条件的转换（引入松弛变量$x_{n+i}$）

$\begin{aligned} \sum^n_{j=1}a_{ij}x_{j} \leq b_{i} &\Rightarrow \begin{cases} \sum^n_{j=1}a_{ij}x_j + x_{n+i} = b_i \\ x_{n+1} \geq 0 \end{cases} \\ \sum^n_{j=1}a_{ij}x_{j} \geq b_{i} &\Rightarrow \begin{cases} -\sum^n_{j=1}a_{ij}x_j + x_{n+i} = -b_i \\ \sum^n_{j=1}a_{ij}x_j - x_{n+i} = b_i \\ x_{n+1} \geq 0 \end{cases} \end{aligned}$

• 变量的非负约束

$\begin{aligned} a \leq x_i \leq b &\Leftrightarrow \begin{cases} x'_i = x_i - a \\ x'_i + x_{n+i} = b - a \\ x'_i \geq 0 \end{cases} \\ x_i\text{自由变量} &\Leftrightarrow \begin{cases} x_i = x'_i - x''_i \\ x'_i, x''_i \geq 0 \end{cases} \\ x_i \leq 0 &\Leftrightarrow \begin{cases} x'_i = -x_i \\ x'_i \geq 0 \end{cases} \end{aligned}$

基本性质

• 可行解：称满足线性规划的约束条件的解$\mathbf{x} = (x_1, x_2, \cdots, x_n)^T$，为线性规划问题的可行解
• 可行域：所有可行解组成的集合称为可行域，记为$D$
  • 可行域为凸集
  • $D = \varnothing$，无解或不可行
  • $D \neq \varnothing$，但目标函数在$D$上无上界，无解
  • $D \neq \varnothing$，且目标函数有限的最优解，有最优解
• 最优解：满足线性规划目标函数的可行解，且是目标函数达到最小的可行解
• 基：设$A=(a_{ij})_{mn}$是约束方程组的系数矩阵，其秩为$m(m < n)$，若$B$是矩阵$A$中$m \times n$阶非奇异子阵，则$B$是基
• 基向量：$B$的列向量$\mathbf{p}_i$为线性规划问题的基向量
• 基变量：与基向量$\mathbf{p}_i$对应的决策变量$\mathbf{x}_i$为线性规划问题的基变量
• 非基变量：与基变量相反的基变量

最优基本可行解

在线性规划中，设矩阵$A$的秩为$m$，又假设$A = [B, N]$，其中$B$是$m$阶可逆矩阵，如果$A$的前$m$列是线性相关的，可以通过基本变换，使前$m$列成为线性无关，$\mathbf{x}$可以记作

$\mathbf{x} = \begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix}$

其中$\mathbf{x}_B$为$B$中的列对应，$\mathbf{x}_N$为$N$的列对应，这样可以改写$A\mathbf{x} = \mathbf{b}$为

$\begin{aligned} [B, N]\begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix} &= \mathbf{b} \\ B\mathbf{x}_B + N\mathbf{x}_N &= \mathbf{b} \end{aligned}$

两边同乘$B^{-1}$，移项后可以得到

$\mathbf{x}_B = B^{-1}\mathbf{b} - B^{-1}N\mathbf{x}_N$

令$\mathbf{x}_N = 0$，得到解

$\mathbf{x} = \begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix} = \begin{bmatrix} B^{-1}\mathbf{b} \\ 0 \end{bmatrix}$

• 基本解：称上述$\mathbf{x}$为方程组$A\mathbf{x} = \mathbf{b}$的一个基本解
• 基矩阵：$B$，简称为基
• 基变量：$\mathbf{x}_B$的各分量
  • 一组基：基变量的全体$\mathbf{x}_{B_1}, \mathbf{x}_{B_2}, \cdots, \mathbf{x}_{B_n}$
• 非基变量：$\mathbf{x}_N$的各分量

如果$B^{-1}\mathbf{b} \geq 0$，则

• 基本可行解：称$\mathbf{x}$为方程组$A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0$的基本可行解
  • 一组可行基：基变量的全体$\mathbf{x}_{B_1}, \mathbf{x}_{B_2}, \cdots, \mathbf{x}_{B_n}$
• 可行基矩阵：称$B$为可行基矩阵
• 非退化的：若$B^{-1}\mathbf{b} > 0$，即基变量的取值均为正数，则基本可行解是非退化的
• 可退化的基本可行解：满足$B^{-1}\mathbf{b} \geq 0$且至少有一个分量是零

基本可行解的存在问题

• 定理：如果$A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0$有可行解，则一定存在基本可行解，其中$A$是$m \times n$矩阵，$A$的秩为$s$
• 定理：令$K = \lbrace \mathbf{x}|A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0 \rbrace, A$是$m \times n$矩阵，$A$的秩为$m$，则$K$的极点集与$A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0$的基本可行解集等价
• 定理：如果线性规划存在有限最优解，则目标函数的最优值可在某个极点上达到

当线性规划问题存在最优解时，一定存在一个基本可行解，且它是最优解，线性规划问题变为求最优基本可行解

单纯性方法

由基本可行解的存在可知道，求解线性规划问题归结于找最优基本可行解，单纯性的方法的基本思想，就是从一个基本可行解出发，求一个使目标函数值所有改善的基本可行解，这样不断的改善基本可行解，力图达到最优基本可行解，考虑问题

$\begin{aligned} min &\qquad f \xlongequal{def} \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} = \mathbf{b} \\ &\qquad \mathbf{x} \geq 0 \end{aligned}$

• $A$是$m \times n$矩阵，秩为$m$
• $\mathbf{c}$是$n$维行向量
• $\mathbf{x}$是$n$维列向量
• $\mathbf{b} \geq 0$是$m$维列向量
• 符号$\xlongequal{def}$表示右端的表达式是左端的定义式，也就是目标函数$f$的具体形式就是$\mathbf{c}\mathbf{x}$

记

$A = \begin{pmatrix} \mathbf{p}_1 & \mathbf{p}_2 & \cdots & \mathbf{p}_n \end{pmatrix}$

现在通过列调换之后，将$A$分解为$\begin{pmatrix}B, N\end{pmatrix}$，使得$B$是基矩阵，$N$是非基矩阵，设

$\mathbf{x}^{(0)} = \begin{bmatrix} B^{-1}\mathbf{b} \\ \mathbf{0} \end{bmatrix}$

是基本可行解，则在$\mathbf{x}^{(0)}$处的目标函数值

$\begin{aligned} f_0 &= \mathbf{c}\mathbf{x}^{(0)} = \begin{pmatrix} \mathbf{c}_B & \mathbf{c}_N \end{pmatrix} \begin{bmatrix} B^{-1}\mathbf{b} \\ \mathbf{0} \end{bmatrix} \\ &= \mathbf{c}_B B^{-1}\mathbf{b} \end{aligned}$

• $\mathbf{c}_B$是$\mathbf{c}$中与基变量对应的分量组成的$m$维行向量
• $\mathbf{c}_N$是$\mathbf{c}$中与非基变量对应的分量组成的$n - m$维行向量

设

$\mathbf{x} = \begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix}$

是任一一个可行解，由$A\mathbf{x} = \mathbf{b}$得到

$\mathbf{x}_B = B^{-1}b - B^{-1}N\mathbf{x}_N$

在点$\mathbf{x}$处的目标函数值为

$\begin{aligned} f &= \mathbf{c}\mathbf{x} = \begin{pmatrix} \mathbf{c}_B & \mathbf{c}_N \end{pmatrix} \begin{bmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{bmatrix} \\ &= \mathbf{c}_B\mathbf{x}_B + \mathbf{c}_N\mathbf{x}_N \\ &= \mathbf{c}_B(B^{-1}\mathbf{b} - B^{-1}N_{\mathbf{x}_N}) + \mathbf{c}_N\mathbf{x}_N \\ &=\mathbf{c}B^{-1}\mathbf{b} - (\mathbf{c}_BB^{-1}N - \mathbf{c}_N)\mathbf{x}_N \\ &=f_0 - \sum_{i \in R}(\mathbf{c}_BB^{-1}\mathbf{p}_i - c_i)x_i \\ &= f_0 - \sum_{i \in R}(z_i - c_i)x_i \end{aligned}$

• $R$是非基变量下标集

$z_i = \mathbf{c}_BB^{-1}\mathbf{p}_i$

由上面的式子可以知道，选取适当的自由未知量$x_i, (i \in R)$就有可能使得

$\sum_{i \in R}(z_i - c_i)x_i > 0$

从而得到使目标函数值减小的新的基本可行解，为此

• 在原来的$n - m$个非基变量中，使得$n - m - 1$个变量仍然取$0$
• 令一个非基变量$x_k$增大（即取正值），来实现目的

我们需要找到方法来确定下标$k$，当$x_i, (i \in R)$取值相同时，$z_i - c_i$（正数）越大，目标函数值下降越多，因此选择$x_k$，使得

$z_k - c_k = \max_{i \in R} (z_i - c_i)$

假设$z_k - c_k > 0$，$x_k$由零变为正数后，得到方程组$A\mathbf{x} = \mathbf{b}$的解

$\begin{aligned} \mathbf{x}_B &= B^{-1}\mathbf{b} - \mathbf{B}^{-1}\mathbf{p}_kx_k \\ &= \overline{\mathbf{b}} - \mathbf{y}_kx_k \end{aligned}$

• $\overline{\mathbf{b}}, \mathbf{y}_k$是$m$维列向量
  • $\overline{\mathbf{b}} = B^{-1}\mathbf{b}$
  • $\mathbf{y}_k = B^{-1}\mathbf{p}_k$

$\begin{gathered} \mathbf{x}_B = \begin{bmatrix} x_{B_1} \\ x_{B_2} \\ \vdots \\ x_{B_m} \end{bmatrix} = \begin{bmatrix} \overline{b}_1 \\ \overline{b}_2 \\ \vdots \\ \overline{b}_m \end{bmatrix} - \begin{bmatrix} y_{1k} \\ y_{2k} \\ \vdots \\ y_{mk} \end{bmatrix}x_k \\ \mathbf{x}_N = \begin{pmatrix} 0 & \cdots & 0 & x_k & 0 & \cdots & 0 \end{pmatrix}^T \end{gathered}$

得到新的点，目标函数值为

$f = f_0 - (z_k - c_k)x_k$

那么如何确定$x_k$的取值呢

• $x_k$取值越大函数值下降越多
• $x_k$的取值受到可行性的限制，不能无限增大
• 对于某个$i$
  • 当$y_{ik} \leq 0$时，$x_k$取任何正值时，总成立$x_{B_i} \geq 0$
  • 当$y_{ik} > 0$时，为保证

$x_{B_i} = \overline{b}_i - y_{ik}x_k \geq 0$

就需要

$x_k \leq \frac{\overline{b}_i}{y_{ik}}$

所以，为了使得$\mathbf{x}_B \geq 0$，则使

$x_k = \min(\frac{\overline{b}_i}{y_{ik}} \Big | y_{ik} > 0) = \frac{\overline{b}_r}{y_{rk}}$

原来的基变量$x_{B_i} = 0$，得到新的可行解

$\mathbf{x}_N = \begin{pmatrix} x_{B_i} & \cdots & x_{B_{r-1}} &0& x_{B_{r+1}} & 0 & \cdots &x_k& 0&\cdots&0 \end{pmatrix}^T$

这个解一定是基本可行解，经过上述的转换

• $x_k$由原来的非基变量变成了基变量
• $x_{B_r}$由原来的基变量变成了非基变量
• 目标函数值减少了$(z_k - c_k)x_k$

重复以上过程，就可以进一步改善基本可行解，直到所有的$(z_i - c_i)$均为非正数，即任意的非基变量取正值都不能使得目标函数值减小为止

在线性规划中，通常称$z_i - c_i$为判别数或检验数

• 在极小化问题中，对于某个基本可行解，所有$z_i - c_i \leq 0$，则这个基本可行解使最优解
• 在极大化问题中，对于某个基本可行解，所有$z_i - c_i \geq 0$，则这个基本可行解使最优解

$z_i - c_i = \mathbf{c}_BB^{-1}\mathbf{p}_i - c_i, \quad j = 1,\cdots,n$

单纯形方法步骤

首先要确定一个初始基本可行解，设初始基为$B$

• 解$Bx_B = \mathbf{b}$，求得$x_B = B^{-1}\mathbf{b} = \overline{\mathbf{b}}$，令$x_N = 0$，计算目标函数值$f = \mathbf{c}_B\mathbf{x}_B$
• 求单纯性乘子$\mathbf{w}$，解$\mathbf{w}B = \mathbf{c}_B$，得到$\mathbf{w} = \mathbf{c}_BB^{-1}$，对于所有非基变量，计算判别数$z_j - c_j = \mathbf{w}\mathbf{p}_i - c_i$，令

$z_k - c_k = \max_{i \in R} (z_i - c_i)$

若$z_k - c_k \leq 0$，则对于所有非基变量$z_i - c_i \leq 0$对应基变量的判别数总是零，因此停止计算，线性基本可行解即为最优解

• 解$B\mathbf{y}_k = \mathbf{p}_k$，得到$\mathbf{y}_k = B^{-1}\mathbf{p}_k$，若$\mathbf{y}_k \leq 0$，即$\mathbf{y}_k$的每个分量均为非正数，则停止计算，问题不存在有限最优解
• 确定下标$r$，使得

$\frac{\overline{b}_r}{y_{rk}} = \min(\frac{\overline{b}_i}{y_{ik}} \Big | y_{ik} > 0)$

• $x_{B_r}$为离基变量，$x_k$为进基变量，用$\mathbf{p}_k$替换$\mathbf{p}_{B_r}$，得到新的基矩阵$B$，返回步骤一

单纯形方法收敛性

令

$z_k = c_k = \max(z_j - c_j)$

每次迭代都会是一下三种情况

• $z_k - c_k \geq 0$，这时现行基本解可行解就是最优解
• $z_k - c_k > 0$且$y_k \leq 0$，无界情形
• $z_k - c_k > 0$且$y > 0$，可以求出新的可行解，若$x_k = \frac{\overline{b_r}}{y_{rk}} > 0$，则函数值下降

当极小化线性规划问题存在最优解的时候，对于非退化情形，每次迭代中，均有：

$\mathbf{x}_B = B^{-1}\mathbf{b} = \overline{\mathbf{b}} > 0$

从而，自然的

$x_k = \frac{\overline{b}_r}{y_{rk}} > 0$

对于非退化情形，经过迭代，函数值减小，每次迭代得到的基本可行解互不相同，基本解个数有限，所有有限次迭代必能达到最优解

对于非退化问题，单纯性方法经有限次迭代能达到最优基本可行解，或得出无界结论

单纯形方法表格法

• $A$：写作$(B, N)$
• $\mathbf{x}$：写作$\begin{bmatrix}\mathbf{x}_B\\\mathbf{x}_N\end{bmatrix}$
• $\mathbf{c}$：写作$(\mathbf{c}_B, \mathbf{c}_N)$

线性规划可以等价形式

$\begin{aligned} min &\qquad f \\ s.t. &\qquad f - \mathbf{c}_B\mathbf{x}_B - \mathbf{c}_N\mathbf{x}_N = 0 \\ &\qquad B\mathbf{x}_B + N\mathbf{x}_N = \mathbf{b} \\ &\qquad \mathbf{x}_B \geq \mathbf{0}, \mathbf{x}_N \geq \mathbf{0} \end{aligned}$

对上诉条件2两端乘$B^{-1}$得到，等于对方程组进行行变换，将基变量的系数变为单位矩阵

$\mathbf{x}_B + B^{-1}N\mathbf{x}_N = B^{-1}\mathbf{b}$

利用$\mathbf{c}_B$左乘两端，加到条件1上，可以得到

$f + 0 \cdot \mathbf{x}_B + (\mathbf{c}_BB^{-1}N - \mathbf{c}_N)\mathbf{x}_N = \mathbf{c}_BB^{-1}\mathbf{b}$

线性规划可以等价形式

$\begin{aligned} min &\qquad f \\ s.t. &\qquad \mathbf{x}_B + B^{-1}N\mathbf{x}_N = B^{-1}\mathbf{b} \\ &\qquad f + 0 \cdot \mathbf{x}_B + (\mathbf{c}_BB^{-1}N - \mathbf{c}_N)\mathbf{x}_N = \mathbf{c}_BB^{-1}\mathbf{b} \\ &\qquad \mathbf{x}_B \geq \mathbf{0}, \mathbf{x}_N \geq \mathbf{0} \end{aligned}$

化为表格

	$f$	$\mathbf{x}_b$	$\mathbf{x}_N$	右端
$\mathbf{x}_B$	0	$\mathbf{I}_m$	$B^{-1}N$	$B^{-1}\mathbf{b}$
$f$	1	0	$\mathbf{c}_BB^{-1}N - \mathbf{c}_N$	$\mathbf{c}_BB^{-1}\mathbf{b}$

其中

• $B^{-1}N$：$B^{-1}(\mathbf{p}_{N_1},\mathbf{p}_{N_2},\cdots,\mathbf{p}_{N_{n-m}}) = (\mathbf{y}_{N_1},\mathbf{y}_{N_2},\cdot,\mathbf{y}_{N_{n-m}})$
• $B^{-1}\mathbf{b}$：$(\overline{b}_1,\overline{b}_2,\cdot,\overline{b}_m)^T$

令$\mathbf{x}_N = 0$，则基变量$\mathbf{x}_B = B^{-1}\mathbf{b}$

$\begin{aligned} \mathbf{c}_BB^{-1}N - \mathbf{c}_N &= \mathbf{c}_BB^{-1}(\mathbf{p}_{N_1},\mathbf{p}_{N_2},\cdots,\mathbf{p}_{N_{n-m}}) - (c_{N_1},c_{N_2},\cdots,c_{N_{n-m}}) \\ &= (z_{N_1},z_{N_2},\cdots,z_{N_{n-m}}) - (c_{N_1},c_{N_2},\cdots,c_{N_{n-m}}) \\ &= (z_{N_1} - c_{N_1},z_{N_2} - c_{N_Z},\cdots,z_{N_{n-m}} - c_{N_{n-m}}) \end{aligned}$

从而可以得到

	$x_{B_1}$	$\cdots$	$x_{B_r}$	$\cdots$	$x_{B_m}$	$\cdots$	$x_j$	$\cdots$	$x_k$
$x_{B_1}$	$\color{green}1$	$\color{green}\cdots$	$\color{green}0$	$\color{green}\cdots$	$\color{green}0$	$\cdots$	$y_{1j}$	$\cdots$	$y_{1k}$	$\cdots$	$\overline{b}_1$
$\vdots$	$\color{green}\vdots$		$\color{green}\vdots$		$\color{green}\vdots$		$\vdots$		$\vdots$		$\vdots$
$x_{B_r}$	$\color{green}0$	$\color{green}\cdots$	$\color{green}1$	$\color{green}\cdots$	$\color{green}0$	$\cdots$	$y_{rj}$	$\cdots$	$\color{red}y_{rk}$	$\cdots$	$\overline{b}_r$
$\vdots$	$\color{green}\vdots$		$\color{green}\vdots$		$\color{green}\vdots$		$\vdots$		$\vdots$		$\vdots$
$x_{B_m}$	$\color{green}0$	$\color{green}\cdots$	$\color{green}0$	$\color{green}\cdots$	$\color{green}1$	$\cdots$	$y_{mj}$	$\cdots$	$y_{mk}$	$\cdots$	$\overline{b}_m$
$f$	$0$	$\cdots$	$0$	$\cdots$	$0$	$\cdots$	$z_j - c_j$	$\cdots$	$z_k - c_k$	$\cdots$	$\mathbf{c}_B\overline{\mathbf{b}}$

假设$\overline{\mathbf{b}} = B^{-1}\mathbf{b} \geq 0$，则上表已经有一个基本可行解，即

$\mathbf{x}_B = \overline{\mathbf{b}}, \quad \mathbf{x}_n = \mathbf{0}$

• 若$\mathbf{c}_B^{-1}N - \mathbf{c}_N \leq 0$，则现行基本解为最优解
• 若$\mathbf{c}_B^{-1}N - \mathbf{c}_N > 0$，需用主元消去法求改进的基本可行解
  • 如果在表的最后一行中，有$z_k - c_k = \max(z_j - c_j)$，则选择$x_k$，所对应的列为主列
  • 令$\frac{\overline{b}_r}{y_{rk}} = \min(\frac{\overline{b}_i}{y_{ik}} \Big | y_{ik} > 0)$，则第$r$行为主行
  • 主列和主行交叉处的元素$y_{rk}$称为主元
  • 用主元$y_{rk}$除第$r$行（主行），再把$r$行的若干倍分布加到各行，使主列中个元素（除$r$行）为$0$
  • 也就是把主列化为单位向量，$x_k$由非基变量变成基变量，$x_{B_r}$由基变量变成非基变量
  • 基变量的系数矩阵$B$在表中总是单位矩阵，因此右端列$\overline{b}$就是新的基变量取值
  • 然后进行下一次迭代即可

两阶段法

使用单纯形方法，需要给定一个初始基本可行解，我们需要直到怎么求初始基本可行解，考虑下面的线性规划标准形问题

$\begin{aligned} min &\qquad \mathbf{c}^T\mathbf{x} & \\ s.t. &\qquad A\mathbf{x} \leq \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}$

• 若$A$中包含$m$阶单位矩阵，则初始基本可行解可以立刻得到
  • $A = [\mathbf{I}_m, N]$
  • $x = \begin{bmatrix}\mathbf{x}_B\\\mathbf{x}_N\end{bmatrix} = \begin{bmatrix}\mathbf{b}\\\mathbf{0}\end{bmatrix}$
• 若$A$中不包含$m$阶单位矩阵，则采用以下方法

设$A$中不包含$m$阶单位矩阵，为了使约束方程的系数矩阵中含有$m$阶单位矩阵，将每一格方程增加一个非负变量，令

$\begin{aligned} A\mathbf{x} + x_a = \mathbf{b} \\ x \geq 0, x_a \geq 0 \end{aligned}$

即

$\begin{aligned} \begin{pmatrix} A, \mathbf{I}_m \end{pmatrix} \begin{bmatrix} x \\ x_a \end{bmatrix} = \mathbf{b} \\ x \geq 0, x_a \geq 0 \end{aligned}$

显然

$\begin{bmatrix} x \\ x_a \end{bmatrix} = \begin{bmatrix} \mathbf{0} \\ \mathbf{b} \end{bmatrix}$

是一个基本可行解，上述的意义在于，从$\begin{pmatrix}A, \mathbf{I}_m\end{pmatrix} \begin{bmatrix}x\\x_a\end{bmatrix} = \mathbf{b}$已知的基本可行解出发，能够求出一个使$x_a = \mathbf{0}$的基本可行解，那么就可以得到原来线性规划问题的基本可行解

向量$x_a \geq 0$称为人工变量

• 松弛变量：将不等式约束改为等式约束，改写前后问题等价
• 人工变量：改变了原来约束条件，改写前后问题不等价

两阶段法·第一阶段

• 利用单纯形方法消去人工变量
  • 把人工变量都变成非基变量
  • 求出原来的问题的基本可行解

$\begin{aligned} min &\qquad \mathbf{e}^Tx_a \\ s.t. &\qquad Ax + x_a = \mathbf{b} \\ &\qquad x, x_a \geq 0 \end{aligned}$

• $\mathbf{e} = \begin{pmatrix}1,1,\cdots,1\end{pmatrix}^T$，分量全是$1$的$m$维列向量
• $x_a = (x_{n+1}, x_{n+2}, \cdots, x_{n+m})^T$，人工变量构成的$m$维列向量

$x = 0, x_a = b$是线性规划的一个基本可行解，目标函数在可行域上有下降，则必然存在最优基本可行解
求解线性规划，设得到的最优基本可行解是$(\overline{x}^T, \overline{x}^T_a)^T$，此时必有下列三种情形之一

• $\overline{x}^T_a \neq 0$，此时线性规划无可行解
• $\overline{x}^T_a = 0$且$x_a$的分量都是非基变量，此时$m$个基变量都是原来的变量，则$\begin{bmatrix}x\\x_a\end{bmatrix} = \begin{bmatrix}\overline{x}\\\mathbf{0}\end{bmatrix}$是线性规划的基本可行解，则$x = \overline{x}$是原线性规划的一个基本可行解
• $\overline{x}^T_a = 0$且$x_a$的分量都是基变量，可用主元消去法
  • 把原变量中非基变量引进基，替换出基变量中的人工变量，再开始二阶法的第二阶段

两阶段法·第二阶段

• 将第一阶段的解，带入回去
• 对于刚刚引入的人工变量的列，可以直接除去
• 第一阶段的基变量，对应第二阶段的基变量，其等式的值即为第一阶段解的值

单纯性方法退化情景

在非退化的情形下，单纯性方法经过有限次迭代必然达到最优解。但是对于非退化情形（$B^{-1}\mathbf{b} \geq 0$且至少有一个分量是$0$），即使最优解存在，也有可能求不出最优解，出现循环现象

摄动法

考虑以下线性规划问题

$\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad Ax = \mathbf{b} \\ &\qquad x \geq 0 \end{aligned}$

让向量$\mathbf{b}$向右摄动，即

$\mathbf{b}(\varepsilon) = \mathbf{b} + \sum^n_{j=1}\varepsilon^j\mathbf{p}_j$

• $\varepsilon$是充分小的正数
• $\varepsilon^j$表示$\varepsilon$的$j$次方
• $\mathbf{p}_j$是矩阵$A$的第$j$列

问题转化为

$\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} = \mathbf{b}(\varepsilon) \\ &\qquad \mathbf{x} \geq 0 \end{aligned}$

定理：对于线性规划问题，存在实数$\varepsilon_1 > 0$，使得当$0 < \varepsilon < \varepsilon_1$时，摄动问题是非退化的。

证明：按照之前，$A$的秩是$m$，因此它能分解为$[B, N]$，其中$B$可逆，$\mathbf{x}$可以分解为$\mathbf{x}=\begin{bmatrix}\mathbf{x}_B\\\mathbf{x}_N\end{bmatrix}$，由$A\mathbf{x} = \mathbf{b}(\varepsilon)$得到

$\begin{aligned} \mathbf{x}_B &= B^{-1}\mathbf{b}(\varepsilon) - B^{-1}N\mathbf{x}_N \\ &= B^{-1}(\mathbf{b} + \sum^n_{j=1}\varepsilon^j\mathbf{p}_j) - B^{-1}N\mathbf{x}_N \\ &= B^{-1}\mathbf{b} + \sum^n_{j=1}\varepsilon^jB^{-1}\mathbf{p}_j - B^{-1}N\mathbf{x}_N \\ &= \overline{\mathbf{b}} + \sum^n_{j=1}\varepsilon^j\mathbf{y}_j - B^{-1}N\mathbf{x}_N \end{aligned}$

把上式按照分量写出

$x_{B_i} = \overline{b} + \varepsilon^{B_i} + \sum_{j \in R}y_{ij}\varepsilon^j - \sum_{j \in R}y_{ij}x_i, \quad i = 1,\cdots, m$

在基$B$下，基本解是

$\begin{aligned} x_{B_i} &= \overline{b} + \varepsilon^{B_i} + \sum_{j \in R}y_{ij}\varepsilon^j, \quad i = 1,\cdots, m \\ x_j &= 0, j \in R \end{aligned}$

• 定理：设对于充分小的$\varepsilon > 0, \hat{\mathbf{x}}(\varepsilon)$是线性规划的基本可行解，则$\hat{\mathbf{x}}(0)$是原来线性规划的基本可行解
• 推论：设对于充分小的$\varepsilon > 0, \hat{\mathbf{x}}(\varepsilon)$是线性规划的最优解，则$\hat{\mathbf{x}}(0)$是原来的最优解
• 定理：若线性规划没有可行解，则原来线性规划也没有可行解
• 定理：若对于充分小的$\varepsilon > 0$线性规划是无界问题则原来线性规划也是无界问题

摄动法算法

摄动法与一般单纯形方法的差别主要在于主行的选择，这种方法是按照

$\frac{\overline{b}_i(\varepsilon)}{y_{rk}} = \min \lbrace \frac{\overline{b}_i(\varepsilon)}{y_{ik}} \Big | y_{ik} > 0\rbrace$

确定主行，关键是确定最小比值，由于$\overline{b}_i(\varepsilon)/y_{ik}$是$\varepsilon$的多项式，即

$\frac{\overline{b}_i(\varepsilon)}{y_{ik}} = \frac{\overline{b}_i}{y_{ik}} + \sum^n_{j=1}\frac{y_{ij}}{y_{ik}}\varepsilon^j$

$\varepsilon$是充分小的正数，该多项式值的大小主要决定于低次项，为了确定最小比值，只需要从$\varepsilon$的零次项开始，逐项比较幂的系数

• 首先比较零此项：$\overline{b}_i/y_{ik}(y_{ik} > 0)$
• 再比较一次项系数，再比较二次项系数

算法：

• 令

$\mathbf{I}_0 = \lbrace r \Big | \frac{\overline{b}_r}{y_{rk}} = \min\lbrace \frac{\overline{b}_i}{y_{ik}} \big | y_{ik} > 0 \rbrace \rbrace$

若$\mathbf{I}_0$只有一个元素$r$，则$\mathbf{x}_{B_r}$为离基变量

• 置$j = 1$
• 令

$\mathbf{I}_j = \lbrace r \Big | \frac{y_{rj}}{y_{rk}} = \min_{i\in I_{j-1}}\lbrace \frac{y_{ij}}{y_{ik}} \rbrace \rbrace$

若$\mathbf{I}_j$只有一个元素$r$，则$\mathbf{x}_{B_r}$为离基变量

• 置$j := j + 1$转上一步骤

Bland规则

1. 选下标最小的正检验数$z_j - c_j$，所对应的非基变量$\mathbf{x}_{N_r}$作为进基变量
2. 离基变量$x_l$的确定：如果同时有几个$\frac{b_i}{y_{ik}}$达到最小，就选其中下标最小的那个基变量作为离基变量。

$r = \min \lbrace r \Big | \frac{\overline{b}_r}{y_{rk}} = \min\lbrace \frac{\overline{b}_i}{y_{ik}} \big | y_{ik} > 0 \rbrace \rbrace$

• Bland规则的优点是简单易行，但缺点是只考虑最小下标，而不考虑目标函数值下降的快慢。故其效率比字典序或原来单纯形法低
• 在实际中，退化是常见的，但退化不一定产生循环。事实上，产生循环是较罕见的。

对偶理论

线性规划中普遍存在配对现象，即对每一个线性规划问题，都存在另一个与它有密切关系的线性规划问题。

• 其中之一称为原问题
• 另一个称为对偶问题

对称形式的对偶

• 原问题

$\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} \geq \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}$

• 对偶问题

$\begin{aligned} max &\qquad \mathbf{w}\mathbf{b} \\ s.t. &\qquad \mathbf{w}A \leq \mathbf{c} \\ &\qquad \mathbf{w} \geq \mathbf{0} \end{aligned}$

	原问题	对偶问题
目标函数	$\mathbf{c}$与$\mathbf{x}$的内积	$\mathbf{b}$与$\mathbf{2}$的内积
不等式约束	$A\mathbf{x} \geq \mathbf{b}$，m个不等式	$\mathbf{w}A \geq \mathbf{c}$，n个不等式
分量不等式约束	$A_i\mathbf{x} \geq b_i$	$\mathbf{wp_j} \geq c_j$
变量约束	$x_j \geq 0$	$w_j \geq 0$

根据对称对偶的定义，$n = m$

例：

$\begin{gathered} \begin{aligned} min &\qquad x_1 - x_2 \\ s.t. &\qquad x_1 + x_2 \geq 5 \\ &\qquad x_1 - 2x_2 \geq 1 \\ &\qquad x_1,x_2 \geq 0 \end{aligned} \\ \Downarrow \\ \begin{aligned} max &\qquad 5w_1 + w_2 \\ s.t. &\qquad w_1 + w_2 \geq 1 \\ &\qquad w_1 - 2w_2 \geq -1 \\ &\qquad w_1,w_2 \geq 0 \end{aligned} \end{gathered}$

非对称形式的对偶

$\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} = \mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}$

先将上式写成等价形式

$\begin{gathered} \begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A\mathbf{x} \geq \mathbf{b} \\ &\qquad -A\mathbf{x} \geq -\mathbf{b} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned} \\ \Downarrow \\ \begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\begin{bmatrix} A \\ -A \end{bmatrix}\mathbf{x} \geq \begin{bmatrix} \mathbf{b} \\ -\mathbf{b} \end{bmatrix} \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned} \end{gathered}$

根据对称对偶的定义，对偶问题为

$\begin{aligned} max &\qquad \mathbf{u}\mathbf{b} - \mathbf{v}\mathbf{b} \\ s.t. &\qquad \mathbf{u}A - \mathbf{v}A \leq \mathbf{c} \\ &\qquad \mathbf{u},\mathbf{v} \geq \mathbf{0} \end{aligned}$

令$\mathbf{w} = \mathbf{u} - \mathbf{v}$，$\mathbf{w}$没有非负限制，得到

$\begin{aligned} max &\qquad \mathbf{w}\mathbf{b} \\ s.t. &\qquad \mathbf{w}A \leq \mathbf{c} \end{aligned}$

与原问题不同的是，对偶问题没有变量的正负号限制，称为非对称对偶

对偶问题一般情形

实际中线性问题一般含有$\geq, \leq, =$等几种约束条件

$\begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A_1\mathbf{x} \geq \mathbf{b}_1 \\ &\qquad A_2\mathbf{x} = \mathbf{b}_2 \\ &\qquad A_3\mathbf{x} \leq \mathbf{b}_3 \\ &\qquad \mathbf{x} \geq \mathbf{0} \end{aligned}$

先引入松弛变量，写为等价形式

$\begin{gathered} \begin{aligned} min &\qquad \mathbf{c}\mathbf{x} \\ s.t. &\qquad A_1\mathbf{x} - \mathbf{x}_s = \mathbf{b}_1 \\ &\qquad A_2\mathbf{x} = \mathbf{b}_2 \\ &\qquad A_3\mathbf{x} + \mathbf{x}_t = \mathbf{b}_3 \\ &\qquad \mathbf{x}, \mathbf{x}_s, \mathbf{x}_t \geq \mathbf{0} \end{aligned} \\ \Downarrow \\ \begin{aligned} min &\qquad \mathbf{c}\mathbf{x} + 0 \cdot \mathbf{x}_s + 0 \cdot \mathbf{x}_t \\ s.t. &\qquad \begin{bmatrix} A_1 & -\mathbf{I}_{m_1} & \mathbf{0} \\ A_2 & \mathbf{0} & \mathbf{0} \\ A_3 & \mathbf{0} & -\mathbf{I}_{m_3} \end{bmatrix}\begin{bmatrix} \mathbf{x} \\ \mathbf{x}_s \\ \mathbf{x}_t \end{bmatrix} = \begin{bmatrix} \mathbf{b}_1 \\ \mathbf{b}_2 \\ \mathbf{b}_3 \end{bmatrix} \\ &\qquad \mathbf{x}, \mathbf{x}_s, \mathbf{x}_t \geq \mathbf{0} \end{aligned} \end{gathered}$

根据对称对偶的定义，对偶问题为

$\begin{aligned} max &\qquad \mathbf{w}_1\mathbf{b}_1 + \mathbf{w}_2\mathbf{b}_2 + \mathbf{w}_3\mathbf{b}_3 \\ s.t. &\qquad \mathbf{w}_1A_1 + \mathbf{w}_2A_2 + \mathbf{w}_3A_3 \leq \mathbf{c} \\ &\qquad \mathbf{w}_1 \geq 0 & \color{grey}A_1\mathbf{x} \geq \mathbf{b}_1 \\ &\qquad \mathbf{w}_3 \leq 0 & \color{grey}A_3\mathbf{x} \leq \mathbf{b}_3 \\ &\qquad \mathbf{w}_2 \text{无限制} & \color{grey}A_2\mathbf{x} = \mathbf{b}_2 \end{aligned}$

• 原问题中约束$A_1\mathbf{x} \geq \mathbf{b}_1$对应的对偶变量$\mathbf{w}_1$有非负限制
• 原问题中约束$A_2\mathbf{x} = \mathbf{b}_2$对应的对偶变量$\mathbf{w}_1$没有限制
• 原问题中约束$A_3\mathbf{x} \leq \mathbf{b}_3$对应的对偶变量$\mathbf{w}_1$有非正限制

上述三种形式的对偶中，原问题和对偶问题是相对的，相互对偶的两个问题中，任何一个问题均可作为原问题，另一个作为对偶问题

对偶问题总结

	原问题	对偶问题
问题	极大化：$\max$	极小化：$\min$
问题	极小化：$\min$	极大化：$\max$
系数·右端向量	系数：$\mathbf{c}$，右端向量：$\mathbf{b}$	系数：$\mathbf{b}$，右端向量：$\mathbf{c}$
变量约束	$\min A\mathbf{x} \geq \mathbf{b}$，$\max A\mathbf{x} \leq \mathbf{b}$	$\mathbf{w} \geq 0$
变量约束	$\min A\mathbf{x} \leq \mathbf{b}$，$\max A\mathbf{x} \geq \mathbf{b}$	$\mathbf{w} \leq 0$
变量约束	$=$	无限制
不等式约束	$\min x \geq 0$，$\max x \leq 0$	$\mathbf{w}A \leq \mathbf{0}$不等式
不等式约束	$\min x \leq 0$，$\max x \geq 0$	$\mathbf{w}A \geq \mathbf{0}$不等式
不等式约束	无限制变量	$=$等式

对偶定理

定理：设$\mathbf{x}^{(0)}$和$\mathbf{w}^{(0)}$分别是原问题和对偶问题的可行解，则$\mathbf{c}\mathbf{x}^{(0)} \geq \mathbf{w}^{(0)}\mathbf{b}$

$\begin{aligned} \sum^n_{j=1}c_jx_j &\leq \sum^m_{i= 1}b_iy_i \\ \text{主问题函数值} &\leq \text{对偶问题函数值} \end{aligned}$

也就是原问题的目标函数值大于对偶函数值，就原问题和对偶问题的可行解而言，对于对偶问题中的两个问题，每一个问题的任何一个可行解处的目标函数值，都给出另一个问题的目标函数值的界

• 极小化问题给出极大化的目标函数值的上界
• 极大化问题给出极小化的目标函数值的下界

推论：若$\mathbf{x}^{(0)}$和$\mathbf{w}^{(0)}$分别是原问题和对偶问题的可行解，且$\mathbf{c}\mathbf{x}^{(0)} = \mathbf{w}^{(0)}\mathbf{b}$，则$\mathbf{x}^{(0)}$和$\mathbf{w}^{(0)}$分别是原问题和对偶问题的最优解
推论：原问题和对偶问题有最优解的充要条件是它们同时具有可行解
推论：若线性规划（对称对偶）存在一个对应基$B$的最优基本可行解，则单纯形乘子$\mathbf{w} = \mathbf{c}_BB^{-1}$是对偶问题的一个最优解
推论：

$\begin{aligned} \text{原问题的目标函数在可行域上无下界，则对偶问题无可行解} \\ \text{对偶问题的目标函数在可行域上无上界，则原问题无可行解} \end{aligned}$

定理；设原问题和对偶问题存在最优解，则另一个问题也存在最优解，且两个问题的目标函数的最优值相等

互补松弛性质

定理：设$\mathbf{x}^{(0)}$和$\mathbf{w}^{(0)}$分别是原问题和对偶问题的可行解（对称对偶），那么$\mathbf{x}^{(0)}$和$\mathbf{w}^{(0)}$都是最优解的充要条件是，对所有$i$和$j$，下列关系成立

$\begin{aligned} \mathbf{x}^{(0)}_j > 0 &\Rightarrow \mathbf{w}^{(0)}\mathbf{p}_j = c_j \\ \mathbf{w}^{(0)}\mathbf{p}_j < c_j &\Rightarrow \mathbf{x}^{(0)}_j = 0 \\ \\ w^{(0)}_i > 0 &\Rightarrow A_i\mathbf{x}^{(0)} = b_j \\ A_i\mathbf{x}^{(0)} > b_j &\Rightarrow w^{(0)}_i = 0 \end{aligned}$

定理：设$\mathbf{x}^{(0)}$和$\mathbf{w}^{(0)}$分别是原问题和对偶问题的可行解（非对称对偶），那么$\mathbf{x}^{(0)}$和$\mathbf{w}^{(0)}$都是最优解的充要条件是，对所有$j$，下列关系成立

$\begin{aligned} \mathbf{x}^{(0)}_j > 0 &\Rightarrow \mathbf{w}^{(0)}\mathbf{p}_j = c_j \\ \mathbf{w}^{(0)}\mathbf{p}_j < c_j &\Rightarrow \mathbf{x}^{(0)}_j = 0 \end{aligned}$

强互补松弛定理

若对称对偶问题存在最优解，则必存在满足强互补松弛条件的最优解，即存在最优解$(\overline{\mathbf{x}}, \overline{\mathbf{x}}_s)$和$(\overline{\mathbf{w}}, \overline{\mathbf{w}}_s)$，使得由对应分量构成的所有二元数值$\lbrace (\overline{x}_j, \overline{w}_{m + j}), \overline{x}_{n+i}, \overline{w}_{i} \ |\ j =1,2,\cdots,n; i =1, 2, \cdots, m\rbrace$中，每个二元数组均包含一个正数，其中$\overline{w}_{m+j}$和$\overline{x}_{n+i}$分别是松弛变量$\overline{\mathbf{w}}_s$和$\overline{\mathbf{x}}_s$的第$j$个和第$i$个分量

参考文献

• 最优化 - 理论与算法丨陈宝林丨第二版丨7-302-11376-9