单纯形法求解.ppt

《单纯形法求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、例：用单纯形法求解x1x2x3x4z-3-1-1-10X3X4-2210310146RHSx1x2x3x4z-220010X3X4-2210310146RHSz00-106X2X4-111/2040-1/2124最优解X=（0，2，0，4），最优值是6。T§2.4初始解（两阶段法）问题：线性规划问题化为标准型时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？§2.4初始解（两阶段法）第一阶段：加入人工变量,构造初始可行基.用单纯形法求解,若g=0,进入第二阶段,否则,原问题无可行解。第二

2、阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。例：求解下列线性规划问题将原问题化成标准型：解:化标准型用两阶段方法来求解。第一阶段的线性规划问题为x1x2x3x4x5x6x7g00000-1-10X4X6X71111000-21-10-1100310001419RHSx1x2x3x4x5x6x7RHSg-2400-10010X4X6X71111000-21-10-1100310001419g60403-406X4X2X730211-10-21-10-11060403-31316g00000

3、-1-10X4X2X10001-1/21/2-1/2011/30001/3102/301/2-1/21/6031x1x2x3x4x5x6x7RHS得原问题的基可行解X=(1,3,0,0,0,)T。第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。Z-301000X4X2X10001-1/2011/300102/301/2031x1x2x3x4x5RHSZ00303/23X4X2X10001-1/2011/300102/301/2031Z-9/200

4、0-3/4-3/2X4X2X30001-1/2-1/2100-1/43/20103/405/23/2x1x2x3x4x5RHS得原标准线性规划问题的最优解X=（0，5/2，3/2，0，0）T，最优值是-3/2。所以最初的线性规划问题的最优解X=（0，5/2，3/2）T，最优值是3/2。例：求解下列线性规划问题将原问题化成标准型：解:化标准型用两阶段方法来求解。第一阶段的线性规划问题为x1x2x3x4x5x6RHSg0000-1-10X5X6X431001043-1001120100363x1x2x3

5、x4x5x6RHSg74-10009X5X6X431001043-1001120100363g05/3-10-7/302X1X6X411/3001/3005/3-10-4/3105/301-1/30122x1x2x3x4x5x6RHSg05/3-10-7/302X1X6X411/3001/3005/3-10-4/3105/301-1/30122g00-1-1-200X1X6X2100-1/52/5000-1-1-110103/5-1/503/506/5g00-1-1-200X1X6X2100-1/5

6、2/5000-1-1-110103/5-1/503/506/5x1x2x3x4x5x6RHSg0000-1-10X1X3X2100-1/52/5000111-10103/5-1/503/506/5第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。z-4-1000X1X3X2100-1/500110103/53/506/5x1x2x3x4RHSz000-1/518/5X1X3X2100-1/500110103/53/506/5所以最初的线性规划问题的

7、最优解X=(3/5，6/5)T，最优值是18/5。例：求解下列线性规划问题将原问题化成标准型：解:化标准型用两阶段方法来求解。第一阶段的线性规划问题为x1x2x3x4x5x6RHSg0000-1-10X5X62-3-1010-110-10123x1x2x3x4x5x6RHSg1-2-1-1005X5X62-3-1010-110-10123g0-1/2-1/2-1-1/204X1X61-3/2-1/201/200-1/2-1/2-11/2114原问题无解。两阶段方法总结第一阶段结束时，辅助问题目标函数

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