运筹学-单纯形法PPT幻灯片课件.ppt

第五章单纯形法,1.线性规划问题的解2单纯形法3求初始基的人工变量法,1,1.线性规划问题的解,(1)解的基本概念,定义在线性规划问题中，约束方程组(2)的系数矩阵A(假定)的任意一个阶的非奇异(可逆)的子方阵B(即)，称为线性规划问题的一个基阵或基。,2,基阵,非基阵,基向量,非基向量,基变量,非基变量,3,令,则,定义在约束方程组(2)中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。,4,定义在基本解中，若该基本解满足非负约束，即，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。,定义在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为非退化解，如果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题；若基本可行解中，有基变量为零，则称为退化解，该问题称为退化的线性规划问题。,基本解中最多有m个非零分量。,基本解的数目不超过个。,5,非可行解,解的集合：,可行解,基本解,最优解,基本可行解,解空间,6,(2)解的基本性质,判别可行解为基可行解的准则,定理1线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关.,线性规划问题的基本定理:定理2和定理3,定理2线性规划问题有可行解,则它必有基可行解.,定理3若线性规划问题有最优解,则一定存在一个基可行解是它的最优解.,7,几点结论,若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过个.,上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.,8,2单纯形法,例1,(1)单纯形法的引入,9,解：(1)、确定初始可行解,B=(P3P4P5)=I,令X1=X2=0,X(1)=(0,0,30,60,24)TZ(1)=0,10,(2)、判定解是否最优,Z=0+40X1+50X2当X1从0或X2从0Z从0,X(1)不是最优解,11,(3)、由一个基可行解另一个基可行解。,5040选X2从0，X1=0,X2=min(30/2,60/2,24/2)=12X2：进基变量，X5：出基变量。,12,B2=(P3P4P2),13,1/2，代入式，,令X1=X5=0X(2)=(0,12,6,36,0)TZ(2)=600,14,(2)判断,400X(2)不是最优解。,(3)选X1从0，X5=0,X1=min(6/1,36/3,aik(i=1,2,m)不全小于或等于零，即至少有一个aik0(1km);bi0(I=1,2,m),即X(0)为非退化的基可行解。则从X(0)出发，一定能找到一个新的基可行解X(1)，使得CX(1)CX(0)。,25,(5)单纯形表,将线性规划问题典式中各变量及系数填写在一张表格中，该表即为单纯形表。,26,单纯形方法的矩阵表示,27,对应I式的单纯形表I表(初始单纯形表),对应B式的单纯形表B表,迭代,当CN-CBB-1N0时，即为最优单纯形表,28,(1)、确定初始基域初始基本可行解,列出初始单纯形表,(3)、若有j0，Pj全0，停止，没有有限最优解；否则转(4),(2)、对应于非基变量检验数j全小于零。若是，停止，得到最优解；若否，转(3)。,(6)单纯形法的迭代步骤,29,定Xr为出基变量，arm+k为主元。,由最小比值法求：,Maxj=m+kXm+k进基变量,j0,(4)、,30,转(2),(5)、以arm+k为中心，换基迭代,从步骤(2)-(5)的每一个循环，称为一次单纯形迭代.,31,单纯形表计算步骤举例给定线性规划问题,32,初始基,最优单纯形表,B-1,初始基可行解,最优值,初始单纯形表,唯一最优解,33,例2,34,35,达到最优状态时，若存在非基变量为零，则为有无穷多最优解,36,例3,37,可以为零,38,例4,例5,无法获得初始基和初始基可行解,39,3求初始基的人工变量法,求解线性规划问题的单纯形法第一步就是要找到一个初始可行基并求出初始基可行解，以它作为迭代的起点。获得初始可行基及初始基可行解的途径主要有：(1)试算法；(2)人工变量法。在约束方程组中的每一个没有单位向量的约束方程中人为加入一个变量，使系数矩阵中凑成一个单位方阵，以形成一个初始可行基阵。,40,约束条件：a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2.am1x1+am2x2+amnxn+xn+m=bmx1，x2，xn,xn+1,xn+m0,s.t,人工变量,人工基,41,等价否？,42,大M法,两阶段法,43,大M法与二阶段法的一些说明由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。大M法实质上与原单纯型法一样，M可看成一个很大的常数人工变量被迭代出去后就不会再成为基变量当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解大M法手算很不方便，因此提出了二阶段法计算机中常用大M法二阶段法手算可能容易,44,例6,大M法,45,46,最优解,人工变量被迭代出去后就不会再成为基变量,47,例4,48,未达到最优状态，但无法继续改进，即无有限最优解,49,例5,已达到最优状态，但基变量中的人工变量未退出，故无可行解,50,例6,(2)两阶段法,51,第一阶段,52,获