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