运筹学-对偶问题.ppt

《运筹学-对偶问题.ppt》由会员分享，可在线阅读，更多相关《运筹学-对偶问题.ppt（54页珍藏版）》请在三一办公上搜索。

1、第二章线性规划的对偶问题及灵敏度分析,基本要求：了解对偶问题的特点；熟悉互为对偶的问题之间的关系；掌握对偶规划的理论和性质；掌握对偶单纯形法；熟悉灵敏度分析的概念和内容。,假定某个公司想把该工厂的资源收买过来，它至少应付出多大代价，才能使该工厂愿意放弃生产活动，出让自己的资源。,第一节线性规划的对偶问题,一、对偶问题的提出,例1.某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，,表1-1,x1,x2,解：设产品的产量为x1吨，产品的产量为x2吨。建模如下：,问应如何安排计划使

2、该工厂获利最多？,y1,y2,y3,第一节线性规划的对偶问题,原问题：,对偶问题：,Y*=(1.5，0.125，)W*=14,X*=(4，2)Z*=14,第一节线性规划的对偶问题,二、对称形式下对偶问题的一般形式：,定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，当目标函数求极小时均取“”号。,第一节线性规划的对偶问题,y1y2ym,原问题,对偶问题,表2-1,第一节线性规划的对偶问题,三、非对称形式的原对偶问题关系,例：写出下述线性规划问题的对偶问题,第一节线性规划的对偶问题,写出下列线性规划问题的对偶问题,解：该问题的对偶问题

3、是：,第一节线性规划的对偶问题,写出下列线性规划问题的对偶问题,第一节线性规划的对偶问题,写出下列线性规划问题的对偶问题,第二节对偶问题的基本性质,1.弱对偶性：如果(j=1,2,n)是原问题的可行解，(i=1,2,m)是对偶问题的可行解，则恒有,推论1：极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界推论2：极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。推论3：若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。,第二节对偶问题的基本性质,原问题：,对偶问题：,思考：当原问题（对偶问题）无可行解时，其对偶问题（原

4、问题）解的情况。,或具有无界解或无可行解,第二节对偶问题的基本性质,第二节对偶问题的基本性质,3.强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,4.互补松弛性：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,设X（x1*,x2*,xm*）TY（y1*,y2*,ym*）T分别为原问题和对偶问题的最优解。,约束条件,变量,或,0,非0,第二节对偶问题的基本性质,例：已知线性规划问题如下，试用对偶理论证明上述线性规划问题无最优解。,证：首先看到该问题

5、存在可行解，例如X=(0,0,0)。其对偶问题为：,由第一约束条件可知对偶问题无可行解，因而此问题目标函数无界，即无最优解。,第二节对偶问题的基本性质,例：已知下述线性规划问题的对偶问题的最优解为Y*（4/5,3/5,）Z*=5。试用对偶理论找出原问题的最优解,其对偶问题的最优解、最优值分别为：Y*=(4/5,3/5)Z*=5,将y1*,y2*的值代入约束条件，得(2)(3)(4)为严格不等式；由互补松弛性得x2*=x3*=x4*=0,因y1*,y2*0得，原问题两个约束条件取严格等式。故有,求解得x1*=1,x5*=1;故原问题的最优解为X(1,0,0,0,1)T;W*=5,原问题,对偶问题

6、,第三节影子价格,影子价格：yi*是资源bi的价值一种度量，即对第i种资源的的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”,影子价格是不稳定的，它随企业的产品结构、技术状况的变化而变化。影子价格是一种边际成本。yi的值相当于在给定的生产条件下，bi每增加一个单位时目标函数Z的增量。资源的影子价格实际上又是一种机会成本。若生产过程中某种资源未得到充分利用,则该种资源的影子价格为零；又当某种资源的影子价格不为零时，表明该种资源在生产过程中已耗费完毕。,XB,XN,CB,CN,B-1N,CN-CBB-1N,CB,XB,CBT,XB,Cj,Xj,b,j(cj-zj),

7、B-1b,0,E,B-1B,CB-CBB-1B,XB,xm+1,CB,cm+1,0,E,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,第四节对偶单纯形法,第四节对偶单纯形法,0,-1/41/2-7/2,010,100,-5/415/2-15/2,1/4-3/2-3/2,y2y3,-24-5,1/41/2,y1 y2 y3 y4 y5,-15-24-5 0 0,XB,CB,b,第四节对偶单纯形法,可行基：当基B对应的基本解是可行解时，称基B为可行基。最优基：当基B对应的基本可行解是

8、最优解时，称基B为最优基。对偶可行基：若CBB-1是对偶问题的可行解时，则称B为对偶可行基。,对偶单纯形法思路：先找到一个对偶可行基，然后保持基的对偶可行性，逐步迭代直至最终达到基的可行性。,XB,CB,b,x4,x5,0,0,3,0,2,3,0,-3/4,7/4,1,0,3/4,1/4,0,1,-1/4,1/4,-9/4,0,5/4,0,-3/4,3/4,9/4,x4,x2,0,3,-1,2,4/3,-1/3,1,0,0,1,-1/3,1/3,-1,-5/3,0,0,-1/3,1,2,x1,x2,2,3,3,9/4,1,9,Cj-zj,Cj-zj,Cj-zj,B1（P4，P5）,B2（P4，

9、P2）,B3（P1，P2）,是可行基，不是对偶可行基,是可行基，不是对偶可行基,是可行基，也是对偶可行基,是最优基,-1,-1,1,0,-1,-4,0,1,-2,-3,x3,x4,0,0,-3,-9,0,0,-3,-9,0,0,x1,x2,x3,x4,3,9/4,-3/4,0,1,-1/4,1/4,1,0,-1/4,-5/4,3/4,x3,x2,0,-9,-3/4,0,0,-9/4,1,9,1,0,-4/3,1/3,0,1,1/3,-1/3,5/3,1/3,x1,x2,-3,-9,0,0,-1,-2,CB,XB,b,cj-zj,cj-zj,cj-zj,第四节灵敏度分析,一、什么是灵敏度分析,第

10、一类：当系数A、b、C发后改变时，目前最优基是否还是最优。第二类：为保持目前最优基还是最优，系数A、b、C的允许变化范围是什么。,A：代表企业的技术状况b：代表企业的资源状况C：代表企业产品的市场状况,第四节灵敏度分析,二、灵敏度分析的类型：,目标函数中价值系数C的变化（基变量价值系数变化；非基变量价值系数变化）右端资源常数b变化增加一个变量增加一个约束技术系数A发生变化,第四节灵敏度分析,XB,XN,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,

11、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,第四节灵敏度分析,1、价值系数C发生改变,a.当CN中某个Cj发生变化时，只影响xj的检验数，且jcj-CBB-1Pj，若cj的变化满足j(cj-zj)0，则目前解还是最优；否则就不是最优，继续单纯形迭代就可以求得新的最优解。,例：对于下例问题，讨论c3范围,第四节灵敏度分析,1、价值系数C发生改变,b.当CB中某个Ci发生变化时，则会影响所有非基变量的检验数，且NcN-CBB-1N，若ci的变化满足N0，则目前解还是最优；

12、否则就不是最优，继续单纯形迭代就可以求得新的最优解。,例：对于下题中，讨论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时，最优解不变。,第四节灵敏度分析,2、右端资源常数b发生改变,当b中某个分量bi发生改变时，将影响所在基变量的取值XB=B-1b。若bi的变化仍满足B-1b0，则目前基还是最优基。

13、最优解为X=(B-1b,0)；否则，若bi的变化使B-1b中某些分量小于0，则目前基成了不可行基。但仍是对偶可行基，因此可以用对偶单纯形法迭代求得新的最优解。,例：在例1中，讨论b1改变的情况（b1在什么范围内变化时，当前最优基不变）,解：设b变为(b1,9)T,若B1b0则,解得9/4b19,第四节灵敏度分析,3、增加一个变量,若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润Cn+1，消耗量Pn+1=(a1n+1,a2n+1,amn+1)T时，可以在最优表中补充一列，其中前m行可以由B1Pn+1得到，而检验数行可以由n+1=cn+1-CBB-1Pn+1计算得到。若n+10，则原

14、最优解仍为最优，原生产计划不变，不生产这种新产品；否则当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/3,CB,XB,b,j(cj-zj),0,x5,5/3,1/3,2/3,3/5,0,-3/5,4/5,-1/

15、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,第四节灵敏度分析,4、增加一个约束,把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束条件对最优解不构成影响，即不影响最优生产计划的实施。若当前最优解不满足新增加的约束，则应把新的约束添加到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。,例：在例1的问题中增加约束2x1+2x2+x35，讨论最优解的情况,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3

16、,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,x6,0,0,2,3,-8/3,2/3,1,3,0,0,-1,-2,0,1

17、,-1,0,0,-1,-5/3,-1/3,0,2,3,0,x1,x2,x4,1/3,13/6,1/2,1,0,-5/3,0,-1/3,0,1,13/6,0,1/3,2/3,-1/6,0,0,1,0,1/2,-1/2,0,0,-1/6,0,-1/3,-5/6,1,5/6,第四节灵敏度分析,5、A中的元素发生变化,N中Pj改变的情形：与增加一个变量时完全相同，只需要认为新增加一个产品，其利润与xj的利润相同为cj，而其消耗系数Pn+1等于变化后的Pj，则可以直接用处理增加一个变量的方法进行处理。,例：对例1中的线性规划，若a23由7改变为5，试讨论其最优解的情况。,-1,2,4/3,-1/3,1,

18、0,0,1,-1/3,1/3,-1,-5/3,0,0,-1/3,1,2,x1,x2,2,3,Cj-zj,XB,CB,b,x4,x5,0,0,3,0,2,3,0,3,9/4,Cj-zj,初始单纯形表,最终单纯形表,解：虚拟一种产品D，其单位利润为c6=3，资源消耗为P6(1，5)T，则,6C6-CBB-1P6-1/30,由此可知，最优解不变。,试讨论a23在什么范围变化时最优解不变？,CB,XB,b,初始单纯形表,最终单纯形表,问题一：若原计划生产产品I的工艺结构有了改进，这时有关它的技术系数向量变为P1(2,5,2)T，每件利润为4元。试分析对原计划有什么影响？,问题二：若原计划生产产品I的工

19、艺结构有了改进，这时有关它的技术系数向量变为P1(4,5,2)T，每件利润为4元。试问该厂应如何安排最优生产方案？,解：把改进工艺的产品I看作产品I，设x1为其产量，计算在最终表中x1对应的列向量B-1P1和检验数1。,100,5/41/23/8,0,x1,x1,3/8,5/4-7/211/8,-21/8,Cj-zj,Cj-zj,1、已知线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表如下所示，请将表中空白处数字填上。,习题,CB,XB,b,cj-zj,cj-zj,习题,2、已知线性规划问题：,(a)写出它的对偶问题；(b)应用对偶理论证明原问题和对偶问题都存在最优解。,习题,3、

20、已知线性规划问题：,应用对偶理论证明该问题最优解的目标函数值不大于25,习题,4、已知线性规划问题：,其最优解为x1=-5，x2=0，x3=-1(a)求k的值；(b)写出并求其对偶问题的最优解。,习题,6、已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：,0,-2,-1,-3,0,01,x5,11,x4,11,x3,13,x2,10,610,x1x5,x1,cj-zj,试说明分别发生下列变化时，新的最优解是什么？(a)目标函数变为maxZ=2x1+3x2+x3(b)约束条件右端项由(6,4)T变为(3,4)T(c)增添一个新的约束x1+2x32,复 习,1、判断下列说法是否正确,

21、(1)任何线性规划问题存在并具有唯一的对偶问题；(2)对偶问题的对偶问题一定是原问题；(3)根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(4)若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；(5)已知yi*为线性规划的对偶问题的最优解，若yi*0，说明在最优生产计划中第i种资源已完全耗尽；,复 习,1、判断下列说法是否正确,(6)若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数将增大5k；(7)应用对偶单纯形法计算时，若单纯形表中某一基变量xi0，又xi所在行的元素

22、全部大于或等于零，则可以判断其对偶问题具有无界解；(8)若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；,复 习,1、判断下列说法是否正确,(9)在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化；(10)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。(11)已知yi*为线性规划的对偶问题的最优解，若yi*=0，说明在最优生产计划中第i种资源一定有剩余；,2、已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：,0,-2,-1,-3,0,01,x5,11,x4,11,x3,13,x2,10,610,x1x5,x1,cj-zj,试说明分别发生下列变化时，新的最优解是什么？(a)目标函数变为maxZ=2x1+3x2+x3(b)约束条件右端项由(6,4)T变为(3,4)T(c)增添一个新的约束x1+2x32,复 习,