第2章对偶理论和灵敏度分析(精品).ppt
《第2章对偶理论和灵敏度分析(精品).ppt》由会员分享,可在线阅读,更多相关《第2章对偶理论和灵敏度分析(精品).ppt(166页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、(本科版(本科版)运筹学运筹学运筹学教材编写组编清华大学出版社第2章对偶理论和灵敏度分析第1节单纯形法的矩阵描述第2节 改进单纯形法第3节 对偶问题的提出第4节 线性规划的对偶理论第5节 对偶问题的经济解释影子价格第6节 对偶单纯形法第7节 灵敏度分析第8节*参数线性规划单纯形原理的矩阵描述单纯形原理的矩阵描述 设标准的线性规划问题为设标准的线性规划问题为minz=CTXs.t.AX=bX 0矩阵矩阵A可以分块记为可以分块记为A=B,N 相应地,向量相应地,向量X和和C可以记为可以记为AX=b可以写成BXB+NXN=b即XB=B-1b-B-1NXN对于一个确定的基B,目标函数z可以写成目标函数
2、z用非基变量表出的形式单纯形表的结构小结1)掌握矩阵的运算;2)理解基矩阵的作用;3)了解矩阵运算与单纯表的关系。第2章对偶理论和灵敏度分析第2节改进单纯形法改进单纯形主要用于计算机求解时,节省计算量和节约内存占用,一般不在手工计算时采用。由于在单纯形迭代时只有一个变量换入和换出,在相关计算时也设法只计算一列。求解线性规划问题的关键是计算以下介绍一种比较简便的计算方法第2章对偶理论和灵敏度分析第3节对偶问题的提出第3节对偶问题的提出对偶是什么:对同一事物(或问题),从不同的角度(或立场)提出对立的两种不同的表述。例如在平面内,矩形的面积与其周长之间的关系,有两种不同的表述方法。(1)周长一定,
3、面积最大的矩形是正方形。(2)面积一定,周长最短的矩形是正方形。这是互为对偶关系的表述。这种表述有利于加深对事物的认识和理解。线性规划问题也有对偶关系。第1章例1的不同表述现从另一角度来讨论这个问题。假设该工厂的决策者决定不生产产品、,而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1,y2,y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额。他在做定价决策时,做如下比较:若用1个单位设备台时和4个单位原材料A可以生产一件产品,可获利2元,那么生产每件产品的设备台时和原材料出租或出让的所有收入应不低于生产一件产品的利润,这就有y1+4y22同理将
4、生产每件产品的设备台时和原材料出租或出让的所有收入应不低于生产一件产品的利润,这就有2y1+4y33把工厂所有设备台时和资源都出租或出让,其收入为 =8y1+16y2+12y3从工厂的决策者来看当然愈大愈好;但受到接受方的制约,从接受者来看他的支付愈少愈好,所以工厂的决策者只能在满足大于等于所有产品的利润条件下,提出一个尽可能低的出租或出让价格,才能实现其原意,为此需解如下的线性规划问题称这个线性规划问题为例1线性规划问题(这里称原问题)的对偶问题。min=8y1+16y2+12y3 y1+4y2 2 2y1 +4y33 yi0,i=1,2,3 (2-8)这就是从另一角度提出的线性规划问题。进
5、一步讨论它们之间的关系从第1节得到检验数的表达式是CN-CBBN-1与-CBB-1在第1章已提到,当检验数CN-CBBN-10(2-9)-CBB-10(2-10)这表示线性规划问题已得到最优解。也是作为得到最优解的判断条件。现在讨论这两个条件。(1)(2-9)式,(2-10)式中都有乘子CBB-1,称它为单纯形乘子,用符号Y=CBB-1表示。由(2-10)式,可得到Y0(2)对应基变量XB的检验数是0。它是CB-CBB-1B=0。包括基变量在内的所有检验数可用C-CBB-1A0表示。从此可得C-CBB-1A=C-YA0移项后,得到YAC(3)Y由(2-10)式,得到-Y=-CBB-(2-11)
6、将(2-11)式两边右乘b,得到-Yb=-CBB-1b(2-12)Yb=CBB-1b=z因Y的上界为无限大,所以只存在最小值(4)从这里可以得到另一个线性规划问题min=YbYACY0称它为原线性规划问题maxz=CXAXb,X0的对偶规划问题对偶规划问题例生产计划问题某厂生产甲乙两种产品,各自的零部件分别在A、B车间生产,最后都需在C车间装配,相关数据如表所示:问如何安排甲、乙两产品的产量,使利润为最大。产品产品车间车间工时单耗工时单耗甲甲乙乙生产能力生产能力ABC10023481236单位产品获利单位产品获利35(1)(1)决决策策变变量量。要决策的问题是甲、乙两种产品的产量,因此有两个决
7、策变量:设x1为甲产品产量,x2为乙产品产量。(2)(2)约约束束条条件件。生产这两种产品受到现有生产能力的制约,用量不能突破。生产单位甲产品的零部件需耗用A车间的生产能力1工时,生产单位乙产品不需耗用A车间的生产能力,A车间的能力总量为8工时,则A车间能力约束条件表述为 x18同理,B和C车间能力约束条件为2x212 3x1+4x236建立模型建立模型(3)(3)目标函数目标函数。目标是利润最大化,用Z表示利润,则 maxZ=3x1+5x2(4)(4)非非负负约约束束。甲乙产品的产量不应是负数,否则没有实际意义,这个要求表述为 x1 0,x2 0综上所述,该问题的数学模型表示为综上所述,该问
8、题的数学模型表示为 maxZ=3x1+5x2 x182x212 3x1+4x236 x1 0,x2 0若例1中该厂的产品平销,现有另一企业想租赁其设备。厂方为了在谈判时心中有数,需掌握设备台时费用的最低价码,以便衡量对方出价,对出租与否做出抉择。在这个问题上厂长面临着两种选择:自行生产或出租设备。首先要弄清两个问题:合理安排生产能取得多大利润?为保持利润水平不降低,资源转让的最低价格是多少?问题的最优解:x1=4,x2=6,Z*=42。一、对偶问题一、对偶问题第二个问题:出让定价第二个问题:出让定价假设出让A、B、C设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时,如若出让,不应
9、低于自行生产带来的利润,否则宁愿自己生产。于是有y1+0y2+3y33同理,对乙产品而言,则有 0y1+2y2+4y35设备台时出让的收益(希望出让的收益最少值)min=8y1+12y2+36y3显然还有 y1,y2,y30对偶问题的最优解:y1=0,y2=1/2,y3=1,W*=42两个问题的目标函数值相等,这不是偶然的,上述两个问题实际上是一个问题的两个方面,如果把前者称为线性规划原问题,则后者便是它的对偶问题,反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中,初始基变量的检验数的负值。例例1的对偶问题的数学模型的对偶问题的数学模型min=8y1+12y2+36y3 y1+0y2+3
10、y33 0y1+2y2+4y35 y1,y2,y30 S.t.maxZ=3x1+5x2 x182x212 3x1+4x236 x1,x2 0对偶的定义对偶的定义 定义定义设以下线性规划问题设以下线性规划问题Maxz=CTXs.t.AXb(P)X0为原始问题,则称以下问题为原始问题,则称以下问题Minz=bTWs.t.ATWC(D)W0为原始问题的对偶问题。为原始问题的对偶问题。例例max Z=4x1+7x2s.t.3x1+5x26x1+2x28x1,x20(P)minW=6w1+8w2s.t.3w1+w245w1+2w27w1,w20(D)第2章对偶理论和灵敏度分析第4节线性规划的对偶理论从理
11、论上讨论线性规划的对偶问题原问题与对偶问题之比较原问题:对偶问题:maxZ=70X1+120X2min=360y1+200y2+300y39X1+4X23609y1+4y2+3y3704X1+5X22004y1+5y2+10y31203X1+10X2300y10,y20,y30X10X20对偶规则原问题一般模型:对偶问题一般模型:maxZ=CXmin=YbAXbYACX0Y0对偶规则原问题有m个约束条件,对偶问题有m个变量原问题有n个变量,对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与
12、对偶问题方向相反原问题与对偶问题优化方向相反对偶规则.原问题对偶问题目标函数maxmin目标函数约束条件=变量无约束变量符号无约束约束条件=对偶规则简捷记法原问题标准则对偶问题标准原问题不标准则对偶问题不标准例max=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y332x1+x2-4x3+x4+3x57y1+3y32x1+2x3-x44-4y1+2y2-6-x1+3x2-x4+x5=-2y1-y2-y30 x1,x2,x30;3y1+y3=1x40;x5无限制y10y20y3无约束例例maxz=8x1+5x2s.t.-x1+2x243x1-x2=72x1+4x28
13、x10,x20minw=4y1+7y2+8y3s.t.-y1+3y2+2y382y1-y2+4y35y10,y2:unry304.1原问题与对偶理论原问题(LP):对偶问题(DP)标准型原问题与对偶问题的关系例2根据表2-3写出原问题与对偶问题的表达式。表2-3 x y x1x2x2y1111y2222y3888c444标准形式的变换关系为对称形式原问题(LP)对偶问题(DP)非对称形式的变换关系原问题的约束条件中含有等式约束条件时,按以下步骤处理。设等式约束条件的线性规划问题第一步:先将等式约束条件分解为两个不等式约束条件。第二步:按对称形式变换关系可写出它的对偶问题设yi是对应(2-13)
14、式的对偶变量 yi是对应(2-14)式的对偶变量。这里i=1,2,,m将上述规划问题的各式整理后得到综合上述,线性规划的原问题与对偶问题的关系,其变换形式归纳为表2-4中所示的对应关系。例3 试求下述线性规划原问题的对偶问题则由表2-4中原问题和对偶问题的对应关系,可以直接写出上述问题的对偶问题,4.2 对偶问题的基本性质(1)对称性对偶问题的对偶是原问题;(2)弱对偶性 若X是原问题的可行解,Y是对偶问题的可行解。则存在CXYb;(3)无界性若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解;(4)可行解是最优解时的性质;(5)对偶定理 若原问题有最优解,那么对偶问题也有最优解;且
15、目标函数值相等;(6)互补松弛性;(7)原问题检验数与对偶问题解的关系.(1)对称性对偶问题的对偶是原问题证设原问题是maxz=CX;AXb;X0根据对偶问题的对称变换关系,可以找到它的对偶问题是min=Yb;YAC;Y0若将上式两边取负号,又因min=max(-)可得到max(-)=-Yb;-YA-C;Y0根据对称变换关系,得到上式的对偶问题是min(-)=-CX;-AX-b;X0又因min(-)=max可得max=maxz=CX;AXb;X0这就是原问题。证毕。(2)弱对偶性 证明:(3)无界性若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解 证:由性质(2)可知,例:从两图对
16、比可明显看到原问题无界,其对偶问题无可行解y1y2(4)可行解是最优解时的性质 设是原问题的可行解,是对偶问题的可行解,当时,是最优解。证明:(5)对偶定理 若原问题有最优解,那么对偶问题也有最优解;且目标函数值相等。互补松弛定理互补松弛定理若若原问题原问题LPLP与对偶问题与对偶问题DPDP的可行解的可行解 与与 分分别最优解的充分必要条件为:别最优解的充分必要条件为:其中其中X XS S和和Y YS S分别为原问题分别为原问题LPLP和对偶问题和对偶问题DPDP的的松弛向量。松弛向量。(6)互补松弛性将原问题目标函数中的系数向量C用C=YA-YS代替后,得到z=(YA-YS)X=YAX-Y
17、SX (2-15)将对偶问题的目标函数中系数列向量b,用b=AX+XS代 替 后,得 到 =Y(AX+XS)=YAX+YXS (2-16)(7)原问题检验数与对偶问题解的关系设原问题是maxz=CX;AX+XS=b;X,XS0它的对偶问题是min=Yb;YA-YS=C;Y,YS0则原问题单纯形表的检验数行对应其对偶问题的一个基解,其对应关系见表2-5。表2-5对应关系YS1是对应原问题中基变量XB的剩余变量,YS2是对应原问题中非基变量XN的剩余变量。证:设B是原问题的一个可行基,于是A=(B,N);原问题可以改写为maxz=CBXB+CNXNBXB+NXN+XS=bXB,XN,XS0相应地对
18、偶问题可表示为min=YbYB-YS1=CB(2-17)YN-YS2=CN(2-18)Y,YS1,YS20这里YS=(YS1,YS2)。当求得原问题的一个解:XB=B-1b其相应的检验数为CN-CBB-1N与-CBB-1现分析这些检验数与对偶问题的解之间的关系:令Y=CBB-1,将它代入(2-17)式,(2-18)式得YS1=0,-YS2=CN-CBB-1N证毕例4 已知线性规划问题max z=x1+x2-x1+x2+x32-2x1+x2-x31x1,x2,x30试用对偶理论证明上述线性规划问题无最优解。先将其变换为对偶问题。上述问题的对偶问题为min=2y1+y2-y1-2y21y1+y21
19、y1-y20y1,y20由第1约束条件,可知对偶问题无可行解;原问题虽然有可行解,但最优解。例5 已知线性规划问题min=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0,j=1,2,5已知其对偶问题的最优解为y1*=4/5,y2*=3/5;z=5。试用对偶理论找出原问题的最优解。解:先写出它的对偶问题max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1,y20将y1*=4/5,y2*=3/5的值代入约束条件,得=1/53,=17/55,=7/50得到x4=0由y40得到x
20、2=0由y50得到x3=0因此原始问题的约束条件x1+x2-x4=1x1+2x2+x3-x5=-1成为x1=1x1-x5=-1由此得到由此得到x1=1,x5=2即原始问题的最优解为即原始问题的最优解为X=(x1,x2,x3,x4,x5)T=(1,0,0,0,2)Tz=6以上是理解对偶单纯形法的理论基础第2章对偶理论和灵敏度分析第5节对偶问题的经济解释影子价格在单纯形法的每步迭代中,目标函数取值z=CBB-1b,和检验数CN-CBB-1N中都有乘子Y=CBB-1,那么Y的经济意义是什么?设B是maxz=CXAXb,X0的最优基,由-Yb=-CBB-1b(2-12)式可知z*=CBB-1b=Y*b
21、。对z求偏导数,得由上式可知,变量yi*的经济意义是在其他条件不变的情况下,单位资源变化所引起的目标函的最优值的变化。cj23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5,y2*=0.125,y3*=0。这说明是其他条件不变的情况下,若设备增加一台时,该厂按最优计划安排生产可多获利1.5元;原材料A增加1kg,可多获利0.125元;原材料B增加1kg,对获利无影响。从图2-1可看到,设备增加一台时,代表该约束条件的直线由移至,相应的最优解由(4,2)变为(4,2.5),目标函数z=
22、24+32.5=15.5,即比原来的增大1.5。又若原材料A增加1kg时,代表该约束方程的直线由移至,相应的最优解从(4,2)变 为(4.25,1.875),目 标 函 数 z=4.25+31.875=14.125。比原来的增加0.125。原材料B增加1kg时,该约束方程的直线由移至,这时的最优解不变。图2-1yi*的值代表对第i种资源的估价-影子价格。这种估价是针对具体工厂的具体产品而存在的一种特殊价格,称它为“影子价格”。在该厂现有资源和现有生产方案的条件下,设备的每小时租费为1.5元,1kg原材料A的出让费为除成本外再附加0.125元,1kg原材料B可按原成本出让,这时该厂的收入与自己组
23、织生产时获利相等。影子价格随具体情况而异,在完全市场经济的条件下,当某种资源的市场价低于影子价格时,企业应买进该资源用于扩大生产;而当某种资源的市场价高于企业影子价格时,则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。对偶变量yi在经济上表示原问题第i种资源的边际价值边际价值。对偶变量的值yi*所表示的第i种资源的边际价值,称为影子价值影子价值。若原问题的价值系数Cj表示单位产值,则yi 称为影子价格影子价格。若原问题的价值系数Cj表示单位利润,则yi 称为影子利润影子利润。对偶问题的经济解释对偶问题的经济解释影子价格不是资
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对偶 理论 灵敏度 分析 精品
限制150内