文档介绍：对偶单纯形法是求解对偶规划的一种方法
×
对偶单纯形法:利用对偶理论得到的一个
求解线性规划问题的方法
对偶单纯形法
单纯形法(原始单纯形法)的两个条件:
1、问题为标准型
2、有初始基本可行解
用单纯形法求解
对偶单纯形法的优点:
1、不需要人工变量;
2、当变量多于约束时,用对偶单纯形法可减少迭代次数;
3、在灵敏度分析中,有时需要用对偶单纯形法处理简化。
B 可逆
原始单纯形法的基本思路:
关于可行基B的典则形式
检验数
XB XN
常数项
检验行
- CBB-1N
Z- CBB-1b
XB
E B-1N
B-1b
初始单纯形表:
原始单纯形法的迭代过程:
对偶单纯形法的基本思路:
XB XN
常数项
检验行
- 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