线性规划课件

1、1.1 线性规划问题及其数学模型线性规划问题及其数学模型 1.1.1 问题的提出 1.1.2 图解法 1.1.3 线性规划问题的标准型1.2 线性规划问题的求解线性规划问题的求解单纯形法单纯形法 1.2.1 基本概念 1.2.2 单纯形法线性规划线性规划1.1 线性规划问题及其数学模型 1.1.1 问题的提出（一）问题的提出（一） 例 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。 该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排生产计划能使该厂获利最多？ 这个问题可以用下面的数学模型来描述，设计划期内产品、的产量分别为x

2、1，x2，可获利润用z表示，则有：Max Z=2x1+3x2x1+2x284x1 16 4x212x1, x20 1.1.1 问题的提出问题的提出(二二) 例例 靠近某河流有两个化工厂，靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天流经第一化工厂的河流流量为每天500万万m3，两工厂之间有一条流量，两工厂之间有一条流量为每天为每天200万万m3的支流（见图）。的支流（见图）。 第一化工厂每天排放污水第一化工厂每天排放污水2万万m3，第二化工厂每天排放污水第二化工厂每天排放污水 1.4万万m3。污水从工厂污水从工厂1流到工厂流到工厂2前会有前会有20%自然净化。根据环保要求，河水中自然净

3、化。根据环保要求，河水中污水的含量应不大于污水的含量应不大于0.2%。而工。而工厂厂1和工厂和工厂2处理污水的成本分别为处理污水的成本分别为1000元元/万万m3和和800元元/万万m3。问两。问两工厂各应处理多少污水才能使处理工厂各应处理多少污水才能使处理污水的总费用最低？污水的总费用最低？ 设工厂设工厂1和工厂和工厂2每天分别处理污水每天分别处理污水x1和和x2万万m3，则有，则有：Min z=1000 x1+800 x2 (2-x1)/500 0.0020.8(2-x1)+1.4-x2/700 0.002 x12, x21.4 x1, x20 1.1.1 问题的提出问题的提出(三三) 以

4、上两例都有一些共同的特征：用一组变量表示某个方案，一般这些变量取值是非负的。存在一定的约束条件，可以用线性等式或线性不等式来表示。都有一个要达到的目标，可以用决策变量的线性函数来表示。 满足以上条件的数学模型称为线性规划模型。线性规划模型的一般形式如下：0,),(),(),(max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz唯一最优解无穷多最优解x1x2x1x2 解无界无可行解 线性规划问题如果有最优解,则最优解一定在可行域的边界上取得,特别地,一定可在可行域的顶点上取得.1.1.2图解法

5、图解法1212121223284164120max. .,zxxs txxxxx x1.1.3 1.1.3 线性规划问题的标准型线性规划问题的标准型线性规划问题的标准型max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1, x2, , xn0其中，bi0 (i=1,2,m)(*)或者更简洁的，利用矩阵与向量记为0max. .TzC xs tAxbx其中C和x为n维列向量，b为m维列向量，b0,A为mn矩阵，mm),b为m维列向量，b0，记R为可行域。 则x为R的极点的充分必要

6、条件为 是 的基本可行解（极点的代数定义）。定理定理2 （线性规划基本定理） （1）若可行域R 则R必有基本可行解 （2）若线性规划存在一个最优解，则必存在一个最优的 基本可行解。0Axbx定理2说明，只要线性规划（*）具有有限最优解，就必定可在基本可行解中找到。x1.2 线性规划问题的求解线性规划问题的求解单纯形法单纯形法 1.2.2 单纯形法单纯形法(一一) 要找到线性规划问题的最优解，只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个（不超过Cnm个），但当m,n较大时，要用“穷举法”求出所有基本可行解也是行不通的。因此，必须寻求一种更有效的方法。 单纯形法的基本思路是：从线性

7、规划问题的一个基本可行解开始，转换到另一个使目标函数值增大的基本可行解。反复迭代，直到目标函数值达到最大时，就得到了最优解。设B为一组非退化的可行基，x =(B b,0) 为其对应的基本可行解。现在，我们来讨论如何判别x 是否为最优解。为此，考察任一可行解 x= 。由Ax=b 可得xB=B b- B NxN代入目标函数，得到-100XBXN-1-11101()()TTTTTBBNNBNBNTTTNBNzC xC xC B bCC B N xC xCC B N x令1TTNNBCC B N 于是我们得到如下最优性判别定理定理定理3（1）若 则 必为（*）的一个最优解。（2）若 则当B为非退化可行

8、基时， 必非最优解。0N 0 x0,jjN 0 x证证（1）显然（2）不妨设 仍令 由非退化假设根据 可知， 当 且充分小时，仍有 。此时 对应的x仍为可行解，而其目标函数值 故 必非最优解。000,jjNjj 且0jx 11BNxB bB Nx00jx0Bx 11000TTTTBjjBzC xC B bxC B bC x 0 x定理定理3不仅给出了判别一个基本可行解是否为最优解的准则，而不仅给出了判别一个基本可行解是否为最优解的准则，而且在且在 非最优时还指出了一条改进它的途径。由于非最优时还指出了一条改进它的途径。由于 在判别现在判别现行基本可行解是否为最优时起了重要的作用，所以行基本可行

9、解是否为最优时起了重要的作用，所以 被成为被成为处的检验向量，而处的检验向量，而 则被称为非基变量则被称为非基变量 的检验数。的检验数。上述过程的另一种实现形式bBNBIbBCBBCCbBNBICCbACTBTBTNrCrTNTBTTB11111100021高斯若当消去法（第一行不变）0 xNN0 x)(Njjjx 0BxNxINB1bB1N 0zNTNTBxCbBCz10上述过程极为简洁明了表达我们需要的全部信息，从其中 所在的m 行可以看出哪些变量是基变量并可以直接读出对应的基本可行解 。其最后一行又给出了非基变量的检验数及 处的目标函数值的相反数。I)0 ,(10bBx0 x接下来，我们

10、将引入所谓的单纯接下来，我们将引入所谓的单纯形表的概念及其具体的工作原理形表的概念及其具体的工作原理 为了便于单纯形法的实施，我们用单纯形表来描述线性规划问题的一个基本可行解的情况。 不妨设x1,x2,xm组成一组基变量，且对应一个基本可行解。用高斯消去法把等式约束和目标函数变形为 x x1 1 +a +a 1m+11m+1x xm+1m+1+a+a 1n1nx xn n=b=b 1 1 x x2 2 +a +a 2m+12m+1x xm+1m+1+a+a 2n2nx xn n=b=b 2 2 x xm m+a+a mm+1mm+1x xm+1m+1+a+a mnmnx xn n=b=b m

11、m -z + -z +m+1m+1x xm+1m+1+n nx xn n= -z= -z0 0把其系数列成数据表即单纯形表: 1.2.2 单纯形法单纯形法(二二) 按照单纯形法的思路求解线性规划问题, 要解决三个技术问题:给出第一个基本可行解; 检验一个基本可行解是否是最优解; 转换到另一个基本可行解. 把线性规划问题变成标准型后, 观察是否每个约束方程中都有独有的、系数为1的变量. 如果是,则取这些变量作为基变量,便得到一个基本可行解; 否则,就给没有这种变量的约束条件添加一个人工变量,同时修改目标函数. (见1.2.2（五）) 如果单纯形表最后以行中的j都满足 j0, 则对应的基本可行解是

12、最优解; 否则就不是最优解. j称为检验数. 第一,确定换入变量. 在大于0的检验数中找最大的为k, 对应变量xk为换入变量. 第二,确定换出变量. 取=minbi/aik|aik0=bl/alk, 对应的第l行的基变量为换出变量. 第三, 旋转运算. 换入变量所在的列与换出变量所在的行交叉点的元素称为中心元素,用高斯削去法把中心元素化成1, 同列的其他元素化成0, 得到一个新的单纯形表,也就得到一个新的基本可行解. 对于上述内容的简单分析对于上述内容的简单分析考虑目标函数11TTTTTBBNNBNBNzC xC xC B bCC B N x()我们知道如果01NBCCTBTNN则目标函数有最

13、优解0 x若0j则令njjmkxxkj, 1, 1, 1, 0, 0显然，随着 的增大，目标函数值得到改进。但是我们知道11BNxB bB Nxjx所以 不能无限制的增大，至少应该保jx证 的可行性。Bx对比理解为何取最大的检验数 为何对应的k 为换入变量，换出变量怎么理解？是否可以理解为随着 的增大， 中第一个为0的那个变量？kxjxBx 1.2.2 单纯形法(三) 用单纯形法求解线性规划问题的具体步骤如下： 找出初始可行基，确定初始基本可行解，建立初始单纯形表；转。 检验对应于非基变量的检验数j。若j0（xj为非基变量）都成立，则当前单纯形表对应的基本解就是最优解，停止计算；否则转。 在所

14、有j0中，若有一个k对应的xk的系数aik0 (i=1,2,m)，则此问题为无界解（无解），停止计算；否则转。 根据 max（j0）=k 确定xk为换入变量；根据规则 minbi/aik1im, aik0bl/alk确定相应的换出变量，并得到中心元素alk。转。 以alk为枢轴元素进行转轴运算，得到新的单纯形表。转. 用单纯行法求解线性规划问题后，应回答下面几个问题： 是否解无界？上面的步骤已作出回答。 是否无可行解？求解后，若人工变量都已取0，则有可行解；否则，无可行解。 唯一最优解还是无穷多最优解？在最后的单纯形表中，若所有非基变量的检验数都严格小于0，则为唯一最优解；若存在某个非基变量的

15、检验数等于0，则有无穷多最优解。1.2.22 单纯形法单纯形法(四四)Max z=2x1+3x2 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1, x2, x3 ,x4,x50 此问题的最优解为此问题的最优解为:x1*=4, x2*=2, x5*=4, x3*= x4*=0 z*=2 4+3 2=14例Max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1, x2 0 1.2.2 单纯形法单纯形法(五五)当线性规划问题（*）的初始可行解不容易看出时，常常引入所谓的人工变量。即对第i个约束引入 ，将其改写为 111,.iinniia xa xyb im0,iiyy 得到辅助规划，其目标函数为11maxmiizy显然，辅助规划有明显的初始可行基。容易看出，原规划有可行解（从而有基本可行解）的充分必要条件为辅助规划的最优目标值为0。故在引入人工变量之后，原规划的目标函数应改写为111maxmnniizc xc xMy求解后，人工变量都取0，则有可行解，否则无解。M作为控制量，控制换入变量 1.2.2 单纯形法单纯形法(五五)例例Min z= -3x1 +x2 +x3 x1 -2x2+x3 11 -4x1 +x2