运筹学全套课件.pptxVIP

第二章 对偶理论与灵敏度分析§1 单纯形法的矩阵描述 设max z = CX AX = b X ≥ 0 A为m×n阶矩阵 RankA=m ,取B为可行基, N为非基， 求解步骤：§2 对偶问题的提出 [eg.1]制定生产计划 M1: max z = 2x1 + 3x2 1x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1，x2 ≥ 0 ⅠⅡ限制 设备台时128台时 材料A4016kg材料B0412kg利润23 ⅠⅡ限制 设备台时128台时 M2: min w = 8y1 + 16y2 + 12y3 y1 + 4y2 ≥ 2 2y1 + 4y3 ≥ 3 y1,y2,y3 ≥ 0材料A4016kg材料B0412kg利润23 现在出租，设y1为设备单位台时的租金 y2,y3为材料A、B转让附加费(kg-1) 则M2为M1的对偶问题，反之亦然。 一般的，原问题：max z = CX AX ≤ b X ≥ 0 对偶问题：min w = Yb YA ≥ C Y ≥ 0 比较：max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “≤” “≥”对偶：min w = 6y1 + 8y2 2y1 ≥ 1 y1 + 2y2 ≥ 2 y2 ≥ 1 y1,y2 ≥ 0§3 对偶问题的化法 1、典型情况 [eg.2]max z = x1 + 2x2 + x3 2x1 + x2 ≤ 6 2x2 + x3 ≤ 8 x1,x2,x3 ≥ 0 2x1 + x2 + 3x3 ≤ 3-2x1 - x2 - 3x3 ≤-3令y1=y1’-y1”,则： min w = 3y1+4y2 2y1 + y2 ≥ 1 y1 +2y2 ≥ 2 3y1 +5y2 ≥ 4 y2 ≥ 0，y1无约束对偶：min w = 3y1’-3y1”+4y2 2y1’-2y1”+ y2 ≥ 1 y1’- y1”+2y2 ≥ 2 3y1’-3y1”+5y2 ≥ 4 y1’,y1”,y2 ≥ 0 2、含等式的情况 [eg.3]max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 ≤ 4 x1,x2,x3 ≥ 0一般，原问题第i个约束取等式，对偶问题第i个变量无约束。-2x1 - x2 - 3x3 ≤-3对偶：min w = -3y1’ + 4y2 -2y1’ + y2 ≥ 1 -y1’ + 2y2 ≥ 2 -3y1’ + 5y2 ≥ 4 y1’,y2 ≥ 0令y1 = -y1’，则： min w = 3y1 + 4y2 2y1 + y2 ≥ 1 y1 + 2y2 ≥ 2 3y1 + 5y2 ≥ 4 y1 ≤ 0,y2 ≥ 0 3、含“≥”的max问题 [eg.4]max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 ≥ 3 x1 + 2x2 + 5x3 ≤ 4 x1,x2,x3 ≥ 0一般:① max问题第i个约束取“≥”，则min问题第i个变量 ≤ 0 ；② min问题第i个约束取“≤”，则max问题第i个变量 ≤ 0 ；③ 原问题第i个约束取等式，对偶问题第i个变量 无约束；④ max问题第j个变量 ≤ 0 ,则min问题第j个约束取“≤” ；⑤ min问题第j个变量 ≤ 0 ，则max问题第j个约束取“≥” ；⑥ 原问题第j个变量无约束，对偶问题第j个约束取等式。对偶：max w = 5y1 + 4y2 + 6y3 y1 + y2 ≥ 2 y1 + y3 ≤ 3 -3y1 + 2y2 + y3 ≤ -5 y1 - y2 + y3 = 1 y1 ≥ 0,y2 ≤ 0,y3无约束 [eg.5]min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 ≥ 5 2x1 + 2x3 - x4 ≤ 4 x2 + x3 + x4 = 6 x1 ≤ 0,x2,x3 ≥ 0,x4无约束§4 对偶问题的性质 1、对称性 对偶问题的对偶为原问题.推论：(1) max问题任一可解的目标值为min问题目标值的一个下界；(2) min问题任一可解的目标值为max问题目标值的一个上界。3、无界性 若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。 4、最优性 设X*，Y*分别为原问题和对偶问题可行解，当 CX*=Y*b时， X*，Y*分别为最优解。 5