第二章对偶理论与灵敏度分析ppt课件.ppt

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

1、第二章对偶理论与灵敏度分析1．线性规划的对偶问题2．对偶问题的基本性质3．影子价格4．对偶单纯形法5．灵敏度分析1．线性规划的对偶问题1.1对偶问题的提出1.2对称形式下对偶问题的一般形式1.3非对称形式的原－对偶问题关系1.4对偶问题的定义1.5对偶关系对应表例1：美佳公司利用该公司资源生产两种家电产品。项目III每天可用能力设备A（h）设备B（h）调试工序（h）06152115245利润（元）211.1对偶问题的提出1．线性规划的对偶问题现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来，它至

2、少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？显然美佳公司愿出让自己资源的条件是，出让代价应不低于用同等数量资源由自己组织生产活动时获取的盈利。设分别用yl，y2和y3代表单位时间（h）设备A、设备B和调试工序的出让代价。因美佳公司用6小时设备A和l小时调试可生产一件家电I，盈利2元；用5小时设备A，2小时设备B及1小时调试可生产一件家电II，盈利1元。1．线性规划的对偶问题由此y1，y2，y3的取值应满足:该公司希望用最小代价把美佳公司的全部资源收买过来。因此，线性规划模型为：1．线性规

3、划的对偶问题例2写出下列问题的原问题与对偶问题12加工能力(小时/天)A2212B128C4016D041223销售收入产品设备1．线性规划的对偶问题原问题：设x1，x2为产品1，2的产量2x1+2x212x1+2x284x1164x212x1x20maxZ=2X1+3x2221212x1840x2160412(23)x1x21．线性规划的对偶问题对偶问题：设y1,y2,y3,y4分别为A,B,C,D设备的单价2y1+y2+4y322y1+2y2+443y1…y4021402204y1y2y

4、3y423(y1y2y3y4)1281612minW=12y1+8y2+16y3+12y4y1…y4“影子价格”1．线性规划的对偶问题对称的含义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，当目标函数求极小时均取“”号。对称形式下线性规划原问题的一般形式为：maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxnb1a21x1+a22x2+…+a2nxnb2………am1x1+am2x2+…+amnxnbmxj0

5、(j=1,…,n)s.t.1.2对称形式下对偶问题的一般形式1．线性规划的对偶问题用yi(i＝1，…m)代表第i种资源的估价，则其对偶问题的一般形式为：minw=b1y1+b2y2+…+bmyma11y1+a21y2+…+am1ymc1a12y1+a22y2+…+am2ymc2………a1ny1+a2ny2+…+amnymcnXj0(j=1,…,m)s.t.1．线性规划的对偶问题用矩阵形式表示，原问题为:其对偶问题为：1．线性规划的对偶问题原问题与对偶问题的对应关系原问题对偶问题A约束系数矩阵其系数矩阵

6、转置B约束条件右端项向量目标函数价值系数C目标函数价值系数约束条件右端项向量目标函数maxz=CXminw=Y’b约束条件AXbA’YC决策变量X0Y01．线性规划的对偶问题1.3非对称形式的原－对偶问题关系1．线性规划的对偶问题例2写出下述线性规划问题的对偶问题无约束1.3非对称形式的原－对偶问题关系1．线性规划的对偶问题写出其对偶问题为：可变换成具有如下对称形式的线性规划问题1.3非对称形式的原－对偶问题关系1．线性规划的对偶问题进行整理为：无约束例3写出下述线性规划问题的对偶问题1.3非对称形式

7、的原－对偶问题关系maxZ=5X1+6X23X1-2X2=74X1+X29X1,X201．线性规划的对偶问题解：原问题可化为maxZ=5X1+6X23X1-2X27-3X1+2X2-74X1+X29X1,X20y1'y1"y2则对偶问题：3y1'-3y1"+4y25-2y1'+2y1"+y26y1',y1",y20minW=7y1'-7y1"+9y21．线性规划的对偶问题令y1=y1'-y1"minW=7y1+9y23y1+4y25-2y1+y26y1自由,y201．线性规划的对偶问题

8、1.4对偶的关系原始问题maxz=CTXs.t.AX≤bX≥0对偶问题miny=bTWs.t.ATW≥CW≥0CATbT≥minmn≤maxbACTmn1．线性规划的对偶问题原问题对偶问题目标函数类型maxmin目标函数系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与0对偶问题约束类型变量0约束的对应关