1、第二章第二章 对偶理论与灵敏度分析1 单纯形法的矩阵描述设 max z = CXAX = bX 0A为 m n阶矩阵 RankA=m ,取 B为可行基 , N为非基， 123 求解步骤：432利润12kg40材料 B16kg04材料 A8台时 21设备台时限制 2 对偶问题的提出eg.1制定生产计划M1: max z = 2x1 + 3x21x1 + 2x2 84x1 164x2 12x1， x2 0 5现在出租，设 y1为设备单位台时的租金y2,y3为材料 A、 B转让附加费 (kg-1) 则 M2为 M1的对偶问题，反之亦然。M2: min w = 8y1 + 16y2 + 12y3y1
2、+ 4y2 22y1 + 4y3 3y1,y2,y3 0 32利润 12kg40材料 B16kg04材料 A8台时 21设备台时限制 6一般的，原问题： max z = CX AX b X 0对偶问题： min w = Yb YA C Y 0比较： max z min w决策变量为 n个 约束条件为 n个约束条件为 m个 决策变量为 m个“” “”73 对偶问题的化法1、 典型情况eg.2max z = x1 + 2x2 + x32x1 + x2 62x2 + x3 8x1,x2,x3 0对偶： min w = 6y1 + 8y22y1 1y1 + 2y2 2y2 1y1,y2 082、含等式
3、的情况eg.3max z = x1 + 2x2 + 4x32x1 + x2 + 3x3 = 3x1 + 2x2 + 5x3 4x1,x2,x3 0对偶： min w = 3y1 -3y1” +4y22y1 -2y1” + y2 1y1 - y1” +2y2 23y1 -3y1” +5y2 4y1 ,y1” ,y2 0令 y1=y1-y 1”, 则：min w = 3y1+4y22y1 + y2 1y1 +2y2 23y1 +5y2 4y2 0， y1无约束一般，原问题第 i个约束取等式，对偶问题第 i个变量无约束。2x1 + x2 + 3x3 3-2x1 - x2 - 3x3 -393、含 “ ” 的 max问题eg.4max z = x1 + 2x2 + 4x32x1 + x2 + 3x3 3x1 + 2x2 + 5x3 4x1,x2,x3 0对偶： min w = -3y1 + 4y2-2y1 + y2 1-y1 + 2y2 2-3y1 + 5y2 4y1 ,y2 0令 y1 = -y1 ， 则：min w = 3y1 + 4y22y1 + y2 1y1 + 2y2 23y1 + 5y2 4y1 0,y2 0-2x1 - x2 - 3x3 -310
