第三章对偶理论优秀课件.ppt

第三章对偶理论第三章对偶理论第1页，本讲稿共75页学习目标理解对偶问题的基本理论；掌握对偶问题的经济解释影子价格；理解对偶单纯性法；掌握灵敏度分析第三章对偶问题与灵敏度分析第2页，本讲稿共75页对偶问题？.对偶理论是线性规划中最重要的理论之一，是深入了解线性规对偶理论是线性规划中最重要的理论之一，是深入了解线性规对偶理论是线性规划中最重要的理论之一，是深入了解线性规对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有划问题结构的重要理论基础。同时，由于问题提出本身所具有划问题结构的重要理论基础。同时，由于问题提出本身所具有划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和的经济意义，使得它成为对线性规划问题系统进行经济分析和的经济意义，使得它成为对线性规划问题系统进行经济分析和的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？么会产生这样一种问题呢？么会产生这样一种问题呢？么会产生这样一种问题呢？引引 言言第3页，本讲稿共75页 从两个不同的角度讨论线性规划问题从两个不同的角度讨论线性规划问题从两个不同的角度讨论线性规划问题从两个不同的角度讨论线性规划问题原始的角度原始的角度对偶的角度对偶的角度例例对偶问题的提出第4页，本讲稿共75页唉唉!我想租您的木工和油漆工一我想租您的木工和油漆工一用。咋样？价格嘛用。咋样？价格嘛好说，好说，肯定不会让您兄弟吃亏讪。肯定不会让您兄弟吃亏讪。王老板做家具赚了王老板做家具赚了 大钱，虽然我也想做家具大钱，虽然我也想做家具生意，却苦于没有生意，却苦于没有足够的木工和油漆工足够的木工和油漆工 咋办？只有租咯。咋办？只有租咯。Hi：王老板，听说：王老板，听说近来家具生意好惨了，近来家具生意好惨了，也帮帮兄弟我哦也帮帮兄弟我哦!家具生意还真赚钱，但家具生意还真赚钱，但 是现在的手机生意这么好，是现在的手机生意这么好，不如干脆把我的木工和油漆不如干脆把我的木工和油漆工租给他，又能工租给他，又能收租金又可做生意。收租金又可做生意。价格嘛价格嘛好商量，好商量，好商量。只是好商量。只是.王王 老老 板板李李 老老 板板引例引例两家具制造商间的对话：两家具制造商间的对话：第5页，本讲稿共75页王老板的王老板的家具生产模型家具生产模型：x1、x2是桌、椅生产量。是桌、椅生产量。Z是家具销售总收入（总利润）。是家具销售总收入（总利润）。max Z=50 x1+30 x2s.t.4x1+3x2 120（木工）木工）2x1+x2 50（油漆工）（油漆工）x1，x2 0原始线性规划问题，记为（原始线性规划问题，记为（P）王老板的王老板的资源出租模型资源出租模型：y1、y2单位木、漆工出租价格。单位木、漆工出租价格。W是资源出租租金总收入。是资源出租租金总收入。min W=120y1+50y2s.t.4y1+2y2 50 3y1+y2 30 y1，y2 0对偶线性规划问题，记为（对偶线性规划问题，记为（D）对偶问题对偶问题王老板按（王老板按（D）的解）的解 y1、y2出租其拥有的木、漆工资源，既保证了自出租其拥有的木、漆工资源，既保证了自己不吃亏己不吃亏(出租资源的租金收入并不低于自己生产时的销售收入出租资源的租金收入并不低于自己生产时的销售收入)，又使，又使得出租价格对李老板有极大的吸引力得出租价格对李老板有极大的吸引力(李老板所付出的总租金李老板所付出的总租金W最少最少).第6页，本讲稿共75页对偶的定义对偶的定义原始原始问题问题max z=Cmax z=CT TX Xs.t.AXs.t.AX b b X 0 X 0对偶问题min W=bTYs.t.ATYC Y 0minCATbTbACTmaxnmnm第7页，本讲稿共75页项目项目项目项目原问题原问题原问题原问题对偶问题对偶问题对偶问题对偶问题A Ab bC C目标函数目标函数目标函数目标函数约束条件约束条件约束条件约束条件决策变量决策变量决策变量决策变量约束系数矩阵约束系数矩阵约束系数矩阵约束系数矩阵约束条件的右端项向量约束条件的右端项向量约束条件的右端项向量约束条件的右端项向量目标函数中的价格系数向量目标函数中的价格系数向量目标函数中的价格系数向量目标函数中的价格系数向量max Z=Cmax Z=CT TX XAX AX b bX X 0 0其约束系数矩阵的转置其约束系数矩阵的转置其约束系数矩阵的转置其约束系数矩阵的转置目标函数中的价格系数向量目标函数中的价格系数向量目标函数中的价格系数向量目标函数中的价格系数向量约束条件的右端项向量约束条件的右端项向量约束条件的右端项向量约束条件的右端项向量min W=bmin W=bT TY YA AT TY Y C CY Y 0 0对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式第8页，本讲稿共75页对称的原始问题和对偶问题对称的原始问题和对偶问题对称的原始问题和对偶问题对称的原始问题和对偶问题对偶问题为min w=2y1+3y2-y3s.t.y1+2y2+y36 2y1-3y2+2y39 y1,y2,y30根据定义，原始问题为max z=6x1+9x2s.t.x1+2x22 2x1-3x23 x1+2x2-1 x1,x20对偶问题是极小化问题对偶问题的约束全为对偶问题有3个变量，2个约束对偶问题的变量全部为非负原始问题是极大化问题原始问题的约束全为原始问题有2个变量，3个约束原始问题的变量全部为非负对偶问题变量的个数(3)等于原始问题约束条件的个数(3)对偶问题约束条件的个数(2)等于原始问题变量的个数(2)第9页，本讲稿共75页根据定义写出对偶问题的练习根据定义写出对偶问题的练习max z=2x1+x2-3x3s.t.x1-3x2+2x3-5x4 6 4x1+x2-5x3+2x4 9 -x1+2x2 +x4 12 x1,x2,x3,x4 0原始问题有4个变量，3个约束，对偶问题应该有3个变量，4个约束。根据定义，对偶问题为：y1y2y3min w=6y1+9y2+12y3s.t.y1+4y2-y3 2 -3y1+y2+2y3 1 2y1-5y2 -3 -5y1+2y2+y3 0 y1,y2,y3 0 x1x2x3x4第10页，本讲稿共75页max z=2x1+3x2-x3s.t.x1+2x2+x3=6 2x1-3x2+2x39 x1,x2,x30max z=2x1+3x2-x3s.t.x1+2x2+x36 x1+2x2+x36 2x1-3x2+2x39 x1,x2,x30max z=2x1+3x2-x3s.t.-x1-2x2-x3-6 x1+2x2+x3 6 2x1-3x2+2x39 x1,x2,x30min w=-6w1+6w2+9w3s.t.-w1+w2+2w3 2 -2w1+2w2-3w3 3 -w1+w2+2w3 -1 w1,w2,w30min w=6(w2-w1)+9w3s.t.(w2-w1)+2w3 2 2(w2-w1)-3w3 3 (w2-w1)+2w3 -1 w1,w2,w30min w=6y1+9y2s.t.y1+2y2 2 2y1-3y2 3 y1+2y2 -1 y1:Free y20y1=w2-w1,y1:Free,y2=w3如果原始问题中一个约束是等号约束，则对偶问题中相应的变量没有符号限制非对称形式的对偶原始问题有“=”约束第11页，本讲稿共75页非对称形式的对偶原始问题有“”约束max z=2x1+3x2-x3s.t.x1+2x2+x3 6 2x1-3x2+2x39 x1,x2,x30max z=2x1+3x2-x3s.t.-x1-2x2-x3-6 2x1-3x2+2x39 x1,x2,x30min w=-6y1+9y2s.t.-y1+2y22 -2y1 -3y23 -y1+2y2-1 y1,y20min w=6y1+9y2s.t.y1+2y22 2y1-3y23 y1+2y2-1 y10,y20y1=-y1,y10如果极大化原始问题中一个约束是“”约束，则对偶问题中相应的变量0第12页，本讲稿共75页非对称形式的对偶总结原始问题约束条件的性质，影响对偶问题变量的性质。原始问题变量的性质，影响对偶问题约束条件的性质。max z=Cmax z=CT TX Xs.t.AXs.t.AX b b X 0 X 0min w=bTYs.t.ATYC Y 0max z=Cmax z=CT TX Xs.t.AXs.t.AX=b b X 0 X 0min w=bTYs.t.ATYC Y:Freemax z=Cmax z=CT TX Xs.t.AXs.t.AX b b X 0 X 0min w=bTYs.t.ATYC Y 0第13页，本讲稿共75页非对称形式下对偶问题的一般形式项目项目项目项目原问题原问题原问题原问题（对偶问题）（对偶问题）（对偶问题）（对偶问题）对偶问题对偶问题对偶问题对偶问题（原问题）（原问题）（原问题）（原问题）目标函数类型目标函数类型目标函数类型目标函数类型maxmaxminmin目标函数系数与右边项目标函数系数与右边项目标函数系数与右边项目标函数系数与右边项的对应关系的对应关系的对应关系的对应关系目标函数各变量系数对应目标函数各变量系数对应目标函数各变量系数对应目标函数各变量系数对应约束条件右边项的系数约束条件右边项的系数约束条件右边项的系数约束条件右边项的系数右边项的系数对应目标右边项的系数对应目标右边项的系数对应目标右边项的系数对应目标函数系数函数系数函数系数函数系数变量个数与约束条件个变量个数与约束条件个变量个数与约束条件个变量个数与约束条件个数的对应关系数的对应关系数的对应关系数的对应关系变量个数变量个数变量个数变量个数 n n约束条件个数约束条件个数约束条件个数约束条件个数 m m约束条件个数约束条件个数约束条件个数约束条件个数 n n变量个数变量个数变量个数变量个数 m m原问题变量类型与对偶原问题变量类型与对偶原问题变量类型与对偶原问题变量类型与对偶问题约束条件类型的对问题约束条件类型的对问题约束条件类型的对问题约束条件类型的对应关系应关系应关系应关系 0 0变量类型变量类型变量类型变量类型 0 0 无限制无限制无限制无限制 约束条件类型约束条件类型约束条件类型约束条件类型 =原问题约束条件类型与原问题约束条件类型与原问题约束条件类型与原问题约束条件类型与对偶问题变量类型的对对偶问题变量类型的对对偶问题变量类型的对对偶问题变量类型的对应关系应关系应关系应关系 约束条件类型约束条件类型约束条件类型约束条件类型 =0 0 变量类型变量类型变量类型变量类型 0 0 无限制无限制无限制无限制第14页，本讲稿共75页max z=2x1+x2-3x3s.t.x1-3x2+2x3-5x46 4x1+x2-5x3+2x4 9 -x1+2x2 +x4 12 x1,x2 0,x3Free,x4 0写对偶问题的练习（1）第15页，本讲稿共75页min z=2x1+4x2-x3s.t.3x1-x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max y=6w1+12w2+8w3+15w4s.t.3w1-w2+2w3+w4 2 -w1+2w2+w3+3w4 4 2w1-3w2+2w3-w4 -1 w1 0,w2 ,w3 0,w4 0=Free=x10 x20 x3:Freep原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；p原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。p原始问题变量的性质影响对偶问题约束条件的性质。p原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习（2）第16页，本讲稿共75页对偶问题的性质总结1、对偶的对偶就是原始问题对偶的定义max z=Cmax z=CT TX Xs.t.AXs.t.AX b b X 0 X 0min w=bTYs.t.ATYCY 0对偶的定义max w=-bTYs.t.-ATY-CY 0min z=-Cmin z=-CT TX Xs.t.-AXs.t.-AX-b-b X 0 X 0第17页，本讲稿共75页2、两个问题的可行解对应的目标函数值互为上下界例：min z=2x1+3x2s.t.x1+3x23 2x1+x2 4 x1,x2 0max w=3y1+4y2s.t.y1+2y22 3y1+y2 3 y1,y2 00 1 2 34321A(3,0)B(1.8,0.4)C(0,4)D(2,2)可行解可行解z z最优解最优解A A6 6B B4.84.8是是C C1212D D10103210 1 2A(1,0)B(1.9,0.4)C(0,1)O(0,0)可行解可行解y y最优解最优解O O0 0A A3 3B B4.84.8是是C C4 4第18页，本讲稿共75页3、若原问题解无界，则其对偶问题无可行解。4、两个问题最优解的目标函数值必相等。5、两个问题都有可行解时则两个问题必都有最优解。6、两个问题最优解中，一个问题中某个变量取值非零，则该变量在对偶问题中对应的约束条件必为紧约束；反之，如果约束条件为松约束，则其对应的对偶变量一定取值为零。互补松弛性定理第19页，本讲稿共75页互补松弛关系的分量表示第20页，本讲稿共75页互补松弛关系的分量表示第21页，本讲稿共75页互补松弛关系的分量表示由于原始问题和对偶问题的所有变量和松弛变量都是非负的，因此以上两式中的每一项都等于0。即在原始问题和对偶问题的最优解中，原始问题的一个变量和对偶问题相应的松弛变量，对偶问题的一个变量和原始问题相应的松弛变量，组成互补松弛对，在每一对变量中，其中一个大于0，另一个一定等于0。互补松弛关系的分量形式第22页，本讲稿共75页 y1.yi.ym ym+1 .ym+j .yn+m x1 .xj .xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0互补松弛关系的分量表示第23页，本讲稿共75页利用互补松弛关系求解线性规划min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3-1 x1,x2,x3 0max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20原始问题对偶问题0 1 2 3 4 5 6 7 8654321y1y2w=-1 w=1w=3w=6最优解为(y1,y2)=(6,0)max w=6先用图解法求解对偶问题。第24页，本讲稿共75页min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3-1 x1,x2,x3 0max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20max w=y1-y2s.t.y1+y2+y3 =6 y1+2y2 +y4 =8 y2 +y5=3 y1,y2,y3,y4,y50(y1,y2)=(6,0)(y1,y2,y3,y4,y5)=(6,0,0,2,3)min z=6x1+8x2+3x3s.t.x1+x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1,x2,x3,x4,x50(x1,x2,x3|x4,x5)(y1,y2|y3,y4,y5)x2=x3=x4=0 x1=1,x5=2引进松弛变量 求对偶引进松弛变量图解法求解代入约束求出松弛变量互补松弛关系代入约束求解(x1,x2,x3,x4,x5)=(1,0,0,0,2)第25页，本讲稿共75页 我们已经明白原始线性规划与对偶线性规划之间形式我们已经明白原始线性规划与对偶线性规划之间形式我们已经明白原始线性规划与对偶线性规划之间形式我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们的解之间的关系，那么对偶问题的解除上的对偶以及他们的解之间的关系，那么对偶问题的解除上的对偶以及他们的解之间的关系，那么对偶问题的解除上的对偶以及他们的解之间的关系，那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含了前面引例中提到的租金这种经济含义外其深刻的经济含了前面引例中提到的租金这种经济含义外其深刻的经济含了前面引例中提到的租金这种经济含义外其深刻的经济含义是什么呢？义是什么呢？义是什么呢？义是什么呢？对偶问题解的经济解释影子价格第26页，本讲稿共75页原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第27页，本讲稿共75页对偶问题资源限量（吨）资源价格（元/吨）总租金（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min y第28页，本讲稿共75页资源的影子价格(Shadow Price)当我们的资源当我们的资源b bi i的数量发生微小变化时，目标的最优值也会变化的数量发生微小变化时，目标的最优值也会变化对偶问题解中变量 yio 的经济含义经济含义是在其他条件不变的情况下，在其他条件不变的情况下，单位第单位第i种种“资源资源”变化所引起的目标函数最优值的变化变化所引起的目标函数最优值的变化。所以，yi o描述了原始线性规划问题达到最优时最优时（各种“资源”都处于最优最优的配置时），第 i 种“资源”的某种“价值”，故称其为第 i 种“资源”的影子价格影子价格.第29页，本讲稿共75页影子价格的特点 影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源在当前的最优利用配置下的一种客观估价，又表明它是一种虚拟的价格（或价值的影象）而不是真实的价格。特点1、影子价格是对系统资源的一种内部最优估价，只有当系统达到最优状态时才可能赋予资源这种价值。特点2、系统资源的一种动态价格体系，影子价格的大小与系统的价值取向有关，并受系统状态变化的影响。系统环境的任何变化都可能会引起影子价格的变化。第30页，本讲稿共75页影子价格的特点 特点3、影子价格的大小客观地反映资源在系统内的稀缺程度。如果某种资源在系统内供大于求，尽管它有实实在在的市场价格，但它在系统内的影子价格却为零，而影子价格越高，资源在系统内越稀缺。特点4、影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因而，在经济管理中有十分重要的应用价值。企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略。特点5、对偶解准确的经济意义与线性规划模型的构造方法有关，模型构造方法的不同有时会导致对偶解的不同经济解释。第31页，本讲稿共75页y1y2ym产品的机会成本(Opportunity Cost)产品j的机会成本：表示减少一件产品所节省的所有资源可以增加的利润增加单位资源可以增加的利润减少一件产品的产量可以节省的资源第32页，本讲稿共75页机会成本利润差额成本产品的差额成本（Reduced Cost）ym+j=(ai1y1+ai2y2+.aimym)-cj产品的差额成本产品的机会成本产品的利润第33页，本讲稿共75页原始问题和对偶问题的经济解释总结资源占用（吨）资源剩余（吨）资源总量（吨）产品的机会成本（元/件）产品的差额成本（元/件）产品的利润（元/件）产品的产量（件）资源的影子价格（元/吨）第34页，本讲稿共75页互补松弛关系的经济解释yixn+i=0如果yi0，则xn+i=0如果xn+i0，则yi=0边际利润大于0的资源，在最优生产计划条件下没有剩余ym+jxj=0如果ym+j0，则xj=0如果xj0，则ym+j=0最优生产计划条件下有剩余的资源，其边际利润等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0（机会成本等于利润）第35页，本讲稿共75页和资源有关的量n资源限量（吨）n资源占用（吨）n资源剩余（吨）n资源的影子价格（元/吨）和产品有关的量n产品利润（元/件）n产品产量（件）n产品的机会成本（元/件）n产品的差额成本（元/件）互补松弛关系，其中一个大于0，另一个一定等于0互补松弛关系，其中一个大于0，另一个一定等于0第36页，本讲稿共75页对偶单纯形法 如果线性规划原问题标准化之后不能简单得出一个初始基可行解，但却能容易得到该问题的对偶问题的一个初始基可行解，此时我们就可以通过保持对偶基可行解的可行性的方法进行迭代，逐步消除原问题基本解的不可行性，最终，当对偶基可行解迭代到对偶最优解的同时原问题也得到了最优的基可行解。第37页，本讲稿共75页书例3-6化成标准形式第38页，本讲稿共75页9/2 10 -3 -第39页，本讲稿共75页 3 7/2 4 -4/3 2 -12第40页，本讲稿共75页已获得最优解：（x1,x2,x3,x4,x5,x6）=（4/3,1/3,0,0,0,0）min z=46/3第41页，本讲稿共75页对偶单纯形法与单纯形法的计算步骤比较单纯形法对偶单纯形法前提条件最优性检验换入、换出变量的确定原始基解的变化所有bi0所有sj0?所有bi0?所有sj0 先确定换入变量后确定换出变量先确定换出变量后确定换入变量可行最优非可行可行(最优)第42页，本讲稿共75页对偶单纯形法练习第43页，本讲稿共75页第44页，本讲稿共75页第45页，本讲稿共75页已获得最优解：（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）min z=35第46页，本讲稿共75页引例 一奶制品加工厂用牛奶生产A，B两种奶制品，1桶牛奶可以在甲车间用12小时加工成3公斤A，或者在乙车间用8小时加工成4公斤B。根据市场需求，生产的A,B全部能售出，且每公斤A获利24元，每公斤B获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大灵敏度分析第47页，本讲稿共75页解：设该厂每天给甲车间x1桶牛奶，给乙车间x2桶牛奶，可得线性规划模型最优解为x1=20，x2=30，最优值z=3360，即用20桶牛奶生产A,30桶牛奶生产B，可获最大利润3360元 第48页，本讲稿共75页并进一步讨论以下3个附加问题：1）若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3）由于市场需求变化，每公斤A的获利增加到30元，应否改变生产计划？第49页，本讲稿共75页 灵敏度分析的作用灵敏度分析的作用在于向决策者提供线性规划问题的最优解所在于向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围，环境条件变化时可能对经营状况带来能适应的环境条件变化的范围，环境条件变化时可能对经营状况带来何种影响，产生影响后的解决途径。何种影响，产生影响后的解决途径。灵敏度分析的类型灵敏度分析的类型n n模型中各个模型中各个参数在什么范围变化时，最优基不发生改变参数在什么范围变化时，最优基不发生改变n n模型中模型中参数变化已经超出上述范围时，如何快速确定新的最优参数变化已经超出上述范围时，如何快速确定新的最优 基和最优解基和最优解新的最优决策方案。新的最优决策方案。灵敏度分析的方法灵敏度分析的方法从单纯形表中参数的变化来分析对应参数的变化情况以回答决策从单纯形表中参数的变化来分析对应参数的变化情况以回答决策者所关心问题。者所关心问题。灵敏度分析第50页，本讲稿共75页Max z=CMax z=CT TX Xs.t.AXbs.t.AXb X 0 X 0生产计划中的一般形式：其中，C代表企业产品的市场状况，称为价值系数向量；A代表企业的技术状况，称为技术系数矩阵；b代表企业的资源状况，称之为资源向量列。第51页，本讲稿共75页一、资源数量b的灵敏度分析资源数量b中某个bi 发生变化，即bi=bi+bi时，假设规划问题的其它系数不变，这样就会影响基变量的值，进而最优解可能发生变化。由于单纯形法的最优性检验标准为B-1b 0，所以只要变化后的b 满足 B-1b 0，则目前的基还是最优基，目前最优解仍然为z=CBTB-1b；否则若B-1b 中某些分量小于0，则目前的基成不了可行基，最优解也会发生变化。此时需用对偶单纯形法重新求解。最优基B的逆矩阵B-1就是最优表中初始基对应的位置.第52页，本讲稿共75页引例 已知线性规划模型的标准型的最优单纯形表如下，其中z=-z,x3,x4,x5为松弛变量.第53页，本讲稿共75页问题：1）若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 10 00 0-48-48-2-20 0-3360-3360 x x5 50 00 00 06 6-3/4-3/41 14040 x x2 20 00 01 13 3-1/4-1/40 03030 x x1 10 01 10 0-2-21/41/40 02020第54页，本讲稿共75页解：由最优单纯形表可见，松弛变量的值分别为-48,-2,0，根据z=-z 和对偶理论得知，牛奶和劳动时间的影子价格分别为48和2，甲车间生产能力的影子价格为0，意味着增加牛奶和劳动时间可以增加利润，从而可以考虑投资购买牛奶和聘用临时工人。zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 10 00 0-48-48-2-20 0-3360-3360 x x5 50 00 00 06 6-3/4-3/41 14040 x x2 20 00 01 13 3-1/4-1/40 03030 x x1 10 01 10 0-2-21/41/40 02020第55页，本讲稿共75页(1)设只有b1 发生变化，由可得130/3 b160，意味着我们可以将牛奶从50桶增加到60桶，即每天最多购买10桶牛奶.由于牛奶的市场价35小于牛奶的影子价格48，故应该作这项投资，且每天最多投资购买10桶牛奶.第56页，本讲稿共75页(2)设只有b2 发生变化，由可得400 b21600/3，意味着我们的劳动时间可以从480小时增加到1600/3小时，即每天最多购买160/3小时劳动时间.由于劳动时间的影子价格为2，故付给临时工人的工资最多为每小时2元.第57页，本讲稿共75页进一步问：若该厂的正式工人中突然有15人请假，则原生产计划还是否可行？若不可行，求改变后的最优生产计划？(假设每名工人每天的劳动时间为8小时)解：15名正式工人请假意味着劳动时间将由480小时减少到360小时，由于360400，故不在最优基允许的范围内，即原生产计划不再可行，须重新求解最优的生产计划.第58页，本讲稿共75页即z=-3120，改写最优单纯形表，zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 10 00 0-48-48-2-20 0-3120-3120 x x5 50 00 00 06 6-3/4-3/41 1130130 x x2 20 00 01 13 3-1/4-1/40 06060 x x1 10 01 10 0-2-21/41/40 0-10-10根据对偶单纯形法-5 -第59页，本讲稿共75页可知，最优解x=(5,45,0,0,100)，z=-2880，最优解z=2880.zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 1-24-240 00 0-8-80 0-2880-2880 x x5 50 03 30 00 00 01 1100100 x x2 20 03/23/21 10 01/81/80 04545x x1 10 0-1/2-1/20 01 1-1/8-1/80 05 5第60页，本讲稿共75页二、价值系数C的灵敏度分析基变量的价值系数变化分析 当某个基变量的价值系数cj发生变化时，会影响目标函数中所有非基变量x的系数发生变化，且目标函数中非基变量xN的系数为CNT-CBTB-1N (N表示约束条件中非基变量xN的技术系数).若cj变化后，仍有新的CBTB-1N-CNT0，则原解还是最优；否则就不是最优，需继续迭代才能达到最优。关键是在最优表中查出矩阵B-1N(它是由最优表中非基变量相对应的列构成的矩阵).第61页，本讲稿共75页对于引例中的线性规划问题，最优表如下zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 10 00 0-48-48-2-20 0-3360-3360 x x5 50 00 00 06 6-3/4-3/41 14040 x x2 20 00 01 13 3-1/4-1/40 03030 x x1 10 01 10 0-2-21/41/40 02020问题：3）由于市场需求变化，每公斤A的获利增加到30元，应否改变生产计划？第62页，本讲稿共75页解：每公斤A获利由24增加到30元，意味着目标函数中基变量x1的系数由72变成90，将影响到所有非基变量的系数，要是最优解不变，则由CBTB-1N-CNT0 及最优表中的数据可得可得64 c1 96，目标函数中X1的新系数90在这个范围内，意味着最优基不变，即不需要改变生产计划.第63页，本讲稿共75页进一步问：若每公斤A的获利增加到35元，则原生产计划还是否可行？若不可行，求改变后的最优生产计划？解：当每公斤A的获利增加到35元，x1的系数由72增加到105，由于10596，故不在最优基允许的范围内，即原生产计划不再可行，须重新求解最优的生产计划.zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 110510564640 00 00 00 0 x x3 30 01 11 11 10 00 05050 x x4 40 012128 80 01 10 0480480 x x5 50 03 30 00 00 01 1100100第64页，本讲稿共75页zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 10 064640 00 0-35-35-3500-3500 x x3 30 00 01 11 10 0-1/3-1/3 50/350/3x x4 40 00 08 80 01 1-4-48080 x x1 10 01 10 00 00 01/31/3100/3100/3zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 10 00 00 0-8-8-3-3-4140-4140 x x3 30 00 00 01 1-1/8-1/81/61/620/320/3x x2 20 00 01 10 01/81/8-1/2-1/21010 x x1 10 01 10 00 00 01/31/3100/3100/3最优解x=(100/3,10,20/3,0,0)，z=-4140，最优解z=4140.第65页，本讲稿共75页非基变量的价值系数变化分析 当某个非基变量的价值系数cj 发生变化时，也就是目标函数中xj 的系数发生变化，且目标函数中xj 的系数为cj-CBTB-1Pj (Pj表示约束条件中xj 的技术系数).若变化后的cj CBTB-1Pj，则原解还是最优；否则就不是最优，可改变系数后重新求解最优值.第66页，本讲稿共75页三、技术系数A的灵敏度分析工艺结构改变的分析 由于设备的改进，人工技术娴熟程度的变化等原因导致的生产工艺结构发生改变使得系数矩阵会发生变化.通常工艺结构改变后，最优解会发生变化，需重新求解.通常用B-1Pj 替换最优表中xj 列的位置，用CBTB-1Pj -cj 来替换单纯形表中目标行里xj 的系数，对新的单纯形表求解即可得改变后的最优解.第67页，本讲稿共75页引例 由于奶制品工厂乙生产车间设备的改进，1桶牛奶可以在乙车间可用6小时加工成4公斤B，问改进后的最优生产计划？解：设备改进后，产品B的技术系数向量由P2T=(1,8,0)变为P2T=(1,6,0)，由c2=6，从而最优解发生变化，需重新计算生产计划.第68页，本讲稿共75页最优表换为zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 10 05454-48-48-2-20 0-3360-3360 x x5 50 00 03/23/26 6-3/4-3/41 14040 x x2 20 00 03/23/23 3-1/4-1/40 03030 x x1 10 01 1-1/2-1/2-2-21/41/40 0202080/320-zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 10 00 0-156-1567 70 0-4440-4440 x x5 50 00 00 03 3-1/2-1/21 11010 x x2 20 00 01 12 2-1/6-1/60 02020 x x1 10 01 10 0-1-11/61/60 03030-180第69页，本讲稿共75页zzx x1 1x x2 2x x3 3x x4 4x x5 5RHSRHSzz1 1-42-420 0-114-1140 00 0-5700-5700 x x5 50 03 30 00 00 01 1100100 x x2 20 01 11 11 10 00 05050 x x4 40 06 60 0-6-61 10 0180180最优解x=(0,50,0,180,100)，z=-5700，最优解z=5700.注意：若碰到原问题和对偶问题均为非可行解时，这就需要引进人工变量后重新求解.(参照人工变量法)第70页，本讲稿共75页增加新变量的分析 由于新产品的研发问题而增加决策变量，使得系数矩阵增加列而改变.引入新变量xj 后，若CBTB-1Pj -cj 0，则意味着新变量的引入可以使得目标函数值优化，从而可以引入新变量；否则没有必要引入新变量xj.第71页，本讲稿共75页引例 该奶制品工厂除了甲车间和乙车间两条生产线外，现安排引进一条新的生产线丙车间，1桶牛奶可以在丙车间用9小时快速加工成3公斤C，且丙车间的加工能力没有限制.设市场对C的需求没有限制，且每公斤C可获利20元，问该奶制品厂是否应该引进这条新的生产线以及引进后的最优生产计划？解：设将x3桶牛奶用于丙车间生产，其技术系数向量P3T=(1,9,0)，由c3=60，从而第72页，本讲稿共75页引进新的生产线丙车间生产产品C是有利的.为了求得新的生产计划，在原最优表的最后一列再增加一列x6，将P3和系数-3填在相应的位置得下表zzx x1 1x x2 2x x3 3x x4 4x x5 5x x6 6RHSRHSzz1 10 00 0-48-48-2-20 06 6-3360-3360 x x5 50 00 00 06 6-3/4-3/41 1-3/4-3/44040 x x2 20 00 01 13 3-1/4-1/40 03/43/43030 x x1 10 01 10 0-2-21/41/40 01/41/42020-4080第73页，本讲稿共75页zzx x1 1x x2 2x x3 3x x4 4x x5 5x x6 6RHSRHSzz1 10 0-8-8-72-720 00 00 0-3600-3600 x x5 50 00 01 19 9-1/2-1/21