运筹学_12灵敏度分析CA

OperationalResearch灵敏度分析之二ZHUTongChang’anUniversityE-mail:[e-mail].2012HomeHomeOperationalResearch2知识回顾与本次课程提纲知识点•灵敏度分析围绕的核心问题：•最优基不变时的参数范围。•操作方法：•约束条件大于等于零；检验数小于等于零。•约束条件b的分析：•公式法VS.数字法•如最优基不变，只需再解方程组就可求出最优基。OperationalResearch3代数灵敏度分析（约束b）书上解法（公式法）：（1）找到B-1（2）如求b1的改变，则看矩阵中的第一列正元素除-bi最大者为下限负元素除-bi最小者为上限数字法：XB’=B-1（b+Δb）≥0Cj58600bCBXBx1x2x3x4x55x11002－148x2011－118检验数00-2-2－38482b020b-12-020-b224,020121112即bOperationalResearch4代数灵敏度分析（价值系数C）目标：价值系数C在什么范围内变化，最优基不发生变化（见图）情况1：非基变量的价值系数变化情况2：基变量的价值系数变化OperationalResearch5图解灵敏度分析（价值系数C）2x1＋x2≤8x2x1x1＋3x2≤8BCFGDEZ=30x1＋20x2OperationalResearch6代数灵敏度分析（价值系数C）情况一：非基变量的价值系数变化OperationalResearch7代数灵敏度分析（价值系数C）情况一：非基变量的价值系数变化例题：第三种产品发生变化，ΔC3在什么范围内变化，不会使最优基变化？OperationalResearch8代数灵敏度分析（价值系数C）情况一：非基变量的价值系数变化例题：第三种产品发生变化，在什么范围内变化，不会使最优基变化？一般表达式：ΔCj≤-σjP45OperationalResearch9代数灵敏度分析（价值系数C）情况二：基变量的价值系数变化OperationalResearch10代数灵敏度分析（价值系数C）情况二：基变量的价值系数变化例题：第1种产品发生变化，ΔC1在什么范围内变化，不会使最优基变化？OperationalResearch11代数灵敏度分析（价值系数C）情况二：基变量的价值系数变化例题：第1种产品发生变化，ΔC1在什么范围内变化，不会使最优基变化？同样有公式法和数字法两种解法。OperationalResearch12代数灵敏度分析（价值系数C）情况二：基变量的价值系数变化•某线性规划问题如下0,,3054345536..53max321321321321xxxxxxxxxtsxxxzCj31500bCBXBx1x2x3x4x53x11－1/301/3－1/355x3011－1/52/53检验数0-300－130OperationalResearch13代数灵敏度分析（价值系数C）如果C2超出界限＝6在改变Cj和Ϭ情况下，继续迭代Cj36500bCBXBx1x2x3x4x53x11－1/301/3－1/355x3011－1/52/53检验数0200－130Cj36500bCBXBx1x2x3x4x53x11－1/301/3－1/355x3011－1/52/53检验数0200－130OperationalResearch14代数灵敏度分析（价值系数C）Cj36500bCBXBx1x2x3x4x53x11－1/301/3－1/355x3011－1/52/53检验数0200－130Cj36500bCBXBx1x2x3x4x53x1101/34/15－1/566x2011－1/52/53检验数00-22/5－9/536如果C2超出界限＝6在改变Cj和Ϭ情况下，继续迭代OperationalResearch15代数灵敏度分析（价值系数C）Cj36500bCBXBx1x2x3x4x50x415/405/41-3/445/26x23/415/401/415/2检验数-3/20-5/20－3/245Cj36500bCBXBx1x2x3x4x53x1101/34/15－1/566x2011－1/52/53检验数00-22/5－9/536如果C2超出界限＝6在改变Cj和Ϭ情况下，继续迭代OperationalResearch16代数灵敏度分析（代数矩阵系数A）A的变换分为以下几类：•非基变量系数列向量变化。0,0Δ31*31*33PBCPPBCcB33B即OperationalResearch17代数灵敏度分析（代数矩阵系数A）A的变换分为以下几类：•非基变量系数列向量变化。•基变量系数列变化。由于基变量系数变化，因此，不再是E。需要重新寻找基。0,0Δ31*31*33PBCPPBCcB33B即OperationalResearch18代数灵敏度分析（代数矩阵系数A）A的变换分为以下几类：•非基变量系数列向量变化。•基变量系数列变化。由于基变量系数变化，因此，不再是E。需要重新寻找基。•增加新变量xjP49例题0,0Δ31*31*33PBCPPBCcB33B即OperationalResearch19代数灵敏度分析（代数矩阵系数A）A的变换分为以下几类：•非基变量系数列向量变化。•基变量系数列变化。由于基变量系数变化，因此，不再是E。需要重新寻找基。•增加新变量xjP49例题•增加新的约束条件P50例题首先判断原解是否满足新约束条件。增加一行一列。新变量是基变量。原基变量保持为基。继续用单纯形法（或对偶单纯形法）求解。0,0Δ31*31*33PBCPPBCcB33B即OperationalResearch20灵敏度分析的实际意义约束条件b的变化是由设备、工时等限制条件造成的。价值系数C的变化是由市场决定的、技术系数矩阵A的变化是由工艺、技术、管理等的变化带来的。•增加新变量xj，在实际问题中就是新开发出一种产品。OperationalResearch21复习本章重点本章重点•b、C、A变化范围（使最优基不变）OperationalResearch22单纯形法的矩阵表达形式矩阵式•MaxZ=CX•s.t.AX=b，X0其中，字母含义•C为n维行向量[1×n]，X为n维列向量[n×1]•b为m维列向量[m×1]，A为m行n列矩阵[m×n]OperationalResearch23单纯形法的矩阵表达形式B为基，因此，•X分为：基变量和非基变量：XB和XN•A分为：基和非基变量之前的系数：B和N•C分为：CB和CN0Xbs.tAXCXzmaxNBNBCCCXXXNBA,;;,OperationalResearch24单纯形法的矩阵表达形式bBNXBBXBbNXBXbXXNBbAXNBNBNB111,NNBBNBNBXCXCXXCCzCXz,maxmax[m×m][m×1]＋[m×(n-m)][(n-m)×1]NBNBXNBCCbBCz11用XN表达XBOperationalResearch25单纯形法的矩阵表达形式jBjjPBCC1NB1基变量价值系数：bB1新的约束向量认识一下这些家伙NBNBXNBCCbBCz11NBCCBN1检验数：bBCB1最优值：bB1最优解：OperationalResearch26单纯形法的矩阵表达形式结合单纯形表再看看NBNBXNBCCbBCz11Cj31500bCBXBx1x2x3x4x53x11－1/301/3－1/355x3011－1/52/53检验数0-300－130OperationalResearch27基变量价值系数变化023/03/103/423/,3/1,3/43/2,13/,3/51,0,05/15/113/13/13/15,11,0,0011111111111ccccccccccbBCZPBCCBjBjj即目标函数检验数613c355,1*1CbBCzB