对偶线性规精品课件

1、对偶线性规第1页，共49页，2022年，5月20日，1点58分，星期三本章学习要求掌握对偶理论及其性质掌握影子价格的应用掌握对偶单纯形法熟悉灵敏度分析的概念和内容掌握右侧常数，价值系数，工艺系数的变换对原最优解的影响掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素的灵敏度范围第2页，共49页，2022年，5月20日，1点58分，星期三2022/9/162浙江科技学院经济管理学院管工系2.1线性规划的对偶问题问题的提出对称形式下对偶问题的一般形式非对称形式下的原问题与对偶问题的关系第3页，共49页，2022年，5月20日，1点58分，星期三2022/9/163浙江科技学院经济管理学

2、院管工系一、对偶问题的提出每一个LP问题，都伴随着另一个LP，而且二者有密切关系，互为对偶，另其中一个问题为原问题，另一个问题为对偶问题，只要得到了其中一个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问题就可以了。例1：（美佳公司）美佳公司应如何生产安排，使已有资源利润最大化。某公司至少该出多大代价，使美佳公司愿意放弃自己的资源，产品资源资源约束A0515B6224调试工序115单位产品利润21产品资源AB调试工序单位资源利润06125211资源量15245第4页，共49页，2022年，5月20日，1点58分，星期三2022/9/164浙江科技学院经济管理学院管工系数学模型Cj2

3、1000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2j000-1/4-1/2cj-15-24-500-MCBYBby1y2y3y4y5y6-My62061-1011/3-15y11/512/51/50-1/505/2j06M-18M-2-M-30-24y21/3011/6-1/601/62-15y11/5102/151/15-1/5-1/151/2j001-3-3-M+8-24y21/4-5/410-1/41/41/2-5y31/215/2011/2-3/2-3j-15/200-7/2-3/2-M-3Z*=

4、8.5W*=8.5第5页，共49页，2022年，5月20日，1点58分，星期三2022/9/165浙江科技学院经济管理学院管工系二、对偶问题的一般形式 一般认为变量均为非负约束的情况下，约束条件在目标函数取Max时均取“”号；当目标函数求Min值时均取“号。则称这些线性规划问题具有对称性。max z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0min w=b1y1+b2y2+bmyms.t. a11y1+a21y2+am1ym c1 a12y1+a

5、22y2+am2ym c2 a1ny1+a2ny2+amnym cn y1, y2, , ym 0Max Z=CX s.t. AXb X0Minw=Yb s.t. AYC Y0第6页，共49页，2022年，5月20日，1点58分，星期三2022/9/166浙江科技学院经济管理学院管工系原问题max z=CXs.t. AXb X 0对偶问题min w=Ybs.t. AYCY 0maxbCCATbminmnmnA第7页，共49页，2022年，5月20日，1点58分，星期三2022/9/167浙江科技学院经济管理学院管工系举例：maxZ=3x1+2x2 s.t. -x1+2x24 3x1+2x214

6、 x1-x2 3 x1,x20minw=4y1+14y2+y3 s.t. -y1+3y2+y33 2y1+2x2-y32 y1,y2,y30y1y2y3第一种资源第二种资源第三种资源第一种产品 第二种产品x1x2第8页，共49页，2022年，5月20日，1点58分，星期三2022/9/168浙江科技学院经济管理学院管工系原始问题为min z=2x1+3x2-x3s.t. x1+2x2+x36 2x1-3x2+2x39 x1, x2, x30根据定义，对偶问题为max y=6y1+9y2s.t. y1+2y22 2y1- 3y23 y1+2y2-1 y1, y20原始问题是极小化问题原始问题的约

7、束全为原始问题有3个变量，2个约束原始问题的变量全部为非负对偶问题是极大化问题对偶问题的约束全为对偶问题有2个变量，3个约束原始问题的变量全部为非负第9页，共49页，2022年，5月20日，1点58分，星期三2022/9/169浙江科技学院经济管理学院管工系对偶问题的对偶max z=6x1+9x2s.t. x1+2x22 2x1- 3x23 x1+2x2-1 x1, x20minw=2y1+3y2-y3s.t. y1+2y2+y36 2y1-3y2+2y39 y1, y2, y30对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题。另一个就是它的对偶问题。根据定义写出对偶问题根据

8、定义写出对偶问题max u=6w1+9w2s.t. w1+2w22 2w1- 3w23 w1+2w2-1 w1, w20第10页，共49页，2022年，5月20日，1点58分，星期三2022/9/1610浙江科技学院经济管理学院管工系对偶问题的性质总结对偶的对偶就是原始问题max z=CXs.t. AXb X 0min w=Ybs.t. ATY CY0对偶的定义max u=CWs.t. AWCW 0第11页，共49页，2022年，5月20日，1点58分，星期三2022/9/1611浙江科技学院经济管理学院管工系maxZ=x1+4x2+2x3 s.t. 5x1-x2+2x38 x1+3x2-3x

9、35 x1,x2,x30minw=8y1+5y2 s.t. 5y1+y21 -y1+3y24 2y1-3y2 2 y1,y20第12页，共49页，2022年，5月20日，1点58分，星期三2022/9/1612浙江科技学院经济管理学院管工系三、非对称形式的原对偶问题minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x45 2x1 +2x3-x44 x2+x3+x4=6 x10,x2,x30minz=-2x1+3x2-5x3+(x4-x4”)1+x2-3x3+(x4-x4”)5 2x1 -2x3+(x4-x4”)-4 x2+x3 +(x4-x4”) 6 -x2-x3-(x4-

10、x4”) -6 x1,x2,x3 ,x4,x4” 0变为对称形式y1y2y3y3”maxw=5y1-4y2+6(y3-y3”)1+2y2 -2 y1 +(y3-y3”) 3 -3y1-2y2+(y3-y3”) -5 y1+y2+(y3-y3”) 1 - y1-y2-(y3-y3”) - 1 y1,y2 ,y3,y3”0写出对偶问题maxw=5y1+4y2+6y3 s.t. y1+2y2 2 y1 +y3 3 -3y1+2y2+y3 -5 y1 -y2 +y3 = 1 y10 ,y20,y3无约束第13页，共49页，2022年，5月20日，1点58分，星期三2022/9/1613浙江科技学院经济

11、管理学院管工系结论LP(LD)MaxX0X0X无约束St st St=LD(LP)Minst St St=Y0Y0Y无约束第14页，共49页，2022年，5月20日，1点58分，星期三2022/9/1614浙江科技学院经济管理学院管工系min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=Fre

12、e=x10 x20 x3: Free原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质。原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习（1）第15页，共49页，2022年，5月20日，1点58分，星期三2022/9/1615浙江科技学院经济管理学院管工系写对偶问题的练习（2）原始问题max z=2x1-x2+3x3-2x4s.t. x1 +3x2 - 2x3 + x412 -2x1 + x2 -3x48 3x1 - 4x2 +5x3 - x4 = 15 x10, x2:

13、Free, x30, x40min w=12y1+8y2+15y3s.t. y1 2y2 + 3y32 3y1 + y2 4y3=-1 -2y1 +5y33 y1 3y2 - y3-2 y10,y20, y3:Free对偶问题第16页，共49页，2022年，5月20日，1点58分，星期三2022/9/1616浙江科技学院经济管理学院管工系maxZ=x1-2x2+3x3 s.t. 2x1+4x2+3x3100 3x1-2x2+6x3200 5x1+3x2+4x3=150 x1, x30练习minw=100y1+200y2+150y3 s.t. 2y1+3y2+5y31 4y1-2y2+3y3=

14、-2 3y1+6y2+4y33 y10,y20minZ=2x1+2x2+4x3 s.t. x1+3x2+4x32 2x1+ x2+3x33 x1+4x2+3x3=5 x1 0, x20maxw=2y1+3y2+5y3 s.t. y1+2y2+ y32 3y1+ y2+4y3 2 4y1+3y2+3y34 y10,y20第17页，共49页，2022年，5月20日，1点58分，星期三2022/9/1617浙江科技学院经济管理学院管工系课后作业P74 2.1(4)第18页，共49页，2022年，5月20日，1点58分，星期三2022/9/1618浙江科技学院经济管理学院管工系2.2 对偶问题的基本性

15、质单纯形法的矩阵描述对偶问题的基本性质第19页，共49页，2022年，5月20日，1点58分，星期三2022/9/1619浙江科技学院经济管理学院管工系一、单纯形法计算的矩阵描述Max Z=CX AXb X0Max Z=CX AX+Xs=b X 0,Xs0引入松弛变量令X=(XB,XN)T C=(CB,CN) A=(B,N) BXB+NXN+XS=bB-1BXB+B-1NXN+B-1XS=B-1bXB=B-1b-B-1NXN-B-1XS MaxZ=CB(B-1b-B-1NXN-B-1XS)+CNXN =CBB-1b（CN-CBB-1N)XN-CBB-1XS第20页，共49页，2022年，5月2

16、0日，1点58分，星期三2022/9/1620浙江科技学院经济管理学院管工系某一决策变量xk系数列向量迭代前为Pk，迭代后为B-1Pk。当B为最优基时MaxZ=CBB-1b（CN-CBB-1N)XN-CBB-1XS令Y=CBB-1由此可以看出，当X为最优解时，Y为对偶问题的可行解。且该可行解对应的目标函数值W=Yb=CX*第21页，共49页，2022年，5月20日，1点58分，星期三2022/9/1621浙江科技学院经济管理学院管工系非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1对

17、应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b；约束矩阵（A，I）（B，N，I），迭代后为（B-1B，B-1N，B-1I）（I，B-1N，B-1)；初始单纯形表中xj的系数向量为Pj，迭代后为Pj，且Pj=B-1Pj。第22页，共49页，2022年，5月20日，1点58分，星期三2022/9/1622浙江科技学院经济管理学院管工系二、对偶问题的基本性质原始问题max z=CXs.t. AXb X 0对偶问题min w=Ybs.t. AY CY 01.弱对偶性若X0为原问题的可行解，Y0为对偶问题的可行解，则恒有CX0Y0b证

18、明：X0 0为LP的可行解，Y0 0为LD的可行解，则有： AX0 b AY0 C Y0AX0 Y0b (AY0)X0 (C)X0 Y0b Y0AX0 CX0第23页，共49页，2022年，5月20日，1点58分，星期三2022/9/1623浙江科技学院经济管理学院管工系推论: (LP-Max LD-Min)1.LP任一可行解的目标函数是其LD目标函数值的下界，反之LD任一可行解的目标函数是其LP目标函数的上界。Z=CXMaxZ=MinW Yb2.如LP有可行解且目标函数值无界，则其LD无可行解；反之LD有可行解且目标函数无界，则LP无可行解。(对偶问题无可行解时，其原问题无界解或无可行解。)

19、Z=CX+ Yb W= Yb - CX3.若LP有可行解而其LD无可行解时，LP目标函数无界反之，若LD有可行解而其LP无可行解时，LD目标函数无界。第24页，共49页，2022年，5月20日，1点58分，星期三2022/9/1624浙江科技学院经济管理学院管工系2.最优性若X0为LP的可行解，Y0为LD的可行解，且CX0Y0b,则X0，Y0分别为LP和LD的最优解。证明：设LP的最优解为X*,LD的最优解为Y*又因为：CX* CX0=Y0b Y*b又由弱对偶性定理：CX Yb则X0必为X*,Y0必为Y*3.强对偶性若原问题和对偶问题均具有可行解，则两者均具有最优解，且他们的最优解的目标值相等

20、。第25页，共49页，2022年，5月20日，1点58分，星期三2022/9/1625浙江科技学院经济管理学院管工系4.互补松弛定理如果X*,Y*分别为LP,LD问题的可行解，则X*,Y*为最优解的充要条件为：Y*XS*=0YS*X*=0 当LP中第i个约束是严格不等式，则Y中的Yi必为0，如果Yi不为0,则LP中第i个约束为严格等式。 当LD中第j个约束是严格不等式，则X中的xj必为0，如果xj不为0,则LD中第j个约束为严格等式。第26页，共49页，2022年，5月20日，1点58分，星期三2022/9/1626浙江科技学院经济管理学院管工系课堂作业P74 2.3课后作业(P75-P76)

21、2.4 2.5 2.6 2.7第27页，共49页，2022年，5月20日，1点58分，星期三2022/9/1627浙江科技学院经济管理学院管工系2.3 影子价格阐述对偶变量的经济意义，即对偶变量的经济解释引例：美佳公司如果已知LP的X*=(7/2,3/2,15/2,0,0) Z*=8.5求解Y*,W*？由对偶问题的基本性质知：W*=Z*=8.5 15Y1+24y2+5y3=8.5又因为Y*XS*=0 X*代入LP的约束条件中，知为严格不等式，则xS10，则y1=0由互补松弛定理：因为YS*X*=0 X10,X20则yS1*=0, yS2*=0 ，即LD的，为严格等式6y2+y3=25y1+2y

22、2+y3=1 Y1=0 Y2=1/4 y3=1/2第28页，共49页，2022年，5月20日，1点58分，星期三2022/9/1628浙江科技学院经济管理学院管工系1.定理：根据对偶问题的基本性质对LP为生产问题而言： bi表示LP中第i种资源的拥有量； Cj表示第j种产品的利润或产值其中Yi*可用下面数学式求得：1）yi*可解释为第i种资源的边际价格，即在其他条件不变的情况下，只增加单位第i种资源所引起的目标函数最优值的变化，bibi+1, bi=1， Z*的值为yi*。2） yi*也可解释为出让单位第i种资源的收益；3）yi*的取值随cj,xj,Aij的变化而变化，因此企业不同，产业不同，

23、资源拥有量不同，yi*的值不同，是具体企业，具体产品和具体资源拥有量的特定价格。第29页，共49页，2022年，5月20日，1点58分，星期三2022/9/1629浙江科技学院经济管理学院管工系例：美佳公司X*=(7/2,3/2,15/2,0,0) Z*=8.5由1）可知：y1*为变为5x216时Z*的增量，y1* Z*0Y2*为变为6x12x225时Z*的增量所以当A的资源增加时，Z*无变化，Y1*0LP中约束为严格的不等式，表明A没有被充分利用。第30页，共49页，2022年，5月20日，1点58分，星期三2022/9/1630浙江科技学院经济管理学院管工系2.影子价格的应用（对偶问题的应

24、用）1）yi*实际上是一种机会成本，当A的单位市场价格无论多低时，还应卖出A资源，直到15/2；当B的单位市场价格0表明该资源已充分利用，因此该资源的增加或减少均会引起Z*的变动，Yi*越大，变动越大。由美佳可得：Y1=0表明A没有充分利用，y2=1/4,y3=1/2表明y3的变动对美佳公司利益的影响要大。 3）新产品是否投产以及合理定价的问题例：美佳考虑生产电器，要耗A 3 ，B 2，调试1个单位，市场价格2元，问是否值得生产。又如果美佳决定生产该种产品，则要定价多少该公司才不会亏本。第31页，共49页，2022年，5月20日，1点58分，星期三2022/9/1631浙江科技学院经济管理学院

25、管工系4）合理调配资源因为影子价格是资源在特点环境下的价值，随环境的变化而变化，同一资源在有些使用中价值低，有些使用中价值高。例：美佳公司有两个子公司（1）A0 B 1/4 C 1/2(2) A2 B 0 C 1因此： （1） （2） A A B B C C第32页，共49页，2022年，5月20日，1点58分，星期三2022/9/1632浙江科技学院经济管理学院管工系课后作业P76 2.8第33页，共49页，2022年，5月20日，1点58分，星期三2022/9/1633浙江科技学院经济管理学院管工系2.4 对偶单纯形法一、基本思路从LP的一个基解出发，转换到另一个基解；在转换过程中，保持对

26、应的LD的解Y的可行性（相当于LP的j0），逐步消除该基解的不可行性，直到基解变成可行解，就获得了最优解。注：该方法不是求解LD的单纯形法，而是利用对偶关系求解LP的另一种方法。第34页，共49页，2022年，5月20日，1点58分，星期三2022/9/1634浙江科技学院经济管理学院管工系二、计算步骤：1.假定已给一对偶可行基单位阵B（对应LD问题的解可行），相应的基解XBb。2.若b的各个分量均非负，则这个解就是最优解，停止迭代。3.如果XB有分量xl0，且xl所在行的所有系数alj0，则LP无可行解，停止迭代。 如果XB有分量xl0，且该分量所在行的系数alj有负分量，则该解不是LP的最

27、优解，继续。4.如果min bi/ bi0bl，则xl为换出变量minj /alj|alj0= k/alk,则xk为换入变量5.以alk为主元，进行系数行变换，得一新的对偶可行基解(也称正则解），转第2步。第35页，共49页，2022年，5月20日，1点58分，星期三2022/9/1635浙江科技学院经济管理学院管工系比较单纯形法和对偶单纯形法单纯形法：先从基解、可行解出发，通过若干次迭代使满足j0对偶单纯形法:先从基解， 对偶可行解（等价于j0）出发，再通过若干次迭代使之可行。对偶单纯形法的优缺点：优点:初始基解可为负，减少人工变量数量，使计算简单；灵敏度分析时使用方便。缺点：不能保证所有的

28、Lp问题的初始单纯形表中的j0。第36页，共49页，2022年，5月20日，1点58分，星期三2022/9/1636浙江科技学院经济管理学院管工系例:cj-2-3-400CBXBbx1x2x3x4x50X4-3-1-2-1100 x5-4-21-301j-2-3-40014/3 0 x4-2x112-1/23/20-1/2-10-5/21/21-1/2j0-2-10-14/52-3x2-2x1 12/50-1/5-2/51/511/5107/5-1/5-2/5j00-9/5-8/5-1/5所以：X*=(x1,x2)T=(11/5,2/5)T Z*=28/5第37页，共49页，2022年，5月2

29、0日，1点58分，星期三2022/9/1637浙江科技学院经济管理学院管工系课后作业2.9（1）第38页，共49页，2022年，5月20日，1点58分，星期三2022/9/1638浙江科技学院经济管理学院管工系2.5 灵敏度分析Cj变化时bi变化时增加一个变量xj时增加一个约束条件时技术系数Pj发生变化时第39页，共49页，2022年，5月20日，1点58分，星期三2022/9/1639浙江科技学院经济管理学院管工系LP变化导致的变化可分为：X*不变，Z*改变X*中基变量不变，取值改变，Z*改变。X*中基变量改变，Z*改变XBXNXSXSBNIbXBIB-1NB-1B-1b0CN-CBB-1N

30、-CBB-1第40页，共49页，2022年，5月20日，1点58分，星期三2022/9/1640浙江科技学院经济管理学院管工系一、分析cj变化当CNj发生变化时， 对应的Nj变化Nj0 X*,Z*不变Nj0 用单纯形法进行基变换XBXNXSXSBNIbXBIB-1NB-1B-1b0CN-CBB-1N-CBB-1当CBi发生变化时， 所有Nj变化Nj0 X*不变,Z*变化Nj0 用单纯形法进行基变换第41页，共49页，2022年，5月20日，1点58分，星期三2022/9/1641浙江科技学院经济管理学院管工系例5：美佳公司1.当C1由2变为1.5时， 当C2由1变为2时，最优解有什么变化？2.

31、当C1不变，C2在什么范围内变换时，最优解不变？Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2j000-1/4-1/2解：1Cj1.52000CBXBbx1x2x3x4x50 x46004/51-61.5x1210-1/5012x23011/500j00-1/100-3/21.51.51/8-9/4 22解：2Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2j000-1/4-1/2c2c2454=（

32、c2-2）/405=（23c2）/2 02/3c22第42页，共49页，2022年，5月20日，1点58分，星期三2022/9/1642浙江科技学院经济管理学院管工系二、分析bi变化该变化只会引起右侧常数的变化：B-1b0 则基变量不变，X*的取值变化，Z*变化B-1b 0 用对偶单纯形法进行基变换XBXNXSXSBNIbXBIB-1NB-1B-1b0CN-CBB-1N-CBB-1第43页，共49页，2022年，5月20日，1点58分，星期三2022/9/1643浙江科技学院经济管理学院管工系例6：美佳公司1.当其他能力不变，B设备由24变为32时，最优解有什么变化？2.当A,B不变，调试工序能力在什么范围内变换时，基变量不变？Cj21000CBXBbx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2j000-1/4-1/2解：1：Cj21000CBXBbx1x2x3x4x50 x315051002x15110010 x420-401-6j0-100-2 解：24b36第