第六章单纯形法的灵敏度分析

第六章 单纯形法的灵敏度分析一、问题的提出二、目标函数系数的变化三、右端项的变化四、技术系数的变化五、增加约束条件一、问题的提出 假设范例 目标函数： Max z= 50x1+100 x2 约束条件： 1x1+1x23002x1+1 x24000x1+1 x2250x1 0， x2 0 中 x2的目标函数系数由 100变为 75，求新问题的解。一、问题的提出 解：经过单纯形迭代得到最优表2-250-5000j=cj zj21250250507550zj2501001075x25011-2000x450-1010150x10007550比值bi/ai2bx5x4x3x2x1CB基变量 XB迭代次数2-500-5000j=cj zj275005005010050zj25010010100x25011-2000x450-1010150x100010050比值bi/ai2bx5x4x3x2x1CB基变量 XB迭代次数一、问题的提出 比较范例的最优表：一、问题的提出 事实上，系数的改变并未改变 LP问题的解。 思考： 1、如果 C2变为 45，最优解会变吗？为保证最优解不变， C2的取值范围？ 2、参数变化时，可否利用原问题的最优表求解，而不必从头进行单纯形迭代，以简化计算？一、问题的提出 要解决以上问题，需要探讨初始单纯形表与最优单纯形表的关系。 观察范例的单纯形求解过程：迭代次数基 变 量XB CB x1 x2 x3 x4 x5 b比 值bi/ai250 100 0 0 00 x3 0 1 1 1 0 0 300 300/1x4 0 2 1 0 1 0 400 400/1x5 0 0 0 0 1 250 250/1zj 0 0 0 0 0 0j 50 100 0 0 01 x3 0 0 1 0 -1 50 50/1x4 0 2 0 0 1 -1 150 150/2x2 100 0 1 0 0 1 250 _zj 0 100 0 0 -100 25000j 50 0 0 0 -1002 x1 50 1 0 1 0 -1 50x4 0 0 0 -2 1 1 50x2 100 0 1 0 0 1 250zj 50 100 50 0 50 27500j 0 0 -50 0 -50一、问题的提出 事实上，在单纯形表的迭代过程中，最核心的变化是系数矩阵的行变换，其它值如 cj在每次迭代中不变， zj和检验数则是根据其它元素计算得出。一、问题的提出初始矩阵最优矩阵行变换初始基初始矩阵变最优矩阵的过程可以表示为：如， b2变为 100，则最优矩阵可计算出：单纯形法的灵敏度分析基本思路：1、将某个参数的变化反映在最终表中；2、看最终表是否还满足最优表的要求：基是否为单位排列阵，检验数是否都非正， b列是否都为非负的数；3、若满足上述要求则最优基没有改变，若不满足则在新的最终表上继续进行迭代，直到找到新的最优基为止。二、目标函数系数 ck的变化1、在最终单纯形表中， xk是非基变量 除了 xk的检验数外， ck的变化不会影响到最终单纯形表中其它任何数值。 只要 xk的检验数仍然非正，最优解和最优值都会保持不变。如范例，使最优解不变的 cj值变化范围？迭代次数基 变量 XB CBx1 x2 x3 x4 x5 b 比 值bi/ai250 100 0 0 02 x1 50 1 0 1 0 -1 50x4 0 0 0 -2 1 1 50x2 100 0 1 0 0 1 250zj 50 100 50 0 50 27500j 0 0 -50 0 -50迭代次数基 变量 XB CBx1 x2 x3 x4 x5 b 比 值bi/ai250 100 c3 0 02 x1 50 1 0 1 0 -1 50x4 0 0 0 -2 1 1 50x2 100 0 1 0 0 1 250zj 50 100 50 0 50 27500j 0 0 c3-50 0 -50要使最优解不变，须 c3-50 0求得 c3 50二、目标函数系数 ck的变化二、目标函数系数 ck的变化2、在最终单纯形表中， xk是基变量 此时各非基变量的检验数均有可能受到影响，同时还会影响到最优值。 要最优解不变，必须保证所有的检验数非正。迭代次数基 变量 XB CBx1 x2 x3 x4 x5 b 比 值bi/ai2c1 100 0 0 02 x1 c1 1 0 1 0 -1 50x4 0 0 0 -2 1 1 50x2 100 0 1 0 0 1 250zj c1 100 c1 0 -c1+100j 0 0 - c1 0 c1-100要使最优解不变，须 - c10且 c1 -100 0求得 0 c1 100二、目标函数系数 ck的变化迭代次数基 变 量XB CB x1 x2 x3 x4 x5 b比 值bi/ai250 c2 0 0 02 x1 50 1 0 1 0 -1 50x4 0 0 0 -2 1 1 50x2 c2 0 1 0 0 1 250zj 50 c2 50 0 c2 - 50j 0 0 -50 0 50 - c2要使最优解不变，须 50-c2 0求得 c2 50二、目标函数系数 ck的变化迭代次数基 变量 XB CBx1 x2 x3 x4 x5 b 比 值bi/ai250 100 0 c4 02 x1 50 1 0 1 0 -1 50x4 c4 0 0 -2 1 1 50x2 100 0 1 0 0 1 250zj 50 100 50-2c4 c4 50+c4j 0 0 2c4-50 0 - c4-50要使最优解不变，须 2c4-50 0且 - c4 -50 0求得 -50 c4 25二、目标函数系数 ck的变化课堂练习 有下列线性规划问题： Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0 分别分析目标函数中 x1和 x3的系数在什么范围内变动时，最优解不变。课堂练习基 变量 XB CBx1 x2 x3 x4 x5 b-2 -3 -4 0 0x1 -2 1 0 7/5 -1/5 -2/5 11/5x2 -3 0 1 -1/5 -2/5 1/5 2/5zj -2 -3 -11/5 8/5 1/5 -28/5j 0 0 -9/5 -8/5 -1/5 解：最优表为课堂练习基 变量 XB CBx1 x2 x3 x4 x5 bc1 -3 -4 0 0x1 c1 1 0 7/5 -1/5 -2/5 11/5x2 -3 0 1 -1/5 -2/5 1/5 2/5zj c1 -3 3/5+7c1/5 6/5-c1/5 -3/5-2c1/5 -6/5+11c1/5j 0 0 -17/5-7c1/5 c1/5-6/5 3/5+2c1/5 所有 j0时，原最优解不变 从表中可得到： -17/7 c1 -3/2 。课堂练习基 变量 XB CBx1 x2 x3 x4 x5 b-2 -3 c3 0 0x1 -2 1 0 7/5 -1/5 -2/5 11/5x2 -3 0 1 -1/5 -2/5 1/5 2/5zj -2 -3 -11/5 8/5 1/5 -28/5j 0 0 c3 +11/5 -8/5 -1/5 从表中看到 3= c3 +11/5 0 可得到 c3 -11/5 时，原最优解不变。三、右端项的变化 右端项发生变化时，最优解中变量的取值总会随之变化。 讨论右端项的取值范围时，考虑的是使最优基和对偶价格不变。三、右端项的变化例：范例中 b1为 300，使最优基不变的 b1取值范围？解：最优表中的 b列可表示为 Bb0 三、右端项的变化 最优表可表示为：迭代次数基 变量 XB CB x1 x2 x3 x4 x5 b比 值bi/ai250 100 0 0 02 x1 50 1 0 1 0 -1 b1 -250x4 0 0 0 -2 1 1 650 -2 b1x2 100 0 1 0 0 1 250zj 50 100 50 0 50 50b1+12500j 0 0 -50 0 -50三、右端项的变化 最优值 z* 50b1 +12500 可见 b1的对偶价格 50。 由 b1 -2500推出 b1 250 由 -2 b1 +650 0推出 325 b1 只要最优基不变，对偶价格也不会变。 即 325 b1 250时对偶价格不变。三、右端项的变化练习：分析范例 b2的变化范围。2-500-5000j=cj zj275005005010050zj25010010100x25011-2000x450-1010150x100010050比值bi/ai2bx5x4x3x2x1CB基变量 XB迭代次数对偶价格在单纯形表中的表示 根据对偶价格定义，如果最优目标函数值 Z*可以表示为右端项 bi的函数，