运筹学基础对偶线性规划(2)

1、1 132112168minyyyg3 , 2 , 1, 034y2y24yy. .3121iytsi2132xxfmax0,12416482. .212121xxxxxxts一、对偶线性规划问题一、对偶线性规划问题 设设 备备128台时台时原原 材材 料料 A A4016Kg原原 材材 料料 B B0412Kg每单位产品利润（万元）每单位产品利润（万元）23n原问题的策略原问题的策略: :n问应如何安排生产才能使工厂获问应如何安排生产才能使工厂获利最大？利最大？n现在的策略现在的策略: :n假设不生产假设不生产、产品产品 , ,而将现而将现有资源出租或出售有资源出租或出售, ,从而获得利润从

2、而获得利润, , 如何定价才合理如何定价才合理? ?对偶线性规划2 2 二、由原问题写出对偶线性规划二、由原问题写出对偶线性规划三、对偶单纯形方法三、对偶单纯形方法 原问题的标准型是：maxZ= -2x1-3x2-4x3 +0 x4 +0 x5 x1+ 2x2+x3 - x4 = 32x1 - x2 +3x3 - x5 =4 x1 , x2 , x3 , x4 , x5 0maxw= -2x1-3x2-4x3 +0 x4 +0 x5 -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0对偶线性规划3

3、 3应用对偶单纯形方法之矩阵法00-4-3-2-41-31-2-30-1-2-10014-1-1-402-1/23/2-1/21-1-1/21/2-5/2000128/5-1/5-3/50011/5-2/57/5012/51/5-1/510-8/5-1/5-2/5对偶线性规划4 4用对偶单纯形方法解下述线性规划问题 原问题是：原问题的标准型是：maxZ= -9x1+7x2-4x3 +0 x4 +0 x5 5x1 + x2 +7x3 +x4 = 5 3x1 +4x2 +8x3 =4 2x1 +6x2 +8x3 -x5=6 x1 , x2 , x3 , x4 , x5 0 0,6862484357

4、5 47-9 min 321321321321321xxxxxxxxxxxxxxxzmaxZ= -9x1+7x2-4x3 +0 x4 +0 x5 5x1 + x2 +7x3 +x4 = 5 3x1 +4x2 +8x3 =4 -2x1 -6x2 -8x3 -x5= -6 x1 , x2 , x3 , x4 , x5 0对偶线性规划5 5 对偶线性规划-61-8-6-2408435071500100-47-9001405/210213/4405017/4001-70-180-57/406 62.4 影子价格 从对偶问题的基本性质可以看出，在单纯形法的每步迭代中有目标函数miiinjjjybxcz1

5、1 此时的估价不是市场价格，而是根据资源在生产中的贡献而作的估价。 此时的定价区别于市场价格称为此时的定价区别于市场价格称为影子价格。影子价格。对偶线性规划第i种资源的估价第i种资源的拥有量7 7n 说明说明 1、市场价格市场价格主要随市场供求变化；而它的影子价格影子价格有赖于资源的利用情况。生产任务、结构的改变会影响影子价格。生产任务、结构的改变会影响影子价格。 2、影子价格是一种边际价格。iiybz y yi i代表代表b bi i每增加一个单位，每增加一个单位， 目标函数目标函数z z的增量的增量maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0,

6、 x2 0+1 （1 1）z z* *=42 =42 不变，不变，A A的边际价格为的边际价格为0 0+1 （2 2）x x* *=(10/3,13/2) z=(10/3,13/2) z* *=42.5=42.5，B B的的边际价格为边际价格为0.50.5+1 （3 3）x x* *=(13/3,6) z=(13/3,6) z* *=43=43，C C的的边际价格为边际价格为1 1x1 =82x2 =123x1 +4 x2 =36x1x24812369miiiybz1对偶线性规划8 8n 说明说明3、资源的影子价格实际上是一种机会成本。 市场价格低于影子价格时，可以买进这种资源。市场价格低于影

7、子价格时，可以买进这种资源。 市场价格高于影子价格时，可以卖出这种资源。市场价格高于影子价格时，可以卖出这种资源。随着资源的买进和卖出，它的影子价格也随之发生变化。4、生产过程中，如果某种资源bi未得到充分利用时，该种资源的影子价格为0； 某种资源的影子价格不为0时，表明该种资源已经耗尽。由对偶互补松弛定理即可说明由对偶互补松弛定理即可说明对偶线性规划9 9 灵敏度分析灵敏度分析，是指对系统或事物因周围条件变化所表现出的敏感性程度的分析。 在前面讲的线性规划问题中，通常都是假定问题中的aij， bi， cj系数是已知的常数,但实际上这些参数都是一些估计或预测的数字。 在现实中，如果市场条件变化

8、， cj值就会发生变化；如果工艺技术条件改变，则aij就会变化；如果资源的可用量发生变化，则bi也会发生变化。问题：1、参数发生变化时，问题的最优解会有什么变化？ 2、参数多大的范围内变化时,原最优解保持不变。对偶线性规划1010 解决方法：解决方法： 1、当参数变化时，用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。 2、把个别参数的变化直接在获得最优解的最终单纯形表上反映出来。这样就不需要从头计算，而只需对获得最优解的单纯形表进行审查，看一些数字变化后是否仍满足最优解的条件,如果不满足的话,再从这个表开始进行迭代计算，求得最优解即可。 这也就是灵敏度分析。对偶线性规划111

9、1灵敏度分析的步骤如下：1.将参数的改变计算反映到最终单纯形表上来b*=B-1 b 具体计算方法是，按下列公式计算出由参数aij、bi、 cj的变化而引起的最终单纯形表上有关数字的变化：Pi*=B-1 Pi(cj-zi)*= (cj-zi) -aijyi*2.检验原问题是否仍为可行解；即右端常数是否大于03.检验对偶问题是否仍为可行解；即检验数是否小于04.按下表所列情况得出结论和决定继续计算的步骤。常数项常数项bi的改变量的改变量系数系数aij的改变量的改变量目标函数系数目标函数系数cj的改变量的改变量对偶线性规划1212解的情况判定表对偶线性规划1313一、分析cj变化的影响 目标函数中的

10、系数cj的变化仅仅影响到检验数(cj-zi)的变化。所以将cj 的变化直接反映到最终单纯形表中，只可能出现表中的前两种情况。【例】已知线性规划问题： maxZ=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0用单纯形法求得最终单纯形表如下对偶线性规划1414Cj比值CBXBb检验数jx1x2x3x4x52100015/20015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2试确定： (a)当目标函数变为max Z=5x1 +1.5x2时，最优解会出现什么变化； (b) 目标函数变

11、为max Z=(2+l) x1+x2时， l在什么范围变化，最优解不变； maxZ=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0 maxZ=5x1 +1.5 x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0对偶线性规划1515【解】 (a)将目标函数系数的变化直接反映到最终单纯形表中 变量x5的检验数为正，继续迭代； maxZ=5x1 +1.5 x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 051.5000051.5-17/25-21.5-10-1/4-1/2-17/23

12、0.50-1/4-1/2-79/4000-7/81/4对偶线性规划1616 继续迭代得下表Cj比值CBXBb检验数jx1x2x3x4x551.5000150510 0411/301/60102/30-1/61x3x1x5050-200-1/60-5/60即得新最优解x1=4，x2=0，x3=15，x4=0 ，x5=1此时MaxZ=20对偶线性规划1717 (b)将目标函数系数的变化直接反映到最终单纯形表中为使表中解为最优，应该有 -1/4-1/4l0， -1/2+1/2l0 即得 ： -1 l12+l100002+l1-17/2l00-1/4-1/2-17/2-7/2l l0 0 0-1/4-

13、1/4l l-1/2+1/2l l即：-1 l1时，最优解不变；对偶线性规划1818二、分析bi变化的影响 b bi i的变化的变化在实际问题中表明可用资源的数量发生变化，其变化b反映到最终单纯形表上反映到最终单纯形表上只引起基变量列数字变化b*。因此灵敏度分析的步骤为：1.由b*=B-1b算出b*，将其加到最终表基变量列的数字上；2.由于其对偶问题仍为可行解（检验行没变），故只需检查原问题是否仍为可行解，再按相应步骤进行。注注:此公式是单纯形法利用公式求解的推导结果此公式是单纯形法利用公式求解的推导结果!问题：问题：B与与B-1分别是什么？分别是什么？对偶线性规划1919n 以此题为例Cj比

14、值CBXBb检验数jy1y2y3y4y5-15-24-500-20-6-110-1-5-2-101y4Y5000-15-24-500检验数j1/4-5/410-1/41/41/215/2011/2-3/2Y2y3-24-517/2-15/200-7/2-3/2初始单纯形表最终单纯形表BB-1原理是：原理是：(B|I)经过初等变换可化为经过初等变换可化为(I|B-1)，其中，其中I是单位阵是单位阵II对偶线性规划2020Cj比值CBXBb检验数jx1x2x3x4x52100015051002462010511001x3x4x5000021000初始单纯形表Cj比值CBXBb检验数j= cj-zj

15、x1x2x3x4x52100015/20 0 15/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/200 0-1/4-1/2B*B-1110260501BI*I对偶线性规划2121【例】上例中Cj比值CBXBb检验数jx1x2x3x4x52100015/20 015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2 (a)若第2个约束条件右端项增大到32，分析最优解变化； (b)若第2个约束条件变为 6x1+2x224+l，分析l在什么范围内变化，表中基为最优解； maxZ=2x1 +

16、 x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0 maxZ=2x1 + x2 5x2 15 6x1 + 2x2 32 x1 + x2 5 x1 , x2 0对偶线性规划2222 (a)第2个约束条件右端项增大到32Cj比值CBXBb检验数jx1x2x3x4x52100015/20015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2因 因表中原问题为非可行解，故用对偶单纯形法继续计算将其加到最终单纯形表的基变量b这一列上得下表080024320b222100802/14/102/34/10

17、2/14/102/154/51*b注： B-1扩充了检验行，目标值的变化b*=B-1b15/2+107/2+23/2-2-17/2-235/211/2-1/2-21/2B-1对偶线性规划2323 继续迭代得下表Cj比值CBXBb检验数jx1x2x3x4x521000150510 051100120-401-6x3x1x4020-100-100-2最优值 maxz*=10即得新最优解 x1=5，x2=0，x3=15，x4=2 ，x5=0对偶线性规划2424 (b)若第2个约束条件变为 6x1+2x224+lCj比值CBXBb检验数jx1x2x3x4x52100015/2 0 0 15/4-15/

18、27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2 0 0 0-1/4-1/2因将其加到最终单纯形表的基变量b这一数列上得下表00lb44445002/14/102/34/102/14/102/154/51*lllllb15/2+5l/47/2+l/43/2-l/4-17/2-l/4 15/2+5/4l0 l67/2+1/4l0 l14 3/2-1/4l0 l6得-6 l6即：-6 l6时，最优解不变；对偶线性规划2525三、增加一个变量的分析 增加一个变量在实际问题中反映为增加一种新的产品。分析步骤是：1.计算新变量最终表检验数 j=cj-zi= cj y*P

19、j2.计算新变量最终表约束函数系数向量Pj*=B-1Pj3.判定： 若j0，只需将Pj和j 的值直接反映到最终单纯形表中，原最优解不变； 若j0，则按单纯形法继续迭代计算。其中cj 是新变量目标函数系数, Pi是新变量约束函数系数，y*是对偶问题的解对偶线性规划2626【例】上例中Cj比值CBXBb检验数jx1x2x3x4x52100015/20015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2 若增加一个变量x6，有c6=3, P6=(3,4,2)T，试分析最优解的变化。 maxZ=2x1 + x2 5x2 15 6x1

20、 + 2x2 24 x1 + x2 5 x1 , x2 0 maxZ=2x1 + x2 +3 x6 5x2 +3x6 15 6x1 + 2x2 +4x6 24 x1 + x2 +2x6 5 x1 , x2 , x6 0对偶线性规划272712432/ 14/ 1036将其反映到最终单纯形表中得下表2072432/34/102/14/102/154/516PCj比值CBXBb检验数jx1x2x3x4x52100015/20015/4-15/2 7/21001/4-1/2 3/2010-1/43/2 x3x1x2021-17/2000-1/4-1/2 因6=10 ,故用单纯形法继续计算-70213

21、x6 增加变量x6，有c6=3, P6=(3,4,2)T，试分析最优解的变化。检验数j=cj-zi= cj y*Pj ， Pj*=B-1Pj对偶线性规划2828继续迭代得下表Cj比值CBXBb检验数jx1x2x3x4x5x621000351/407/213/8-9/407/21001/4-1/203/401/20-1/83/41x3x1x6023-37/4 0-1/2 0-1/8-5/4 0 由此得新的解为 x1=7/2， x2=0， x3=51/4， x4=0， x5=0，x6=3/4，Max z*=27/2+33/4=37/4对偶线性规划2929四、分析aij变化的影响 假如xj在最终表中

22、为基变量，则aij的变化将使最终表中的B-1变化，因此有可能出现原问题与对偶问题均为非可行解的情况。【例】上例中， c2=3，x2的系数向量变为P2=(8，4，1)T，试分析最优解的变化。【解】同上例 maxZ=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0 maxZ=2x1 +3x2 8x2 15 6x1 + 4x2 24 x1 + x2 5 x1 , x2 0231482/14/103*2Pycjj21212111482/34/102/14/102/154/51 212PBP对偶线性规划3030231482/14/1032Cj比值CBXBb

23、检验数jx1x2x3x4x52100315/200 15/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/221212111482/34/102/14/102/154/512P11/21/21/2 3/2对偶线性规划3131 因原问题与其对偶问题均为非可行解，通过引入人工变量将原问题转化为可行解，再用单纯形法继续计算。 将第一行x3+4x4 -24x5= -9 化为标准型-x3-4x4 +24x5=9 再加上人工变量 x3 4x4 +24x5 +x6 =9Cj比值CBXBb检验数jx1x2x3x4x523000-90 014-24

24、21001/2-23010-1/23x3x1x2023-130001/2-5对偶线性规划3232Cj比值CBXBb检验数jx1x2x3x4x5 x623000 -M900-1-424 121001/2-2 03/2010-1/23 0 x6x1x2023 因5 0 ,故用单纯形法迭代计算x34x4 +24x5 +x6 =9-130 001/2-5-M-13+9M00-M -4M-5+24M 0对偶线性规划3333Cj比值CBXBb检验数jx1x2x3x4x5x62300033/800-1/24-1/6 11/2411/410-1/121/301/1215/80 11/800-1/8x5x1x2

25、023-89/8 0 0-5/24-2/3 0-M+5/24 新的最优值为maxz*=89/8 得到新最优解：x1=11/4，x2=15/8，x3=0，x4=0，x5=3/8，x6=0对偶线性规划3434五、增加一个约束条件的分析五、增加一个约束条件的分析 增加一个约束条件，在实际问题中相当于增添一道工序。分析的方法是先将原来的问题的最优解变量取值代入这个新增的约束条件中，如满足，说明新增约束未起到限制作用，原最优解不变。否则，将新增约束直接反映到最终表中，再进行分析。【例】上例中， 新增添一个约束条件 3x1+2x2 12，试分析最优解的变化。【解】先将原问题最优解x1 =7/2, x2 =

26、3/2代入新约束条件，因有故将约束条件写成3x1+2x2 +x6 = 12，并取x6为基变量，直接反映到最终表中37/2+23/2=27/212 maxZ=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 3x1 +2x2 12 x1 , x2 0对偶线性规划3535Cj比值CBXBb检验数jx1x2x3x4x5x621000015/200 15/4-15/207/21001/4-1/2 03/2010-1/4 3/2 0 x3x1x2x60210-17/2000-1/4-1/20 x1与x2的向量不是单位向量，要继续变换1232000 1对偶线性规划3636Cj比

27、值CBXBb检验数jx1x2x3x4x5 x621000 015/200 15/4-15/2011/41001/4-1/2 03/2 010-1/43/2 0 x3x1x2x60210-17/2 0 0 0-1/4-1/2 0用对偶单纯形法迭代继续变换-3/2 000-1/4-3/2 1对偶线性规划3737Cj比值CBXBb检验数jx1x2x3x4x5x6210000150 0 15/20-541001/30-1/30 010-1/201x3x1x2x50210-8 000-1/60 -1/31 0001/61-2/3 新的最优值为max z*=8得新的最优解为：x1=4， x2=0， x3=

28、15， x4=0， x5=1，x6=0，对偶线性规划38382.7 参数线性规划参数线性规划 参数aij、bi、 cj在什么范围内变化时最优解不变是实际问题中常常要研究的问题，当这些参数超出这个范围时，最优解会发生怎样的变化，即为参数线性规划要研究的问题。 【例】线性规划问题 maxZ(l l)=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5+l l x1 , x2 0第三个约束右端不断增大，分析最优解会发生怎样的变化？ 此时此时l l 0对偶线性规划3939n参数线性规划求解步骤参数线性规划求解步骤 1、令l=0求解得最终单纯形表 2、将参数的变化反映到最终单纯形

29、表中；因l00b2232215002/14/102/34/102/14/102/154/511*lllllbBb对偶线性规划4040Cj比值CBXBb检验数jx1x2x3x4x52100015/2-(15/2) l0 0 15/4-15/27/2-(1/2) l1001/4-1/23/2 +(3/2) l010-1/43/2x3x1x2021-17/2-(1/2) l0 00-1/4-1/23、让 l逐步增大，观察原问题与对偶问题解的变化，看哪一个首先出现非可行解。x1= 7/2-(1/2) lx2= 3/2 +(3/2) lZ*= 17/2+(1/2) l表中解为最优解。此时对偶线性规划41

30、41Cj比值CBXBb检验数jx1x2x3x4x52100015/2-(15/2) l 0015/4-15/27/2-(1/2) l1 001/4-1/23/2 +(3/2) l0 10-1/43/2x3x1x2021-17/2-(1/2) l 0 0 0-1/4-1/2当 l1时，用对偶单纯形法迭代注：不用讨论7/2-(1/2)l0的情况，因为此时，15/2-(15/2)l也是负的，且绝对值更大。因此出基项仍然是x3（第一行）。对偶线性规划4242Cj比值CBXBb检验数jx1x2x3x4x521000-1+ l00-2/15-1/61310-1/151/6 03011/50 0 x5x1x

31、2021-900-1/15-1/30当 l继续增大，原问题与对偶问题都保持可行解，故计算至此结束。结论： 01, x1= 3, x2= 3, maxZ= 9对偶线性规划4343【图示】目标函数Z(l)与l的变化关系图lZ(l)12l8.51522.59 l1, Z= 17/2+(1/2) ll1, Z= 9注：问题中多个参数变化时，应使目标函数z(l)是l的线性函数。对偶线性规划4444【例】求解下述参数线性规划问题 maxZ=（2+l l )x1 +(1+2l l )x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0 【解】按参数线性规划求解问题的第一、二步，令l0l0求得最优解，并将cj的变化值反映到最终单纯形表中。 对偶线性规划4545反映到最终单纯形表中Cj比值CBXBb检验数jx1x2x3x4x52+l1+2l00015/20 0 15/4-15/27/210 01/4-1/23/201 0-1/43/2x3x1x202+l1+2l-17/2 l 2l 0-1/4-1/2当 l时，表中解为最优解。此时当l ，变量x4的检验数为正值，用单纯形法继续迭代得z*7/2