《运筹学对偶灵敏》由会员分享，可在线阅读，更多相关《运筹学对偶灵敏（42页珍藏版）》请在金锄头文库上搜索。
1、第第3 3章章 对偶理论和灵敏度分析对偶理论和灵敏度分析v对偶理论对偶理论(Dual Theory)v灵敏度分析灵敏度分析(Sensitivity Analysis)s.tv用矩阵形式表示用矩阵形式表示v原问题：原问题：s.tv对偶问题：对偶问题：min = YbAYCY0max Z = CXAXbX0项目项目原问题原问题对偶问题对偶问题系数矩阵系数矩阵A约束系数矩阵约束系数矩阵约束系数矩阵的转置约束系数矩阵的转置右端常数右端常数b约束条件的右端项向量约束条件的右端项向量目标函数中价格系数向量目标函数中价格系数向量系数列系数列C目标函数中价格系数向量目标函数中价格系数向量约束条件的右端项向量约
2、束条件的右端项向量目标函数目标函数max Z = CXmin = Yb约束条件约束条件AXbAYC决策变量决策变量X0Y0原问题原问题(或对偶问题或对偶问题)对偶问题对偶问题(或原问题或原问题)max Zmin约束条件数约束条件数m个个第第i个约束条件：个约束条件：“” “” “ = ”对偶变量数对偶变量数m个个第第i个对偶变量：个对偶变量：“yi0” “yi0” yi为自由变量为自由变量决策变量数决策变量数n个个第第j个对偶变量：个对偶变量：“xj0” “xj0” xj为自由变量为自由变量约束条件数约束条件数n个个第第j个约束条件：个约束条件：“” “” “ = ”v原问题与对偶问题的关系原
3、问题与对偶问题的关系在形式上可归结为表在形式上可归结为表3.4 3.4 对偶问题的基本性质对偶问题的基本性质s.tv原问题：原问题：s.tv对偶问题：对偶问题：min = YbAT YCT Y0max Z = CXAXbX0v(1). 对称性：对称性：对偶问题的对偶问题是原问题。对偶问题的对偶问题是原问题。即原问题和对偶问题之间是互为对偶的。即原问题和对偶问题之间是互为对偶的。v证明：（略）证明：（略）v(2). 弱对偶性：弱对偶性：设设X# #、Y# #分别是原问题和对偶分别是原问题和对偶问题的可行解，则有问题的可行解，则有CX# #Y# #b。v证明：（略）证明：（略）v从弱对偶性可知，原
4、问题从弱对偶性可知，原问题(极大化问题极大化问题)的任意的任意一个可行解所对应的目标函数值是其对偶问题一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。最优目标函数值的一个下界。v对偶问题对偶问题(极小化问题极小化问题)的任意一个可行解所对的任意一个可行解所对应的目标函数值是其原问题最优目标函数值的应的目标函数值是其原问题最优目标函数值的一个上界。一个上界。v原问题任一可行解对应的目标函数值不大于其原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值。对偶问题的任一可行解对应目标函数值。v(3). 无界性：无界性：若原问题可行，但目标函数无上若原问题可行，
5、但目标函数无上界，则对偶问题无可行解。界，则对偶问题无可行解。v若对偶问题可行，但目标函数无下界，则原问若对偶问题可行，但目标函数无下界，则原问题无可行解。题无可行解。v证明：（略）证明：（略）v(4). 最优性：最优性：设设X# #、Y# #分别是原问题和对偶问分别是原问题和对偶问题的可行解，则当题的可行解，则当CX# #=Y# #b时，时， X# #、Y# #分别分别为原问题和对偶问题的最优解为原问题和对偶问题的最优解X* *、Y* * 。v证明：（略）证明：（略）v(5).强对偶性：强对偶性：若原问题和对偶问题之一有最优若原问题和对偶问题之一有最优解，则另一个问题也一定有最优解，且目标函
6、解，则另一个问题也一定有最优解，且目标函数值相等。数值相等。v证明：（略）证明：（略）v从强对偶性可知，若原问题有一个对应于基从强对偶性可知，若原问题有一个对应于基B的的最优解，则最优解，则CBB-1就是对偶问题的一个最优解，就是对偶问题的一个最优解，并且两个问题的最优值相等。并且两个问题的最优值相等。v另外，原问题获得最优解时，其松弛变量对应另外，原问题获得最优解时，其松弛变量对应的检验数的相反数的检验数的相反数CBB-1 ，就是对偶问题的最优，就是对偶问题的最优解。该性质常被称为解。该性质常被称为主对偶定理主对偶定理。vCBB-1称为单纯形乘子称为单纯形乘子。v(6).互补松弛性：互补松弛
7、性：该性质常被称为该性质常被称为对偶问题的松对偶问题的松紧定理紧定理。v(7). 对应性：对应性：原问题对应其可行基的检验数的原问题对应其可行基的检验数的相反数是对偶问题的一个基解。相反数是对偶问题的一个基解。v证明：（略）证明：（略）v从性质从性质7可知，用单纯形法求解可知，用单纯形法求解LP问题时，迭代的每问题时，迭代的每一步在得到原问题的一个基可行解的同时，其一步在得到原问题的一个基可行解的同时，其检验数检验数行的各检验数对应于对偶问题的一个基解，它们之间行的各检验数对应于对偶问题的一个基解，它们之间仅差一个负号。仅差一个负号。v在单纯形表中，在单纯形表中，原问题的松弛变量对应于对偶问题
8、的原问题的松弛变量对应于对偶问题的变量，对偶问题的剩余变量对应于原问题的变量；变量，对偶问题的剩余变量对应于原问题的变量；这这些互相对应的变量，如果在一个问题的解中是基变量，些互相对应的变量，如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。则在另一个问题的解中是非基变量。v原问题与对偶问题之间的变量对应关系见表原问题与对偶问题之间的变量对应关系见表3-5。原问题的变量原问题的变量基变量基变量XB非基变量非基变量XN松弛变量松弛变量Xs对应于可行基对应于可行基B的检验数的检验数0CN-CBB-1N-CBB-1对偶问题的变量对偶问题的变量-Ys1-Ys2-Yv表表3-5的进一步说明：
9、用单纯形法求解的进一步说明：用单纯形法求解LP问题时，原问问题时，原问题的题的检验数行的各检验数对应于对偶问题的一个基解，检验数行的各检验数对应于对偶问题的一个基解，它们之间仅差一个负号。它们之间仅差一个负号。v在单纯形表中，在单纯形表中，原问题的松弛变量原问题的松弛变量(Xs)对应于对偶问题对应于对偶问题的变量的变量(-Y)，对偶问题的剩余变量对偶问题的剩余变量(-Ys1、 -Ys2)分别对应分别对应于原问题的变量于原问题的变量(XB、XN) 利用这种对应关系，利用这种对应关系，只需只需求解其中一个问题，就可以求解其中一个问题，就可以从从原问题原问题最终单纯形表中同最终单纯形表中同时得到其对
10、偶问题的最优解时得到其对偶问题的最优解，而不须求解过程。，而不须求解过程。v以上这些互相对应的变量，如果在以上这些互相对应的变量，如果在一个一个问题的解中问题的解中是是基变量基变量，则在，则在另一个另一个问题的解中问题的解中是非基变量是非基变量。v根据上述的一些性质，互为对偶的两个根据上述的一些性质，互为对偶的两个LP问题之间问题之间的解有以下几种情况，见表的解有以下几种情况，见表3-6。原问题原问题对偶问题对偶问题有最优解有最优解有可行解，但目标函数无界有可行解，但目标函数无界无可行解无可行解无可行解无可行解有最优解有最优解无可行解无可行解有可行解，但目标函数无界有可行解，但目标函数无界无可
11、行解无可行解v例例3-4：求解下列：求解下列LP问题。问题。v max Z = x1 + x2s.t. -x1 + x2 + x3 2-2x1 + x2 - x3 1x1，x2 ，x3 0v解：由于解：由于X=(0,0,0)T满足满足s.t.，所以，所以X=(0,0,0)T为为可行解。现写出其对偶问题如下可行解。现写出其对偶问题如下v min = 2y1 + y2s.t. -y1 - 2y2 1 x10 y1 + y2 1 x20 y1 - y2 0 x30 y1 ，y2 0 第第i个约束条件个约束条件(1)(2)v由于第一个约束条件由于第一个约束条件-y1-2y21是矛盾不等式，是矛盾不等式
12、，v所以对偶问题所以对偶问题(2)无可行解。无可行解。v根据对偶问题的强对偶性可知，若原问题根据对偶问题的强对偶性可知，若原问题(1)有最优解，则对偶问题有最优解，则对偶问题(2)一定也有最优解。一定也有最优解。v因此，原问题因此，原问题(1)不可能有最优解，但是，原不可能有最优解，但是，原问题问题(1)有可行解，有可行解，v所以原问题所以原问题(1)无有限最优解，即目标函数无无有限最优解，即目标函数无上界。上界。v对偶问题的解在经济学上称为原问题的资源的影子价对偶问题的解在经济学上称为原问题的资源的影子价格，为什么呢？格，为什么呢？v单纯形表中目标值为：单纯形表中目标值为：z = CBB-1
13、bv检验数为：检验数为：N= CNCBB-1Nv其中都有乘子其中都有乘子Y=CBB-1，Y的经济学意义是什么？的经济学意义是什么？第第5节节 影子价格（影子价格（shadow price）v假设假设X*和和Y*分别是原问题和对偶问题的最优解，由分别是原问题和对偶问题的最优解，由主对偶定理，相应的目标函数值相等，即：主对偶定理，相应的目标函数值相等，即：v z*=CX*=Y*b=*v因此，因此，y*i实际上表示原问题约束条件中第实际上表示原问题约束条件中第i种资种资源增加一个单位时，目标函数最优值的改变量。源增加一个单位时，目标函数最优值的改变量。v这就是说，这就是说，影子价格就是对系统中的各个
14、资源影子价格就是对系统中的各个资源的使用价值的一个定量分析的使用价值的一个定量分析，它是原问题目标，它是原问题目标函数对某种资源的一阶偏导数。函数对某种资源的一阶偏导数。v从最终单纯形表可知，第从最终单纯形表可知，第i种资源的影子价格就种资源的影子价格就是对应的原问题松弛变量的检验数的相反数。是对应的原问题松弛变量的检验数的相反数。v第第2章例章例1的最终单纯形表的最终单纯形表(P41)v max z = 2x1 + 3x2cj23000CBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/8 0-z-1400-3/2 -1/8 0v从最终单纯形表
15、可知，第从最终单纯形表可知，第i种资源的影子价格就种资源的影子价格就是对应的原问题松弛变量的检验数的相反数。即是对应的原问题松弛变量的检验数的相反数。即y1*=3/2，y2*=1/8，y3*=0。 x1 + 2x2 84x1 16 4x2 12x10，x2 0max Z = 2x1 + 3x2 x1 + 2x2 84x1 16 4x2 12x10，x2 0s.t.x2x1O11223344x1+2x2=84x1=164x1=12Q1Q2Q3Q4v图图2-1，y1*=3/2，y2*=1/8，y3*=0。x1+2x2=92x1+3x2=142x1+3x2=15.5Q2。max Z = 2x1 +
16、3x2 x1 + 2x2 84x1 16 4x2 12x10，x2 0s.t.x2x1O11223344x1+2x2=84x1=164x1=12Q1Q2Q3Q4v图图3-1，y1*=3/2，y2*=1/8，y3*=0。2x1+3x2=142x1+3x2=14.125Q2”4x1=17。v以上可知，以上可知，资源的影子价格资源的影子价格是针对具体生产或具体企是针对具体生产或具体企业而言的；它对于拥有资源的决策者有非常重要的作业而言的；它对于拥有资源的决策者有非常重要的作用：用：v(1) 影子价格影子价格ri 0，可，可增加这种资源来收益，或降低这增加这种资源来收益，或降低这种资源的消耗来收益。种
17、资源的消耗来收益。企业内部可以挖潜的方向。企业内部可以挖潜的方向。v(2)对企业外部，按影子价格制定外协加工的收费标准。对企业外部，按影子价格制定外协加工的收费标准。v(3) 当某种资源的影子价格当某种资源的影子价格ri高于资源的市场价格时，高于资源的市场价格时，生产活动具有经济效益，并可购买增加这种资源来收生产活动具有经济效益，并可购买增加这种资源来收益。否则，可出售这种资源，从而在生产上获得利润。益。否则，可出售这种资源，从而在生产上获得利润。第第6节节 对偶单纯形法对偶单纯形法v对偶单纯形法并不是解对偶问题的单纯形法，对偶单纯形法并不是解对偶问题的单纯形法，而是根据对偶问题的特点和对称性
18、，设计出而是根据对偶问题的特点和对称性，设计出的一种解法。的一种解法。v对偶问题的对应性告诉我们，对偶问题的对应性告诉我们，原问题可行基原问题可行基所对应的检验数的相反数所对应的检验数的相反数 = 对偶问题的一个对偶问题的一个基解基解。但这个基解不一定是可行解。但这个基解不一定是可行解。v经过迭代，当原问题在经过迭代，当原问题在单纯形表上的全部单纯形表上的全部检检验数变成非正时，得到原问题的最优解。这验数变成非正时，得到原问题的最优解。这时，检验数的相反数即是对偶问题的一个基时，检验数的相反数即是对偶问题的一个基可行解。由主对偶定理可知，这个对偶问题可行解。由主对偶定理可知，这个对偶问题的基可
19、行解就是对偶问题的最优解。的基可行解就是对偶问题的最优解。v对偶单纯形法的基本思路：对偶单纯形法的基本思路：1.基于对偶问题的对称性，在每次迭代中保持基于对偶问题的对称性，在每次迭代中保持对偶问题的解是可行解，而不管原问题所获对偶问题的解是可行解，而不管原问题所获得的基解是否为可行解。得的基解是否为可行解。2.但是，当原问题所获得的基解为可行解时，但是，当原问题所获得的基解为可行解时，则这个基可行解就是原问题最优解。则这个基可行解就是原问题最优解。v在具体求解过程中，在具体求解过程中，对偶单纯形法是在原问对偶单纯形法是在原问题的单纯形表上进行对偶处理的题的单纯形表上进行对偶处理的。这种解法。这
20、种解法对于需要引入人工变量构造基进行求解是一对于需要引入人工变量构造基进行求解是一种改进，因为它可以种改进，因为它可以不用引入不用引入人工人工变量变量就能就能求得解，因此计算简便。求得解，因此计算简便。v例例2-g：用对偶单纯形法求解下列：用对偶单纯形法求解下列LP问题。问题。v min = y1 + 3y2s.t. 1/3y1 + 1/3y2 2 1/3y1 + 4/3y2 3 1/3y1 + 7/3y2 1y1 ，y2 0 max = - y1 - 3y2 -1/3y1 - 1/3y2 +y3 = -2-1/3y1 - 4/3y2 +y4 = -3-1/3y1 - 7/3y2 +y5 =
21、-1y1 ，y2 ，y3 ，y4 ，y5 0s.t.解：解：原问题的对偶问题：原问题的对偶问题：max Z=2x1+3x2+x31/3x1+1/3x2+1/3x311/3x1 +4/3x2+7/3x33x1, x2, x3 0 max = - y1 - 3y2 -1/3y1 - 1/3y2 +y3 = -2-1/3y1 - 4/3y2 +y4 = -3-1/3y1 - 7/3y2 +y5 = -1y1 ，y2 ，y3 ，y4 ，y5 0CBYBb-1-3000y1y2y3y4y50y3-2-1/3-1/31000y4-3-1/3(-4/3)0100y5-1-1/3-7/3001-0-1-300
22、0比比值值i i39/40y3-5/4(-1/4)01-1/40-3y29/41/410-3/400y517/41/400-7/41-27/4-1/400-9/40比比值值i i19-1y1510-410-3y21011-100y53001-21- -800-1-20v例例2-6：用对偶单纯形法求解下列：用对偶单纯形法求解下列LP问题。问题。v min = 2x1 + 3x2 + 4x3v x1+2x2 + x3 3v 2x1 - x2 +3x3 4v x1, x2, x3 0v上述上述LP问题的对偶问题：问题的对偶问题：v max z = 3y1 + 4y2v y1+2y2 2v 2y1 -
23、 y2 3v y1 +3y24v y1, y20v从求解过程可知，从求解过程可知，对偶单纯形法的优点对偶单纯形法的优点：v(1) 当原问题的初始解是非可行解，且相应的当原问题的初始解是非可行解，且相应的检验数都是非正时，这时不需要引入人工变检验数都是非正时，这时不需要引入人工变量，简化计算。量，简化计算。v(2) 当变量个数多于约束条件个数时，用对偶当变量个数多于约束条件个数时，用对偶单纯形法求解，可以减少计算工作量。因此，单纯形法求解，可以减少计算工作量。因此，对变量少，约束条件多的对变量少，约束条件多的LP问题，问题，可先将它可先将它变换成对偶问题，变换成对偶问题，然后用对偶单纯形法求解然
24、后用对偶单纯形法求解其对偶问题，再根据其其对偶问题，再根据其对偶问题最优解时的对偶问题最优解时的检验数检验数，写出原问题的最优解，写出原问题的最优解。 当当aij，bi，cj这些参数这些参数中的某一个发生变化时，中的某一个发生变化时，问题的最优解会有什么变问题的最优解会有什么变化呢？化呢？ 第第7节节 灵敏度分析灵敏度分析(Sensitivity Analysis)max z = c1x1 + c2x2 + cnxns.t.a11x1+a12x2+a1n xn =b1 a21x1+a22x2+a2n xn = b2 am1x1+am2x2+amn xn = bmx1, x2, , xn0vv灵
25、敏度分析灵敏度分析灵敏度分析灵敏度分析(Sensitivity Analysis)(Sensitivity Analysis)是对系统是对系统是对系统是对系统因环境变化显示出来的敏感程度因环境变化显示出来的敏感程度因环境变化显示出来的敏感程度因环境变化显示出来的敏感程度的分析。的分析。的分析。的分析。vv在线性规划中讨论灵敏度分析，目的是描在线性规划中讨论灵敏度分析，目的是描在线性规划中讨论灵敏度分析，目的是描在线性规划中讨论灵敏度分析，目的是描述一种能确定模型结构中元素变化对问题述一种能确定模型结构中元素变化对问题述一种能确定模型结构中元素变化对问题述一种能确定模型结构中元素变化对问题最优解
26、影响的分析方法。最优解影响的分析方法。最优解影响的分析方法。最优解影响的分析方法。vv灵敏度分析主要回答两方面问灵敏度分析主要回答两方面问灵敏度分析主要回答两方面问灵敏度分析主要回答两方面问题：题：题：题：vv(1) (1) 因素有一定量变化时，最优因素有一定量变化时，最优因素有一定量变化时，最优因素有一定量变化时，最优解有什么变化；解有什么变化；解有什么变化；解有什么变化；vv(2) (2) 因素在什么范围内变化时，因素在什么范围内变化时，因素在什么范围内变化时，因素在什么范围内变化时，最优解保持不变。最优解保持不变。最优解保持不变。最优解保持不变。CBXBbCBCN10XBXN1XS2CB
27、XBB-1bIB-1N1B-1S2ZCBB-1b0CNCBB-1N1CBB-1S2 单纯形表中的基单纯形表中的基B B是最优基，线性规划问题的各系是最优基，线性规划问题的各系数的变化会引起最优单纯形表的哪些部分改变数的变化会引起最优单纯形表的哪些部分改变? ?br变化只引起变化只引起B-1b改变；改变；cj变化只引起变化只引起=(CN -CBB-1N1，-CBB-1)改变；改变；aij变化时：变化时：若若aij属于属于N，则其改变只会引起，则其改变只会引起的改变；的改变； 若若aij属于属于B，则其改变引起，则其改变引起B-1的改变，从而引起的改变，从而引起=(CN - CBB-1N，-CBB
28、-1)和右端常数项和右端常数项B-1b的同时改变。的同时改变。其中其中S2=I7.1 约束方程右端常数项约束方程右端常数项br发生改变发生改变br的改变只会引起的改变只会引起B-1b的改变；的改变；CBXBbCBCN10XBXN1XS2CBXBB-1bIB-1N1B-1ZCBB-1b0CNCBB-1N1CBB-1v第第1章例章例1的最终单纯形表的最终单纯形表(P32) cj23000CBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80-z-1400-3/2-1/80max z = 2x1 + 3x2 x1 + 2x2 84x1 16 4x2
29、12x10，x2 0v例例7 当当b1=8+4=12时，时，cj23000CBXBbx1x2x3x4x52x141001/400x5-400-21/213x24011/2-1/80-z-1400-3/2-1/80max z = 2x1 + 3x2 x1 + 2x2 8+44x1 16 4x2 12x10，x2 0v表表2-10中中b列有负，用对偶单纯形法解得表列有负，用对偶单纯形法解得表2-11。cj23000CBXBbx1x2x3x4x52x141001/400x5-400-21/213x24011/2-1/80-z-1400-3/2-1/80比值比值3/42x141001/400x3200
30、1-1/4 -1/23x2301001/4-z-17000-1/2 -3/4vx5换出，换出，x4换入。换入。v用对偶单纯形法解得表用对偶单纯形法解得表2-11：vx1*=4，x2*=3，z*=17；由；由x3*=2可知，设备有可知，设备有2小时未被小时未被利用。利用。v(1) cj为非基变量的价值系数为非基变量的价值系数v其它条件不变，目标函数中非基变量其它条件不变，目标函数中非基变量xj的的价值系数价值系数cj发生变化，要影响到发生变化，要影响到xj所对应的所对应的j= cj-CBB-1pj，但并不影响其它变量所对，但并不影响其它变量所对应的检验数，也并不影响应的检验数，也并不影响xj=
31、B-1b00。因此，因此，要使现行最优基要使现行最优基B仍为最优基，仍为最优基，只需只需使使改改变后的变后的cj仍满足仍满足j0。7.2 目标函数中价值系数目标函数中价值系数cj发生改变发生改变v即即 cj- -CBB-1pj00v或或 cjCBB-1pjv其中，其中，cj为改变后的目标函数中的非基变量价为改变后的目标函数中的非基变量价值系数。值系数。v所以，当改变后的所以，当改变后的cjCBB-1pj，则现行最优基，则现行最优基B仍为最优基，此时，最优解保持不变，目标函仍为最优基，此时，最优解保持不变，目标函数值数值CBB-1pj也不会改变。也不会改变。v如果改变后如果改变后cjCBB-1p
32、j，即，即j= cj-CBB-1pj0，则，则须改变现行最优基，此时，须改变现行最优基，此时，利用现行最终单纯利用现行最终单纯形表，只须改变表中的形表，只须改变表中的cj和和j，然后，然后继续迭代继续迭代，直到得到最优解为止。直到得到最优解为止。例例2-h(a)：已知已知LP：max z = 5x1+2x2+3x3 x1+2x2+2x38 3x1+4x2+x37 x1,x2,x30若已经求得最终单纯形表若已经求得最终单纯形表，非基变量非基变量x2的价值系数的价值系数c2发在发在什么范围内变化，最优解不变？什么范围内变化，最优解不变？s.t.cj52300CBXBbx1x2x3x4x535x3x
33、117/56/5012/56/5103/5-1/5-1/52/5cjzj0-26/5 0 -4/5 -7/5v(2) cj为基变量的价值参数为基变量的价值参数v其它条件不变，基变量的价值参数其它条件不变，基变量的价值参数cj发生变化，要影发生变化，要影响到响到CB，所以要影响到所有的非基变量的检验数，但，所以要影响到所有的非基变量的检验数，但并不影响并不影响xj= B-1b00。因此，。因此，要使现行最优基要使现行最优基B仍为最仍为最优基，只需使改变后的优基，只需使改变后的cj仍满足仍满足N0。v解不等式解不等式CB- -CBB-1N0 ，就可得现行最优基，就可得现行最优基B仍为最仍为最优基的
34、范围，当优基的范围，当cj在此范围内变化，则最优解保持不在此范围内变化，则最优解保持不变，但此时变，但此时zCBB-1b变化。变化。v当当cj的改变超出此范围时，则须改变现行最优基，的改变超出此范围时，则须改变现行最优基，利利用现行最终单纯形表，只须改变表中的用现行最终单纯形表，只须改变表中的cj和和N，然后，然后继续迭代继续迭代，直到得到最优解为止。，直到得到最优解为止。v例例8：第第1章例章例1的最终单纯形表的最终单纯形表(P32) v讨论基变量的价值系数讨论基变量的价值系数c2在什么范围内变化，可以保在什么范围内变化，可以保持最优解不变。持最优解不变。cj23000CBXBbx1x2x3
35、x4x52x141001/400x5400-21/213x22011/2-1/80-z-1400-3/2-1/80max z = 2x1 + 3x2 x1 + 2x2 84x1 16 4x2 12x10，x2 0vc2为基变量为基变量x2的价值系数，的价值系数，若要保持最优解不变，若要保持最优解不变，只要满足只要满足N0即可。由单纯形法可知即可。由单纯形法可知由由N0得不等式组：得不等式组：解得：解得：0c24只要只要c2在上述范围内变化，原最优生产计划在上述范围内变化，原最优生产计划就不用改变。但相应的就不用改变。但相应的zCBB-1b82c2；cj23000CBXBbx1x2x3x4x52
36、x141001/400x5400-21/213x22011/2-1/80-z-1400-3/2-1/80v如果如果c2的变化超出上述范围，则需改变现行最优基。的变化超出上述范围，则需改变现行最优基。不妨设不妨设c2=5，改变，改变c2和和N，继续迭代，直到得到最优解，继续迭代，直到得到最优解为止。因为为止。因为c2=5，得，得40，继续迭代，继续迭代：v最优解最优解X*=(2,3,0,8,0)T；v最优值最优值z*=19。cj25000CBXBbx1x2x3x4x52x141001/40160x5400-21/2185x22011/2-1/80-z-1800-5/21/802x121010-1
37、/20x4800-4125x2301001/4-z-1900-20-1/4vx4换入，换入，x5换出。换出。v7.3 约束条件的系数矩阵中某一个约束条件的系数矩阵中某一个aij发生改变发生改变v例例9 第第1章例章例1.cj235000CBXBbx1x2x3x3(xs1)x4(xs2) x5(xs3)2x14103/201/400x54002-21/213x22011/41/2-1/80-z-14005/4-3/2-1/80max z = 2x1 + 3x2+ 5x3 x1 + 2x2 + 2x384x1 + 6x316 4x2 + 3x312x10，x2 0，x3 0v用单纯形法解得表用单纯
38、形法解得表2-13(b)：cj235000CBXBbx1x2x3x3x4x52x14103/201/408/30x54002-21/2123x22011/41/2-1/808-z-14005/4-3/2-1/802x111004/3-1/8 -3/40x32001-11/41/23x23/20103/4-3/161/8-z-16.5000-1/4-7/16-5/8x3换入，换入，x5换出。换出。v用单纯形法解得表用单纯形法解得表2-13(b)：vx1*=1，x2*=3/2，x3*=2， z*=16.514。v例例10 第第1章例章例1.cj43000CBXBbx1x2x3x4x52x145/4
39、001/400x541/20-21/213x223/811/2-1/80-z-143/80-3/2-1/80max z = 4x1 + 3x22x1 + 2x2 85x1 162x1 + 4x2 12x10，x2 0v用单纯形法解得表用单纯形法解得表2-15：vx1*=3.2，x2*=0.8，z*=15.214。cj43000CBXBbx1x2x3x4x52x145/4001/4016/50x541/20-21/2183x223/811/2-1/8016/3-z-143/80-3/2-1/802x13.21001/500x52.400-22/513x20.8011/2-1/50-z-15.200-3/2-1/50x1换入，换入，x1换出。换出。v用单纯形法解得表用单纯形法解得表2-15：vx1*=3.2，x2*=0.8，z*=15.214。第第8节节 参数规划参数规划v当当aij，bi，cj这些参数中的某一个参数是函数这些参数中的某一个参数是函数变化时，怎样求出问题的最优解呢？变化时，怎样求出问题的最优解呢？
