2第二章 线性规划与单纯形法(第7节)

第20页 页
人工变量目标函数系数设置的原因： 人工变量目标函数系数设置的原因：
使人工变量在迭代过程中尽快从基变量中被换出。 使人工变量在迭代过程中尽快从基变量中被换出。 注意： 注意： 最终单纯形表中，如果基变量中有非零的人工变量 最终单纯形表中， 如果基变量中有非零的人工变量 ，则问题无可行解。 则问题无可行解。
cm +1 −
cm+1 xm+1 a1, m+1 a2, m+1 … am, m+1
… … … … … … …
cn xn a1n a2n … amn
θi θ1 θ2 … θm
∑ca
i i=1
m
i ,m + 1
cn −
∑ca
i i=1
m
i ,n
第6页 页
例：
max z = 2x1 + 3x2
s .t .
第23页 页
cj CB 0 -M -M XB x4 x6 x7 c j– z j 0 -M -1 x4 x6 x3 c j– z j 10 1 1 b 11 3 1
3 x1 1 -4 -2
3-6M
-1 x2 -2 1 0
M-1
-1 x3 1 2 [1]
3M-1
0 x4 1 0 0 0 1 0 0 0
第21页 页
例：
min z = −3 x1 + x
2
+ x
3
x1 − 2 x2 + x 3 ≤ 11 − 4 x1 + x2 + 2 x3 ≥ 3 x3 = 1 − 2 x1 + x1, x2, x3 ≥ 0
第22页 页
解：加入 松弛变量： 松弛变量： x4 剩余变量： 剩余变量： x5 人工变量： 人工变量： x6 和 x7 得到： 得到：
第2页 页
（3）在 σj > 0 ，j = m+1, .. , n 中，若某个非基变量 ） xj 的系数列向量 Pk ≤0，则此问题无界，停止计算，否 ，则此问题无界，停止计算， 则转下步； 则转下步； （4）根据 ）根据max( σj > 0 ) = σk，来确定 xk 为换入变量 （最大检验数有多个时，可任选一个）； 最大检验数有多个时，可任选一个）
第七节 单纯形法的应用
一、单纯形法的计算步骤
步骤： 步骤： （1）找出初始基可行解； ）找出初始基可行解； （2）检验各非基变量的检验数： σ j = c j − ）检验各非基变量的检验数：
∑c a
i i =1
m
ij
如果σ 如果 j ≤ 0，j = m+1, .. , n ，则当前解就是最优解 ， ，停止计算： 停止计算：
x 1 + 2 x 2 ≤ 8 ≤ 16 4 x 1 4 x 2 ≤ 12 x 1 , x 2 ≥ 0
第7页 页
解：（1）将模型转化为标准型，得到初始单纯形表 ）将模型转化为标准型，
cj CB 0 0 0 XB x3 x4 x5 c j– z j b 8 16 12 2 x1 1 4 0 2 3 x2 2 0 [4] 3 0 x3 1 0 0 0 0 x4 0 1 0 0 0 θi x5 0 0 1 0 4 3
第12页 页
引入剩余变量化为标准型， 引入剩余变量化为标准型，但无法直接得到初始可 行基： 行基：
= b1 a11 x1 + a12 x 2 + ... + a1 n x n − x n + 1 ... − x n + m = bm a m 1 x1 + a m 2 x 2 + ... + a mn x n x1 , ... , x n , x n + 1 ,... , x n + m ≥ 0
第16页 页
3. 当约束条件中有 、≥ = 时，要直接凑出初始可行 当约束条件中有≤、 基： 的不等式直接加上一个松弛变量； （1）≤的不等式直接加上一个松弛变量； ） 的不等式直接加上一个松弛变量 的不等式减去一个剩余变量， （ 2）≥的不等式减去一个剩余变量， 再加上一个人 ） 的不等式减去一个剩余变量 工变量； 工变量； （3）等式直接加上一个人工变量。 ）等式直接加上一个人工变量。
造仅含人工变量的目标函数。 造仅含人工变量的目标函数。
第26页 页
max z = c 1 x 1 + c 2 x 2 + ... + c n x n a 11 x 1 + a 12 x 2 + ... + a 1 n x n = b1 ... a m 1 x 1 + a m 2 x 2 + ... + a mn x n = b m x 1 , ... , x n ≥ 0
第19页 页
1. 大 M 法 人工变量为虚拟变量， 人工变量为虚拟变量 ， 完全是为了凑出初始可行 基而引入， 基而引入 ， 所以在目标函数中人工变量的系数应 符合如下规则： 符合如下规则： （1）目标函数为极大化：很大的负数（ - M ） ）目标函数为极大化：很大的负数（ （2）目标函数为极小化：很大的正数（ M ） ）目标函数为极小化：很大的正数（
第1页 页
如果σ 如果 j < 0，j = m+1, .. , n ，则当前解为唯一最优 ， 解；
如果有{σj ，j = m+1, .. , n }中有 j = 0，则当前最优解。 是最优解，但不唯一，问题有无穷多最优解。 否则 ，转下步； 转下步；
松弛变量 剩余变量
+ ... + a 1 n x n + x n + 1 + ... + a 2 n x n + ... + a 3 n x n , xn ≥ 0 − x n+ 2 + x n+ 3 + x n+4
人工变量
= b1 = b2 = b3
第18页 页
1. 大 M 法
有人工变量引入时的求解方法 2. 两阶段法
3 x1 [3] 0 -2 1 1 0 0 0
-1 x2 0 1 0 0 0 1 0 0
-1 x3 0 0 1 0 0 0 1 0
0 x4 1 0 0 0 1/3 0 2/3
0 x5 -2 -1 0 -1 -2/3 -1 -4/3
-M x6 2 1 0
1-M
-M x7 -5 -2 1
-1-M
θi 4 -
第9页 页
2 4 -
（3）x1 为换入变量，x3 为换出变量，进行旋转运算， ） 为换入变量， 为换出变量，进行旋转运算， 得到新的单纯形表： 得到新的单纯形表：
cj CB 2 0 3 XB x1 x4 x2 c j– z j b 2 8 3 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 1 -4 0 -2 0 x4 0 1 0 0 0 θi x5 -1/2 [2] 1/4 1/4
max z = 3 x 1 − x 2 − x 3 + 0 x 4 + 0 x 5 − Mx 6 − Mx 7 x1 − 2 x 2 + x 3 + x 4 = 11 − x5 + x6 = 3 − 4 x1 + x 2 + 2 x 3 x3 + x7 = 1 − 2 x1 + x1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ≥ 0
0 x5 0 -1 0
-M
-M x6 0 1 0 0 0 1 0 0
-M x7 0 0 1 0 -1 -2 1
1-3M
第24页 页
θi 11 3/2 1
3 0 -2 1
-2 [1] 0
M-1
0 0 1 0
0 -1 0
-M
1 -
cj CB 0 -1 -1 XB x4 x2 x3 c j– z j 3 -1 -1 x1 x2 x3 c j– z j 4 1 9 b 12 1 1
第4页 页
（6）以 al ）
k
为主元素进行旋转运算， 为主元素进行旋转运算，从而得到一个
新的基可行解。 新的基可行解。
（7） 重复（2）~（6），直到找到问题的最优解。 ） 重复（ ） （ ） 直到找到问题的最优解。
第5页 页
二、单纯形表的设计
cj CB c1 c2 … cm XB x1 x2 … xm c j– z j b b1 b2 … bm c1 x1 1 0 … 0 0 … … … … … … … cm xm 0 0 … 1 0
2/3 1 4/3
-5/3 -2 -7/3
第25页 页
-1/3 -1/3
1/3-M 2/3-M
问题的最优解： 问题的最优解： X = ( x1 , x2 , x3 ) = ( 4, 1, 9 ) T 2. 两阶段法 第一阶段：给原线性规划问题加入人工变量， 第一阶段 ：给原线性规划问题加入人工变量， 并构
第10页 页
4 12
（4）x5 为换入变量，x4 为换出变量，进行旋转运算， ） 为换入变量， 为换出变量，进行旋转运算， 得到新的单纯形表： 得到新的单纯形表：
cj CB 2 0 3 XB x1 x5 x2 c j– z j b 4 4 2 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 0 -2 1/2 -3/2 0 x4 1/4 1/2 -1/8 -1/8 0 θi x5 0 1 0 0
这些新变量无实际含义， 这些新变量无实际含义，完全是为了凑出初始可行 基以便于运算，称为人工变量。 基以便于运算，称为人工变量。
第14页 页
2. 当约束条件不等式为 = 时，也无法直接得出一个 初始可行基， 初始可行基，也可采取引入人工变量的方法凑出一 个初始可行基： 个初始可行基：