第二章2.3对偶单纯形法讲解学习.ppt

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章2.3对偶单纯形法,所有检验数0意味着,，,说明,原始问题的最优基也是对偶问题的可行基,。换言之，当原始问题的基,B,既是原始可行基又是对偶可行基时，,B,成为最优基。,定理2-5,B,是线性规划的最优基的充要条件是，,B,是可行基，同时也是对偶可行基。,单纯形法的求解过程就是：,在保持原始可行的前提下,(,b,列保持0)，,通过逐步迭代实现对偶可行,(检验数行0),。,2、,对偶单纯形法思想：,换个角度考虑,LP,求解过程,：保持,对偶可行,的前提下（,检验数行保持0,），通过逐步迭代,实现原始可行,（,b,列0,，从非可行解变成可行解）。,三、对偶单纯形法的实施,1、使用条件：,检验数全部0；,解答列至少一个元素 0；,2、实施对偶单纯形法的基本原则：,在保持对偶可行的前提下进行基变换,每一次迭代过程中取出,基变量中的一个负分量,作为,换出变量,去,替换,某个,非基变量,(作为,换入变量,),使原始问题的非可行解向可行解靠近。,3、计算步骤,：,建立初始单纯形表，计算检验数行。,解答列,0已得最优解；,至少一个元素0,转下步;,解答列,0原始单纯形法；,至少一个元素0,另外处理；,检验数全部,0,（非基变量检验数0,基变换：,先确定换出变量,解答列中的负元素,（一般选最小的负元素）,对应的基变量出基,；,即,相应的行,为主元行,。,然后确定换入变量,原则,是：在,保持对偶可行的前提,下，,减少原始问题的不可行性,。,如果,(最小比值原则),则选 为换入变量,相应的列为,主元列,主元行和主元列交叉处的元素,为主元素,。,按主元素进行换基迭代（旋转运算、枢运算）,，,将主元素变成1，主元列变成单位向量,，得到新的单纯形表。,继续以上步骤，直至求出最优解。,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,