对偶及对偶单纯形法.ppt

关于对偶及对偶单纯形法关于对偶及对偶单纯形法现在学习的是第1页，共40页Page 2本节主要内容本节主要内容线性规划的对偶模型线性规划的对偶模型对偶性质对偶性质对偶单纯形法对偶单纯形法 学习要点：学习要点：1.掌握线性规划的对偶形式掌握线性规划的对偶形式 2.掌握对偶单纯形法的解题思路及求解步骤掌握对偶单纯形法的解题思路及求解步骤现在学习的是第2页，共40页Page 3对偶现象普遍存在对偶现象普遍存在 “对偶对偶”，在不同的领域有着不同的诠释。在词语中，在不同的领域有着不同的诠释。在词语中，它是一种修辞方式，指两个字数相等、结构相似的语句，它是一种修辞方式，指两个字数相等、结构相似的语句，旨表达出相关或相反的意思。如：旨表达出相关或相反的意思。如：“下笔千言，离题万里下笔千言，离题万里”周长一定，面积最大的矩形是正方形；周长一定，面积最大的矩形是正方形；面积一定，周长最小的矩形是正方形。面积一定，周长最小的矩形是正方形。数学上也有如下对偶例子：数学上也有如下对偶例子：“横眉冷对千夫指，俯首甘为孺子牛横眉冷对千夫指，俯首甘为孺子牛”“天高任鸟飞，海阔凭鱼跃天高任鸟飞，海阔凭鱼跃”现在学习的是第3页，共40页Page 4一、线性规划的对偶模型一、线性规划的对偶模型设某工厂生产两种产品甲和乙，生产中需设某工厂生产两种产品甲和乙，生产中需4种设备按种设备按A，B，C，D顺序加工，生产每件产品所需的机时数、每件产品的利润值及每种设顺序加工，生产每件产品所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表备的可利用机时数列于下表：表表1.产品数据表产品数据表设备产品ABCD产品利润（千元件）甲 21402乙 22043设备可利用机时数（时）1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？润？1.对偶问题的现实来源对偶问题的现实来源对偶问题的现实来源对偶问题的现实来源现在学习的是第4页，共40页Page 5解：解：设甲、乙型产品各生产设甲、乙型产品各生产x1及及x2件，件，最优解为最优解为最优值为最优值为如何安排生产，如何安排生产，使获利最多使获利最多？则数学模型为：则数学模型为：现在学习的是第5页，共40页Page 6反过来问：反过来问：若厂长决定不生产甲和乙型产品，决定出租若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？时如何定价才是最佳决策？出让代价应不低于用同等数量的资源自己生产的利润。付出的代价最小，付出的代价最小，且对方能接受。且对方能接受。现在学习的是第6页，共40页Page 7在市场竞争的时代，厂长的最佳决策应符合两条：在市场竞争的时代，厂长的最佳决策应符合两条：（1）不吃亏原则。）不吃亏原则。即机时定价所赚利润不能低于加工甲、即机时定价所赚利润不能低于加工甲、乙型产品所获利润。乙型产品所获利润。（2）竞争性原则。）竞争性原则。即在上述不吃亏原则下，机时总收费即在上述不吃亏原则下，机时总收费尽可能低一些，以便争取更多用户，最终将设备出租出去。尽可能低一些，以便争取更多用户，最终将设备出租出去。现在学习的是第7页，共40页Page 8解：设解：设A、B、C、D设备的机时价分别为设备的机时价分别为y1、y2、y3、y4元，元，用单纯形法求得最优解为用单纯形法求得最优解为最优值为最优值为则新的线性规划数学模型为：则新的线性规划数学模型为：现在学习的是第8页，共40页Page 92.原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题原问题（对偶问题）（对偶问题）对偶问题对偶问题（原问题）（原问题）原始规划与对偶规划是同一组数原始规划与对偶规划是同一组数据参数据参数,只是位置有所不同只是位置有所不同,所描所描述的问题实际上是同一个问题从述的问题实际上是同一个问题从另一种角度去描述另一种角度去描述.现在学习的是第9页，共40页Page 10线性规划的对偶模型线性规划的对偶模型特点特点：目标函数求极大值时，所有约束条件为：目标函数求极大值时，所有约束条件为号，号，变量非负变量非负;目标函数求极小值时，所有约束条件为目标函数求极小值时，所有约束条件为号，变量号，变量非负非负.原始线性规划问题原始线性规划问题对偶线性规划问题对偶线性规划问题对称形式对称形式的线性规划的线性规划现在学习的是第10页，共40页Page 11线性规划的对偶模型线性规划的对偶模型例例2 写出线性规划问题的对偶问题写出线性规划问题的对偶问题解：由于若给出的线性规划不是对称形式，所以先将解：由于若给出的线性规划不是对称形式，所以先将它化成对称形式，然后再写出相应的对偶问题。它化成对称形式，然后再写出相应的对偶问题。现在学习的是第11页，共40页Page 12解：首先将原问题变形为解：首先将原问题变形为则对偶模型为：则对偶模型为：现在学习的是第12页，共40页Page 13线性规划的对偶变换规则线性规划的对偶变换规则(单向单向)原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数 max目标函数 min约束条件m个m个变量00=无约束变量n个n个约束条件00无约束=现在学习的是第13页，共40页Page 14对偶问题的形成对偶问题的形成min z=2x1+4x2-x3s.t.3x1-x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max 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:unrq原始问题变量的个数原始问题变量的个数(3)等于对偶问题约束条件的个数等于对偶问题约束条件的个数(3)；原始问题约束条件的个数原始问题约束条件的个数(4)等于对偶问题变量的个数等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用原始问题变量的性质影响对偶问题约束条件的性质，用 表示表示 原始问题约束条件的性质影响对偶问题变量的性质，用原始问题约束条件的性质影响对偶问题变量的性质，用 表示表示现在学习的是第14页，共40页Page 15例例4:4:写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题.解：原问题的对偶问题为解：原问题的对偶问题为现在学习的是第15页，共40页Page 16定理定理6.1(对合性对合性)对偶线性规划的对偶问题是原始线性规对偶线性规划的对偶问题是原始线性规划问题。划问题。对偶定义对偶定义对偶定义对偶定义二、对偶性质（选读）二、对偶性质（选读）现在学习的是第16页，共40页Page 17定理定理6.2 弱对偶原理弱对偶原理(弱对偶性弱对偶性)：设设 和和 分别是问分别是问题题(LP)和和(DP)的可行解，则必有的可行解，则必有推论推论1:原问题任一可行解的目标函数值是其对偶问题原问题任一可行解的目标函数值是其对偶问题目标函数值的上界；反之，对偶问题任意可行解的目目标函数值的上界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的下界。标函数值是其原问题目标函数值的下界。现在学习的是第17页，共40页Page 18推论推论2:在一对对偶问题（在一对对偶问题（LP）和（）和（DP）中，若其中一个）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；问题可行但目标函数无界，则另一个问题无可行解；这也这也是对偶问题的无界性。是对偶问题的无界性。推论推论3：在一对对偶问题（在一对对偶问题（LP）和（）和（DP）中，若一个）中，若一个有可行解，而另一个无可行解，则该可行的问题目标有可行解，而另一个无可行解，则该可行的问题目标函数值无界函数值无界。现在学习的是第18页，共40页Page 19定理定理6.3 最优性判定定理最优性判定定理：如果如果 是原问题的可行解，是原问题的可行解，则则 是原问题的最优解，是原问题的最优解，是其对偶问题的最优解。是其对偶问题的最优解。是其对偶问题的可行解，并且是其对偶问题的可行解，并且:定理定理6.4.在一对对偶问题（在一对对偶问题（LP）和（）和（DP）中，若任意）中，若任意一个有最优解，则另一个也有最优解，且对应的最优一个有最优解，则另一个也有最优解，且对应的最优值相等。值相等。现在学习的是第19页，共40页Page 20定理定理6.6 强对偶性强对偶性：若原问题及其对偶问题均具有可行解，则两者均：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。具有最优解，且它们最优解的目标函数值相等。推论推论4：（LP）与（）与（DP）要么两者都有最优解，要么都无最优解。）要么两者都有最优解，要么都无最优解。定理定理6.7 互补松弛性互补松弛性：设设X0和和Y0分别是分别是(LP)问题和问题和(DP)问题的可行问题的可行解，则它们分别是最优解的充要条件是：解，则它们分别是最优解的充要条件是：其中：其中：Xs为松弛变量、为松弛变量、Ys为剩余变量为剩余变量.互补松弛条件互补松弛条件现在学习的是第20页，共40页Page 21对偶性质的应用对偶性质的应用 借助以上性质可以证明，在用单纯形法求解原问题的迭代借助以上性质可以证明，在用单纯形法求解原问题的迭代过程中，单纯形表过程中，单纯形表右列中的元素右列中的元素对应于对应于原问题的基本可行解，原问题的基本可行解，底行中松弛变量对应的元素底行中松弛变量对应的元素恰好构成恰好构成对偶问题的基本解。对偶问题的基本解。逐次逐次迭代下去，当底行对应于对偶问题的解也变成基本可行解（底迭代下去，当底行对应于对偶问题的解也变成基本可行解（底行元素全非负）时，原问题和对偶问题同时达到最优解行元素全非负）时，原问题和对偶问题同时达到最优解.即此时即此时对偶问题的这个基本可行解就是它的最优解。对偶问题的这个基本可行解就是它的最优解。用单纯形方法求解原线性规划的过程中，每次迭代都保证得到用单纯形方法求解原线性规划的过程中，每次迭代都保证得到原问题的一个基本可行解，底行某些元素对应于对偶问题的基本原问题的一个基本可行解，底行某些元素对应于对偶问题的基本解解.单纯形法的迭代的过程既可以看作使原问题的基本可行解逐单纯形法的迭代的过程既可以看作使原问题的基本可行解逐步变为最优解（此时底行元素非负步变为最优解（此时底行元素非负)的过程，也可看作使对偶问题的基的过程，也可看作使对偶问题的基本解逐步变成基本可行解的过程。本解逐步变成基本可行解的过程。现在学习的是第21页，共40页Page 22根据性质根据性质1（对偶问题的对偶是它本身），在用单纯形法求（对偶问题的对偶是它本身），在用单纯形法求解解LP时也可这样考虑：从对偶问题的某个基本可行解开始，时也可这样考虑：从对偶问题的某个基本可行解开始，每次迭代总保证得到对偶问题的一个基本可行解（底行元素每次迭代总保证得到对偶问题的一个基本可行解（底行元素均非负），通过逐步迭代，当对偶问题达到最优解时，根据均非负），通过逐步迭代，当对偶问题达到最优解时，根据对偶理论，对偶问题的对偶即原问题也达到最优解。对偶理论，对偶问题的对偶即原问题也达到最优解。对偶单纯形法对偶单纯形法 适用情况：当原问题没有初始的基本可行解，但是对偶问题有初适用情况：当原问题没有初始的基本可行解，但是对偶问题有初始的基本可行解（初始表格容易满足始的基本可行解（初始表格容易满足）时时，用此方法。，用此方法。优点：当原问题没有初始的基本可行解，不需要借助大优点：当原问题没有初始的基本可行解，不需要借助大M M法或二阶段法构造新的模型法或二阶段法构造新的模型.对偶单纯形法的基本思想对偶单纯形法的基本思想现在学习的是第22页，共40页Page 23三、对偶单纯形法三、对偶单纯形法注意注意：它并不是求解对偶问题的单纯形法，而是一：它并不是求解对偶问题的单纯形法，而是一 个直接个直接求解原求解原LP问题的新算法。问题的新算法。对偶单纯形法是求解对偶单纯形法是求解LP问题的另一个基本方法。它是问题的另一个基本方法。它是根据对偶理论和单纯形法原理而设计出来的，因根据对偶理论和单纯形法原理而设计出来的，因此称为对偶单纯形法。此称为对偶单纯形法。现在学习的是第23页，共40页Page 24对偶单纯形法对偶单纯形法找出一个找出一个DP的基本可行解的基本可行解LP是否可行是否可行保持保持DP为基本可行解情况下转移到为基本可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环结束结束现在学习的是第24页，共40页Page 251.1.对偶单纯形法的迭代步骤对偶单纯形法的迭代步骤1）将原问题化为标准形）将原问题化为标准形,写出相应的表格写出相应的表格;2）利用容许的运算建立满足）利用容许的运算建立满足 三个特点的三个特点的单纯形表单纯形表;3）检查右列元素，若全非负，即表格满足）检查右列元素，若全非负，即表格满足 四个特点，结束运算；否则，进去第四个特点，结束运算；否则，进去第4）步；）步；4）确定离基变量确定离基变量.取右列中最小的负元素所在的行取右列中最小的负元素所在的行设是第设是第行行.现在学习的是第25页，共40页Page 265)5)确定进基变量确定进基变量所在列对应的变量所在列对应的变量取为进基变量取为进基变量;观察该行竖线左边的元素观察该行竖线左边的元素若所有若所有则无可行解，结束运算则无可行解，结束运算;否则，按如下规则从否则，按如下规则从负系数负系数中选择一个记为中选择一个记为现在学习的是第26页，共40页Page 276)6)进行旋转运算进行旋转运算利用容许的运算将利用容许的运算将变为变为1,1,该列其它元素变为该列其它元素变为0,0,从而实现将从而实现将变为基变量的目的变为基变量的目的.7）观察得到的新表）观察得到的新表(满足满足).若右列元素均非负若右列元素均非负,则已得最优解则已得最优解,结束运算结束运算;否则否则,返回第返回第4)步步.现在学习的是第27页，共40页Page 28例例 5.（教材（教材P79 例例5.4）用对偶单纯形法求解：）用对偶单纯形法求解：引入松引入松弛变量弛变量得到标得到标准型线准型线性规划性规划解：解：现在学习的是第28页，共40页Page 29构造对偶单纯形表构造对偶单纯形表选取离基变量选取离基变量选取进基变量选取进基变量-1-2-310 -5-2-2-101-6345000满足满足,但但不满足不满足现在学习的是第29页，共40页Page 300-1-5/21-1/2 -2111/20-1/23017/203/2-9015/2-11/2 210-21-1100111-11满足满足,但但不满足不满足满满足足 现在学习的是第30页，共40页Page 31满满足足 是具有标准形式的是具有标准形式的LP的最优解的最优解.略去松弛变量得原略去松弛变量得原LP问题的最优解为问题的最优解为最优值为最优值为015/2-11/2 210-21-1100111-11现在学习的是第31页，共40页Page 32例例6.用对偶单纯形法求解：用对偶单纯形法求解：引入松引入松弛变量弛变量得到标得到标准型线准型线性规划性规划解：解：现在学习的是第32页，共40页Page 33构造对偶单纯形表构造对偶单纯形表选取离基变量选取离基变量选取进基变量选取进基变量-2-1-4010 -2-2-20-401-31281612000满足满足,但但不满足不满足现在学习的是第33页，共40页Page 34-2-1-4010 -2-2-20-401-31281612000-2-1-4010 -21/21/2010-1/43/46216003-9满足满足,但但不满足不满足现在学习的是第34页，共40页Page 35-2-1-4010 -21/21/2010-1/4 3/46216003-92140-10 2-1/20-211/2-1/4-1/4208023-13满足满足,但但不满足不满足现在学习的是第35页，共40页Page 3611020-1/2 3/21/401-1/2-1/41/81/8000442-142140-10 2-1/20-211/2-1/4-1/4208023-13满满足足 现在学习的是第36页，共40页Page 3711020-1/2 3/21/401-1/2-1/41/81/8000442-14满满足足 是具有标准形式的是具有标准形式的LP的最优解的最优解.略去松弛变量得原略去松弛变量得原LP问题的最优解为问题的最优解为最优值为最优值为现在学习的是第37页，共40页Page 38 对偶单纯形法应注意的问题：对偶单纯形法应注意的问题：对对偶偶单单纯纯形形法法是是直直接接求求解解原原线线性性规规划划是是一一种种方方法法，而而不不是去求对偶问题的最优解是去求对偶问题的最优解.初初始始表表中中一一定定要要满满足足对对偶偶问问题题的的基基本本解解可可行行，即即底底行行中对应于单位子块的元素为零，其余元素非负中对应于单位子块的元素为零，其余元素非负.对对偶偶单单纯纯形形法法与与普普通通单单纯纯形形法法的的换换基基顺顺序序不不一一样样，普普通通单单纯纯形形法法是是先先确确定定进进基基变变量量后后确确定定离离基基变变量量，对对偶偶单单纯纯形形法法是先确定离基变量后确定进基变量；是先确定离基变量后确定进基变量；现在学习的是第38页，共40页Page 39 普通单纯形法的最小比值是普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，其目的是保证下一个原问题的基本解可行，其目的是保证下一个对偶其目的是保证下一个对偶问题的基本解可行问题的基本解可行.对偶单纯形法在确定出基变量时，若不遵循对偶单纯形法在确定出基变量时，若不遵循 规规则则，任任选选一一个个小小于于零零的的b bi i对对应应的的基基变变量量出出基基，不不影影响响计计算算结结果果，只只是是迭迭代代次次数数可可能能不一样。不一样。对偶单纯形法的最大比值是对偶单纯形法的最大比值是现在学习的是第39页，共40页Page 40感感谢谢大大家家观观看看现在学习的是第40页，共40页