运筹学(灵敏性分析).ppt

单纯形法计算的矩阵描述(nm) 若初始矩阵中变量 xj的系数向量为Pj, 迭代后为P’j, 则有 P’j=B-1 Pj 当B为最优基时，应有 令Y=CBB-1, 则 单纯形法和对偶单纯形法步骤 方法的选取 3.灵敏度分析 进一步理解最优单纯性表中各元素的含义考虑问题 Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 . . . am1x1 + am2x2 + … + amnxn = bm x1 ，x2 ，… ，xn ≥ 0 灵敏度分析 价值系数c发生变化： 考虑检验数 灵敏度分析 例3.3: Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 ≥0 灵敏度分析 例：最优单纯形表 灵敏度分析 2、若 cs 是基变量的系数： 设 cs 变化为 cs + ?cs ，那么 ?j’= cj -∑cri arij - ( cs + ?cs ) asj = ?j - ?cs asj ， i ≠ s 灵敏度分析 例3.4: Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 例: 下表为最优单纯形表,考虑 基变量系数c2发生变化 灵敏度分析 右端项 b 发生变化 设分量 br 变化为 br + ?br ，根据第1章的讨论，最优解的基变量 xB = B-1b，那么只要保持 B-1(b + ?b) ≥ 0 ，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。 对于问题 (LP) Max z = cT x s.t. Ax ≤ b x ≥ 0 灵敏度分析 最优单纯形表中含有 B-1=( aij ）i=1,…,m; j=n+1,…,n+m 那么 新的xi=(B-1b)i+?brair i=1,…, m 。 由此可得，最优基不变的条件是 Max {-bi/air?air0}≤?br≤Min{-bi/air?air0} 例3.5: 上例最优单纯形表如下 灵敏度分析 0 0.25 0 这里 B-1 = -2 0.5 1 0.5 -0.125 0 3.灵敏度分析 增加一个变量 增加变量 xn+1 则有相应的pn+1 ,cn+1 。 那么 计算出B-1pn+1 , ?n+1=cn+1-∑cri ari n+1 填入最优单纯形表, 若 ?n+1 ≤ 0 则 最优解不变； 否则，进一步用单纯形法求解。 3.灵敏度分析 例3.6: 例3.4增加x6 , p6=( 2, 6, 3 )T, c6=5 计算得到 灵敏度分析 增加一个约束 增加约束一个之后，应把最优解带 入新的约束，若满足则最优解不变，否则 填入最优单纯形表作为新的一行，引入一 个新的非负变