运筹学课件第二章对偶理论与灵敏度

1、2021-9-231第二章第二章 对偶理论与灵敏度分对偶理论与灵敏度分析析2021-9-232 1 线性规划问题的对偶及其变换线性规划问题的对偶及其变换 1、线性规划对偶问题的提出 线性规划对偶理论是线性规划理论中一个非常重要和有趣的概念。 支持线性规划对偶理论的主要背景是，每个线性规划问题都有一个与之对应的对偶线性规划问题。 线性规划问题与其对偶线性规划问题在模型的表现形式和问题的解之间存在着许多联系。 我们先分析一个实际的线性规划模型与其对偶线性规划问题的经济意义。 2021-9-233 例 某工厂要用25个单位的A资源和15个单位的B资源生产4种产品，这4种产品的单位利润和对A资源和B资

2、源的单位消耗量如表所示。 问该工厂应如何安排生产才能使工厂的总利润最大?产 品 1产 品 2产 品 3 产 品 4A资 源 消 耗 量122-3B资 源 消 耗 量21-32单 位 利 润12-342021-9-234 现假设有一商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的? 从拥有资源的工厂来说，是否要出售资源A和资源B取决于商人给出资源A和资源B的价格。工厂出售资源A和资源B的条件是：出售A资源和B资源的收入应不低于用同等数量资源由自己组织生产相应产品时所获得的利润。设商人开出的A资源和B资源的单位价格分别为y1和y2，则工厂在满足什么条件时可出售A资源和B资源。2021-

3、9-235 一般的，原问题：max z = CX对偶问题：min w = Yb2、原问题与对偶问题AX b X 0YA C Y 02021-9-236一般: max问题第i个约束取“”，则min问题第i个变量 0 ； min问题第i个约束取“”，则max问题第i个变量 0 ； 原问题第i个约束取等式，对偶问题第i个变量 无约束； max问题第j个变量 0 ,则min问题第j个约束取“” ； min问题第j个变量 0 ，则max问题第j个约束取“” ； 原问题第j个变量无约束，对偶问题第j个约束取等式。2021-9-237 原问题（或对偶问题）原问题（或对偶问题） 对偶问题（或原问题）对偶问题（

4、或原问题） 目标函数目标函数 MaxZ目标函数目标函数 MinW约束条件数：约束条件数：m个个第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“=” 对偶变量数：对偶变量数：m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量 决策变量数：决策变量数：n个个第第j个变量个变量0第第j个变量个变量0第第j个变量是自由变量个变量是自由变量 约束条件数：约束条件数：n第第j个约束条件类型为个约束条件类型为“”第第j个约束条件类型为个约束条件类型为“”第第j个约束条件类型为个约束条件类型为“=”

5、2021-9-238例例 写出对偶问题写出对偶问题 max z = x1 + 2x2 + x3 2x1 + x2 6 2x2 + x3 8 x1,x2,x3 0对偶：min w = 6y1 + 8y2 2y1 1 y1 + 2y2 2 y2 1 y1,y2 02021-9-239 写出下述线性规划问题的对偶问题 1）2021-9-2310 2）2021-9-2311 3） 2021-9-23120.XbAXtsCXMaxZ)(NBCCC)(NBXXX)(),(21NBPPPAn2021-9-2313 1）由约束条件）由约束条件 bNXBXXXNBAXNBNB)(可得可得 NNBNXBbBNXb

6、BX111)(（2-1） 2021-9-2314）（得令22)()()(11111111NNBBNNNBNBNNNBBNNNBNNBBNBNBXbBCZNBCCXNBCCbBCXCNXBCbBCXCNXBbBCXCXCXXCCCXZ 2021-9-2315cjjTBXTNXTBCBXbB1BB1NB1jjCZNBCCBN1 CB XB xjbCB CN 0 2021-9-2316 2 对偶问题的性质对偶问题的性质 Dual property0 )max(0;,min)max(YCYAYbwYCYACYAYbww即0)min(XbAXCXw0 , ,min 0 , ,maxYCYAYbwXbAX

7、CXz 1、对称性 对偶问题的对偶为原问题.2021-9-23170)min(XbAXCXw证毕令0 max maxmax)min(XbAXCXzwzCXwww2021-9-2318.,:的可行解分别为原问题和对问题设证明YXXCXAYCAYCYAbYXAYbXAbAX证毕bYXCbYXAYXC bYXCYX ,. 2则存在为对偶问题的可行解为原问题的可行解设弱对偶性2021-9-2319 推论： (1) max问题任一可行解的目标值为min问题目标值的一个下界； (2) min问题任一可行解的目标值为max问题目标值的一个上界。2021-9-23203、无界性 若原问题(对偶问题)为无界解，

8、则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。2021-9-2321例如：例如：0,22212min21212121xxxxxxxxz无可行解无可行解0,221122max21212121yyyyyyyyw必有无界解。必有无界解。2021-9-2322 4、最优性 设X*，Y*分别为原问题和对偶问题可行解，当CX*=Y*b时， X*，Y*分别为最优解。证毕为最优解即为最优解即由弱对偶性题的任一可行解分别为原问题和对偶问设证明 * )2( ) 1 (.,:*YbYbYbYCXbYXCXXCCXbYXCYX2021-9

9、-2323 5、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标值相等。*11*1*1*1*11*0)(:, 0.:wbYbBCbBCCCXzbBXbBCbYwYBCYCAYCABCABCCXBNBBBBB则其目标值为因原问题最优解则为对偶问题的可行解若其中全部检验数可表示为则其对应的基矩阵存在为原问题的最优解设证明2021-9-2324Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕6、松弛性 若X*，Y*分别为原问题及对偶问题的可行解， 那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为 最优解。证明：0,0max:SSSXXbXAXXCXz设原问题为0,0

10、min:SSSYYCYYAYYbw设对偶问题为2021-9-23250,0maxSSSXXbXAXXCXz0,0minSSSYYCYYAYYbwXYYAXXYYACXzSS)(SSYXYAXXAXYYbw)(将b,Cb,C分别代入目标函数：;,0, 0,*为最优解时当为可行解若YXzwXYXYYXSS证毕必有则分别为最优解若另一方面0 , 0,*SSXYXYzwYX2021-9-2326【例】【例】 已知线性规划已知线性规划3 , 2 , 1, 0162210243max321321321jxxxxxxxxxxzj的最优解是的最优解是 求对偶问题的最优解。求对偶问题的最优解。TX)0 , 2

11、, 6(2021-9-2327【解】对偶问题是【解】对偶问题是0,1422321610min2121212121yyyyyyyyyyw422322121yyyyy1=1,y2=1, 对偶问题的最优解为对偶问题的最优解为Y=（1，1），最优值），最优值w=26。TX)0 , 2 , 6(2021-9-2328【例】【例】 已知线性规划已知线性规划 无约束321321321321, 0, 06422minxxxxxxxxxxxxz的对偶问题的最优解为的对偶问题的最优解为Y=（0，2），求原问题的最），求原问题的最优解。优解。2021-9-2329【解】【解】021264max2121212121y

12、yyyyyyyyyw无约束，2021-9-2330 x 1=5,x 3=1, 所以原问题的最优解为所以原问题的最优解为X=（5，0，1），最优值），最优值Z=12。643131xxxx因为因为y20，所以原问题第二个松弛变量，所以原问题第二个松弛变量 =0，而，而y1=0、y2= -2，松弛变量，松弛变量 故故x2=0, 1, 021SSyy2Sx2021-9-2331【例】【例】 证明下列线性规划无最优解：证明下列线性规划无最优解：3 , 2 , 1, 0324min32131321jxxxxxxxxxZj2021-9-23320, 0121134max212122121yyyyyyyyyw

13、将三个约束的两端分别相加得将三个约束的两端分别相加得而第二个约束有而第二个约束有y21，矛盾，故对偶问，矛盾，故对偶问题无可行解，题无可行解，因而原问题具有无界因而原问题具有无界解，即无最优解解，即无最优解。 212y【证】容易看出【证】容易看出X=（4，0，0）是一可行解，故问题可行。对）是一可行解，故问题可行。对偶问题偶问题2021-9-2333 例：已知线性规划问题例：已知线性规划问题 Min z = 2x1+3x2+5x3+2x4+3x5 s.t. x1+x2+2x3+x4+3x5 4 2x1-x2 +3x3 +x4+x5 3 xj 0 j=1,2,3,4,5 已知其对偶问题的最优解为

14、： y1=4/5, y2=3/5, z=5。 试用对偶理论找出原问题的最优解。2021-9-23347、原问题检验数与对偶问题解的关系 (1)原问题非最优检验数的负值为对偶问题的一个基解。 (2)原问题最优检验数的负值为对偶问题的最优解。 设原问题是 max z=CX; AX+XS=b; X,XS0 它的对偶问题是 min =Yb; YA-YS=C; Y,YS0 则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系见表1。2021-9-2335表1 对应关系YYYBCNBCCXXXSSBBNSNB21110YS1是对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩

15、余变量。 2021-9-2336证: 设B是原问题的一个可行基，于是A=(B,N)；原问题可以改写为max z=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS0 相应地对偶问题可表示为 min =Yb YB-YS1=CB (2-17) YN-YS2=CN (2-18)Y，YS1,YS20 这里YS=(YS1，YS2)。2021-9-2337 当求得原问题的一个解：XB=B-1b 其相应的检验数为CN-CBB-1N与 -CBB-1 现分析这些检验数与对偶问题的解之间的关系：令Y=CBB-1，将它代入(2-17)式，(2-18)式得 YS1=0, -YS2=CN-CBB-1N 证毕 2

16、021-9-2338 8 线性规划对偶问题的经济解释影子价格 线性规划对偶问题中线性规划对偶问题中yi的值代表对第的值代表对第i种资源的种资源的估价。这种估价是针对具体工厂的具体产品而存在估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为的一种特殊价格，称它为“影子价格影子价格”。 在完全市场经济的条件下，当某种资源的市场在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，产；而当某种资源的市场价高于企业影子价格时，企业的决策者应把已有的资源卖掉。企业的决策者

17、应把已有的资源卖掉。2021-9-2339 对偶单纯形法的基本思想对偶单纯形法的基本思想: 对偶单纯形法的基本思想是：从原规划的一个基本解基本解出发，此基本解不一定可行，但它对应着一个对偶可行解对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。3 对偶单纯形法对偶单纯形法2021-9-2340 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐

18、步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。2021-9-2341 应用前提：应用前提：有一个基，其对应的基满满足足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。2021-9-2342 1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=

19、r/akr那么 xr为进基变量,转4； 4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。 对偶单纯形法求解线性规划问题对偶单纯形法求解线性规划问题过程：过程：2021-9-2343 【例】【例】用对偶单纯形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 02021-9-2344解：max z = -2x1 - 3x2 - 4x3 + 0 x4 + 0 x5 - x1 - 2x2 - x3 + x4 = -1 -2x1 + x2 - 3x3 + x5 = -4 x1,x2,x3,x4

20、,x5 02021-9-2345-2-3-400CBXBbx1x2x3x4X50 x4-10 x5-4出出出x4,x5 0 最优最优解：最优解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0目标值：目标值：w* = -z* = 42021-9-2346例：求解线性规划问题：例：求解线性规划问题：Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + 3x3 4 x1 , x2 , x3 0 2021-9-2347 标准化：标准化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2

21、-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 02021-9-23482021-9-2349单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minmin0ikejejekaaa2021-9-23504 灵敏度分析灵敏度分析 一、灵敏度分析的含义和内容一、灵敏度分析的含义和内容 1、什么是灵

22、敏度分析？、什么是灵敏度分析？ 研究线性规划模型某些参数或限制量的变研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵化对最优解的影响及其程度的分析过程称为灵敏度分析。敏度分析。2021-9-23512 2、灵敏度分析的内容：、灵敏度分析的内容： 目标函数的系数变化对最优解的影响；目标函数的系数变化对最优解的影响；约束方程右端系数变化对最优解的影响；约束方程右端系数变化对最优解的影响； 约束方程组系数阵变化对最优解的影响约束方程组系数阵变化对最优解的影响 ； 回答两个问题回答两个问题2021-9-2352这些系数在什么范围内发生变化时，最优基这些系数在什么范围内发生变

23、化时，最优基不变（即最优解或最优解结构不变）？不变（即最优解或最优解结构不变）？系数变化超出上述范围时，如何用最简便的系数变化超出上述范围时，如何用最简便的方法求出新的最优解？方法求出新的最优解？二、二、 手工进行灵敏度分析的基本原则手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行；、在最优表格的基础上进行； 2、尽量减少附加计算工作量；、尽量减少附加计算工作量； 2021-9-2353njpBCcABCCNBCCjBjjBBNN, 2 , 1, 0 0 0 :111 或或最优性条件分析 变化对最优解的影响。j ,ijiacb0 :1bBXB可行性条件三、灵敏度分析三、灵敏度分析202

24、1-9-23541. ib资源 的变化TiTmiiiibbbbbbbbbbbb)0b 0 0() ( 21 bBbBbbBbBXB1111)(.,0 11这里用到可行性条件保持问题的最优性不变的变化范围求出由ibbBbB2021-9-2355例1 已知下述问题的最优解及最优单纯形表,0,124 164 82 00032max54321524132154321xxxxxxxxxxxxxxxxxz., ) 12使最优基不变的变化范围求 b. 4 )21时的最优解求b2021-9-2356最优单纯形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/40014200032

25、bBXBC5x4x3x2x1x1x5x2x14 Z)4 0 0 2 4(,*TX此时2021-9-235722216 1) :bbb解08/12/112/1204/101B2441216808/12/112/1204/101*bBXB由最优单纯形表得:2021-9-2358)(012bbBb221118/12/14/12440008/12/112/1204/10244)(bbbBbBbbB0008/22/44/4222bbb08/202/404/4222bbb.1682最优基不变b2021-9-2359TTbb)0 0 4()0 0 ( )214 44 28024400408/12/112/1

26、204/10244)(111bBbBbbB不可行!用对偶单纯形法计算2021-9-2360-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/2000-1/81/2102+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1bXBCB00032x23/4-2)(17 : . 0, 0, 2, 3, 4 :*5*4*3*2*1元目标值最优解zxxxxx2021-9-23612. jc价值系数 的变化.01分两种情况讨论进行分析根据最优性条件NBCCBNN1)kc非基变量价值系数 的变化kBkkpBCc1:原

27、检验数/ :kkkkkccccc变化kkkBkkkcpBCcc1/., 0 :/此时最优解不变令kkkkkcc2021-9-2362例2 求例1 c4的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x204c8/1)8/1(8/1444c由解:. 8/1 4时最优解不变即c2021-9-2363rc2 基变量价值系数的变化NBCCBNN1 原BBBCCC 若NBCNBCNBCCNBCCCBNBBNBBNN1111/ )( 则分析:)0 0 0( ) ( :21 rBmrBcCcccc

28、C其中.变化影响所有可见jrc2021-9-2364方法:.0 1/的变化范围求出令rBNNcNBC例3 求例1 c2的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x22021-9-2365解:0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2) 0 0( ),3 0 2(2cCCBB 1/8)- (-3/2) (43N ) (/4/3/n44414/433313/3pcpBcpcpBcBBBB

29、2021-9-236602232/120)c 0 0(232233/3cpcB08818/12/14/1)c 0 0(812244/4cpcB1322cc. 13 2时最优解不变即c2021-9-2367 3. i ja技术系数的变化kBkkpBCc1 原T1k k k 0) a 0( ) ( , lkkTmklkkkkkklllpaaappppaaaa若分析:.k 的变化讨论非基变量技术系数la2021-9-2368lklkakBkBkkkBkKpBCpBCcppBCc111 )( 则TlkmlkkBkapBC)00)(11 0lklkka令., 最优解不变时当lkkla2021-9-236

30、9例4 求例1 a24的变化范围,使最优解不变.解:242424241, 1aaaa) (0) 1/8 2/3( 3) 0 2(32111BBCB24242448181aa08181 244a令. , 1 24此时最优解不变a2021-9-2370 例5 在例1的基础上，企业要增加一个新产品,每件产品需2个台时，原材料A 6kg，原材料B 3kg，利润 5元/件，问如何安排各产品的产量，使利润最大？解：0,1234 1664 822 532max3213231321321xxxxxxxxxxxxxz532利润12340料B16604料A8221设备b则有为新产品生产的件数设,3x2021-9-

31、237131 )2pB计算25. 025 . 136208/12/112/1204/1031pB0453620 81 2353133pBCcB3 ) 1计算表明生产新品有利。2021-9-2372., ) 3331加入原最优表计算将pB2 ,53出基主元为入基 xx5/40-1/8-3/2001/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix32021-9-23735/40-1/8-3/2001/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500

32、032x28/34/28ix320-5/8-7/16-1/4000-1/8-3/163/4103/2311/21/4-10020-3/4-1/83/2011x12x5x4x3x2x1bXBCB500032x2ix3x35)(5 . 2 )(5 .16 . 2 , 2/3 , 1*3*2*1元增加元zxxx2021-9-23742021-9-23752021-9-2376 四、灵敏度分析举例：四、灵敏度分析举例：0,974)(3. .332max321321321321xxxxxxxxxtsxxxZ（原材料约束）劳动力约束引入非负的松弛变量引入非负的松弛变量x4,x5, 将该将该LP化为化为 标

33、准型：标准型：2021-9-23770,974)(3. .00332max543215321432154321xxxxxxxxxxxxxtsxxxxxZ（原材料约束）劳动力约束用表格单纯形法求解如下：用表格单纯形法求解如下：2021-9-2378 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 X1 X2 2 3 3/1 6/3 1 1 1 1 0 0 3 6 -1 1 3 6 X1 X5 2 0 0 1 1 -2 0 Cj -Zj 0 0 -1 -5/3 -1/3 Cj -Zj 2 3 3 0 0 Cj -Zj3/19/1 1 1 1 1 0 1 4 7 0 1 3 9

34、 X4 X5 0 0 j 2 3 3 0 0 x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 Cj b xj XB CB2021-9-23791、研究最优表格中的数据来源：、研究最优表格中的数据来源：（1）如果选）如果选B=（P1，P2）为初始可行基，）为初始可行基，能否从表格中直接看出能否从表格中直接看出B-1？N舍弃中间计算过程，舍弃中间计算过程，只考察初始表和最终表：只考察初始表和最终表：2021-9-2380N 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 X1 X2 2 3 0 0 -1 -5/3 -1/3 Cj -Zj 2 3 3 0

35、0 Cj -Zj3/19/1 1 1 1 1 0 1 4 7 0 1 3 9 X4 X5 0 0 j 2 3 3 0 0 x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 Cj b xj XB CB2021-9-23812、价值系数、价值系数C发生变化的情况：发生变化的情况：（1）当）当cj是非基变量的价值系数是非基变量的价值系数它的变它的变化只影响化只影响 一个检验数一个检验数。为什么？。为什么？j例：例：c3发生变化时，发生变化时， =c3-z3=c3-2（-1）+32=c3-40，3令令得得c34。即当。即当c34时，最优解不变；时，最优解不变；3否则否则 0,可使用

36、可使用原始单纯形法原始单纯形法继续迭代求出新继续迭代求出新的最优解。的最优解。2021-9-2382（2）当）当cj是基变量的价值系数是基变量的价值系数它的变化它的变化将影响所有非基变量的检验数将影响所有非基变量的检验数，为什么？，为什么？NBCCBNN1 当当cj变化时，如能保持变化时，如能保持 ，则当前解仍为，则当前解仍为最优解，最优解，否则否则可用可用单纯形法单纯形法继续迭代继续迭代求出新求出新的最优解的最优解。0N将将cj看作待定参数，令看作待定参数，令 01NBCCBNN解这解这n-m个不等式，可算出保持最优解不变个不等式，可算出保持最优解不变时时cj的变化范围的变化范围 ！2021

37、-9-2383例：当例：当c1发生变化时，仍用发生变化时，仍用c1代表代表x1的价值系的价值系数（看成待定参数），原最优表格即为：数（看成待定参数），原最优表格即为： 0 1 2 -1/3 1/3 cjxj CB XB b c1 3 3 0 0 X1 X2 X3 X4 X5 c1 3 X1 X2 1 21 0 -1 4/3 -1/3 CjCj -Zj-Zj 0 0 c1-3 1-4/3c1 1/3c1-1 2021-9-2384令所有检验数小于令所有检验数小于0，得不等式组：，得不等式组：0131034103111ccc解该不等式组得：解该不等式组得： 3431 c说明当说明当 时，最优解不变

38、。时，最优解不变。 3 , 4/31c当当c13时时,有有 ,可选可选x3或或 x5进基进基,x2出基出基.0131, 031513cc2021-9-23853、右端常数、右端常数b发生变化：发生变化： 当当bi发生变化时，将影响所有基变量的取值。发生变化时，将影响所有基变量的取值。为什么？为什么？：bBXB1保持保持B-1b0,当前的基仍为最优基，最优解的结构当前的基仍为最优基，最优解的结构不变（取值改变）；不变（取值改变）；（B-1b）i0,当前基为非可行当前基为非可行基基,但是仍保持为对偶可行基但是仍保持为对偶可行基,(为什么为什么?),可用对偶单纯可用对偶单纯形法求出新的最优解；形法求

39、出新的最优解；如何求出保持最优基不变如何求出保持最优基不变的的bi的范围的范围?把把bi看作待定参数看作待定参数,令令B-1b0,求解该不等式组即可；求解该不等式组即可；2021-9-2386 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 X1 X2 2 3 0 0 -1 -5/3 -1/3 Cj -Zj 2 3 3 0 0 Cj -Zj3/19/1 1 1 1 1 0 1 4 7 0 1 3 9 X4 X5 0 0 j 2 3 3 0 0 x1 x2 x3 x4 x5 Cj b xj XB CB仍然来看上例的最优表格：仍然来看上例的最优表格： 2021-9-23879

40、490330334333349313131349111011111bbbbbbbBb令该向量313131341B原原b1=3，现用待定参数，现用待定参数b1代替代替3，则最优表中的解答列应为：则最优表中的解答列应为： 若若b1的变化超出这个范围，则解答列中至少有一个元的变化超出这个范围，则解答列中至少有一个元素小于素小于0，可用对偶单纯形法迭代求出新的最优解。，可用对偶单纯形法迭代求出新的最优解。2021-9-23884、系数阵、系数阵A的元素发生变化：的元素发生变化：（1）增加）增加1个新变量：相当于系数阵个新变量：相当于系数阵A增加增加1列列 如开发出一种新产品，已知其有关工艺参数如开发出

41、一种新产品，已知其有关工艺参数（或消耗的资源量）和单位产品利润，设该种（或消耗的资源量）和单位产品利润，设该种产品的产量为产品的产量为xk，则，则ck和和Pk已知，需要进行已知，需要进行“是是否投产否投产”的决策。的决策。如例中欲增加产品如例中欲增加产品D，单件利润，单件利润为为c6=5千元，工时消耗与材料千元，工时消耗与材料消耗为消耗为 326P2021-9-2389相当于在原始表中增加相当于在原始表中增加1列列P6，则在最优表中，则在最优表中P6应变成应变成31353231313134616PBP相应的检验数：相应的检验数：323135) 3 , 2(5666166PCcPBCcBB在此基

42、础上继续迭代，直至求出最优解：在此基础上继续迭代，直至求出最优解：2021-9-2390 23 CB XB cj xjb j X1 X2 X3 X4 X5 X6 X1 X2 1 21/(5/3)2/(1/3) -Z -80 0 -1 -5/3 -1/3 2/3 5 3 X6X23/59/53/5 0 -3/5 4/5 -1/5 1-1/5 1 11/5 -3/5 2/5 0 -Z-42/5-2/5 0 -3/5 -11/5 -1/5 0 2 3 3 0 0 5 1 0 -1 4/3 -1/3 5/3 0 1 2 -1/3 1/3 1/3q CjCj -Zj-Zj0 0 -1 -5/3 -1/3 2/3CjCj -Zj-Zj2/5 0 -3/5 -11/5 -1/5 02021-9-2391说明新产品说明新产品D应于投产，新的生产计划应于投产，新的生产计划为为X*=(0,9/5,0,0,0,3/5)T,即生产即生产B产品产品5/9吨吨,生生产产D产品产品3/5吨吨,两种资源全部用完两种资源全部用完,可得到最可得到最大利润为大利润为8.4 (千元千元)( 42/5=8.4)。 如果算出的如果算出的60,说明新产品说明新产品D不宜投产不宜投产，否则会使产品总利润下降！，否则会使产品总利润下降！2021-9-2392 q 2021-9-2393 202