03灵敏度分析

第1页练习（对偶单纯形法求解）0,1242332..3min2121212121xxxxxxxxtsxxz第2页第六节灵敏度分析•单纯形法的矩阵表示•系数变化的灵敏度分析•决策变量增减的灵敏度分析•约束条件增减的灵敏度分析•灵敏度分析小结第3页一、单纯形法的矩阵表示0,..0maxsssxXbIxAXtsxCXzNBA,NBNBCCCxxX,,第4页sNBXBNXBbBX1110,,..0maxsNBSNBSNNBBXXXbIXNXBXtsXXCXCzsBNBNBXBCXNBCCbBCz111)(将约束条件两边同时左乘B-1bBXBNXBIXsNB111bBXBNXBBXBsNB1111化简得：第5页1B1BbBXBNXBBXBsNB1111bBXBNXBIXsNB111松弛变量的系数矩阵正好是每个变量的系数列向量都是乘以该变量的原始列向量而得到的。1jjBjcCBPsBNBNBXBCXNBCCbBCz111)(第6页列12345行xx1x2x3x4x5bθc430001x302210016001600/2=8002x4052.501025002500/5=5003x50(1)0001400400/1=4004zj0000005zj-cj-4-3000列12345行xx1x2x3x4x5bθc430001x300210-2800800/2=4002x400(2.5)01-5500500/2.5=2003x14100014004zj4000416005zj-cj0-3004列12345行xx1x2x3x4x5bθc430001x30001-0.82400400/2=2002x230100.4-22003x1410001400400/1=4004zj4301.2-222005zj-cj0001.2-2列12345行xx1x2x3x4x5bθc430001x50000.5-0.412002x23011-0.406003x1410-0.50.402004zj4310.4026005zj-cj0010.40最优解04.05.004.0114.05.010155.202201BB10015204.05.004.0114.05.011PB2006002004002500160004.05.004.0114.05.01bB01005.2204.05.004.0114.05.021PB第7页二、系数变化的灵敏度分析研究当决策变量和约束条件数目不变时，各种系数变化对最优解的影响：（1）系数在什么范围内变化，能保持最优解不变或最优解的基变量不变；（2）如果最优解发生了变化，新的最优解是什么。第8页1、价值系数的变化范围的确定1）非基变量的系数2）基变量的系数2、右端项（资源系数）的变化范围的确定3、技术系数的变化对最优解的影响1）基变量系数变化2）非基变量系数的变化范围第9页价值系数cj的变化1.cj是非基变量Xj的系数cj的变化只影响对应非基变量Xj的检验数，不影响其它变量的检验数，也不影响b项的值。要保持最优解不变，只需满足：0''jjjjjjjjccczcz第10页04.04.00122cc112c２.cj是基变量Xj的系数影响所有非基变量的检验数422c行xcx1x2x3x4x5b1x50000.5-0.412002x23+Δc2011-0.406003x1410-0.50.402004zj43+Δc21+Δc20.4-0.4Δc202600+5zj-cj001+Δc20.4-0.4Δc20600Δc2第11页0,,3054345536..53max321321321321xxxxxxxxxtsxxxz讨论：c1，c2在什么范围内变化，可以保持最优解不变。例题：已知某LP问题及其单纯形法终表：x1x2x3x4x5行xc31500b1X131-1/301/3-1/352X35011-1/52/534zj34501305zj-cj03001第12页x1x2x3x4x5行xc36500b1X131-1/301/3-1/352X35011-1/52/534zj34501305zj-cj0-2001若c2=6：x4015/405/41-3/445/2x263/415/401/415/2zj9/2615/203/245zj-cj3/205/203/2第13页•bi的变化，只影响最优解的数值，不影响任何系数，所以只需保证最后解仍然是可行解即可。右端项资源系数bi的变化第14页•b1=1600+△b1时40040005.0200060005.02005.02006005.02004002500160004.05.004.0114.05.0111111111bbbbbbbbbBX当△b1=200，b1=1800时教材例题第15页•b1=2200时，这时最终单纯形表变成：行xcx1x2x3x4x5b1x50000.5-0.415002x23011-0.4012003x1410(-0.5)0.40-1004zj4310.4032005zj-cj0010.40行xcx1x2x3x4x5b1x50100014002x232100.4010003x30-201-0.802004zj6301.2030005zj-cj2001.20第16页0,,3054345536..53max321321321321xxxxxxxxxtsxxxzx1x2x3x4x5行xc31500b1X131-1/301/3-1/352X35011-1/52/534zj34501305zj-cj03001试求：b2由30分别变为40、60时的最优解。同上例：已知某LP问题及其单纯形法终表：第17页技术系数aij的变化•aij为非基变量的技术系数时，对检验数有影响，只需保证对应非基变量的检验数非负。•aij为基变量的技术系数时,需继续进行初等行变换，将对应基变量技术系数列变为单位列向量。第18页0,,3054345536..53max321321321321xxxxxxxxxtsxxxzx1x2x3x4x5行xc31500b1X131-1/301/3-1/352X35011-1/52/534zj34501305zj-cj03001试求：a22由4变为2时，最优解是否变化。同上例：已知某LP问题及其单纯形法终表：第19页教材例题•a11由2变成3时行xcx1x2x3x4x5b1x500.500.5-0.412002x23111-0.406003x140.50-0.50.402004zj5zj-cj第20页行xcx1x2x3x4x5b1x50001-0.8102x23012-1.202003x1410-10.804004zj432-0.4022005zj-cj002-0.40表1-15行xcx1x2x3x4x5b1x50100014002x231.510.5008003x401.250-1.25105004zj4.531.50024005zj-cj0.501.500最优解表1-16第21页三、决策变量增减的灵敏度分析增加产品新品种相当于增加一列：–1、解决是否值得生产的问题–2、解决若值得生产，生产计划应如何调整•第一种问题可以直接使用机会成本分析法•第二种问题需先计算新的一列当前值，再继续求解。第22页行xcx1x2x3x4x5x6b1x50000.5-0.41(0.5)200200/0.5=4002x23011-0.401600600/1=6003x1410-0.50.40-0.252004zj4310.40226005zj-cj0010.40-1表1-17若研制出一种新产品——小型旅游车，问如何安排生产计划。教材例题第23页行xcx1x2x3x4x5x6b1x63001-0.8214002x23010(0.4)-20200200/0.4=5003x1410-0.250.20.50300300/0.2=15004zj432-0.42330005zj-cj002-0.420行xcx1x2x3x4x5x6b1x630210-218002x4002.501-505003x141-0.5-0.2501.502004zj44200332005zj-cj012000最优解表1-18第24页•例：某汽车电器厂现有两种原材料8t和5t，用来生产A、B、C、D四种产品，每万件产品的利润分别为3、4、2、7万元，每万件产品对原材料的消耗见下表产品原料ABCD现有原料甲23158乙12135利润3427•问如何安排生产，才能使利润最大。•若增加一种新产品E，其对原材料的消耗分别为2和3，利润为6，问要不要安排这种新产品的生产。第25页0,,,5328532..7243max4321432143214321xxxxxxxxxxxxtsxxxxzx1x2x3x4X5X6行xc342700b1X1311021-132X320111-1224zj352811135zj-cj010111第26页0)7,,2,1(533282532..67243max76432175432174321ixxxxxxxxxxxxxtsxxxxxzi若生产新产品E，应如何安排生产计划。思考：若决定不再生产A，应如何安排生产计划。第27页四、约束条件增减的灵敏度分析•约束条件增加（或减少）相当于在原最优解的表中同时增加（或减少）一行和一列。•增加一个基变量，首先通过初等行变换将各基变量的技术系数列变为单位列向量，然后继续迭代。第28页教材例题•增加约束条件X1+X2≤600X1+X2+X7=600行xcx1x2x3x4x5x7b1x50000.5-0.4102002x23011-0.4006003x1410-0.50.4002004x701100016005zj6zj-cj第29页行xcx1x2x3x4x5x7b1x50000.5-0.4102002x23011-0.4006003x1410-0.50.4002004x7000(-0.5)001-2005zj4310.40126006zj-cj0010.401表1-20行xcx1x2x3x4x5x7b1x50000-0.41002x23010-0.4022003x141000.40-14004x3000100-24005zj4300.40222006zj-cj0000.402最优解表1-21第30页五、灵敏度分析总结灵敏度分析步骤：根据给定系数、变量和约束条件的变化，直接求出最终单纯形表中的相应变化；若变换后的最终表，基变量的系数向量不再是单位向量，则首先进行初等行变换，将其变为单位向量。同时得到修正后的最终表。检查所得到的解是否为最优解。第31页灵敏度分析总是要修正甚至扩展单纯形表，修正后的单纯形表有四种可能，应分别对待处理：（1）（2）（3）（4）原问题可行解可行解不可行解不可行解对偶问题可行解不可行解可行解不可行解处理方法是最优解停止迭代单纯形法继续迭代对偶单纯形法继续迭代引入人工变量，建立初始基本可行解第32页0,,426..2max32