[理学]Chapter02线性规划的对偶理论ppt课件

1、 2020年3月2022-5-52+设备租赁问题假定有四海机器厂想扩大消费规模想租赁常山机器厂的三种设备，常山方面应如何决定出租价格呢？+设常山机器厂对三种设备的出租定价分别为y1,y2,y3元/小时。+常山机器厂的考虑：不能比自己组织消费获利少约束条件；+四海机器厂的考虑：租金尽可能少目的函数加工设备ABC单件利润产品 I2402元产品 II2053元设备时限12h16h15h0,155 16 41222. .32max21212121xxxxxxtsxxz两种产品的件数。在计划期内应该生产为常山机器厂和21xx2022-5-53+写出原问题和新问题的约束矩阵，右端项和目的函数系数0,155

2、 16 41222. . 32 max )(21212121xxxxxxtsxxz原问题0,35 22 42. . 151612 min )(3213121321yyyyyyytsyyyw对偶问题)3 ,2( 151612,500422 )(cbA原问题)15,16,12( 32,502042 )(cbA对偶问题问题：原问题的约束矩阵等和对偶问题的之间有什么关系？2022-5-54+原问题和对偶问题A, b 和 c 的对应关系： A AT, bT c , cT b ;+原问题是极大化问题，对偶问题是极小化问题；+原问题 vs. 对偶问题：约束条件个数 = 决策变量个数，反之仍然；+原问题的约束

3、为“号，对偶问题的约束为“号。0,155 16 41222. . 32 max )(21212121xxxxxxtsxxz原问题0,35 22 42. . 151612 min )(3213121321yyyyyyytsyyyw对偶问题2022-5-55+定义2.1 原问题 LP 的对偶问题为DP其中 y = y1,y2,ymT 为对偶问题的决策变量，称LP为标准形式原问题。注：在对偶理论中，一般不再要求x和 b 非负。+例2.1 求下述问题的对偶问题。0s.t. max xbAxcxzTT0s.t. min ycyAybTw0, 0121 s.t.5 max21212121xxxxxxxxz

4、标准原问题0, 0121 s.t.5 max21212121xxxxxxxxz问题：请某位同学上黑板写下对偶问题 4？2022-5-56+定理2.1 对偶问题 DP 的对偶问题为LP+证明思路：将对偶问题转化为标准形式原问题，即 “max + 约束 形式，再用定义求解。0s.t. max xbAxcxzTT0s.t. min ycyAybTw2022-5-57).12(.s.t. s.t. 1 . 2min max TTT，也可用定义证明可以利用定理的对偶问题为原问题推论0ycyA0 xbAxybcxwz难点记住：对偶问题约束的符号取决于原问题的变量符号； 对偶问题的变量符号取决于原问题的约束

5、符号。)(.s.t. s.t. 2 . 2max min TTT当做课堂练习的对偶问题为原问题推论0ycyA0 xbAxybcxwz2022-5-58)(.s.t. s.t. 2 . 2min max TTT证明过程：见黑板的取值无限制的对偶问题为原问题定理ycyA0 xbAxybcxwz2022-5-59+设对偶问题的决策变量为 y = y1,y2,y3T， 对偶问题目的函数，约束矩阵，右端项容易写出；关键是约束符号和变量符号问题。+第1约束：min + x1 0, 假如x10, 对偶问题约束该取“，此处相反取 “；+第2约束取“=；第3约束为 min + x3 0，约束取“；+对偶问题第1

6、变量y1: 由 min+第1约束“ 决定，y1 0 ;变量y2: 由 min+第2约束“ 决定，y2 0 ; 原问题第3个等式决定了变量y3取值无限制。0, 0303 5 5146324624 s.t.347min 32132321321321xxxxxxxxxxxxxxz取值无约束0s.t. max xbAxcxzTT0s.t. min ycyAybTw2022-5-510+始终规定 原问题 LP 对偶问题为DP其中 A为m n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。0s.t. max xbAxcxzTT0s.t. min ycyAybTw)(. )DP( )LP( .32T

7、系即可证明，见黑板利用两个问题的约束关的可行解，则恒有和分别是和若（弱对偶定理）定理ybxcyx).32( )DP( )LP( .32T反证法，见黑板证明和最优解定义，或者用利用定理解。分别为两个问题的最优和则，的可行解，且有和分别是和若推论yxybxcyx2022-5-511+ 原问题 LP 对偶问题为DP其中 A为m n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。0s.t. max xbAxcxzTT0s.t. min ycyAybTw，具体见黑板。证明理利用反证法和弱对偶定证明最优性条件，和推论如利用其中一个问题，比行解。，则另外一个问题无可若其中一个问题解无界）（且目标函数

8、值相同；解另外一个一定也有最优之中一个有最优解，则和若（强对偶定理）定理)2() 3 . 2() 1 (.32)LP( 2 , )DP( )LP( ) 1 ( .422022-5-512+ 原问题 LP 对偶问题为DP其中 A为m n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。0s.t. max xbAxcxzTT0s.t. min ycyAybTw. 0 , )4(. , 0 )3(. 0, )2(. , 0 ) 1 ()DP()LP()( .52TT列的第为行，的第为其中就有如果就有如果就有如果就有如果，下列条件成立：和是，对所有的都是最优解的充要条件和的可行解，那么和分别为和

9、设松紧定理定理jiybbyxccxjijiiiiiiijjjjjjApAAxAxAypypyxyx2022-5-513求原问题的最优解。解为已知其对偶问题的最优给定线性规划问题),711,71(,0,23213. . 32 min 21321321321321yyxxxxxxxxxtsxxxTy.)0 ,75,74(,) 3)(2(Tx最终结果为求解划，利用松紧定理解题思路：写出对偶规2022-5-514+ 原问题 LP 对偶问题为DP其中 A为m n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。+推论2.4 LP和DP存在一对互补的最优基解：原问题的剩余变量对应对偶问题的变量，对偶

10、问题的松弛变量对应原问题的变量原问题解的基变量非基变量对应对偶问题的非基变量基变量互补的基解对应原问题和对偶问题的目的函数值一样+推论2.4的应用 假如原问题不方便求解，求其对偶问题最优解，利用对偶问题最终单纯形表的检验数行获得原问题最优解。0s.t. max xbAxcxzTT0s.t. min ycyAybTw2022-5-515+问题1：原问题和对偶问题哪个更容易求解？为什么？+问题2：不容易求解的问题用什么方法求解？0,155 16 41222. . 32 max )(21212121xxxxxxtsxxz原问题0,35 22 42. . 151612 min )(3213121321

11、yyyyyyytsyyyw对偶问题2022-5-516原maxbx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5cj zj00-10-1/5对偶minby1y2y3y4y512y11120-1/2015y31/50-4/511/5-1/5cj zj04033就是对偶问题最优解。由定理1T 4 . 2BcyB问题3：这个最优解在原最终单纯形表中的什么位置？是原问题最优解。1T BcxB问题4：这里的B和B1分别是什么？2022-5-517bi : 第i种资源的拥有量；yi : 第i种资源的单位估价，不是市场价格，是消费奉献估价，称为影子价格shad

12、ow price；影子价格是边际价格。0,155 16 41222. .32max21212121xxxxxxtsxxznjmiiijjybxcz11 根据基解互补原理2022-5-518+影子价格和资源利用的关系1 假设Ai x 0, 那么Ai x = bi ;+结论：资源消耗完毕，影子价格大于零；未充分利用，影子价格为0+单纯法中检验数的含义：miiijjjjjyaccc11pBBn各个变量的含义cj : 第j种产品的产值；aijyi : 消费单位产品消耗各种该资源的影子价格的总和，即产品的隐含本钱；n检验数的含义三种情况n影子价格的应用书P632022-5-519+单纯形法的思想：保持原

13、问题是可行解，在目的函数值不减的条件下迭代求解，直至检验数满足最优性标准。+原问题 vs. 对偶问题:根据基解互补原理，原问题检验数非正时，其对偶问题到达可行解，此时相应解为两个问题的最优解。+对偶单纯形法的根本思想：保持对偶问题为可行解检验数非正，此时原问题解未必可行的根底上，迭代求解目的函数值不增，当原问题解变为可行解时，即到达最优。2022-5-520+化标准形式：1 目的函数最大化？2 约束的处理？要求获得初始单位阵基0,35 22 42. . 151612 min 3213121321yyyyyyytsyyywn对偶单纯形算法的要求：保持对偶问题可行min + cj 0。cj-12-

14、16-1500CBBby1y2y3y4y50y4-2-2-40100y5-3-20-501cj zj-12-16-15000y4-2-2-4010-15y33/52/5010-1/5cj zj-6-1600-3-12y11120-1/20-15y31/50-4/511/5-1/5cj zj0-40-3-32022-5-521+先确定离基变量 br = minbi | bi 0, 那么对应xr离基。+再确定进基变量 = mincjzj/arj | arj 0,那么xj进基继续迭代。+假如某个基变量xi系数ci发生变化, cici ：所有检验数都发生变化，目的函数值也会改变；此时需重新计算所有检验

15、数，依情况考虑是否继续迭代。n 检验数 j =cj cBB1pj ci aij目的函数值 z = z + ci bi+对和的分析见黑板。2022-5-524+考虑如下问题：1 把c1= 1改为 c1 = 4，求新问题最优解；2 c2在什么范围内变化时，原问题最优解仍是新问题的最优解？0,4 26. . 2z max 32121321321xxxxxxxxtsxxx最优单纯形表为cj-12100CBBbx1x2x3x4x52x26111100 x51030111cj zj-30-1-202022-5-525+1x1是非基变量，只有1发生变化， c1 =1, c1 =4, c1=5， 1 = 1+

16、5 = 2 0 ,需要继续迭代求解+2 x2是基变量，系数由2变为c2 ， c2=c2-2,据6.12 = 2= 01 = 1 c2 1 = 1c23 = 3 c2 1 = 1c24 = 4 c2 1 = c2所有j 0，得c21最优解不变，最优值呢？cj42100CBBbx1x2x3x4x52x26111100 x51030111cj zj20-1-202x28/3012/32/3-1/34x110/3101/31/31/3cj zj00-5/3-8/3-2/3问题：新问题的最优解和最优值什么？2022-5-526+假设右端项b变为b,此时xB= B1b和 z=cBB1b都有改变： 假如B1

17、b 0，最优基不变，重新计算最优解和最优值即可。 假如B1b 0，说明B1b中有负的分量，当前解不是不行的，但是对偶可行的为什么？，修改右端列，代以B1b，利用对偶单纯形法继续求解。2022-5-527n问题：请问最优基B B是什么？ B B1是什么？ 5 求新问题的最优解。），（），（变为），（先将已知问题的最优表如右给定线性规划问题例TTT321321321321321323 )2(319 ) 1 (429,0,42 92. . 4z max 6.2 bbbxxxxxxxxxxxxtsxxxcj-1-14000CBBbx1x2x3x4x5x6-1x11/31-1/301/30-2/30 x

18、560200114x313/302/311/301/3cj zj0-40-10-22022-5-528+1 B1，重新计算xB= B1b即可：+ B1b = 1,4,4T 0, 现行解仍是可行解，又对偶可行的，故当前基解为最优解，x*=1,0,4, z* = 15.问题：最优解和最优值分别是什么？+2 计算 B1b = -1,5,2T ，b1 0,那么xj进基继续迭代。基列pi发生变化，变为pi 1 假设pi 和原基中其余各列线性无关不易判断，此时可在原最优表中增加一列pn+1 = B1pi ,令cn+1= ci, 原ci = M充分小，在原最优表根底上继续迭代计算不作为大纲要求。2 假设pi

19、 和原基中其余各列线性相关，一般需要重新计算不作为大纲要求。增加一个变量的分析书P69类似和的分析，最优表中先增加一列pn+1 = B1pn+1,再重新计算检验数，根据检验数的符号决定是否继续迭代。2022-5-530+在第一章的例子中本幻灯片第二页，假设增加一个变量，比方x6, c6 =4, p6=2,4,5T,分析最优解的变化最优解如右所示。cj23000CBBbx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5cj zj00-10-1/5n分析和求解：1 B，计算B1p6 增加到最优表中；2 计算检验数c6-z6，决定是否继续迭代。4x604

20、112x13101/20-1/504x6100-1/21/41/513x22011/2-1/400cj zj00-1/2-1/4-2/502022-5-531+设原问题约束为Ax=b，x0, A为mn矩阵，秩A=m .现增加一个约束条件 x bm+1, 为n维行向量，此时：+假设原问题最优解x*满足新的约束条件，那么x*也是新问题的最优解证明略。+假设x* bm+1,说明x*不是新问题的可行解，需要重新构造新基B见黑板,这种情况下， x*是对偶可行的，可利用对偶单纯形法求解约束写成BxB+ NxN+xn+1 = bm+1：n 结论1：新约束添加消元后，原变量检验数j1jn不变， n+1=0n

21、结论2：消元后bm+1 位置变为： bm+1 BB 1b 0,故可以利用对偶单纯形法处理。新基B确实定，结论1和结论2见黑板推导。2022-5-532+在第一章的例子中本幻灯片第二页，假设增加一个约束条件3x1+2x214,分析最优解的变化。cj230000CBBbx1x2x3x4x5x62x13101/20-1/500 x4400-214/503x2301001/500 x614320001cj zj00-10-1/50n分析和求解：1原最优解x*=3,3T, 不满足新约束；2新约束化为等式参加到最终单纯形表中;3把新约束的B部分消元为0，检验数部分不必重新计算。0 x6502-3/203/

22、510 x6-100-3/201/512022-5-533n新问题最优解：x*=8/3,3T, z*=43/3cj230000CBBbx1x2x3x4x5x62x13101/20-1/500 x4400-214/503x2301001/500 x6-100-3/201/51cj zj00-10-1/500 x32/30010-2/15-2/30 x416/300018/15-4/32x18/31000-2/151/3cj zj0000-1/3-2/32022-5-534+灵敏度分析研究的内容参数aij,bi,cj离散变化时，最优解和最优值的变化情况最优解或最优基不变的情况下，参数aij,bi,

23、cj的变化区间+参数线性规划的研究内容和要求 研究内容：引进新参数，把原参数写成与的线性和的形式，即bibi+di 以及cjcj+dj ,研究当连续变化时, 问题的最优解值z=z和之间的关系。 要求： z=z 是的线性函数，因此一般要求b和c不能同时含参数，一般也不研究A的变化问题：为什么这样要求？。 z=z一般为 +的分段线性函数。+参数线性规划和灵敏度分析之间的关系稍后将2022-5-535+求解方法：先令=0求得最终单纯形表将参数的反映到最终单纯表中，据参数变化范围迭代。cj2+2 3+ 000CBBbx1x2x3x4x52+2 x13101/20-1/50 x4400-214/53+ x2301001/5cj zj0