生产管理学 2.3 对偶单纯形法.pdf

对偶单纯形法对偶单纯形法
一、什麽是对偶单纯形法？一、什麽是对偶单纯形法？
对偶单纯形法对偶单纯形法是应用对偶原理对偶原理求解原始
线性规划的一种方法——在原始问题的单
纯形表格上进行对偶处理对偶处理。
注意：注意：不是解对偶问题的单纯形法！
二、对偶单纯形法的基本思想二、对偶单纯形法的基本思想
11、对、对““单纯形法单纯形法””求解过程认识的提升求解过程认识的提升—
—
从更高的角度理解单纯形法
初始可行基初始可行基（对应一个初始基本可行
解）
→迭代→→迭代→另一个可行基另一个可行基（对应另一个基
本可行解），直至所有检验数≤所有检验数≤00为止。
所有检验数≤0意味着
1
CN CB B N  0 A  C ，
说明原始问题的最优基也是对偶问题的可行原始问题的最优基也是对偶问题的可行
基基。换言之，当原始问题的基B既是原始可
行基又是对偶可行基时，B成为最优基。
定理定理22--55 BB是线性规划的最优基是线性规划的最优基的的充要条件充要条件
是，是，BB是可行基，同时也是对偶可行基。是可行基，同时也是对偶可行基。
单纯形法的求解过程就是：单纯形法的求解过程就是：
在保持在保持原始可行原始可行的前提下的前提下（b列保持≥0），
通过逐步迭代通过逐步迭代实现对偶可行实现对偶可行（检验数行
≤220、、） 对偶单纯形法思想：。对偶单纯形法思想：。
换个角度考虑换个角度考虑LPLP求解过程求解过程：保持对偶可行对偶可行
的前提下（检验数行保持≤检验数行保持≤00） ，通过逐步
迭代实现原始可行实现原始可行（bb列≥列≥00，从非可行解变
成可行解）。
三、对偶单纯形法的实施三、对偶单纯形法的实施
11、使用条件：、使用条件： ①检验数全部≤①检验数全部≤00；；
②解答列至少一个元素②解答列至少一个元素 << 00；；
22、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：
在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换——每一
次迭代过程中取出基变量中的一个负分量基变量中的一个负分量作为
换出变量换出变量去替换替换某个非基变量非基变量（作为换入变换入变
量量），使原始问题的非可行解向可行解靠近。
33、计算步骤、计算步骤：
①建立初始单纯形表，计算检验数行。①建立初始单纯形表，计算检验数行。
解答列≥0——已得最优解；
检验数全部≤0
（非基变量检验数<0）
至少一个元素<0,转下步;
解答列≥0——原始单纯形法；
至少一个检验数>0
至少一个元素<0,另外处理；
 基变换：基变换：
先确定换出变量先确定换出变量——解答列中的负元素解答列中的负元素
（一般选最小的负元素）对应的基变量对应的基变量出出
基基；
即 1 1 1
min(B b)i (B b)i  0 (B b)l ,则选xl出基，
i
相应的行为主元行为主元行。
然后然后确定换入变量确定换入变量——原则原则是：在保持对偶保持对偶
可行的前提可行的前提下，减少原始问题的不可行性减少原始问题的不可行性。
如果  
 c j  z j '  c k  z k
min  a lj  0 
j ' '
 a lj  a lk
（最小比值原则） ，则选x k 为换入变量，相
应的列为主元列主元列，主元行和主元列交叉处的
'
元素 alk 为主元素为主元素。
按主元素进行换基迭代按主元素进行换基迭代（旋转运算、枢（旋转运算、枢
运算）运算），将主元素变成将主元素变成11，主元列变成单位向，主元列变成单位向
量量，得到新的单纯形表。
继续以上步骤，直至求出最优解。继续以上步骤，直至求出最优解。
课后小组讨论课后小组讨论44 讨论对偶单纯形法中确定换入讨论对偶单纯形法中确定换入
变量的最小比值原则的依据，给出详细的证明变量的最小比值原则的依据，给出详细的证