物流优化技术课件第3章3.7对偶单纯形法.ppt

3.33.3对偶单纯形法对偶单纯形法一、什麽是对偶单纯形法？一、什麽是对偶单纯形法？对偶单纯形法对偶单纯形法是应用对偶原理对偶原理求解原始线性规划的一种方法在原始问题的单纯形表格上进行对偶处理对偶处理注意：注意：不是解对偶问题的单纯形法！二、对偶单纯形法的基本思想二、对偶单纯形法的基本思想1 1、对、对“ “单纯形法单纯形法” ”求解过程认识的提升求解过程认识的提升从更高的角度理解单纯形法初始可行基初始可行基（对应一个初始基本可行解）迭代迭代另一个可行基另一个可行基（对应另一个基本可行解），直至所有检验数所有检验数 0 0为止 所有检验数0意味着，说明原始问题的最优基也是对偶问题的可行原始问题的最优基也是对偶问题的可行基基换言之，当原始问题的基B既是原始可行基又是对偶可行基时，B成为最优基定理定理2-52-5B B是线性规划的最优基的充要条件是线性规划的最优基的充要条件是，是，B B是可行基，同时也是对偶可行基是可行基，同时也是对偶可行基单纯形法的求解过程就是：单纯形法的求解过程就是：在保持原始可行的前提下在保持原始可行的前提下(b列保持0)，通过逐步迭代实现对偶可行通过逐步迭代实现对偶可行(检验数行 0)。

2 2、 对偶单纯形法思想：对偶单纯形法思想：换个角度考虑换个角度考虑LPLP求解过程求解过程：保持对偶可行对偶可行的前提下（检验数行保持检验数行保持0 0） ，通过逐步迭代实现原始可行实现原始可行（b b列列00，从非可行解变成可行解） 三、对偶单纯形法的实施三、对偶单纯形法的实施1 1、使用条件：、使用条件：检验数全部检验数全部0 0；解答列至少一个元素解答列至少一个元素00；2 2、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换每一次迭代过程中取出基变量中的一个负分量基变量中的一个负分量作为换出变量换出变量去替换替换某个非基变量非基变量(作为换入换入变量变量),使原始问题的非可行解向可行解靠近3 3、计算步骤、计算步骤： 建立初始单纯形表，计算检验数行建立初始单纯形表，计算检验数行解答列解答列00已得最优解；已得最优解；至少一个元素至少一个元素0,0,转下步转下步; ;解答列解答列00原始单纯形法；原始单纯形法；至少一个元素至少一个元素0,0,另外处理；另外处理；检验数全部检验数全部 0 0（基变量检验数（基变量检验数=0=0）至少一个检验数至少一个检验数 0 0 基变换：基变换：先确定换出变量先确定换出变量解答列中的负元素解答列中的负元素（一般选最小的负元素）对应的基变量出基对应的基变量出基；即相应的行为主元行为主元行。

然后确定换入变量然后确定换入变量原则原则是：在保持对偶保持对偶可行的前提可行的前提下，减少原始问题的不可行性减少原始问题的不可行性如果(最小比值原则),则选为换入变量,相应的列为主元列主元列 ,主元行和主元列交叉处的元素为主元素为主元素 按主元素进行换基迭代（旋转运算、枢按主元素进行换基迭代（旋转运算、枢运算）运算），将主元素变成将主元素变成1 1，主元列变成单位向，主元列变成单位向量量，得到新的单纯形表 继续以上步骤，直至求出最优解继续以上步骤，直至求出最优解。