单纯形法简介

大家好，欢迎来到IT知识分享网。

原理

考虑目标函数，

$$max z=3x_1+4x_2$$

增加

x1
$x_1$和

x2
$x_2$的值都将改进

z
$z$的值，单纯形法的设计要求每次都选择使



z

$z$值有最大改善的那个变量。意味着在上述目标函数中，首先选择增加

x2
$x_2$的值。

基础

通过对问题约束施加以下两项要求来方便单纯形法的计算：
1. 所有的约束都是等式，并且具有非负右端项
2. 所有变量都是非负的

松弛化

将不等式转化为带有非负右端项的等式约束

• 为了把$\le$不等式约束转换为等式约束，在不等式的左端，增加非负的松弛变量。
• 把$\ge$不等式约束转换为等式约束，在不等式的左端，减去非负的剩余变量。

基本术语

在$m*n$阶方程组定义的解空间中，基本解对应解空间的角点，设定$n-m$个变量等于零，求解剩下的$m$个变量的$m$阶方程组。因此角点的最大数目为$C_n^m$。其中$n-m$个零变量称为非基变量，剩余$m$个变量称为基变量。

实例

$$\max z=5x_1+4x_2\\s.t.\begin{cases}&6x_1+4x_2\le 24 \\&x_1+2x_2\le 6\\&-x_1+x_1\le 1\\&x_2\le 2\\&x_1,x_2\ge 0\end{cases}$$

松弛化后，

$$\max z=5x_1+4x_2+0s_1+0s_2+0s_3+0s_4\\s.t.\begin{cases}&6x_1+4x_2+s_1=24 \\&x_1+2x_2+s_2=6\\&-x_1+x_1+s_3=1\\&x_2+s_4=2\\&x_1,x_2,s_1,s_2,s_3,s_4\ge 0\end{cases}$$

初始单纯形表表示为：

目标函数$z=5x_1+4x_2$表明，$x_1$作为进基变量，可以最大程度增$z$，$x_1$成为进基变量后，当前的某个基变量就必须离开，变成取值为零的非基变量。确定离基变量的技巧，计算方程的右端项与相应的在进基变量$x_1$下方约束系数的非负比(实际上计算的比值是这些约束关于进基变量$x_1$轴的截距)，

$$\begin{array}{cccc}基 & 进基变量 & 解 & 比值 \\\hlines_1 & 6 & 24 & {24\over 6}=4 \\s_2 & 1 & 6 & {6\over 1}=6 \\s_3 & -1 & 1 & {1\over -1}=-1(分母为负不考虑)\\s_4 & 0 & 2 & {2\over 0}=\infty(分母为0不考虑)\end{array}$$

进基变量和离基变量的交换过程由高斯-若尔当行计算完成。其中进基变量所在列为枢轴列，离基变量所在行为枢轴行，处于枢轴行列交叉位置的元素为枢轴元素(高斯-若尔当行计算具体步骤看基本步骤部分)。由此得到新的单纯形表，

第三次迭代得到最优结果，

基本步骤

• 最优性条件 在极大化(极小化)问题中，进基变量是$z$行中具有最小负值(最大正值)系数的非基变量，如有多个则选其一。当非基变量的所有$z$行系数是非负(非正)时，迭代达到最优。
• 可行性条件 对于极大化问题和极小化问题，离基变量都是具有最小非负比(有严格正分母)的基变量。
• 高斯-若尔当行计算
  
  1. 枢轴行。
     (a) 在基列中，用进基变量替换离基变量。
     (b) 新的枢轴行 = 当前枢轴行 / 枢轴元素
  2. 包括 z <script type=”math/tex” id=”MathJax-Element-22″>z</script>的所有其他行
     新行 = 当前行 – 枢轴列元素 * 新的枢轴行

单纯形法的步骤如下：
S1: 确定初始基本可行解
S2: 用最优性条件选择一个进基变量。如果没有进基变量，停止计算，上一个解就是最优的。否则，转到S3.
S3: 用可行性条件选择离基变量。
S4: 用高斯-若尔当运算确定新的基本解，转到S2。

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可