第二章对偶问题与灵敏度分析

《第二章对偶问题与灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章：对偶问题与灵敏度分析第一部分：§3，§4，§5，§6第二部分：§7，§81第二章：第一部分LP的对偶理论1.7.1对偶问题例12加工能力(小时/天)A2212B128C4016D041223销售收入产品设备2设X1，X2为产品1，2的产量2X1+2X212X1+2X284X1164X212X1X20maxZ=2X1+3X2221212X1840X2160412(23)X1X23设y1,y2,y3,y4分别为A,B,C,D设备的单价2y1+y2+4y322y1+2y2+443y1…y4021402204y1y2y3y4234

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

3、3X1-2X273X1-2X274X1+X29maxZ=5X1+6X23X1-2X27-3X1+2X2-74X1+X29X1,X20y1'y1"y29对偶问题令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010(3)、原问题第k个约束为等式，对偶问题第k个变量是自由变量。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。11对偶关系对应表原问题对偶问题目标函

4、数类型maxmin目标函数系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数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=4

5、X1+2X2-3X3X1-2X2-62X1+3X3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=1845600X1X2X3X4XB056000X34831100X41203(4)0

6、11801/200-3/20X318(9/4)01-1/46X2303/4101/418400-2/9-13/95X18104/9-1/96X22401-1/31/3183y1+3y25y1+4y26minW=48y1+120y23y1+3y2-y3+y5=5y1+4y2-y4+y6=6minW=48y1+120y2+My5+My6194812000MMy1y2y3y4y5y6yB11M48-4M120-7MMM00My5533-1010My66140-101yB180+1/2M18-9/4M0M30-3/4M0-30+7/4MMy51/29/4

7、0-13/41-3/4120y23/21/410-1/401/4yB18400824M-8M-2448y12/910-4/91/34/9-1/3120y213/9011/9-1/3-1/91/3y=(2/9,13/9),Z=18420观察结论:①一对对偶问题都有最优解，且目标函数值相等。②最优表中有两个问题的最优解。211.7.2对偶问题解的性质maxZ=CXAX≤bX0(P)minW=ybyACy0(D)22定理1、(弱对偶定理)分别为(P),(D)的可行解，则有CbX，yXy证明：由AXb,y0有yAXby由AyC,X0有yAX

8、CX所以CXyAXyb23推论2、(P)有可行解,但无有限最优解，则(D)无可行解。定理2、yX,分别