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

第六章 单纯形法的灵敏度分析,一、问题的提出 二、目标函数系数的变化 三、右端项的变化 四、技术系数的变化 五、增加约束条件,一、问题的提出,假设范例 目标函数：Max z= 50x1+100 x2 约束条件：1·x1+1·x2≤300 2·x1+1 ·x2≤400 0·x1+1 ·x2≤250 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是基变量此时各非基变量的检验数均有可能受到影响，同时还会影响到最优值 要最优解不变，必须保证所有的检验数非正要使最优解不变，须- c1≤0且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 - 4x3S.t. -x1-2x2-x3+x4 = - 3-2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 ≥0 分别分析目标函数中x1和x3的系数在什么范围内变动时，最优解不变。

课堂练习,解：最优表为,课堂练习,所有σj≤0时，原最优解不变 从表中可得到： -17/7≤ c1 ≤ -3/2 课堂练习,从表中看到σ3= c3 +11/5 ≤0 可得到c3 ≤ -11/5 时，原最优解不变三、右端项的变化,右端项发生变化时，最优解中变量的取值总会随之变化讨论右端项的取值范围时，考虑的是使最优基和对偶价格不变三、右端项的变化,例：范例中b1为300，使最优基不变的b1取值范围？ 解：最优表中的b列可表示为B×b0,×,＝,三、右端项的变化,最优表可表示为：,三、右端项的变化,最优值z*＝ 50b1 +12500 可见b1的对偶价格50 由b1 -250≥0推出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’ 若仍有k≤0，则最优解不变，否则继续迭代，直到找到新的最优解四、技术系数的变化,2、对于增加一个变量，从而使得系数矩阵增加一列pn+1的情况： 技术矩阵由m×n阶变为m×(n+1)阶 在最终表中加入一列pn+1’＝B0 pn+1 然后计算检验数若n+1>0，则进行迭代，直到找到新的最优解四、技术系数的变化,如范例，新增产品3，价值系数为150，相应增加一个技术列向量p6＝(2,0.5,1.5)T则最优矩阵中p6’ ＝B× ＝检验数6＝150-(50,0,100) × ＝-25四、技术系数的变化,所有检验数仍然小于0，故最优基和最优解不变说明增加了产品3并不改变原生产计划四、技术系数的变化,假如产品3的工艺改进，价值系数变为160，技术列向量变为(1.5，2，1)T则最优矩阵中p6’ ＝B× ＝检验数6＝160-(50,0,100) × ＝35。

四、技术系数的变化,检验数6＝35，还需迭代四、技术系数的变化,3、最终单纯形表中基变量对应的系数列向量由pk→ pk’时，原最优解的可行性和最优解都可能遭到破坏，情况比较复杂，一般重新求解五、增加约束条件,在原线性规划中增加一个约束条件时，先将原问题的最优解的变量值代入新增的约束条件 如果满足，则说明新增的条件没有起到限制作用，故最优解不变； 如果不满足，则将新增的约束添入原最终单纯形表中进一步求解五、增加约束条件,如范例，新增约束条件——电量限制5000度，生产一个产品1需要用电10度，生产一个产品2需要用电30度 即，10x1+30x2≤5000 原最优解（50，250，0，50，0）代入， 10x1+30x2＝8000>5000，不满足，须迭代五、增加约束条件,引入松弛变量x6， 10x1+30x2 + x6＝5000,五、增加约束条件,用行变换将基变量对应的系数列向量化为单位列向量：,课堂练习,对于LP问题：Max z = 2x1 + 3x2 s.t. x1 + 2x2 + x3 = 84x1 + x4 = 16 4x2 + x5 = 12x1 , x2 , x3 , x4 , x5 ≥ 0,课堂练习,分析： 1、使最优解不变的系数c2的取值范围； 2、使最优基不变的b1的取值范围； 3、若增加x6 , p6=( 2, 6, 3 )T, c6=5，最优解如何？ 4、若增加3x1+ 2x2≤15，最优解如何？,课堂练习,解：原问题最优表为,课堂练习,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,0,2 )T z* = 16.5,课堂练习,4、增加3x1+ 2x2≤15，原最优解不满足这个约束，故在原最优表上增加相应行列：,课堂练习,通过行变换，将基向量变为单位列,课堂练习,经添加人工变量，迭代后，可得： 最优解为（3.5, 2.25, 0, 0, 3, 2 )T， 最优值为 13. 75,作业,教材124页第5题。