吉林大学本科运筹学课件-对偶理论与灵敏度分析.ppt

Chapter2 对偶理论 ( Duality Theory ),线性规划的对偶模型 对偶性质 对偶问题的经济解释影子价格 对偶单纯形法 灵敏度分析,本章主要内容：,对偶理论是线性规划的重要内容之一。随着线性规划问题研究的深入，人们发现对应于每个线性规划问题都伴生一个相应的线性规划问题。 前者是由矩阵，右端向量和价值向量定义的，称之为原问题； 后者也是由相同的数据集合，和构成的，称之为原问题的对偶问题。 一对原问题和对偶问题是紧密关联的，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。对偶理论深刻地指示了原问题和对偶问题的内在联系，由对偶问题引伸出来的对偶解还有着重要的经济意义，是研究经济学的重要概念和工具之一。,线性规划的对偶模型,设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表 ：,产品数据表,问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？,1. 对偶问题的提出,线性规划的对偶模型,解：设甲、乙型产品各生产x1及x2件，则数学模型为：,反过来问：若工厂决策者决定不再自己生产甲、乙产品，而是把各种设备的有限机时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价，才是最佳决策？,线性规划的对偶模型,在市场竞争的时代，厂长的最佳决策显然应符合两条： （1）不吃亏原则。把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润。由此原则，便构成了新规划的不等式约束条件。 （2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。,设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：,线性规划的对偶模型,把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。,原问题与对偶问题对比表,对偶性是线性规划问题的最重要的内容之一。每一个线性规划（ LP ）必然有与之相伴而生的另一个线性规划问题，即任何一个求 maxZ 的LP都有一个求 minZ 的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。,线性规划的对偶模型,2. 原问题与对偶问题的对应关系,原问题-P,对偶问题-D,线性规划的对偶模型,线性规划的对偶模型,（1）对称形式,特点：目标函数求极大值时，所有约束条件为号，变量非负;目标函数求极小值时，所有约束条件为号，变量非负.,线性规划的对偶模型,例2.1 写出线性规划问题的对偶问题,解：首先将原问题变形为对称形式,注意：以后不强调等式右段项 b0，原因在对偶单纯型表中只保证 而不保证 ，故 b可以是负数。,线性规划的对偶模型,线性规划的对偶模型,(2) 非对称型对偶问题,若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按教材表2-2中的对应关系写出非对称形式的对偶问题。,线性规划的对偶模型,线性规划的对偶模型,例2.2 写出下列线性规划问题的对偶问题.,解：原问题的对偶问题为,无约束,线性规划的对偶模型,例2.3 写出下列线性规划问题的对偶问题.,解：原问题的对偶问题为,线性规划的对偶模型,例2.4,线性规划的对偶模型,对偶性质,性质1 对称性定理：对偶问题的对偶是原问题,min Z= - CX s.t. - AX - b X 0,max W = -Yb s.t. -AY -C Y 0,对偶性质,性质2 弱对偶原理(弱对偶性)：设 和 分别是问题(P)和(D)的可行解，则必有,推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。,推论2: 在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解（如果原问题没有上界，即maxZ+，则对偶问题不可行。如果对偶问题没有下界，即minW-，则原问题不可行 ）；反之不成立(即无可行解的原因有二）。这也是对偶问题的无界性。,对偶性质,例2.5,对偶性质,推论3：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题目标函数值无界。,试估计它们目标函数的界，并验证弱对偶性原理。,（P）,例2.6,对偶性质,解：,（D）,对偶性质,性质3 最优性定理：如果 是原问题的可行解， 是其对偶问题的可行解，并且:,则 是原问题的最优解， 是其对偶问题的最优解。,例如:在一对对偶问题（P）和（D）中，可找到 X*=（0.0.4.4）， Y*=（1.2，0.2）,且Z=W=28 ， 则X*，Y*分别是 P和D 的最优解。,对偶性质,性质4 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,（还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。）,推论 若原问题有一个对应于基的最优解，那么此时的单纯形乘子 是对偶问题的一个最优解。 根据这个推论我们可以在原问题的最优单纯形表中直接找到对偶问题的最优解，即松弛变量检验数的相反数 。,对偶问题可改写为,原问题的检验数对应对偶问题的一个基本解。 证明：设是原问题的一个可行基， 且 则原问题可以写为,其中 分别为原问题决策变量中基变量和非基变量所对应的对偶约束的剩余变量。 对偶问题也可等价表示为：,对原问题可行基，可得可行解 对应于 的检验数分别为 。 不难验证， 为对偶问题的一个基本解。,例 利用单纯形表求原问题的最优解，并由最优单纯形表推出对偶问题的最优解。 解：原问题线性规划模型为： 引入松弛变量 ， 化标准形得:,1 0 -2/3 0 1/3,4/3,X1,32,0 0 1/3 1 -2/3,3/4,X4,0,4/2,1 0 0 2 -1,4,X1,32,4/3,0 0 1 3 -2,4,X3,0,8/4/5,1 4/5 0 1/5 0,8,X1,32,12/8/5,0 8/5 1 -3/5 0,12,X3,0,40/5,5 4 0 1 0,40,X4,0,36/3,3 4 1 0 0,36,X3,0,0 0 -7/6 0 -19/6,Z,0 1 3/4 0 -1/4,8,X2,30,0 0 0 7/2 -11/2,278,Z,0 1 0 -9/4 5/4,5,X2,30,0 22/5 0 -32/5 0,256,Z,4/4/5,0 4/5 0 -9/5 1,4,X5,0,32 30 0 0 0,0,Z,76/9,9 8 0 0 1,76,X5,0,X1 X2 X3 X4 X5,b,XB,CB,32 30 0 0 0,C,由最优表可知，原问题最优解 同时不难得到原问题的最优基 由强对偶定理的推论可得此时的单纯形乘子 为对偶问题的最优解,即松弛变量检验数的相反数。,对偶性质,性质5 互补松弛性：设X0和Y0分别是P问题 和 D问题 的可行解，则它们分别是最优解的充要条件是：,其中：Xs、Ys为松弛变量（松驰变量*对偶变量=0）,对偶性质,性质5的应用：,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零。,该性质给出了已知一个问题最优解求另一个问题最优解的方法.,对偶性质,例2.7 已知线性规划,的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。,解：写出原问题的对偶问题，即,标准化,对偶性质,设对偶问题最优解为Y(y1，y2),由互补松弛性定理可知，X和 Y满足：,即：,因为X1=60，X2=20，所以对偶问题的第一、二个约束的松弛变量等于零，即y30，y40，带入方程中：,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为： Y=(1,1)，最优值w=26。,对偶性质,例2.8 已知线性规划,的对偶问题的最优解为Y=(0,-2)，求原问题的最优解。,解: 对偶问题是,标准化,无约束,对偶性质,设对偶问题最优解为X(x1，x2 ，x3)T ,由互补松弛性定理可知，X和 Y满足：,将Y =(0,-2)带入由方程可知，y3y50，y41。,y2=-20 x50 又y4=10 x20,将x2，x5分别带入原问题约束方程中，得：,解方程组得：x1=-5,x3=-1, 所以原问题的最优解为,X=(-5,0,-1)，最优值z=-12,对偶性质,原问题与对偶问题解的对应关系小结,对偶问题的经济解释影子价格,1. 影子价格的数学分析：,定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi （第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z* 的改变量称为第 i 种资源的影子价格，其值等于D问题中对偶变量yi*。,由强对偶定理可知，如果原问题有最优解 ，那么对偶问题也有最优解 ，而且它们的目标函数值相等，即有： 其中 是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。 为对偶问题最优解，它代表在资源最优利用条件下对各种单位资源的估价，这种估计不是资源的市场价格，而是根据资源在生产中所作出的贡献（如创造利润、产值等）而作出估价。,对偶问题的经济解释影子价格,2. 影子价格的经济意义 1）影子价格是一种边际价格 在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量yi 就是第 i 种资源的影子价格。即：,对偶问题的经济解释影子价格,2）影子价格是一种机会成本,在市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进这种资源用于扩大生产；相反当某种资源的市场价格高于影子价格时，企业应卖出这种资源。随着资源的买进卖出，企业资源的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。,影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。如果第i种资源供大于求，即在达到最优解时，该种资源没有用完，或松弛变量 ，由互补松弛定理，在对偶最优解 中，第i种资源的影子价格 。反之如果第i种资源的影子价格 ，那么由互补松弛定理，原问题的第i个约束为严格等式，即 ，这表明第i种资源已经用完，成为稀缺资源。,3）影子价格在资源利用中的应用,对偶问题的经济解释影子价格,对偶问题的经济解释影子价格,4）影子价格对单纯形表计算的解释,单纯形表中的检验数,其中cj表示第j种产品的价格; 表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。,当产值大于隐含成本时，即 ，表明生产该项产品有利，可在计划中安排；否则 ，用这些资源生产别的产品更有利，不在生产中安排该产品。,例,对偶最优解 其中 为设备A的影子价格， 在资源最优利用的条件下，设备A每增加 一个单位台时，可以使总利润增加 元。 若设备可供台时数，则,对偶单纯形法,对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。,对偶单纯形法原理,对偶单纯形法基本思路：,找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，(即必须保持所有的检验数非正，同时取消原问题必须可行的要求，即取消常数列的非负限制)，判断XB是否可行（XB=b为非负），有最优解。否则，通过变换基解，直到找到原问题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解。,对偶单纯形法,找出一个DP的可行基,LP是否可行 （XB 0）,保持DP为可行解情况下转移到LP的另一个基本解,最优解,是,否,循 环,结束,对偶单纯形法,例2.9 用对偶单纯形法求解：,解:（1）将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行（求max问题）。,对偶单纯形法,对偶单纯形法,对偶单纯形法,原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72 由定理4，其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），W*= 72,对偶单纯形法,对偶单纯形法应注意的问题：,用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解,初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则,对偶单纯形法,对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；,普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是,其目的是保证下一个对偶问题的基本解可行,对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。,灵敏度分析,一个标准形式的线性规划问题可由约束矩阵，右端项向量b，和价值向量完全确定，假如一个线性规划问题对于给定的数据集合，b，有最优解，则最优解 。最优目标函数值 ，其中为最优基。 但是线性规划问题所对应的数据集合，b，常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。因此有必要来分析一下当这些数据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。,灵敏度分析主要讨论如下二类问题： 线性规划的数据集合在什么范围内波动将不影响最优解或最优基？ 若最优解发生变化，应如何用最简单的方法找到新的最优解。 为讨论方便，以下列出标准型线性规划问题最优单纯形表的一般形式，其中B为线性规划问题的最优基：,灵敏度分析,线性规划问题的标准形式,令：,灵敏度分析,一、 价值系数cj的变化分析(将c的变化直接反映到最终单纯形表）,例1-1：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划,问题： （1）确定x2的系数c2的变化范围，使原最优解保持最优； （2）若c2=6，求新的最优计划。,灵敏度分析,最优表如下：,灵敏度分析,4 = c25 0 5 = 52c2 0 5/2 c2 5,最优解X*=（35，10，25，0，0）保持不变。,（1）,灵敏度分析,（2）,用单纯形法求解得。,x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=405/2,例1-2 某工厂用甲乙两种原料生产A，B，C，D四种产品，每种产品的利润，现有原料数及每种产品消耗原料定额如表所示：,问应该怎样组织生产，才能使总利润最大，若产品或的利润产生波动，波动范围多大时，原最优解保持不变？ 解：设生产，四种产品 各 万件，则此问题的 线性规划模型为：,标准化，引入松弛变量x5,x6， 利用单纯形表求解：,-4 -2/3 0 0 -13/3 -10/3,88,Z,2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3,2 1,X4 X3,19 50,0 2 0 2 -3 -10,84,Z,2 6,1 2/3 0 1/2 1/3 -5/3 0 0 1 1/4 0 1/2,1 3/2,X1 X3,9 50,9 8 0 13/2 0 -25,75,Z,1 -,3 2 0 3/2 1 -5 0 0 1 1/4 0 1/2,3 3/2,X5 X3,0 50,9 8 50 19 0 0,0,Z,9/5 3/2,3 2 10 4 1 0 0 0 2 1/2 0 1,18 3,X5 X6,0 0,X1 X2 X3 X4 X5 X6,B,XB,CB,9 8 50 19 0 0,C,即最优生产方案是生产产品1万件，产品2万件， 不生产,两种产品。可得最大利润为88万元。,最优表：,(1)若产品的利润 ，有改变量 。因为 为非基变量， 推得 4 或 （万元）时,原最优解 不变，最优利润值 （万元）也不变。,()若产品的利润 ，有改变量 。因为 为基变量， 推得,原最优解不变，最优利润值 （万元）,即当,时,灵敏度分析,二、右端常数bi的变化分析,XB= B1b,例2：对于上例中的线性规划作下列分析： （1）b3在什么范围内变化，原最优基不变？ （2）若b3=55，求出新的最优解。,灵敏度分析,灵敏度分析,（1）,XB=B1b=,解得40b350，即当b340，50 时，最优基B 不变,灵敏度分析,（2）当 b3= 55 时,=,最优解：X*=（30，20，0，0，5）,灵敏度分析 例1,最优表如下：,灵敏度分析,三、增加一个变量 的分析,例3：（续例1）设企业研制了一种新产品， 对三种资源的消耗系数列向量以P6表示P6= 。问它的价值系数c6符合什么条件才必须安排它的 生产？设c6=3，新的最优生产计划是什么？,6=c6CBB1P6 =c6（0，5，4） = c65/2,灵敏度分析,灵敏度分析 例1,最优表如下：,灵敏度分析,四、 增加新的约束条件的分析（直接添加到最终单纯形表中）,例4: 假设在例1中，还要考虑一个新的资源约束： 4x1+2x2150,标准化,灵敏度分