对偶单纯形法 灵敏度分析.ppt

第二章
线性规划的对偶理论与灵敏度分析
第四节对偶单纯形法
对偶单纯形法并不是求对偶问题解的方法,而是利用单纯形法求解规划问题时运用了对偶理论。
也就是说:对偶单纯形法与单纯形法一样都是是求解线性规划的一种基本方法。它是根据对偶原理和单纯形法原理设计出来的,因此称为对偶单纯形法。
在了解对偶单纯形法的实质之前,我们回顾一下单纯形法。
单纯形法开始于初始基可行解。如果不满足最优性条件,则要换基迭代转到能使目标函数值得到改善的邻近顶点上。在这个转换过程中,存在两个原则: 一是首先保持原问题的解仍是可行的,另一个是要求目标函数值有改善。
如何保证可行?
项目
非基变量
基变量
XB XN
XS
0 XS b
B N
I
Cj-Zj
0
项目
基变量
非基变量
XB
XN XS
CB XB B-1 b
I
B-1 N B-1
Cj-Zj
0
CN -CB B-1 N -CB B-1
初始单纯形表
CB
CN
0
单纯形法是在保持所有约束条件常数项总是保持大于等于零的情况(保证可行),通过迭代,使所有检验数小于等于零(求最大值),求得最优解。
1、当原问题达到最优时,松弛变量经过上述转换后构成的检验数的相反数为其对偶问题的一个可行解,反之亦成立
原问题表中的检验数满足最优性条件
CN-CB B-1 N≤0
-CB B-1 ≤0;
ATY ≥ CT;
Y≥0
YT= CB B-1
从上面可以看出:
也就是说,当原问题达到最优时,对偶问题的解可行。并且根据对偶的性质,我们可以确定此时对偶问题也达到最优
CB:1×m B-1:m ×m
CB B-1:1 ×m Y: m ×1
项目
非基变量
基变量
XB XN
XS
0 XS b
B N
I
Cj-Zj
0
项目
基变量
非基变量
XB
XN XS
CB XB B-1 b
I
B-1 N B-1
Cj-Zj
0
CN -CB B-1 N -CB B-1
初始单纯形表
也就是:单纯形法计算时只要原问题可行(B-1b ≥ 0),对偶问题可行(即检验数小于0),解就是最优解。单纯形法的基本过程就是保证原问题解可行的情况下,不停迭代,直至对偶问题也达到可行,此时原问题达到最优,对偶问题也达到最优
根据刚才所说,单纯形法只要单纯形法计算时只要原问题可行(B-1b ≥ 0),对偶问题可行(即检验数小于0),解就是最优解。所以,我们利用单纯形法对原问题求解时,如果首先保持对偶问题的可行性(即原问题检验数≤0),然后再看原问题是否可行,如果此时原问题的解不可行,则换基迭代,换基过程中保证对偶可行(检验数≤0 ),直至原问题由不可行解变为可行解,此时就得到它的最优解,——这就是对偶单纯形法的基本思想。
第四节对偶单纯形法
也就是说:对偶单纯形法是在保持原问题所有检验数都小于等于零的基础上,通过迭代,使原问题的解(即右边常数项)都大于等于零,从而求得最优解。
第四节对偶单纯形法
(2)初始解不可行,即右端常数项有负分量(如果原问题可行,则直接用单纯形法)
使用对偶单纯形法必须满足两个条件:
(1)单纯形表中的所有检验数必须符合对偶可行,即小于等于0
①先找一个基,建立初始对偶单纯形表,使检验数全部非正,即C全部为非正;
②若b列元素非负,则已经是最优基。反之,则换基迭代,直至原问题可行。
第四节对偶单纯形法
怎么做呢?
例用对偶单纯形法求解
该问题用单纯形法求解时,需要先化标准型,此时约束方程两边左边需要减去剩余变量,同时为了构造单位阵,需要添加人工变量,采用大M法求解。
第四节对偶单纯形法
思考:上面约束方程化为标准型后,两边乘以-1,就可得到单位阵。此时能否用单纯形法?原因?
答:不能。因为此时右边常数项为负数,解不可行。为了保证初始解可行
例用对偶单纯形法求解
第四节对偶单纯形法
能否用对偶单纯形法呢?
对偶单纯形法初始对偶单纯形表只要保证对偶可行,即检验数全部非正即可。并不要求初始解可行,所以右边常数项可以非负,此题目价值系数均为负,意味着初始单纯形表格的检验数为负,而右端常数项又有负数,正好满足对偶单纯形法的要求。