用单纯形法求解

用单纯形法求解x1x2x3x4z-220010X3X4-2210310146RHSz00-106X2X4-111/2040-1/2124最优解X=（0，2，0，4），最优值是6。T§2.4初始解（两阶段法）问题：线性规划问题化为标准型时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？

§2.4初始解（两阶段法）第一阶段：加入人工变量,构造初始可行基.用单纯形法求解,若g=0,进入第二阶段,否则,原问题无可行解。第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。例：求解下列线性规划问题将原问题化成标准型：解:化标准型用两阶段方法来求解。第一阶段的线性规划问题为x1x2x3x4x5x6x7

g00000-1-10X4X6X71111000-21-10-1100310001419RHSx1x2x3x4x5x6x7RHSg-2400-10010X4X6X71111000-21-10-1100310001419

g60403-406X4X2X730211-10-21-10-11060403-31316g00000-1-10X4X2X10001-1/21/2-1/2011/30001/3102/301/2-1/21/6031x1x2x3x4x5x6x7

RHS得原问题的基可行解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。例：求解下列线性规划问题将原问题化成标准型：解:化标准型用两阶段方法来求解。第一阶段的线性规划问题为x1x2x3x4x5x6RHS

g0000-1-10X5X6X431001043-1001120100363x1x2x3x4x5x6RHS

g74-10009X5X6X431001043-1001120100363g05/3-10-7/302X1X6X411/3001/3005/3-10-4/3105/301-1/30122x1x2x3x4x5x6RHS

g05/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/5x1x2x3x4x5x6RHS

g0000-1-10X1X3X2100-1/52/5000111-10103/5-1/503/506/5第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。z-4-1000X1X3X2100-1/500110103/53/506/5x1x2x3x4

RHS

z000-1/518/5X1X3X2100-1/500110103/53/506/5所以最初的线性规划问题的最优解X=(3/5，6/5)T，最优值是18/5。例：求解下列线性规划问题将原问题化成标准型：解:化标准型用两阶段方法来求解。第一阶段的线性规划问题为x1x2x3x4x5x6RHS

g0000-1-10X5X62-3-1010-110-10123x1x2x3x4x5x6RHS

g1-2-1-100