对偶单纯形法精品课件

1、对偶单纯形法第1页，共22页，2022年，5月20日，1点56分，星期三 二、对偶单纯形法的基本思想 1、对“单纯形法”求解过程认识的提升 从更高的层次理解单纯形法 初始可行基（对应一个初始基本可行解） 迭代另一个可行基（对应另一个基本可行解），直至所有检验数0为止。第2页，共22页，2022年，5月20日，1点56分，星期三 所有检验数0意味着 ，说明原始问题的最优基也是对偶问题的可行基。换言之，当原始问题的基B既是原始可行基又是对偶可行基时，B成为最优基。定理2-5 B是线性规划的最优基的充要条件是，B是可行基，同时也是对偶可行基。第3页，共22页，2022年，5月20日，1点56分，星期

2、三LP原问题:若B是A中的一个基可行基B对应的解是基本可行解，则B是可行基对偶可行基若单纯形乘子 是对偶问题的可行解，则B是对偶可行基 是对偶问题的可行解检验数等价 第4页，共22页，2022年，5月20日，1点56分，星期三 证明：第5页，共22页，2022年，5月20日，1点56分，星期三单纯形法的求解过程就是： 在保持原始可行的前提下(b列保持0)， 通过逐步迭代实现对偶可行(检验数行0)。 2、 对偶单纯形法思想： 换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持0） ，通过逐步迭代实现原始可行（b列0，从非可行解变成可行解）。 第6页，共22页，2022年，5月20日，1

3、点56分，星期三对偶单纯形法的思想（图示）原问题初始基本可行解保持为基本可行解初始对偶可行解保持对偶可行性最优解基本可行性对偶可行性始终满足解的可行性始终满足对偶可行性第7页，共22页，2022年，5月20日，1点56分，星期三 三、对偶单纯形法的实施1、使用条件： 检验数全部0； 解答列至少一个元素 0；2、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量),使原始问题的非可行解向可行解靠近。 第8页，共22页，2022年，5月20日，1点56分，星期三3、计算步骤： 建立初始单纯形表，计算检验数

4、行。解答列0已得最优解；至少一个元素0,转下步;解答列0原始单纯形法；至少一个元素0,另外处理； 检验数全部0（非基变量检验数0第9页，共22页，2022年，5月20日，1点56分，星期三 基变换： 先确定换出变量解答列中的负元素（一般选最小的负元素）对应的基变量出基； 即相应的行为主元行。第10页，共22页，2022年，5月20日，1点56分，星期三然后确定换入变量原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果 (最小比值原则),则选 为换入变量 , 相应的列为主元列 , 主元行和主元列交叉处的元素 为主元素。若 ,要计算最小比值吗？为什么？第11页，共22页，2022年，5月

5、20日，1点56分，星期三 按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。 循环以上步骤，直至求出最优解。第12页，共22页，2022年，5月20日，1点56分，星期三3、举例用对偶单纯形法求解LP： 化为标准型 将两个等式约束两边分别乘以-1，得第13页，共22页，2022年，5月20日，1点56分，星期三以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：第14页，共22页，2022年，5月20日，1点56分，星期三 -2/-2 - -4/-3 - - 比 值 -2 -3 -4 0 0 0 -Z -1 -2 -1 1 0 -2 1

6、-3 0 1 -3 -4 x4 x5 0 0 -2 -3 -4 0 0 x1 x2 x3 x4 x5 cj xj b XB CB第15页，共22页，2022年，5月20日，1点56分，星期三- -4/-5/2 - -1/-1/2 比 值 0 -4 -1 0 -1 0 cj-zj 0 -5/2 1/2 1 -1/2 1 -1/2 3/2 0 -1/2 -1 2 x4 x1 0 -2 -2 -3 -4 0 0 x1 x2 x3 x4 x5 cj xj b XB CB第16页，共22页，2022年，5月20日，1点56分，星期三 0 0 -3/5 -8/5 -1/5 0 cj-zj 0 1 -1/5

7、 -2/5 1/5 1 0 7/5 -1/5 -2/5 2/5 11/5 x2 x1 -3 -2 -2 -3 -4 0 0 x1 x2 x3 x4 x5 cj xj b XB CB最优解: X*=（11/5，2/5, 0, 0, 0）T，最优值: minW= -maxZ* = -11/5(-2)+2/5(-3)= 28/5第17页，共22页，2022年，5月20日，1点56分，星期三4、举例用对偶单纯形法求解LP： 化为标准型 将三个等式约束两边分别乘以-1，然后列表求解如下：第18页，共22页，2022年，5月20日，1点56分，星期三 -3/-1 -9/-1 - - - 比 值 -3 -9

8、 0 0 0 0 -Z -1 -1 1 0 0 -1 -4 0 1 0 -1 -7 0 0 1 -2 -3 -3 y3 y4 y5 0 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB第19页，共22页，2022年，5月20日，1点56分，星期三 - -6/-3 -3/-1 - - 比 值 0 -6 -3 0 0 6 -Z 1 1 -1 0 0 0 -3 -1 1 0 0 -6 -1 0 1 2 -1 -1 y1 y4 y5 -3 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB第20页，共22页，2022年，5月20日，1点56分，星期三 0 0 -1 -2 0 8 -Z 1 0 -4/3 1/3 0 0 1 1/3 -1/3 0 0 0 1 -2 1 5/3 1/3 1 y1 y2 y5 -3 -9 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB最优解是Y*=（5/3，1/3，0，0，1）T，目标