对偶问题三对偶单纯形法.ppt

对偶问题三对偶单纯形法
你现在浏览的是第一页，共16页
单纯形法与对偶单纯形法比较
你现在浏览的是第二页，共16页
单纯形法的步骤
你现在浏览的是第三页，共16页
对偶单纯形法的步骤
你现在浏览的是第四页，共16页
如何用？
你现在浏览的是第五页，共16页
基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均非负，
则问题一定无可行解
否则，做换基迭代
你现在浏览的是第六页，共16页
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
你现在浏览的是第七页，共16页
你现在浏览的是第八页，共16页
不是典则形式
X1
X2
X3
X4
X5
检
2
1
0
0
0
Z
X1
1
1
1
0
0
5
X4
0
2
1
1
0
5
X5
0
-4
-6
0
1
-9
0
-1
-2
0
0
Z-10
X1
X2
X3
X4
X5
检
X1
X4
X2
0
1
3/2
0
-1/4
9/4
0
0
-2
1
1/2
1/2
1
0
-1/2
0
1/4
11/4
0
0
-1/2
0
-1/4
Z-31/4
你现在浏览的是第九页，共16页
注意：对偶单纯形法仅限于初始基B对应
的典则形式中目标函数的系数（检
验数）均≤0的情形。
可用对偶单纯形法
B的典则形式
你现在浏览的是第十页，共16页