《管理运筹学》02-4两阶段法和大M法.pptVIP

第二节 单纯形法 Simplex Method 一、单纯形法原理及步骤 二、用向量矩阵描述单纯形法原理 三、单纯形表 四、两阶段法和大M法 五、退化和循环 两阶段法和大M法 当不能通过转化标准形式使约束方程系数矩阵中出现单位矩阵时，此时可以通过添加人工变量的方法，人为地使系数矩阵中出现一个单位矩阵，以它作为初始可行基。 例如: 设一线性规划问题的约束为 人工变量法有两种方法：两阶段法和大M法。 引进变量X4,X5 基中不包含单位矩阵，因此无法直接获得初始可行基。 两阶段法和大M法 X=(x1,x2,…,xn)T 引进人工变量 Xa=(xn+1,xn+2,…, xn+m)T 基础可行解X=0,Xa=b 非原问题的 基础可行解 两阶段法和大M法 基本思想： 人造解 X0 不是原LP问题的基本可行解。 但若能通过单纯形法的迭代步骤，将虚拟 的人工变量都替换出去，都变为非基变量（即 人工变量xn+1 = xn+2 = … = xn+m = 0），则X0的 前n个分量就构成原LP问题的一个基本可行解。 反之，若经过迭代，不能把人工变量都变 为非基变量，则表明原LP问题无可行解。 两阶段法和大M法 两阶段法 阶段Ⅰ 求解辅助问题 构造 辅助问题 (1)若辅助问题的最优基B全部在A中，即Xa全部是非基变量（min z’=0），则B为原问题的一个可行基。转阶段Ⅱ; (2)若辅助问题的最优目标函数值min z’>0，则至少有一个人工变量留在第一阶段问题最优解的基变量中，这时原问题无可行解。 两阶段法和大M法 阶段Ⅱ 求解原问题 以阶段Ⅰ的最优基B作为原问题的初始可行基，求解原问题，得到原问题的最优基和最优解。 例1 求解以下线性规划问题。 两阶段法和大M法 引进松弛变量x3，x4，x5?0，得到 增加人工变量x6，x7≥0，构造辅助问题，并进入第一阶段求解。 两阶段法和大M法 标准化并写出辅助问题的系数矩阵表： 消去目标函数中基变量x6、x7的系数，得到初始单纯形表并进行单纯形变换： x2进基 [ ] X7离基 Cj ? 0 0 0 0 0 1 1 两阶段法和大M法 x1进基 [ ] X6离基 第一阶段最优，z’’=0 Cj ? 0 0 0 0 0 1 1 - - 两阶段法和大M法 在第一阶段最优单纯形表换入原问题的目标函数，去掉人工变量x6、x7以及相应的列，得到第二阶段的系数矩阵表： 消去基变量x1、x2在目标函数中的系数，得到第二阶段问题的单纯形表： x4进基 [ ] X1离基 Cj ? -1 2 0 0 0 两阶段法和大M法 x3进基 [ ] X5离基 问题的最优解为X=(x1,x2,x3,x4,x5)T=(0,3,1,2,0)T， max z’=6 ，即 min z=-6。 Cj ? -1 2 0 0 0 两阶段法和大M法 O A B C D 0 1 2 1 2 3 x1 x2 第一阶段：在原问题的可行域外部进行基变换，第一阶段结束后进入可行域 第二阶段：从可行域内部的的一个极点B（原问题的一个可行基）开始，在可行域内部进行基变换 基迭代路线 两阶段法和大M法 大M法的基本步骤如下： （1）引进松弛变量，使约束条件成为等式； （2）如果约束条件的系数矩阵中不存在一个单位矩阵，则引进人工变量； （3）在原目标函数中，加上人工变量，每个人工变量的系数为一个充分大的正数M； （4）用单纯形表求解以上问题，如果这个问题的最优解中有人工变量是基变量，则原问题无可行解。如果最优解中所有人工变量都离基，则得到原问题的最优解。 两阶段法和大M法 例2 求解以下线性规划问题。 引进松弛变量x4，x5并标准化 两阶段法和大M法 引进人工变量x6，x7?0，在目标函数中增加人工变量 列出系数矩阵表 两阶段法和大M法 消去基变量x6、x7在目标函数中的系数