单纯形法求解

例：用单纯形法求解4,3,2,1,063422..3min4213214321jxxxxxxxtsxxxxzjx1x2x3x4z-3-1-1-10X3X4-2210310146RHSx1x2x3x4z-220010X3X4-2210310146RHSz00-106X2X4-111/2040-1/2124最优解X=（0，2，0，4），最优值是6。T§2.4初始解（两阶段法）问题：线性规划问题化为标准型时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？§2.4初始解（两阶段法）11221111221121122222112212minz...............................................................,,...,0nnnnnnmmmnnmncxcxcxaxaxaxbaxaxaxbaxaxaxbxxx0b第一阶段：加入人工变量,构造初始可行基.1111221112112222221122121,............................................................,,...,,...,nnnnnnmmmnnnmmnnnmaxaxaxxbaxaxaxxbaxaxaxxbxxxxx012ming...nnnmxxx用单纯形法求解,若g=0,进入第二阶段,否则,原问题无可行解。第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。1312312323123max342139,,0zxxxxxxxxxxxxx例：求解下列线性规划问题将原问题化成标准型：解:1312312323123max342139,,0zxxxxxxxxxxxxx131234123523min3421390,1,...5jzxxxxxxxxxxxxxj化标准型用两阶段方法来求解。第一阶段的线性规划问题为67123412356237min421390,1,...7jgxxxxxxxxxxxxxxxjx1x2x3x4x5x6x7g00000-1-10X4X6X71111000-21-10-1100310001419RHSx1x2x3x4x5x6x7RHSg-2400-10010X4X6X71111000-21-10-1100310001419g60403-406X4X2X730211-10-21-10-11060403-31316g00000-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/2000-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。例：求解下列线性规划问题0,3263433..4min2121212121xxxxxxxxtsxxz将原问题化成标准型：解:化标准型用两阶段方法来求解。0,3263433..4min2121212121xxxxxxxxtsxxz0,,,3263433..4min43214213212121xxxxxxxxxxxxtsxxz第一阶段的线性规划问题为x1x2x3x4x5x6RHSg0000-1-10X5X6X431001043-10011201003630,,,,,3263433..min654321421632152165xxxxxxxxxxxxxxxxtsxxgx1x2x3x4x5x6RHSg74-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/52/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所以最初的线性规划问题的最优解X=(3/5，6/5)T，最优值是18/5。例：求解下列线性规划问题0,3232..42min21212121xxxxxxtsxxz将原问题化成标准型：解:化标准型用两阶段方法来求解。0,3232..42min21212121xxxxxxtsxxz0,,,3232..42min432142132121xxxxxxxxxxtsxxz第一阶段的线性规划问题为x1x2x3x4x5x6RHSg0000-1-10X5X62-3-1010-110-101230,,,,,3232..min6543216421532165xxxxxxxxxxxxxxtsxxgx1x2x3x4x5x6RHSg1-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原问题无解。两阶段方法总结第一阶段结束时，辅助问题目标函数值大于0，原问题无解；第一阶段结束时，辅助问题目标函数值等于0，且人工变量都是非基变量，那末，所得基本可行解为原问题初始基本可行解，去掉人工变量，目标函数行换为原问题目标函数，继续求解。第一阶段结束时，辅助问题目标函数值等于0，但是人工变量不都是非基变量，那么令其强行出基，然后继续求解。小结线性规划问题图解法只有两个变量约束矩阵A中含有一个m阶的单位矩阵右端向量非负单纯形方法约束矩阵A中没有一个m阶的单位矩阵两阶段法小结(一).会用两阶段法解线性规划问题.(二).作业74页17(3)