管理运筹学Chapter 2.2 单纯形法

线性规划,Chapter Two：LP,第二节 单纯形法,单纯形法原理及步骤 用向量矩阵描述单纯形法原理 单纯形表 单纯形表解题补遗总结 单纯形法进阶两阶段法和大M法,LP的标准形式 LP的解的各种概念与形式 单纯形法的原理 单纯形法求解LP问题的步骤 最终解的判别,将LP问题转化为标准形式 单纯形表格法求解LP问题,1.单纯形法原理及步骤,单纯形法思路,单纯形法原理及步骤,关键问题,Q1：初始基本可行解如何找？ 标准型 基本解 Q2：怎样判断最优？ 最优性条件 Q3：如何找下一个相邻的基本可行解？ 确定移动的方向 确定在何处停下 确定新的基本可行解,单纯形法原理及步骤,1.单纯形法原理及步骤,步骤1：确定初始基本可行解，判断其是否最优 找到一个单位矩阵作为初始基，得到相应基本可行解，确定相应的基变量、非基变量以及目标函数的值，并将目标函数和基变量分别用非基变量表示。如果目标函数的表达式中，非基变量的系数均为负数，即任何一个非基变量的增加都不能使目标函数增加，则当前基本可行解是最优解。否则，转步骤2。,1.单纯形法原理及步骤,步骤2：确定入基变量 根据目标函数用非基变量表出的表达式中非基变量的系数，选择一个非基变量，使它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量称为“进基变量”。 步骤3：确定出基变量 在基变量用非基变量表出的表达式中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量，这个基变量称为“出基变量”。当进基变量的值增加到使出基变量的值降为0时，可行解移动到相邻的极点。,1.单纯形法原理及步骤,出基变量无法确定且目标函数无限递增为无界解 如果进基变量的值增加时，所有基变量的值都不减少，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加。即该线性规划问题目标函数值无界。否则转步骤4。 步骤4：进行换基操作 将进基变量作为新的基变量，出基变量作为新的非基变量，变换约束方程系数矩阵确定新的基、新的基本可行解和新的目标函数值。返回步骤1。 重复以上步骤。,1.单纯形法原理及步骤,例：用单纯形法求解以下线性规划问题,1.单纯形法原理及步骤,首先将模型转化成标准形式,1.单纯形法原理及步骤,确定初始的基本可行解 选择单位阵作为初始基：令非基变量 x1=x2=0得：X0=(0，0，3，4)T,1.单纯形法原理及步骤,最优性检验 将目标函数用非基变量线性表示，得到z=2x1+3x2 其中，非基变量x1，x2的系数都是正数，当x1，x2增加时，目标函数增大。可以判断，当前的基本可行解不是最优解。,1.单纯形法原理及步骤,确定进基变量 x1，x2进基都可以使目标函数z增大，但x2的系数为3，绝对值比x1的系数2大，因此x2进基有可能使目标函数z增长更快。选择x2进基，使x2的值从0开始增加，另一个非基变量x1=0保持不变。,1.单纯形法原理及步骤,确定离基变量 为了保证所有变量的非负性，x2增长需要保证x2=min3/1，4/2=2（最小比值法）,1.单纯形法原理及步骤,确定新的基本可行解寻找新的基本可行解： 初等数学变换,初等数学变换,X*=（0, 2, 1, 0）,Z*=6+ x1/2- 3x4/26,原方程,非基变量x1的系数是正数！,非最优解！,新方程,第2次迭代 确定进基变量x1 确定离基变量,非基变量x4=0,确定x3为离基变量, 初等行变换,初等行变换,非基变量系数>0，最优！,Z*=7,X*=(2,1,0,0),单纯形法原理及步骤,1.单纯形法原理及步骤,例2-9目标函数无界的情况,1.单纯形法原理及步骤,首先标准化确定初始基本可行解 X0 = (0, 0, 1, 2)T z0 = 0 这个解对应原点O,1.单纯形法原理及步骤,判断最优性 将目标函数用非基变量线性表示，得到z=x1+2x2 其中，非基变量x1，x2的系数都是正数，当x1，x2增加时，目标函数增大。可以判断，当前的基本可行解不是最优解。,1.单纯形法原理及步骤,进基 x1，x2进基都可以使目标函数z增加，但x2的系数为2，绝对值比x1的系数1大，因此x2进基有可能使目标函数z增加更快。选择x2进基，使x2的值从0开始增加，另一个非基变量x1=0保持不变。 出基 x2的增长需满足 x3=1+x1-x2 0，x4=2-x2 0 由于非基变量x1=0，因此x2= min1，2=1。即当x2增加到1时，x3首先下降为0成为非基变量。新的基变量为x2，x4，新的非基变量为x1，x3。,1.单纯形法原理及步骤,对约束条件进行行变换。 -x1+x2+x3=1 x1-x3+x4=1 令x1=x3=0，则新的基本可行解 (x1，x2，x3，x4)=(0，1，0，1)，z=2，这个解对应于极点B。 最优性检验 用非基变量对目标函数线性表示，得到z=x1+2(1+x1-x3)= 2+3x1-2x3 非基变量x1的系数是正数，因此当前基本可行解不是最优解。,1.单纯形法原理及步骤,第二次迭代 选择进基变量X1，出基变量X4 新的基本可行解为： (x1，x2，x3，x4)=(1，2，0，0)，z=5。这个解对应于极点C。 目标函数用当前非基变量表出的形式： z= (1+x3-x4)+2(2-x4)= 5+x3-3x4 从目标函数的表达式看出当前基本可行解不是最优解。,1.单纯形法原理及步骤,第三次迭代 选择进基变量x3, x3的增长需满足： x1=1+x3-x40x2=2-x40 从约束条件可以看出，进基变量x3的值增加时，基变量x1的值增加，x2的值不变，因此进基变量x3的值可以无限增加，目标函数值z可以无限增加，即原问题目标函数值z可以无限减小。此时可行域不封闭，目标函数无界。,目标函数无界的线性规划问题,单纯形法原理及步骤,练习：用单纯形法求解下列线性规划问题,2.用向量矩阵描述单纯形法原理,2.用向量矩阵描述单纯形法原理,2.用向量矩阵描述单纯形法原理,2.用向量矩阵描述单纯形法原理,基于向量矩阵的单纯形法基本思路： 1)取得初始可行基B、相应的基本可行解及对应的目标函数值2)从当前的非基变量中选取一个xk ,使xk的值由当前的值0开始增加，其余非基变量的值均保持零值不变。如果任何一个非基变量的值由0增加时，目标函数都不能增加，则当前的基已经是最优基。,2.用向量矩阵描述单纯形法原理,基于向量矩阵的单纯形法基本思路： 3)当xk的值由0开始增加时，当前各基变量的值也会随之变化： (1)当xk的值增加时，某些基变量的值随之减小，则必定有一个基变量xr的值在xk的增加过程中首先降为0。这时，这个基变量xr成为非基变量，而非基变量xk进基成为基变量，相应地， xk在矩阵A中相应（不在基B中）的列向量pk将取代基变量xr在基B中的列向量pr。此时基变换后的目标函数值必定大于原目标函数值。,2.用向量矩阵描述单纯形法原理,(2)当xk的值增加时，所有基变量的值都随之增加，则不会有任何基变量出基，这时xk值的增加没有任何限制。注意到进基变量xk的选取，xk的增加使目标函数增加，此时可行域无界，即目标函数无界。 4)重复步骤(2)和(3)，就一定可以获得最优基或确定目标函数无界。,2.用向量矩阵描述单纯形法原理,单纯形法的几何意义： 从几何意义方面解释，单纯形法就是在可行域的边界上，沿着相邻的极点进行搜索的一种算法。所谓相邻的极点，就是每次只有一个变量进基，一个变量出基转换前后所对应的基本可行解。我们把这两个基本可行解所对应的两个基称为“相邻的”基。,3.单纯形表,根据单纯形法的向量矩阵描述，可得：,系 数 矩 阵,B-1,B-1,B-1,CB,CB,CB,3.单纯形表,与基B对应的单纯形表,目标函数值,基变量的目标函数系数,令,则检验数j可以记为,3.单纯形表,3.单纯形表,3.单纯形表,3.单纯形表,用单纯形表求解线性规划问题的步骤可以归纳如下： 1. 把线性规划问题化成标准形式。 2.在系数阵中找出或构造一个m阶排列矩阵作为初始可行基，建立初始单纯形表。 3.若所有检验数j0，就得到一个最优基本解，停止计算；否则转下一步。 4.在所有j<0中，只要有一个k<0所对应的系数列向量pk0，即该列向量中所有分量均小于等于0，则该线性规划问题为无界解，停止计算；否则转下一步。,3.单纯形表,5.按最小检验数规则minj|j<0=k确定进基变量xk和主列pk；再按最小比值规则确定主元ark，同时也确定xr是出基变量。 6.以ark为主元进行行变换，使得单纯形表中： （1）进基变量xk在目标函数中的系数为0； （2）约束条件中主元ark1，主元所在列的其他元素为0。 转第1步。 反复进行以上步骤，直至获得最优解或确定目标函数无界。,3.单纯形表,例2-10,3.单纯形表,X*=(2,1,0,0), Z*=7,3.单纯形表,例2-11,3.单纯形表,由于存在检验数-1所对应的系数列向量均小于等于0，所以该线性规划模型为无界解,3.单纯形表,例2-12,3.单纯形表,标准化,3.单纯形表,3.单纯形表,多重最优解的问题 在最优单纯形表中，若有一个或更多个非基变量的检验数为零，则该LP问题有无穷多个最优解 若上述非基变量在该表中的系数列向量非零，则按单纯形法另作迭代，让该非基变量进基，可得到其他最优解 若LP问题有r个（r2）最优极点解，则该LP问题有无穷多个最优解（不一定是极点解），且其中任意最优解都能表示成这r个最优极点解的凸组合,3.单纯形表,最优解X1=(0,1,0,1)T，z=2,最优解X2=(1,2,0,0)T，z=2,最优解X=X1+(1-) X2=(1-,2-,0, )T，(01),3.单纯形表,例2-13,3.单纯形表,3.单纯形表,3.单纯形表,3.单纯形表,进基变量的相持及其突破 出现多个j<0同时达到最小而相持不下的情况 解决办法：任选一个对应的基变量 效果：结果相同，迭代次数不同且不可预知 离基变量的相持及其突破 出现多个比值同时最小 解决办法：摄动法、辞典序法、Bland法。 摄动法的方案是：从相持的离基变量中选择下标最大者离基。 Bland法的方案是：从相持的离基变量中选择下标最小者离基。 效果：导致一个退化的基本可行解 现实意义：模型中存在多余的约束,3.单纯形表,单纯形算法流程图,3.单纯形表,3.单纯形表,例2-13,X*=(1,3/2,0,0), Z*=35/2,3.单纯形表,例2-14,最优解为x=（0，3，9，0，0，12）， max z=15,4.单纯形表解题补遗总结,4.单纯形表解题补遗总结,定义2-6 设B是线性规划的一个可行基，XB=B-1b=(xB1,xB2,xBi,xBm)T是这个基本解中的基变量。如果其中至少有一个分量xBi=0(i=1,2,m)，则称此基本可行解是退化的。,4.单纯形表解题补遗总结,退化的结构对单纯形迭代会有不利的影响。当迭代进入一个退化极点时，可能出现以下情况(1)进行进基、离基变换后，虽然改变了基，但没有改变极点，目标函数当然也不会改进。进行若干次基变换后，才脱离退化极点，进入其他极点。这种情况会增加叠代次数，使单纯形法收敛的速度减慢。 (2)在十分特殊的情况下，退化会出现基的循环，一旦出现这样的情况，单纯形叠代将永远停留在同一极点上，因而无法求得最优解。,4.单纯形表解题补遗总结,尽管如此，人们还是对如何防止出现循环作了大量研究。 1952年Charnes提出了“摄动法” 1954年Dantzig，Orden和Wolfe又提出了“字典序法”,4.单纯形表解题补遗总结,对此，Bland提出了一个避免循环的方法，在选择进基变量和离基变量时作了以下规定： （1）在选择进基变量时，在所有检验数zj-cj<0的非基变量中选取下标最小的进基； （2）当有多个变量同时可作为离基变量时，选择下标最小的那个变量离基。这样就可以避免出现循环。 当然，用Bland的方法，由于选取进基变量时不再考虑检验数zj-cj绝对值的大小，将会导致收敛速度的降低。,