23对偶单纯形法 、什麽是对偶单纯形法? 对偶单纯形法是应用对偶原理求解原始 线性规划的一种方法在原始问题的单 纯形表格上进行对偶处理 注意:不是解对偶问题的单纯形法!
2.3 对偶单纯形法 一、什麽是对偶单纯形法？ 对偶单纯形法是应用对偶原理求解原始 线性规划的一种方法——在原始问题的单 纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！
二、对偶单纯形法的基本思想 1、对“单纯形法”求解过程认识的提 升 从更高的角度理解单纯形法 初始可行基(对应一个初始基本可行解) →迭代→另一个可行基(对应另一个基 本可行解),直至所有检验数≤0为止
二、对偶单纯形法的基本思想 1、对“单纯形法”求解过程认识的提 升—— 从更高的角度理解单纯形法 初始可行基（对应一个初始基本可行解） →迭代→另一个可行基（对应另一个基 本可行解），直至所有检验数≤0为止
所有检验数<0意味着 C-CBN≤0→zA≥C 说明原始问题的最优基也是对偶问题的可行 基。换言之,当原始问题的基B既是原始可 行基又是对偶可行基时,B成为最优基。 定理25B是线性规划的最优基的充要条件 是,B是可行基,同时也是对偶可行基
所有检验数≤0意味着 CN −CB B N A C ， − 0 1 说明原始问题的最优基也是对偶问题的可行 基。换言之，当原始问题的基B既是原始可 行基又是对偶可行基时，B成为最优基。 定理2-5 B是线性规划的最优基的充要条件 是，B是可行基，同时也是对偶可行基
单纯形法的求解过程就是: 在保持原始可行的前提下(b列保持≥0), 通过逐步迭代实现对偶可行(检验数行≤0)。 2、对偶单纯形法思想: 换个角度考虑LP求解过程:保持对偶可行 的前提下(检验数行保持<0),通过逐步迭 代实现原始可行(b列≥0,从非可行解变成 可行解)
单纯形法的求解过程就是： 在保持原始可行的前提下（b列保持≥0）， 通过逐步迭代实现对偶可行（检验数行≤0）。 2、 对偶单纯形法思想： 换个角度考虑LP求解过程：保持对偶可行 的前提下（检验数行保持≤0） ，通过逐步迭 代实现原始可行（b列≥0，从非可行解变成 可行解）
三、对偶单纯形法的实施 1、使用条件:①检验数全部<0; ②解答列至少一个元素<0; 2、实施对偶单纯形法的基本原则 在保持对偶可行的前提下进行基变换每 次迭代过程中取出基变量中的一个负分量作为 换出变量去替换某个非基变量(作为换入变 量),使原始问题的非可行解向可行解靠近
三、对偶单纯形法的实施 1、使用条件： ①检验数全部≤0； ②解答列至少一个元素 < 0； 2、实施对偶单纯形法的基本原则： 在保持对偶可行的前提下进行基变换——每一 次迭代过程中取出基变量中的一个负分量作为 换出变量去替换某个非基变量（作为换入变 量），使原始问题的非可行解向可行解靠近