《用单纯形法求解》PPT课件.ppt

《《用单纯形法求解》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《用单纯形法求解》PPT课件.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、例：用单纯形法求解例：用单纯形法求解x x1 1 x x2 2 x x3 3 x x4 4 z-3 -1 -1 -1 0 X3 X4-2 2 1 0 3 1 0 1 4 6 RHSRHSx x1 1 x x2 2 x x3 3 x x4 4 z-2 2 0 0 10 X3 X4-2 2 1 0 3 1 0 1 4 6 RHSRHS z 0 0 -1 0 6 X2 X4-1 1 1/2 0 4 0 -1/2 1 2 4 最优解最优解X=（0，2，0，4），最优值是），最优值是6。T2.4 初始解（两阶段法）初始解（两阶段法）问题：线性规划问题：线性规划问题化为标准型时，问题化为标准型时，若约束条

2、件的系数若约束条件的系数矩阵中不存在单位矩阵中不存在单位矩阵，如何构造矩阵，如何构造初始可行基？初始可行基？2.4 初始解（两阶段法）初始解（两阶段法）第一阶段：第一阶段：加入人工加入人工变量量,构造初始可行基构造初始可行基.用用单纯形法求解形法求解,若若g=0,进入第二入第二阶段段,否否则,原原问题无可行解。无可行解。第二第二阶段段：去掉人工：去掉人工变量，量，还原目原目标函数系数，做函数系数，做出初始出初始单纯形表。形表。例：求解下列线性规划问题例：求解下列线性规划问题将原将原问题化成化成标准型：准型：解解:化标准型化标准型用两阶段方法来求解。用两阶段方法来求解。第一阶段第一阶段的线性规划

3、问题为的线性规划问题为x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 g 0 0 0 0 0 -1 -1 0 X4 X6 X7 1 1 1 1 0 0 0-2 1 -1 0 -1 1 0 0 3 1 0 0 0 1 4 1 9RHSRHSx x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 RHS RHS g-2 4 0 0 -1 0 0 10 X4 X6 X7 1 1 1 1 0 0 0-2 1 -1 0 -1 1 0 0 3 1 0 0 0 1 4 1 9 g 6 0 4 0 3 -4 0 6 X

4、4 X2 X7 3 0 2 1 1 -1 0-2 1 -1 0 -1 1 0 6 0 4 0 3 -3 1 3 1 6 g 0 0 0 0 0 -1 -1 0 X4 X2 X1 0 0 0 1 -1/2 1/2 -1/2 0 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 -1/2 1/6 0 3 1x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 RHSRHS得原问题的基可行解得原问题的基可行解X=(1,3,0,0,0,)T。第二阶段：第二阶段：将上表中的人工变量去除，目标函数换成原问题的将上表中的人工变量去除，目标函数换成原问题的

5、目标函数从上表的最后一个单纯形表出发，继续计算。目标函数从上表的最后一个单纯形表出发，继续计算。Z-3 0 1 0 0 0 X4 X2 X1 0 0 0 1 -1/2 0 1 1/3 0 0 1 0 2/3 0 1/2 0 3 1x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 RHSRHS Z 0 0 3 0 3/2 3 X4 X2 X1 0 0 0 1 -1/2 0 1 1/3 0 0 1 0 2/3 0 1/2 0 3 1 Z-9/2 0 0 0 -3/4-3/2 X4 X2 X3 0 0 0 1 -1/2-1/2 1 0 0 -1/4 3/2 0 1 0 3/4 0

6、 5/2 3/2x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 RHSRHS得原标准线性规划问题的最优解得原标准线性规划问题的最优解X=（0，5/2，3/2，0，0）T，最优值是最优值是-3/2。所以最初的线性规划问题的最优解所以最初的线性规划问题的最优解X=（0，5/2，3/2）T，最优，最优值是值是3/2。例：求解下列线性规划问题例：求解下列线性规划问题将原将原问题化成化成标准型：准型：解解:化标准型化标准型用两阶段方法来求解。用两阶段方法来求解。第一阶段第一阶段的线性规划问题为的线性规划问题为x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x

7、x6 6 RHS RHS g 0 0 0 0 -1 -1 0 X5 X6 X4 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS g 7 4 -1 0 0 0 9 X5 X6 X4 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3 g 0 5/3 -1 0 -7/3 0 2 X1 X6 X4 1 1/3 0 0 1/3 0 0 5/3 -1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 2x x1 1 x x2

8、2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS g 0 5/3 -1 0 -7/3 0 2 X1 X6 X4 1 1/3 0 0 1/3 0 0 5/3 -1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 2 g 0 0 -1 -1 -2 0 0 X1 X6 X2 1 0 0 -1/5 2/5 0 0 0 -1 -1 -1 1 0 1 0 3/5 -1/5 0 3/5 0 6/5 g 0 0 -1 -1 -2 0 0 X1 X6 X2 1 0 0 -1/5 2/5 0 0 0 -1 -1 -1 1 0 1 0 3/5 -1/5 0 3/5 0 6/5x

9、 x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS g 0 0 0 0 -1 -1 0 X1 X3 X2 1 0 0 -1/5 2/5 0 0 0 1 1 1 -1 0 1 0 3/5 -1/5 0 3/5 0 6/5第二阶段：第二阶段：将上表中的人工变量去除，目标函数换成原问题的将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。目标函数从上表的最后一个单纯形表出发，继续计算。z-4 -1 0 0 0 X1 X3 X2 1 0 0 -1/5 0 0 1 1 0 1 0 3/5 3/5 0 6/5x x1 1

10、 x x2 2 x x3 3 x x4 4 RHS RHS z 0 0 0 -1/518/5 X1 X3 X2 1 0 0 -1/5 0 0 1 1 0 1 0 3/5 3/5 0 6/5所以最初的线性规划问题的最优解所以最初的线性规划问题的最优解X=(3/5，6/5)T，最优值是最优值是18/5。例：求解下列线性规划问题例：求解下列线性规划问题将原将原问题化成化成标准型：准型：解解:化标准型化标准型用两阶段方法来求解。用两阶段方法来求解。第一阶段第一阶段的线性规划问题为的线性规划问题为x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS g 0

11、0 0 0 -1 -1 0 X5 X6 2 -3 -1 0 1 0 -1 1 0 -1 0 1 2 3x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 RHS RHS g 1 -2 -1 -1 0 0 5 X5 X6 2 -3 -1 0 1 0 -1 1 0 -1 0 1 2 3 g 0 -1/2 -1/2 -1 -1/2 0 4 X1 X6 1 -3/2 -1/2 0 1/2 0 0 -1/2 -1/2 -1 1/2 1 1 4原问题无解。原问题无解。两阶段方法总结两阶段方法总结第一阶段结束时，辅助问题目标函数值大于第一阶段结束时，辅助问题目标函数值大于0，

12、原，原问题无解；问题无解；第一阶段结束时，辅助问题目标函数值等于第一阶段结束时，辅助问题目标函数值等于0，且，且人工变量都是非基变量，那末，所得基本可行解人工变量都是非基变量，那末，所得基本可行解为原问题初始基本可行解，去掉人工变量，目标为原问题初始基本可行解，去掉人工变量，目标函数行换为原问题目标函数，继续求解。函数行换为原问题目标函数，继续求解。第一阶段结束时，辅助问题目标函数值等于第一阶段结束时，辅助问题目标函数值等于0，但，但是人工变量不都是非基变量，那么令其强行出基，是人工变量不都是非基变量，那么令其强行出基，然后继续求解。然后继续求解。小小 结结线性线性规划规划问题问题图解法图解法只有两个变量只有两个变量约束矩阵约束矩阵A中中含有一个含有一个m阶阶的单位矩阵的单位矩阵右端向量非负右端向量非负单纯形方法单纯形方法约束矩阵约束矩阵A中中没有一个没有一个m阶阶的单位矩阵的单位矩阵两阶段法两阶段法小结小结(一一).会用会用两阶段法两阶段法解线性规划问题解线性规划问题.(二二).作业作业 74页页 17(3)