第6章+对偶问题和灵敏度分析.ppt

1、灵敏度分析与对偶,王广民 中国地质大学 经济管理学院 ,一、线性规划的对偶问题,1、问题的提出,生产问题,分析： 决策者显然要考虑两个因素： 第一，每种资源所收回的费用应不底于自己生产时所获得的利润； 第二，定价又不能太高，要使对方容易接受。,资源定价问题,(DP),(LP),2、对称形式的原始对偶问题,对称形式 LP与DP之间的关系：,A,b,c,y,x,3、对称形式的对偶规则,给每个原始约束条件定义一个非负对偶变量yi(i=1,2,m)； 使原问题的目标函数系数 cj 变为其对偶问题约束条件的右端常数； 使原问题约束条件的右端常数 bi 变为其对偶问题目标函数的系数； 将原问题约束条件的系

2、数矩阵转置，得到其对偶问题约束条件的系数矩阵； 改变约束问题不等号的方向，即将“”改为“”； 原问题为“max”型，对偶问题为“min”型。,4、一般的线性规划问题的对偶问题,混合型问题的对偶规则：,原问题为“max”，对偶问题为“min”； 原问题中目标函数系数 ci 变为其对偶问题约束条件的右端常数； 原问题约束条件的右端常数 bi 变为其对偶问题目标函数的系数； 原问题约束条件的系数矩阵转置，即为其对偶问题的系数矩阵； 原问题的变量个数n等于其对偶问题的约束条件个数n，原问题 约束条件的个数m等于其对偶问题变量的个数m； 在求极大值的原问题中，“”，“”和“=”的约束条件分别对应其对偶变

3、量“0”，“0”和“无符号限制”； 在求极大值的原问题中，变量“0”，“0”和“无符号限制”分别对应其对偶约束条件的“”，“”和“=”约束.,对偶规则表,二、对偶原理,对偶原理给出了原问题和对偶问题之间的重要关系.,为了讨论问题方便我们以“对称形式”来进行研究和证明，当然所有这些结论对于其它形式的对偶问题也同样成立。,定理1（对称性）对偶问题的对偶是原问题.,定理2（弱对偶定理）,分别是问题(P)和(D)的可行解，,设,和,则必有,注：推论2不存在逆.,推论1：若 X0 和Y0 分别是问题(P)和(D)的可行解，则 （1） CX0是问题(D)的目标函数的一个下界；（2） Y0 b是问题(P)的

4、目标函数的一个上界。,推论3：在一对对偶问题(P)和(D)中，若其中一个问题有可行解，而另一个无可行解，则该问题无界.,推论2：在一对对偶问题(P)和(D)中，若其中一个问题有可行解，但目标函数无界，则另一个问题无可行解.,定理4（对偶定理） 若一对对偶问题（P）和（D）一个有最优解，则另一个也有最优解，且目标函数的最优值必相等.,定理5 （互补松弛定理）,设 X* 和Y* 分别是问题（P）和（D）的可行解，则它们分别是最优解的充要条件是 同时成立：,定理3(最优性判别定理) 若X*和Y*分别是问题(P)和(D)的可行解，且CX*=Y*b， 则X*，Y*分别是问题(P)和(D)的最优解.,紧约

5、束与松约束,一个约束称为紧约束，如果该约束在所有最优解上的值使左右取等号。 即我们把严格等式约束称为紧约束（或起作用约束）.,不是紧约束的约束称为松约束。 即把某一最优解处取严格不等式的约束称为松约束（或不起作用约束）。,以上关系称为对偶问题的互补松弛关系或松紧关系。在计算上，若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解.,松紧关系,非常重要,对于最优解X*和Y*而言，松约束的对偶约束是紧约束.,1、简介 在线性规划中，若某个约束条件的右端常数bi增加1个单位时，所引起的目标函数最优值Z* 的改变量称为第i个约束条件的影子价格。影子价格又称为边际价格。 影子价格的经济意义是

6、在其它条件不变的情况下，单位资源变化所引起的目标函数最优值的变化，即对偶变量yi就是第i个约束条件的影子价格。 影子价格是针对某一具体的约束条件而言的，而问题所有其他数据都保持不变，因此影子价格也可以理解为目标函数最优值对资源的一阶偏导数.,三、影子价格,考虑一对对称的对偶问题,从对偶问题的基本性质可知，当(P)问题求得最优解 x* 时，(D)问题也得到最优解 y*，,且有,在上式中对 z 求,的偏导数，得：,的值相当于在资源得到最优利用的生产,每增加一个单位时目标函数z的增量，,这说明,条件下，,所以，影子价格是一种边际价格.,影子价格说明增加哪一种资源对增加经济效益最有利. 三种资源的影子

7、价格为（0,1,3），说明首先应考虑增加资源C，因为相比之下它能给收益带来的增加最大. 影子价格又是一种机会成本. 企业经营决策者可以把本企业资源的影子价格与当时的市场价格进行比较，当年i种资源的影子价格高于市场价格时，则企业可以买进该种资源；而当某种资源的影子价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，以获得较大的利润 企业在新产品投产之前，可利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产. 利用影子价格分析现有产品价格变动时资源紧缺情况的影响。 利用影子价格可以帮助分析工艺改变后对资源节约的收益. 根据互补松弛定理可知，当一种资源的影子价

8、格为0时表明这种资源尚未用完，而当一种资源的影子价格大于0时，表明这种资源已经用完，属于紧缺资源，增加这种资源可以增加总的利润。,2、影子价格在经营管理中的应用,影子价格能批示企业内部挖潜的方向 利用影子价格进行企业经济活动分析，不仅可以实现资源的最优配置，而且可以指明企业内部挖潜的主攻方向。因为影子价格能指出各种资源在实现企业最优目标时的影响作用，影子价格愈高的资源，表明它对目标增益的影响愈大，同时也表明这种资源对该企业来说愈稀缺和愈贵重，企业的管理者就应该更加重视对这种资源的管理，通过挖潜革新、降低消耗或及时补充该资源，以保证给企业带来较大的收益。对影子价格大于零的资源都应采取措施，增加投

9、入以保证生产正常进行，实现利润最大化。 紧缺资源 对影子价格为零的资源，企业的管理者也不能忽视，这种资源对该企业来说是相对富裕的。一方面，可以向另的企业转让这种资源或者以市场价出售，以免形成积和浪费；另一方面，通过企业内部的改造、挖潜和增加对影子价格大于零的资源投入后，使原有的剩余资源又可以得到充分利用，而变为新的紧缺资源（变为影子价格大于零）。这样不断调整、补充，真正实现资源的合理利用 影子价格在企业经营决策中的作用 因为影子价格不是市场价格，它是根据企业本身的资源情况 、消耗系数 和产品的利润计算出来的一种价格，是新增资源所创造的价值，是边际价格。不同的企业，即使是相同的资源（例如钢材），

10、其影子价格也不一定相同。就是同一个企业，在不同的生产周期，资源的影子价格也不完全一样。因此，企业的决策者可以把本企业资源的影子价格与当时的市场价格进行比较，当第 种资源的影子价格高于市场价格时，则 企业可以买进该种资源，以获得较大的利润，随着资源的买进和卖出，它的影子价格也将发生变化，直到影子价格与市场价格保持同等水平时，才处于平衡状态。所以我们说影子价格又是一种机会成本，它在决定企业的经常策略中起着十分重要的作用。,3、影子价格在经济管理中的应用,四、对偶单纯形法,对偶规划可以用线性规划的单纯形法求解。 由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题

11、的解，反之依然。 互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。 对偶单纯形法是求解线性规划的另一个基本方法，它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。,先回顾一下单纯形算法：它是从线性规划的一个基可行解迭代到另一个基可行解的过程，在迭代过程中，保持基解的可行性，逐步消除基解的检验数的非负性，即,1、对偶单纯形法的基本思想,为了求解线性规划，我们也可以从线性规划的一个基解迭代到另一个基解，在迭代过程中，保持基解的检验数的非正性，逐步消除基解的不可行性，即,概念：正则解,如果原问题(P)的一个基解X 对应的检验数向量满足条件,则称X为(P)的一个正则解

12、，同时称这一基为正则基.,求解原问题(P)时，可以从(P)的一个正则解开始,迭代到另一个正则解，使目标函数值增加，当迭代到正则解满足原始可行性条件(即xi0)时，就找到了原问题(P)的最优解。这一方法称为对偶单纯形法.,2、对偶单纯法的迭代步骤：,（1）找一个正则基B和初始正则解X(0)，将问题（P）化为关于基B的典式，列初始对偶单纯形表.,设正则解,的典式为：,将上面的典式转换成前面所学习过的单纯形表：,为换出变量。若,（3）确定换出变量：若,则取相应的变量,则迭代停止，原问题无解；否则转下一步。,找初始正则解X0及可行基B,对偶单纯法计算框图,3、初始正则解的确定(略),4、对偶单纯形法的

13、理论解释,对偶单纯形法所使用的表格与原单纯形法一样，可将典式中的数据放在原单纯形表上，即得到对偶单纯形表，所不同的是这里保证在整个过程中,而不保证,这就是为什么我们从本章起,不强调右端常数非负这个条件的原因。,即右端常数中可以出现负数.,设正则基 的典式为：,对偶单纯形表,对偶单纯形法的迭代方式与原单纯形法基本一致.所不同的是：先定换出变量，再定换入变量，决定主元并作基变换得到一个新的正则解X(1),从而完成一次迭代.算法的后半部分与原单纯形法完全一致.,(2)再选进基变量:假定xk为进基变量, 我们分析一下xk 应满足什么条件,才能使迭代后得到的解仍为问题(P)的正则解.,(1)先选出基变量

14、:若 则取与 相对应的基变量 xr 为出基变量.,因为 ,而换基运算的第一步是用主元 去除第r 行中的各元素,为了使变换后 为正数,所以主元 必须从第r 行的负元素中选取,即 .,设主元处在第 k 列,于是换基运算后,各检验数变为,因为要求迭代后得到的解仍为正则解,于是,又因为,于是当 时,不等式(1)自然成立;,由此,则取与之相对应的非基变量 为换入变量。,否则,当 时,要使不等式(1)成立,必须,又因为,于是当 时,不等式(1)自然成立;,最后证明对应于新的正则解X(1),对偶问题(D)的目标函数值将得到改善.,这样,上述求极大值问题(P)的迭代过程,实质上是在对对偶问题(D)求极小值,所

15、以目标函数越小就越接近最优解.直到得到对偶问题(D)的最小值,相应地也就求出了原问题(P)的最大值.,出基变量 与进基变量 xk 确定以后,以 为主元进行换基运算(方法与原单纯形法相同)即可得新的正则解X(1) .,这是因为 ,故,和原始单纯形法一样,若对偶问题是非退化的(即对偶问题的每一个基可行解都是非退化的,或者说,对于原问题的每一个正则解，都有 ,则每迭代一次,目标函数都将严格减小,从而一定能在有限次迭代后得到原问题的最优解,或者判定它无解.,容易证明:若 ,且所有的 ,则原问题(P)无解(自己证明).,用对偶单纯形法求解线性规划问题时当约束条件为“”时，不必引进人工变量，使计算简化。

16、当线性规划问题中变量多于约束条件时，用对偶单纯形法计算可以减少工作量。 对偶单纯形法的局限性主要是：对大多数线性规划问题，很难找到一个初始正则解。因此对偶单纯形法一般不单独使用，而主要应用于灵敏度分析及整数规划等有关章节中。,从以上对对偶单纯形法的讨论，可以看到：,因此就会提出以下问题： （1）当参数中的一个或者几个发生变化时，导致决策变量的最优解 X 的变化情况； （2）参数在什么范围内变化时，最优解 X 不会发生变化. 这就是线性规划的灵敏度分析所要研究解决的问题.,1、问题简介,以前讲的线性规划问题中，都假定问题中的A、b、C 是已知常数。但实际上这些数往往是一些估计和预测的数字，如市场

17、条件一变C 值就会变化。 A 是随工艺技术条件的改变而改变而 b 值则是根据资源投入后能产生多大经济效果来决定的一种决策选择。,五、灵敏度分析,灵敏度分析的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。,灵敏度分析（Sensitivity analysis)又称为优化后分析（Postoptimality analysis)。因为它是在已求得线性规划最优解的基础上，来讨论这些数据的变化对最优解的影响。,当然当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。 因为前面已经讲到，单纯形法的迭代计算是从一组基变量变换为另一组基变量

18、表中每步迭代得到的数字只随基变量的不同选择而改变，因此有可能把个别参数的变化直接在计算得到最优解的最终单纯形表上反映出来。 这样就不需要从头计算，而直接对计算得到最优解的单纯形表进行审查，看一些数字变化后，是否仍满足最优解的条件，如果不满足的话，再从这个表开始进行迭代计算，求得最优解.,1. 将参数的改变计算反映到最终单纯形表上来； 2. 检查原问题是否仍为可行解； 3. 检查对偶问题是否仍为可行解； 4. 按下表所列情况得出结论和决定继续计算的步骤,灵敏度分析的步骤可归纳如下：,灵敏度分析,1、价值系数cj的灵敏度分析,从上面的典式的推导可以看出，目标函数的价值系数cj的改变仅仅影响到检验数

19、和最优值,非基变量的价值系数cj的灵敏度分析,设cj有变化量 cj，则记,因此求出对检验数的影响,如果要求最优解保持不变，即,结 论,基变量的价值系数cj的灵敏度分析,设xi是基变量，ci是CB的一个分量，当ci发生变化产生ci时，则多个检验数都会受到影响,其中,可以得到,为了不破坏最优基的情况，即要求,当aij0时 ；,当aij0时,令,则当Di,1ciDi,2时，最优基不变.,结 论,2 资源系数bi的灵敏度分析,当资源系数bi改变时，仅影响最优解和最优值.,设bi改变量为bi,为保证最优基不变，应满足,所以若,若,令,则当Ti,1biTi,2时，最优基不变.,结 论,3 技术系数（资源消耗系数）aij的灵敏度分析,非基变量的系数向量的灵敏度分析,Xj 是非基变量，pj 是其对应的系数列向量， pj是变化量。由,可见变化仅影响xj的检验数，记,为保证最优基不变，即,记,有,令,则当SijaijSij时，最优基不变.,，则最优基地位不变.,若仅限 pj 的一个分量有变动，如aij 变动 aij ，则,结 论,结 论,对于最优基 B 而言，当基变量 的系数列向量 发生变化时，对基 B 及其逆矩阵 都有影响。即不仅影响原先最优解的可行性，也影响到它的最优性，这里不介绍求变化范围的一般公式，而建议按具体的最优化表格进行分析。我们不做讨论。,基变量的系数向量的灵敏度分析,4 增加新