第3章 运筹学对偶问题.ppt

1、第3章 对偶线性规划,线性规划的对偶问题 对偶问题的基本性质 对偶的经济解释 灵敏度分析*,DUAL,主讲人：晋琳琳,一、线性规划的对偶问题,如何将生产能力出让出去?,设y1,y2和y3分别表示出让资源A，B和C的单价，则穗羊公司同意出让的条件将是 同意出让生产产品I的资源 同意出让生产产品II的资源 购买者希望用最少的代价获得这些资源，因此,这样得到一个新的线性规划问题,称这一问题是原来的LP问题的对偶线性规划问题或对偶问题。,原问题,对偶问题,原问题 max z=C X s.t.AX b X 0,对偶问题 min w=bY s.t. AY C Y 0,C,A,b,min,m,n,1、规范形

2、式下的原问题与对偶问题,LP问题的规范形式,变量：所有变量均具有非负约束 约束条件： 最大化问题 所有约束条件都是“”型 最小化问题 所有约束条件都是“”型,原问题（对偶）,对偶问题（原）,系数矩阵,约束条件右端向量,目标函数系数向量,目标函数系数向量,max z = C X,min w = Y b,AX b,AY C,X 0,Y 0,b,c,约束条件右端向量,目标函数,约束条件,决策变量,原问题变量个数=对偶问题约束条件方程个数 原问题约束条件方程个数=对偶问题变量个数,2、非规范形式下的原问题与对偶问题(x变),2、非规范形式下的原问题与对偶问题(方程变),非规范形式下的对偶关系,方程对变

3、量， 变量对方程； 正常对正常， 不正常对不正常； 变量正常是非负， 方程正常看目标(max ，min )。,初始单纯形表,迭代后的单纯形表,单纯形法的矩阵表示,添加松弛变量XS,将XB的系数矩阵化为单位矩阵,原问题最终单纯形表,对偶问题最终单纯形表,最大化问题检验数的相反数给出了对偶问题的解,原本在对偶关系中，原问题的变量对应着对偶问题的约束条件，原问题的约束条件对应着对偶变量。但在分别添加了松弛变量和剩余变量后，也可以建立原问题变量与对偶问题变量之间的对应关系,注 上表中我们将松弛变量与剩余变量统称为松弛变量,二、对偶问题的基本性质,1、对偶问题的对偶问题是原问题,推论1：原问题任一可行解

4、的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是起原问题目标函数值的上界。 推论2： 原问题 对偶问题 无界解 无可行解 无可行解 无界解,2、弱对偶性 如果 是原问题的可行解， 是其对偶问题的可行解，则：,推论3：原问题 对偶问题 无可行解 + 可行解 对偶问题有无界解 可行解 + 无可行解 原问题有无界解 3、最优性 如果 是原问题的可行解， 是其对偶问题的可行解，且有 则： 是原问题和对偶问题的最优解。 4、强对偶性 X*、Y* 分别是原问题和对偶问题的最优解，则：,5、互补松弛性,在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则其对应的约

5、束条件取等式;反之若一个约束条件为严格的不等式,则其对应的对偶变量为零。,互补松弛性的另一种表述,在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则该约束条件中松弛变量等于零;反之若一个约束条件中松弛变量非零,则其对应的对偶变量为零。,max z = CX s.t. AX + XS = b X, XS0,min w = bY s.t. AY - YS = C Y, YS0,max z = CX s.t. AX b X 0,min w = bY s.t. AY C Y0,X YS = 0 , Y XS = 0,互补松弛关系,X , Xs,Y , Ys,w1 wi wm wm+1

6、wm+j wn+m,x1 xj xn xn+1 xn+I xn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,Xj Ym+j = 0Yi Xn+i = 0( i = 1,2,m ; j = 1,2,n ) 在一对变量中，其中一个大于0，另一个一定等于0,例3.6 已知下面的LP1和LP2为一组对偶规划，且已知LP1的最优解为X=（1.5，1）。试运用互补松弛定理求出对偶问题的最优解Y。,生产计划问题（LP1）,资源定价问题（LP2）,解：由X=（1.5，1）得,联立求解得：,三、影子价格,式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量

7、yi*的意义代表在资源最优利用的条件下对第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格。,设 和 分别是原问题和对偶问题的最优解，则由对偶性质，有,资源的影子价格随企业的生产任务、产品结构的改变而改变 影子价格是资源的边际利润 资源的影子价格也可视为一种机会成本 在生产过程中若某种资源未得到充分利用则其影子价格为零；只有在资源得到充分利用时，其影子价格才可能非零 可以利用影子价格确定企业内部的核算价格，以便控制有限资源的使用和考核下属企业经营的好坏。,Max z=2x1+x2 s.t. 5x215 6x1+2x2 24 x1+x

8、2 5 x1,x20,x2=3,6x1+2x2 =24,x1+x2 =5,最优解,可行域,最优目标函数值的变化：8.5变到8.75，增加1/4,资源的变化：设备B的可用时间增加1小时,根据对偶问题与原问题之间的关系，对最大化问题，在用单纯形法求解原问题时，最终表不但给出了原问题的最优解，而且其检验数的相反数就是对偶问题的最优解。,四、对偶单纯形法,（对偶问题可行解）,保持对偶问题有基可行解，而原问题只是基解，通过迭代，使后者的负分量个数减少，一旦成为基可行解，则原问题与对偶问题同时实现最优解。,对偶单纯形法计算步骤,适应于求解的LP问题：标准化后不含初始基变量，但将某些约束条件两端乘以“-1”

9、后，即可找出初始基变量。 要求：初始单纯形表中的检验数满足最优性条件,对满足上述条件的LP问题，对偶单纯形法的步骤是：,旋转运算。然后回到第2步。,作出初始单纯形表（注意要求）,检查b列的数据是否非负，若是，表中已经给出最优解；否则转下一步,确定换出变量：取b列负数对应的变量为换出变量,确定换入变量：用检验数去除以换出变量行对应的负系数，在除得的商中选取其中最小者对应的变量为换入变量,例 用对偶单纯形法求解如下的LP问题,化成标准形式,将各约束条件两端同乘“-1”得,用对偶单纯形法求解得,最优解：x1=0, x2=1/4, x3=1/2, x4=0, x5=0,最优目标函数值：w*=-8.5（

10、z*=8.5）,注：通常很少直接使用对偶单纯形法求解线性规划问题。,灵敏度分析,将讨论LP问题中的参数 中有一个或几个发生改变时问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变,研究思路,将个别参数的变化直接在计算得到的最终单纯形表中反映出来，这样就不需要从头计算，而直接检查在参数改变后最终表有什么改变，若仍满足最终表的条件，则表中仍给出最优解，否则从这个表开始进行迭代求改变以后的最优解。,灵敏度分析的步骤,将参数的改变计算反映到最终表上来。具体计算公式可以使用 检查原问题是否仍为可行解 检查对偶问题是否仍为可行解 对检查情况按下表进行处理,1、目标函数系数cj

11、变化 例 3.7 C由(3.2)变为(3,1)，请问最优生产计划如何变化？ 解：由原最优单纯形表得：,单纯形迭代得：,所以得到新的最优生产计划为产品I生产2件，产品II不生产，此时总利润上升为6万元。,例3.8假设产品II的价格不变，请问产品I的利润在什么范围内波动时，最优生产计划不变？ 解：假设c1由3变为 ，则,欲使最优生产计划不变，须,2、约束条件右端向量b的变化,例3.9 穗羊公司仓库盘点时发现，资源B的每周可使用量可以增加到5吨，请制定新的最优生产计划。,解：,因为,，所以需要进行对偶单纯形迭代。由原最优单纯形表得：,因为x2=-10，所以令其岀基。 拿检验数所在行除以出基变量所在行

12、，商最小的列对应的元素作为主元素。这里正数和零不能作为主元素 。 本题中第三行只有a34=-20，所以选择a34作为主元素，进行对偶迭代。 迭代的目标： 右端向量划为非负 把基变量所在列划成单位矩阵 基变量检验数化为零。,迭代后得：,3、增加一种新产品,例3.10 穗羊公司研发部门开发了一种新产品III，单位产品对A、B、C三种资源的消耗系数为，该产品单位利润为2万元。问产品III是否应该生产？如果生产，各产品生产量是多少？,解：产品III机会成本,该产品的检验数,，所以应该生产。,将上述数据代入原最优单纯形表得下表：,所以，新的最优生产计划是产品I和产品III分别生产2件和1/2件，产品II不生产，总利润为7万元。,4、增加一个新的约束条件,例3.11：穗羊公司生产部门发现生产除了受到A、B、C三种资源的约束外，还要受到资源D的约束。资源D周可用量为6，生产单位产品I、II对资源D的消耗分别为7/2和2。请制定新的最优生产计划。,解：根据题意，需要在原问题后面增加新约束,将原最优生产计划X=（3/2，1）代入该约束方程得：,不满足新约束条件。将约束方程添加松弛条件得：,将此约束方程代入原最优单纯形表得下表：,将a41、a42化为0得下表：,对偶单纯形迭代得下表：,所以新的最优生产计划是产品I和产品II分别生产2/5件和23/10件，总利润为24