单纯形法的计算步骤.ppt

单纯形法的计算步骤
用单纯形法求下列线性规划的最优解
解:1)将问题化为标准型,加入松驰变量x3、x4则标准型为:
单纯形法的计算步骤
2)求出线性规划的初始基可行解,列出初始单纯形表。
cj
3
4
0
0
θi
cB
基
b
x1
x2
x3
x4
0
x3
40
2
1
1
0
0
x4
30
1
3
0
1
3
4
0
0
检验数
单纯形法的计算步骤
3)进行最优性检验
如果表中所有检验数,则表中的基可行解就是问题的最优解,计算停止。否则继续下一步。
4)从一个基可行解转换到另一个目标值更大的基可行解,列出新的单纯形表
确定换入基的变量。选择,对应的变量xj作为换入变量,当有一个以上检验数大于0时,一般选择最大的一个检验数,即: ,其对应的xk作为换入变量。
确定换出变量。根据下式计算并选择θ,选最小的θ对应基变量作为换出变量。
单纯形法的计算步骤
用换入变量xk替换基变量中的换出变量,得到一个新的基。对应新的基可以找出一个新的基可行解,并相应地可以画出一个新的单纯形表。
5)重复3)、4)步直到计算结束为止。
单纯形法的计算步骤
cj
3
4
0
0
θi
cB
基变量
b
x1
x2
x3
x4
0
x3
40
2
1
1
0
0
x4
30
1
3
0
1
3
4
0
0
0
x3
4
x2
3
x1
4
x2
换入列
bi /ai2,ai2>0
40
10
换出行
将3化为1
5/3
1
18
0
1/3
0
1/3
10
1
-1/3
30
30
0
5/3
0
-4/3
乘以1/3后得到
1
0
3/5
-1/5
18
0
1
-1/5
-2/5
4
0
0
-1
-1
单纯形法的进一步讨论-人工变量法
用大M法解下列线性规划
解:首先将数学模型化为标准形式
系数矩阵中不存在单位矩阵,无法建立初始单纯形表。
单纯形法的进一步讨论-人工变量法
故人为添加两个单位向量,得到人工变量单纯形法数学模型:
其中:M是一个很大的抽象的数,不需要给出具体的数值,可以理解为它能大于给定的任何一个确定数值;再用前面介绍的单纯形法求解该模型,计算结果见下表。
单纯形法的进一步讨论-人工变量法
cj
3
2
-1
0
0
-M
-M
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
θi
0
x6
4
-4
3
1
-1
0
1
0
4
-M
x5
10
1
-1
2
0
1
0
0
5
-M
x7
1
2
-2
1
0
0
0
1
1
3-2M
2+M
-1+2M↑
-M
0
x6
3
-6
5
0
-1
0
1
3/5
-M
x5
8
-3
3
0
0
1
0
8/3
-1
x3
1
2
-2
1
0
0
0
——