2. 3 单纯形法的计算步骤
由于单纯形(2. 12) 的目标函数和约束函数中含有基变量和非基变量, 为了设计出方便,
有效的计算方法, 我们将简化单纯形的表达形式, 称其为单纯形表格。比如, 下述单纯形:
η=6-3x 1-x 2
s 1=4-x 1 s 2=3-2x 1-x 2
的简化单纯形表格如下(参见表2. 3) 。这种格式使得我们非常容易识别基变量, 我们只要将仅
表2. 3:简单单纯形表
有1个" 1" 的列(s 1和s 2) 为基变量。
2. 3. 1 标准最大化线性规划的单纯型法
为了设计标准最大化线性规划问题(1. 15) 的初始单纯形表, 我们首先将它的等价问题
(2. 11) 改写为:
max η=
∑c x +∑0⨯x
j
j
j =1
i =1
n m
n +i
⎧n
⎪∑a ij x j +x n +i =b i , i =1, 2,..., m s . t . ⎨j =1 (2. 16)
⎪x j ≥0, j =1, 2,..., n , n +1,..., n +m ⎩
那么标准最大化线性规划问题(1. 15) 的初始单纯形表被表示为(参见表2. 4): 表2. 4:标准最大化线性规划的初始单纯形表
其中:c j , j =1, 2,..., n 为原问题目标函数的系数, B ={n +1, n +2,..., n +m }为基变量下标集合, N ={1, 2,..., n }为非基变量下标集合, x B 为基变量, c B 为基变量在原问题目标函数系数, b B 为基变量的解, 那么初始基可行解为x 0=(0,..., 0, b 1,..., b m ) , 为对应初始目标函数值。
我们将解释表2. 6中sac j 和imp j 行的计算方法和经济涵义。由于标准最大化线性规划问题可被看成是利用m 种资源生产n 种产品, 决策变量x j 在线性规划约束条件中的系数a ij 可以被理解为, 为了生产一件产品j (j =1, 2,..., n ) 需要消耗原材料i (i =1, 2,..., m ) 的数量; 决策变量x j 在目标函数中的系数c j 是一件产品j 的利润; 松弛变量x n +i 则表示第i 种原材料的剩余量。基于上述描述, 我们引入下面两个概念:
(1) 生产一件产品j 的单位边际损失值
sac j =∑c i ⨯ij j ∈N
i ∈B
(2. 17)
其中c i , i ∈B 是对应基变量在目标函数中的系数, 显然c i 或表示某件产品的单位利润或等于
0。乘积项c i ⨯ij 有四种经济解释:
(a ) 如果j , j ∈N 代表产品且i , i ∈B 代表尚未使用的原材料, ij 表示生产一件产
品j 所消耗原材料i 的数量, 则c i ⨯ij =0, 表示生产一件产品j 没有产生边际损失;
(b ) 如果j , j ∈N 代表产品且i , i ∈B 也代表产品, ij 表示产品j 与产品i 的替代
关系, c i ⨯ij , 表示未了生产一件产品j 而放弃生产产品i 所产生的利润损失, 所以c i ⨯ij 是生产一件产品j 而发生的边际损失;
(c ) 如果j , j ∈N 代表剩余原材料且i , i ∈B 代表剩余原材料, ij 表示剩余原材料
j 与剩余原材料i 的之间的替代关系, 则c i ⨯ij =0, 表示这种替代不产生边际损失;
(d ) 如果j , j ∈N 代表剩余原材料且i , i ∈B 代表产品, ij 表示剩余原材料j 增加
一个单位导致产品i 的产量减少, 则c i ⨯ij 是剩余原材料j 增加一个单位所引起的边际损失;
所以, 我们将为了生产一件产品j 的所有边际损失值相加, 即,
∑c ⨯a
i i ∈B
ij
, 它就是为了生产
单位产品j 而放弃生产其他产品所产生的利润损失之和。如果j 代表剩余原材料,
∑c ⨯a
i i ∈B
ij 的经济涵义是
j 种剩余原材料增加了一个单位而引起所有产品产量减少引起的利
i
ij
润损失之和。我们将
∑c ⨯a
i ∈B
称为单位边际损失值。
(2) 生产一件产品j 的边际收益
imp j =c j -∑c i ⨯a ij j ∈N (2. 18)
i ∈B
由于生产一件产品j 的单位边际损失值是
∑c ⨯a
i i ∈B
ij
, 而生产一件产品j 获得的单位利
润是c j , 那么imp j 代表生产单位产品j 的实际收益。对于利润最大化的线性规划问题, imp j 的经济学含义就是产品j 的边际收益。只有当imp j 大于0时, 生产产品j 才能够增加收益。如果j 代表剩余原材料, 则c j =0, 这时imp j =-
∑c ⨯a
i i ∈B
ij , 如果
imp j 大于0, 这意味着当j
种剩余原材料增加一个单位反而引起实际收益增加。总之, imp j 是否大于0作为单纯形法是否继续迭代的判别条件或检验准则。imp j 是单纯形(2. 12) 中的j , 它可用于单纯形是否继续迭代的准则。
(3) 按当前计划生产的利润
单纯形迭代是从初始表2. 6开始, 通过选择主元素a lk , k ∈N , l ∈B 进行高斯变换, 产生新的单纯形表。所以我们将单纯形法的计算步骤总结如下:
第一步:转换标准最大化线性规划问题为标准格式
对标准最大化线性规划问题(1. 15) 引进松弛变量, 消除小于等于不等式约束, 构造初始单
=∑c i ⨯i
i ∈B
(2. 19)
纯形表, 并以松弛变量为初始基变量x n +i , i ∈B , 以决策变量为初始非基变量x j , j ∈N 。
第二步:计算单纯形表的sac 和imp 行
利用公式(2. 17) 和(2. 18) , 我们分别计算单纯形表中sac j 和imp j 行的数值。并利用
imp j , j ∈N 的符号判断是否继续进行迭代。如果对所有j ∈N 都有:imp j ≤0, 则当前单纯
形表对应的基可行解就是标准最大化线性规划问题的最优解。
第三步:确定换入变量
根据imp j , j ∈N 来决定换入变量, 我们的目标是选择对目标函数(利润) 贡献最大的那
个边际收益, 即确定换入变量的准则为:
imp k =m ax {imp j >0}
j ∈N
下标k ∈N 所对应的变量x k 就是换入变量。
第四步: 确定换出变量
根据换入变量x k , k ∈N 所在的列, 计算换出比例:
b i
, i ∈B , 由于变量x i , i ∈B 的非负a ik
符号限制, 换出变量的选择规则为:
或者:
b l b
:l =1, 2,..., l 1}=min {i :a ik >0, i ∈B } a lk a ik i ∈B a lk a
:l =1, 2,..., l 1}=max ik :i ∈B } b l b i i ∈B
选择l =min{1, 2,..., l 1}, 以x l , l ∈B 表示换出变量, 那么称变量x k 与变量x l 的交换系数a lk 为迭代的主元素。
第五步:构造一个新的单纯形表
以主元素a lk 进行迭代, 把x k 所对应的列变换为:
⎧0i ≠l
, i ∈B ik =⎨
1i =l ⎩
在x B 列中, 用换入变量x k 替代换出变量x l , 在c B 列中, 用c k 替代c l , 得到一个新的单纯形表。
(6) 回到第二步
计算新单纯形表中sac j 和imp j 行的数值, 如果imp j ≤0, ∀j ∈N , 那么当前基可行解就
是最优解, 否则继续进行迭代。 我们用例2. 1来说明单纯形法的计算步骤。
第一步:对例2. 1的约束条件引进松弛变量x 3+i , i =1, 2, 3, 那么例2. 1的标准格式为:
max η=5x 1+4x 2+3x 3
⎧2x 1+3x 2+x 3+x 4=5
⎪4x +x +2x +x =11⎪1235
s . t . ⎨
3x +4x +2x +x =8236⎪1⎪⎩x j ≥0, j =1, 2,..., 6
(2. 20)
然后, 根据式(2. 20) 构造例2. 1初始单纯形表(参见表2. 5):
表2. 5: 例2. 1初始单纯形表
第二步:计算sac j 和imp j 行如下:
由于基变量下标集为:B ={4, 5, 6}, 非基变量下标集为:N ={1, 2, 3}, 对于任意i ∈B , 有
c 4=0, c 5=0, c 6=0, 所以, 对于非基变量sac j , j ∈N 的计算如下:
sac 1=0⨯2+0⨯4+0⨯3=0
同样原理, 对于j =2, 3, sac 2=sac 3=0。对于基变量的sac i , i ∈B 的计算如下:
sac 4=0⨯1+0⨯0+0⨯0=0
同理, sac 5=sac 6=0。根据imp j =c j -sac j , j =1, 2,..., 6, imp j 行的各列计算结果参见表
2. 5的imp 行。
第三步:确定换入变量:
由于选择换入变量的标准是max {imp j >0}, 根据表2. 5的imp 行, 可以确定k =1为换
j ∈N
入变量的下标, 而x 1为本次迭代的换入变量。
第四步:确定换出变量
根据换入变量x 1所在的列, 计算换出比例:{
b i
},i ∈B , 即: a i 1
{
由于它们的最小值为
b 4b 5b 65118, , }={, , a 41a 51a 61243
5
, 所以l =4为换出变量的下标, 同时变量x 4被确定为换出变量。 2
第五步:构造一个新的单纯形表
以a 41=2为主元素对x 1所在列进行高斯变换: 根据表2. 5, 换出变量x 4与非基变量的关系为:2x 1+3x 2+x 3+x 4=5, 将其两端同时除以2后, 则有:
x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5
考虑下面二个方程:
x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5 (表2. 5的第3行) 4x 1+x 2+2x 3+x 5=11 (表2. 5的第4行)
希望消去变量x 1, 所以:
-4⨯(x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5)
+(4x 1+x 2+2x 3+x 5=11)
_________________________________
-5x 2-2x 4+x 5=1
再考虑下面二个方程:
x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5 (表2. 5的第3行)
3x 1+4x 2+2x 3+x 6=8 (表2. 5的第5行)
为了消去变量x 1, 有:
-3⨯(x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5)
+(3x 1+4x 2+2x 3+x 6=8)
_________________________________
-0. 5x 2+0. 5x 3-1. 5x 4+x 6=0. 5
更新基变量下标集:B ={1, 5, 6}和非基变量下标集:N ={4, 2, 3}, 再将变量x 4用x 1替换,
c 4用c 1替换, 就获得一张新单纯形表(参见表2. 6) 。若令所有非基变量等于0,
即:x 4=0, x 2=0, x 3=0, 基变量就分别为:x 1=2. 5, x 5=1, 及x 6=0. 5, 它们共同组成了一个基可行解, 最后根据式(2. 19) , 目标函数η=5⨯2. 5+0⨯1+0⨯0. 5=12. 5。 表2. 6: 例2. 1第二张单纯形表
对表2. 6重复单纯形算法第二步第五步。
(1) 计算表2. 6中的sa c 和imp 行。从表2. 6的imp 行看到, 对应非基变量x 3的
imp 3=0. 5>0, 需要继续迭代。
(2) 确定换入变量:
换入变量。
由于只有imp 3≥0, 那么确定换入变量的下标为:k =3, 而x 3为
(3) 确定换出变量: 根据换入变量x 3所在的列, 计算换出比例:b i
i ∈B , 即: a i 3
b 1b 5b 62. 510. 5, , ={, , ={5, ∞, 1}, a 13a 53a 630. 500. 5
它们的最小值为1, 对应的下标为l =6, 所以x 6被确定为换出变量。
(4) 构造下一个新的单纯形表:我们首先以a 63=1为主元素对x 3所在列(表2. 6的第五
列) 进行高斯变换, 。然后再更新基变量下标集:B ={1, 5, 3}和非基变量下标集:N ={4, 2, 6}, 再用变量x 3替换x 6, 用c 3替换c 6, 就获得一张新单纯形表(参见表2. 7) 。若令所有非基变量等于0, 即:x 4=0, x 2=0, x 6=0, 基变量就分别为:x 1=2, x 5=1, 及x 3=1, 它们共同组成了一个基可行解, 目标函数为η=5⨯2+0⨯1+3⨯1=13。
表2. 7: 例2. 1第三张单纯形表
对表2. 7重复单纯形法的第二步第五步。
(1) 计算表2. 7的sac 行和imp 行。从表2. 7的imp 行看到, 对于所有非基变量, 均
有:imp j
2. 3. 2 利用单纯形法求解最小化问题
利用单纯形法求解最小化线性规划问题的方法有两种, 我们将通过例2. 2来说明它们的
应用。
例2. 2 考虑下述最小化线性规划问题:
min
η=2x 1-3x 2
(2. 21)
⎧x 1+x 2≤4⎪
s . t . ⎨x 1-x 2≤6
⎪x , x ≥0⎩12
*
方法一
**
如果点x *=(x 1, x 2) 是例2. 2的最优解, 则x 一定是问题(2. 21) 的可行域中使得目标函
*
数:η=2x 1-3x 2达到最小值的可行解。这等价于x 是问题(2. 21) 的可行域中使得函数
-η=-2x 1+3x 2达到最大值的可行解。所以为了求问题(2. 21) 的最优解, 我们只需要求解
下述线性规划问题:
m a x -η=-2x 1+3x 2
⎧x 1+2x 2≤4
⎪
s . t . ⎨x 1-x 2≤6
⎪x , x ≥0⎩12
(2. 22)
在对问题(2. 22) 引进松弛变量x 3, x 4之后, 我们可获得其初始单纯形表(参见表2. 8) :
2. 82. 2
选择非基变量x 2为换入变量, 换出比例说明x 3为换出变量, 迭代后的单纯形(表参见表
2. 9) 为:
2. 92. 2
因为非基变量对应的imp 那么, 问题1和imp 3都小于0, 所以表2. 9是例2. 2的最优单纯形表。
(2. 22) 的最优解为:x 2=2, x 4=8, x 1=0, x 3=0, -=6。而问题(2. 21) 的最优解
为:x 2=2, x 4=8, x 1=0, x 3=0, =-6。或者将x 1和x 2代入问题(2. 21) 的目标函数, 有:
η=2x 1-3x 2=2⨯0-3⨯2=-6
总而言之, 对于最小化线性规划问题, 可对它的目标函数成-1, 然后按最大化线性规划问题进行求解。
方法二 我们对求解最大化线性规划问题的单纯形法略作修改, 就可获得求解最小化线性规划问题的单纯形法。修改第二步:计算单纯形表的sac 和imp 行, 选择imp j 0, j ∈N , 对应单纯形表上的基可行解就是最小化线性规划问题的最优解。这是因为增加非基变量的值只能能够使目标函数值增大。在对问题(2. 21) 直接引进松弛变量x 3, x 4之后, 我们可获得其初始单纯形表(参见表2. 10) : 表2. 10: 例2. 2初始单纯形表-方法二
因为对应于非基变量x 2的检验数为imp 2=-3, 选择x 2为换入变量, 换出比例说明x 3为换出变量, 迭代后的单纯形表参见表2. 11:
2. 112. 2因为非基变量对应的检验数imp 1和imp 3都大于0, 所以表2. 11是例2. 2的最优单纯形表。那么, 问题(2. 21) 的最优解为:x 2=2, x 4=8, x 1=0
, x 3=0, =-6。
2. 3. 3多重最优解
我们将说明如何利用单纯形法确定一个线性规划问题是否存在多重最优解。我们在1. 4
节中利用图解法说明当电视机生产问题的目标函数为η=100x A +300x B 时的线性规划具有多重最优解。
例2. 3 重新考虑电视机生产的线性规划问题:
max η=100x A +300x B
⎧2x A +x B ≤40⎪x +3x ≤45⎪A B
s . t . ⎨ (2. 23)
⎪x A ≤12⎪⎩x A , x B ≥0
对问题(2. 23) 引进松弛变量s 1, s 2, 和s 3之后, 我们获得初始单纯形(参见表2. 12)
因为在检验行中, imp B =300具有最大值, 所以选择非基变量x B 为换入变量, 比例值表明s 2为换出变量, 进行迭代后, 获得一新单纯形表(参见表2. 13): 表2. 13: 例2. 3最优单纯形表一
因为对应于非基变量x A 和s 2的检验数imp A 和imp 2均不大于0, 表2. 13是例2. 3的最优单纯形表, 最优解为:x A =0, x B =15, s 1=25, s 2=0, s 3=12, =4500。然而, 在最优单纯形表中, 非基变量x A 的检验数im p A 等于0, 如果选择x A 为换入变量, 对应的比例值为
{15, 45, 12}, 则s 3为换出变量, 迭代后的单纯形表(参见表2. 14) 为:
表2. 14: 例2. 3最优单纯形表二
因为对应于非基变量s 2和s 3的检验数im p A 和imp 2均不大于0, 表2. 14是例2. 3的另一个最优单纯形表, 最优解为:x A =11, x B =12, s 1=5, s 2=0, s 3=0, =4500。
由于基可行解对应可行域的一个顶点, 那么我们可以说明连接上述两个最优顶点线段上的所有点都是例2. 3的最优解。为此, 我们设:
1
⎡x 12⎤⎡11⎤⎡x 1⎤⎡0⎤2
最优顶点1:x =⎢1⎥=⎢⎥ 最优顶点1:x =⎢2⎥=⎢⎥
⎣x 2⎦⎣12⎦⎣x 2⎦⎣15⎦
1
那么, 对于任意0≤δ≤1,
x =⎢
⎡x 1⎤⎡0⎤⎡12⎤⎡12-12δ⎤
=δ⎢⎥+(1-δ) ⎢⎥=⎢⎥⎥
⎣15⎦⎣11⎦⎣11+4δ⎦⎣x 2⎦
也都是例2. 3的最优解。比如, 选择δ=0. 5, 我们获得一最优解x A =6, x B =13, =4500。
2. 3. 4 无界解
我们在2. 2节中讨论了判断标准最大化线性规划问题(1. 5) 是无界的条件, 即:对于可行解, 如果存在某个k ∈
N 使k >0, 并且对任意i ∈B , 都有ik ≤0。在本节中, 我们将讨论如何利用单纯形来判断线性规划问题(1. 5) 是无界的。 例2. 4考虑下述线性规划问题:
max η=36x 1+30x 2-3x 3-4x 4
⎧x 1+x 2-x 3≤5⎪
s . t . ⎨6x 1+5x 2-x 4≤10
⎪x , x , x , x ≥0⎩1234
(2. 24)
对问题(2. 24) 引进松弛变量x 5和x 6后, 获其初始单纯形表(参见2. 15):
因为对应非基变量的检验数中绝对值最大的为imp 1=36, 选择x 1为换入变量。比例值表明
x 6为换出变量。迭代后的新单纯形表(参见表2. 16) 为:
表2. 16: 例2. 4的第二张单纯形表
选择非基变量x 4作为换入变量, 比例值说明x 5为换出变量。迭代后的新单纯形表(参见表
2. 17) 为:
表2. 17: 例2. 4的第三张单纯形表
选择非基变量x 3作为换入变量, 保持其他非基变量x 2, x 5, 和x 6为0, 基变量x 1, x 4与x 3的关系为：
x 1=5+x 3 x 4=20+6x 3
将它们代入问题(2. 24) 的目标函数中, 则有：
η=100+12x 3
当x 3的取值不断增大时, 比如x 3=1000, x 1=1005, x 2=0, x 4=6020, 目标值也不断增大, 等于η=12010, 所以线性规划问题(2. 24) 无界。
2. 3. 5 根据检验数确定目标函数系数
在2. 2节中, 我们讨论了线性规划在若干次迭代之后的单纯形：
η=+∑j x j
j ∈N
x i =i -
∑j ∈N
ij
x j i ∈B , j ∈N
那么根据式中的检验数系数j , i , 和ij , 我们应当能够计算原问题目标函数的系数c j , 并将它转换成单纯形表。
例2. 5 考虑下述单纯形:
η=3+x 3-x 1
x 2=10+2x 3-3x 1
(2. 25)
x 4=7+0x 3-4x 1
x 5=0+0x 3+x 1
因为基变量下标集为{2, 4, 5}, 非变量下标集为{1, 3}, 我们可判断出决策变量为n =2，约束条件为m =3，c 3=c 4=c 5=0，需要求出c 1和c 2。由于1=-1, 3=1, =5,
⎡2⎤⎡10⎤⎡a 21⎤⎡3⎤⎡a 23⎤⎡-2⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥
⎢4⎥=⎢7⎥, ⎢a 41⎥=⎢4⎥, ⎢a 43⎥=⎢0⎥，而根据式(2. 18) 非基变量x 3的检验数为： ⎢5⎥⎢⎣a 51⎥⎦⎢⎣-1⎥⎦⎢⎣a 53⎥⎦⎢⎣0⎥⎦⎦⎢⎣⎦⎣0⎥
1=c 3-[c 2
⎡-2⎤
⎥=0+2c
00]⎢02⎢⎥
⎢⎣0⎥⎦
那么, c 2=
1
非基变量x 1的检验数为： 2
-1=c 1-[c 2
⎡3⎤
⎥=c -3c
00]⎢412⎢⎥
⎢⎣-1⎥⎦
1
, 而对应单纯形(2. 25) 的单纯形表为(参见2. 18)
2
则, c 1=
2. 3 单纯形法的计算步骤
由于单纯形(2. 12) 的目标函数和约束函数中含有基变量和非基变量, 为了设计出方便,
有效的计算方法, 我们将简化单纯形的表达形式, 称其为单纯形表格。比如, 下述单纯形:
η=6-3x 1-x 2
s 1=4-x 1 s 2=3-2x 1-x 2
的简化单纯形表格如下(参见表2. 3) 。这种格式使得我们非常容易识别基变量, 我们只要将仅
表2. 3:简单单纯形表
有1个" 1" 的列(s 1和s 2) 为基变量。
2. 3. 1 标准最大化线性规划的单纯型法
为了设计标准最大化线性规划问题(1. 15) 的初始单纯形表, 我们首先将它的等价问题
(2. 11) 改写为:
max η=
∑c x +∑0⨯x
j
j
j =1
i =1
n m
n +i
⎧n
⎪∑a ij x j +x n +i =b i , i =1, 2,..., m s . t . ⎨j =1 (2. 16)
⎪x j ≥0, j =1, 2,..., n , n +1,..., n +m ⎩
那么标准最大化线性规划问题(1. 15) 的初始单纯形表被表示为(参见表2. 4): 表2. 4:标准最大化线性规划的初始单纯形表
其中:c j , j =1, 2,..., n 为原问题目标函数的系数, B ={n +1, n +2,..., n +m }为基变量下标集合, N ={1, 2,..., n }为非基变量下标集合, x B 为基变量, c B 为基变量在原问题目标函数系数, b B 为基变量的解, 那么初始基可行解为x 0=(0,..., 0, b 1,..., b m ) , 为对应初始目标函数值。
我们将解释表2. 6中sac j 和imp j 行的计算方法和经济涵义。由于标准最大化线性规划问题可被看成是利用m 种资源生产n 种产品, 决策变量x j 在线性规划约束条件中的系数a ij 可以被理解为, 为了生产一件产品j (j =1, 2,..., n ) 需要消耗原材料i (i =1, 2,..., m ) 的数量; 决策变量x j 在目标函数中的系数c j 是一件产品j 的利润; 松弛变量x n +i 则表示第i 种原材料的剩余量。基于上述描述, 我们引入下面两个概念:
(1) 生产一件产品j 的单位边际损失值
sac j =∑c i ⨯ij j ∈N
i ∈B
(2. 17)
其中c i , i ∈B 是对应基变量在目标函数中的系数, 显然c i 或表示某件产品的单位利润或等于
0。乘积项c i ⨯ij 有四种经济解释:
(a ) 如果j , j ∈N 代表产品且i , i ∈B 代表尚未使用的原材料, ij 表示生产一件产
品j 所消耗原材料i 的数量, 则c i ⨯ij =0, 表示生产一件产品j 没有产生边际损失;
(b ) 如果j , j ∈N 代表产品且i , i ∈B 也代表产品, ij 表示产品j 与产品i 的替代
关系, c i ⨯ij , 表示未了生产一件产品j 而放弃生产产品i 所产生的利润损失, 所以c i ⨯ij 是生产一件产品j 而发生的边际损失;
(c ) 如果j , j ∈N 代表剩余原材料且i , i ∈B 代表剩余原材料, ij 表示剩余原材料
j 与剩余原材料i 的之间的替代关系, 则c i ⨯ij =0, 表示这种替代不产生边际损失;
(d ) 如果j , j ∈N 代表剩余原材料且i , i ∈B 代表产品, ij 表示剩余原材料j 增加
一个单位导致产品i 的产量减少, 则c i ⨯ij 是剩余原材料j 增加一个单位所引起的边际损失;
所以, 我们将为了生产一件产品j 的所有边际损失值相加, 即,
∑c ⨯a
i i ∈B
ij
, 它就是为了生产
单位产品j 而放弃生产其他产品所产生的利润损失之和。如果j 代表剩余原材料,
∑c ⨯a
i i ∈B
ij 的经济涵义是
j 种剩余原材料增加了一个单位而引起所有产品产量减少引起的利
i
ij
润损失之和。我们将
∑c ⨯a
i ∈B
称为单位边际损失值。
(2) 生产一件产品j 的边际收益
imp j =c j -∑c i ⨯a ij j ∈N (2. 18)
i ∈B
由于生产一件产品j 的单位边际损失值是
∑c ⨯a
i i ∈B
ij
, 而生产一件产品j 获得的单位利
润是c j , 那么imp j 代表生产单位产品j 的实际收益。对于利润最大化的线性规划问题, imp j 的经济学含义就是产品j 的边际收益。只有当imp j 大于0时, 生产产品j 才能够增加收益。如果j 代表剩余原材料, 则c j =0, 这时imp j =-
∑c ⨯a
i i ∈B
ij , 如果
imp j 大于0, 这意味着当j
种剩余原材料增加一个单位反而引起实际收益增加。总之, imp j 是否大于0作为单纯形法是否继续迭代的判别条件或检验准则。imp j 是单纯形(2. 12) 中的j , 它可用于单纯形是否继续迭代的准则。
(3) 按当前计划生产的利润
单纯形迭代是从初始表2. 6开始, 通过选择主元素a lk , k ∈N , l ∈B 进行高斯变换, 产生新的单纯形表。所以我们将单纯形法的计算步骤总结如下:
第一步:转换标准最大化线性规划问题为标准格式
对标准最大化线性规划问题(1. 15) 引进松弛变量, 消除小于等于不等式约束, 构造初始单
=∑c i ⨯i
i ∈B
(2. 19)
纯形表, 并以松弛变量为初始基变量x n +i , i ∈B , 以决策变量为初始非基变量x j , j ∈N 。
第二步:计算单纯形表的sac 和imp 行
利用公式(2. 17) 和(2. 18) , 我们分别计算单纯形表中sac j 和imp j 行的数值。并利用
imp j , j ∈N 的符号判断是否继续进行迭代。如果对所有j ∈N 都有:imp j ≤0, 则当前单纯
形表对应的基可行解就是标准最大化线性规划问题的最优解。
第三步:确定换入变量
根据imp j , j ∈N 来决定换入变量, 我们的目标是选择对目标函数(利润) 贡献最大的那
个边际收益, 即确定换入变量的准则为:
imp k =m ax {imp j >0}
j ∈N
下标k ∈N 所对应的变量x k 就是换入变量。
第四步: 确定换出变量
根据换入变量x k , k ∈N 所在的列, 计算换出比例:
b i
, i ∈B , 由于变量x i , i ∈B 的非负a ik
符号限制, 换出变量的选择规则为:
或者:
b l b
:l =1, 2,..., l 1}=min {i :a ik >0, i ∈B } a lk a ik i ∈B a lk a
:l =1, 2,..., l 1}=max ik :i ∈B } b l b i i ∈B
选择l =min{1, 2,..., l 1}, 以x l , l ∈B 表示换出变量, 那么称变量x k 与变量x l 的交换系数a lk 为迭代的主元素。
第五步:构造一个新的单纯形表
以主元素a lk 进行迭代, 把x k 所对应的列变换为:
⎧0i ≠l
, i ∈B ik =⎨
1i =l ⎩
在x B 列中, 用换入变量x k 替代换出变量x l , 在c B 列中, 用c k 替代c l , 得到一个新的单纯形表。
(6) 回到第二步
计算新单纯形表中sac j 和imp j 行的数值, 如果imp j ≤0, ∀j ∈N , 那么当前基可行解就
是最优解, 否则继续进行迭代。 我们用例2. 1来说明单纯形法的计算步骤。
第一步:对例2. 1的约束条件引进松弛变量x 3+i , i =1, 2, 3, 那么例2. 1的标准格式为:
max η=5x 1+4x 2+3x 3
⎧2x 1+3x 2+x 3+x 4=5
⎪4x +x +2x +x =11⎪1235
s . t . ⎨
3x +4x +2x +x =8236⎪1⎪⎩x j ≥0, j =1, 2,..., 6
(2. 20)
然后, 根据式(2. 20) 构造例2. 1初始单纯形表(参见表2. 5):
表2. 5: 例2. 1初始单纯形表
第二步:计算sac j 和imp j 行如下:
由于基变量下标集为:B ={4, 5, 6}, 非基变量下标集为:N ={1, 2, 3}, 对于任意i ∈B , 有
c 4=0, c 5=0, c 6=0, 所以, 对于非基变量sac j , j ∈N 的计算如下:
sac 1=0⨯2+0⨯4+0⨯3=0
同样原理, 对于j =2, 3, sac 2=sac 3=0。对于基变量的sac i , i ∈B 的计算如下:
sac 4=0⨯1+0⨯0+0⨯0=0
同理, sac 5=sac 6=0。根据imp j =c j -sac j , j =1, 2,..., 6, imp j 行的各列计算结果参见表
2. 5的imp 行。
第三步:确定换入变量:
由于选择换入变量的标准是max {imp j >0}, 根据表2. 5的imp 行, 可以确定k =1为换
j ∈N
入变量的下标, 而x 1为本次迭代的换入变量。
第四步:确定换出变量
根据换入变量x 1所在的列, 计算换出比例:{
b i
},i ∈B , 即: a i 1
{
由于它们的最小值为
b 4b 5b 65118, , }={, , a 41a 51a 61243
5
, 所以l =4为换出变量的下标, 同时变量x 4被确定为换出变量。 2
第五步:构造一个新的单纯形表
以a 41=2为主元素对x 1所在列进行高斯变换: 根据表2. 5, 换出变量x 4与非基变量的关系为:2x 1+3x 2+x 3+x 4=5, 将其两端同时除以2后, 则有:
x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5
考虑下面二个方程:
x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5 (表2. 5的第3行) 4x 1+x 2+2x 3+x 5=11 (表2. 5的第4行)
希望消去变量x 1, 所以:
-4⨯(x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5)
+(4x 1+x 2+2x 3+x 5=11)
_________________________________
-5x 2-2x 4+x 5=1
再考虑下面二个方程:
x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5 (表2. 5的第3行)
3x 1+4x 2+2x 3+x 6=8 (表2. 5的第5行)
为了消去变量x 1, 有:
-3⨯(x 1+1. 5x 2+0. 5x 3+0. 5x 4=2. 5)
+(3x 1+4x 2+2x 3+x 6=8)
_________________________________
-0. 5x 2+0. 5x 3-1. 5x 4+x 6=0. 5
更新基变量下标集:B ={1, 5, 6}和非基变量下标集:N ={4, 2, 3}, 再将变量x 4用x 1替换,
c 4用c 1替换, 就获得一张新单纯形表(参见表2. 6) 。若令所有非基变量等于0,
即:x 4=0, x 2=0, x 3=0, 基变量就分别为:x 1=2. 5, x 5=1, 及x 6=0. 5, 它们共同组成了一个基可行解, 最后根据式(2. 19) , 目标函数η=5⨯2. 5+0⨯1+0⨯0. 5=12. 5。 表2. 6: 例2. 1第二张单纯形表
对表2. 6重复单纯形算法第二步第五步。
(1) 计算表2. 6中的sa c 和imp 行。从表2. 6的imp 行看到, 对应非基变量x 3的
imp 3=0. 5>0, 需要继续迭代。
(2) 确定换入变量:
换入变量。
由于只有imp 3≥0, 那么确定换入变量的下标为:k =3, 而x 3为
(3) 确定换出变量: 根据换入变量x 3所在的列, 计算换出比例:b i
i ∈B , 即: a i 3
b 1b 5b 62. 510. 5, , ={, , ={5, ∞, 1}, a 13a 53a 630. 500. 5
它们的最小值为1, 对应的下标为l =6, 所以x 6被确定为换出变量。
(4) 构造下一个新的单纯形表:我们首先以a 63=1为主元素对x 3所在列(表2. 6的第五
列) 进行高斯变换, 。然后再更新基变量下标集:B ={1, 5, 3}和非基变量下标集:N ={4, 2, 6}, 再用变量x 3替换x 6, 用c 3替换c 6, 就获得一张新单纯形表(参见表2. 7) 。若令所有非基变量等于0, 即:x 4=0, x 2=0, x 6=0, 基变量就分别为:x 1=2, x 5=1, 及x 3=1, 它们共同组成了一个基可行解, 目标函数为η=5⨯2+0⨯1+3⨯1=13。
表2. 7: 例2. 1第三张单纯形表
对表2. 7重复单纯形法的第二步第五步。
(1) 计算表2. 7的sac 行和imp 行。从表2. 7的imp 行看到, 对于所有非基变量, 均
有:imp j
2. 3. 2 利用单纯形法求解最小化问题
利用单纯形法求解最小化线性规划问题的方法有两种, 我们将通过例2. 2来说明它们的
应用。
例2. 2 考虑下述最小化线性规划问题:
min
η=2x 1-3x 2
(2. 21)
⎧x 1+x 2≤4⎪
s . t . ⎨x 1-x 2≤6
⎪x , x ≥0⎩12
*
方法一
**
如果点x *=(x 1, x 2) 是例2. 2的最优解, 则x 一定是问题(2. 21) 的可行域中使得目标函
*
数:η=2x 1-3x 2达到最小值的可行解。这等价于x 是问题(2. 21) 的可行域中使得函数
-η=-2x 1+3x 2达到最大值的可行解。所以为了求问题(2. 21) 的最优解, 我们只需要求解
下述线性规划问题:
m a x -η=-2x 1+3x 2
⎧x 1+2x 2≤4
⎪
s . t . ⎨x 1-x 2≤6
⎪x , x ≥0⎩12
(2. 22)
在对问题(2. 22) 引进松弛变量x 3, x 4之后, 我们可获得其初始单纯形表(参见表2. 8) :
2. 82. 2
选择非基变量x 2为换入变量, 换出比例说明x 3为换出变量, 迭代后的单纯形(表参见表
2. 9) 为:
2. 92. 2
因为非基变量对应的imp 那么, 问题1和imp 3都小于0, 所以表2. 9是例2. 2的最优单纯形表。
(2. 22) 的最优解为:x 2=2, x 4=8, x 1=0, x 3=0, -=6。而问题(2. 21) 的最优解
为:x 2=2, x 4=8, x 1=0, x 3=0, =-6。或者将x 1和x 2代入问题(2. 21) 的目标函数, 有:
η=2x 1-3x 2=2⨯0-3⨯2=-6
总而言之, 对于最小化线性规划问题, 可对它的目标函数成-1, 然后按最大化线性规划问题进行求解。
方法二 我们对求解最大化线性规划问题的单纯形法略作修改, 就可获得求解最小化线性规划问题的单纯形法。修改第二步:计算单纯形表的sac 和imp 行, 选择imp j 0, j ∈N , 对应单纯形表上的基可行解就是最小化线性规划问题的最优解。这是因为增加非基变量的值只能能够使目标函数值增大。在对问题(2. 21) 直接引进松弛变量x 3, x 4之后, 我们可获得其初始单纯形表(参见表2. 10) : 表2. 10: 例2. 2初始单纯形表-方法二
因为对应于非基变量x 2的检验数为imp 2=-3, 选择x 2为换入变量, 换出比例说明x 3为换出变量, 迭代后的单纯形表参见表2. 11:
2. 112. 2因为非基变量对应的检验数imp 1和imp 3都大于0, 所以表2. 11是例2. 2的最优单纯形表。那么, 问题(2. 21) 的最优解为:x 2=2, x 4=8, x 1=0
, x 3=0, =-6。
2. 3. 3多重最优解
我们将说明如何利用单纯形法确定一个线性规划问题是否存在多重最优解。我们在1. 4
节中利用图解法说明当电视机生产问题的目标函数为η=100x A +300x B 时的线性规划具有多重最优解。
例2. 3 重新考虑电视机生产的线性规划问题:
max η=100x A +300x B
⎧2x A +x B ≤40⎪x +3x ≤45⎪A B
s . t . ⎨ (2. 23)
⎪x A ≤12⎪⎩x A , x B ≥0
对问题(2. 23) 引进松弛变量s 1, s 2, 和s 3之后, 我们获得初始单纯形(参见表2. 12)
因为在检验行中, imp B =300具有最大值, 所以选择非基变量x B 为换入变量, 比例值表明s 2为换出变量, 进行迭代后, 获得一新单纯形表(参见表2. 13): 表2. 13: 例2. 3最优单纯形表一
因为对应于非基变量x A 和s 2的检验数imp A 和imp 2均不大于0, 表2. 13是例2. 3的最优单纯形表, 最优解为:x A =0, x B =15, s 1=25, s 2=0, s 3=12, =4500。然而, 在最优单纯形表中, 非基变量x A 的检验数im p A 等于0, 如果选择x A 为换入变量, 对应的比例值为
{15, 45, 12}, 则s 3为换出变量, 迭代后的单纯形表(参见表2. 14) 为:
表2. 14: 例2. 3最优单纯形表二
因为对应于非基变量s 2和s 3的检验数im p A 和imp 2均不大于0, 表2. 14是例2. 3的另一个最优单纯形表, 最优解为:x A =11, x B =12, s 1=5, s 2=0, s 3=0, =4500。
由于基可行解对应可行域的一个顶点, 那么我们可以说明连接上述两个最优顶点线段上的所有点都是例2. 3的最优解。为此, 我们设:
1
⎡x 12⎤⎡11⎤⎡x 1⎤⎡0⎤2
最优顶点1:x =⎢1⎥=⎢⎥ 最优顶点1:x =⎢2⎥=⎢⎥
⎣x 2⎦⎣12⎦⎣x 2⎦⎣15⎦
1
那么, 对于任意0≤δ≤1,
x =⎢
⎡x 1⎤⎡0⎤⎡12⎤⎡12-12δ⎤
=δ⎢⎥+(1-δ) ⎢⎥=⎢⎥⎥
⎣15⎦⎣11⎦⎣11+4δ⎦⎣x 2⎦
也都是例2. 3的最优解。比如, 选择δ=0. 5, 我们获得一最优解x A =6, x B =13, =4500。
2. 3. 4 无界解
我们在2. 2节中讨论了判断标准最大化线性规划问题(1. 5) 是无界的条件, 即:对于可行解, 如果存在某个k ∈
N 使k >0, 并且对任意i ∈B , 都有ik ≤0。在本节中, 我们将讨论如何利用单纯形来判断线性规划问题(1. 5) 是无界的。 例2. 4考虑下述线性规划问题:
max η=36x 1+30x 2-3x 3-4x 4
⎧x 1+x 2-x 3≤5⎪
s . t . ⎨6x 1+5x 2-x 4≤10
⎪x , x , x , x ≥0⎩1234
(2. 24)
对问题(2. 24) 引进松弛变量x 5和x 6后, 获其初始单纯形表(参见2. 15):
因为对应非基变量的检验数中绝对值最大的为imp 1=36, 选择x 1为换入变量。比例值表明
x 6为换出变量。迭代后的新单纯形表(参见表2. 16) 为:
表2. 16: 例2. 4的第二张单纯形表
选择非基变量x 4作为换入变量, 比例值说明x 5为换出变量。迭代后的新单纯形表(参见表
2. 17) 为:
表2. 17: 例2. 4的第三张单纯形表
选择非基变量x 3作为换入变量, 保持其他非基变量x 2, x 5, 和x 6为0, 基变量x 1, x 4与x 3的关系为：
x 1=5+x 3 x 4=20+6x 3
将它们代入问题(2. 24) 的目标函数中, 则有：
η=100+12x 3
当x 3的取值不断增大时, 比如x 3=1000, x 1=1005, x 2=0, x 4=6020, 目标值也不断增大, 等于η=12010, 所以线性规划问题(2. 24) 无界。
2. 3. 5 根据检验数确定目标函数系数
在2. 2节中, 我们讨论了线性规划在若干次迭代之后的单纯形：
η=+∑j x j
j ∈N
x i =i -
∑j ∈N
ij
x j i ∈B , j ∈N
那么根据式中的检验数系数j , i , 和ij , 我们应当能够计算原问题目标函数的系数c j , 并将它转换成单纯形表。
例2. 5 考虑下述单纯形:
η=3+x 3-x 1
x 2=10+2x 3-3x 1
(2. 25)
x 4=7+0x 3-4x 1
x 5=0+0x 3+x 1
因为基变量下标集为{2, 4, 5}, 非变量下标集为{1, 3}, 我们可判断出决策变量为n =2，约束条件为m =3，c 3=c 4=c 5=0，需要求出c 1和c 2。由于1=-1, 3=1, =5,
⎡2⎤⎡10⎤⎡a 21⎤⎡3⎤⎡a 23⎤⎡-2⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥
⎢4⎥=⎢7⎥, ⎢a 41⎥=⎢4⎥, ⎢a 43⎥=⎢0⎥，而根据式(2. 18) 非基变量x 3的检验数为： ⎢5⎥⎢⎣a 51⎥⎦⎢⎣-1⎥⎦⎢⎣a 53⎥⎦⎢⎣0⎥⎦⎦⎢⎣⎦⎣0⎥
1=c 3-[c 2
⎡-2⎤
⎥=0+2c
00]⎢02⎢⎥
⎢⎣0⎥⎦
那么, c 2=
1
非基变量x 1的检验数为： 2
-1=c 1-[c 2
⎡3⎤
⎥=c -3c
00]⎢412⎢⎥
⎢⎣-1⎥⎦
1
, 而对应单纯形(2. 25) 的单纯形表为(参见2. 18)
2
则, c 1=