对偶单纯形法(经典运筹学).ppt

该【对偶单纯形法(经典运筹学) 】是由【piaoshumai】上传分享，文档一共【23】页，该文档可以免费在线阅读，需要了解更多关于【对偶单纯形法(经典运筹学) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。×
对偶单纯形法：利用对偶理论得到的一个
求解线性规划问题的方法
对偶单纯形法
对偶单纯形法是求解对偶规划的一种方法
01
02
03
有初始基本可行解
问题为标准型
用单纯形法求解
单纯形法（原始单纯形法）的两个条件：
对偶单纯形法的优点：
不需要人工变量；
当变量多于约束时，用对偶单纯形法可减少迭代次数；
在灵敏度分析中，有时需要用对偶单纯形法处理简化。
原始单纯形法的基本思路：
可逆
关于可行基B的典则形式
检验数
原始单纯形法的迭代过程：
初始单纯形表：
XB XN
常数项
检验行
0 CN- CBB-1N
Z- CBB-1b
XB
E B-1N
B-1b
对偶单纯形法的基本思路：
logo
作对偶单纯形表：
XB XN
常数项
检验行
0 CN- CBB-1N
Z- CBB-1b
XB
E B-1N
B-1b
基B的典则形式
X1
X2
X3
X4
X5
检
-2
-1
0
0
0
Z
X3
-3
-1
1
0
0
-3
X4
-4
-3
0
1
0
-6
X5
1
2
0
0
1
3
不可行
检验行≤0
分析：
若X3或X4所在的行的aij均非负，
则问题一定无可行解
否则，做换基迭代
X1
X2
X3
X4
X5
检
-2
-1
0
0
0
Z
X3
-3
-1
1
0
0
-3
X4
-4
-3
0
1
0
-6
X5
1
2
0
0
1
3
1、确定出基变量：
设br =min{bi | bi <0}
则取br所在行的基变量
为出基变量
即取X4为出基变量
2、确定入基变量：
原则：
保持检验行系数≤0
X1
X2
X3
X4
X5
检
X3
X2
X5
X1
X2
X3
X4
X5
检
X3
X2
X1
-2/3 0 0 -1/3 0 Z+2
-5/3 0 1 -1/3 0 -1
4/3 1 0 -1/3 0 2
-5/3 0 0 2/3 1 -1
0 0 0 -3/5 -2/5 Z+12/5
0 0 1 -1 -1 0
0 1 0 1/5 4/5 6/5
1 0 0 -2/5 -3/5 3/5
对偶单纯形法步骤：
1、找出一个初始对偶可行解。
把原问题写成该基的典则形式时，目标函数的系数均≤0
2、判断：
（1）若B-1b≥0，则得到最优解
结束
（2）若B-1b≥0，
则问题无可行解。
3、换基迭代：
（1）确定出基变量：
（2）确定入基变量
即找出一个基B，
否则转下一步