线性规划大M法或两阶段法.ppt

1,第八节 单纯形法的进一步讨论 人工变量,人工变量法,考虑标准型 (M)： 分别给每个约束方程硬性加入一个非负变量 a11x1 +a12x2+a1nxn +xn+1 = b1 (0) a12x1 +a22x2+a2nxn +xn+2 = b2 (0) am1x1+am2x2+amnxn +xn+m = bm(0),n个,xn+1, xn+2, , xn+m 称为人工变量。 初始基本可行解：( 人造基本解 ) X0 = ( 0, 0, , 0, b1, b2, , bm )T,(2.1),基本思想： 人造解 X0 不是原LP问题的基本可行解。 但若能通过单纯形法的迭代步骤，将虚拟 的人工变量都替换出去，都变为非基变量（即 人工变量xn+1 = xn+2 = = xn+m = 0），则X0的 前n个分量就构成原LP问题的一个基本可行解。 反之，若经过迭代，不能把人工变量都变 为非基变量，则表明原LP问题无可行解。,人工变量法,大M法或两阶段法,4,一、大M法,若迭代最终得到最优解X* ，而且基变量中不含有人工变量，则X*的 前n个分量就构成原问题的一个最优基本解；否则，原问题无可行解。 若迭代结果是解无界，而且基变量中不含有人工变量， 则原问题也 解无界；否则，原问题无可行解。,一、大M法,例： 用大M法解下列线性规划,解：首先将数学模型化为标准形式,系数矩阵中不存在单位矩阵，无法建立初始单纯形表。,一、大M法,故人为添加两个单位向量，得到人工变量单纯形法数学模型：,其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。,一、大M法,一、大M法,例 用大M法求解下述LP问题 max z = 3x1 x2 2x3 3x1+ 2x2 3x3 = 6 x1 2x2 + x3 = 4 x1， x2， x3 0,max z = 3x1 x2 2x3,3x1+ 2x2 3x3 +x4 = 6, Mx4,x1 2x2 + x3 + x5 = 4,Mx5,x1， x2， x3 ， x4， x5 0,s.t.,解,s.t.,一、大M法,cj,基,解,x1 x2 x3 x4 x5,3 -1 -2 - M - M,比 值,3 2 -3 1 0,x4 x5,6 4,1 -2 1 0 1,- M - M,10M 3+4M -1 -2+2M 0 0,2 4,3,2 1 2/3 -1 1/3 0,x1 x5,3 - M,2 0 -8/3 2 -1/3 1,-6+2M 0 -3-8M/3 1+2M -4M/3-1 0,2,3 -2,x1 x3,1 0 - 4/3 1 -1/6 1/2,3 1 -2/3 0 1/6 1/2,-7 0 -5/3 0 -M-5/6 -M-1/2,min,X* = ( 3, 0, 1 )T, z* = 7,单纯形法的进一步讨论人工变量法,解的判别： 1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个k 0且aik（i=1，2,m）则线性规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在人工变量时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。,11,二、两阶段法,两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划问题分两段来求解。 第一阶段：要判断原线性规划问题是否存在基本可行解。 第二阶段：将第一阶段的最终计算表中的人工变量取消，并将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字，继续求解，直到得到最优解。,两阶段法,阶段 求解人造极大问题（先将线性规划问题化标准型，并将其约束条件中加入人工变量，得第一阶段的数学模型） max w = -xn+1 -xn+2 - -xn+m 或者 min w = xn+1 +xn+2 + +xn+m s.t. ( 2.1 ) 因为人工变量 xn+1, xn+2, , xn+m 0 所以 max w 0,(1) 若w* 0，说明人工变量中至少有一个为正（针对max w来说），表示原问题无可行解，停止计算； (2) 若w* = 0，且人工变量都变换为非基变量，说明原问题得到了初始基本可行解，转入阶段： 求解原问题；,人工变量的系数均为1或-1,两阶段法,(3) 若w* = 0，但“基列”存在人工变量，例如该列第l 行的基变量xBl是人工变量，同时该行的前n个系数al j全都是0，这说明 原问题的该约束方程式多余的，那么删去第l 行及xBl列，类 似情况全都这样删去相应行、列；转入阶段； (4) 若w* = 0，且存在人工变量xBl是基变量，但该行的前n个系数 中存在al k0 ，则以al k为主元进行一次换基运算，可使原变 量xk取代人工变量xBl作为基变量，类似可将这类人工变量全 部都由基变量变为非基变量；转入阶段。,阶段 求解原问题 将第一阶段求得的基本可行解对原问题的目标函数进行优化，将目标函数换成原目标函数，建立原问题的初始单纯形表。只需把阶段的最末单纯形表修改如下： (1) 人工变量 xn+1，xn+2 ， ， xn+m诸列去掉； (2) 把cj行与cj列的数字换成原问题目标函数的相应系数; (3) 重新计算z0和j ，用以取代原检验行中相应数字。 然后用单纯形法进行迭代，直到运算结束。,两阶段法,两阶段法,例 用两阶段法求解下述LP问题 max z = 3x1 x2 2x3 3x1+ 2x2 3x3 = 6 x1 2x2 + x3 = 4 x1， x2， x3 0,解,s.t.,s.t.,3x1 +2x2 3x3 +x4 = 6,x1 2x2 + x3 + x5 = 4,x1， x2 ， x3， x4， x5 0,max w = x4 x5,第一阶段： 先将线性规划问题化标准型，并将其约束条件中加入人工变量，得第一阶段的数学模型,两阶段法,cj,基,解,x1 x2 x3 x4 x5,0 0 0 - 1 -1,比 值,3 2 -3 1 0,x4 x5,6 4,1 -2 1 0 1,-1 -1,10 4 0 - 2 0 0,2 4,3,2 1 2/3 -1 1/3 0,x1 x5,0 -1,2 0 -8/3 2 -1/3 1,2 0 -8/3 2 -4/3 0,2,min,0 0,x1 x3,1 0 - 4/3 1 -1/6 1/2,3 1 -2/3 0 1/6 1/2,0 0 0 0 -1 -1,第一阶段得最优解X* = ( 3, 0, 1 , 0, 0)T, w* = 0 因人工变量x4=x5=0，所以( 3, 0, 1 , 0, 0)T是原线性规划问题的基可行解。,两阶段法,阶段：求解原问题 将阶段一最终表中的人工变量去掉，并填入原问题的目标函数，作单纯形表,X* = ( 3, 0, 1 )T, z* = 7,3 -1 -2,3 -2,-7 0 -5