一文助你搞懂单纯形法

水深无声 2021-09-24 23:56 699阅读 0赞

# 1. 题目 #

考虑如下两个变量的线性规划：  
 max ⁡ z = 5 x 1 + 4 x 2 s.t. \{ 6 x 1 + 4 x 2 ≤ 24 x 1 + 2 x 2 ≤ 6 − x 1 + x 2 ≤ 1 x 2 ≤ 2 x 1 , x 2 ≥ 0 \\max z = 5x\_1 + 4x\_2 \\\\ \\textbf\{s.t.\} \\begin\{cases\} 6x\_1 + 4x\_2 \\leq 24 \\\\ x\_1 + 2x\_2 \\leq 6 \\\\ -x\_1 + x\_2 \\leq 1 \\\\ x\_2 \\leq 2 \\\\ x\_1, x\_2 \\geq 0 \\\\ \\end\{cases\} maxz=5x1\+4x2s.t.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧6x1\+4x2≤24x1\+2x2≤6−x1\+x2≤1x2≤2x1,x2≥0

# 2. 标准型 #

将上面的线性规划化成标准型：  
 max ⁡ z = 5 x 1 + 4 x 2 s.t. \{ 6 x 1 + 4 x 2 + s 1 = 24 x 1 + 2 x 2 + s 2 = 6 − x 1 + x 2 + s 3 = 1 x 2 + s 4 = 2 x 1 , x 2 , s 1 , s 2 , s 3 , s 4 ≥ 0 \\max z = 5x\_1 + 4x\_2 \\\\ \\textbf\{s.t.\} \\begin\{cases\} 6x\_1 + 4x\_2 + s\_1 = 24 \\\\ x\_1 + 2x\_2 + s\_2 = 6 \\\\ -x\_1 + x\_2 + s\_3 = 1 \\\\ x\_2 + s\_4 = 2 \\\\ x\_1, x\_2, s\_1, s\_2, s\_3, s\_4 \\geq 0 \\\\ \\end\{cases\} maxz=5x1\+4x2s.t.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧6x1\+4x2\+s1=24x1\+2x2\+s2=6−x1\+x2\+s3=1x2\+s4=2x1,x2,s1,s2,s3,s4≥0

目标方程：  
 z − 5 x 1 − 4 x 2 = 0 z - 5x\_1 - 4x\_2 = 0 z−5x1−4x2=0

# 3. 单纯形法 #

## 3.1 初始单纯形表 ##

该单纯形表提供了相应的初始迭代解。该单纯形迭代从原点  ( x 1 , x 2 ) = ( 0 , 0 ) (x\_1, x\_2) = (0, 0) (x1,x2)=(0,0) 开始。 因此定义  ( x 1 , x 2 ) (x\_1, x\_2) (x1,x2) 为非基变量， ( s 1 , s 2 , s 3 , s 4 ) (s\_1, s\_2, s\_3, s\_4) (s1,s2,s3,s4) 为基变量。当前解为  z = 0 z = 0 z=0。

## 3.2 单纯形法 ##

以上的单纯性表不是最优的，目标函数  z = 5 x 1 + 4 x 2 z = 5x\_1+4x\_2 z=5x1\+4x2 表明，可以通过增加  x 1 x\_1 x1 或  x 2 x\_2 x2 来改进这个解。通常，选择具有最大正值系数的变量  x 1 x\_1 x1 作为进基变量。这等价于，因为单纯性表将目标函数表示为  z − 5 x 1 − 4 x 2 = 0 z-5x\_1-4x\_2=0 z−5x1−4x2=0，则进基变量将对应于目标方程中那些最大负值系数的变量。这一规则称为**单纯形最优性条件**。在单纯形法中， x 1 x\_1 x1 称为进基变量，因为它进入了基本解。

若  x 1 x\_1 x1 是进基变量，当前的某个基变量必须离开，即变成取值为零的非基变量（非基变量的个数必须总是 n - m 个）。确定**离基变量**的技巧是，计算方程的右端项（解列）于相应的在进基变量  x 1 x\_1 x1 列下的约束系数的非负比，如下表所示

<table> 
 <thead> 
 <tr> 
 <th>基</th> 
 <th>进基</th> 
 <th>解</th> 
 <th>比（截距）</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> s 1 s_1 s1</td> 
 <td>6</td> 
 <td>24</td> 
 <td> 24 6 = 4 ← \frac{24}{6}=4 \leftarrow 624=4← 最小值</td> 
 </tr> 
 <tr> 
 <td> s 2 s_2 s2</td> 
 <td>1</td> 
 <td>6</td> 
 <td> 6 1 = 6 \frac{6}{1}=6 16=6</td> 
 </tr> 
 <tr> 
 <td> s 3 s_3 s3</td> 
 <td>-1</td> 
 <td>1</td> 
 <td>分母为负不考虑</td> 
 </tr> 
 <tr> 
 <td> s 4 s_4 s4</td> 
 <td>0</td> 
 <td>2</td> 
 <td>分母为零不考虑</td> 
 </tr> 
 </tbody> 
</table>

对应于比值计算的规则称为**单纯形可行性条件**。

新解由进基变量  x 1 x\_1 x1 和 离基变量  s 1 s\_1 s1 的单纯形表中的 “交换” 来确定。  
交换过程基于**高斯 – 若尔当行运算**。它认定进基变量所在的列为**枢轴列**，离基变量所在的行称为**枢轴行**，处于枢轴列和枢轴行交叉位置的元素称为**枢轴元素**。

为产生新的基本解，高斯 – 若尔当行运算需要产生两种类型的新的基本解。  
（1）枢轴行。  
（2）在基列中，以进基变量替换离基变量。  
（3）新的枢轴行 = 当前枢轴行  ÷ \\div ÷ 枢轴元素。  
（4）其他所有行，包括  z z z 行。  
 新 的 行 = 当 前 行 − 当 前 行 枢 轴 列 的 系 数 × 新 的 枢 轴 行 新的行 = 当前行 - 当前行枢轴列的系数 \\times 新的枢轴行 新的行=当前行−当前行枢轴列的系数×新的枢轴行

（1）在基列中，以  x 1 x\_1 x1 替换  s 1 s\_1 s1：  
 新 的 x 1 行 = 当 前 s 1 行 ÷ 6 = 1 6 \[ 0 6 4 1 0 0 0 24 \] T = \[ 0 1 2 / 3 1 / 6 0 0 0 4 \] T \\begin\{aligned\} 新的 x\_1 行 & = 当前 s\_1 行 \\div 6 \\\\ & = \\frac\{1\}\{6\} \\begin\{bmatrix\} 0 \\\\ 6 \\\\ 4 \\\\ 1 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 24 \\end\{bmatrix\}^T = \\begin\{bmatrix\} 0 \\\\ 1 \\\\ 2 / 3 \\\\ 1 / 6 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 4 \\end\{bmatrix\}^T \\end\{aligned\} 新的x1行=当前s1行÷6=61⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡064100024⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡012/31/60004⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T  
（2）新的  z z z 行 = 当前  z z z 行 - (-5)  × \\times × 新的  x 1 x\_1 x1 行  
 = \[ 1 − 5 − 4 0 0 0 0 0 \] T − ( − 5 ) \[ 0 1 2 / 3 1 / 6 0 0 0 4 \] T = \[ 1 0 − 2 / 3 5 / 6 0 0 0 20 \] T \\begin\{aligned\} & = \\begin\{bmatrix\} 1 \\\\ -5 \\\\ -4 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ \\end\{bmatrix\}^T - (-5) \\begin\{bmatrix\} 0 \\\\ 1 \\\\ 2 / 3 \\\\ 1 / 6 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 4 \\end\{bmatrix\}^T = \\begin\{bmatrix\} 1 \\\\ 0 \\\\ -2 / 3 \\\\ 5 / 6 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 20 \\end\{bmatrix\}^T \\end\{aligned\} =⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡1−5−400000⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T−(−5)⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡012/31/60004⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡10−2/35/600020⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T  
（3）新的  s 2 s\_2 s2 行 = 当前  s 2 s\_2 s2 行 - (1)  × \\times × 新的  x 1 x\_1 x1 行  
 = \[ 0 1 2 0 1 0 0 6 \] T − \[ 0 1 2 / 3 1 / 6 0 0 0 4 \] T = \[ 0 0 4 / 3 − 1 / 6 1 0 0 2 \] T \\begin\{aligned\} & = \\begin\{bmatrix\} 0 \\\\ 1 \\\\ 2 \\\\ 0 \\\\ 1 \\\\ 0 \\\\ 0 \\\\ 6 \\\\ \\end\{bmatrix\}^T - \\begin\{bmatrix\} 0 \\\\ 1 \\\\ 2 / 3 \\\\ 1 / 6 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 4 \\\\ \\end\{bmatrix\}^T = \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 4 / 3 \\\\ -1 / 6 \\\\ 1 \\\\ 0 \\\\ 0 \\\\ 2 \\\\ \\end\{bmatrix\}^T \\end\{aligned\} =⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡01201006⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T−⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡012/31/60004⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡004/3−1/61002⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T  
（4）新的  s 3 s\_3 s3 行 = 当前  s 3 s\_3 s3 行 - (-1)  × \\times × 新的  x 1 x\_1 x1 行  
 = \[ 0 − 1 1 0 0 1 0 1 \] T − ( − 1 ) \[ 0 1 2 / 3 1 / 6 0 0 0 4 \] T = \[ 0 0 5 / 3 1 / 6 0 1 0 5 \] T \\begin\{aligned\} & = \\begin\{bmatrix\} 0 \\\\ -1 \\\\ 1 \\\\ 0 \\\\ 0 \\\\ 1 \\\\ 0 \\\\ 1 \\\\ \\end\{bmatrix\}^T - (-1) \\begin\{bmatrix\} 0 \\\\ 1 \\\\ 2 / 3 \\\\ 1 / 6 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 4 \\\\ \\end\{bmatrix\}^T = \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 5 / 3 \\\\ 1 / 6 \\\\ 0 \\\\ 1 \\\\ 0 \\\\ 5 \\\\ \\end\{bmatrix\}^T \\end\{aligned\} =⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡0−1100101⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T−(−1)⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡012/31/60004⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡005/31/60105⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T

（5）新的  s 4 s\_4 s4 行 = 当前  s 3 s\_3 s3 行 - 0 × \\times × 新的  x 1 x\_1 x1 行  
 = \[ 0 0 1 0 0 0 1 2 \] T \\begin\{aligned\} & = \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 1 \\\\ 2 \\\\ \\end\{bmatrix\}^T \\end\{aligned\} =⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡00100012⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤T

新的基本解释  ( x 1 , s 2 , s 3 , s 4 ) (x\_1, s\_2, s\_3, s\_4) (x1,s2,s3,s4)，因此新的单纯形表变为：

可观察到，新表与初始表有相同的性质。  
在最后的表中，最优性条件表明，  x 2 x\_2 x2（带有最大负值的  z z z 行系数）是进基变量。又最优性条件得到下列信息：

<table> 
 <thead> 
 <tr> 
 <th>基</th> 
 <th>进基</th> 
 <th>解</th> 
 <th>比（截距）</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> x 1 x_1 x1</td> 
 <td> 2 3 \frac{2}{3} 32</td> 
 <td>4</td> 
 <td> 4 ÷ 2 3 = 6 4 \div \frac{2}{3}=6 4÷32=6</td> 
 </tr> 
 <tr> 
 <td> s 2 s_2 s2</td> 
 <td> 4 3 \frac{4}{3} 34</td> 
 <td>2</td> 
 <td> 2 ÷ 4 3 = 3 2 ← 2 \div \frac{4}{3}=\frac{3}{2} \leftarrow 2÷34=23← 最小值</td> 
 </tr> 
 <tr> 
 <td> s 3 s_3 s3</td> 
 <td> 5 3 \frac{5}{3} 35</td> 
 <td>5</td> 
 <td> 5 ÷ 5 3 = 3 5 \div \frac{5}{3}=3 5÷35=3</td> 
 </tr> 
 <tr> 
 <td> s 4 s_4 s4</td> 
 <td>1</td> 
 <td>2</td> 
 <td> 2 ÷ 1 = 2 2 \div 1=2 2÷1=2</td> 
 </tr> 
 </tbody> 
</table>

因此，进基变量为  x 2 x\_2 x2，出基变量为  s 2 s\_2 s2。  
在基列中，用进基变量  x 2 x\_2 x2 代替  s 2 s\_2 s2，应用高斯 – 若尔当行运算：  
（1）新的枢轴  x 2 x\_2 x2 = 当前  s 2 s\_2 s2 行  ÷ 4 3 \\div \\frac\{4\}\{3\} ÷34  
（2）新的  z z z 行 = 当前  z z z 行 - ( − 2 3 -\\frac\{2\}\{3\} −32)  × \\times × 新的  x 2 x\_2 x2 行  
（3）新的  x 1 x\_1 x1 行 = 当前  x 1 x\_1 x1 行 - ( 2 3 \\frac\{2\}\{3\} 32)  × \\times × 新的  x 2 x\_2 x2 行  
（4）新的  s 3 s\_3 s3 行 = 当前  s 3 s\_3 s3 行 - ( 5 3 \\frac\{5\}\{3\} 35) 新的  x 2 x\_2 x2 行  
（5）新的  s 4 s\_4 s4 行 = 当前  s 4 s\_4 s4 行 - 新的  x 2 x\_2 x2 行  
计算产生下表：

基于最优性条件， z z z 行中对应于非基变量  s 1 s\_1 s1 和  s 2 s\_2 s2 的系数没有一个是负的。因此，最后一张表是最优的。

<table> 
 <thead> 
 <tr> 
 <th>决策变量</th> 
 <th>最优值</th> 
 <th>建议</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> x 1 x_1 x1</td> 
 <td>3</td> 
 <td>日生产 3 吨外墙涂料</td> 
 </tr> 
 <tr> 
 <td> x 2 x_2 x2</td> 
 <td> 3 2 \frac{3}{2} 23</td> 
 <td>日生产 1.5 吨内墙涂料</td> 
 </tr> 
 <tr> 
 <td> z z z</td> 
 <td>21</td> 
 <td>日利润是 21000 美元</td> 
 </tr> 
 </tbody> 
</table>

这一最优解还给出了资源的状况。若相应的松弛变量为零，即这一活动（变量）使用了全部资源，则资源被认为是**匮乏的**；若松弛变量取正值，则资源是**充裕的**。

<table> 
 <thead> 
 <tr> 
 <th>项目</th> 
 <th>松弛变量的值</th> 
 <th>状况</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>原料 M1</td> 
 <td> s 1 = 0 s_1 = 0 s1=0</td> 
 <td>匮乏</td> 
 </tr> 
 <tr> 
 <td>原料 M2</td> 
 <td> s 2 = 0 s_2 = 0 s2=0</td> 
 <td>匮乏</td> 
 </tr> 
 <tr> 
 <td>市场限制</td> 
 <td> s 3 = 5 2 s_3 = \frac{5}{2} s3=25</td> 
 <td>充裕</td> 
 </tr> 
 <tr> 
 <td>需求限制</td> 
 <td> s 4 = 1 2 s_4 = \frac{1}{2} s4=21</td> 
 <td>充裕</td> 
 </tr> 
 </tbody> 
</table>