对偶理论与灵敏度分析讲稿.ppt

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

1、 关于对偶理论与灵敏度分析第一页，讲稿共四十二页哦 第一章例1中：美佳公司利用自身资源生产两种家电产品，其线形规划问题表示为：max z=2x1+x2 5x2 15 St.6x1+2x224 x1 x2 5 x1、x2 0 现假定有某公司想把美佳公司的资源买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。设y1、y2 和y3代表单位时间设备A、设备B和调试工序的出让代价，则6 y2 y3 2、5y1+2y2+y3 1；另外要求，min z=15y1+24y2+5y3，且y1、y2、y3 0即 min z=15y1+24y2+5y3 6 y2 y3 2 5y1+2y2

2、+y3 1 y1、y2、y3 0St.2.1 线性规划的对偶问题线性规划的对偶问题对偶问题的提出对偶问题的提出第二页，讲稿共四十二页哦 max z=2x1+x2 5x2 156x1+2x224 x1+x2 5 x1、x2 0St.min z=15y1+24y2+5y3 6 y2+y3 25y1+2y2+y3 1y1、y2、y3 0St.对称形式的对偶问题对称形式的对偶问题对称形式对称形式变量非负，求极大时约束条件取变量非负，求极大时约束条件取号、求极小时约束条件取号、求极小时约束条件取号号.Max z=(2,1)x1x20 5261 1x1x21524 5(x1 x2)T 0 min w=(1

3、5,24,5)y1 y2 y30 6 15 2 1y1 y2 y321(y1 y2 y3)T 0 第三页，讲稿共四十二页哦 Max z=CX AX b X 0st.min w=YTb ATY CT Y 0st.Max z=c1 x1+c2 x2+.+cnxn a11x1+a12 x2+.+a1n xn b1 a21x1+a22 x2+.+a2n xn b2 am1x1+am2 x2+.+amn xn bm x1,x2,xn0Min w=b1 y1+b2 y2+.+bmym a11y1+a21 y2+.+am1 ym c1 a12y1+a22 y2+.+am2 ym c2 a1ny1+a2n y

4、2+.+amn ym cn y1,y2,ym0对称形式的对偶问题对称形式的对偶问题第四页，讲稿共四十二页哦 1,若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然。2,原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵。3,极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。4,原问题与对偶问题互为对偶问题。对偶问题的特点对偶问题的特点Max z=CX AX b X 0St.Min z=-CX -AX -b X 0st.Max w=-YTb -ATY -CT Y 0st.min w=YTb ATY CT Y 0st.求对偶求对偶标准化标准化求对偶求

5、对偶标准化标准化第五页，讲稿共四十二页哦 321324maxxxxZ0,32121321321,01413121110987654xxxxxxxxxxx符号不限32114117minyyyW0y0,y,3212132132131062139541284符号不限yyyyyyyyy非对称形式的对偶问题非对称形式的对偶问题max z=2x1+x2 5x2 156x1+2x224 x1+x2 5 x1、x2 0St.min z=15y1+24y2+5y3 6 y2+y3 25y1+2y2+y3 1y1、y2、y3 0St.第六页，讲稿共四十二页哦 njjmnmnmmnnnnxbxaxaxabxaxax

6、abxaxaxa1),0(0),(),(),(22112222212111212111或符号不限nnxcxcxcZ2211maxmijnmmnnnmmmmycyayayacyayayacyayaya1),0(0),(),(),(22112222211211221111或符号不限mmybybybW2211min原问题原问题对偶问题对偶问题目标函数目标函数max min目标函数目标函数约束条件约束条件=无约束无约束 变量变量变量变量 无约束无约束 =约束条件约束条件非对称形式的对偶问题非对称形式的对偶问题第七页，讲稿共四十二页哦 若互为对偶的线性规划分别有可行解 则其相应的目标函数值满足 性质性质

7、1 弱对偶性弱对偶性TnxxxX),(21),(21myyyYWybybybxcxcxcZmmnn22112211CXZ max0.XbAXtsYbW min0.YCYAtsbYXAYXC2.2 对偶问题的基本性质对偶问题的基本性质第八页，讲稿共四十二页哦 推论1 极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。推论2 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。推推 论论推论3 若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。第九页，讲稿共四十二页哦 若X和Y分别是互为对偶的线性规划的可行解，且使CX=Y

8、b，则X和Y分别是相应线性规划问题的最优解。性质性质2：最优性准则：最优性准则若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1性质性质3：强对偶性（对偶定理）：强对偶性（对偶定理）第十页，讲稿共四十二页哦 性质性质4：互补松弛性：互补松弛性最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。max z=2x1+x2 5x2 156x1+2x224 x1+x2 5 x1、x2 0St.最优解最优解X*=(x1,x2,x3,x4,x5)(7/

9、2,3/2,15/2,0,0)min z=15y1+24y2+5y3 6 y2+y3 25y1+2y2+y3 1y1、y2、y3 0St.最优解最优解y*=(y1,y2,y3,y4,y5)(0,1/4,1/2,0,0)y1 0y2 1/4y3 1/2x1 7/2x2 3/2第十一页，讲稿共四十二页哦 2.3 影子价格影子价格max z=2x1+x2 5x2 156x1+2x224 x1+x2 5 x1、x2 0St.min z=15y1+24y2+5y3 6 y2+y3 25y1+2y2+y3 1y1、y2、y3 0St.最优解最优解X*=(x1,x2,x3,x4,x5)(7/2,3/2,15

10、/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第十二页，讲稿共四十二页哦 当线形规划原问题

11、与对偶问题同时取得最优解时，其对偶最优解yi 代表在资源最优利用条件下对单位第i种资源的估价，这个估价称为这种资源的影子价格。其经济意义是：在其它条件不变的情况下，单位资源变化所在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。引起的目标函数的最优值的变化。第十三页，讲稿共四十二页哦 原问题是利润最大化的生产计划问题Max z=c1 x1+c2 x2+.+cnxn a11x1+a12 x2+.+a1n xn+x n+1 =b1 a21x1+a22 x2+.+a2n xn +x n+2 =b2 .am1x1+am2 x2+.+amn xn +x n+m=bm x1,x2,x n

12、+m0总利润（元）单位产品的利润（元/件）产品产量（件）消耗的资源（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）资源限量（吨）第十四页，讲稿共四十二页哦 Min w=b1 y1+b2 y2+.+bmym a11y1+a21 y2+.+am1 ym ym+1 =c1 a12y1+a22 y2+.+am2 ym ym+2 =c2 .a1ny1+a2n y2+.+amn ym ym+n=cn y1,y2,ym+n0 资源价格（元/吨）资源限量（吨）总利润（元）对偶问题的最优解y1、y2、.、ym称为m种资源的影子价影子价格（格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 m

13、ax z=min y对偶问题是资源定价问题第十五页，讲稿共四十二页哦 1、影子价格依赖于资源的利用情况，各企业不同。影子价格的经济解释影子价格的经济解释2、影子价格表示的是资源的一种边际价格。mmiiybybybybwz2211mmiiiybybbybybzz)(2211iiybz种资源的边际利润第种资源的增量第最大利润的增量iibzyiooi影子价格越大，说明这种资源越是相对紧缺；影子价格越小，说明这种资源相对不紧缺若某种资源影子价格为零，则说明此资源未得到充分利用；若不为零，则表明该资源得到充分利用。第十六页，讲稿共四十二页哦 0 xxxxbxaxaxaxabxaxaxaxabxaxaxa

14、xas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211y1y2ym增加单位资源可以增加的利润减少一件产品可以节省的资源3、影子价格代表一种机会成本机会成本机会成本a1jy1+a2jy2+aijyi+amjym表示减少一件产品所节省的资源可以增加的利润第十七页，讲稿共四十二页哦 机会成本利润差额成本4、产品的差额成本（Reduced Cost）jjTjmjmjjjmcaycayayayy)(22110.min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyy

15、yyyycyyayayacyyayayacyyayayat sybybybw差额成本差额成本=机会成本机会成本-利润利润第十八页，讲稿共四十二页哦 在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产影子价格的经济含义影子价格的经济含义第十九页，讲稿共四十二页哦 p在单纯形法中，原问题的最优解满足：（1）是基本解；（2）可行；（3）检验数 0（YAC），即对偶解可行。p单纯形算法是从满足（1）、（2）的一个基可行解出发，转换到另一个基可行解，一直迭代到（3）得到满足，即对偶解可行为止

16、。p对偶单纯形法则是从满足（1）、（3）的一个对偶可行解出发，以基变量值是否全非负为检验数，连续迭代到（2）得到满足，即原问题的基解可行为止。p两种算法结果是一样的，区别是对偶单纯形法的初始解不一定可行，只要求所有检验数都非正，在保证所得解始终是对偶可行解的前提下，连续迭代到原问题的基解可行，从而取得问题的最优解 2.4 对偶单纯形法对偶单纯形法第二十页，讲稿共四十二页哦 单纯形法与对偶单纯形法比较第二十一页，讲稿共四十二页哦 单纯形法的步骤第二十二页，讲稿共四十二页哦 对偶单纯形法的步骤第二十三页，讲稿共四十二页哦 对偶单纯形法单纯形法解线性规划问题的方法如何用？第二十四页，讲稿共四十二页哦

17、 例:5,1,04323243253214321321jxxxxxxxxxxxxZMaxj标标准准化化3,2,1,043232432321321321jxxxxxxxxxxMinZjcj-2-3-400CBXBbx1x2x3x4x50X4-3-1-2-1100 x5-4-21-301j-2-3-4000 x4-2x1-1/23/20-1/2-10-5/21/21-1/2j0-2-10-1-3x2-2x12/50-1/5-2/51/511/5107/5-1/5-2/5j00-9/5-8/5-1/5第二十五页，讲稿共四十二页哦 对偶单纯形法单纯形法解线性规划问题的方法如何用？第二十六页，讲稿共四十

18、二页哦 对应B的基解：5,150,1,0000，X存在检验数0不可行单纯形法对偶单纯形法？12342345123471381234max98322132215.5982Zxxxxxxxxxxxxxstxxxxxxx 6123456780,0 xx xx x x x xx,单纯形法和对偶单纯形法均不可行的例子第二十七页，讲稿共四十二页哦 9x增加人工变量用大M法求解或用两阶段法求解12342345123471381293max98322132215.598Zxxxxxxxxxxxxxxs txxxxxx 4612345678920,0 xxxxxxxxxxx,第二十八页，讲稿共四十二页哦 灵敏度

19、分析的两把尺子：j=Cj-CBB-1pj 0；xB=B-1b 0假设每次只有一种系数变化 价值系数C变化（单位产品利润变化）右端常数b变化（资源拥有量变化）2.5 灵敏度分析（灵敏度分析（Lindo求解）求解）当系数A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基不变，系数A，b，C的允许变化范围是什么？第二十九页，讲稿共四十二页哦 第一章例1中，若家电的利润降至1.5元/件，家电的利润增至2元/件，最优生产计划是否改变；原最终表1.51.52 2000CB 基bx1 x2x3x4x501.51.52 2x3 x1x215/27/23/20100011005/41/4-1/4-15

20、/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，分析公司最优计划的变化；b=B-1b=1 5/4 -15/20 1/4 -1/20 -1/4 3/2080102-2=21000CB 基bx1 x2x3x4x5021x3 x1x215/2+1015/2+107/2+27/2+23/2-23/2-2

21、0100011005/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利润（元）21LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)8.500000 VARIABLE VALUE REDUCED COST X1 3.500000 0.000000 X

22、2 1.500000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)7.500000 0.000000 3)0.000000 0.250000 4)0.000000 0.500000 NO.ITERATIONS=2 max 2x1+x2st2)5x2=153)6x1+2x2=244)x1+x2=5end第三十二页，讲稿共四十二页哦 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE

23、DECREASE X1 2.000000 1.000000 1.000000 X2 1.000000 1.000000 0.333333 RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 15.000000 INFINITY 7.500000 3 24.000000 6.000000 6.000000 4 5.000000 1.000000 1.000000max 2x1+x2st2)5x2=153)6x1+2x2=244)x1+x2=5endTHE TABLEAU ROW (BASIS)X

24、1 X2 SLK 2 SLK 3 SLK 4 1 ART 0.000 0.000 0.000 0.250 0.500 8.500 2 SLK2 0.000 0.000 1.000 1.250 -7.500 7.500 3 X1 1.000 0.000 0.000 0.250 -0.500 3.500 4 X2 0.000 1.000 0.000 -0.250 1.500 1.500第三十三页，讲稿共四十二页哦 DAKOTA家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。若要求桌子的生产量不超过5 件，如何安排三种产品的生产可使利润最大？每个书桌每个餐桌每个椅子资源总数木料8单

25、位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20 用DESKS、TABLES 和CHAIRS 分别表示三种产品的生产量，建立LP 模型，输入如下。MAX 60DESKS+30TABLES+20CHAIRSST 2)8DESKS+6 TABLES+CHAIRS=48 3)4DESKS+2 TABLES+1.5CHAIRS=20 4)2DESKS+1.5TABLES+0.5CHAIRS=8 5)TABLES =5END第三十四页，讲稿共四十二页哦 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUN

26、CTION VALUE 1)280.0000 VARIABLE VALUE REDUCED COST DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)24.000000 0.000000 3)0.000000 10.000000 4)0.000000 10.000000 5)5.000000 0.000000 NO.ITERATIONS=2MAX 60DESKS+30TABLES+20CHAIRSST 2)8DESKS+6 T

27、ABLES+CHAIRS=48 3)4DESKS+2 TABLES+1.5CHAIRS=20 4)2DESKS+1.5TABLES+0.5CHAIRS=8 5)TABLES =5END第三十五页，讲稿共四十二页哦 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE DESKS 60.000000 20.000000 4.000000 TABLES 30.000000 5.000000 INFINITY CH

28、AIRS 20.000000 2.500000 5.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 48.000000 INFINITY 24.000000 3 20.000000 4.000000 4.000000 4 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000MAX 60DESKS+30TABLES+20CHAIRSST 2)8DESKS+6 TABLES+CHAIRS=48 3)4DESKS+2 TA

29、BLES+1.5CHAIRS=20 4)2DESKS+1.5TABLES+0.5CHAIRS=8 5)TABLES =5END第三十六页，讲稿共四十二页哦 THE TABLEAU ROW (BASIS)DESKS TABLES CHAIRS SLK 2 SLK 3 SLK 4 SLK 5 1 ART 0.000 5.000 0.000 0.000 10.000 10.000 0.000 280.000 2 SLK 2 0.000 -2.000 0.000 1.000 2.000 -8.000 0.000 24.000 3 CHAIRS 0.000 -2.000 1.000 0.000 2.00

30、0 -4.000 0.000 8.000 4 DESKS 1.000 1.250 0.000 0.000 -0.500 1.500 0.000 2.000 5 SLK 5 0.000 1.000 0.000 0.000 0.000 0.000 1.000 5.000MAX 60DESKS+30TABLES+20CHAIRSST 2)8DESKS+6 TABLES+CHAIRS=48 3)4DESKS+2 TABLES+1.5CHAIRS=20 4)2DESKS+1.5TABLES+0.5CHAIRS=8 5)TABLES=5END第三十七页，讲稿共四十二页哦 奶制品加工厂用牛奶生产A1,A2两

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

32、元，应否改变生产计划？补充问题补充问题设用x1桶牛奶加工A1，用x2桶牛奶加工A2；max z=72x1+64x2 x1+x250 12x1+8x2480 3x1100 x1,x20 St.max 72x1+64x2stmilk)x1+x2 =50time)12x1+8x2=480shop)3x1 =100end第三十八页，讲稿共四十二页哦 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.

33、000000 ROW SLACK OR SURPLUS DUAL PRICES MILK)0.000000 48.000000 TIME)0.000000 2.000000 SHOP)40.000000 0.000000 NO.ITERATIONS=2 max 72x1+64x2stmilk)x1+x2 =50time)12x1+8x2=480shop)3x1 =100end问题1）3548，该做这项投资；2）临时工人的工资最多是每小时2元；第三十九页，讲稿共四十二页哦 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES

34、VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE MILK 50.000000 10.000000 6.666667 TIME 480.000000 53.333332 80.000000 SHOP 100.000000 INFINITY 40.000000问题 3）x1的系数变为90，在允许范围内，不改变生产计划；1）每天最多购买10桶牛奶；第四十页，讲稿共四十二页哦 第二章习题第二章习题(第77页)2.1(2)、2.13(1)、（2）第四十一页，讲稿共四十二页哦 9/6/2022感谢大家观看感谢大家观看第四十二页，讲稿共四十二页哦