运筹学-运筹学第3讲 线性规划2-精品文档整理.ppt
线性规划解的概念线性规划解的概念 基(矩阵)： 假设A为m*n阶矩阵，A的秩为m（即A为行满秩矩阵） 等价定义：B为A的m个线性无关的列向量构成的m阶方阵，则称B是线性规划问题的一个基，也称基矩阵。11121212221212A0,(1,2,)(1,2,)mmmmmmmjjBm mBBBaaaaaaBP PPaaaBP jmxjmnm是系数矩阵 中的阶子矩阵，若 非奇异，称 为线性规划问题的基。基矩阵 中所对应的向量，为基向量，为基变量，其余个向量称为非基变量。 线性规划解的概念线性规划解的概念 基本解：对于取定的一个基B，在约束方程组中令非基变量取零值，可以得到方程组的一个确定的解，称这个解为基本解。 基可行解：当基本解的所有分量均非负时，称之为基本可行集。 可行基：基可行解对应的基称为可行基。 最优基：最优解对应的基称为最优基。 线性规划解的概念线性规划解的概念 一个基矩阵对应一个基本解，由于基矩阵的个数是有限的，所以基本解的个数也是有限的，当然，基可行解的个数更是有限的，最多为 个。 几个解之间的关系：mnC非可行解非可行解可可行行解解基解基解基可行解基可行解线性规划问题的几何意义线性规划问题的几何意义关于线性规划问题的几个定理：定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。定理3：若问题存在最优解，该最优解一定在某个顶点取得。 以上证明过程见P24-27. 单纯形法单纯形法 单纯形法的基本步骤： 单纯形法单纯形法 单纯形法的基本步骤：(1)确定初始的基本可行解X1；1、 假设在约束系数矩阵中含有单位阵并且bi 0， i=1,2,m，则令单位阵所在列对应的变量为基变量，其他变量为非基变量，并令非基变量取零值，可得到初始基本可行解。2、对于所有行约束条件为“”不等式，在每行引入松弛变量化为标准形后，所有松弛变量的系数矩阵正好为单位矩阵。3、对于所有行约束条件为“”不等式及化为标准形后系数矩阵中不含有单位阵时，确定初始基本可行解的方法可采用人工变量法。（后面再讨论）- 首先假设系数矩阵含单位阵的情况。 单纯形法单纯形法 单纯形法的基本步骤：(2) 确定最优性判别准则；设线性规划问题(LP)约束系数矩阵中的前m列为一个单位阵，其模型有如下形式，其中bi 0，i=1,2,m。max z = c1 x1 + c2 x2 + + cn xn s. t. x1 + a1m+1 x m+1 + + a1n xn = b1 x2 + a2m+1 x m+1 + + a2n xn = b2 xm + amm+1 x m+1 + + amn xn= bm x1 ，x2 ， ，xn 0. 单纯形法单纯形法 单纯形法的基本步骤：取x1，xm为基变量，xm+1，xn为非基变量。基本解为X1=（b1，b2，bm，0，0）T。 x1 = b1-（a1m+1 x m+1 + + a1n xn） x2 = b2-（a2m+1 x m+1 + + a2n xn） xm = bm-（ amm+1 x m+1 + + amn xn）代入目标函数中： Z= c1 x1 + c2 x2 + + cn xn 单纯形法单纯形法 单纯形法的基本步骤：111111111111()() mniijjij mmnniiijjjjij mj mmmnni iiimjiijjjjiij mj mmni ijij mjic xc xc ba xc xcbca xc xxccacb记得到目标函数由当前解X1的非基变量的线性表示：111,1,mmjjiijii iiccZcbjman11jjnj mZxZ其中Z1即为X1对应的目标函数值。 单纯形法单纯形法 单纯形法的基本步骤：将上面结果整理后，可得到与原线性规划等价的模型111max,1,2,0,1,2,njjj mniijjij mjZZxxa xb imxjn定义：称此等价模型为基本可行解X1对应的典式。 单纯形法单纯形法 单纯形法的基本步骤：定理4：设X1 =（b1，b2，bm，0，0）T为线性规划(LP) 的基可行解，如果在其对应的典式中则X1为最优解。注：此定理就是单纯形法中的最优性判别准则。0,1,jjmn 单纯形法单纯形法 单纯形法的基本步骤：注：典式中的 称为基可行解的检验数，确切地说，是X1的非基变量的检验数。 为了统一起见，对X1的基变量也规定检验数 ，显然，应有 (因为典式中不含基变量，实际通过公式计算也为零) ，即基变量的检验数为零。,1,jjmn,1,2,jjm0,1,2,jjm 单纯形法单纯形法例3.1试判断 是否为最优解。1(6,2,15,0,0)TX 12345145245345max2266262150,1,2,5jZxxxxxxxxxxxxxxxj 100160101 100162A( )3r A 1233123( ,),BP P PIx x x为基矩阵，故为基变量。解: X1=(6,2,15,0,0)T 可知，x4,x5为非基变量， Z= -(6-x4-6x5)+(2+ x4-x5)+2(15- 6x4-2x5)+2x4+x5 =26-8x4+2x5由此可知 其中 不满足最优性准则，因此不能判断X1为最优解。451238,2,0 520 单纯形法单纯形法 单纯形法的基本步骤：(3) 确定无最优解判别准则；定理5 设X1为线性规划问题的基本可行解，如果在X1对应的典式中存在检验数 ，并且 的约束系数 皆小于等于零，则该线性规划问题的目标函数在可行域上没有上界，即没有最优解（无界解）。0kkx12,kkm kaaa例 3.2 判断下面的问题是否没有最优解。1231234135max233560,1,2,5jZxxxxxxxxxxxj 单纯形法单纯形法解: 取 为基本可行解，对于X1此模型已经为典式形式。其中检验数 ，并且 皆小于等于零，由定理判断无最优解。怎么理解？1(0,0,0,5,6)TX 33013233,1aa 分析：由约束条件可知，对于x3取任何非负值，此问题都存在可行解 目标函数值为 1(0,0,53,6)TXMMM3ZM故而可知当M逐渐增大时，Z也相应增大，因此Z无最大值。 单纯形法单纯形法 单纯形法的基本步骤：(3) 基本可行解的迭代； 定义: 根据已有的基可行解求新的基可行解称为迭代。 定义: 将原基可行解X1中的某个非基变量变为基变量，称为换入变量；将X1的某个基变量变为非基变量，称为换出变量。 单纯形法单纯形法迭代方法: 设 为基变量，由X1 的典式形式的目标函数的表达式可知其中Z1为X1对应的目标函数值。若存在 ，则需选出一个非基变量作为换入变量。一般情况下选择 中较大者所对应的非基变量为换入变量。11212( ,0,0) , ,TmmXb bbx xx111mmkknnZZxxx0k0k11111122112211mmn nmmn nmmmmmn nmxaxa xbxaxa xbxaxa xb 为了确定换出变量，首先在典式的约束中，令除xk以外的其余非基变量仍取零值，得到:111222kkkkmmkkmxa xbxa xbxaxb 根据这个关系式，又考虑到每个决策变量的可行性，从而选取xk，使其满足如下的关系式:0,1,2,iiikkxba xim 单纯形法单纯形法 当 时，因为bi 非负，故只需要 即可; 当 时，则需 。 综合上面两种情况，因此，应使 xk 满足0ika 0ika /kiikxba0kx min|0ilikiiklkbbaaa0llllkllklkbxbabaa即基变量 xl 成为换出变量。 单纯形法单纯形法 定义: 一般称 为最小比值规则，或称为 规划，其中 称为主元。min|0ilikiiklkbbaaalka现将基本可行解的迭代过程归纳如下：(1)取 对应的xk为进基变量。(2)按最小比值规则确定xk的值，并确定出基变量。(3)按右式确定新的基本可行解。max|0kjj 单纯形法单纯形法 单纯形法的求解过程，实际上是在一系列表格上进行的。从这些表格上可以得到基本解、检验数等信息，这些表格称为单纯形表。每一个单纯形表相当于一个矩阵，每次迭代就是对矩阵进行初等行变换。例3.5 求解下面的线性规划问题234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxj 单纯形法单纯形法解: 单纯形表的主要步骤1：构造初始单纯形表；234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxj构造初始单纯形表234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxjcj02-210CBXBbx1x2x3x4x50 x15111001x4601-4100 x52402601cj-zj0 1200iCB表示基变量的价值系数，XB表示当前基变量，b表示当前基变量的取值，cj行为基变量的价值系数， 为待填入的按最小比值规则计算的值。i 单纯形法单纯形法解: 单纯形表的主要步骤2：迭代求新的基本可行解及其检验数；234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxjcj02-210CBXBbx1x2x3x4x50 x151110051x4601-410-0 x524026014cj-zj0 1200i 单纯形法单纯形法解: 单纯形表的主要步骤2：迭代求新的基本可行解及其检验数；234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxjcj02-210CBXBbx1x2x3x4x50 x1112/300-1/63/21x42207/3012/366/7-2x3401/3101/612cj-zj0 1/300-1/3i 单纯形法单纯形法解: 单纯形表的主要步骤3：继续迭代；234123234235max2254626240,1,2,5jZxxxxxxxxxxxxxjcj02-210CBXBbx1x2x3x4x52x23/23/2100-1/41x437/2-7/20015/4-2x37/2-1/20101/4cj-zj-1/2 000-1/4i 此表格中全部检验数均小于等于零，故得到最优解 X*=(0,3/2,7/2,37/2,0)T,其对应的目标函数值为29/2。最优单纯形表最优单纯形表 单纯形法单纯形法例3.5 用单纯形法求解23512352342356max323272412438100,1,2,6jZxxxxxxxxxxxxxxxj 单纯形法单纯形法cj0-130-20CBXBbx1x2x3x4x5x60 x1713-102070 x4120-2410030 x6100-4308110/3cj-zj00 -130-20i 单纯形法单纯形法cj0-130-20CBXBbx1x2x3x4x5x60 x11015/201/4203x330-1/211/4000 x610-5/20-3/481cj-zj-901/20-3/4-20i 单纯形法单纯形法cj0-130-20CBXBbx1x2x3x4x5x6-1x245/2101/104/503x351/5013/102/500 x611100-1/2101cj-zj-11 -1/500-4/5-12/50i由上表得知，最优解为X*=(0,4,5,0,0,11)T,最优值为11。 单纯形法单纯形法小结： 线性规划标准形的几种表示形式(习惯矩阵和向量表示); 几个基本概念(基矩阵，基本解，基本可行解); 几何意义中的重要结论(凸集、基本可行解的含义); 单纯形法的主要思路; 单纯形法中检验数的确定以及最优性判别准则。 单纯形法的主要步骤及单纯形表。
