第二章:对偶问题(1) 对偶单纯形法 2.对偶单纯形法计算步骤 第一步:先定行,负中取小 第二步:再定列,相除后 正 中取 XB XN B-1b XB X 1 b 存在负数 先定行: 负中取小 非正 再定列: 正中取 运学 狼中教授
运筹学 熊中楷教授 对偶单纯形法 2. 对偶单纯形法计算步骤 第一步：先定行，负中取小 第二步：再定列，相除后 正 中取小 XB XN B-1 b 存在负数 非正 第二章：对偶问题（1） XB XN B-1 b 先定行： 负中取小 再定列： 正中取 小
第二章:对偶问题(1) 例:试用对偶单纯形法求解线性规划问题 Minix, + 2x1+x,>4 X1+7x27 x2=0 解:变换问题形式为:(没有人工变量,出现单位矩阵) Max(z=-X,-X2 -2x1-x2+x3=-4右边有负数 7x,+x:=-7右边有负数 运学 狼中教授
运筹学 熊中楷教授 例： 试用对偶单纯形法求解线性规划问题 Min Z=x1+x2 2x1+x2 ≥4 x1+7x2 ≥7 x1 , x2 ≥0 解: 变换问题形式为: （没有人工变量, 出现单位矩阵） Max(-z)= - x1 - x2 -2x1 -x2+x3 = -4 右边有负数 -x1 - 7x2 +x4 = -7 右边有负数 x1 , x2 ≥0 第二章：对偶问题（1）
第二章:对偶问题(1) 2 0 70 对偶单纯 0 先定行, 负中取小 再定列, 相除后正 中取小 -1370 1/7-3 下一步 转轴元所 1/71 0 1/71 在列变为 单位向量 670 0 运学 狼中教授
运筹学 熊中楷教授 x1 x2 x3 x4 x5 -2 -1 1 0 -4 x4 -1 -7 0 1 -7 -1 -1 0 0 X1 X2 X3 X4 X3 -13/7 0 1 -1/7 -3 X2 1/7 1 0 -1/7 1 -6/7 0 0 -1/7 1 第二章：对偶问题（1） 对偶单纯 形法: 先定行， 负中取小 再定列， 相除后正 中取小 下一步： 转轴元所 在列变为 单位向量
对偶单纯形法: 第二章:对偶问题(1)/先定行,负中取小 无法进行,表示最优解达 X 0 7/31/1321/13 1/13 2/13 10/13 0 6/13 X331/13 最优解为x*=(21,10,0,0)(x3x是松弛变量) Z*=31/13 对偶解Y*=(613,113)r只有两种资源(两个约束) W*=31/13 松弛变量检验数对应对偶解-Y 运学 中数
运筹学 熊中楷教授 X1 X2 X3 X1 1 0 -7/13 1/13 21/13 X2 0 1 1/13 -2/13 10/13 0 0 -6/13 - 1/13 31/13 最优解为 x*＝(21/13, 10/13, 0, 0 )T (X3 X4 是松弛变量) Z*=31/13 对偶解 Y*＝(6/13, 1/13 ) T 只有两种资源（两个约束） W*=31/13 第二章：对偶问题（1） 松弛变量检验数 对应对偶解－Y X4 对偶单纯形法: 先定行，负中取小 无法进行，表示最优解达 到
第二章:对偶问题(1) 对偶单纯形法 3优缺点 优点(1)初始解可以是非可行解,不需要加入人工变量 (2)适合于XB少,X很多的情况 对偶转换 XN多 多 XB少 (3)敏度分析,有时可简化分析 缺点初始可行基难找 狼中教
运筹学 熊中楷教授 对偶单纯形法 3.优缺点 优点 （1）初始解可以是非可行解，不需要加入人工变量 （2）适合于XB少，XN很多的情况 对偶转换 （3）灵敏度分析，有时可简化分析 缺点 初始可行基难找 XN 少 XB 多 XN多 XB少 第二章：对偶问题（1）