线性规划及单纯形法PPT课件.ppt

第一章线性规划及单纯形法,1线性规划介绍2线性规划数学模型3线性规划标准形式4线性规划的图解法5线性规划基本概念6单纯形法7应用举例,1线性规划介绍,历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。,线性规划理论的发展：1939年前苏联康托洛维奇（KOHTOPOBUZ）生产组织与计划中的数学方法提出“解乘数法”。,1线性规划介绍,美国科学院院士DANTZIG（丹齐克），1948年在研究美国空军资源的优化配置时提出线性规划及其通用解法“单纯形法”。被称为线性规划之父。,1线性规划介绍,线性规划之父的Dantzig(丹齐克)。据说，一次上课，Dantzig迟到了，仰头看去，黑板上留了几个几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是惭愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很不解,后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。,1线性规划介绍,1960年，“最佳资源利用的经济计算”康托洛维奇和库伯曼斯(Koopmans)。两人因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖,1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。20世纪70年代，斯姆李与杰斯开莱尼应用计算机处理目标规划问题。计算机50约束100变量30000约束3000000变量,1线性规划介绍,从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。,1线性规划介绍,保罗-萨缪尔逊（PAULASAMUELSON）,他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里列昂惕夫（WASSILYLEONTIEF），美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗（KENNETHJ.ARROW）,美国人，因与约翰-希克斯（JOHNR.HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒（MERTONM.MILLER）,1923-2000,美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。,1线性规划介绍,线性规划研究的主要问题：有一定的人力、财力、资源条件下，如何合理安排使用，效益最高?某项任务确定后，如何安排人、财、物，使之最省?,例1美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表Il所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大？,2线性规划数学模型,例2捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随合同期定，期限越长折扣越大，具体数字见下表。租借仓库的合同每月初都可办理，每份台同具体现定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借台同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,2线性规划数学模型,目标函数,约束条件,解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。,例1,用数学语言描述,2线性规划数学模型,解：设变量xij表示捷运公司在第i(i1，4)个月初签订的租借期为jj1，4)个月的仓库面积的合同(单位为100m2)。,约束条件,目标函数,例2,2线性规划数学模型,求：最大利润的生产计划。,练习1生产计划问题,2线性规划数学模型,maxZ=40 x1+50 x2,解:设产品A,B产量分别为变量x1，x2,2线性规划数学模型,求：最低成本的原料混合方案？,练习2混合配料问题,2线性规划数学模型,解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4),minZ=2x1+5x2+6x3+8x4,2线性规划数学模型,决策变量：向量(x1xn)T决策人要考虑和控制的因素。非负约束条件：线性等式或不等式目标函数：Z=(x1xn)线性式，求Z极大或极小,线性规划模型特点,2线性规划数学模型,如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。实际问题中线性的含义：一是严格的比例性。如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例。二是可叠加性。如生产多种产品时对某项资源的消耗量应等于各产品对该项资源的消耗量之和。,2线性规划数学模型,19,max(min)Z=c1x1+c2x2+cnxn,n个变量,价值系数,第i种资源的拥有量,技术系数或工艺系数,线性规划的一般式,2线性规划数学模型,线性规划的简写式,2线性规划数学模型,线性规划的向量表示式,2线性规划数学模型,线性规划的矩阵表示式,2线性规划数学模型,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij,bi,ci为确定值。,隐含的假设,2线性规划数学模型,练习3运输问题工厂需要的原棉存放在三个仓库中，现将原棉运往工厂以满足工厂生产的需求。已知原棉运到各个工厂的单位运费如表所示。问使总运费最小的运输方案？,2线性规划数学模型,解：设xij为i仓库运到j工厂的原棉数量(i=1,2,3j=1,2,3),minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33,2线性规划数学模型,练习4连续投资10万元A：从第1年到第4年每年初投资，次年末回收本利1.15；B：第3年初投资，到第5年末回收本利1.25，最大投资4万元；C：第2年初投资，到第5年末回收本利1.40，最大投资3万元；D：每年初投资，每年末回收本利1.11。求：使5年末总资本最大的投资方案。,分析：,2线性规划数学模型,解：xik(i=1,2,5;k=A,B,C,D)为第i年初投资到第k个项目的资金数。,MaxZ=1.15x4A+1.40 x2C+1.25x3B+1.11x5D,2线性规划数学模型,线性规划问题应用市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用),2线性规划数学模型,线性规划的适用情况要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件,2线性规划数学模型,线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,0,线性规划的标准形式目标函数：max约束条件：=变量符号：0,3线性规划标准形式,标准型的一般型,maxZ=c1x1+c2x2+cnxn,其中bi0(i=1,2,m),3线性规划标准形式,C=(C1C2Cn),标准型的矩阵型,3线性规划标准形式,P1x1+P2x2+Pnxn=b,标准型的向量型,3线性规划标准形式,线性规划问题化标准型：,(1)、约束条件(2)、变量(3)、目标函数(4)、右端常数,3线性规划标准形式,(1)、约束条件,x3为松弛变量,x4为剩余变量,松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。,当约束条件为“”时：,当约束条件为“”时：,3线性规划标准形式,3线性规划标准形式,转化为：maxZ=40X1+50X2+0X3+0X4+0X5,例：maxZ=40 x1+50 x2,松弛变量,3线性规划标准形式,例：,剩余变量,(2)、变量,1、x0的情况，,令x1=x1-x1,2、x取值无约束的情况。,令x-x。,令x=x-x,3线性规划标准形式,（3）、x两边有约束的情况。,-6+6x1+610+6令x1=x1+60x116,3线性规划标准形式,(3)、目标函数,令Z=-Z,3线性规划标准形式,(4)、右端常数,右端项b0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。,3线性规划标准形式,例3：将minZ=-x1+2x2-3x3,化为标准型,3线性规划标准形式,解：令x3=x4-x5,加松弛变量x6,加剩余变量x7,令Z=-Z,maxZ=x1-2x2+3x4-3x5,3线性规划标准形式,(1)minZ=2x1-x2+2x3,练习5将下列线性规划问题化成标准型：,(2)maxZ=2x1+x2+3x3+x4,3线性规划标准形式,(3)minZ=2x1+3x2+5x3,(4)maxZ=x1-3x2,3线性规划标准形式,作业:课本P4412,3线性规划标准形式,定义1：满足约束(1)、(2)的x=(x1xn)T称为LP问题的可行解，全部可行解的集合称为可行域。,定义2：满足(3)的可行解称为LP问题的最优解,线性规划的标准型,4线性规划的图解法,图解法求解的目的：一是判别线性规划问题的求解结局；二是在存在最优解的条件下，把问题的最优解找出来。,4线性规划的图解法,图解法的步骤：1、在平面上建立直角坐标系；2、图示约束条件，找出可行域；3、图示目标函数和寻找最优解。,4线性规划的图解法,例4maxZ=40 x1+50 x2,4线性规划的图解法,解：(1)、确定可行域x10 x1=0(纵)x20 x2=0(横),x1+2x230 x1+2x2=30(0,15)(30,0),3x1+2x2=60(0,30)(20,0),2x2=24,4线性规划的图解法,(2)、求最优解,最优解：x*=(15,7.5)Zmax=975,Z=40 x1+50 x20=40 x1+50 x2(0,0)，(10,-8),4线性规划的图解法,解:最优解：BC线段B点C点x(1)=(6,12)x(2)=(15,7.5)x=x(1)+(1-)x(2)(01),4线性规划的图解法,4线性规划的图解法,无界解无有限最优解,4线性规划的图解法,无解无可行解,4线性规划的图解法,当目标函数的直线族与某约束条件平行，且该问题有解时。,约束条件无公共区域。,有解但可行域可伸展到无穷时,总结,4线性规划的图解法,由图解法得到的启示(1)、线性规划问题的解的情况有四种：唯一最优解；无穷多最优解；无界解；无可行解。(2)、若线性规划可行域存在，则可行域是一个凸集。(3)、若有最优解，定可在可行域的顶点得到。(4)、解题思路是找出凸集的各顶点的最大目标函数值。,4线性规划的图解法,作业：,用图解法解以下问题：maxZ=5x1+6x2,4线性规划的图解法,一、线性规划问题的解的概念,5线性规划基本概念,定义1：基(基阵)设A为约束方程组的mn阶系数矩阵设(nm)，其秩为m，B是矩阵A中的一个mm阶的满秩子矩阵，称B是线性规划问题的一个基。,B,5线性规划基本概念,B中的每一个列向量Pj称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。,5线性规划基本概念,Ax=b的求解,BxB+NxN=bBxB=b-NxNxB=B-1b-B-1NxN,A=(BN)x=(xBxN)T,若B为单位矩阵xB=b-NxN若xN0 xB=B-1b,5线性规划基本概念,定义2：可行解满足方程约束条件的解x（x1，x2，xn)T,称为线性规划问题的可行解。全部可行解的集合称为可行域。,定义3：最优解使目标函数达到最大值的可行解，称为最优解。,5线性规划基本概念,基本解中最多有m个非零分量。,定义6：可行基对应于基可行解的基称为可行基。,5线性规划基本概念,5线性规划基本概念,B=(P3P4P5)=I是满秩子矩阵非基N=(P1P2),5线性规划基本概念,令x1=x2=0,x3=30,x4=60,x5=24,5线性规划基本概念,求出基变量是x1,x3,x4的基本解，是不是可行解？,5线性规划基本概念,5线性规划基本概念,x=(1,0,3/2,3/2)T是,5线性规划基本概念,凸集D是n维空间的一个集合，x(1),x(2)D,若对任何x(1),x(2)，有x=x(1)+(1-)x(2)D(01)，则D为凸集。,定义1：,凸集如果集合D中任意两个点，其连线上的所有点也都是集合D中的点，则称D为凸集。,二、凸集及其顶点,5线性规划基本概念,凸多边形,凹多边形,5线性规划基本概念,第一章,x(1),x(2),x(k)是n维欧氏空间中的k个点，若有一组数1,2,k满足0i1(i=1,k),定义2,有点x=1x(1)+kx(k)则称点x为x(1),x(2),x(k)的凸组合。,凸组合,5线性规划基本概念,凸集D,点xD，若找不到两个不同的点x(1),x(2)D使得x=x(1)+(1-)x(2)(01)则称x为D的顶点。,定义3,顶点,5线性规划基本概念,证明：设LP问题的可行解域为集合CC=x|Ax=bx0任取x(1),x(2)C,则x=x(1)+(1-)x(2)0(01)又因为Ax(1)=b，Ax(2)=b所以Ax=Ax(1)+(1-)x(2)=b+(1-)b=b则xC，C为凸集,定理1：LP问题的可行解域一定是凸集。,三、几个基本定理的证明,5线性规划基本概念,只须证明：D的k个顶点x(1),x(k)，有,预理1D为有界凸多面集，xD，x必可表为D的顶点的凸组合。,5线性规划基本概念,证明可用归纳法（略）,x在边界上,x在内部,5线性规划基本概念,证明：设x(1),x(k)为可行域顶点，若x*不是顶点，但maxZ=Cx*,定理2：可行域有界，最优值必可在顶点得到,5线性规划基本概念,引理2：,证明：（1）必要性。由基可行解的定义显然。（2）充分性。若向量P1，P2,Pk线性独立，则必有km。当k=m时，它们恰好构成一个基，从而x=(x1,x2,xm,0,0)为相应的基可行解。当km时，则一定可从其余列向量中找出(m-k)个与P1,P2,Pk构成一个基，其对应的解恰为x，所以据定义它是基可行解。,5线性规划基本概念,证明(反证法）：,由引理2知，p1,pk线性相关必有不全为0的1,k使1p1+kpk=0,做(1,k,0,0)T则有A1p1+kpk=0,定理3：,5线性规划基本概念,选任一不为零的数,令x(1)=x+0 x(2)=x0,因为x1/2x(1)+1/2x(2),所以x不是可行域的顶点,5线性规划基本概念,83,x=x(1)+(1-)x(2)(00，xj(1)0，xj(2)0,所以xj(1)xj(2)0(j=k+1,n),即p1x1(1)+pkxk(1)=b(a)p1x1(2)+pkxk(2)=b(b),5线性规划基本概念,由(a)(b)得,(x1(1)x1(2)p1+(xk(1)xk(2)pk=0,即x不是基可行解,所以p1,pk线性相关,定理4若线性规划问题有最优解，一定存在一个基可行解是最优解。,5线性规划基本概念,若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。,5线性规划基本概念,LP问题解的性质,6单纯形法,6.1、单纯形法迭代原理6.2、单纯形法计算步骤6.3、人工变量法6.4、两阶段法6.5、计算中的几个问题,6.1单纯形法迭代原理,一、确定初始基可行解二、从一个基可行解转换为相邻基可行解三、最优性检验和解的判别,A中总存在一个单位矩阵（P1,P2,Pm)。,一、确定初始基可行解,当约束条件为时，加上松驰变量的系数矩阵即为单位矩阵。当约束条件为或时，可以构造人工基，人为产生一个单位矩阵。基向量、基变量、非基向量、非基变量可得初始基可行解:x=(x1,xm,xm+1,xn)T=(b1,bm,0,0)T,6.1单纯形法迭代原理,两个基可行解相邻指的是它们之间变换且仅变换一个基变量。设x(0)=(x10,x20,xm0,0,0)T，有,系数矩阵的增广矩阵,二、基可行解的转换,6.1单纯形法迭代原理,两边乘上一个正数0，得,所以得到另一个点x(1),使,可行解?,基解?,6.1单纯形法迭代原理,所以x(1)是可行解,令,存在：,6.1单纯形法迭代原理,重新排列后不含非基向量的增广矩阵：,因alj0，故上述矩阵元素组成的行列式不为零，P1,P2,Pl-1,Pj,Pl+1,Pm是一个基。所以，x(1)，是基可行解。,000100,6.1单纯形法迭代原理,进行初等变换：,b=(b1-a1j,bl-1-al-1,j,bl+1-al+1,j,bm-amj)T,由此x(1)是x(0)相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。,x(1)=(b1-a1j,bl-1-al-1,j,bl+1-al+1,j,bm-amj)T？,6.1单纯形法迭代原理,将基本可行解x（0）和x（1）分别代入目标函数得：,三、最优性检验和解的判别,6.1单纯形法迭代原理,是对线性规划问题的解进行最优性检验的标志。,当所有的i0，又Pj0,则判定原问题无可行解。第2阶段：去除人工变量，求解原问题。第一阶段的最优解为原问题的初始基可行解。,6.4两阶段法,例2：,解：第(1)阶段：,maxW=-x6-x7,6.4两阶段法,列初始单纯形表,第二阶段：去除人工变量，列新单纯形表求解。,6.4两阶段法,6.4两阶段法,6.4两阶段法,6.5计算中的几个问题,2、退化：（非退化值唯一）,在下一次迭代中有一个或几个基变量为0，从而出现退化解。可能会导致循环，永远达不到最优解。,1、目标函数极小化时解的最优性判别以i0作为判别表中解是否最优的标志,如何解决退化问题？,Dantzig规则：,6.5计算中的几个问题,6.5计算中的几个问题,1951年Hoffman给出反例。（3个方程，11个变量）1955年E.M.L.Beale3个方程，7个变量。6次迭代后，出现循环。,Bland原则（1976年第9届国际数学规划大会）,6.5计算中的几个问题,3、无可行解的判别,当线性规划问题中添加人工变量后，无论用人工变量法或两阶段法，初始单纯形表中的解因含非零人工变量，故实质上是非可行解。当求解结果出现所有i0时，如基变量中仍含有非零的人工变量(两阶段法求解时第一阶段目标函数值不等于零)，表明问题无可行解。,6.5计算中的几个问题,6.5计算中的几个问题,例7用单纯形法求解线性规划问题,6.5计算中的几个问题,解：添加松弛变量和人工变量，原模型化为标准型。,以X3，X5为基变量列初始单纯形表，进行计算。,6.5计算中的几个问题,6.6单纯形法小结,6.6单纯形法小结,7应用举例,例1：用长7.4m的钢材做100套钢架，每套钢架需长2.9m,2.1m,1.5m的料各一根。问如何下料，使用的原料最省？分析：可行的下料方案有：,解：设第i种方案用xi根原料。,解之得x3=30 x5=50 x6=10,思考：1）目标函数可否改为z=x1+x2+x3+x4+x5+x62）若每套钢架需长2.9m一根，2.1m二根，1.5m五根。问如何求解。,7应用举例,例2连续投资问题李勇拟定在三年后购买一套房子，准备在今后的三年