《运筹学教学资料》运筹学第2章.ppt

Chapter2 对偶理论(Duality Theory),单纯形法的矩阵描述对偶问题的提出线性规划的对偶理论对偶问题的经济解释影子价格对偶单纯形法灵敏度分析(选讲)掌握WinQSB软件求解对偶规划,本章主要内容：,学习要点：1.理解对偶理论，掌握描述一个线性规划问题 的对偶问题。2.能够运用对偶单纯形法来求解线性规划问题。3.会用互补松弛条件来考虑一对对偶问题的界。4.了解影子价格、灵敏度分析以及用WinQSB求 解对偶规划问题。,2.1 单纯形法矩阵描述,每一列的含义？每个表中的B和B-1的查找？,B从初表中找，B-1从当前表中找，相当于初表中的I的位置,单纯形法的矩阵描述,单纯形法的主要步骤,因此，单纯形表的主体内容是B-1(b,A),单纯形表的主要结构,单纯形法的矩阵描述,单纯形法的矩阵描述,单纯形法的矩阵描述,单纯形法的矩阵描述,2.2 改进单纯形法,思考：P1分别与P1、P1的关系,改进的单纯形法,改进的单纯形法,改进的单纯形法,设mm系数矩阵A，求其逆矩阵,可以先从第1列开始:,以下介绍一种比较简便的计算方法,求解线性规划问题的关键是计算B-1,改进的单纯形法,以a11为主元素,进行变换,然后构造含有（1）列，而其他列都是单位列的矩阵,改进的单纯形法,可得到：,而后以第2列的a22(1)为主元素，进行变换,改进的单纯形法,然后构造含有（2）列，而其他列都是单位列的矩阵,可得到,改进的单纯形法,重复以上的步骤，直到获得,求单纯形表的基矩阵的逆矩阵也可以用这方法。,改进的单纯形法,书上例题自学。,2.3 对偶问题的提出,对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？,对偶问题的提出,俩家具制造商间的对话：,唉!我想租您的木工和油漆工一用。咋样？价格嘛好说，肯定不会让您兄弟吃亏。,王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。,Hi：王老板，听说近来家具生意好呀，也帮帮兄弟我哦!,家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。,价格嘛好商量，好商量。只是.,王 老 板,李 老 板,引例1,对偶问题的提出,王老板的家具生产模型：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最少）。,按时下最流行的一个词，叫什么来着,对偶问题的提出,设三种资源的使用单价分别为 y1,y2,y3,y1 y2 y3,生产单位产品A的资源消耗所得不少于单位产品A的获利,生产单位产品B的资源消耗所得不少于单位产品B的获利,y1+3 y2 40,2y1+2 y2+2y3 50,引例2,通过使用所有资源对外加工所获得的收益,W=30y1+60 y2+24y3,对偶问题的提出,根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：,Min W=30y1+60 y2+24y3,y1+3y2 402y1+2 y2+2y3 50y1,y2,y3 0,s.t,目标函数,约束条件,原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3为对偶变量，也称为影子价格,对偶问题的提出,2.4 线性规划的对偶理论,Max Z=40 x1+50 x2,x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0,s.t,原问题（对偶问题）,对偶问题（原问题）,一、原问题与对偶问题的对应关系,3个约束2个变量,2个约束 3个变量,线性规划的对偶理论,对偶问题的形式,定义 设原线性规划问题为 则称下列线性规划问题,为其对偶问题，其中yi(i=1,2,m)称为对偶变量,上述对偶问题称为对称型对偶问题,原问题简记为(P)，对偶问题简记为(D),称问题(P)和(D)为一对对偶问题,线性规划的对偶理论,对称型问题的对偶规则,1、给每个原始约束条件定义一个非负对偶变量yi(i=1,2,m)；2、使原问题的目标函数系数 cj 变为其对偶问题约束条 件的右端常数；3、使原问题约束条件的右端常数 bi 变为其对偶问题目 标函数的系数；4、将原问题约束条件的系数矩阵转置，得到其对偶问 题约束条件的系数矩阵；5、改变约束问题不等号的方向，即将“”改为“”；6、原问题为“max”型，对偶问题为“min”型。,线性规划的对偶理论,原始问题Max Z=CXs.t.AXbX 0,b,A,C,Max,n,m,对偶问题Min W=Ybs.t.YACY 0,Min,C,AT,b,n,m,线性规划的对偶理论,当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。,线性规划的对偶理论,求线性规划问题的对偶规划,解：由原问题的结构可知为对称型对偶问题,例1,线性规划的对偶理论,求线性规划问题的对偶规划,解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。,例2,线性规划的对偶理论,求线性规划问题的对偶规划,解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。,例3,线性规划的对偶理论,上式已为对称型对偶问题，故可写出它的对偶规划,令,则上式化为,线性规划的对偶理论,对偶问题的非对称形式,min z=2x1+4x2-x3s.t.3x1-x2+2x3 6-x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2-y1+2y2+y3+3y4 4 2y1-3y2+2y3-y4-1 y1 0,y2,y3 0,y4 0,=,unr,=,x10,x20,x3:unr,线性规划的对偶理论,1 原问题为“max”，对偶问题为“min”；2 原问题中目标函数系数 ci 变为其对偶问题约束条件的右端常数；3 原问题约束条件的右端常数 bi 变为其对偶问题目标函数的系数；4 原问题约束条件的系数矩阵转置，即为其对偶问题的系数矩阵；5 原问题的变量个数n等于其对偶问题的约束条件个数n，原问题 约束条件的个数m等于其对偶问题变量的个数m；6 在求极大值的原问题中，“”，“”和“=”的约束条件分别对应其对偶变量“0”，“0”和“无符号限制”；7 在求极大值的原问题中，变量“0”，“0”和“无符号限制”分别对应其对偶约束条件的“”，“”和“=”约束.,混合型问题的对偶规则：,线性规划的对偶理论,线性规划的对偶理论,Max Z=40 x1+50 x2,x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0,s.t,y1y2y3,Min W=30y1+60y2+24y3,y1+3y2+0y3 402y1+2y2+2y3 50 y1,y2,y3 0,s.t,Max W=-30y1-60y2-24y3,y1+3y2+0y3 y4=402y1+2y2+2y3 y5=50 y1,y2,y3,y4,y5 0,s.t,例4,二、对偶问题的解,线性规划的对偶理论,Max W=-30y1-60y2-24y3+0(y4+y5)-M(y6+y7),y1+3y2+0y3 y4+y6=402y1+2y2+2y3 y5+y7=50 y1,y2,y3,y4,y5 0,s.t,线性规划的对偶理论,线性规划的对偶理论,线性规划的对偶理论,线性规划的对偶理论,原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。,线性规划的对偶理论,原问题最优表,对偶问题最优表,线性规划的对偶理论,性质1 对称性定理：对偶问题的对偶是原问题,三、对偶原理,线性规划的对偶理论,对偶的定义,简要证明：,线性规划的对偶理论,性质2 弱对偶原理(弱对偶性)：设 和 分别是问题(P)和(D)的可行解，则必有,推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。,证明：,(1)当X和Y为原问题和对偶问题的一个可行解,有,原问题目标函数值,对偶问题目标函数值,线性规划的对偶理论,推论2:在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。,线性规划的对偶理论,推论3：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题目标函数值无界。,已知原问题(LP)，,试估计它的目标函数值的界,并验证弱对偶定理.,例5,线性规划的对偶理论,解：,问题(LP)的对偶问题(DP)为,(DP),线性规划的对偶理论,由观察可知,分别是原问题和对偶问题的可行解。,，弱对偶定理成立。,且由推论1知，对偶问题目标函数W的下界为10，原问题目标函数Z的上界为40。,且原问题的目标函数值为,对偶问题的目标函数值为,故,线性规划的对偶理论,例：利用对偶性质判断下面问题有无最优解,例6,解：此问题的对偶问题为,不能成立，因此对偶问题不可行。故由推论3知原问题无界。,线性规划的对偶理论,性质3 最优性定理：如果 是原问题的可行解，是其对偶问题的可行解，并且:,则 是原问题的最优解，是其对偶问题的最优解。,线性规划的对偶理论,性质4 强(主)对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,还可推出另一结论：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等；若一个问题无最优解，则另一问题也无最优解。,一对对偶问题的关系，有且仅有下列三种：都有最优解，且目标函数最优值相等；两个都无可行解；一个问题无界，则另一问题无可行解。,线性规划的对偶理论,证明：当X*为原问题的一个最优解，B为相应的最优基，通过引入松弛变量Xs，将问题(P)转化为标准型,说明Y*可行,线性规划的对偶理论,问题:（1）由性质4可知，对偶问题最优解的表达式 Y*=?,（2）求 Y*是否有必要重新求解(D)?,不必。可以从原问题（P）的单纯形终表获得。,线性规划的对偶理论,性质5 互补松弛性：设X0和Y0分别是P问题 和 D问题 的可行解，则它们分别是最优解的充要条件是：,其中：Xs、Ys为松弛变量。,在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应的变量一定为零。,紧约束与松约束,线性规划的对偶理论,一个约束称为紧约束，如果该约束在所有最优解上的值使左右取等号。即我们把严格等式约束称为紧约束（或起作用约束）.,不是紧约束的约束称为松约束。即把某一最优解处取严格不等式的约束称为松约束（或不起作用约束）。,对于最优解X*和Y*而言，松约束的对偶约束是紧约束.,以上关系称为对偶问题的互补松弛关系或松紧关系。在计算上，若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解.,紧约束与松约束,松紧关系,非常重要,线性规划的对偶理论,证:(必要性）,线性规划的对偶理论,x1 xj xn xn+1 xn+i xn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0,线性规划的对偶理论,性质5的应用：该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y求X或已知X求Y,互补松弛条件,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：若Y0，则Xs必为0；若X0，则Ys必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。,线性规划的对偶理论,已知线性规划,的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。,解：写出原问题的对偶问题，即,标准化,例7,线性规划的对偶理论,设对偶问题最优解为Y(y1，y2),由互补松弛性定理可知，X和 Y满足：,即：,因为x10，x20，所以对偶问题的第一、二个约束的松弛变量等于零，即y30，y40，带入方程中：,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：Y=(1,1)，最优值w=26。,线性规划的对偶理论,已知线性规划,的对偶问题的最优解为Y=(0,-2)，求原问题的最优解。,解:对偶问题是,例8,线性规划的对偶理论,设原问题最优解为X(x1，x2，x3)T,由互补松弛性定理知，X和 Y满足：,将Y带入由方程可知，y3y50，y41。,y2=-20 x50又y4=10 x20,将x2，x5分别带入原问题约束方程中，得：,解方程组得：x1=-5,x3=-1,所以原问题的最优解为,X=(-5,0,-1)，最优值z=-12,线性规划的对偶理论,试用对偶原理求解线性规划问题,已知其对偶规划的最优解为,练习,线性规划的对偶理论,解：,该问题的对偶规划为,线性规划的对偶理论,利用松紧关系，,代入对偶规划的约束条件得下列约束是松约束，,将最优解,松约束,紧约束,其对偶约束是紧约束,线性规划的对偶理论,设原问题的最优解为,紧约束,线性规划的对偶理论,对偶规划可以用线性规划的单纯形法求解。由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。,对偶问题解的求法,线性规划的对偶理论,原问题与对偶问题解的对应关系小结,线性规划的对偶理论,思考题,判断下列结论是否正确，如果不正确，应该怎样改正？,1）任何线性规划都存在一个对应的对偶线性规划.2）原问题第i个约束是“”约束，则对偶变量yi0.3）互为对偶问题，或者同时都有最优解，或者同时都无最优解.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能无界解.9）原问题与对偶问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.,线性规划的对偶理论,2.5 影子价格,单位产品消耗的资源(吨/件),原始问题是利润最大化的生产计划问题,总利润(元),产品产量(件),单位产品的利润(元/件),消耗的资源(吨),剩余的资源(吨),资源限量(吨),影子价格,对偶问题资源定价问题,对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 Max z=Min w,总利润(元),资源限量(吨),资源价格(元/吨),影子价格,在一对 P 和 D 中，若 P 的某个约束条件的右端项常数 bi（第 i 种资源的拥有量）增加一个单位时，所引起目标函数最优值z*的改变量称为第 i 种资源的影子价格，其值等于D问题中对偶变量 yi*。,由对偶问题得基本性质可得：,1.影子价格的数学分析：,影子价格,2.影子价格的经济意义1）影子价格是一种边际价格在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量yi 就是第 i 种资源的影子价格。即：,影子价格,资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,影子价格,0,X2,X1,X=(15,7.5)Z=975,X=(15.5,7.25)Z=982.5,X=(14.5,8.25)Z=992.5,0,X2,X1,X=(15,7.5)Z=975,0,X2,X1,X=(15,7.5)Z=975,X=(14.5,8.25)Z=992.5,0,X2,X1,X=(15,7.5)Z=975,X=(15.5,7.25)Z=982.5,0,X2,X1,X=(15,7.5)Z=975,0,X2,X1,X=(15,7.5)Z=975,X=(15.5,7.25)Z=982.5,X=(14.5,8.25)Z=992.5,2）影子价格是一种机会成本影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。,若第i 种资源的单位市场价格为mi，则有当yi*mi 时，企业愿意购进这种资源，单位纯利为yi*mi，则有利可图；当yi*mi 时，企业有偿转让这种资源，可获单位纯利miyi*，否则，企业无利可图，甚至亏损。,结论：若yi*mi 则购进资源 i，可获单位纯利yi*mi；若yi*mi则转让资源 i，可获单位纯利miyi。,影子价格,y1y2ym,产品的机会成本,机会成本表示减少一件产品所节省的资源可以增加的利润,影子价格,机会成本,利润,差额成本,产品的差额成本（Reduced Cost）,差额成本=机会成本-利润,影子价格,3）影子价格在资源利用中的应用 根据对偶理论的互补松弛性定理:Y*Xs=0,YsX*=0表明生产过程中如果某种资源 bi 未得到充分利用时，该种资源的影子价格为0；若当资源资源的影子价格不为0时，表明该种资源在生产中已耗费完。,影子价格,yixn+i=0,如果yi 0，则xn+i=0,如果xn+i 0，则yi=0,影子价格大于0的资源，在最优生产计划条件下没有剩余,ym+jxj=0,如果ym+j 0，则xj=0,如果xj 0，则ym+j=0,最优生产计划条件下有剩余的资源，其影子价格等于0,差额成本大于0（机会成本大于利润）的产品，不安排生产,安排生产的产品，差额成本等于0（机会成本等于利润）,互补松弛关系经济解释,影子价格,4）影子价格对单纯形表计算的解释,单纯形表中的检验数,其中cj表示第j种产品的价格;表示生产该种产品所消耗的各项资源的影子价格的总和，即产品的隐含成本。,当产值大于隐含成本时，即，表明生产该项产品有利，可在计划中安排；否则，用这些资源生产别的产品更有利，不在生产中安排该产品。,影子价格,2.6 对偶单纯形法,对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。,对偶单纯形法原理,对偶单纯形法基本思路：,找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（XB为非负），若否，通过变换基解，直到找到原问题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解，由定理4可得最优解。,对偶单纯形法,找出一个DP的可行基,LP是否可行（XB 0）,保持DP为可行解情况下转移到LP的另一个基本解,最优解,是,否,循环,结束,对偶单纯形法,先回顾一下单纯形算法：它是从线性规划的一个基可行解迭代到另一个基可行解的过程，在迭代过程中，保持基解的可行性，逐步消除基解的检验数的非负性，即,为了求解线性规划，我们也可以从线性规划的一个基解迭代到另一个基解，在迭代过程中，保持基解的检验数的非正性，逐步消除基解的不可行性，即,对偶单纯形法,如果原问题(P)的一个基本解X与对偶问题(D)的基可 行解Y对应的检验数向量满足条件 则称X为原问题(P)的一个正则解。,求解原问题(P)时，可以从(P)的一个正则解开始，迭代到另一个正则解，使目标函数值增加，当迭代到正则解满足原始可行性条件(即xi0)时，就找到了原问题(P)的最优解。这一方法称为对偶单纯形法,对偶单纯形法,定义,对偶单纯形法,原问题解空间,对偶问题解空间,可行解,可行解,基本解,基本解,正则解,正则解,基可行解,基可行解,最优解,对偶单纯形法,对偶单纯法的迭代步骤：,（1）找一个正则基B和初始正则解X(0)，将问题（P）化为关于基B的典式，列初始对偶单纯形表.,设正则解,的典式为：,对偶单纯形法,将上面的典式转换成前面所学习过的单纯形表：,对偶单纯形法,对偶单纯形法,对偶单纯形法,用对偶单纯形法计算,例9,对偶单纯形法,由于初始正则解有负分量，于是取min-3,-4=-4x5为换出变量，取,x1为换入变量，得新基x4,x1，51=-2为主元,对偶单纯形法,基变换的过程：,主元变为1，即用-2去除单纯形表中基变量x5所在的行；主元所在列的其它元变为0，消去非基变量x1所在的列的其余元-1，-2；得新基x4,x1的单纯形表,对偶单纯形法,基变换的过程：,对偶单纯形法,可见正则解的有负分量，由于x4=1,所以取x4为换出变量，取,x2为换入变量，得新基x2,x1，42=-5/2为主元,对偶单纯形法,此时正则解是可行解，也是最优解。X*=(11/5，2/5，0，0，0)；z*=-28/5,进行基变换，得新正则解的单纯形表：,对偶单纯形法,例10,例11,例12,对偶单纯形法的迭代步骤中,如何找一个初始正则解？,初始正则解的确定,标准形线性规划问题,选定的基B，不妨设,对偶单纯形法,可行基B的典式为,右端常数中有负数，而检验数全非正，则基B为正则基，相应的 解为初始正则解，就可用对偶单纯形法求解。,否则，若出现正检验数，X(0)就不是正则解。,为此，求初始正则基和初始正则解，可增加一个约束条件：,原问题(P)的典式扩充为下列问题:,扩充问题：,对偶单纯形法,扩充问题的一个正则基和正则解是不难得到的。,对偶单纯形法,扩充问题的两种可能结果：,（1）若扩充问题无可行解，则原问题(P)也无可行解。,则把 x0 作为换出变量，xk 作为换入变量，经过一次迭代，就可得到一个正则解：,具体计算可以在单纯形表上实现.,证明:,则 一定是扩充问题的可行解，与假设矛盾。,令,对偶单纯形法,（1）若扩充问题无可行解，则原问题(P)也无可行解。事实上，若原问题如果有可行解：,由于,所以,则 是扩充问题的可行解，又因扩充问题与原问题的目标函数相同，且都与 无关,所以必有,这与 是扩充问题的最优解矛盾。,对偶单纯形法,（2）若扩充问题有最优解,且目标函数最优值与 M 无关,则有,必为原问题(P)的最优解。事实上，如果原问题有可行解,对偶单纯形法的理论解释,对偶单纯形法所使用的表格与原单纯形法一样，可将典式中的数据放在原单纯形表上，即得到对偶单纯形表，所不同的是这里保证在整个过程中,不保证,即右端常数中可以出现负数。,对偶单纯形法,先定换出变量，再定换入变量。,设正则基 的典式为：,对偶单纯形法,对偶单纯形表,对偶单纯形法的迭代方式与原单纯形法基本一致.所不同的是：先定换出变量，再定换入变量，决定主元并作基变换得到一个新的正则解X(1),从而完成一次迭代.算法的后半部分与原单纯形法完全一致.,对偶单纯形法,(2)再选进基变量:假定xk为进基变量,我们分析一下xk 应满足什么条件,才能使迭代后得到的解仍为问题(P)的正则解.,(1)先选出基变量:若 则取与 相对应的基变量 xr 为出基变量.,因为,而换基运算的第一步是用主元 去除第r 行中的各元素,为了使变换后 为正数,所以主元 必须从第r 行的负元素中选取,即.,设主元处在第 k 列,于是换基运算后,各检验数变为,因为要求迭代后得到的解仍为正则解,于是,又因为,于是当 时,不等式(1)自然成立;,由此,则取与之相对应的非基变量 为换入变量。,否则,当 时,要使不等式(1)成立,必须,又因为,于是当 时,不等式(1)自然成立;,对偶单纯形法,最后证明对应于新的正则解X(1),对偶问题(D)的目标函数值将得到改善.,这样,上述求极大值问题(P)的迭代过程,实质上是在对对偶问题(D)求极小值,所以目标函数越小就越接近最优解.直到得到对偶问题(D)的最小值,相应地也就求出了原问题(P)的最大值.,出基变量 与进基变量 xk 确定以后,以 为主元进行换基运算(方法与原单纯形法相同)即可得新的正则解X(1).,这是因为,故,和原始单纯形法一样,若对偶问题是非退化的(即对偶问题的每一个基可行解都是非退化的,或者说,对于原问题的每一个正则解，都有,则每迭代一次,目标函数都将严格减小,从而一定能在有限次迭代后得到原问题的最优解,或者判定它无解.,容易证明:若,且所有的,则原问题(P)无解(自己证明).,用对偶单纯形法求解线性规划问题时，当约束条件为“”时，不必引进人工变量，使计算简化。当线性规划问题中变量多于约束条件时，用对偶单纯形法计算可以减少工作量。对偶单纯形法应用于主要应用于灵敏度分析及整数规划等有关章节中。对偶单纯形法的局限性主要是：对大多数线性规划问题，很难找到一个初始正则解。因此对偶单纯形法一般不单独使用。,对偶单纯形法的优缺点：,对偶单纯形法,2.7 灵敏度分析,灵敏度分析=对于市场的变化，我们的决策究竟怎样变化（不需要将它当成一个新问题）,灵敏度分析的重要性在于：1.向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围；2.环境条件变化时可能对经营状况带来何种影响；3.产生影响后的解决途径。,灵敏度分析,灵敏度分析的类型：1.模型中各个参数在什么范围变化时，最优基不发生改变。2.模型中参数变化已经超出上述范围时，如何快速确定新的最优基和最优解新的最优决策方案。模型中参数变化主要指：1.目标函数的系数变化；2.约束条件右边的值变化；3.约束条件中aij 的变化；4.可决策变量增减的变化；5.约束条件增减的变化。,灵敏度分析,灵敏度分析的任务：1.当系数A、b、C中的某个发生变化时,目前的最优基是否仍最优（即目前的最优生产方案是否要变化）?(称为模型参数的灵敏度分析)2.增加一个变量或增加一个约束条件时，目前的最优基是否仍最优（即目前的最优生产方案是否要变化）？(称为模型结构的灵敏度分析),灵敏度分析,线性规划问题 I 表与 B 表的关系对给定符合典式的线性规划问题中，初始基矩阵为 I，基变量为 XS，即松弛变量。其对应的初始单纯形表如下：I 表（初始表）对初始单纯形表进行迭代之后得到 B 为最优基矩阵，最终典式所对应的单纯形表：B 表（最终表）,灵敏度分析,线性规划原问题单纯形法对应的 I 表中参数的变化将引起B 表中对应参数的变化情况如下：,灵敏度分析,I 表（初始表）,B 表（最终表）,灵敏度分析的方法：灵敏度分析方法的关键是从单纯形法对应的 I 表中参数的变化来分析B 表中对应参数的变化情况来回答决策者所关心问题。,灵敏度分析的方法是在目前最优基B下进行的。即当参数A、b、c中的某一个或几个发生变化时，考察是否影响以下两式的成立？,灵敏度分析,1.对于参数b的灵敏度分析,I 表,B 表,当I 表中b变化为b时，在B 表中将只有解列 B-1b发生变化。,灵敏度分析,b变化的时候，仅对B-1b有影响,仅关心B-1b0?,若新的B-1b不满足0，最优基发生变化，此时需用对偶单纯形法进行计算，调整可行性可能,当B-1b0时，最优基不变（即生产产品的品种不变，但数量及最优值会变化），此时可以简单求出新最优解。,所以，b的变化只影响最优解的变化和最优值的变化。,灵敏度分析,若B-1b0，其是一个不等式组，从中可以解得b的变化范围（此时，需保证当前最优基变化后仍为最优基）,若B-1b中有小于0的分量，则需用对偶单纯形法迭代，以求出新的最优方案。（此时，基变量不变，因为基变量只需要相应的B可逆就可以了）,灵敏度分析,灵敏度分析,若b2增加到30，最优解如何变化？,最优基不变，最优解变为（5，0，15，0，0）。,灵敏度分析,灵敏度分析,若b2增加到32，最优解如何变化？,最优基发生变化，用对偶单纯形法求解。,灵敏度分析,灵敏度分析,已知某生产计划问题的数学模型，为使最优方案不变，试讨论第二个约束条件b2的变化范围。,解：生产计划问题的数学模型和最优单纯形表为：,灵敏度分析,从矩阵形式的单纯形表中可知，b2的变化只影响解的可行性B-1b0，因此，为使最优解不变，只需变化以后的B-1b0即可。,由,解得：,当数据量十分大的时候，十分麻烦,写为B-1(24,26)+B-1b,灵敏度分析,若b2变化超过范围，则需用对偶单纯形法进行求解。如b2=6，则,将上述数字替换最优单纯形表中相应位置的数据得：,灵敏度分析,用对偶单纯形法迭代，求出的最优单纯形表如下：,得到新的最优解为：x1=0，x2=3;max z=9,灵敏度分析,当 Cj 是非基变量 X 的目标系数时，若要保持最优解（或基）不变，则必须满足：CN CB B-1N 0,I 表,B 表,2.对价值系数Cj变化的分析(1),当 Cj 变化使得非基变量的Cj Zj 0，即最优解（或基）发生变化，则在原单纯形表的基础上，继续求解模型。,灵敏度分析,max z=2x1+x2 5x2 15s.t.6x1+2x2 24 x1+x2 5 x1，x2 0,灵敏度分析,若要使最优解保持不变，求x1的价值系数变化范围。,灵敏度分析,因此：当CN（非基变量的目标函数系数）中某个Cj发生变化时，只影响到非基变量xj的检验数,最优解改变，需要用单纯形法重新进行迭代，以求得新的最优解。,灵敏度分析,对于下列线性规划模型,为使最优解不变，讨论非基变量y1的目标函数系数c3的变化范围。,用单纯形法求得其最优表为：,灵敏度分析,解：因为y1为非基变量，其目标函数系数c3的变化只会影响到y1的检验数，因此为使最优解不变，只需,即,继续迭代以求出新的最优解。,灵敏度分析,当 Cj 变化使得非基变量的Cj Zj 0，即最优解（或基）发生变化，则在原单纯形表的基础上，继续求解模型。,当 Ci 是基变量 Xi 的目标系数时，若要保持最优解（或基）不变，则必须满足：CN CB B 1N 0-CB B-1 0,I 表,B 表,2.对价值系数Cj变化的分析(2),灵敏度分析,在上题中，设基变量x1的系数C1变化为C1+C1，在最优性不变的条件下，试确定C1的范围,解：,因此：当CB（基变量的目标函数系数）中某个Cj发生变化时，会影响到所有变量的检验数，解不等式组,灵敏度分析,将上述数字替换单纯形表中相应位置的数字得：,灵敏度分析,用单纯形法迭代得最优解表如下：,灵敏度分析,第一种情况（当jJN）：即aij为非基变量xj的技术系数时，它的变化只影响xj的系数列B-1Pj和检验数j，为使最优方案不变，只需j 0。,3.对技术系数aij变化的分析,第二种情况（当jJB）：由于B中元素的改变影响到B-1的变化，因此也影响到整个单纯形表T(B)的变化。目前的基B对应的解有可能既不是原始可行，也不是对偶可行。于是不如重新求解。,灵敏度分析,对于下列规划问题的最优解，若由于工艺改进，y1的技术系数改为p3=(1,1)T，试讨论最优解的变化。,解：,最优解改变。此时其系数列改为：,灵敏度分析,将上述数据替换最优表中相应位置的数据，然后再用单纯形法求得新的最优解。,灵敏度分析,设某企业在计划期内，拟议生产新产品Xn+1，并已知新产品的单位利润为Cn+1，消耗系数向量为Pn+1=(a1,n+1,a2,n+1,am,n+1)T，此时应如何分析才能确定该新产品是否值得投产？增加新产品应在不影响企业目前计划期内最优生产的前提下进行。因此可从现行的最优基B出发考虑：若n+1=CBB-1Pn+1Cn+10，则不应投入。即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。,4.对增加新产品的分析,灵敏度分析,现有一新产品丙，经预测其单位利润为3，技术消耗系数为P5=（2，2）T，问该产品是否值得投产？,解：,值得投产。,其系数列为：,灵敏度分析,将此变量加入最优单纯形表中得：,用单纯形法迭代求得最优解为：,灵敏度分析,在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，对生产过程提出了新约束等。对增加新约束条件的分析方法步骤是：,第一步：将目前的最优解代入新增加的约束，若能满足约束条件，则说明新增约束对目前的最优解（即最优生产方案）不构成影响（称此约束为不起作用约束），可暂时不考虑新增约束条件。否则转下一步；第二步：把新增约束添加到原问题最终表中，并作初等行变换，构成对偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。,5.对增加新约束条件的分析,灵敏度分析,