第2章对偶理论与灵敏度分析(5h)16

1、第二章第二章第二章 对偶理论与灵敏度分析对偶理论与灵敏度分析1线性规划的对偶问题2对偶问题的基本性质3影子价格4对偶单纯形法5现性规划问题的矩阵形式 6灵敏度分析第二章1线性规划的对偶问题线性规划的对偶问题1.1 对偶问题的提出1.2 对称形式下对偶问题的一般形式1.3 非对称形式的原对偶问题关系1.4 对偶问题的定义1.5 对偶关系对应表第二章项目项目I IIIII每天可用能力每天可用能力设备设备A A（h h）设备设备B B（h h）调试工序（调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21 1212maxxxz0,52426155.

2、2121212xxxxxxxst1.1 对偶问题的提出对偶问题的提出1线性规划的对偶问题线性规划的对偶问题如何组织生产，才能获得最大利润？假定有另一公司想把美佳公司的如何组织生产，才能获得最大利润？假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？产活动，出让自己的资源？32152415minyyyz0,12526.32132132yyyyyyyyts第二章max Z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn b1a21x1+ a22x2+ a2

3、nxn b2 am1x1+ am2x2+ amnxn bmxj 0(j=1,n)s.t.1.2 对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式1线性规划的对偶问题线性规划的对偶问题min w=b1y1+ b2y2+bmyma11y1+ a21y2+ am1ym c1a12y1+ a22y2+ am2ym c2 a1ny1+ a2ny2+ amnym cnXj 0(j=1,m)s.t.CXz max0.XbAXstbYwTmin0.YCYAstTT第二章1.3 1.3 对偶对应表对偶对应表1线性规划的对偶问题线性规划的对偶问题第二章maxZ= 5X1 +6X2 3X1 -2X2 =74

4、X1 +X2 9X1 , X2 01线性规划的对偶问题线性规划的对偶问题maxZ= 5X1 +6X2 3X1 -2X2 7-3X1 +2X2 -74X1 +X2 9X1 , X2 0y1y1 y23y1 -3y1 +4y2 5 -2y1 +2y1 +y2 6y1 , y1 , y2 0minW=7y1 -7y1 +9y2minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1自由 , y2 0第二章2对偶问题的基本性质对偶问题的基本性质一、对称性对称性 二、弱对偶性弱对偶性三、无界性无界性 四、可行解是最优解的性质可行解是最优解的性质五、对偶定理对偶定理六、松紧定理六、松紧定理

5、第二章一、对称性一、对称性 ： 对偶问题的对偶是原问题对偶问题的对偶是原问题2. 对偶问题的基本性质对偶问题的基本性质二、弱对偶性：二、弱对偶性：若x是原问题的可行解，y是对偶问题的可行解。则有 cxyb 推论（推论（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。（若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。（

6、3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界，反之对若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界，反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。三、最优性：三、最优性：设x是原问题的可行解，y是对偶问题的可行解.当cx=yb时 x, y是最优解。四、四、 强对偶性（对偶定理）：强对偶性（对偶定理）：若原问题及其对偶问题均具有可行解，则两者均具有最优解且它们最优解的目标函数值相等。五、互补松弛性（松紧定理）五、互补松弛性（松紧定理）在线性规划问题的最优解中，如果对应某一约束条件

7、的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。第二章0324min32131321ixxxxxxxxx2. 对偶问题的基本性质对偶问题的基本性质故无最优解。原问题是无界的，对偶问题不可行，因而考虑其对偶问题为其一可行解。证明：0,121134max)0 , 0 , 4(212122121yyyyyyyyyzx1.证明数学模型无最优解第二章025357162954max321321321ixxxxxxxxxxz2、考虑问题回答：1 ）说明原问题和对偶问题都有最优解.2 ）求原问题和对偶问题的最优目标函数值的一个上界和下界.2. 对偶问题的基

8、本性质对偶问题的基本性质0,93255472516min2121212121yyyyyyyyyy1）解：原问题有可行解（0,0,8）对偶问题有可行解（5,0）强对偶性定理则有最优解8072.80)0 , 5(;72)8 , 0 , 0(2*zzyzx下界。有上数值由弱对偶性最优目标函有对于对偶问题的可行解有）对于原问题的可行解第二章02023220322432max432143214321ixxxxxxxxxxxxxz0,42333222122020min212121212121yyyyyyyyyyyy2. 对偶问题的基本性质对偶问题的基本性质3、线性规划问题有最优解（0,0,4,4）最优值2

9、8。用互补松弛定理计算对偶问题的最优解。最优值。为对偶问题的最优解和；对应目标函数值为对偶问题的可行解，经检验解得有由有根据互补松弛定理，由285/1, 5/6285/1, 5/65/1, 5/6423043320421*2121214213yyzyyyyyyxyyx解：原问题的对偶问题为第二章3影子价格影子价格式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi*的意义代表在资源最优利用条件下对单位第i仲资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格(shadow price)。njmiiijjwybxc

10、z11*miiiybz1*iiybz求导 这说明影子价格的值相当于在资源得到最优利用的生产条件下，b每增加一个单位时目标函数Z的增量。 关于影子价格的几点说明： 1）影子价格是未知数,有赖于资源的利用情况。 2）影子价格是一种边际价格。第二章原问题变量松弛变量XB bx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2对偶问题的剩余变量对偶问题变量y4y5y1y2y3例1ABC15/200资源剩余01/41/2影子价格543210002maxxxxxxz)5,.,1(05242615552142132jx

11、xxxxxxxxj3影子价格影子价格第二章（15/4，5/4）z=8.75（3，3）z=9BAC（7/2，3/2）z=8.5所以第2种资源的影子价格为0.25，第3种资源的影子价格为0.5。3影子价格影子价格第二章3）资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，可以根据影子价格与市场价格的关系确定资源的买进或卖出。4）生产过程中如果某种资源末得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。3影子价格影子价格 5）单纯形表中各个检验数的经济意义。当产品产值大于隐含成本时，表明生产该项产品有利，可在计划中安排，否则这些资源来生产别的

12、产品更为有利，就不在计划中安排。这就是单纯形表中各个检验数的经济意义。 6）对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价。miiijjjBjjyacPBCc11第二章对偶单纯形法的基本思路对偶单纯形法的基本思路：先找出一个对偶问题的可行基，并保持对偶问题为可行解条件下，如不存在XB o，通过变换到一个相邻的目标函数值较小的基本解(因对偶问题是求目标函数极小化)，并循环进行，一直到原问题也为可行解(即XB o)，这时对偶问题与原问题均为可行解。在迭代过程中保持原问题的检验数为非正，逐步替换负基变量，从而得到最优解。4对偶单纯形法对偶单纯形法第二章对偶

13、单纯形法的计算步骤：对偶单纯形法的计算步骤： 1. 列出初始单纯形表，且检验数非正。 为换出变量。对应的基变量按rriiixbBbBbB1110min. 2为换入变量确定按srsssrjrjjjxazcaazc0min. 34对偶单纯形法对偶单纯形法4.以ars为主元素，进行迭代变换。5 . 返 2，直到B 0为止。原始单纯形法 按列选主元 对偶单纯形法 按行选主元第二章例5：用对偶单纯形法求解下列问题02225324. .23min321321321321321xxxxxxxxxxxxtsxxxz02225324. .23min654321632153214321321xxxxxxxxxxx

14、xxxxxxxtsxxxz4对偶单纯形法对偶单纯形法第二章02225324. .23max654321632153214321321xxxxxxxxxxxxxxxxxxtsxxxzCj321000CBXBbx1x2x3x4x5x60 x441111000 x552310100 x62221001 j=cj-zj4对偶单纯形法对偶单纯形法第二章Cj321000CBXBbx1x2x3x4x5X60 x417/31/302/31-1/30-2x25/3-2/31-1/30-1/300X6-16/3-2/30-1/302/31 j=cj-zjCj321000CBXBbx1x2x3x4x5X60 x41

15、7/31/302/31-1/30-2X25/3-2/31-1/30-1/300X6-16/3-2/30-1/302/31 j=cj-zj-13/30-5/30-2/304对偶单纯形法对偶单纯形法第二章Cj321000CBXBbx1x2x3x4x5X60 x4-5-10011/32-2X270100-1-1-1X3162010-2-3 j=cj-zj-1000-7/3-5Cj321000CBXBbx1x2x3x4x5X6-3x15100-1-1/3-2-2X270100-1-1-1X360012-21 j=cj-zj000-1-5-74对偶单纯形法对偶单纯形法第二章已获得最优解：（x1, x2,

16、 x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35对偶问题的最优解为：（w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=354对偶单纯形法对偶单纯形法第二章 从以上计算可以看出，用对偶单纯形法求解线性规划问题时，当约束条件为“”时，不必引进人工变量，使计算简化。但在初始单纯形表中其对偶问题应是基可行解这点，对多数线性规划问题很难实现。因此对偶单纯形法一般不单独使用，而主要应用于灵敏度分析及整数规划等有关章节中。4对偶单纯形法对偶单纯形法第二章对偶单纯形法的优点：对偶单纯形法的优点： 1 简化计算 2 减少

17、计算量 3 灵敏度分析缺点：缺点： 第一个正则解很难找到4对偶单纯形法对偶单纯形法第二章单纯形法计算的矩阵描述单纯形法计算的矩阵描述对称形式线性规划问题的矩阵表达式加上松弛变量后为：5单纯形法的矩阵描述单纯形法的矩阵描述) ,(21mnnnSxxxX上式中XS为松弛变量 I 为mm单位矩阵通过迭代后: X=XB + XN相应地: C=CB + CN系数矩阵 : A= B + N参1-1050, 00maxSSSXXbIXAXXCXZSBNBNBSNNSNBSNNBBSNBXIBCXNBCCbBCZXXCIXBNXBbBCZXXCXCZbBIXBNXBBXB)0()(0)(01111111111

18、第二章5单纯形法的矩阵描述单纯形法的矩阵描述参1-1050, 00maxSSSXXbIXAXXCXZ0000)0()(0)(01111111111111111BBCCIBCNBCCXIBCXNBCCbBCZXXCIXBNXBbBCZXXCXCZbBIXBNXBXbBIXBNXBBXBBBBBNSBNBNBSNNSNBSNNBBSNBSNB第二章迭代后新的单纯形表为：初始单纯形表：非基变量基变量XB XN XS0 XS bB NIcj-zjCB CN0基变量非基变量XB XN XSCB XB B-1bI B-1N B-1cj-zjCB- CBB-1BCN- CBB-1N -CBB-1C- CBB

19、-1A5单纯形法的矩阵描述单纯形法的矩阵描述第二章可以看出：(1)对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1 ；(2)初始单纯形表中基变量Xsb，迭代后的表中 XB=B1b ；(3)初始单纯形表中约束系数矩阵为A，I B，N，I ，迭代后的表中约束系数矩阵为B-1A，B-1IB-1B，B-1N，B-1I I，B-1N，B-1 ；(4)若初始矩阵中变量Xi的系数向量为Pj，迭代后为Pj，则有Pj=B-1Pj 。5单纯形法的矩阵描述单纯形法的矩阵描述第二章当B为最优基时因xB的检验数可写为 CB- CBI=0CBB-1称为单纯形乘子，若令Y= CBB-1 ，则所以0YCAY0YCY

20、ACN- CBB-1N 0 -CBB-1 0C- CBB-1A 0 -CBB-1 05单纯形法的矩阵描述单纯形法的矩阵描述第二章6灵敏度分析灵敏度分析灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。A，b，C当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变。这就是灵敏度分析所要研究解决的问题。单纯形法的迭代计算是从一组基向量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改变，因此有可能把个别参数的变化直接在计算得到最优解的最终单纯形表上反映出来。第二章 灵敏度分析的步骤灵敏度分析的步骤1将参数

21、的改变计算反映到最终单纯形表上来2检查原问题是否仍为可行解；3检查对偶问题是否仍为可行解；4按下表所列情况得以结论和决定继续计算的步骤。6灵敏度分析灵敏度分析原问题对偶问题结论或继续计算的步骤可行解可行解最优解可行解非可行解用单纯形法求解最优解非可行解可行解用对偶单纯形法求解最优解非可行解非可行解引入人工变量求解最优解第二章6灵敏度分析灵敏度分析(1)若家电I的利润降至1. 5元件，而家电的利润增至2元件时，美佳公司最优生产计划有何变化?Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2 j=cj-

22、zj000-1/4-1/2变量系数Cj的变化仅仅影响到检验数(Cj-Zj)约变化。一、分析一、分析Cj的变化的变化第二章6灵敏度分析灵敏度分析解 (1)将家电I，II的利润变化直接反映到最终单纯形表中。Cj1.52000CBXBbX1x2x3x4x50 x315/20015/4-15/21.5x17/21001/4-1/22x23/2010-1/43/2 j=cj-zj0001/8-9/4以x4为换入变量,x3为换出变量，列新单纯形表。Cj1.52000CBXBbx1x2x3x4x50 x46004/51-61.5x1210-1/5012x23011/500 j=cj-zj00-1/10 0-

23、3/2所有检验数为非正，问题得到最优解：X（2，3，0，6，0）第二章6灵敏度分析灵敏度分析(2)若家电I的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化？设家电II的利润为(1十)元，反映到最终单纯形表中为：Cj21十000CBXBbx1x2x3x4x50 x460015/4-15/22x121001/4-1/21十x23010-1/43/2 j=cj-zj000-1/4+1/4 -1/2-3/2 为使表中的解仍为最优解，应有即家电II的利润C2的变化范围应满足：第二章二、分析二、分析bi的变化的变化右端项bj的变化在实际问题中反映为可用资源数量的变化。6灵

24、敏度分析灵敏度分析Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2 j=cj-zj000-1/4-1/2解：因为：080b22100802/ 34/ 102/ 14/ 102/154/ 511bBb(1)若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化?第二章以X2为换出变量，X4为换入变量，列新单纯形表得：问题的最优解：X（5，0，15，2，0）Cj21000CBXBbx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-

25、1/21x2-1/2010-1/43/2 j=cj-zj000-1/4-1/2Cj21000CBXBbx1x2x3x4x50 x315051002x15110011x420-401-6 j=cj-zj0-100-26灵敏度分析灵敏度分析第二章单纯形表中b列数字为：(2)若设备A和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变?设调试工序每天可用能力为（5+）小时，因有2321215002/ 34/ 102/ 14/ 102/154/ 511bBb23232127215215b当b 0时问题的最优基不变，解得：-1 1因此调试工序的能力应在4小时-6小时之间。6灵敏度分析

26、灵敏度分析第二章三、增加一个变量三、增加一个变量xj的分析的分析增加一个变量在实际问题中反映为增加一种新的产品。其分析步骤为：miiijjjjjyaczc1*计算. 1jjPBP1计算. 23.若 ，原最优解不变，只需将计算得到的 和 直接写入最终单纯 形表中；若 ，则按单纯形法继续迭代计算找出最优。0jjPj0j6灵敏度分析灵敏度分析第二章在美佳公司例子中，设该公司又计划推出新型号的家电III，生产一件所需设备A、B及调试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3元件。试分析该种产品是否值得投产，如投产，对该公司的最优生产汁划有何变化。1243)21,41, 0(32072

27、432/ 34/ 102/ 14/ 102/154/ 516P解：设该公司生产家电III 件，有TPc)2 , 4 , 3(, 3666灵敏度分析灵敏度分析第二章以x2 为换出变量， x6 为换入变量，列新单纯形表得：Cj210003CBXBbx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22 j=cj-zj000-1/4-1/216灵敏度分析灵敏度分析第二章问题的最优解：X（7/2，0，51/4，0，0，3/4）T。所以，该公司新的生产计划应为每天生产家电I 7/2件，生产家电III 3/4件。Cj21000

28、3CBXBbx1x2x3x4x5x60 x351/407/213/8-9/402x17/21001/41/203x63/401/20-1/83/41 j=cj-zj0-1/20-1/8-5/406灵敏度分析灵敏度分析第二章四、分析参数四、分析参数aij的变化的变化 aij的变化使线性规划的约束系数矩阵A发生变化。若变量xj在最终单纯形表中为非基变量，其约束条件中系数aij的变化分析步骤可参照本节之三；若变量xi在最终单纯形表中为基变量，则aij的变化将使相应的B和B-1 发生变化因此有可能出现原问题和对偶问题均为非可行解的情况。出现这种情况时，需引进入工变量将原问题的解转化为可行解，再用单纯形

29、法求解。6灵敏度分析灵敏度分析第二章若家电II每件需设备A，B和调试工时变为8小时、4小时、1小时，该产品的利润变为3元/件，试重新确定该公司最优生产计划。解：将生产工时变化后的新家电II看作是一种新产品，生产量为x2。2/3148)21,41, 0(322/ 12/ 12/111482/ 34/ 102/ 14/ 102/154/ 512P6灵敏度分析灵敏度分析第二章因x2已变换为x2 ，故用单纯形算法将x2替换出基变量中的x2 ，并在单纯形表中不再保留x2。Cj213000CBXBbx1x2x2x3x4x50 x315/20011/215/4-15/22x17/2101/201/4-1/2

30、1x23/2011/20-1/43/2 j=cj-zj003/20-1/4-1/2Cj23000CBXBbx1x2x3x4x50 x3-90014-242x121001/2-23x2 30101/23 j=cj-zj0001/2-56灵敏度分析灵敏度分析第二章增加人工变量。Cj23000CBXBbx1x2x3x4x50 x3-90014-242x121001/2-23x2 30101/23 j=cj-zj0001/2-5Cj23000-MCBXBbx1x2x3x4x5x6-Mx3900-1-42412x121001/2-203x2 30101/230 j=cj-zj00-M1/2-4M-5+2

31、4M0X3+ 4X4 - 24X5= -96灵敏度分析灵敏度分析第二章美佳公司的最优生产计划为每天生产家电I 11/4件，新家电II 15/8件。Cj23000-MCBXBbx1x2x3x4x5x60 x53/800-1/24-1/611/242x111/410-1/121/301/123x2 15/8011/800-1/8 j=cj-zj00-5/24-2/30-M-5/246灵敏度分析灵敏度分析第二章五、增加一个约束条件的分析五、增加一个约束条件的分析 增加一个约束条件在实际问题中相当增添一道工序。从图形（二维）上分析相当于增加了一条直线。分析的方法是先将原问题最优解的变量值代入新增的约束条件。如满足，说明新增的约束未起到限制作用，原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进步分析。6灵敏度分析灵敏度分析第二章设家电I，II经调试后，还需经过道环境试验工序。家电I每件须环境试验3小时，家电II每件2小时，又环境试验工序每天生产能力为12小时试分析增加该工序后的美佳公司最优生产计划。解：先将原问题的最优解x1 =7/2, x2 =3/2代入环境试验工序的约束条件： 3x1 +2 x2 12。因为37/2 + 23/2 12，故原问题最优解不是本例的最优解。6灵敏度分析灵敏度分析第二章在试验工序中加入松驰变量得：3X