运筹学基础及应用-胡运权-第二章--线性规划的对偶理论

1、2.线性规划的对偶问题2.1 对偶问题的提出2.2 原问题与对偶问题2.3 对偶问题的性质2.4 影子价格2.5 对偶单纯形法2.6 灵敏度分析 2.6.1 Cj 的变化 2.6.2 bi 的变化 2.6.3 增加一个变量 2.6.4 aij 的变化 2.6.5 增加一个约束条件,2.1 对偶问题的提出,设甲企业有m种资源用于生产n种不同产品，各种资源的拥有量分别为bi(i=1,2, ,m)，又生产每单位的第j 种产品(j=1,2, ,n)消耗第i 种资源aij单位，第j 种产品的单位产值为cj元。若用xj代表第j 种产品的产量，则使该企业获得最大产值的线性规划模型应表示为：,现假定乙企业欲收

2、购甲企业拥有的资源，至少应付出多大代价，才能使甲企业愿意放弃生产活动而出让资源。,显然，甲企业放弃自己组织生产活动的条件是：出让同等数量资源的收益应不低于用其组织生产活动创造的产值。,2.1 对偶问题的提出,设用yi代表乙企业收购一单位的第i 种资源付出的代价，从乙企业角度建立的数学模型为：,2.1 对偶问题的提出,2.2 原问题与对偶问题（一）,2.2 原问题与对偶问题（二）,例1：写出下述线性 规划的对偶问题。,解：根据对偶问题的提出，有：,例2：写出例1中对偶问题的对偶。,解：,结论：原问题与对偶问题之间是互为对偶的关系。,原问题（对偶问题） 目标函数 max n个 0 0 无约束 目标

3、函数中变量的系数 m个 = 约束条件右端项,变量,约束条件,对偶问题（原问题） 目标函数 min n个 = 约束条件右端项 m个 0 0 无约束 目标函数中变量的系数,约束条件,变量,2.2 原问题与对偶问题（三）,没有绝对的原问题，也没有绝对的对偶问题。,例3：写出下述线性规划的对偶问题。,min z= 7x1+4x2 -3x3 -4x1+2x2 -6x324 -3x1 -6x2 -4x3 15 5x2 +3x3 =30 x10 , x2无约束, x3 0,解：,2.2 原问题与对偶问题（四）,=,0,0,无约束,2.3 对偶问题的基本性质,假定线性规划原问题为：,则对偶问题为：,2.3 对

4、偶问题的基本性质,(1) 弱对偶性；,如果 (j=1, ,n)为原问题的任一可行解, (i=1, ,m)是其对偶问题的任一可行解,则恒有,如果 (j=1, ,n)为原问题的任一可行解, (i=1, ,m)是其对偶问题的任一可行解,则恒有,=,(2) 最优性；,如果 (j=1, ,n)为原问题的可行解, (i=1, ,m)是其对偶问题的可行解,且有,则 是原问题的最优解, 是对偶问题的最优解。,(3) 无界性；,如果一线性规划问题具有无界解,则其对偶问题具有无可行解;反之,如果一线性规划问题具有无可行解,则其对偶问题具有无界解或无可行解。,(4) 强对偶性；,如果原线性规划问题具有最优解,则其对

5、偶问题也一定具有最优解,且有maxz=minw。,(5) 互补松弛性；,在线性规划问题的最优解中,如果对应某一约束条件的对偶变量为非零,则该约束条件取严格等式;反之如果约束条件取严格不等式,则其对应的对偶变量一定为零。也即：,(6) 同一张单纯形表中，原问题与 对偶问题之间的关系。,用单纯形法求解线性规划问题时,迭代的每一步在得到原问题一个基本可行解的同时,其检验数行各变量检验数的相反数是其对偶问题的一个基本解;在单纯形表中,原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问题的变量;这些互相对应的变量如果在一个问题的解中是基变量,则在另一问题的解中是非基变量;将这两个解代入各自的

6、目标函数中有z=w。,2.4 影子价格,根据对偶理论的基本性质，单纯形表迭代的每一步中，原问题与对偶问题的目标函数恒有,式中yi 表示对一单位第i种资源的估价，这种估价有别于市场价格，是根据资源的拥有量及其在生产中所起的作用而进行的估价。也就是说同一种资源在不同的企业中会因为拥有量或者在生产中所起的作用的不同而得到不同的估价，称为资源的影子价格(shadow price)。,正确理解影子价格利用影子价格进行经济分析,2.影子价格是一种边际价格。,上式表明，增加一个单位的第i 种资源所引起的目标函数的增量即为既定条件下第i 种资源的影子价格。,1.影子价格是一种易变价格。在单纯形法迭代过程中，同

7、一变量在不同单纯形表的检验数一般不同，即不同变量在不同生产计划下的估价也不同。,3.影子价格是一种机会成本。由于影子价格有别于市场价格，因此可以根据影子价格与市场价格之间的关系进行决策。当影子价格高于市场价格时，应买入该资源；当影子价格低于市场价格时，应卖出该资源。,4.互补松弛性的经济解释。,根据互补松弛性可以得出一下结论：,上式表明，如果某种资源在生产过程中有剩余，则该资源的影子价格一定为0；如果某种资源的影子价格大于0，则该资源在生产过程中一定已经完全消耗。,5.检验数的经济解释。,式中cj表示第j种产品的单位产值；YA表示生产一单位第j种产品所需的各种资源的影子价格的总和，即一单位第j

8、种产品的隐含成本。当产品产值大于隐含成本时，生产该产品有利可图；反之，不应该生产该产品。,2.5 对偶单纯形法,根据对偶理论，单纯形法的解体思路可以总结为：在保证原问题为可行解的前提下，通过迭代使对偶问题的解不断由非可行解转化为可行解，当原问题与对偶问题同为可行解时，就得到了各自问题的最优解。,能否在保证对偶问题为可行解的前提下，通过迭代使原问题的解不断由非可行解转化为可行解，当两个问题同为可行解时，也可以得到各自问题的最优解。,这就是对偶单纯形法的解体思路。,注意：对偶单纯形法是与单纯形法并列的另一种求解线性规划问题的方法，并不能因为方法中带有“对偶”字样而认为该方法只能用来求解对偶问题，因

9、为原问题与对偶问题本身就是相对而言的。,对偶单纯形法的解题步骤：,1.建立一张单纯形表，通过恰当地处理使表中所有变量的检验数为负数，保证对偶问题的解可行。,2.对偶单纯形法的最优性判断。当原问题迭代为可行解时，就得到了互为对偶的问题的最优解，停止运算；否则转3。,3.确定换出变量。,设bl所在行的基变量为xl，则xl即为换出变量。,4.确定换入变量。,则xk为换入变量，alk为主元素。若无法找到符合条件的xk，则对偶问题无可行解；否则转5。,5.以主元素为核心进行矩阵的初等行变换得到新的基本解，然后转2。,例4：用对偶单纯形法求解下述线性规划问题。,从对偶单纯形法的求解过程可见，该方法有很大的局限性，因此，准确地说对偶单纯形法是辅助求解线性规划问题的方法。,通过单纯形法和对偶单纯形法的对比学习，应掌握两种方法的适用情况和题型，现总结如下：,2.6 灵敏度分析,灵敏度分析是指当线性规划问题中的某一个或几个参数发生变化时，对原最优结论受到影响的分析。参