运筹学 第一章 (第三版) 线性规划 与单纯性 法 《运筹学》教材编写组编 第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为任意大的正 数)， • 这样目标函数要实现最大化时，必须把 人工变量从基变量换出。否则目标函数 不可能实现最大化