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

《《管理运筹学》02-4两阶段法和大m法.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》02-4两阶段法和大m法.ppt（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二节第二节 单纯形法单纯形法Simplex Method一、单纯形法原理及步骤一、单纯形法原理及步骤二、用向量矩阵描述单纯形法原理二、用向量矩阵描述单纯形法原理三、单纯形表三、单纯形表四、四、两阶段法和大两阶段法和大M法法五、退化和循环五、退化和循环两阶段法和大两阶段法和大M M法法当不能通过转化标准形式使约束方程系数矩阵中出现单位矩阵时，此时可以通过添加人工变量添加人工变量的方法，人为地使系数矩阵中出现一个单位矩阵，以它作为初始可行基。例如例如:设一线性规划问题的约束为设一线性规划问题的约束为人工变量法有两种方法：两阶段法和大两阶段法和大M法法。引进变量X4,X5基中不包含单位矩阵，因此无

2、法直接获得初始可行基。基中不包含单位矩阵，因此无法直接获得初始可行基。两阶段法和大两阶段法和大M M法法X=(x1,x2,xn)T引进人工变量Xa=(xn+1,xn+2,xn+m)T基础可行解X=0,Xa=b非原问题的基础可行解两阶段法和大两阶段法和大M M法法 基本思想：基本思想：基本思想：基本思想：人造解人造解 X0 不是原不是原LPLP问题的基本可行解。问题的基本可行解。但若能通过单纯形法的迭代步骤，将虚拟但若能通过单纯形法的迭代步骤，将虚拟 的人工变量都替换出去，都变为非基变量（即的人工变量都替换出去，都变为非基变量（即 人工变量人工变量xn+1=xn+2=xn+m=0），则），则X0

3、的的 前前n个分量就构成原个分量就构成原LPLP问题的一个基本可行解。问题的一个基本可行解。反之，若经过迭代，不能把人工变量都变反之，若经过迭代，不能把人工变量都变 为非基变量，则表明原为非基变量，则表明原LPLP问题问题无可行解无可行解。两阶段法和大两阶段法和大M M法法两阶段法两阶段法 阶段阶段 求解求解辅助问题辅助问题 构造辅助问题 (1)若辅助问题的最优基B全部在A中，即Xa全部是非基变量（min z=0），则B为原问题的一个可行基。转阶段;(2)若辅助问题的最优目标函数值min z0，则至少有一个人工变量留在第一阶段问题最优解的基变量中，这时原问题无可行解。两阶段法和大两阶段法和大M

4、 M法法 阶段阶段 求解求解原问题原问题 以阶段的最优基B作为原问题的初始可行基，求解原问题，得到原问题的最优基和最优解。例1 求解以下线性规划问题。两阶段法和大两阶段法和大M M法法引进松弛变量x3，x4，x50，得到增加人工变量x6，x70，构造辅助问题，并进入第一阶段求解。两阶段法和大两阶段法和大M M法法标准化并写出辅助问题的系数矩阵表：消去目标函数中基变量x6、x7的系数，得到初始单纯形表并进行单纯形变换：x2进基 X7离基Cj 0 0 0 0 0 1 1两阶段法和大两阶段法和大M M法法x1进基 X6离基第一阶段最优，z=0Cj 0 0 0 0 0 1 1-两阶段法和大两阶段法和大

5、M M法法在第一阶段最优单纯形表换入原问题的目标函数，去掉人工变量x6、x7以及相应的列，得到第二阶段的系数矩阵表：消去基变量x1、x2在目标函数中的系数，得到第二阶段问题的单纯形表：x4进基 X1离基Cj -1 2 0 0 0两阶段法和大两阶段法和大M 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 M法法OABCD012123x1x2 第一阶段：在原问题的可行域外部进行基变换，第一阶段结束后进入可行域 第二阶段：从可行域内部的的一个极点B（原问题

6、的一个可行基）开始，在可行域内部进行基变换基迭代路线基迭代路线两阶段法和大两阶段法和大M M法法 大大M法法的基本步骤如下：（1）引进松弛变量，使约束条件成为等式；（2）如果约束条件的系数矩阵中不存在一个单位矩阵，则引进人工变量；（3）在原目标函数中，加上人工变量，每个人工变量的系数为一个充分大的正数M；（4）用单纯形表求解以上问题，如果这个问题的最优解中有人工变量是基变量，则原问题无可行解。如果最优解中所有人工变量都离基，则得到原问题的最优解。两阶段法和大两阶段法和大M M法法例2 求解以下线性规划问题。引进松弛变量x4，x5并标准化两阶段法和大两阶段法和大M M法法引进人工变量x6，x70

7、，在目标函数中增加人工变量列出系数矩阵表两阶段法和大两阶段法和大M M法法消去基变量x6、x7在目标函数中的系数x1进基 X6离基x3进基 X7离基Cj -2 -3 -1 0 0 -M -M两阶段法和大两阶段法和大M M法法已获得最优解，最优解为：（x1，x2，x3，x4，x5，x6，x7）(8，0，16，0，0，0，0)，max z=-32，即min z=32Cj -2 -3 -1 0 0 -M -M退化和循环退化和循环定义定义2-6 设B是线性规划的一个可行基，XB=B-1b=(xB1,xB2,xBi,xBm)T 是这个基础解中的基变量。如果其中至少有一个分量xBi=0(i=1,2,m)，

8、则称此基础可行解是退化的。退化的结构对单纯形迭代会有不利的影响。当迭代进入一个退化极点时，可能出现以下情况：(1)进行进基、离基变换后，虽然改变了基，但没有改变极点，目标函数当然也不会改进。进行若干次基变换后，才脱离退化极点，进入其他极点。这种情况会增加叠代次数，使单纯形法收敛的速度减慢。(2)在十分特殊的情况下，退化会出现基的循环，一旦出现这样的情况，单纯形叠代将永远停留在同一极点上，因而无法求得最优解。退化和循环退化和循环 对此，Bland提出了一个避免循环的方法，在选择进基变量和离基变量时作了以下规定：（1）在选择进基变量时，在所有检验数zj-cj0的非基变量中选取下标最小的进基；（2）当有多个变量同时可作为离基变量时，选择下标最小的那个变量离基。这样就可以避免出现循环。当然，用Bland的方法，由于选取进基变量时不再考虑检验数zj-cj绝对值的大小，将会导致收敛速度的降低。LP的标准形式LP的解的各种概念与形式单纯形法的原理单纯形法求解LP问题的步骤最终解的判别需要具备的技能：需要具备的技能：将LP问题转化为标准形式单纯形表格法求解LP问题第二节第二节 单纯形法单纯形法 总结总结下周见！