纯形法的灵敏度分析.ppt

第六章 单纯形法的灵敏度分析,一、问题的提出 二、目标函数系数的变化 三、右端项的变化 四、技术系数的变化 五、增加约束条件,一、问题的提出,假设范例 目标函数：Max z= 50x1+100 x2 约束条件：1x1+1x2300 2x1+1 x2400 0x1+1 x2250 x1 0， x2 0 中x2的目标函数系数由100变为75，求新问题的解。,一、问题的提出,解：经过单纯形迭代得到最优表,一、问题的提出,比较范例的最优表：,一、问题的提出,事实上，系数的改变并未改变LP问题的解。 思考： 1、如果C2变为45，最优解会变吗？为保证最优解不变， C2的取值范围？ 2、参数变化时，可否利用原问题的最优表求解，而不必从头进行单纯形迭代，以简化计算？,一、问题的提出,要解决以上问题，需要探讨初始单纯形表与最优单纯形表的关系。 观察范例的单纯形求解过程：,一、问题的提出,事实上，在单纯形表的迭代过程中，最核心的变化是系数矩阵的行变换，其它值如cj在每次迭代中不变，zj和检验数则是根据其它元素计算得出。,一、问题的提出,初始矩阵,最优矩阵,行变换,初始基,初始矩阵变最优矩阵的过程可以表示为：,如，b2变为100，则最优矩阵可计算出：,单纯形法的灵敏度分析基本思路：,1、将某个参数的变化反映在最终表中； 2、看最终表是否还满足最优表的要求：基是否为单位排列阵，检验数是否都非正，b列是否都为非负的数； 3、若满足上述要求则最优基没有改变，若不满足则在新的最终表上继续进行迭代，直到找到新的最优基为止。,二、目标函数系数ck的变化,1、在最终单纯形表中，xk是非基变量 除了xk的检验数外， ck的变化不会影响到最终单纯形表中其它任何数值。 只要xk的检验数仍然非正，最优解和最优值都会保持不变。,如范例，使最优解不变的cj值变化范围？,要使最优解不变，须c3-50 0求得c3 50,二、目标函数系数ck的变化,二、目标函数系数ck的变化,2、在最终单纯形表中， xk是基变量 此时各非基变量的检验数均有可能受到影响，同时还会影响到最优值。 要最优解不变，必须保证所有的检验数非正。,要使最优解不变，须- c10且c1 -100 0 求得0 c1 100,二、目标函数系数ck的变化,要使最优解不变，须50-c2 0求得c2 50,二、目标函数系数ck的变化,要使最优解不变，须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的系数在什么范围内变动时，最优解不变。,课堂练习,解：最优表为,课堂练习,所有j0时，原最优解不变 从表中可得到： -17/7 c1 -3/2 。,课堂练习,从表中看到3= c3 +11/5 0 可得到c3 -11/5 时，原最优解不变。,三、右端项的变化,右端项发生变化时，最优解中变量的取值总会随之变化。 讨论右端项的取值范围时，考虑的是使最优基和对偶价格不变。,三、右端项的变化,例：范例中b1为300，使最优基不变的b1取值范围？ 解：最优表中的b列可表示为Bb0,三、右端项的变化,最优表可表示为：,三、右端项的变化,最优值z* 50b1 +12500 可见b1的对偶价格50。 由b1 -2500推出b1 250 由-2 b1 +650 0推出 325 b1 只要最优基不变，对偶价格也不会变。 即325 b1 250时对偶价格不变。,三、右端项的变化,练习：分析范例b2的变化范围。,对偶价格在单纯形表中的表示,根据对偶价格定义，如果最优目标函数值Z*可以表示为右端项bi的函数，则对于目标函数最大化的LP问题， bi的对偶价格可以表示为数学表达式： 关键是：如何将目标函数表示为bi的函数？,B,CB*,对偶价格在单纯形表中的表示,观察范例最优表：,对偶价格在单纯形表中的表示,由于 故，,最终表中第i个初始基变量的z值,对偶价格在单纯形表中的表示,结论： 各右端项的对偶价格就是其所在方程中初始基变量在最优表中的zj值。 相关概念： 影子价格右端项增加一单位，使最优目标函数值增加的数量。,四、技术矩阵的变化,1、最终单纯形表中非基变量对应的系数列向量由pk pk时，最优表中发生变化的有： 最优矩阵中的第k列，变为 B0pk 最终表中检验数k=ck-CB*T B0pk 若仍有k0，则最优解不变，否则继续迭代，直到找到新的最优解。,四、技术系数的变化,2、对于增加一个变量，从而使得系数矩阵增加一列pn+1的情况： 技术矩阵由mn阶变为m(n+1)阶 在最终表中加入一列pn+1B0 pn+1 然后计算检验数。若n+10，则进行迭代，直到找到新的最优解。,四、技术系数的变化,如范例，新增产品3，价值系数为150，相应增加一个技术列向量p6(2,0.5,1.5)T 则最优矩阵中p6 B 检验数6150-(50,0,100) -25。,四、技术系数的变化,所有检验数仍然小于0，故最优基和最优解不变。 说明增加了产品3并不改变原生产计划。,四、技术系数的变化,假如产品3的工艺改进，价值系数变为160，技术列向量变为(1.5，2，1)T 则最优矩阵中p6 B 检验数6160-(50,0,100) 35。,四、技术系数的变化,检验数635，还需迭代。,四、技术系数的变化,3、最终单纯形表中基变量对应的系数列向量由pk pk时，原最优解的可行性和最优解都可能遭到破坏，情况比较复杂，一般重新求解。,五、增加约束条件,在原线性规划中增加一个约束条件时，先将原问题的最优解的变量值代入新增的约束条件。 如果满足，则说明新增的条件没有起到限制作用，故最优解不变； 如果不满足，则将新增的约束添入原最终单纯形表中进一步求解。,五、增加约束条件,如范例，新增约束条件电量限制5000度，生产一个产品1需要用电10度，生产一个产品2需要用电30度。 即，10x1+30x25000 原最优解（50，250，0，50，0）代入， 10x1+30x280005000，不满足，须迭代。,五、增加约束条件,引入松弛变量x6， 10x1+30x2 + x65000,五、增加约束条件,用行变换将基变量对应的系数列向量化为单位列向量：,课堂练习,对于LP问题： Max z = 2x1 + 3x2 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0,课堂练习,分析： 1、使最优解不变的系数c2的取值范围； 2、使最优基不变的b1的取值范围； 3、若增加x6 , p6=( 2, 6, 3 )T, c6=5，最优解如何？ 4、若增加3x1+ 2x215，最优解如何？,课堂练习,解：原问题最优表为,课堂练习,1、由-c2 /2 0， c2/8-1/2 0 ， 得c2的取值范围：（0，4）,课堂练习,2、用b1表示最优表中的右端项：,初始基在最优 表中的形式,课堂练习,由于最优表右端项有非负要求，即 解得b1的取值范围：（4，10）,0,课堂练习,3、增加p6=( 2, 6, 3 )T ，最优表中增加列：,初始基在最优 表中的形式,课堂练习,最优表变为：,课堂练习,用单纯形法进一步求解，可得： X* = ( 1,1.5,0,0