运筹学-第七周-灵敏度分析-运输问题

第二章对偶理论与灵敏度分析线性规划问题的引出|线性规划问题的概念和模型|线性规划的标准型|线性规划模型的标准化本章内容对偶理论是线性规划最重要的基础理论之一是进行经济分析的重要工具一般形式单纯形法计算的矩阵描述设线性规划问题:目标函数约束条件AX≤b;非负条件X≥0线性规划问题的约束条件加入松弛变量以后，得到标准型：maxz=CX+0XsAX+IXs=b;X，Xs≥0mmI1001maxz=CX矩阵A可以分块记为A=[B，N]相应地，向量X和C可以记为CCNBNB,,CXXXXB=B-1b—B-1NXN—B-1Xs对于一个确定的基B，目标函数z可以写成NNBBNBNBXCXCXX.C,CXCz目标函数z用非基变量表出的形式S1BN1BN1BNNS1N11BXBCN)XBC(CbBCXC)XBNXBb(BCz0x,x,xbIxNxBxs.t.0xxCxCmaxzsNBsNBsNNBB0,,0maxSNBSNBSNNBBXXXbEXNXBXXXCXCZCBCN00XBXNXSb0XSBNIb检验数CBCN00XBXNXSbCBXBIB－1NB－1B－1b检验数0CN－CBB－1N－CBB－1－CBB－1b初始单纯形表迭代n步之后的单纯形表S1BN1BN1BNNS1N11BXBCN)XBC(CbBCXC)XBNXBb(BCz线性规划问题的引出|线性规划问题的概念和模型|线性规划的标准型|线性规划模型的标准化影子价格总结：3.影子价格是在系统达到最优时对系统资源的一种最优估价，并假设第i种资源增加一个单位时最优基没改变。4.影子价格可以告诉管理人员，增加哪一种资源对增加经济效益有利，帮助企业调节生产规模；5.影子价格可以告诉管理人员，花多大的代价来增加资源才是合算的；6.影子价格可以帮助管理人员进行生产要素对产出贡献的分解；7.影子价格可以告诉管理人员如何考虑新产品的价格。1.影子价格的大小客观地反映了资源在系统内的稀缺程度。2.影子价格的取值与系统的状态有关，系统中任一状态的改变都会引起影子价格的变化。对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！什么是对偶单纯形法？1.使用条件：①检验数全部≤0；②右端向量列至少一个元素0；2.实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个右端负分量作为换出变量去替换某个非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。对偶单纯形法的实施3.计算步骤：①建立初始单纯形表，计算检验数行。右端向量列≥0——已得最优解；右端向量至少一个元素0,转下步;右端向量列≥0——原始单纯形法；至少一个元素0,另外处理；检验数全部≤0（非基变量检验数0）至少一个检验数0基变换：先确定换出变量——右端向量列中的负元素（一般选最小的负元素）对应的基变量出基；出基，则选lliiixbBbBbB,)(0)()(min111相应的行为主元行。然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果'''0minlkkkljljjjjazcaazc（最小比值原则），则选为换入变量，相应的列为主元列，主元行和主元列交叉处的元素为主元素。kx'lka按主元素进行换基变换（初等行变换），将主元素变成1，主元列变成单位向量，得到新的单纯形表。最优解判别法则：右端向量满足非负约束第五节灵敏度分析•以前讨论线性规划问题时，假定αij，bi,cj都是常数，但实际上这些系数往往是估计值或预测值。•如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。灵敏度分析：指对系统或事物因周围条件变化显示出来的敏感程度的分析。线性规划模型的灵敏性分析：研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程，称为线性规划的灵敏度分析。一、灵敏度分析的含义和内容目标函数的价值系数变化约束方程右端向量变化约束方程组系数阵变化决策变量或约束条件变化2.线性规划灵敏度分析的内容maxz=CXAX=bX≥01.最优解保持不变，即基变量和它们的取值没有变化2.基变量保持不变，但它们的值改变了3.基解完全变了对解的影响主要有:可行性B－1b≥0最优性CN－CBB－1N≥0LP灵敏度分析最终回答：计算量少，充分利用到原最优的单纯形表结果1.这些系数在什么范围内变化时，原先求出的线性规划问题的最优解或最优基不变。2.如果系数的变化超出了上述范围，如何用最简便的方法求出新的最优解。三、灵敏度分析的步骤1.将参数的改变通过计算反映到最终单纯形表上2.检查原问题和对偶问题是否还是可行解3.按照下表所列情况分别进行讨论原问题对偶问题结论或继续计算方法可行解可行解问题的最优解保持不变可行解非可行解用单纯形法继续求解非可行解可行解对对偶单纯形法求解非可行解非可行解引用人工变量，构造基，重新计算1.价值系数cj的变化分析四、灵敏度分析的具体内容XBXNXSbCBXBIB－1NB－1B－1b检验数0CN－CBB－1N－CBB－1－CBB－1bCBCN00XBXNXSb0XSBNIb检验数CBCN00初始单纯形表最优单纯形表当cj变化时，如能保持，则当前解仍为最优解，否则可用单纯形法继续迭代求出新的最优解。0N将cj看作待定参数，令01NBCCBNN解这n-m个不等式，可算出保持最优解不变时cj的变化范围。（1）当cj是非基变量的价值系数——它的变化只影响一个检验数。j（2）当cj是基变量的价值系数——它的变化将影响所有非基变量的检验数，NBCCBNN1例16：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划：0,4580290345max2121212121xxxxxxxxxxZ已知最优表如下：（1）确定x2的系数c2的变化范围，使原最优解保持最优；（2）若c2=6，求新的最优计划。cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14x210010-12000-1-3cj5c2000CBXBbx1x2x3x4x50x3250012-55x1351001-1c2x210010-12000c2-55-2c2σ4=c2－5≤0σ5=5－2c2≤05/2≤c2≤5最优解X*=（35，10，25，0，0）保持不变。最优单纯形表Cj56000CBXBbx1x2x3x4x50x325001[2]-55x1351001-16x210010-12σj0001-70x425/2001/21-5/25x145/210-1/203/26x245/2011/20-1/2σj00-1/20-9/2x1*=45/2，x2*=45/2，x4*=25/2，x3*=x5*=0，z*=495/22.右端常数bi(资源系数)的变化分析XBXNXSbCBXBIB－1NB－1B－1b检验数0CN－CBB－1N－CBB－1－CBB－1bCBCN00XBXNXSb0XSBNIb检验数CBCN00初始单纯形表最优单纯形表当bi发生变化时，将影响所有基变量的取值①保持B-1b≥0,当前的基仍为最优基，最优解的结构不变（取值改变）；②（B-1b）i0,当前基为非可行基，但是仍保持为对偶可行基,可用对偶单纯形法求出新的最优解；③如何求出保持最优基不变的bi的范围?把bi看作待定参数，令B-1b≥0，求解该不等式组即可。例17：对于上例中的线性规划作下列分析：（1）b3在什么范围内变化，原最优基不变？（2）若b3=55，求出新的最优解。0,4580290345Zmax2121212121xxxxxxxxxxcj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14x210010-12000-1-321-01105-21最优基：B=（P3，P1，P2）B－1=最优单纯形表的A中松弛变量的系数最优单纯形表（1）21-01105-213b8090333b280b805b-2503b8090B－1==≥0解得40≤b3≤50，即当b3∈[40，50]时，最优基B不变z*=5×（80－b3）+4×（－80+2b3）=80+3b3333b280b805b-250*2*1*3xxx=（2）当b3=55时333b280b805b-250302525=x2x1x50-11/5-3/500σj0-1/52/51020403/5-1/5013051-2/5-1/50050-32-1[-5]x50-1000σj-101030x24100125x152100-25x30x4x3x2x1bXBCB0045CjbBXB1=3.增加一个新决策变量xj的变化分析资源的合理利用问题：新问题：如开发出一种新产品，已知其有关工艺参数（或消耗的资源量）和单位产品利润，设该种产品的产量为xn+1，则cn+1和Pn+1已知，需要进行“是否投产”的决策。（1）增加1个新变量：相当于系数阵A增加1列112211maxnnnnxcxcxcxczmnmnnmnmmnnnnnnnnbxaxaxaxabxaxaxaxabxaxaxaxa11221121122222121111112121110,,,121nnxxxx对新问题：XBXN检验行IB-1NB-1bXB0CN-CBB-1N-CBB-1b最优单纯形表1nx111nBnPBCc11nPB，此时01NBCCBN01bB：若0111nBnPBCc此表达到最优为非基变量1nx：若0111nBnPBCc此表未达到最优为入基变量，1nx用单纯形法迭代至找到最优解0*1nx新产品不投产例18：（续例）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示，P6=。(1)问它的价值系数c6符合什么条件才必须安排它的生产？(2)设c6=3，新的最优生产计划是什么？2/112/36P21-01105-212/112/302/11=B－1P6==解：(1)σ6=c6－CBB－1P6=c6－（0，5，4）=c6－5/202/11σ60,说明新产品D不宜投产，否则会使产品总利润下降cj54000c6CBXBbx1x2x3x4x5x60x3250012-55x1351001-14x210010-12000-1-3最优单纯形表Cj540003CBXBbx1x2x3x4x5x60x3250012-5[1]5x1351001-11/26x210010-120σj000-1-31/23x6250012-515x145/210-1/203/204x210010-120σj00-1/2-2-1/20(2)4.约束条件增减的变化分析如果当前最优解满足新增约束条件，则最优解不变；否则，增加约束条件体现在单纯形表中，相当于多了一行，从而增加一个基变量，同时还要增加一列。增加一个约束后，可行域的变化为R’⊆RR’为空集，新问题无可行解删除一个约束条件若这个约束条件对来说是不起作用约束，即松弛变量，剩余变量不为零，则去掉这个约束条件对最优解无影响。反之，则使最优解发生变