01线性规划与单纯型法

Lingfeng 2025-02-21

01线性规划与单纯型法

1. 多面体模型和标准模型

Definition (多面体模型)

设决策变量为 $X$ ，求解以下优化问题 $\begin{align*}\min C^{T}X \\ s.t. AX\geq b\end{align*}$ 其中 $X=\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$ ， $A=\left(\begin{matrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{matrix}\right)$ ， $C=\begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix}$ ， $b=\begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}$ 。由不等式描述的约束条件将线性规划的可行域约束为一个多面体区域。

Definition (线性规划标准模型)

线性规划标准形式为 $\begin{align*} \max C^{T}X\\s.t. AX=b \\X\geq 0 \end{align*}$

Theorem (松弛变量转换法)

$\leq$ 不等式 $x_{1}\leq b \implies x_{1}+x_{2}=b$
$\geq$ 不等式 $x_{1}\geq b\implies x_{1}-x_{2}=b$
取值无约束 $x=x^{+}-x^{-},x^{+}\geq 0,x^{-}\geq 0$
$x\leq 0$ $x'=-x$

2. 线性规划基本定理

Definition (基)

设 $B$ 是秩为 $m$ 的约束矩阵 $A$ 中的一个 $m$ 阶满秩子方阵，称 $B$ 的一个基。 $B$ 中 $m$ 个线性无关的列向量称为基向量。变量 $x$ 中与之对应的 $m$ 个分量称为基变量，其余的分量称为非基变量。

Definition (可行基)

令所有非基变量取值为零，得到解称为基本解。当基本解非负时，称为基本可行解，此时对应的基称为可行基。

Theorem (可行域性质)

线性规划若存在可行集，则可行域是凸集（多面体）。

Lemma (可行解是基本可行解的充要条件)

可行解是基本可行解的充要条件是它的正分量所对应的列向量线性无关。

Theorem (基本可行解与顶点)

线性规划问题的基本可行解对应着线性规划问题可行域的顶点。

Theorem (基本可行解与最优解)

若线性规划问题有最优解，则一定存在一个基本可行解是最优解。

3. 单纯型法

3.1 定义

Definition (单纯型法)

给出初始基本可行解 $X=(0\dots,0,b_{1},\dots,b_{m})$
计算非基变量 $x_{j}$ 的检验数 $\sigma_{j}$
若存在检验数大于0，则选检验数最大的基，用最小比值法确定传出的基变量 $\theta=\min \left\{ \frac{b_{i}}{a_{ik}}\Big| a_{ik}>0 \right\}=\frac{b_{l}}{a_{lk}}$
所有非基变量检验数都为负，则已经达到最优解。若存在检验数为正，但是对应列系数都为负，则无有限最优解。

考虑 $z=\sum_{j = 1}^{n}c_{j}x_{j}+\sum_{i = 1}^{m} c_{n+i}x_{n+i}$ 其中不妨设 $x_{n+i}$ ， $i=1,\dots,m$ 为基变量，其余为非基变量。此时注意到所有的基变量可由非基变量线性表出，有 $x_{n+i}=b_{i}-\sum_{j = 1}^{n} a_{ij}x_{j},\quad i=1,\dots,m$ 因此 $\begin{align*} z & =\sum_{j = 1}^{n}c_{j}x_{j}+\sum_{i = 1}^{m} c_{n+i}\left( b_{i}-\sum_{j = 1}^{n} a_{ij}x_{j} \right) \\ & =\sum_{i = 1}^{m} c_{n+i}b_{i}+\sum_{j = 1}^{n} \left( c_{i}-\sum_{i = 1}^{m}c_{n+i}a_{ij} \right)x_{i} \end{align*}$ 令 $\sigma_{j}=c_{j}-\sum_{i = 1}^{m}c_{n+i}a_{ij}$ 为检验数，此时 $z=C+\sum_{j = 1}^{n} \sigma_{j}x_{j}$ 其中 $\sigma_{j}$ 表示 $x_{j}$ 增大时对目标函数值的单位贡献。

Theorem (最优性判别定理)

若 $X=(0,\dots,0,b_{1},\dots,b_{m})$ 是对应 $B$ 的基本可行解， $\sigma_{j}$ 是用非基变量表示目标函数表达式中 $x_{j}$ 的检验数，若均有 $\sigma_{j}\leq 0$ ，则当前基本可行解为最优解。

3.2 人工变量法

Definition (人工变量)

添加人工变量，通过在迭代过程中把人工变量换出可行基获得原问题的可行基。

Definition (人工变量换出可行基方法)

大M法。把目标函数换成 $\max\sum_{j = 1}^{n} c_{j}x_{j}+\sum_{i = 1}^{m}(-M) x_{n+i}$
两阶段法。先把目标函数设为 $\max\sum_{i = 1}^{m}(-1)x_{n+i}$ ，迭代到该目标函数等于零时再用原目标函数。