单纯形法的计算步骤.ppt

单纯形法的计算步骤
用单纯形法求下列线性规划的最优解
解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:
精选课件
单纯形法的计算步骤
2）求出线性规划的初始基可行解，列出初始单纯形表。
检验数
精选课件
单纯形法的计算步骤
3）进行最优性检验
如果表中所有检验数 ，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。
4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表
确定换入基的变量。选择 ，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即： ，其对应的xk作为换入变量。
确定换出变量。根据下式计算并选择θ ，选最小的θ对应基变量作为换出变量。
精选课件
单纯形法的计算步骤
用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。
5）重复3）、4）步直到计算结束为止。
精选课件
单纯形法的计算步骤
换入列
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是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。
精选课件
单纯形法的进一步讨论－人工变量法