1.5 线性规划单纯形法

1.5.1 单纯形法原理

从可行解域的一个初始顶点（初始基本可行解）出发，沿着可行解域的边界逐个验算遇到的顶点（基本可行解），直至找到最优点（最优解）为止。现以上述【例1-1】的数学模型介绍单纯形法的求解过程，数学模型如下。

最优解为：X*= (75,15)T

Z*=5700

从原点O出发，沿着可行解域的边界可沿两条路线到达最优点h：

一条是O → a → h；另一条是O → b → k → h。

显然O → a → h是最近的路线，如图1-8所示。

线性规划数学模型要用单纯形法求解，数学模型必须具备一定的条件，即为标准型和规范型。否则该数学模型不能直接用单纯形法求解。

1.5.2 线性规划数学模型的标准型

要用单纯法求解线性规划数学模型，必须首先把数学模型化成标准型，因此我们首先介绍线性规划数学模型的标准型。具备下列条件的数学模型称为标准型数学模型。

条件①：数学模型具有等式约束方程组。

条件②：约束方程右边常数非负。

条件③：所有变量非负。

条件④：目标函数为Max型。

如以【例1-1】的数学模型，检验上述条件。

条件①：数学模型具有等式约束方程组。一般通过引入松弛变量将不等式约束化为等式约束。

对设备A的可用工时约束3x1+ 9x2≤540，引入非负松弛变量x3，加到不等式的左边得：

对设备B的可用工时约束5x1+ 5x2≤450，引入非负松弛变量x4，加到不等式的左边得：

对设备C的可用工时约束9x1+ 3x2≤720，引入非负松弛变量x5，加到不等式的左边得：

条件②：约束方程右边常数非负。否则可在两边同时乘以（-1）使得约束方程右边常数变为非负。这个条件已经满足。

条件③：所有变量非负。这个条件已经满足。

若xk为无约束变量（即可正可负），则令xk=x′k -x′′k，其中xk′, xk′′≥0，即可变为非负变量。

条件④：目标函数为Max型。这个条件也已经满足。对于Min型目标函数，则化为Max型目标函数。

如Min Z =x1-3x2+2x3，两边乘以（-1）得：-Min Z =-x1+3x2-2x3

令Z =-D，则原目标函数等价于Max D =-x1+3x2-2x3

因此，【例1-1】数学模型的标准型为：

1.5.3 线性规划数学模型的规范型

数学模型为标准型还不够，还需要把数学模型化成规范型，下面介绍线性规划数学模型的规范型。在标准型的基础上再增加下列两个条件的数学模型称为规范型数学模型。

条件①：约束方程组系数矩阵中含有至少一个单位子矩阵，对应的变量称为基变量。

条件②：目标函数中不含基变量。

如【例1-1】中，约束方程组系数矩阵中有单位子矩阵（第3、第4、第5列） ，对应的变量x3、x4、x5为基变量，此时x1、x2为非基变量。因此条件①满足。

基的作用是：可得到初始基本可行解（即初始顶点，通常是原点O），这是单纯形迭代的基础。

由于目标函数中不含基变量，这是因为基变量（即松弛变量）x3、x4、x5是从外面引进到约束方程中的变量，所以目标函数中当然不含这些基变量。因此条件②自然就满足。

所以【例1-1】的数学模型规范型为：

Max Z = 70x1+30x2

1.5.4 最优解寻求步骤

第一步 确定初始基本可行解X(1)。

利用规范型数学模型，令非基变量xj=0，求出基变量xi=bi，即得初始基本可行解。

在【例1-1】的数学模型中，令非基变量x1=x2=0，求出基变量x3=540、x4=450、x5=720，得初始基本可行解为：

X(1)=(x1,x2,x3,x4,x5)T=(0,0,540,450,720)T

Z(1)= 0

此时甲、乙两个产品的产量都为0，未进行生产，利润为0，设备A、B、C的空闲工时等于可用工时，即设备全部闲置，初始基本可行解对应原点O。此时x3、x4、x5为基变量，x1、x2为非基变量。

第二步 判断当前解X(1)是否最优。

检查用非基变量表达的目标函数中非基变量前的系数Rj，称为检验数。

① 若全部检验数Rj≤0，则当前解最优，解不能改进。

② 若存在Rj＞0，当前解非最优，解可改进，寻求更好的解。

在目标函数Max Z=70x1+30x2中，因为x1、x2为非基变量，所以70、30是检验数。

因为检验数70、30＞0，所以当x1和x2从0增大时，Z也会增大，故当前解非最优，须改进，寻求更好的解。

第三步 确定增大的非基变量（入基）及其上界。

选择使目标Z值改变得最快的非基变量优先增大（或称入基），即选择最大的正检验数对应的非基变量入基。在目标函数MaxZ = 70x1+30x2中，因为70＞30，即x1增加1千克，可使目标Z增加70元；x2增加1千克，可使目标Z增加30元，因此应选最大的正检验数70对应的非基变量x1优先增大（入基），此时x2仍然为0保持不变。

从图解法可知x1增加的上界是80。另外也可从约束方程组得出x1增加的上界是80，从三个约束方程组中可分别解出x1：

从设备最优利用角度，总希望设备空闲工时x3=x4=x5=0，而此时x2=0，于是得：

x1=180，表示目前可用的设备A台时数允许生产甲产品最多180千克，对应于P点（不可行）；

x1=90，表示目前可用的设备B台时数允许生产甲产品最多90千克，对应于Q点（不可行）；

x1=80，表示目前可用的设备C台时数允许生产甲产品最多80千克，对应于a点（可行）。

为了保证生产的可行性，受到三种设备可用工时的限制，x1应该取最小值80作为非基变量x1增加的上界，称为最小比值规则。即。

第四步 确定新解X(2)。

将x1=80、x2=0代入约束方程组中求出x3=300、x4=50、x5=0，于是得新解X(2)为：

X(2)=(x1, x2, x3, x4, x5)T=(80,0,300,50,0)T

Z(2)=5600

此时甲产品产量为80千克，乙产品产量为0，利润为5600元，设备A、B、C的空闲工时分别等于300、50、0，分别消耗了A、B、C设备240、400、720工时，该基本可行解对应顶点a。此时x1、x3、x4为基变量，x2、x5为非基变量。

从X(1)到X(2)，基的结构进行了置换，x1的值从0变成正数80，称为入基；x5的值从正数720变成0，称为出基，此时目标函数值从0增加到5600。

第五步 判断当前解X(2)是否最优。

在目标函数Max Z = 70x1+30x2中，因为x1已变成了基变量，不再是非基变量，因此需要消去，从第三个约束方程9x1+3x2+ x5= 720中，解出，代入目标函数中得

因为检验数，所以当x2从0增大时，Z还会增大，故当前解仍然非最优，须改进，继续寻求更好的解。

第六步 确定增加的非基变量（入基）及其上界。

目标函数中只有一个正检验数，因此选该正检验数对应的非基变量x2入基。

从图解法可知x2增加的上界是15。另外也可从约束方程组得出x2增加的上界是15，从三个约束方程组中可分别解出x2，同时令x3=x4=x5=0，得：

从第三个约束条件方程式（因为此时设备C可用工时已经用完，所以设备C对后续生产无作用，可消去）中解出，代人第一、二个方程式中消去x1，可得：

x2=37.5，表示目前可用的设备A台时数允许生产乙产品37.5千克，对应于R点（不可行）；

x2=15，表示目前可用的设备B台时数允许生产乙产品15千克，对应于h点（可行）。

根据最小比值规则，取x2=15（上界），此时。

第七步 确定新解X(3)。

将x1=75、x2=15代入约束方程组中求出x3=180、x4=0、x5=0、于是得新解X(3)为：

X(3)=(x1, x2, x3, x4, x5)T=(75,15,180,0,0)T

Z(3)=5700

此时乙产品产量为15千克，受设备可用工时限制，甲产品产量降为75千克，利润为5700元，设备A、B、C的空闲工时分别等于180、0、0，分别进一步消耗了A、B、C设备120、50、0工时，该基本可行解对应顶点h。此时x1、x2、x3为基变量，x4、x5为非基变量。

从X(2)到X(3)，基的结构也进行了置换，x2的值从0变成正数15，称为入基；x4的值从正数50变成0，称为出基，此时目标函数值从5600增加到5700。

第八步 判断当前解X(3)是否最优。

在目标函数Max Z =70x1+30x2中，因为x1和x2都已变成了基变量，不再是非基变量，因此需要消去，从第二、三个约束方程5x1+5x2+x4=450、9x1+3x2+x5=720中解出x1和x2：

代入目标函数中得：

因为检验数-2、，所以当x2和x5从0增大时，Z只会减少而不会增加，故当前解最优。最优解为：X*= X(3)= (x1, x2, x3, x4, x5)T= (75,15,180,0,0)T

Z*=Z(3)=5700

所以，产品甲、乙分别安排产量75千克、15千克，可使公司获最大利润为5700元。

从以上过程可以看出，单纯形法过程是从一个基本可行解变换到另一个基本可行解的重复过程，直至找到最优解。

1.5.5 单纯形表求解

上面我们讨论了单纯形法的求解过程，实际上单纯形法是用单纯形表来计算的，原理相同但比较简洁，仍以【例1-1】数学模型为例进行说明。将规范型数学模型写成如下形式：

第一步 列出初始单纯形表，获得初始基本可行解X(1)。

第二步 判断当前表是否最优。

当前表中存在两个正检验数R1=70和R2=30，因此当前表非最优，转下步。

第三步 确定入基的非基变量。

选择最大的正检验数R1=70对应的非基变量x1入基，根据规范型的要求x1入基后必须符合两个条件：一是x1的系数列向量为单位向量，二是x1的检验数为0。

第四步 确定出基的基变量。

由于基变量的个数等于约束方程个数（即3个）, x1入基后就必须选择一个非基变量出基以保持三个基变量。选择正的最小比值θ3=Min{540/3,450/5,720/9}= Min{180,90,80}=80对应的非基变量x5出基。

第五步 确定主元素a31=9。

以主元素a31为中心进行旋转运算（用初等行变换将入基列变为单位向量列，入基变量的检验数变为0，此时出基列变为非单位向量列），得第二个表。

操作过程：将表1的第三行（主元行）除以主元素9得表2的第三行；将表2的第三行乘以（-3）后加上表1的第一行得表2的第一行，即

同理将表2的第三行乘以（-5）后加上表1的第二行得表2的第二行；将表2的第三行乘以（-70）后加上表1的（-Z）行得表2的（-Z）行。

另外（-Z）行的检验数和目标值还有一种计算方法：

比如，初始表x1的检验数；初始表（-Z）。其他类似。

第六步 重复第二、三、四、五步直至所有检验数Rj均为非负，得最优表。过程如表1-11所示。

最优解为：

X*=X(3)=(75,15,180,0,0)T

Z*=Z(3)=5700

即得最优决策方案：产品甲、乙分别安排产量75千克、15千克，可使公司获得最大利润为5700元。

1.5.6 人造基下的单纯形表求解——大M法

用单纯形法求解需要将数模化为规范型，但是并非所有的数模都能够通过引入松弛变量化为规范型，当数模的约束条件出现“=”或“≥”时，要将数模化为规范型，一般情况下就需要引入一种新的变量（称之为人工变量）形成初始基（称之为人造基）。

因此，规范型数学模型解基的形成只有三种可能：

（1）由决策变量自然形成的解基；

（2）由添加松弛变量形成的解基；

（3）由引入人工变量形成的解基，叫人造基，它由虚拟的人工变量组成。

前二种解基由具体的物理变量组成，每步迭代后的解均是可行解，可含在最优解里，具有实际的经济意义。

第三种解基中的人工变量是虚拟变量，没有任何意义，它们的引入改变了原s.t.，使得求出的解是不可行解。第三种解基（人造基）的规范型数学模型采用大M（很大很大的正数）法求解：通过单纯形迭代，将人工变量从基中置换出来，使其取值为0，并得初始基本可行解，这相当于第一阶段；舍去人工变量，继续用单纯形迭代，求出最优解，这相当于第二阶段。

【例1-11】求解下列线性规划数学模型

解：用图解法可求得最优解X*= (0,3)T, Z*=6，如图1-9所示。

引入非负剩余变量——松弛变量x3、x4和x5将约束条件化为标准型：

令Z=-Z′，原目标函数等价于Max Z′ = -x1+ 2x2

再引入非负人工变量x6和x7将约束条件化为规范型。于是得原问题的规范型为

现采用大M法求解。在原目标函数Min Z = x1-2x2中的后面加上（Max型目标函数减去）阻碍项M （x6+x7）得新目标函数Min Z = x1-2x2+M（x6+x7），其中M是很大的正数。

令Z=-Z′，则新目标函数等价于目标函数Max Z′ =-x1+ 2x2-M（x6+x7），由于x6、x7为基变量，须消去，从约束条件得x6+x7=3-2 x2+x3+x 4，代入目标函数Z′中得：Max Z′=-3M-x1+（2M+2）x 2-Mx 3-Mx4。于是得出如下新的规范型数学模型：

单纯形表求解如表1-12所示。

所以最优解为：

X*= X(5)= (0,3,1,2,0)T

Z*= -Z′ (5)= -6