3对偶理论与灵敏度分析解析参考课件.ppt

1、第2章 对偶理论(Duality Theory),一、对偶问题的提出 二、线性规划的对偶理论 三、对偶问题的经济解释-影子价格 四、对偶单纯形法 五、灵敏度分析,一、问题的提出,对偶是什么：对同一事物（或问题），从不同的角度（或立场）提出对立的两种不同的表述。 在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。 （1）周长一定，面积最大的矩形是正方形。 （2）面积一定，周长最短的矩形是正方形。 这种表述有利于加深对事物的认识和理解。 线性规划问题也有对偶关系。,例：资源的合理利用问题,常山机器厂生产、两种产品。这两种产品都要分别在A、B、C三种不同设备上加工。按工艺资料规定，生产每

2、件产品需占用各设备分别为2h、4h、0h，生产每件产品需占用各设备分别为2h、0h、5h，已知各设备计划期内用于生产这两种产品的能力分别是12h、16h、15h，又知每生产一件产品企业能获得2元利润，每生产一件产品企业能获得3元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大。,下面从另一个角度来讨论这个问题：,假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。,建立数学模型如下：,如何安排生产， 使获利最多？,出 租,出让代价应不低于 用同等数量的资源 自己生产的利润。,价格应该尽量低，这样，才

3、能有竞争力,出让代价应不低于 用同等数量的资源 自己生产的利润。,约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润,目标函数：所获租金总额尽量少,设y1，y2，y3分别为出租三种设备每小时的收费,该问题的数学模型为：,模型对比：,厂 家,一对对偶问题,租 借,每一个线性规划(LP)必然有与之相伴而生的另一个线性规划问题，即任何一个求 maxZ 的LP都有一个求 minZ 的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。,（1）对称型对偶问题：已知 P，写出 D。,二、线性规划的对偶理论,1、对偶问题的形式,“Max - ” “Min

4、- ”,特点：目标函数求极大值时，所有约束条件为号，变量非负；目标函数求极小值时，所有约束条件为号，变量非负。,例：写出线性规划问题的对偶问题,解：首先将原式变形,（2）非对称型对偶问题,对偶的基本定理：若一个问题的某约束为等式，那么对应的对偶问题的相应变量无非负限制；反之， 若一个问题的某变量无非负限制，那么对应的对偶问题的相应约束为等式。,P：,D：,例：,原问题为,（3）混合型对偶问题,P：,D：,式中Y为行向量Y=(y1,y2,ym),例,P：,D：,对偶变换的规则,例：线性规划问题如下：,练习：,1.,2.,练习 P78-2.1（a）（b）,min Z= - CX s.t. - AX

5、 - b X 0,（1）对称性：对偶问题的对偶是原问题。,max W = -Yb s.t. -ATY -C Y 0,2、对偶问题的性质,（2）弱对偶性：设 和 分别是问题（P）和（D）的可行解，则必有,推论1：若 和 分别是问题（P）和（D）的可行解，则 是（D）的目标函数最小值的一个下界； 是（P）的目标函数最大值的一个上界。,例,试估计它们目标函数的界，并验证弱对偶性原理。,P：,解：,D：,推论2：在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。,关于无界性有如下结论：,推论3：在一对对偶问题（P）和（D）中，若一

6、个可行（如P），而另一个不可行，（如D），则该可行的问题无界。,试用对偶理论证明原问题无界。,解： =（0,0,0）是 P 的一个可行解，而 D 的第一个约束条件不能成立（因为y1 , y2 0)。因此，对偶问题不可行，由推论可知，原问题无界。,（3）最优性：若 X* 和 Y* 分别是 （P ）和 （D） 的可行解且CX* = Y* b，则X*,Y*分别是问题 （P）和（D） 的最优解。,例如，上例找到 X*=（0，0，4，4）， Y*=（1.2，0.2），则Z=28，W=28。故X* ，Y*分别是 P和D 的最优解。,（4）强对偶性：若一对对偶问题（ P） 和（ D ）都有可行解，则它们都有

7、最优解，且目标函数的最优值必相等。,推论4：若 （P ）和 （D） 的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。,（5）互补松弛性：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零，也即,将互补松弛性应用于其对偶问题地可以这样叙述：,约束条件,变量,或,0,非0,其对偶问题的最优解、最优值分别为： Y*=(4/5,3/5) Z*=5,将y1*,y2*的值代入约束条件，得(2)(3)(4)为严格不等式；由互补松弛性得x2*=x3*=x4*=0,因y1*,y2*0得，原问题两个约束

8、条件取严格等式。故有,求解得x1*=1,x5*=1;故原问题的最优解为 X(1,0,0,0,1)T;W*=5,解：设原问题的最优解为X(x1*, x2*, x3*, x4*, x5*)T,y1* y2*,=4/5 =3/5,33,例：已知,试通过求对偶问题的最优解来求解原问题的最优解。,解：对偶问题为,用图解法求出： Y*=（1 , 3）， W=11。 将y*1=1， y*2=3 代入对偶约束条件，（1）（2）（5）式为严格等式，（3）（4）为严格不等式。 令原问题的最优解为X* = （x1,x2,x3,x4,x5），则根据互补松弛条件，必有x3 = x4 =0,(1 , 3),（1）,（2）

9、,（3）,（4）,（5）,又由于y*10， y*2 0，原问题的约束必为等式，即,化简为,此方程组为无穷多解,令x5 =0,得到x1=1，x2=2。即X*1 =（1,2,0,0,0）为原问题的一个最优解，Z=11。 再令 x5 =2/3，得到x1=5/3，x2=0。 即X*2 =（5/3,0,0,0,2/3）也是原问题的一个最优解，Z=11。,例：已知原问题的最优解为 X* =（0，0，4），Z=12 试求对偶问题的最优解。,解：,（1）,（2）,（3）,将X* =（0，0 ，4）代入原问题中，有下式：,所以，根据互补松弛条件，必有y*1= y*2=0，代入对偶问题 （3）式， y3 =3。因

10、此，对偶问题的最优解为 Y*=（0 ，0，3），W=12。,（6）线性规划的原问题(P)与其对偶问题（D）之间存在一对互补的基解；其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题 变量；这些互相对应的变量如果在一个问题解中是基变量，则在另一个问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有Z=W。,分别用单纯形法求解上述规划问题，得到最终单纯形表如下表：,原问题最优表,对偶问题最优表,表23,原问题与对偶问题解的对应关系小结,练习 P88-3.4,三、对偶问题的经济解释影子价格,例：,由强对偶定理可知，如果原问题有最优解，那么对偶问题也有最优解，而

11、且它们的目标函数值相等，即有： 其中是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。 则是单位资源微小变化所引起的目标函数的最优值变化的比值，即梯度。,为对偶问题最优解，它代表在资源最优利用条件下对各种单位资源的估价，这种估计不是资源的市场价格，而是根据资源在生产中所作出的贡献（如创造利润，产值等）而作出估价，为区别起见，称之为影子价格(shadow price)。,1.影子价格的定义,（1）影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。 如果第i种资源供大于求，即在达到最优解时，该种资源没有用完，或松弛变量 ，由互补松弛定理，在对偶最优解 中，第i种资源的影子价格

12、。 如果第i种资源的影子价格，那么由互补松弛定理，原问题的第i个约束为严格等式，即，这表明第i种资源已经用完，成为稀缺资源。,2.影子价格的经济意义,48,（2）影子价格是不稳定的，它随企业的生产任务、产品结构、技术状况的变化而变化。 资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。,（3）影子价格是一种边际价格。 在上式中， 。 说明 的值相当于在资源得到最优利用的生产条件下， 每增加一个单位时目标函数 的增量。其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi 就是第 i 个约束条件的影子价格。,y*1=0

13、, y*2=0.25, y*3=0.75,x*17/2， x*2=3/2,几何解释：,y*1=0, y*2=0.25, y*3=0.75,x*17/2， x*2=3/2,（4）资源的影子价格实际上又是一种机会成本。 在纯市场经济条件下，当第2种资源的市场价格低于1/4时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。,（5）一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。,经济学研究如

14、何管理 自己的稀缺资源,四、对偶单纯形法,1.什么是对偶单纯形法？,对偶单纯形法是应用对偶原理求解原始线性规划的一种方法在原始问题的单纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！,（1）对“单纯形法”求解过程认识的提升从更高的层次理解单纯形法 初始可行基（对应一个初始基本可行解） 迭代另一个可行基（对应另一个基本可行解），直至所有检验数0为止。,2.对偶单纯形法的基本思想,所有检验数0意味着,说明原始问题的最优基也是对偶问题的可行基。换言之，当原始问题的基B既是原始可行基又是对偶可行基时，B成为最优基。 定理2-5 B是线性规划的最优基的充要条件是，B是可行基，同时也是对偶可行基

15、。,LP原问题:,若B是A中的一个基,证明：,单纯形法的求解过程就是： 在保持原始可行的前提下(b列保持0)， 通过逐步迭代实现对偶可行(检验数行0)。,（2） 对偶单纯形法思想： 换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持0） ，通过逐步迭代实现原始可行（b列0，从非可行解变成可行解）。,对偶单纯形法的思想,原问题,初始基本可行解,保持为基本可行解,初始对偶可行解,保持对偶可行性,最优解,基本可行性,对偶可行性,始终满足解的可行性,始终满足对偶可行性,3.对偶单纯形法的实施 （1）使用条件： 检验数全部0； 解答列至少一个元素 0； （2）实施对偶单纯形法的基本原则： 在保

16、持对偶可行的前提下进行基变换每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。,（3）计算步骤 建立初始单纯形表，计算检验数行。,基变换： 先确定换出变量解答列中的负元素（一般选最小的负元素）对应的基变量出基； 即,相应的行为主元行。,然后确定换入变量原则是：在保持对偶可行的前提下，减少原始问题的不可行性。 如果,(最小比值原则),则选 为换入变量 , 相应的列为主元列 , 主元行和主元列交叉处的元素 为主元素。,若 ,要计算最小比值吗？为什么？,按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量

17、，得到新的单纯形表。 循环以上步骤，直至求出最优解。,例用对偶单纯形法求解P：,化为标准型 ,将两个等式约束两边分别乘以-1，得,以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：,0 0 -3/5 -8/5 -1/5,0,cj-zj,0 1 -1/5 -2/5 1/5 1 0 7/5 -1/5 -2/5,2/5 11/5,x2 x1,-3 -2,-2 -3 -4 0 0 x1 x2 x3 x4 x5,cj xj b,XB,CB,最优解: X*=（11/5，2/5, 0, 0, 0）T， 最优值: minW= -maxZ* = -11/5(-2)+2/5(-3)= 28/5,例用对偶

18、单纯形法求解P：,化为 标准型 ,将三个等式约束两边分别乘以-1，然后 列表求解如下：,最优解是Y*=（5/3，1/3，0，0，1）T， 目标函数最优值为Wmin=-Zmax=8,五、 灵敏度分析,1.什么是灵敏度分析,第一类：当系数A、b、C发后改变时，目前最优基是否还是最优。 第二类：为保持目前最优基还是最优，系数A、b、C的允许变化范围是什么。,A：代表企业的技术状况 b：代表企业的资源状况 C：代表企业产品的市场状况,2、灵敏度分析的类型,目标函数中价值系数C的变化（基变量价值系数变化；非基变量价值系数变化） 右端资源常数b变化 增加一个变量 增加一个约束 技术系数A发生变化,XB,X

19、N,CB,CN,CB-CBB-1B,B-1B,B-1N,CN-CBB-1N,CB,XB,CBT,XB,Cj,Xj,b,j(cj-zj),B-1b,XB,xm+1,CB,cm+1,CB-CBB-1B,B-1B,B-1Pm+1,Cm+1-CBB-1Pm+1,CB,XB,CBT,XB,Cj,Xj,b,j(cj-zj),B-1b,xn,cn,B-1Pn,Cn-CBB-1Pn,3、价值系数C发生改变,(1)当CN中某个Cj发生变化时，只影响xj的检验数，且jcj-CBB-1Pj，若cj的变化满足j(cj-zj)0，则目前解还是最优；否则就不是最优，继续单纯形迭代就可以求得新的最优解。,例：对于下例问题，

20、讨论c3范围,(2)当CB中某个Ci发生变化时，则会影响所有非基变量的检验数，且NcN-CBB-1N，若ci的变化满足N0，则目前解还是最优；否则就不是最优，继续单纯形迭代就可以求得新的最优解。,例：对于下题中，讨论C1在什么范围内变化，问题的最优解不变,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,0,0,c1-3,CB,XB,b,j(cj-zj),c1,c1,-1,-5/3,-1/3,3c1-3,4,5,0,0,0,c13,C13/4,c13,当3/4c13时，最优解不变。,4、右端资源常数b发生

21、改变,当b中某个分量bi发生改变时，将影响所在基变量的取值XB=B-1b。若bi的变化仍满足B-1b0，则目前基还是最优基。最优解为X=(B-1b,0)；否则，若bi的变化使B-1b中某些分量小于0，则目前基成了不可行基。但仍是对偶可行基，因此可以用对偶单纯形法迭代求得新的最优解。,例：在例1中，讨论b1改变的情况（b1在什么范围内变化时，当前最优基不变）,解：设b变为(b1,9)T,若B1b0则,解得9/4b19,5、增加一个变量,若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润Cn+1，消耗量Pn+1=(a1n+1,a2n+1,amn+1)T时，可以在最优表中补充一列，其中前

22、m行可以由B1Pn+1得到，而检验数行可以由n+1=cn+1-CBB-1Pn+1计算得到。若n+10，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则当n+10时，则应以xn+1进基，作单纯形迭代，从而找出新的最优解。,例：在例1中，讨论增加产品D时的情况，假设产品D的单位利润为5（千元），工时消耗和材料消耗为（2,3）T,解：,6=c6-CBB-1P6=5-(2,3) =2/30,5,x6,5/3,1/3,2/3,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,0,0,-1,-5/3,-1/

23、3,CB,XB,b,j(cj-zj),0,x5,5/3,1/3,2/3,3/5,0,-3/5,4/5,-1/5,-1/5,1,11/5,-3/5,2/5,3/5,9/5,x6,x2,5,3,1,0,-2/5,0,-3/5,-11/5,-1/5,0, ,6、增加一个约束,把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束条件对最优解不构成影响，即不影响最优生产计划的实施。若当前最优解不满足新增加的约束，则应把新的约束添加到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。,例：在例1的问题中增加约束2x1+2x2+x35，讨论最优解的情况,2,3,3,0,

24、0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,0,0,-1,-5/3,-1/3,CB,XB,b,j(cj-zj),解：将当前最优解X=(1,2,0)T代入约束条件中，得 21+22+065,在新增加的约束条件中引入松弛变量得2x1+2x2+x3+x6=5 加入最优表得,2,2,1,0,0,1,0,x6,0,0,5,x6,0,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,CB,XB,b,j(cj-zj),0,x6,0,0,2,2,1,0,0,1,5,x