运筹学：C8对偶问题的提出

1、运筹学线性规划与目标规划第二章 对偶问题与灵敏度分析Duality Theory and Sensitivity Analysis上节内容回顾上节内容回顾m ax 0zA XbXC Xm a x 0 0 ,0ssszC XXA XIXbXXXSXAI1Ib1BCCIAC10BBCCII0SCbBXNXSX1B BI1BBCC BB1B N1NBCC B N11B IB10BC B I1Bb1BCBb1NNBCC B N10jB P111:min0ilkikiB bxB PB P1BC B b1B为单纯形法中关键的因素！111012BBB如何求每步迭代中基变量对应的基矩阵的逆矩阵、？100,;B

2、IBI易得12EE 如何求、？11110;BE B11221BE B本节内容摘要本节内容摘要产品产品I产品产品II供应量供应量设设 备备原材料原材料A原材料原材料利 润润23现工厂决策者决定不生产产品，而将其所有资源出租或现工厂决策者决定不生产产品，而将其所有资源出租或出售，应如何给每种资源定价？出售，应如何给每种资源定价？设y1，y2和y3分别表示出租单位设备台时的租金和出让单位原材料A，B的价格。则有：1242yy13243yy12381612yyy123,0y yy min1242yy13243yy12381612yyy123,0y yy 1228xx14 16

3、x2412x 1223zxxmax12,0 x x . .stmax0zCXAXbXmin0YbYACYmin产品产品I产品产品II供应量供应量设设 备备原材料原材料A原材料原材料利 润润2310BCC B A(P) max . .0zCXAXbstX(D) min . .0YbYACs tY1BYC B0Y YACYbz1BzC B b10BC B1228xx14 16x2412x 1223zxxmax12,0 x x . .st124004A2,3C 81612b1238min,1612y yy12312,402304yyy0Y 1242yy13243yy123m

4、in81612yyy123,0y yy min0YbYACYmax0zCXAXbX每一个线性规划（每一个线性规划（ LP ）必然有与之相伴而生的另一）必然有与之相伴而生的另一个线性规划问题，即任何一个求个线性规划问题，即任何一个求 maxZ 的的LP都有一都有一个求个求 minZ 的的LP。其中的一个问题叫。其中的一个问题叫“原问题原问题”，记为记为“P”，另一个称为，另一个称为“对偶问题对偶问题”，记为，记为“D”。本节内容摘要本节内容摘要1242yy13243yy123min81612yyy123,0y yy 1228xx14 16x2412x 1223zxxmax12,0 x x iyj

5、x12nxxx12myyy111212122212nnmmmnaaaaaaaaa12nccc123bbbmaxminzminmax z 注意：以后不强调等式右端项注意：以后不强调等式右端项 b b00，b b可以是负数。可以是负数。故对于约束为故对于约束为的情形可以先乘以的情形可以先乘以1 1变为变为再按照对再按照对称形式的变换关系进行变换称形式的变换关系进行变换. .对偶模型的一般式对偶模型的一般式max. .0zCXAXbstX(P)上对偶模型称为对称式对偶模型。二者间有对称的对应关系：上对偶模型称为对称式对偶模型。二者间有对称的对应关系： 原问题（原问题（P P） 对偶问题对偶问题 （D

6、 D） 目标目标max型型 目标目标min型型 有有n个变量（非负）个变量（非负） 有有n个约束（大于等于）个约束（大于等于） 有有m个约束个约束 （小于等于）（小于等于） 有有m个变量（非负）个变量（非负） 价格系数价格系数 资源向量资源向量 资源向量资源向量 价格系数价格系数 技术系数矩阵技术系数矩阵 技术系数矩阵的转置技术系数矩阵的转置 min. .0YbYACs tY(D)非对称形式（即原问题约束条件中含有等式非对称形式（即原问题约束条件中含有等式约束、原问题的变量无非负约束）怎样求其约束、原问题的变量无非负约束）怎样求其对偶问题？对偶问题？2、非对称型对偶问题、非对称型对偶问题123

7、4123412412341234P max235 4 325 32 74 2 34 60,0,Zxxxxxxxxxxxxxxxxxxx无约束12312312313123123D min 5464322 233 3 +452710,0,yyyyyyyyyyyyyyyyy 无约束大约变，小相反，实例参考定价与生产！大约变，小相反，实例参考定价与生产！(P) max . .0zCXAXbstX(D) min . .0YbYACs tY练习练习1：求下面线性规划问题的对偶问题：求下面线性规划问题的对偶问题1231213123123123P max 4562 =1 5 327420,0,yyyyyyyy

8、yyyyyyyy 无约束123412341342341234D min572 3 42 245 6 00Zxxxxxxxxxxxxxxx, xx,x无约束、练习练习2：求下面线性规划问题的对偶问题：求下面线性规划问题的对偶问题123412341342341234P min572 3 42 245 6 00Zxxxxxxxxxxxxxxx, xx,x无约束、1231213123123123D max 4562 =1 5 327420,0,yyyyyyyyyyyyyyyy 无约束123412341342341234D min572 3 42 245 6 00Zxxxxxxxxxxxxxxx, xx,x无约束、1231213123123123P max 4562 =1 5 327420,0,yyyyyyyyyyyyyyyy 无