《《线性规划基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《线性规划基础》PPT课件.ppt（49页珍藏版）》请在三一办公上搜索。
1、第六章 线性规划基础,-环境系统污染控制规划的数学基础,6.1 线性规划概述,线性规划是数学规划与运筹学的一个分支，是运筹学中最重要的一种数学方法。主要研究解决有限资源的最佳分配问题，即如何对有限的资源作出最佳方式的调配和最有利的使用，以便最充分地发挥资源的效能去获取最佳经济效益。这种数学规划的方法，如果用数学语言表达，就是在一定的约束条件下，寻找目标函数的极值问题。所谓线性规划，是指约束条件为线性等式或不等式，且目标函数也是线性函数。,生产调度问题,1.线性规划问题的提出,一、线性规划及其数学模型,某企业生产甲、乙两种产品，分别用A、B、C 3种不同的原料，每生产1个单位的甲，需用1个单位的
2、A、1个单位的B、0个单位的C，利润为3千元；每生产1个单位的乙，需用1个单位的A、2个单位的B、1个单位的C，利润为4千元；现有6个单位的A、8个单位的B、3个单位的C，问企业如何安排生产，可使利润最大。,产品,甲,乙,x1,x2,原料,A,B,C,利润,1,1,0,3,1,2,1,4,原料限制,6,8,3,2.建模的步骤,(1)明确问题的经济背景,(2)设定决策变量,(3)明确目标-给出目标函数,(4)明确问题的所有限制-给出约束条件,Z=3x1+4x2,x1+x2 6,x1+2x2 8,x2 3,x10,x2 0,每天总利润：Z=3x1+4x2 变量 x1 和x2必须满足三个条件：x1+
3、x2 6 x1+2x2 8 x2 3非负性约束：x10,x2 0,目标函数,决策变量,函数约束,约束条件,Max Z=3x1+4x2 x1+x2 6 x1+2x2 8 x2 3 x10,x2 0,数学模型,s.t.,线性规划的数学表达,即求一组变量x1,x2,xn,在满足约束条件：a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm x1,x2,xn 0 的情况下，使目标函数：f=c1x1+c2x2+cnxn 达到最大值或最小值。,Max/Min F=CX AXB 或 AXB X0 或 X0 或 X自由其中：C=(c1,c2,c
4、n)B=(b1,b2,bm)X=(x1,x2,xn)A=aij（i=1,2,m；j=1,2,n）,一般来说，满足约束条件的变量X=(x1,x2,xn)T有无穷多个解，求解LP问题的目的就是从中找出一个能满足目标函数最大或最小的解，作为该LP问题的最终决策。决策变量、目标函数、约束条件是LP模型的三要素，其中后两者都是关于前者的线性表达式；而LP模型就是由最优化的目标函数和约束条件这两部分构成的。,二、线性规划的图解法,线性规划的图解法，就是借助几何图形来求解线性规划问题的一种方法。图解法的基本步骤：1.可行域的确定 LP模型所有约束条件共同构成的图形，称为可行域图形。2.目标函数的等值线和最优
5、点的确定,F(0,6),x1+x2=6,X1,X2,O,B(4,2),C(2,3),E(8,0),G(0,6),Z=20,Z=3x1+4x2,A(6,0),x1+2x2=8,x2=3,D(0,3),可以看到：当沿法线方向平行移动直线Z=3x1+4x2至B点时，Z值在可行域R上就达到了最大值，从而确定B点即为该LP问题的最优点。最优点的坐标值为最优解。记为X*=(x1*,x2*)T,X*对应的目标函数值称为最优值，记为Z*。该实例的最优解：X*=(4,2)T,Z*=20 说明最优生产方案是：生产甲产品4件，乙产品2件，可获得最大利润20千元。,LP问题几种可能的结果：唯一解；多重解；无界解；无可
6、行解。唯一解：只有一个最优点多重解：有些LP问题最优解可能不唯一，如:前例中目标函数改为：max Z=x1+2x2 则目标函数等值线与约束条件x1+2x28的边界线平行。当将等值线沿法线方向平移到B点时，就与R的边界线BC段重合。这表明BC上的每一点都使目标函数值取得同样的最大值。这时出现多重解的情形。,无界解：Max Z=3x1+2x2-2x1+x2 2 x1-3x2 3 x10,x2 0,s.t.,x1,x2,无可行解：有些LP问题可能不存在可行点，也就是说由约束条件得到的可行域R为空集，即R=。这时问题无可行解，也就无最优解了，简称无解。LP问题的可行域一般是凸多边形，而且若最优解存在，
7、则一定在可行域的某个顶点上得到；若在两个顶点同时得到最优解，则这两个顶点连线上的每一点都是最优解，且最优值相等；若可行域无界，则可能发生最优解无界的情况，此时无最优解。若可行域为空集，则问题无可行解。,三、线性规划的标准形式,LP问题的各种不同形式可以相互转化，只需给出其中一种形式的解法，就可以普遍适用于一切形式的LP问题，而单纯形法所基于的LP问题的形式，称为标准形式。,1.线性规划问题的标准形式,A=（aij）mn为约束方程组的系数阵。R(A)=mn,即A为满秩阵，称m为LP问题的阶数，n为维数,目标函数 min Z=CTX函数约束bi0 两端乘以-1约束为“”的情况，增加非负变量 松弛变
8、量约束为“”的情况，减去非负变量剩余变量决策变量对不满足非负性要求的变量，采用“变量代换法”,2.非标准形LP问题的标准化,max z=-CTX,举例：,如果xk0,可令xk=-xk，xk 0。如果xk为自由变量，可令xk=xk_xk，且xk0，xk0。如果方程中有多个xk为自由变量，按照上述方法会使变量的个数扩大一倍，从而增加问题求解时的计算量，为了尽量少地增加变量的个数，可以令xk=xk-x“，其中x“对每个xk的表达式都是同一个数。,变量代换法,四、线性规划的解及其性质,可行解：满足LP问题所有约束条件的向量X 可行域所有可行解构成的集合最优解：满足目标要求的可行解，记为X*，其所对应的
9、目标函数值称为最优值，记为z*。基本解：基本解的概念只适用于标准型LP问题。,基向量和非基向量：A=(aij)mn=(P1 P2 Pn)为线性规划问题LP的约束条件系数矩阵，其秩为m。则A中任一组m个线性无关的列向量构成的矩阵B=(Pji pj2 Pjm)非奇异，称此m个线性无关的列向量为线性规划问题的一个基。如果约束矩阵A中某一列向量Pj包含于基B中，则称Pj为基向量，否则称为非基向量。对于给定的一个基，整个矩阵A可以分为两部分，即可表示为A=(B N),基变量与非基变量：与基向量Pjt(t=1,2,m)相对应的变量xjt称为基变量，否则称为非基变量。LP问题的变量也自然被相应地分成了两部分
10、X=(xB xN)T基本解：在LP问题中，满足条件AX=b且非基变量全部为零的X成为基本解。X=(xB xN)T=(xB 0)T AX=(B N)(xB xN)T=BxB+NxN=b 即基本解X可以用基变量部分来表示成xB=B-1b,基本可行解：满足非负条件的基本解，或者说xB=B-1b0就称其为基本可行解。,基本解,可行解,基本可行解,约束矩阵A中基的数目最多为Cnm，因而基本解的个数最多也只能有Cnm个，所以基本可行解的个数也不会超过Cnm,退化基本解：如果基本解中有一个或者多个基变量为零，则称为退化基本解可行基：基本可行解对应的基最优基：最优基本解对应的基标准形LP问题的任一基本可行解，
11、其所含正分量的个数比不超过问题的阶数m，而一个非退化的基本可行解必恰有m个正分量，其余分量均为0。,标准形LP问题解的概念与关系,线性规划解的性质,性质1：LP问题的可行域R为一凸集性质2：LP问题的一个基本可行解与可行域R的一个极点互相对应性质3：线性规划的基本定理：对于任何一个给定的标准形LP问题M来说，若M有可行解，则必有基本可行解；如M有最优解，则必有最优基本可行解。性质4：若LP问题的可行域R，则R至少有一极点性质5：LP问题可行域R的极点数量必为有限多个,五、线性规划的单纯形法,单纯形法的基本思想 单纯形法有三种形式：方程组形式 表格形式 矩阵形式单纯形法的计算过程 单纯形表,单纯
12、形法的基本思想,单纯形法的基本思路：求出可行域S的一个基本可行解 判别这个基本可行解是否为最有解 在使得目标函数值有所改进的前提下进行顶点的转换 重复上述过程，通过有限步来求解LP问题。,范例说明,Max Z z 3x1 5x2=0 x1+x 3=8 2x2+x4=12 3x1+4x2+x5=36 x1,x2,x3,x4,x5 0,约束方程系数阵：,有一个基,的非退化的基本可行解为:X0=(0,0,8,12,36)T,条典：基本可行解对应的可行基是一个m阶单位阵（排列阵）目标方程中所有基变量的系数全为0典式：满足条典的线性方程组检验数：当目标方程中基变量的系数全为0时，非基变量的系数可以作为判
13、断当前基本可行解是否最优的一个标志，称检验数只要目标方程中存在负检验数，就意味着目标值还能增加，就需要把它对应的非基变量变换为基变量。,进基变量选择的规则最小检验数规则 在负检验数中选择数值最小者，让它对应的非基变量进基。即：如果记检验数为j（j=1,2,n）包括基变量的检验数（全为0）那么可用数学表达式表示：minj|j0=K k对应的变量xk进基。,离基变量选择的规则最小比值规则 min bi/aik|aik0=bl/alk 确定主元alk，同时也确定l行的基变量离基。基本可行解的变换矩阵初等变换,6,8,X1,X2,O,A,B,C,D,E(12,0),G(0,9),F(8,6),Z=42
14、,单纯形法的几何意义,单纯形法的计算过程单纯形表,单纯形法的计算步骤,把LP问题化成标准型在系数阵中找出或构造出一个m阶排列矩阵作为初始可行基，建立初始单纯形表若所有检验数j0，得到一个最优基本解，停止运算，否则转4在所有j0中，只要有一个r0所对应的系数列向量ar0,即一切air0,则该问题无最优解，停止运算，否则转5按最小检验数规则minj|j0=K确定进基变量xk和主列ak，再按最小比值规则min bi/aik|aik0=bl/alk 确定主元alk，同时也确定l行的基变量离基。以ak为主元对当前表格进行一次换基运算，得到一个新的单纯形表的形式。,人工变量法,单纯形法要求先从系数阵中找出
15、一个m阶排列阵，这往往不容易做到，特别对于系数阵A为降秩阵的LP问题，根本就找不出；还有些LP问题本身并没有可行解，当然也就找不出基本可行解。但由于问题的形式比较复杂，往往不易判断。采用人工变量法可以解决上述问题。,A,分别给每个约束方程硬行加入一个非负变量xn+1，xn+2，xn+m，得到,B,这样，以xn+1，xn+2，xn+m为基变量，可以得到如下的一个初始基本可行解：X0=(0,0,0,b1,b2,bm)T,这个解X0完全是人为地加入m个变量而得到的，因此称为人造基本解，而把变量xn+1，xn+2，xn+m称为人工变量。,人造解X0显然不是原LP问题A的基本可行解，但是若能通过单纯形法
16、的迭代步骤将虚拟的人工变量全部从基中替换出去，这时可以得到一个基本解Xk，不仅满足式B,而且由于人工变量xn+1=xn+2=xn+m=0，因此Xk的前n个分量就构成了原LP问题的一个基本可行解。如果经过迭代不能将人工变量变为非基变量，则表明原问题没有可行解。,？怎样对式B进行迭代才能实现上面的意图呢？,这和如何处理人工变量与目标函数的关系密切相关。,大M 法,两阶段法,大M 法,在原LP问题A的目标函数中添加全部人工变量，并令其系数均为-M，而M为一个充分大的数。即构造如下的辅助问题：(FI)：max z=c1x1+c2x2+cnxn-M(xn+1+xn+m)并用单纯形法进行求解。(1)若迭代
17、最终得到FI的最优解X*,而且X*的基中部含人工变量，则X*的前n个分量就构成了原LP问题的一个最优基本解；否则原问题无可行解。(2)如迭代的最终结果为FI解无界，此时基中如果没有人工变量，则原问题也解无界。否则原问题无可行解。,举例说明：max z=3x1-x2-2x3 s.t.3x1+2x2-3x3=6 x1-2x2+x3=4 x10,x20,x30,按大M法引入人工变量x4,x5,得到FI:max z=3x1-x2-2x3-Mx4-Mx5 s.t.3x1+2x2-3x3+x4=6 x1-2x2+x3+x5=4 x1,x2,x3,x4,x50,辅助问题最优解：x1*=3,x3*=1,x2*=x4*=x5*=0;z*=7原问题的最优解：X*=(3,0,1)T,z*=7,
