用单纯形法求解.ppt

例：用单纯形法求解,x1 x2 x3 x4,RHS,x1 x2 x3 x4,RHS,§2.4 初始解（两阶段法）,问题：线性规划 问题化为标准型时， 若约束条件的系数 矩阵中不存在单位 矩阵，如何构造 初始可行基？,§2.4 初始解（两阶段法）,第一阶段：加入人工变量,构造初始可行基.,用单纯形法求解,若g=0, 进入第二阶段,否则,原问 题无可行解。 第二阶段：去掉人工变量，还原目标函数系数，做 出初始单纯形表。,例：求解下列线性规划问题,将原问题化成标准型：,解:,用两阶段方法来求解。,第一阶段的线性规划问题为,x1 x2 x3 x4 x5 x6 x7,RHS,x1 x2 x3 x4 x5 x6 x7 RHS,x1 x2 x3 x4 x5 x6 x7 RHS,得原问题的基可行解X=(1,3,0,0,0,)T。,第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。,x1 x2 x3 x4 x5 RHS,x1 x2 x3 x4 x5 RHS,得原标准线性规划问题的最优解X=（0，5/2，3/2，0，0）T，最优值是-3/2。 所以最初的线性规划问题的最优解X=（0，5/2，3/2）T，最优值是3/2。,例：求解下列线性规划问题,将原问题化成标准型：,解:,用两阶段方法来求解。,第一阶段的线性规划问题为,x1 x2 x3 x4 x5 x6 RHS,x1 x2 x3 x4 x5 x6 RHS,x1 x2 x3 x4 x5 x6 RHS,x1 x2 x3 x4 x5 x6 RHS,第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。,x1 x2 x3 x4 RHS,所以最初的线性规划问题的最优解X=(3/5，6/5)T， 最优值是18/5。,例：求解下列线性规划问题,将原问题化成标准型：,解:,用两阶段方法来求解。,第一阶段的线性规划问题为,x1 x2 x3 x4 x5 x6 RHS,x1 x2 x3 x4 x5 x6 RHS,原问题无解。,两阶段方法总结,第一阶段结束时，辅助问题目标函数值大于0，原问题无解； 第一阶段结束时，辅助问题目标函数值等于0，且人工变量都是非基变量，那末，所得基本可行解为原问题初始基本可行解，去掉人工变量，目标函数行换为原问题目标函数，继续求解。 第一阶段结束时，辅助问题目标函数值等于0，但是人工变量不都是非基变量，那么令其强行出基，然后继续求解。,小 结,线性规划问题,图解法,只有两个变量,约束矩阵A中含有一个m阶的单位矩阵,右端向量非负,单纯形方法,约束矩阵A中没有一个m阶的单位矩阵,两阶段法,小结,(一). 会用两阶段法解线性规划问题.,(二). 作业 74页 17(3),