运筹学 第一章 (第三版) 线性规划 与单纯性 法 《运筹学》教材编写组编 第5节 单纯形法的 进一步讨论 钱颂迪制作 清华大学出版社
运筹学 （第三版） 《运筹学》教材编写组 编 清华大学出版社 第一章 线性规划 与单纯性 法 第5节 单纯形法的 进一步讨论 钱颂迪 制作
第一章线性规划与单纯型法 第5节单纯形法的进一步讨论 51人工变量法 52退化 53检验数的几种表示形式
第一章 线性规划与单纯型法 • 第5节 单纯形法的进一步讨论 • 5.1 人工变量法 • 5.2 退化 • 5.3 检验数的几种表示形式
51人工变量法 设线性规划问题的约束条件∑Px=b 其中没有可作为初始基的单位矩阵,则分别给每一个 约束方程加入人工变量x11,…,x,得到 十C1x)+ 12 aux.+x nn n+1 211+a22x2+…+a2nxn+xn+2 Cm1x1+am2x2+…+al mn n +Xn+m ≥0:x m+1 x≥0 n+m
5.1 人工变量法 • 设线性规划问题的约束条件 • 其中没有可作为初始基的单位矩阵，则分别给每一个 约束方程加入人工变量xn+1,…,xn+m，得到 = = n j Pj x j b 1 + + + + = + + + + = + + + + = + + + + + 1 , , 0; 1 , , 0 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 n m n m m m m n n n m n n n n n n x x x x a x a x a x x b a x a x a x x b a x a x a x x b
单位矩阵。令非基变量3”0零,便可停 以xn1,…,xn-为基变量,并可得到一个m 个初始基可行解X0(0,0,…,0,b,b2…,b)T 因为人工变量是后加入到原约束条件中的虚拟变量, 要求经过基的变换将它们从基变量中逐个替换出来 基变量中不再含有非零的人工变量,这表示原问题 有解。 若在最终表中当所有c;z;≤0,而在其中还有某个非 零人工变量,这表示原问题无可行解。 以下讨论如何解含有人工变量的线性规划问题
以xn+1,…，xn+m为基变量，并可得到一个m×m 单位矩阵。令非基变量x1 ,…,xn为零，便可得到一 个初始基可行解X (0)=(0,0,…,0,b1 ,b2,…,bm ) T • 因为人工变量是后加入到原约束条件中的虚拟变量， 要求经过基的变换将它们从基变量中逐个替换出来。 • 基变量中不再含有非零的人工变量，这表示原问题 有解。 • 若在最终表中当所有cj -zj≤0，而在其中还有某个非 零人工变量，这表示原问题无可行解。 • 以下讨论如何解含有人工变量的线性规划问题
1大M法 在一个线性规划问题的约束条件中加进 人工变量后,要求人工变量对目标函数 取值不受影响;为此假定人工变量在目 标函数中的系数为(-M)M为任意大的正 数) 这样目标函数要实现最大化时,必须把 人工变量从基变量换出。否则目标函数 不可能实现最大化
1 大M法 • 在一个线性规划问题的约束条件中加进 人工变量后，要求人工变量对目标函数 取值不受影响；为此假定人工变量在目 标函数中的系数为(-M)(M为任意大的正 数)， • 这样目标函数要实现最大化时，必须把 人工变量从基变量换出。否则目标函数 不可能实现最大化
例8现有线性规划问题,试用大M法求解。 min z==3xtx tx 1-2x2+x3≤11 4x1+ x2+2x3≥3 2 +x2=1 x,x2,x3≥0
例8 现有线性规划问题，试用大M法求解。 − + = − + + − + = − + + , , 0 2 1 4 2 3 2 11 min 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x z x x x
解在上述问题的约束条件中加入松弛变 量x,剩余变量x5,人工变量x,x7,得到 min 2=-3x+x,+xx+OxA +Oxs+Mxe+mx x1-2x2+x2+x 11 4x1+x2+2x3 Xs+x 2 +x7=1 X1 2,3,14,5X6x7≥0 这里M是一个任意大的正数
解 在上述问题的约束条件中加入松弛变 量x4，剩余变量x5，人工变量x6 ,x7，得到 − + + = − + + − + = − + + = = − + + + + + + , , , , , , 0 2 1 4 2 3 2 11 min 3 0 0 1 2 3 4 5 6 7 1 3 7 1 2 3 5 6 1 2 3 4 1 2 3 4 5 6 7 x x x x x x x x x x x x x x x x x x x z x x x x x Mx Mx 这里M是一个任意大的正数
因本例的目标函数是要求min,所以用所有 Cjzj≥0来判别目标函数是否实现了最小化.用单 纯形法进行计算时,见表1-6。 M B b X2 M 2 03/2 X 0[11000 Ci-Z +6MI-M1-3MOM0O
因本例的目标函数是要求min，所以用所有 cj-zj≥0来判别目标函数是否实现了最小化.用单 纯形法进行计算时，见表1-6。 cj→ -3 1 1 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 θi 0 M M x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 [1] 1 0 0 0 -1 0 0 1 0 0 0 1 11 3/2 1 cj -zj -3+6M 1-M 1-3M 0 M 0 0
在表1-6的最终计算结果表中,表明已得到最优解是: 9 X2=9,ⅩA=X=X 3 0;目标涵数z=2 一 M C X X 2 0 0 Ci-Z 1-M1-3M0 M 03M-1 0 12 0 0 0 0 Ci-zi M-1 M+ X 0 1/3-2/32/3 5/3 2/3-434/3-7/3 Ci-Z 0 /31/3M-1/3M2/3
在表1-6的最终计算结果表中，表明已得到最优解是： x1 =4,x2 =1,x3 =9，x4 =x5 =x6 =x7 =0；目标函数z=-2 cj→ -3 1 1 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 θi 0 M 1 x4 x6 x3 10 1 1 3 0 -2 -2 [1] 0 0 0 1 1 0 0 0 -1 0 0 1 0 -1 -2 1 1 cj -zj -1 1-M 1-3M 0 M 0 3M-1 0 1 1 x4 x2 x3 12 1 1 [3] 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 2 1 0 -5 -2 1 4 cj -zj -1 0 0 0 1 M-1 M+1 -3 1 1 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 2/3 1 4/3 -5/3 -2 -7/3 cj -zj 2 0 0 0 1/3 1/3 M-1/3 M-2/3
两阶段法 以下介绍求解含有人工变量线性规划问 题的两阶段法。 第一阶段:不考虑原问题是否存在基可 解;给原线性规划问题加入人工变量, 并构造仅含人工变量的目标函数和要求 实现最小化
2. 两阶段法 • 以下介绍求解含有人工变量线性规划问 题的两阶段法。 • 第一阶段：不考虑原问题是否存在基可 行解；给原线性规划问题加入人工变量， 并构造仅含人工变量的目标函数和要求 实现最小化