清华大学运筹学2对偶理论.pptx

第二章 线性规划对偶理论,第一节 线性规划对偶理论 第二节 对偶问题基本性质 第三节 影子价格 第四节 对偶单纯形法 第五节 灵敏度分析,1/66,第一节 线性规划对偶理论,一、对偶问题的提出 例,2/66,3/66,生产是为赢利（取得收入）。还有别的办法赢利（取得收入） 。例如，卖出或出租设备。 问，三种设备卖价或租价各应是多少，进项才不低于自己生产时的销售收入？,原来的问题：两种产品各生产多少，利润总额最大？,4/66,用y1、y2和y3分别表示A、 B和 C三种设备单位台时卖价或租价，则，总进项w可表示成 w=4y1 +12y2+18y3 生产两种产品消耗的设备台时的价值（或称出售或出租两种产品所用设备台时的进项）分别是 1y1 +0y2+3y3 和 0y1 +2y2+2y3 两种产品售价分别是3和5。出售或出租产品所用设备台时的进项不能低于售价。所以，应有 1y1 +0y2+3y3 3 和 0y1 +2y2+2y3 5 从另一个角度看，w=4y1 +12y2+18y3是总消耗。,5/66,回答y1、y2和y3各是多少的问题，可表示如下： Min w=4y1 +12y2+18y3 s.t. y1 +3y3 3 2y2 +2y3 5 y1, y2, y30 该问题叫做原问题(P)的对偶问题(D)。可看出， Max z=CX Min w=bTY (P) s.t. AXb (D) s.t. ATYCT X0 Y0,6/66,若要问对偶问题的解是什么，可以看解(P)时得到的最终单纯形表。 最终单纯形表,7/66,从该表松弛变量的检验数行得到： 3 =0， 4 = -3/2，5 = -1， y1 =0，y2 = 3/2，y3 = 1，将其代入(D): w=40 +123/2+181=36 (1) 0 +31 =3 (2) 23/2+21 =5 (3) y1, y2, y30 (4) 这是对偶问题有趣的一个方面。,8/66,二、对称的对偶问题一般形式 上面的例子叫做对称的对偶问题。 三、非对称的对偶问题 请见教科书第三版第52页或第四版第53页的表。,9/66,第二节 对偶理论基本性质,一、对称形式单纯形法矩阵表达 Max z=CX s.t. AXb X0 化成标准形式 Max z=CX+0Xs s.t. AX+IXs=b X，Xs0 Xs =(xs1, xs2, ,xsm)T 是松弛变量,10/66,令 X = XB ，(C, 0)=(CB, CN) Xs XN (A, I)=(B, N) z=CBB-1b+(CN-CBB-1N)XN (1) CN-CBB-1N是非基变量xm+1, xm+2, ,xn的检验数，令j =cj -CBB-1Pj，若所有的j 0，即 CN-CBB-1N0 (2) 则表示目前的基可行解最优。另外，基变量XB 的检验数是 CB-CBB-1B=0 (3),11/66,松弛变量Xs =(xs1, xs2, ,xsm)T的检验数是 0-CBB-1I 0，即 -CBB-10 (4) 将(2)和(3)写在一起： (CB，CN) - (CBB-1B，CBB-1N)0或 (CB，CN) - CBB-1(B，N)0 ，即 C- CBB-1A0 (5),12/66,再将(1) z=CBB-1b 、(5)和(4)写在一起： z=CBB-1b (1) C- CBB-1A0 (5) -CBB-10 (4) 令YT=CBB-1，w=YTb (1) C- YTA0 (5) -YT0 (4) 或 w=YTb ATYCT Y0,13/66,Min w=YTb (D) s.t. ATYCT Y0 添加剩余变量后，变成 Min w=YTb+0Ys (D) s.t. ATY-IYs=CT Y, Ys0 Ys =(ys1, ys2, ,ys,n-m)T 是剩余变量,14/66,15/66,例 Max z=3x1+5x2 s.t. x1 4 y1 (P) 2x2 12 y2 3x1+2x2 18 y3 x1，x2 0 Min w=4y1 +12y2+18y3 s.t. y1 +3y3 3 x1 (D) 2y2 +2y3 5 x2 y1, y2, y30,Max z=3x1+5x2 +0x3+0x4 +0x5 s.t. x1 + x3 =4 (P) 2x2 + x4 =12 3x1+2x2 + x5 =18 x1，x2 ，x3 ，x4 ，x5 0 Min w=4y1 +12y2+18y3 +0y4+0y5+My6+My7 s.t. y1 +3y3 -y4 +y6 = 3 (D) 2y2 + 2y3 -y5 +y7 =5 y1, y2, y3, y4, y5, y6, y7 0,16/107,17/66,对偶问题初始单纯形表,3应当是18-5M，但错算为18-2M，所以误选y2为换入变量。以下将错就错算下去。,18/66,对偶问题最终单纯形表,19/66,重新算一遍， 对偶问题初始单纯形表,20/66,对偶问题最终单纯形表,计算结果同上。,21/66,(P)最终单纯形表,22/66,(D)对偶问题最终单纯形表,二、对偶问题基本性质 1. 弱对偶性。若 (1jn)和 (1im)分别是(P)和(D)的可行解，则恒有 C bT 证： C = = ，回想ATYCT ，即 cj PjTY= = ，所以，有 C = = = ( = ) ，另一方面，bT = = ，回想AXb ，即 bi = ，所以，有 bT = = = ( = ) ，证毕。,23/107,推论1 (P)任一可行解目标函数值是(D)目标函数值下界。反之， (D)任一可行解目标函数值是(P)目标函数值上界。 推论2 若(P)有可行解且目标函数值无界，则(D)无可行解；反之， (D)有可行解且目标函数无界，则(P)无可行解。当 (D)无可行解时， (P)无可行解或目标函数值无界。 推论3 若(P)有可行解，而(D)无可行解，则(P)目标函数值无界；反之， (D)有可行解，而(P)无可行解，则(D)目标函数值无界。,24/66,2. 最优性。若 (j=1, 2, , n)和 (i=1, 2, , m)分别是(P)和(D)的可行解，且有 C =bT 则 和 分别是(P)和(D)的最优解。 证明:设X*和Y *分别是(P)和(D)的最优解。则有C CX * ，bTY * bT ，即bTYbT =C CX * 另一方面，根据性质1，CX * bTY * ，这就是说CX * =bTY * ，证毕。,25/107,3. 对偶定理。若(P)和(D)均有可行解，则均有最优解，且两者的目标函数值相等。 证明:由于(P)和(D)均有可行解，根据弱对偶性推论1，(P)目标函数值有上界， (D)目标函数值有下界，因此，(P)和(D)都有最优解。另外，根据 ATYCT，Y0，w=YTb=CBB-1b=z知道，当(P)取得最优解时，(D)有可行解，且有w=z，根据性质2（最优性）， (D)的可行解也是最优解，证毕。,26/107,4. 互补松弛性。若 和 分别是(P)和 (D)的可行解，那么， TXs=0和 TYs=0的充分必要条件是 和 分别是(P)和 (D)的最优解。 证明: Max z=CX+0Xs (P) s.t. AX+IXs=b X，Xs0 Xs =(xs1, xs2, ,xsm)T 是松弛变量 Min w=bTY-0Ys (D) s.t. ATY-IYs=CT Y，Ys0 Ys =(ys1, ys2, ,ys,n-m)T 是剩余变量,27/107,z=CX+0Xs=(YTA-IYsT)X+0Xs=YTAX-IYsTX w=bTY-0Ys=(AX+IXs)TY-0Ys=XTATY+IXsTY 若 TXs=0和 TYs=0 ，有z=w，根据性质2，知 和 是最优解。若 和 是最优解，则有z=w，即 CX=YTAX-IYsTX=bTY=XTATY+IXsTY 或 YTAX-IYsTX=XTATY+IXsTY 或 -YsTX=XsTY 即 YsTX=XsTY=0 证毕。,28/107,第三节 影子价格,一、影子价格 在例子 Max z=3x1+5x2 s.t. x1 4 (P) 2x2 12 3x1+2x2 18 x1，x2 0 bT=(4, 12, 18)是资源，即可利用的设备台班量。在讨论如何才能赢利最多时，没有考虑三种设备单位台班的价格。它们的价格藏在深处。,29/66,30/66,有些经济学家认为，自由的市场交易，商品成交价格能够反映其真正价值。但是，资源的现实市场价格并不反映其“真正”价值。还有些经济学家认为，影子价格是原本无交易的资源，在转为其他用途时的价格，或者说，另外再增加一个单位此种资源需要付出的价格。这个问题可以利用对偶问题的解给予某种解释。 Min w=4y1 +12y2+18y3 s.t. y1 +3y3 3 (D) 2y2 +2y3 5 y1, y2, y30 其解是(Y, Ys)T=(y1, y2, y3, y4, y5) =(0, 3/2, 1, 0, 0),31/66,这就是说，三种设备每台时的价格分别是0, 3/2和1。第一种设备每台时的价格为0，这是什么意思？ 请看原问题 Max z=3x1+5x2 +0x3+0x4 +0x5 s.t. x1 + x3 =4 (P) 2x2 + x4 =12 3x1+2x2 + x5 =18 x1，x2 ，x3 ，x4 ，x5 0 其解是(X, Xs)T=(x1, x2, x3, x4, x5) =(2, 6, 2, 0, 0),32/66,x3=2，也就说，第一种设备台时有余裕，再增加其台时，无助于增加利润，因此，“另外再增加一个单位此种资源需要付出的价格”为0。 第i种资源“再增加一个单位需要付出的价格”=limit w/ b=w/b=bTY/b=Y，这就是说，Y设备台时的影子价格。 w/b1 y1 w= w/b= w/b2 = y2 =Y . . . . . . w/bm ym,33/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,(2, 6),z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,34/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,(2, 6),z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,x1=5,z=36-36=0,35/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,(5/3, 6.5),z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,2x2=13,z=3x1+5x2=37.5,z=37.5-36=1.5,36/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,z=3x1+5x2=37,3x1+2x2=19,z=37-36=1,第四节 对偶单纯形法,一、对偶单纯形法思路 Min w=bTY-0Ys (D) s.t. ATY-IYs=CT Y，Ys0,37/66,二、对偶单纯形法计算步骤,Step1：找出初始可行基、初始单纯形表和初始基解。 Step2：若B-1b0，初始基解是最优解，停。否则，下一步。 Step3：取(B-1b)l=min(B-1b)i|(B-1b)i0，第l行基变量换出。若所有的alj0，无可行解，停。 Step4：计算k/alk=minj/alj|alj0，第k列非基变量换入。 Step5：求基的逆矩阵、新基解和z。回Step2。,38/107,39/66,例1 Min w=4x1+12x2 +18x3 s.t. x1 + 3x3 3 2x2 + 2x3 5 x1，x2 ，x3 0 将其改写如下： Max -w= -4x1-12x2 -18x3+0x4+0x5 s.t. -x1 - 3x3 +x4 = - 3 -2x2 -2x3 +x5 = -5 x1，x2 ，x3 ，x4 ，x5 0,40/66,初始单纯形表,先确定换出变量，再换入变量,41/66,求B-1,再确定换出变量和换入变量，,42/66,求B-1,判断是否最优,第五节 灵敏度分析,问题的由来，先看一个方程 x1+ x2=10 1.01x1+ x2=11, x1=100, x2= -90 如果1.01增加到1.011，该方程解会如何变化？ x1+ x2=10 1.011x1+ x2=11, x1=1/0.011=90.91, x2= -80.91 a21/a21 =0.001/1.01=0.1%, x1/x1 =(90.91-100)/100=-9%,43/66,再看另外一个方程 x1+ x2=10 2.02x1+ x2=11, x1=0.980, x2= 9.020 如果2.02增加到2.022，该方程解会如何变化？ x1+ x2=10 2.022x1+ x2=11, x1=0.978, x2= 9.022 a21/a21 =0.002/2.02=0.1%, x1/x1 =(0.978-0.980)/0.980=0.2%, 这时候，可以说，第一个方程组的解对于a21敏感，而第一个方程组则否。,44/66,实际问题的数学模型，应当避免第一种情况，因为实际中很难避免将1.011算成1.01。 LP问题也会遇到类似情况。其中A、b和C都是从实际中收集、归纳和整理的数字，很难保证与实际情况丝毫不差。 如果LP问题的解因为这些数字与实际稍有偏差就会相差很大，那就说明利用A、b、C构造的LP问题模型不能用做实际问题的模型。 合理的 LP问题模型不应敏感于A、b或C的些小变化。本节课学习，当 A、b或C发生小变动时，最优解将如何变化，看一看对这些变化的敏感性。,45/66,灵敏度分析的步骤： 1. 先用最终单纯形表中B-1变换A、b和C的增量 b =B-1b， Pj =B-1Pj ， 2. 检查(P)是否仍为可行解。 3. 检查(D)是否仍为可行解。 4. 根据下表中各种情况决定下一步行动。,46/66,一、分析C的变化 问题1 若两种产品单价分别变成5元/件和3.25元/件，两种产品最优产量是否变化？ 问题2 使最优产量不变的第二种单价变化范围多大？,47/66,48/66,为了回答问题1，将两种产品改变后的单价填入最终单纯形表，并重新计算检验数，得到：,为了回答问题2，用5+c2表示第二种产品改变后的单价，并填入最终单纯形表，并重新计算检验数，得到： c4=-3/2-c2/2，若使最优解不变，则须有c40 -3/2-c2/20，c2-3,49/66,若回答使最优产量不变的第一种产品单价变化范围，则用3+c1表示第一种产品改变后的单价，并填入最终单纯形表，并重新计算检验数： c4=-3/2+c1/3， c5=-1-c1/3，若使最优解不变，则须有c40，c50，-3/2+c1/30， -1-c1/30， -3c19/2,50/66,二、分析b的变化 若b=(0, b2, 0)T，问最优解是否改变，为此，先计算 b2/3 b =B-1b = = b2/2 -b2/3 将其添入最终单纯形表中，得到：,51/66,52/66,为使第二种设备可用台时改变后的解仍然可行，须有：2+b2/30， 6+b2/20， 2-b2/30， max-6, -12b2min6, -6b26， 对于b1和b3，同样处理。,三、分析增添新变量xj的情况 如果增加新产品x6 ，单价为4元，问如何生产，总收入最多。设其所需三种设备台时为 2 5/3 P6= 0 ，变换，得P6 = = 0 1 1/3 将P6 填入最终单纯形表，并重新计算检验数：,53/66,54/66,四、分析技术系数aij变化时的情况 如果aij对应的xj是非基变量，处理办法同“三”。如果xj是基变量，先变换Pj， Pj =B-1Pj 例1第二种产品用设备台时由 0 改为 0 2 P2 = 2 2 3/2 单价由5元增加为5.5元/件，用x*2表示这种“新”产品产量，先变换P2如下，然后添入最终单纯形表，并重新计算检验数：,55/66,1/6 P