运筹学第二章对偶理论与灵敏度分析.ppt

《运筹学第二章对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学第二章对偶理论与灵敏度分析.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.1 线性规划的对偶问题线性规划的对偶问题2.2 对偶问题的基本性质对偶问题的基本性质2.3 影子价格影子价格2.4 对偶单纯形法对偶单纯形法2.5 灵敏度分析灵敏度分析 第一章例1中：美佳公司利用自身资源生产两种家电产品，其线形规划问题表示为：max z=2x1+x2 5x2 15 St.6x1+2x224 x1 x2 5 x1、x2 0 现假定有某公司想把美佳公司的资源买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。设y1、y2和y3代表单位时间设备A、设备B和调试工序的出让代价，则6y2y32、5y1+2y2+y31；另外要求，minz=15y1+24y2

2、+5y3，且y1、y2、y30即minz=15y1+24y2+5y36y2y325y1+2y2+y31y1、y2、y30St.2.1 线性规划的对偶问题线性规划的对偶问题对对偶偶问问题题的的提提出出max z=2x1+x2 5x2 156x1+2x224 x1+x2 5 x1、x2 0St.minz=15y1+24y2+5y36y2+y325y1+2y2+y31y1、y2、y30St.对对称称形形式式的的对对偶偶问问题题对称形式对称形式变量非负，求极大时约束条件取变量非负，求极大时约束条件取号、求极小时约束条件取号、求极小时约束条件取号号.Maxz=(2,1)x1x20562711x1x215

3、245(x1x2)T0minw=(15,24,5)y1y2y3061521y1y2y321(y1y2y3)T0Maxz=CXAXbX0st.minw=YTbATYCTY0st.Maxz=c1x1+c2x2+.+cnxna11x1+a12x2+.+a1nxnb1a21x1+a22x2+.+a2nxnb2am1x1+am2x2+.+amnxnbm x1,x2,xn0Minw=b1y1+b2y2+.+bmyma11y1+a21y2+.+am1ymc1a12y1+a22y2+.+am2ymc2a1ny1+a2ny2+.+amnymcn y1,y2,ym0对对称称形形式式的的对对偶偶问问题题1,若原问题

4、目标是求极大化，则对偶问题的目标是极小化，反之亦然。2,原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵。3,极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。4,原问题与对偶问题互为对偶问题。对对偶偶问问题题的的特特点点Maxz=CXAXbX0St.Minz=-CX-AX-bX0st.Maxw=-YTb-ATY-CTY0st.minw=YTbATYCTY0st.求对偶求对偶标标准准化化求对偶求对偶标标准准化化非非对对称称形形式式的的对对偶偶问问题题max z=2x1+x2 5x2 156x1+2x224 x1+x2 5 x1、x2 0St.minz=

5、15y1+24y2+5y36y2+y325y1+2y2+y31y1、y2、y30St.原问题原问题对偶问题对偶问题目标函数目标函数max min目标函数目标函数约束条件约束条件=无约束无约束 变量变量变量变量 无约束无约束 =约束条件约束条件非非对对称称形形式式的的对对偶偶问问题题若互为对偶的线性规划分别有可行解则其相应的目标函数值满足性质性质1 弱对偶性弱对偶性2.2 对偶问题的基本性质对偶问题的基本性质推论1极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。推论2极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。推推 论论推论

6、3若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。若X和Y分别是互为对偶的线性规划的可行解，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解。性质性质2：最优性准则：最优性准则若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1性质性质3：强对偶性（对偶定理）：强对偶性（对偶定理）性质性质4：互补松弛性：互补松弛性最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。max z=2x1+x2 5x2 156x1+2x224

7、 x1+x2 5 x1、x2 0St.最优解最优解X*=(x1,x2,x3,x4,x5)(7/2,3/2,15/2,0,0)minz=15y1+24y2+5y36y2+y325y1+2y2+y31y1、y2、y30St.最优解最优解y*=(y1,y2,y3,y4,y5)(0,1/4,1/2,0,0)y1 0y2 1/4y3 1/2x1 7/2x2 3/22.3 影子价格影子价格max z=2x1+x2 5x2 156x1+2x224 x1+x2 5 x1、x2 0St.minz=15y1+24y2+5y36y2+y325y1+2y2+y31y1、y2、y30St.最优解最优解X*=(x1,x2

8、,x3,x4,x5)(7/2,3/2,15/20,0)，最优值最优值:Z*=17/2最终表21000CB 基bx1 x2x3x4x5021x3 x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cjzj000-1/4-1/2原原问问题题对对偶偶问问题题最终表-15-24-500CB 基by1 y2y3y4y5-24-5y2 y31/41/41/21/2-5/415/21001-1/41/21/4-3/2cjzj-15/200-7/2-3/2最优解最优解y*=(y1,y2,y3,y4,y5)(0,1/4,1/2,0,0)，最优值最优值:Z*=17/2当线形

9、规划原问题与对偶问题同时取得最优解时，其对偶最优解yi代表在资源最优利用条件下对单位第i种资源的估价，这个估价称为这种资源的影子价格。其经济意义是：在其它条件不变的情况下，单位资在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。源变化所引起的目标函数的最优值的变化。原问题是利润最大化的生产计划问题Maxz=c1x1+c2x2+.+cnxna11x1+a12x2+.+a1nxn+xn+1=b1a21x1+a22x2+.+a2nxn+xn+2=b2.am1x1+am2x2+.+amnxn+xn+m=bm x1,x2,xn+m0总利润（元）单位产品的利润（元/件）产品产量（件）消耗

10、的资源（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）资源限量（吨）Minw=b1y1+b2y2+.+bmyma11y1+a21y2+.+am1ymym+1=c1a12y1+a22y2+.+am2ymym+2=c2.a1ny1+a2ny2+.+amnymym+n=cn y1,y2,ym+n0资源价格（元/吨）资源限量（吨）总利润（元）对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润maxz=miny对偶问题是资源定价问题1、影子价格依赖于资源的利用情况，各企业不同。影影子子价价格格的的经经济济解解释释2、影

11、子价格表示的是资源的一种边际价格。影子价格越大，说明这种资源越是相对紧缺；影子价格越小，说明这种资源相对不紧缺若某种资源影子价格为零，则说明此资源未得到充分利用；若不为零，则表明该资源得到充分利用。y1y2ym增加单位资源可以增加的利润减少一件产品可以节省的资源3、影子价格代表一种机会成本机会成本机会成本a1jy1+a2jy2+aijyi+amjym表示减少一件产品所节省的资源可以增加的利润机会成本利润差额成本4、产品的差额成本（ReducedCost）差额成本差额成本=机会成本机会成本-利润利润在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安

12、排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产影子价格的经济含义影子价格的经济含义p在单纯形法中，原问题的最优解满足：（1）是基本解；（2）可行；（3）检验数0（YAC），即对偶解可行。p单纯形算法是从满足（1）、（2）的一个基可行解出发，转换到另一个基可行解，一直迭代到（3）得到满足，即对偶解可行为止。p对偶单纯形法则是从满足（1）、（3）的一个对偶可行解出发，以基变量值是否全非负为检验数，连续迭代到（2）得到满足，即原问题的基解可行为止。p两种算法结果是一样的，区别是对偶单纯形法的初始解不一定可行，只要求所有检验数都非正，在保证所得解始终是对偶可行解的前提下，连续迭代到

13、原问题的基解可行，从而取得问题的最优解2.4 对偶单纯形法对偶单纯形法单纯形法与对偶单纯形法比较单纯形法的步骤对偶单纯形法的步骤如何用？例:cj-2-3-400CB XBbx1x2x3x4x50X4-3-1-2-1100 x5-4-21-301j-2-3-400 1 14/34/3 0 x4-2x11 12 2-1/23/20-1/2-10-5/21/21-1/2j0-2-10-1 4/54/52 2-3x2-2x1 1 12/50-1/5-2/51/511/5107/5-1/5-2/5j00-9/5-8/5-1/5所以：所以：所以：所以：X*=(xX*=(xX*=(xX*=(x1 1 1 1

14、,x,x,x,x2 2 2 2)T T T T=(11/5,2/5)=(11/5,2/5)=(11/5,2/5)=(11/5,2/5)T T T T Z*=28/5 Z*=28/5 Z*=28/5 Z*=28/5如何用？对应B的基解：存在检验数0不可行单纯形法对偶单纯形法？用大M法求解或用两阶段法求解灵敏度分析的两把尺子：j=Cj-CBB-1pj 0；xB=B-1b 0假设每次只有一种系数变化 价值系数C变化（单位产品利润变化）右端常数b变化（资源拥有量变化）2.5 灵敏度分析（灵敏度分析（Lindo求解）求解）当系数A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基不变，系数A，b

15、，C的允许变化范围是什么？第一章例1中，若家电的利润降至1.5元/件，家电的利润增至2元/件，最优生产计划是否改变；原最终表1.51.52 2000CB 基bx1 x2x3x4x501.51.52 2x3 x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cjzj0001/8-9/41.51.52 2000CB 基bx1 x2x3x4x501.52x4 x1x26230100014/5-1/51/5100-610cjzj00-1/100-3/2价价值值系系数数 变变化化C右右端端常常数数 变变化化b第一章例1中，若其它资源不变，而设备B的能力增加到32h

16、，分析公司最优计划的变化；b=B-1b=15/4-15/201/4-1/20-1/43/2080102-2=21000CB 基bx1 x2x3x4x5021x3 x1x215/2+1015/2+107/2+27/2+23/2-23/2-20100011005/41/4-1/4-15/2-1/23/2cjzj000-1/4-1/2020 x3 x1x415155 52 201051-410000101-6cjzj0-100-2灵灵敏敏度度分分析析Lindo第一章例1，美佳公司生产状况如下表项目每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21LPOPTIMUM

17、FOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)8.500000VARIABLEVALUEREDUCEDCOSTX13.5000000.000000X21.5000000.000000ROWSLACKORSURPLUSDUALPRICES2)7.5000000.0000003)0.0000000.2500004)0.0000000.500000NO.ITERATIONS=2max2x1+x2st2)5x2=153)6x1+2x2=244)x1+x2=5endRANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARI

18、ABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX12.0000001.0000001.000000X21.0000001.0000000.333333RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE215.000000INFINITY7.500000324.0000006.0000006.00000045.0000001.0000001.000000max2x1+x2st2)5x2=153)6x1+2x2=244)x1+x2=5endTHETABLEAUROW

19、(BASIS)X1X2SLK2SLK3SLK41ART0.0000.0000.0000.2500.5008.5002SLK20.0000.0001.0001.250-7.5007.5003X11.0000.0000.0000.250-0.5003.5004X20.0001.0000.000-0.2501.5001.500DAKOTA家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。若要求桌子的生产量不超过5 件，如何安排三种产品的生产可使利润最大？每个书桌每个餐桌每个椅子资源总数木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位

20、成品单价60单位30单位20用DESKS、TABLES 和CHAIRS 分别表示三种产品的生产量，建立LP 模型，输入如下。MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS=483)4DESKS+2TABLES+1.5CHAIRS=204)2DESKS+1.5TABLES+0.5CHAIRS=85)TABLES=5ENDLPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)280.0000VARIABLEVALUEREDUCEDCOSTDESKS2.0000000.000000TABLES0.0000

21、005.000000CHAIRS8.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)24.0000000.0000003)0.00000010.0000004)0.00000010.0000005)5.0000000.000000NO.ITERATIONS=2MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS=483)4DESKS+2TABLES+1.5CHAIRS=204)2DESKS+1.5TABLES+0.5CHAIRS=85)TABLES=5ENDRANGESINWHICHTHEBASISIS

22、UNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEDESKS60.00000020.0000004.000000TABLES30.0000005.000000INFINITYCHAIRS20.0000002.5000005.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE248.000000INFINITY24.000000320.0000004.0000004.00000048.00

23、00002.0000001.33333355.000000INFINITY5.000000MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS=483)4DESKS+2TABLES+1.5CHAIRS=204)2DESKS+1.5TABLES+0.5CHAIRS=85)TABLES=5ENDTHETABLEAUROW(BASIS)DESKSTABLESCHAIRSSLK2SLK3SLK4SLK51ART0.0005.0000.0000.00010.00010.0000.000280.0002SLK20.000-2.0000.0001.000

24、2.000-8.0000.00024.0003CHAIRS0.000-2.0001.0000.0002.000-4.0000.0008.0004DESKS1.0001.2500.0000.000-0.5001.5000.0002.0005SLK50.0001.0000.0000.0000.0000.0001.0005.000MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS=483)4DESKS+2TABLES+1.5CHAIRS=204)2DESKS+1.5TABLES+0.5CHAIRS=85)TABLES=5END 奶制品加工厂用牛

25、奶生产A1,A2两种奶制品，1桶牛奶可以在甲车间用12小时加工成3公斤A1，或者在乙车间用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A1，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：1）若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3）由于市场需求变化，每公斤A1

26、的获利增加到30元，应否改变生产计划？补补充充问问题题设用x1桶牛奶加工A1，用x2桶牛奶加工A2；maxz=72x1+64x2x1+x25012x1+8x24803x1100 x1,x20St.max72x1+64x2stmilk)x1+x2=50time)12x1+8x2=480shop)3x1=100endLPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICESM

27、ILK)0.00000048.000000TIME)0.0000002.000000SHOP)40.0000000.000000NO.ITERATIONS=2max72x1+64x2stmilk)x1+x2=50time)12x1+8x2=480shop)3x1=100end问题1）3548，该做这项投资；2）临时工人的工资最多是每小时2元；RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASEMILK50.00000010.0000006.666667TIME480.00000053.33333280.000000SHOP100.000000INFINITY40.000000问题3）x1的系数变为90，在允许范围内，不改变生产计划；1）每天最多购买10桶牛奶；第二章习题第二章习题(第77页)2.1(2)、2.13(1)、（2）