文档介绍：对偶单纯形算法
techlzj@
math123
4. 对偶单纯形算法
得到最优解时的单纯形表的情况:
对偶单纯形算法思想
在最优解处
令
,则(1)变为
(1)
因此:原始单纯型算法的思想可以概括为
,向对偶可行性靠拢
由对偶问题的对称性,把上述思想对称描述,即
,向原始可行性靠拢(对偶单纯形算法思想)
目标函数特点
其中是基本解(但不可行,有负值基本量)
由强对偶定理知,在最优解处最优目标值相等,
因此有:
即
从而对偶单纯形算法的操作方式是:
保持对偶可行性,让目标不断增大,直到满足
原始可行性。
单纯形表
出基
变量
任务是选择进基变量
使得转轴运算后,有
需进一步确定
从而要使
必然有
故取
否
算法过程
对偶可行初始解
检查可行
是则停止
得最优解
选出基变量
检查
是否无可
行解
是则停止
否
无最优解
选入基变量
计算典式检验数
原—对偶算法对比
原始单纯形法
对偶单纯形法
1
给定初始点,要求
给定初始对偶可行解,要求
2
找入基变量( )
找出基变量( )
3
找出基变量
找入基变量
4
最优
最优
5
无界
不可行
最优单纯形表中直接获得 对偶最优解
从而
If
对应的变量时人工变量或者松弛变量,
则对应的
故(1)变为:
(1)
算例