对偶理论1（运筹学）课件.ppt

《对偶理论1（运筹学）课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§1.7LP的对偶理论1.7.1对偶问题例12加工能力(小时/天)A2212B128C4016D041223销售收入产品设备1设X1，X2为产品1，2的产量2X1+2X212X1+2X284X1164X212X1X20maxZ=2X1+3X2221212X1840X2160412(23)X1X22设y1,y2,y3,y4分别为A,B,C,D设备的单价2y1+y2+4y322y1+2y2+443y1…y4021402204y1y2y3y423minW=12y1+8y2+16y3+12y43(y1y2y3y4)22124004(2,3)minW=12y1+8y

2、2+16y3+12y4y1…y4“影子价格”4“对称型”定义：对偶问题minW=ybyACy0A矩阵y,C行向量b列向量minW=bTyATyCTy0A矩阵y,b列向量C行向量maxZ=CXAXbX0A矩阵X,b列向量C行向量原问题5对偶问题的性质：(1)、对偶问题的对偶问题是原问题。(2)、maxZ=CXAX=bX0的对偶问题是6例1、写出下面问题的对偶规划maxZ=5X1+6X23X1-2X2=74X1+X29X1,X207解：3X1-2X273X1-2X274X1+X29maxZ=5X1+6X23X1-2X27-3X1+2X2-74X1+X2

3、9X1,X20y1'y1"y28对偶问题令y1=y1'-y1"3y1'-3y1"+4y25-2y1'+2y1"+y26y1',y1",y20minW=7y1'-7y1"+9y2minW=7y1+9y23y1+4y25-2y1+y26y1自由,y209对偶问题的性质：(1)、对偶问题的对偶问题是原问题。(2)、maxZ=CXAX=bX0的对偶问题是minW=ybyACy为自由10(3)、原问题第k个约束为等式，对偶问题第k个变量是自由变量。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。11对偶关系对应表原问题对偶问题目标函数类型maxmin目标函数

4、系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与0对偶问题约束类型变量0约束的对应关系无限制＝原问题约束类型与0对偶问题变量类型约束变量0的对应关系＝无限制12例2、写对偶规划minZ=4X1+2X2-3X3-X1+2X262X1+3X39X1+5X2-2X3=4X2,X3013maxW=6y1+9y2+4y3-y1+2y2+y3=42y1+5y323y2-2y3-3y10,y20,y3自由14minZ=4X1+2X2-3X3X1-2X2-62X1+3X3

5、9X1+5X2-2X3=4X2,X30或将原问题变形为15maxW=-6y1+9y2+4y3y1+2y2+y3=4-2y1+5y323y2-2y3-3y1,y20,y3自由对偶规划16产品A，B产量X1，X2，Z为利润例1、3X1+X2+X3=483X1+4X2+X4=120X1…X40maxZ=5X1+6X23X1+X2483X1+4X2120X1,X20机器台时劳动工时17X=(8,24)TZ=184183y1+3y25y1+4y26minW=48y1+120y23y1+3y2-y3+y5=5y1+4y2-y4+y6=6minW=48y1+120y2+M

6、y5+My619y=(2/9,13/9),Z=18420观察结论:①一对对偶问题都有最优解，且目标函数值相等。②最优表中有两个问题的最优解。21