线性规划大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问题maxz=3x1x22x33x1+2x23x3=6x12x2+x3=4x1，x2，x30,maxz=3x1x22x3,3x1+2x23x3+x4=6,Mx4,x12x2+x3+x5=4,Mx5,x1，x2，x3，x4，x50,s.t.,解,s.t.,一、大M法,cj,基,解,x1x2x3x4x5,3-1-2-M-M,比值,32-310,x4x5,64,1-2101,-M-M,10M3+4M-1-2+2M00,24,3,212/3-11/30,x1x5,3-M,20-8/32-1/31,-6+2M0-3-8M/31+2M-4M/3-10,2,3-2,x1x3,10-4/31-1/61/2,31-2/301/61/2,-70-5/30-M-5/6-M-1/2,min,X*=(3,0,1)T,z*=7,单纯形法的进一步讨论人工变量法,解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个k0且aik（i=1，2,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在人工变量时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。,11,二、两阶段法,两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划问题分两段来求解。第一阶段：要判断原线性规划问题是否存在基本可行解。第二阶段：将第一阶段的最终计算表中的人工变量取消，并将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字，继续求解，直到得到最优解。,两阶段法,阶段求解人造极大问题（先将线性规划问题化标准型，并将其约束条件中加入人工变量，得第一阶段的数学模型）maxw=-xn+1-xn+2-xn+m或者minw=xn+1+xn+2+xn+ms.t.(2.1)因为人工变量xn+1,xn+2,xn+m0所以maxw0,(1)若w*0，说明人工变量中至少有一个为正（针对maxw来说），表示原问题无可行解，停止计算；(2)若w*=0，且人工变量都变换为非基变量，说明原问题得到了初始基本可行解，转入阶段：求解原问题；,人工变量的系数均为1或-1,两阶段法,(3)若w*=0，但“基列”存在人工变量，例如该列第l行的基变量xBl是人工变量，同时该行的前n个系数alj全都是0，这说明原问题的该约束方程式多余的，那么删去第l行及xBl列，类似情况全都这样删去相应行、列；转入阶段；(4)若w*=0，且存在人工变量xBl是基变量，但该行的前n个系数中存在alk0，则以alk为主元进行一次换基运算，可使原变量xk取代人工变量xBl作为基变量，类似可将这类人工变量全部都由基变量变为非基变量；转入阶段。,阶段求解原问题将第一阶段求得的基本可行解对原问题的目标函数进行优化，将目标函数换成原目标函数，建立原问题的初始单纯形表。只需把阶段的最末单纯形表修改如下：(1)人工变量xn+1，xn+2，xn+m诸列去掉；(2)把cj行与cj列的数字换成原问题目标函数的相应系数;(3)重新计算z0和j，用以取代原检验行中相应数字。然后用单纯形法进行迭代，直到运算结束。,两阶段法,两阶段法,例用两阶段法求解下述LP问题maxz=3x1x22x33x1+2x23x3=6x12x2+x3=4x1，x2，x30,解,s.t.,s.t.,3x1+2x23x3+x4=6,x12x2+x3+x5=4,x1，x2，x3，x4，x50,maxw=x4x5,第一阶段：先将线性规划问题化标准型，并将其约束条件中加入人工变量，得第一阶段的数学模型,两阶段法,cj,基,解,x1x2x3x4x5,000-1-1,比值,32-310,x4x5,64,1-2101,-1-1,1040-200,24,3,212/3-11/30,x1x5,0-1,20-8/32-1/31,20-8/32-4/30,2,min,00,x1x3,10-4/31-1/61/2,31-2/301/61/2,0000-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,-70-5/30,单纯形法的进一步讨论人工变量