04-线性规划

问题描述&相关定义

该部分所讨论的优化问题形如：

$$\begin{array}{rl}minimize& {\mathbf{c}}^{\top }\mathbf{x}\\ subject& \mathbf{A}\mathbf{x}=\mathbf{b},\mathbf{x}⩾0,b⩾0\end{array}$$

其中 $\mathbf{A}$ 是 $m\times n$ 实数矩阵，$m<n$ ，$rank\mathbf{A}=m$. 一般线性规划化标准型规则： (1) $\max f(x)$ 与 $\min -f(x)$ 有相同的最优解, 互为相反的最优值 (2) 对不等式约束引入松弛变量, 变成等式约束 (3) 有决策变量属于实数时, 即 $x_i\in R^n$, 对分量进行非负拆分 (4) 如果变量 $b_i<0$, 则对等式两边乘以-1

我们从 $\mathbf{A}$ 中选择 $m$ 个线性无关的列向量组成方阵 $\mathbf{B}$ , $\mathbf{A}=[\mathbf{B},\mathbf{D}]$ ，矩阵 $\mathbf{B}$ 是非奇异的 $\iff \mathbf{x}={\left[{\mathbf{x}}_B^{\top },0^{\top }\right]}^{\top }$ 是方程 $\mathbf{Ax}=\mathbf{b}$ 在基 $\mathbf{B}$ 下的基本解（也就是最下面的元素一定是0） 其中, ${\mathbf{x}}_{\mathbf{B}}={\mathbf{B}}^{-1}\mathbf{b}$ 。如果 $x_B$ 中有变量为零，那么称为退化的基本解。满足约束条件 $\mathbf{A}\mathbf{x}=\mathbf{b},\mathbf{x}⩾0$ 的向量 $\mathbf{x}$ 称为可行解。如果某个可行解也是基本解，那么称之为基本可行解。如果可行解能使得 $minimize{\mathbf{c}}^{\top }\mathbf{x}$ 成立，那么称 $\mathbf{x}$为最优可行解 。如果最有可行解也是基本解，那么称为最优基本可行解。线性规划的极值点一定是多胞形的边界点（顶点），且该点一定为基本可行解

解的相关定义实例

各种解的相关定义|课程PPT

各种解的求法

各种解的求法实例|课程PPT

单纯形法

• 思想：从找到的最初基本可行解通过线性变换转移到另一个基本可行解，在方向选取合适情况下，最后可以找到最优基本可行解。

线性规划的标准型

$$\begin{array}{rl}& minimize{\mathbf{c}}^{\top }\mathbf{x}\\ & subjectto\mathbf{A}\mathbf{x}=\mathbf{b}\end{array}$$

令 $A$ 的前 $m$ 列是基向量, 这 $m$ 列组成了 $m\times m$ 可逆矩阵 $B$ 。 $A$ 的非基列向量组成了 $m\times (n-m)$ 矩阵 $D$ 即 $A=[B,D]$ 相应地, 有 $x=\left[x_B,x_D\right],c^{\top }=\left[{\mathbf{c}}_B^{\top },c_D^{\top }\right]$ 线性规划的标准型 可等价地表示为:

$$\begin{array}{rl}& minimize{\mathbf{c}}_B^{\top }{\mathbf{x}}_B+{\mathbf{c}}_D^{\top }{\mathbf{x}}_D\\ & subjectto[\mathbf{B},\mathbf{D}]\left[\begin{array}{l}{\mathbf{x}}_B\\ {\mathbf{x}}_D\end{array}\right]=\mathbf{B}{\mathbf{x}}_B+\mathbf{D}{\mathbf{x}}_D=\mathbf{b}\\ & {\mathbf{x}}_B⩾0,{\mathbf{x}}_D⩾0\end{array}$$

1. 如果 $x_D=0$, 则 $x=\left[x_B,x_D\right]$ 是关于基 $B$ 的基本可行解, 具体地为: $\mathbf{x}=\left[\begin{array}{c}{\mathbf{x}}_B\\ {\mathbf{x}}_D\end{array}\right]=\left[\begin{array}{c}{\mathbf{B}}^{-1}\mathbf{b}\\ 0\end{array}\right]$ 此时的目标函数值为 $:z_0={\mathbf{c}}_B^{\top }{\mathbf{B}}^{-1}\mathbf{b}$
2. 如果 $x_D\ne 0$, 则 $x=\left[x_B,x_D\right]$ 不是关于基 $B$ 的基本可行解为, 此时有

$${\mathbf{x}}_B={\mathbf{B}}^{-1}\mathbf{b}-{\mathbf{B}}^{-1}\mathbf{D}{\mathbf{x}}_D$$

此时的目标函数值为:

$$\begin{array}{rl}z& ={\mathbf{c}}_B^{\top }{\mathbf{x}}_B+{\mathbf{c}}_D^{\top }{\mathbf{x}}_D\\ & ={\mathbf{c}}_B^{\top }\left({\mathbf{B}}^{-1}\mathbf{b}-{\mathbf{B}}^{-1}\mathbf{D}{\mathbf{x}}_D\right)+{\mathbf{c}}_D^{\top }{\mathbf{x}}_D\\ & ={\mathbf{c}}_B^{\top }{\mathbf{B}}^{-1}\mathbf{b}+\left({\mathbf{c}}_D^{\top }-{\mathbf{c}}_B^{\top }{\mathbf{B}}^{-1}\mathbf{D}\right){\mathbf{x}}_D\\ & =z_0+{\mathbf{r}}_D^{\top }{\mathbf{x}}_D\\ & \stackrel{\text{ 定义 }}{⟶}{\mathbf{r}}_D^{\top }={\mathbf{c}}_D^{\top }-{\mathbf{c}}_B^{\top }{\mathbf{B}}^{-1}\mathbf{D}\end{array}$$

• 分类讨论：

  • 如果 $r_D\ge 0$ 则关于基 $B$ 的基本可行解就是最优解, 即 $\mathbf{x}=\left[\begin{array}{c}{\mathbf{B}}^{-1}1\\ 0\end{array}\right]$ 因此, 可以通过 $r_D\ge 0$ 是否成立, 判定一个基本可行解是否是最优解
  • 如果 $r_D$ 中存在负分量, 则可通过将 $x_D$ 中相应的值从零变为正数, 使目标函数值变小。$z={\mathbf{c}}_B^{\top }{\mathbf{x}}_B+{\mathbf{c}}_D^{\top }{\mathbf{x}}_D=z_0+{\mathbf{r}}_D^{\top }{\mathbf{x}}_D$即通过转轴运算更新一次矩阵

• 转轴元素选取 从 ${\mathbf{r}}_D$ 中对应的负元素所在的第 $l$ 列元素 ${\mathbf{a}}_{k,l}$ 中选取满足如下条件做转轴元素$\frac{b_k}{a_{kl}}={\min }_{i=1,\cdots ,m}\left\{\frac{b_i}{a_{il}}\mid a_{il}>0\right\}$将第 $l$ 列上元素通过矩阵变换变成0，转轴元素则单位化为1。

单纯形法具体矩阵表示形式

$$\begin{array}{rl}& \left[\begin{array}{cc}\mathbf{A}& \mathbf{b}\\ {\mathbf{c}}^{\top }& 0\end{array}\right]=\left[\begin{array}{ccc}\mathbf{B}& \mathbf{D}& \mathbf{b}\\ {\mathbf{c}}_B^{\top }& {\mathbf{c}}_D^{\top }& 0\end{array}\right]\end{array}$$

分块矩阵行初等变换（倍乘）

$$\begin{array}{rl}& \left[\begin{array}{ccc}{\mathbf{I}}_m& {\mathbf{B}}^{-1}\mathbf{D}& {\mathbf{B}}^{-1}\mathbf{b}\\ {\mathbf{c}}_B^{\top }& {\mathbf{c}}_D^{\top }& 0\end{array}\right]\end{array}$$

分块矩阵行初等变换（倍加）

$$\begin{array}{rl}& \left[\begin{array}{ccc}{\mathbf{I}}_m& {\mathbf{B}}^{-1}\mathbf{D}& {\mathbf{B}}^{-1}\mathbf{b}\\ 0^{\top }& {\mathbf{c}}_D^{\top }-{\mathbf{c}}_B^{\top }{\mathbf{B}}^{-1}\mathbf{D}& -{\mathbf{c}}_B^{\top }{\mathbf{B}}^{-1}\mathbf{b}\end{array}\right]\end{array}$$

（1）若上述矩阵中的判别式全部非负, 则此时的基本解就是最优解, 最优值的相反数在矩阵的右下角 （2） 若上述矩阵中的判别式有负元素, 则取最小的负元素所在的列进基, 做1次转轴运算

单纯形法计算实例

单纯形法计算实例|课程PPT

单纯形法改进-两阶段法

• 来源：有些约束条件不是特别容易求初始基本可行解，需要添加人工松弛变量来构造初始可行解。

两阶段法计算实例|课程PPT

大M方法

(P0)$\begin{array}{rl}minimize& {\mathbf{c}}^{\top }\mathbf{x}\\ subjectto& \mathbf{A}\mathbf{x}=\mathbf{b}\\ & \mathbf{x}⩾0\end{array}$ 若无明显的初始基本可行解，则构造新的LP问题： (P1) $\begin{array}{r}\min c^{T}x+M{e}^{Ty}\\ \text{ s.t. }Ax+y=b\end{array}$

$$x\ge 0,y\ge 0$$

其中 $M\ge 0$ 称为 “大”常数, $e$ 为全1行向量 P0无法直接单纯形法求解；P1可以单纯形法求解（尽管含有参数 $M$ ) 定理：P1有若无解, P0更若无解;P1若有解 $\left[x\ast ,y^{\ast }\right]$, (1) 若 $y^{\ast }=0\iff x\ast$ 是 $\mathrm{P}0$ 的最优解; (2)若 $y^{\ast }\ne 0\iff$ P0无解;

大M方法计算实例|课程PPT

---

参考资料