《对偶单纯形法详解优秀课件.ppt》由会员分享，可在线阅读，更多相关《对偶单纯形法详解优秀课件.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、对偶单纯形法详解第1页，本讲稿共22页 二、对偶单纯形法的基本思想二、对偶单纯形法的基本思想1、对、对“单纯形法单纯形法”求解过程认识的提升求解过程认识的提升求解过程认识的提升求解过程认识的提升从更高的层次理解单纯形法从更高的层次理解单纯形法初始可行基初始可行基（对应一个初始基本可行解）（对应一个初始基本可行解）迭迭代代另另另另一一一一个个个个可可可可行行行行基基基基（对对应应另另一一个个基基本本可可行解），直至行解），直至所有检验数所有检验数0为止为止。第2页，本讲稿共22页 所有检验数所有检验数0意味着意味着，说说明明原原始始问问题题的的最最优优基基也也是是对对偶偶问问题题的的可可行行基基
2、。换换言言之之，当当原原始始问问题题的的基基B既既是是原原始始可可行行基基又又是是对偶可行基时，对偶可行基时，B成为最优基。成为最优基。定定定定理理理理2-5B是是线线性性规规划划的的最最优优基基的的充充充充要要要要条条条条件件件件是是，B是可行基，同时也是对偶可行基。是可行基，同时也是对偶可行基。是可行基，同时也是对偶可行基。是可行基，同时也是对偶可行基。第3页，本讲稿共22页LP原问题原问题:若若B是是A A中的一个基中的一个基可行基可行基B对应的解是基对应的解是基本可行解，则本可行解，则B是可行基是可行基对偶可行基对偶可行基若单纯形乘子若单纯形乘子是对偶问题的可行解，是对偶问题的可行解，
3、则则B是对偶可行基是对偶可行基 是对偶问题是对偶问题是对偶问题是对偶问题的可行解的可行解的可行解的可行解检验数检验数等价等价 第4页，本讲稿共22页 证明：证明：第5页，本讲稿共22页单纯形法的求解过程就是：单纯形法的求解过程就是：在保持在保持原始可行原始可行的前提下的前提下的前提下的前提下(b列保持列保持0)，通过逐步迭代通过逐步迭代实现对偶可行实现对偶可行(检验数行检验数行0)。2、对偶单纯形法思想：对偶单纯形法思想：换换个个角角度度考考虑虑LP求求解解过过程程：保保持持对对偶偶可可行行的的前前提提下下（检检验验数数行行保保持持0 0），通通过过逐逐步步迭迭代代实实现现原始可行原始可行（b
4、列列0，从非可行解变成可行解）。，从非可行解变成可行解）。第6页，本讲稿共22页对偶单纯形法的思想（图示）对偶单纯形法的思想（图示）初始基本可初始基本可行解行解保持为基本保持为基本可行解可行解初始对偶可行解初始对偶可行解保持对偶可行性保持对偶可行性始终满足解始终满足解的可行性的可行性始终满始终满足对偶足对偶可行性可行性第7页，本讲稿共22页 三、对偶单纯形法的实施三、对偶单纯形法的实施三、对偶单纯形法的实施三、对偶单纯形法的实施1、使用条件：、使用条件：检验数全部检验数全部检验数全部检验数全部 0；解答列至少一个元素解答列至少一个元素解答列至少一个元素解答列至少一个元素0；2、实施对偶单纯形法
5、的基本原则：、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换每一次每一次迭代过程中取出迭代过程中取出基变量中的一个负分量基变量中的一个负分量作为作为换出换出换出换出变量变量变量变量去去替换替换某个某个非基变量非基变量(作为作为换入变量换入变量),使原始使原始问题的非可行解向可行解靠近。问题的非可行解向可行解靠近。第8页，本讲稿共22页3、计算步骤、计算步骤、计算步骤、计算步骤：建立初始单纯形表，计算检验数行。建立初始单纯形表，计算检验数行。建立初始单纯形表，计算检验数行。建立初始单纯形表，
6、计算检验数行。解答列解答列解答列解答列00已得最优解；已得最优解；已得最优解；已得最优解；至少一个元素至少一个元素至少一个元素至少一个元素0,0,转下步转下步转下步转下步;解答列解答列解答列解答列00原始单纯形法；原始单纯形法；原始单纯形法；原始单纯形法；至少一个元素至少一个元素至少一个元素至少一个元素0,0,另外处理；另外处理；另外处理；另外处理；检验数全部检验数全部检验数全部检验数全部0 0（非基变量检验数（非基变量检验数（非基变量检验数（非基变量检验数000第9页，本讲稿共22页 基变换：基变换：基变换：基变换：先先先先确确确确定定定定换换换换出出出出变变变变量量量量解解答答列列中中的的
7、负负元元素素（一一般般选最小的负元素）选最小的负元素）对应的基变量对应的基变量出基出基；即即相应的行相应的行为主元行为主元行。第10页，本讲稿共22页然然后后确确确确定定定定换换换换入入入入变变变变量量量量原原则则是是：在在保保保保持持持持对对对对偶偶偶偶可可可可行行行行的前提的前提的前提的前提下，下，减少原始问题的不可行性减少原始问题的不可行性减少原始问题的不可行性减少原始问题的不可行性。如果如果(最小比值原则最小比值原则),则选则选为换入变量为换入变量,相应相应的列为的列为主元列主元列,主元行和主元列交叉处的元主元行和主元列交叉处的元素素为主元素为主元素。若 ,要计算最小比值吗？为什么？第
8、11页，本讲稿共22页 按按主主元元素素进进行行换换基基迭迭代代（旋旋转转运运算算、枢枢运运算算），将将主主元元素素变变成成1 1，主主主主元元元元列列列列变变变变成成成成单单单单位位位位向向向向量量量量，得得到到新新的单纯形表。的单纯形表。循环以上步骤，直至求出最优解。循环以上步骤，直至求出最优解。第12页，本讲稿共22页3、举例、举例用对偶单纯形法求解用对偶单纯形法求解LP：化为标准型化为标准型化为标准型化为标准型 将两个等式约束两边分别乘以将两个等式约束两边分别乘以将两个等式约束两边分别乘以将两个等式约束两边分别乘以-1，得，得，得，得第13页，本讲稿共22页以此形式进行列表求解，满足对
9、偶单纯形法的以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：基本条件，具体如下：第14页，本讲稿共22页-2/-2 -4/-3 -比比值值-2-3-4000-Z-1-2-110-21-301-3-4x4x500-2-3-400 x1x2x3x4x5cjxjbXBCB第15页，本讲稿共22页-4/-5/2 -1/-1/2 比比值值0-4-10-10cj-zj0-5/21/21-1/21-1/23/20-1/2-12x4x10-2-2-3-400 x1x2x3x4x5cjxjbXBCB第16页，本讲稿共22页00-3/5-8/5-1/50cj-zj01-1/5-2/51/5107/5-
10、1/5-2/52/511/5x2x1-3-2-2-3-400 x1x2x3x4x5cjxjbXBCB最优解最优解最优解最优解:X*=（11/5，2/5,0,0,02/5,0,0,0）T，最优值最优值最优值最优值:minW=-maxZ*=minW=-maxZ*=-11/5(-2)+2/5(-3)=28/5第17页，本讲稿共22页4、举例、举例用对偶单纯形法求解用对偶单纯形法求解LP：化为化为化为化为标准型标准型标准型标准型 将三个等式约束两边分别乘以将三个等式约束两边分别乘以-1，然后，然后列表求解如下：列表求解如下：第18页，本讲稿共22页-3/-1 -9/-1 -比比值值-3-90000-Z
11、-1-1100-1-4010-1-7001-2-3-3y3y4y5000-3-9000y1y2y3y4y5cjyjbXBCB第19页，本讲稿共22页 -6/-3-3/-1-比比值值0-6-3006-Z11-1000-3-1100-6-1012-1-1y1y4y5-300-3-9000y1y2y3y4y5cjyjbXBCB第20页，本讲稿共22页00-1-208-Z10-4/31/30011/3-1/30001-215/31/31y1y2y5-3-90-3-9000y1y2y3y4y5cjyjbXBCB最优解是最优解是Y*=（5/35/3，1/31/3，0 0，0 0，1）T，目标函数最优值为目标函数最优值为WWmin=-Zmax=8第21页，本讲稿共22页 思考题：思考题：能否不要化为标准型，直接按能否不要化为标准型，直接按极小化问题用单纯形表格迭代求解？极小化问题用单纯形表格迭代求解？（结合课后小组讨论（结合课后小组讨论4一并思考研究）一并思考研究）第22页，本讲稿共22页