用单纯形法求解ppt课件

1、例：用单纯形法求解例：用单纯形法求解4 , 3 , 2 , 1, 06 3 4 22 . .3 min4213214321jxxxxxxxtsxxxxzj z -3 -1 -1 -1 0 X3 X4 -2 2 1 0 3 1 0 1 4 6 z -2 2 0 0 10 X3 X4 -2 2 1 0 3 1 0 1 4 6 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 初始解两阶段法初始解两阶段法11221111221121122222112212min z.,.,0nnnnnnmmm nnmnc xc xc xaxaxaxbaxaxaxbaxaxaxbxxx 0b第一阶段：参与人工变量第一阶段：参与人工变量,构造初始可行基构造初始可行基. 1111221112112222221122121,. . . ,.,.,nnnnnnmmmnnn mmnnn ma xa xa xxba xa xa xxbaxaxaxxbx xxxx 0 12min g.nnnmxxx

3、 用单纯形法求解用单纯形法求解, ,假设假设g=0, g=0, 进入第二阶段进入第二阶段, ,否那么否那么, ,原问原问题无可行解。题无可行解。 第二阶段：去掉人工变量，复原目的函数系数，做第二阶段：去掉人工变量，复原目的函数系数，做出初始单纯形表。出初始单纯形表。 1312312323123m ax342139,0zxxxxxxxxxxxxx 例：求解以下线性规划问题例：求解以下线性规划问题将原问题化成规范型：将原问题化成规范型：1312312323123max342139,0zxxxxxxxxxxxxx 131234123523min3421390,1,.5jzxxxxxxxxxxxxxj

4、 化规范型化规范型用两阶段方法来求解。用两阶段方法来求解。第一阶段的线性规划问题为第一阶段的线性规划问题为67123412356237min421390,1,.7jgxxxxxxxxxxxxxxxj 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 9 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 X4 X2 X7 3 0 2 1 1 -

5、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 1得原问题的基可行解得原问题的基可行解X=(1,3,0,0,0,)TX=(1,3,0,0,0,)T。第二阶段：将上表中的人工变量去除，目的函数换成原问题的第二阶段：将上表中的人工变量去除，目的函数换成原问题的目的函数从上表的最后一个单纯形表出发，继续计算。目的函数从上表的最后一个单纯形表出发，继续计算。 Z -3 0 1

6、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 1 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 5/2 3/2得原规范线性规划问题的最优解得原规范线性规划问题的最优解X=X=0 0，5/25/2，3/23/2，0 0，0 0T T，最优值是最优值是-3/2-3/2。所以最初的线性规划问

7、题的最优解所以最初的线性规划问题的最优解X=X=0 0，5/25/2，3/23/2T T，最优，最优值是值是3/23/2。例：求解以下线性规划问题例：求解以下线性规划问题 0,3263433.4min2121212121xxxxxxxxtsxxz将原问题化成规范型：将原问题化成规范型：化规范型化规范型用两阶段方法来求解。用两阶段方法来求解。 0,3263433.4min2121212121xxxxxxxxtsxxz 0,3263433.4min43214213212121xxxxxxxxxxxxtsxxz第一阶段的线性规划问题为第一阶段的线性规划问题为 g 0 0 0 0 -1 -1 0 X5

8、 X6 X4 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3 0,3263433.min654321421632152165xxxxxxxxxxxxxxxxtsxxg 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 2 g 0 5/3 -1 0 -7/3 0 2 X1 X6 X4 1 1/3 0 0

9、 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/5 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

10、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/5 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/5X=(3/5，6/5)T6/5)T，最优值是最优值是18/5

11、18/5。例：求解以下线性规划问题例：求解以下线性规划问题 0,3232.42min21212121xxxxxxtsxxz将原问题化成规范型：将原问题化成规范型：化规范型化规范型用两阶段方法来求解。用两阶段方法来求解。 0,3232.42min21212121xxxxxxtsxxz 0,3232.42min432142132121xxxxxxxxxxtsxxz第一阶段的线性规划问题为第一阶段的线性规划问题为 g 0 0 0 0 -1 -1 0 X5 X6 2 -3 -1 0 1 0 -1 1 0 -1 0 1 2 3 0,3232.min6543216421532165xxxxxxxxxxxx

12、xxtsxxg 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，原问题无解；原问题无解；第一阶段终了时，辅助问标题的函数值等于第一阶段终了时，辅助问标题的函数值等于0，且人工变量都是非基变量，那末，所得根本可行且人工变量都是非基变量，那末，所得根本可行解为原问题初始根本可行解，去掉人工变量，目解为原问题初始根本可行解，去掉人工变量，目的函数行换为原问标题的函数，继续求解。的函数行换为原问标题的函数，继续求解。第一阶段终了时，辅助问标题的函数值等于第一阶段终了时，辅助问标题的函数值等于0，但是人工变量不都是非基变量，那么令其强行出但是人工变量不都是非基变量，那么令其强行出基，然后继续求