《纯形法的灵敏度分析》由会员分享，可在线阅读，更多相关《纯形法的灵敏度分析（56页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 单纯形法单纯形法的灵敏度分析的灵敏度分析一、问题的提出一、问题的提出二、目标函数系数的变化二、目标函数系数的变化三、右端项的变化三、右端项的变化四、技术系数的变化四、技术系数的变化五、增加约束条件五、增加约束条件一、问题的提出假设范例假设范例目标函数：目标函数：Max z= 50x1+100 x2 约束条件：约束条件：1x1+1x2300 2x1+1 x2400 0x1+1 x2250 x1 0， x2 0中中x2的目标函数系数由的目标函数系数由100变为变为75，求新问题，求新问题的解。的解。一、问题的提出解：经过单纯形迭代得到最优表解：经过单纯形迭代得到最优表2-250-50
2、00 j=cjzj21250250507550zj2501001075x25011-2000x450-1010150x10007550比值比值bi/ai2bx5x4x3x2x1CB基变基变量量XB迭代迭代次数次数2-500-5000 j=cjzj275005005010050zj25010010100x25011-2000x450-1010150x100010050比值比值bi/ai2bx5x4x3x2x1CB基变基变量量XB迭代迭代次数次数一、问题的提出一、问题的提出比较范例的最优表：比较范例的最优表：一、问题的提出一、问题的提出事实上，系数的改变并未改变事实上，系数的改变并未改变LP问题的
3、解。问题的解。思考：思考：1、如果、如果C2变为变为45，最优解会变吗？为保证最，最优解会变吗？为保证最优解不变，优解不变， C2的取值范围？的取值范围？2、参数变化时，可否利用原问题的最优表求、参数变化时，可否利用原问题的最优表求解，而不必从头进行单纯形迭代，以简化计解，而不必从头进行单纯形迭代，以简化计算？算？一、问题的提出一、问题的提出要解决以上问题，需要探讨初始单纯形要解决以上问题，需要探讨初始单纯形表与最优单纯形表的关系。表与最优单纯形表的关系。观察范例的单纯形求解过程：观察范例的单纯形求解过程：迭代次迭代次数数基变量基变量XBCBx1x2x3x4x5b比值比值bi/ai250100
4、0000x3011100300300/1x4021010400400/1x500001250250/1zj000000 j501000001x30010-15050/1x402001-1150150/2x210001001250_zj010000-10025000 j50000-1002x1501010-150x4000-21150x210001001250zj501005005027500 j00-500-50一、问题的提出一、问题的提出事实上，在单纯形表的迭代过程中，最事实上，在单纯形表的迭代过程中，最核心的变化是系数矩阵的行变换，其它核心的变化是系数矩阵的行变换，其它值如值如cj在每次迭
5、代中不变，在每次迭代中不变，zj和检验数则和检验数则是根据其它元素计算得出。是根据其它元素计算得出。一、问题的提出一、问题的提出初始初始矩阵矩阵最优最优矩阵矩阵行变换行变换初始基初始基初始矩阵变最优矩阵的过程可以表示为：初始矩阵变最优矩阵的过程可以表示为： 如，如，b2变为变为100，则最优矩阵可计算出：，则最优矩阵可计算出：单纯形法的灵敏度分析基本思路：单纯形法的灵敏度分析基本思路：1、将某个参数的变化反映在最终表中；、将某个参数的变化反映在最终表中；2、看最终表是否还满足最优表的要求：、看最终表是否还满足最优表的要求：基是否为单位排列阵，检验数是否都非基是否为单位排列阵，检验数是否都非正，
6、正，b列是否都为非负的数；列是否都为非负的数；3、若满足上述要求则最优基没有改变，、若满足上述要求则最优基没有改变，若不满足则在新的最终表上继续进行迭若不满足则在新的最终表上继续进行迭代，直到找到新的最优基为止。代，直到找到新的最优基为止。二、目标函数系数二、目标函数系数ck的变化的变化1、在最终单纯形表中，、在最终单纯形表中，xk是非基变量是非基变量除了除了xk的检验数外，的检验数外， ck的变化不会影响的变化不会影响到最终单纯形表中其它任何数值。到最终单纯形表中其它任何数值。只要只要xk的检验数仍然非正，最优解和最的检验数仍然非正，最优解和最优值都会保持不变。优值都会保持不变。如范例，使最
7、优解不变的如范例，使最优解不变的cj值变化范围？值变化范围？迭代迭代次数次数基变基变量量XBCBx1x2x3x4x5b比值比值bi/ai2501000002x1501010-150x4000-21150x210001001250zj501005005027500 j00-500 -50迭代迭代次数次数基变基变量量XBCBx1x2x3x4x5b比值比值bi/ai250100c3002x1501010-150x4000-21150x210001001250zj5010050050 27500 j00c3-500-50要使最优解不变，须要使最优解不变，须c3-50 0求得求得c3 50二、目标函数系
8、数二、目标函数系数ck的变化的变化二、目标函数系数二、目标函数系数ck的变化的变化2、在最终单纯形表中，、在最终单纯形表中， xk是基变量是基变量此时各非基变量的检验数均有可能受到此时各非基变量的检验数均有可能受到影响，同时还会影响到最优值。影响，同时还会影响到最优值。要最优解不变，必须保证所有的检验数要最优解不变，必须保证所有的检验数非正。非正。迭代迭代次数次数基变基变量量XBCBx1x2x3x4x5b比值比值bi/ai2c11000002x1c11010-150x4000-21150x210001001250zjc1100c10-c1+100 j00- c10c1-100要使最优解不变，须
9、要使最优解不变，须- c10且且c1 -100 0求得求得0 c1 100二、目标函数系数二、目标函数系数ck的变化的变化迭代次迭代次数数基变量基变量XBCBx1x2x3x4x5b比值比值bi/ai250c20002x1501010-150x4000-21150x2c201001250zj50c2500 c2 - 50 j00-50050 - c2要使最优解不变，须要使最优解不变，须50-c2 0求得求得c2 50二、目标函数系数二、目标函数系数ck的变化的变化迭代迭代次数次数基变基变量量XBCBx1x2x3x4x5b比值比值bi/ai250 1000c402x1501010-150x4c40
10、0-21150x2100 01001250zj50 10050-2c4c450+c4 j002c4-500- c4-50要使最优解不变，须要使最优解不变，须2c4-50 0且且- c4 -50 0求得求得-50 c4 25二、目标函数系数二、目标函数系数ck的变化的变化课堂练习课堂练习有下列线性规划问题：有下列线性规划问题： Max z = -2x1 - 3x2 - 4x3 . -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0分别分析目标函数中分别分析目标函数中x1和和x3的系数在什的系数在什么范围内变动时，最优解不变。
11、么范围内变动时，最优解不变。课堂练习课堂练习基变基变量量XBCBx1x2x3x4x5b-2-3-400x1-2107/5 -1/5 -2/511/5x2-301-1/5 -2/5 1/52/5zj-2-3-11/5 8/5 1/5 -28/5 j00-9/5 -8/5 -1/5解：最优表为解：最优表为课堂练习课堂练习基变基变量量XBCBx1x2x3x4x5bc1-3-400x1c1107/5-1/5-2/511/5x2-301-1/5-2/51/52/5zjc1-33/5+7c1/56/5-c1/5 -3/5-2c1/5-6/5+11c1/5 j00-17/5-7c1/5c1/5-6/53/5
12、+2c1/5所有所有j0时，原最优解不变时，原最优解不变从表中可得到：从表中可得到： -17/7 c1 -3/2 。课堂练习课堂练习基变基变量量XBCBx1x2x3x4x5b-2-3c300x1-2107/5-1/5 -2/511/5x2-301-1/5-2/51/52/5zj-2-3-11/58/51/5-28/5 j00c3 +11/5 -8/5 -1/5从表中看到从表中看到3= c3 +11/5 0可得到可得到c3 -11/5 时，原最优解不变。时，原最优解不变。三、右端项的变化三、右端项的变化右端项发生变化时，最优解中变量的取右端项发生变化时，最优解中变量的取值总会随之变化。值总会随之
13、变化。讨论右端项的取值范围时，考虑的是使讨论右端项的取值范围时，考虑的是使最优基和对偶价格不变。最优基和对偶价格不变。三、右端项的变化三、右端项的变化例：范例中例：范例中b1为为300，使最优基不变，使最优基不变的的b1取值范围？取值范围？解：最优表中的解：最优表中的b列可表示为列可表示为Bb0三、右端项的变化三、右端项的变化最优表可表示为：最优表可表示为：迭代迭代次数次数基变基变量量XBCBx1x2x3x4x5b比值比值bi/ai250 1000002x1501010-1b1 -250x4000-211650 -2 b1x210001001250zj50 100 50050 50b1+125
14、00 j00-500-50三、右端项的变化三、右端项的变化最优值最优值z* 50b1 +12500可见可见b1的对偶价格的对偶价格50。由由b1 -2500推出推出b1 250由由-2 b1 +650 0推出推出 325 b1只要最优基不变，对偶价格也不会变。只要最优基不变，对偶价格也不会变。即即325 b1 250时对偶价格不变。时对偶价格不变。三、右端项的变化三、右端项的变化练习：分析范例练习：分析范例b2的变化范围。的变化范围。2-500-5000 j=cjzj275005005010050zj25010010100x25011-2000x450-1010150x100010050比值比
15、值bi/ai2bx5x4x3x2x1CB基变基变量量XB迭代迭代次数次数对偶价格在单纯形表中的表示对偶价格在单纯形表中的表示根据对偶价格定义，如果最优目标函数值根据对偶价格定义，如果最优目标函数值Z*可以表示为右端项可以表示为右端项bi的函数，则对于目标函的函数，则对于目标函数最大化的数最大化的LP问题，问题， bi的对偶价格可以表示的对偶价格可以表示为数学表达式：为数学表达式：关键是：如何将目标函数表示为关键是：如何将目标函数表示为bi的函数？的函数？BCB*对偶价格在单纯形表中的表示对偶价格在单纯形表中的表示2-500-5000 j=cjzj275005005010050zj2501001
16、0100x25011-2000x450-1010150x100010050比值比值bi/ai2bx5x4x3x2x1CB基变基变量量XB迭代迭代次数次数观察范例最优表：观察范例最优表：对偶价格在单纯形表中的表示对偶价格在单纯形表中的表示由于由于故，故，最终表中第最终表中第i个初个初始基变量的始基变量的z值值对偶价格在单纯形表中的表示对偶价格在单纯形表中的表示结论：结论：各右端项的对偶价格就是其所在方程中各右端项的对偶价格就是其所在方程中初始基变量在最优表中的初始基变量在最优表中的zj值。值。相关概念：相关概念：影子价格影子价格右端项增加一单位，使最右端项增加一单位，使最优目标函数值增加的数量。
17、优目标函数值增加的数量。四、技术矩阵的变化四、技术矩阵的变化1、最终单纯形表中非基变量对应的系数、最终单纯形表中非基变量对应的系数列向量由列向量由pk pk时，最优表中发生变时，最优表中发生变化的有：化的有：最优矩阵中的第最优矩阵中的第k列，变为列，变为 B0pk最终表中检验数最终表中检验数 k=ck-CB*T B0pk若仍有若仍有 k0，则最优解不变，否则继续，则最优解不变，否则继续迭代，直到找到新的最优解。迭代，直到找到新的最优解。四、技术系数的变化四、技术系数的变化2、对于增加一个变量，从而使得系数矩、对于增加一个变量，从而使得系数矩阵增加一列阵增加一列pn+1的情况：的情况：技术矩阵由
18、技术矩阵由mn阶变为阶变为m(n+1)阶阶在最终表中加入一列在最终表中加入一列pn+1B0 pn+1然后计算检验数。若然后计算检验数。若 n+10，则进行迭，则进行迭代，直到找到新的最优解。代，直到找到新的最优解。 四、技术系数的变化四、技术系数的变化如范例，新增产品如范例，新增产品3，价值系数为，价值系数为150，相应增加一个技术列向量相应增加一个技术列向量p6(2,0.5,1.5)T则最优矩阵中则最优矩阵中p6 B 检验数检验数 6150-(50,0,100) -25。四、技术系数的变化四、技术系数的变化所有检验数仍然小于所有检验数仍然小于0，故最优基和最优，故最优基和最优解不变。解不变。
19、说明增加了产品说明增加了产品3并不改变原生产计划。并不改变原生产计划。四、技术系数的变化四、技术系数的变化假如产品假如产品3的工艺改进，价值系数变为的工艺改进，价值系数变为160，技术列向量变为，技术列向量变为，2，1)T则最优矩阵中则最优矩阵中p6 B 检验数检验数 6160-(50,0,100) 35。四、技术系数的变化四、技术系数的变化迭代迭代次数次数基变基变量量XBCBx1x2x3x4x5x6b比值比值bi/ai2501000001602x1501010-10.550100x4000-211050x2100010011250250zj5010050050 125 27500 j00-5
20、00-5035检验数检验数 635，还需迭代。，还需迭代。四、技术系数的变化四、技术系数的变化3、最终单纯形表中基变量对应的系数列、最终单纯形表中基变量对应的系数列向量由向量由pk pk时，原最优解的可行性时，原最优解的可行性和最优解都可能遭到破坏，情况比较复和最优解都可能遭到破坏，情况比较复杂，一般重新求解。杂，一般重新求解。五、增加约束条件五、增加约束条件在原线性规划中增加一个约束条件时，在原线性规划中增加一个约束条件时，先将原问题的最优解的变量值代入新增先将原问题的最优解的变量值代入新增的约束条件。的约束条件。如果满足，则说明新增的条件没有起到如果满足，则说明新增的条件没有起到限制作用，
21、故最优解不变；限制作用，故最优解不变；如果不满足，则将新增的约束添入原最如果不满足，则将新增的约束添入原最终单纯形表中进一步求解。终单纯形表中进一步求解。五、增加约束条件五、增加约束条件如范例，新增约束条件如范例，新增约束条件电量限制电量限制5000度，生产一个产品度，生产一个产品1需要用电需要用电10度，度，生产一个产品生产一个产品2需要用电需要用电30度。度。即，即，10x1+30x25000原最优解（原最优解（50，250，0，50，0）代入，）代入， 10x1+30x280005000，不满足，须迭，不满足，须迭代。代。五、增加约束条件五、增加约束条件引入松弛变量引入松弛变量x6， 1
22、0x1+30x2 + x65000基变基变量量XBCBx1x2x3x4x5x6b比值比值bi/ai2501000000x1501010-1050x4000-211050x2100010010250x60103000015000zj5010050050027500 j00-500-500五、增加约束条件五、增加约束条件用行变换将基变量对应的系数列向量化为单用行变换将基变量对应的系数列向量化为单位列向量：位列向量：基变基变量量XBCBx1x2x3x4x5x6b比值比值bi/ai2501000000x1501010-1050x4000-211050x2100010010250x6000-100-20
23、1-3000zj5010050050027500 j00-500-500课堂练习课堂练习对于对于LP问题：问题： Max z = 2x1 + 3x2. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0课堂练习课堂练习分析：分析：1、使最优解不变的、使最优解不变的系数系数c c2 2的取值范围；的取值范围；2 2、使最优基不变的、使最优基不变的b1的取值范围；的取值范围；3、若增加、若增加x6 , p6=( 2, 6, 3 )T, c6=5，最优，最优解如何？解如何？4、若增加若增加3x3x1 1+ 2x
24、+ 2x2 21515，最优解如何？最优解如何？课堂练习课堂练习基变基变量量XBCBx1x2x3x4x5b23000x121001/404x5000-21/214x23011/2-1/802zj233/21/8014 j00-3/2 -1/80解：原问题最优表为解：原问题最优表为课堂练习课堂练习基变量基变量XBCBx1x2x3x4x5b2c2000x121001/404x5000-21/214x2c2011/2-1/802zj2c2c2 /21/2-c2/808+2c2 j00 -c2 /2c2/8-1/201、由、由-c2 /2 0， c2/8-1/2 0 ，得得c2的取值范围的取值范围：（
25、：（0，4）课堂练习课堂练习2、用、用b1表示最优表中的右端项：表示最优表中的右端项：初始基在最优初始基在最优表中的形式表中的形式课堂练习课堂练习由于最优表右端项有非负要求，即由于最优表右端项有非负要求，即解得解得b1的取值范围的取值范围：（：（4，10）0课堂练习课堂练习3、增加、增加p6=( 2, 6, 3 )T ，最优表中增加列：，最优表中增加列：初始基在最优初始基在最优表中的形式表中的形式课堂练习课堂练习基变基变量量XBCBx1x2x3x4x5x6b230005x121001/403/24x5000-21/2124x23011/2-1/801/42zj233/21/8015/414 j
26、00-3/2 -1/805/4最优表变为：最优表变为：课堂练习课堂练习用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：X* = ( 1,1.5,0,0,0,2 )T课堂练习课堂练习基变量基变量XBCBx1x2x3x4x5x6b230000x121001/4004x5000-21/2104x23011/2-1/8002x6032000115zj j4、增加、增加3x1+ 2x215，原最优解不满足这个约，原最优解不满足这个约束，故在原最优表上增加相应行列：束，故在原最优表上增加相应行列：课堂练习课堂练习基变量基变量XBCBx1x2x3x4x5x6b230000x121001/4004x5000-21/2104x23011/2-1/8002x6000-1-1/201-1zj233/21/80014 j00-3/2-1/800通过行变换，将基向量变为单位列通过行变换，将基向量变为单位列课堂练习课堂练习经添加人工变量，迭代后，可得：经添加人工变量，迭代后，可得：最优解为（最优解为（3.5, 2.25, 0, 0, 3, 2 )T，最优值为最优值为 13. 75作业作业教材教材124页第页第5题。题。
