《对偶单纯形法.pptx》由会员分享，可在线阅读，更多相关《对偶单纯形法.pptx（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、什麽是对偶单纯形法？对偶单纯形法是应用对偶原理求解原始线性规划的一种方法在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！第1页/共21页二、对偶单纯形法的基本思想1、对“单纯形法”求解过程认识的提升从更高的角度理解单纯形法初始可行基（对应一个初始基本可行解）迭代另一个可行基（对应另一个基本可行解），直至所有检验数0为止。第2页/共21页 所有检验数0意味着，说明原始问题的最优基也是对偶问题的可行基。换言之，当原始问题的基B既是原始可行基又是对偶可行基时，B成为最优基。定理2-5B是线性规划的最优基的充要条件是，B是可行基，同时也是对偶可行基。第3页/共21页单纯形法的
2、求解过程就是：在保持原始可行的前提下(b列保持0)，通过逐步迭代实现对偶可行(检验数行0)。2、对偶单纯形法思想：换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持0），通过逐步迭代实现原始可行（b列0，从非可行解变成可行解）。第4页/共21页 三、对偶单纯形法的实施1、使用条件：检验数全部0；解答列至少一个元素0；2、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量),使原始问题的非可行解向可行解靠近。第5页/共21页3、计算步骤：建立初始单纯形表，计算检验数行。解答列解答列00已得最优
3、解；已得最优解；至少一个元素至少一个元素0,0,转下步转下步;解答列解答列00原始单纯形法；原始单纯形法；至少一个元素至少一个元素0,0,另外处理；另外处理；检验数全部检验数全部0 0（非基变量检验数（非基变量检验数000第6页/共21页 基变换：先确定换出变量解答列中的负元素（一般选最小的负元素）对应的基变量出基；即相应的行为主元行。第7页/共21页然后确定换入变量原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果(最小比值原则),则选为换入变量,相应的列为主元列,主元行和主元列交叉处的元素为主元素。第8页/共21页 按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列
4、变成单位向量，得到新的单纯形表。继续以上步骤，直至求出最优解。第9页/共21页对偶单纯形法举例(例1-1)1-1)例1 1：用对偶单纯形法解下列线性规划解:先将原问题化为标准形式第10页/共21页再将标准形式改为下列形式：对偶单纯形法举例(例1-2)1-2)则第一个基为B1B1=(P4,P5)=I=(P4,P5)=I基变量为y y4 4,y,y5 5第一个对偶可行基对应的单纯形表如下第11页/共21页XBbY1Y2Y3Y4Y5Y4Y5-2-10-6-110-5-2-101-w0-15-24-500T(B1)Y2Y5-w1/3011/6-1/60-1/3-50-2/3-1/318-150-1-4
5、0T(B2)对偶单纯形法举例(例1-3)第12页/共21页T(B2)Y2Y5-w1/3011/6-1/60-1/3-50-2/3-1/318-150-1-40T(B3)对偶单纯形法举例(例1-4)XBbY1Y2Y3Y4Y5Y2Y3-w-5/410-1/41/415/2011/2-3/21/41/217/2-15/200-7/2-3/2最优解Y*=(0,1/4,1/2,0,0)T最优值W*=-17/2第13页/共21页对偶单纯形法举例(例2-1)例2 2：用对偶单纯形法解下列线性规划解:先将原问题化为下列形式第14页/共21页对偶单纯形法举例(例2-2)则第一个基为B1=(B1=(P3,P4,P
6、5)=IP3,P4,P5)=I基变量为y y3 3,y,y4 4,y,y5 5第一个对偶可行基对应的单纯形表如下T(B1)Y3Y4w-4-2-1100-6-1-30110-2-3000XBbY1Y2Y3Y4Y5Y5-3-1-1001第15页/共21页对偶单纯形法举例(例2-3)T(B1)Y3Y4w-4-2-1100-6-1-30110-2-3000XBbY1Y2Y3Y4Y5Y5-3-1-1001Y3Y2Y5w-2-5/301-1/3-1/321/310-1/3-1/3-1-2/300-1/32/36-100-1-1第16页/共21页对偶单纯形法举例(例3-1)例3 3：用对偶单纯形法解下列线性
7、规划解:取B B1 1=(P=(P3 3，P P4 4，P P5 5)=I)=I为对偶可行基因此其对应的单纯形表如下第17页/共21页对偶单纯形法举例(例3-2)x3x4x5-w-13-1100-2-110104220010-1-1000 x3x4x5x1x2T(B1)x3x1x5-w-70213021-10-1000402120-20-10T(B2)由于基变量X3所在行的变量系数全大于等于0，则原问题无可行解第18页/共21页对偶单纯形法适用范围对偶单纯形法的适用范围：对偶单纯形法适合于解如下形式的线性规划问题第19页/共21页是是是是否否否否得到最优解典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有可行解单纯形法对偶单纯形法所有所有计算计算所有所有计算计算第20页/共21页谢谢大家观赏！第21页/共21页