1线性规划与单纯形法

119,9/29/2024,运筹学,Operational Research,主讲：张晓果,运筹学是一门基础性应用学科，主要是将社会经济建设实践中经济、军事、成产、管理、组织等事件中出现的一些带有普遍性的,运筹问题,加以提炼，然后利用科学方法进行分析、求解等。前者提供模型，后者提供理论和方法。运筹学主要研究系统最优化问题，通过对建立的模型求解，为决策者进行决策提供科学依据。,绪 论,一、运筹学发展简介,二、运筹学定义,三、运筹学的性质与特点,四、运筹学的应用,五、运筹学的工作步骤,六、运筹学的分支,一、运筹学（,OR,）,发展简介,英国称为,Operational Research,美国称为,Operations Research,朴素运筹学思想的出现可以追溯到很早,战国时期,齐王田忌赛马,、北宋,丁渭重修皇宫,运筹学的三个起源：军事、经济、管理,军 事,第一次世界大战期间,1914-1915,兰彻斯特的若干军事论文,研究战争的胜负同兵力多寡、火力强弱之间的关系；,爱迪生解决反潜战的“战术对策演示盘”,反潜战的研究项目：汇编各项典型统计数据用于选择回避或击毁潜艇的最佳方法，使用“战术对策演示盘”解决,免受潜艇攻击,的问题。,军 事,二战期间的案例,鲍德西,（,Bawdsey,）雷达站的研究,“,布莱克特马戏团,/,杂技班”的出色工作,项目的巨大实际价值：明确的目标；整体化的思想；数量化的分析；多学科的协调；最优化的结果,大西洋反潜战,Morse,小组的重要工作,协助英国打破了德国对英吉利海峡的海上封锁；,军事运筹学的特点,定量化系统化方法迅速发展,采集真实的数据,多学科密切协作（数学、管理等）,解决方法渗透着物理学思想,管 理,泰勒的动作研究,切削效率与车速、进刀量等因素的数学关系,优选问题（提高切削效率）,统筹方法（用于生产活动分析和计划安排）,前苏联康特洛维奇的工作（生产组织与计划方法）,经 济,QUSNAY,（魁内）,1758,年在凡尔赛发表,经济表,对经济中各部门的平衡关系做了最早的研究,Walras,（沃尔拉思）对经济平衡问题的研究,1932,年,Von Neumann,提出第一个广义经济平衡模型,马克思是最早将数学用于经济研究的经济学家之一，在沃尔拉思钻研他的数理经济问题的同时，马克思也在研究他所碰到的数理经济问题,运筹学的发展,萌芽时期,朴素的,OR,思想自古有之,早期研究,经济表,、一战、生产组织与计划,形成与发展时期,二战；战后,20,世纪,50-60,年代走向成熟,成立学会，创办刊物，高校开课，军事运筹学,运筹学的发展趋势,成熟的学科分支纵深发展,新的研究领域产生,与新的技术结合,与其他学科的结合加强,传统优化观念不断变化,二、运筹学定义,运筹学为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法,Morse,和,Kimball,运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测、比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策,英国运筹学会,二、运筹学定义,运筹学,是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理,中国企业管理百科全书（,1984,年版）,运筹学是一门应用于管理有组织系统的科学，为掌管这类系统的人提供决策目标和数量分析的工具,大英百科全书,二、运筹学定义,运筹学用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，是实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案,中国大百科全书（自动控制与系统工程卷，,1991,年版）,由于运筹学涉及的主要领域是管理问题，研究的基本手段是建立数学模型，并比较多地利用各种数学工具，于是有人将运筹学称做,“,管理数学,”。,三、运筹学的性质与特点,引入数学方法解决实际问题,定性与定量方法结合,系统与整体性,从全局考察问题,应用性,源于实践、为了实践、服务于实践,交叉学科,涉及经济、管理、数学、工程和系统等多学科,开放性,不断产生新的问题和学科分支,多分支,问题的复杂和多样性,四、运筹学的应用,生产计划,：,生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。,库存管理,：,多种物资库存量的系统组织与安排管理，确定某些设备的能力或容量，如停车场的大小、合理的水库容量等,运输问题,：,确定最小成本的运输线路、物资的调拨、运输工具的调度以及厂址的选择等。,人事管理,：,对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系、人才开发的规划、激励机制的研究等。,财务和会计,：,包括预测、贷款、成本分析、定价、证券管理、现金管理等。,市场营销,：,广告预算、媒介选择、定价、产品开发与销售计划制定等。,城市管理,：,各种紧急服务系统的设计与应用，城市垃圾的清扫、搬运和处理，城市供水和污水处理系统的规划，区域规划，市区交通网络的规划与管理等。,五、运筹学的工作步骤,提出问题,用自然语言描述问题。,建立数学模型,用变量、函数、方程描述问题。,求解,主要用数学方法将模型求解。解可以是最优解、次优解、满意解，复杂模型求解要用计算机。,解的检验,检查模型和求解步骤有无错误，检查解是否反映现实问题。,解的实施,决策者根据自己的经验和偏好，对方案进行选择和修改，作出实施的决定。,六、运筹学的分支,数学规划,包括：线性规划，,非线性规划，,整数规划，,目标规划，动态规划，,随机,规划，模糊规划；图论与网络；排队论；存储论；对策论；决策论；可靠性和质量管理等。,七、如何学好运筹学,学习运筹学要把,重点,放在分析、理解有关的概念、思路上。在学习过程中，应该多向自己提问，例如一个方法的实质是什么，为什么这样做，怎么做等。,学习或复习时要掌握三个,重要环节,：,1.,认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助你开阔思路，使学习深入。,2.,要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因此，做题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容有内在联系，只要学到一定程度，知识融会贯通起来，你自己就能够对所做题目的正确性作出判断。,3,、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来概述该书所讲内容。这样，你才能够从较高的角度来看问题，更深刻地理解有关知识和内容。,这就称作,“,把书读薄,”,，若能够结合相关参考文献并深入理解，把相关知识从更深入、广泛的角度进行论述，,则,称,为,“,把书读厚,”,。,第一章 线性规划与单纯形法,本章内容重点,线性规划模型与解的主要概念,线性规划的单纯形法，线性规划多解分析,线性规划应用,建模,第,1,节 线性规划问题及其数学模型,一、实例,例,1,某工厂在计划期内要安排生产,、,两种产品，已知生产单位产品所需的设备台时和原料,A,、,B,的消耗量如下表。该工厂每生产一件,产品,可获利,2,元，每生产一件产,品,可获利,3,元，问应如何安排生,产计划能使该厂获利最多？,解：这个问题可以用下面的数学模型来描述，设计划期内产品,、,的产量分别为,x,1,，,x,2,，可,获利润用,z,表示，则有：,Max Z=2x,1,+3x,2,x,1,+2x,2,8,4x,1,16,4x,2,12,x,1, x,2,0,例,2,靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天,500,万,m,3,，,两工厂之间有一条流量为每天,200,万,m,3,的支流（见图）。,第一化工厂每天排放污水,2,万,m,3,，,第二化工厂每天排放污水,1.4,万,m,3,。,污水从工厂,1,流到工厂,2,前会有,20%,自然净化。根据环保要求，河水中污水的含量应不大于,0.2%,。而工厂,1,和工厂,2,处理污水的成本分别为,1000,元,/,万,m,3,和,800,元,/,万,m,3,。,问两工厂各应处理多少污水才能使处理污水的总费用最低？,解： 设工厂,1,和工厂,2,每天分别处理污水,x,1,和,x,2,万,m,3,，,则有：,Min z=1000x,1,+800x,2,(2-x,1,)/500 0.002,0.8(2-x,1,)+1.4-x,2,/700,0.002,x,1,2, x,2,1.4,x,1, x,2,0,二、总结,都有一个要达到的目标，可以用决策变量的线性函数,(,目标函数,Objective Function,）来表示。,按问题的不同，要求目标函数实现最大化或最小化。,线性规划（,Linear Programming,）问题的,共同特征,：,每一个问题都用一组决策变量,(Decision Variable),（,x,1,x,2, ,x,n,）,表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。,存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。,结论,：,线性规划是研究在一组线性不等式或等式约束条件下，使某一线性目标函数取最大或最小的极值问题。,满足以上条件的数学模型称为线性规划模型。线性规划模型的一般形式如下：,三、线性规划问题的标准型,1.,标准型,标准型的四个特点：,目标最大化、约束条件为线性等式、决策变量均非负、约束条件右端项非负。,2.,所有,LP,问题均可化为标准型,(1),若目标函数为,MinZ,，令,Z,=-Z,，则,MinZ,等价于,MaxZ,(2),将不等式约束条件化为等式约束条件,令,x,j,=,x,j, -,x,j,，,对模型中的进行变量代换。,不符合标准型的几个方面：,目标函数为,min z=c,1,x,1,+c,2,x,2,+,+c,n,x,n,令,z,=-z,变为,max z,= -c,1,x,1,- c,2,x,2,-, -,c,n,x,n,约束条件为,a,11,x,1,+a,12,x,2,+a,1n,x,n,b,1,加入非负变量,x,n+1,，,称为松弛变量，有,a,11,x,1,+a,12,x,2,+a,1n,x,n,+x,n+1,=b,1,约束条件为,a,11,x,1,+a,12,x,2,+a,1n,x,n,b,1,减去非负变量,x,n+1,，,称为剩余变量，有,a,11,x,1,+a,12,x,2,+a,1n,x,n,- x,n+1,=b,1,变量,x,j,无约束。,例,3,可化为,例,4,化标准型,3.,线性规划的向量和矩阵表达式,式,中：,C = c,1,c,2,.,c,n,矩阵式：,向量式：,课堂作业,四、两变量线性规划问题的图解法,1.,线性不等式的几何意义,半平面,作出,LP,问题的可行域,作出目标函数的等值线,移动等值线到可行域边界得到最优点,2.,图解法步骤,对于只有两个变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。,4x,1,=16,4x,2,=12,x,1,+2x,2,=8,x,1,x,2,4,8,4,3,0,例,6,（书,P10,）：,Q(4,2),Z=2x,1,+3x,2,做目标函数,2x,1,+3x,2,的等值线，与阴影部分的边界相交于,Q(4,2),点，表明最优生产计划为：生产,I,产品,4,件，生产,II,产品,2,件。,唯一最优解,无穷多最优解,x,1,x,2,x,1,x,2,解无界,3.,图解法,(Graphical Solution),的启示,具有两个变量的线性规划问题的可行域是凸多边形。,LP,问题,有,可行解,有,最优解,唯一解,无穷多解,无,最优解（可行域为无界）,无,可行解（无解）,线性规划问题的解的若干情况,若线性规划存在最优解，它一定在可行域的某个顶点得到。,若线性规划问题有可行解，则可行域是一个凸,多边形。它可能有界，也可能无解。,若线性规划问题有最优解，则最优解可能是唯,一的；也可能是无穷多个。如果是唯一的，这个,解一定在该凸多边形的某个顶点上；如果是无穷,多个，则这些最优解一定充满凸多边形的一条边,界（包括此边界的两个顶点）。,若线性规划问题有可行解，但是没有有限最优,解，此时凸多边形是无界的。,若线性规划问题没有可行解，则该问题没有最,优解。,五、标准型,LP,问题的解的概念,可行解,(Feasible Solution),：满足,（,2,）、（,3,）,的解；,最优解,(Optimal Solution),：满足,（,1,）,的可行解；,基,(Basis),：设 为,LP,问题的系数矩阵， 为,A,的非奇异子矩阵 ，则称,B,为,LP,问题,的一个基。,令,B = =( P,1, P,2, , P,m,),且,| B |, 0,，则称,P,j,(j=1,2,m),为,基向量,。,与基向量,P,j,对应的变量,x,j,称为,基变量,，,记为,X,B,= ( x,1, x,2, ,x,m,),T,，,其余的变量称为,非基变量,(Non-basic Variable),，记为,X,N,= ( x,m+1, x,m+2, ,x,m+n,),T,。,基变量,(Basic Variable),：,基解,(Basic Solution),令非基变量,X,N,= 0,，,求得的一组基变量,X,B,的值称为基解。,基可行解,(Basic Feasible Solution),（顶点）,满足非负条件的基解,(,既是基解，又是可行解,),。,基最优解,既是基解，又是使目标函数值达到最优的解,结论,:,基可行解数目 基解数目,线性规划标准型问题解的关系,约束方程的,解空间,基解,可行解,非可行解,基可,行解,10/3,2,4,4,x,1,x,2,x,1,+x,2,=4,3x,1,+5x,2,=10,第,2,节,LP,问题的基本理论,一、基本概念,二、基本定理,定理,1,LP,问题的可行域为凸集。,引理：,线性规划问题的可行解,X=(x,1,x,2,x,n,),T,是基,可行解的充要条件是,X,的正分量所对应的系数列向量是线性独立的。,必要性：由基可行解的定义可知。,定理,2,线性规划问题的基可行解对应于可行域的顶点。,定理,3,若可行域有界，则,LP,问题的目标函数一定可以在其可行域的顶点上达到最优。,重要结论,:,线性规划问题的所有可行解构成的集合（可行域）是凸集,(,定理,1);,凸集的每个顶点对应于一个基可行解,(,定理,2),基可行解,(,顶点,),的个数是有限的,;,若线性规划有最优解,必在可行域某顶点上达到,(,定理,3).,因此,我们可在有限个基可行解中寻找最优解,.,第,3,节 单纯形法,(Simplex Method),一、基本思想,化,LP,问题为标准型，,确定一个初始基可行解,检验解的,最优性,结束,Y,枢轴运算（旋转运算）,寻找另一个基可行解,N,要找到线性规划问题的最优解，只要在基可行解中寻找就可以了。虽然基可行解的数目是有限个（不超过,C,n,m,个），但当,m,n,较大时，要用,“,穷举法,”,求出所有基可行解也是行不通的。因此，必须寻求一种更有效的方法。,单纯形法的基本思路是：从线性规划问题的一个基可行解开始，转换到另一个使目标函数值增大的基可行解。反复迭代，直到目标函数值达到最大时，就得到了最优解。,按照单纯形法的思路求解线性规划问题,要解决三个问题,:,给出基可行解,; ,检验一个基可行解是否是最优解,; ,转换到另一个基可行解,.,把线性规划问题变成标准型后,观察是否每个约束方程中都有独有的、系数为,1,的变量,.,如果是,则取这些变量作为基变量,便得到一个基可行解,;,否则,就给没有这种变量的约束条件添加一个人工变量,同时修改目标函数,. (,见例题,),如果单纯形表最后一行中的,j,都满足,j,0,则对应的基可行解是最优解,;,否则就不是最优解,. ,j,称为检验数,.,第一,确定换入变量,.,在大于,0,的检验数中找最大的为,k,对应变量,x,k,为换入变量,.,第二,确定换出变量,.,取,=,minb,i,/a,ik,|a,ik,0=,b,l,/a,lk,对应的第,l,行的基变量为换出变量,.,第三,旋转运算,.,换入变量所在的行与换出变量所在的列交叉点的元素称为主元素,用高斯消去法把主元素化成,1,同列的其他元素化成,0,得到一个新的单纯形表,也就得到一个新的基可行解,.,化为标准型,单纯形表算法,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,8,16,12,1 2 1 0 0 4,4 0 0 1 0 -,0 4 0 0 1 3,0,2 3 0 0 0,以,4,为主元素进行旋转运算，,x,2,为换入变量，,x,5,为换出变量,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,3,X,2,2,16,3,1 0 1 0 -1/2 2,4 0 0 1 0 4,0 1 0 0 1/4 -,-9,2 0 0 0 -3/4,以,1,为主元素进行运算，,x,1,为换入变量，,x,3,为换出变量,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,2,X,1,0,X,4,3,X,2,2,8,3,1 0 1 0 -1/2 -,0 0 -4 1 2 4,0 1 0 0 1/4 12,-13,0 0 -2 0 1/4,以,2,为主元素进行运算，,x,5,为换入变量，,x,4,为换出变量,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,2,X,1,0,X,5,3,X,2,4,4,2,1 0 0 1/4 0,0 0 -2 1/2 1,0 1 1/2 -1/8 0,-14,0 0 -3/2 -1/8 0,此时达到最优解。,X,*,=(4,2),MaxZ,=14,。,化为标准型,单纯形表计算,C,j,2 1 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,15,24,5,0 5 1 0 0 -,6 2 0 1 0 4,1 1 0 0 1 5,2 1 0 0 0,以,6,为主元素进行旋转运算，,x,1,为换入变量，,x,4,为换出变量,C,j,2 1 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,2,X,1,0,X,5,15,4,1,0 5 1 0 0 3,1 1/3 0 1/6 0 12,0 2/3 0 -1/6 1 3/2,0 1/3 0 -1/3 0,以,2/3,为主元素进行运算，,x,2,为换入变量，,x,5,为换出变量,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,2,X,1,3,X,2,7.5,3.5,1.5,0 0 1 5/4 -15/2,1 0 0 1/4 -1/2,0 1 0 -1/4 3/2,0 0 0 -1/4 -1/2,此时达到最优解。,X,*,=(3.5,1.5),MaxZ,=8.5,。,用单纯形法求解线性规划问题的具体步骤如下：,找出初始可行基，确定初始基可行解，建立初始单纯形表；转。,检验对应于非基变量的检验数,j,。若,j,0,（,x,j,为非基变量）都成立，则已得最优解，停止计算；否则转。,在所有,j,0,中，若有一个,k,对应的,x,k,的系数,a,ik0 (i=1,2,m),，,则此问题为无界解（无解），停止计算；否则转。,根据,max,（,j,0,）,=,k,确定,x,k,为换入变量；根据,规则,minb,i,/a,ik,1im,a,ik,0,b,l,/a,lk,确定相应的换出变量，并得到主元素,a,lk,。,转。,以,a,lk,为枢轴元素进行转轴运算，得到新的单纯形表。转,.,用单纯,形,法求解线性规划问题后，应回答下面几个问题：,是否解无界？上面的步骤已作出回答。,是否无可行解？求解后，若人工变量都取,0,，则有可行解；否则，无可行解。,唯一最优解还是无穷多最优解？在最后的单纯形表中，若所有非基变量的检验数都严格小于,0,，则为唯一最优解；若存在某个非基变量的检验数等于,0,，则有无穷多最优解。,第,5,节 单纯形法的进一步讨论,一、人工变量法,1),人工变量的识别,2),目标函数的处理,3),计算,(,单纯形法,),（大,M,法，其中,M,为任意大的正数,),加入松弛变量,x,4,;,剩余变量,x,5,;,人工变量,x,6,x,7,C,j,-3,1,1,0,0,M,M,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,11,1,-2,1,1,0,0,0,11,M,x,6,3,-4,1,2,0,-1,1,0,3/2,M,x,7,1,-2,0,1,0,0,0,1,1,-3+6M,1-M,1-3M,0,M,0,0,0,x,4,10,3,-2,0,1,0,0,-1,-,M,x,6,1,0,1,0,0,-1,1,-2,1,1,x,3,1,-2,0,1,0,0,0,1,-,-1,1-M,0,0,M,0,3M-1,注意：,本例是求最小值，所以用所有 来判别目标函数是否实现了最小化。因而换入变量,x,k,的选取标准为,结果得,: X,*,=(4,1,9,0,0,0,0) Z,*,=-2,C,j,-3,1,1,0,0,M,M,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,12,3,0,0,1,-2,2,-5,4,1,x,2,1,0,1,0,0,-1,1,-2,-,1,x,3,1,-2,0,1,0,0,0,1,-,-1,0,0,0,1,M-1,M+1,-3,x,1,4,1,0,0,1/3,-2/3,2/3,-5/3,1,x,2,1,0,1,0,0,-1,1,-2,1,x,3,9,0,0,1,2/3,-4/3,4/3,-7/3,0,0,0,1/3,1/3,M-1/3,M-2/3,（接上表）,两阶段法,(,将,LP,问题分成两个阶段来考虑,),第,I,阶段,:,不考虑原问题是否存在可行解，给原,LP,问题加入人工变量，并构造仅含人工变量的目标函数和要求最小化；然后用单纯型法求解，若得,w=0,，,则进行第二阶段计算，否则无可行解。,第,II,阶段,：,将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。,加入松弛变量,x,4,;,剩余变量,x,5,;,人工变量,x,6,x,7,用,单纯形法求解第一阶段的结果得：,C,j,0,0,0,0,0,1,1,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,11,1,-2,1,1,0,0,0,11,1,x,6,3,-4,1,2,0,-1,1,0,3/2,1,x,7,1,-2,0,1,0,0,0,1,1,6,-1,-3,0,1,0,0,0,x,4,10,3,-2,0,1,0,0,-1,-,1,x,6,1,0,1,0,0,-1,1,-2,1,0,x,3,1,-2,0,1,0,0,0,1,-,0,-1,0,0,1,0,3,0,x,4,12,3,0,0,1,-2,2,-5,4,0,x,2,1,0,1,0,0,-1,1,-2,-,0,x,3,1,-2,0,1,0,0,0,0,-,0,0,0,0,0,1,1,此时，达到第一阶段的最优解，,W=0,C,j,-3,1,1,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,4,12,3,0,0,1,-2,4,1,x,2,1,0,1,0,0,-1,-,1,x,3,1,-2,0,1,0,0,-,-1,0,0,0,1,-3,x,1,4,1,0,0,1/3,-2/3,1,x,2,1,0,1,0,0,-1,1,x,3,9,0,0,1,2/3,-4/3,0,0,0,1/3,1/3,由于人工变量,x,6,=x,7,=0,所以（,0,1,1,12,0,）,T,是该线性规划问题的基可行解。于是转入第二阶段运算：,此时达到该,LP,问题的最优解：,x,1,=4,x,2,=1,x,3,=9;,目标函数值,Z=-2,。,二、单纯形法中存在的问题,1.,存在两个以上的最大正检验数。,选择任何变量（对应最大正检验数）作为进基变量。,2.,最小比值相同。,LP,问题出现退化现象，即基变量取值为,0,C,j,3/4 -20 1/2 -6 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,X,6,X,7,0,X,5,0,1/4,-8,-1,9,1,0,0,0,X,6,0,1/2,-12,-1/2,3,0,1,0,0,X,7,1,0,0,1,0,0,0,1,0,3/4,-20,1/2,-6,0,0,0,C,j,3/4 -20 1/2 -6 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,X,6,X,7,3/4,X,1,0,1,-32,-4,36,4,0,0,0,X,6,0,0,4,3/2,-15,0,1,0,0,X,7,1,0,0,1,0,0,0,1,0,0,4,7/2,21,-3,0,0,选取,x,1,为换入变量；按,Bland,算法，,选取下标最小的,x,5,为换出变量，得下表：,此时换出变量为,x,1,，,换入变量为,x,4,，,迭代后目标函数值不变，继而出现了循环现象，达不到最优解。,解决退化的方法有：,“摄动法”、“辞典序法”、,Bland,规则等,1974,年,Bland,提出,Bland,算法规则：,3.,最小比值原则失效,C,j,2,3,0,0,C,B,X,B,b,X,1,X,2,X,3,X,4,0,X,3,6,-2,0,1,1,3,X,2,4,-3,1,0,1,C,j,-Z,j,-12,11,0,0,-3,经过一次迭代后可得右表,4.,在最优表中出现某非基变量检验数为,0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,4,0,0,1,2/3,-1/3,4,X,2,6,0,1,0,1/2,0,3,X,1,4,1,0,0,-2/3,1/3,C,j,-Z,j,-36,0,0,0,0,-1,0,X,4,6,0,0,3/2,1,-1/2,4,X,2,3,0,1,-3/4,0,1/4,3,X,1,8,1,0,1,0,0,C,j,-Z,j,-36,0,0,0,0,-1,C,j,-Z,j,0,3,4,0,0,0,第五节 应用举例,例,1,某工厂要用三种原材料,C,、,P,、,H,混合调配出三种不同规格的产品,A,、,B,、,C,。,已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？,产品名称,规格要求,单价,(,元,/kg,）,A,原材料,C,不少于,50%,原材料,P,不,超过,25%,50,B,原材料,C,不少于,25%,原材料,P,不超过,50%,35,D,不限,25,原材料名称,每天最多供应量,(kg),单价,(,元,/kg),C,100,65,P,100,25,H,60,35,用单纯型法计算得结果,:,每天生产,A,产品,200kg,分别需要原料,:C,为,100kg;P,为,50kg;H,为,50kg.,总利润收入,Z=500,元,/,天,.,先,考虑一月份的线性规划模型,:,例,2,（书,P41,例,12,）,以,一月份内各种设备的生产能力总和为分母,生产产品所需要的各类设备的总台时数为分子,可计算出一月份的平均设备利用系数,Z,将,Z,作为目标函数,可得下面的模型,:,考虑二月份线性规划模型时,:(1),从全年计划中减去一月份已生产的数量,;(2),对批量小的产品,如一月份已经安排较大产量的,二月份将剩余部分安排生产,;(3),保证第,4,号产品在月底前交货,.,这样,我们可以依次对,12,个月列出线性规划模型并求解,再根据具体情况对计算结果进行必要调整,.,例,3,某部门在今后,5,年内连续给以下项目投资：,项目,A,，,第一年至第四年每年年初投资，次年末回收本利,115%,；,项目,B,，,第三年初投资，第五年末回收本利,125%,，最大投资额不超过,4,万元；,项目,C,，,第二年初投资，第五年末回收本利,140%,，最大投资额不超过,3,万元；,项目,D,，,五年内每年初可购买公债，当年末归还，并加利息,6%,。,该部门现有资金,10,万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？,1,2,3,4,5,A,x,1A,x,2A,x,3A,x,4A,B,x,3B,C,x,2C,D,x,1D,x,2D,x,3D,x,4D,x,5D,班次,时间,所需,人数,1,6:0010:00,60,2,10:0014:00,70,3,14:0018:00,60,4,18:0022:00,50,5,22:002:00,20,6,2:006:00,30,例,4,某公交线路每天各时段内所需司乘 人员数如下：,设所有的司乘人员分别在各时段的开始上班，并连续工作,8,小时，问该公交线路至少需配备多少司乘人员。列出该问题的线性规划模型。,单纯形法,例,1,，生产配比问题,某长拟生产甲、乙两种适销产品，每件利润分别为,3,，,5,百元。甲、乙产品的部件各自在,A,、,B,两个车间分别生产，每件甲、乙产品的部件分别需要,A,、,B,车间的生产能力,1,，,2,工时；两种产品的部件最后都要在,C,车间装配，装配每件甲、乙产品分别需要,3,，,4,工时。,A,、,B,、,C,三个车间每天可用于生产这两种产品的工时分别为,8,，,12,，,36,，应如何安排生产这两种产品才能获利最多？,下面用单纯形法来计算,（第,0,次迭代）,c,j,3,5,0,0,0,比值,基,解,x,1,x,2,x,3,x,4,x,5,0,x,3,8,1,0,1,0,0,0,x,4,12,0,0,1,0,12/2=6,(min),0,x,5,36,3,4,0,0,1,36/4=9,检验行,0,3,5,0,0,0,表,1,（第,1,次迭代）,c,j,3,5,0,0,0,比值,基,解,x,1,x,2,x,3,x,4,x,5,0,x,3,8,1,0,1,0,0,8,5,x,2,6,0,1,0,1/2,0,0,x,5,12,0,0,-2,1,4,（,min),检验行,30,3,0,0,-5/2,0,表,2,（第,2,次迭代）,c,j,3,5,0,0,0,比值,基,解,x,1,x,2,x,3,x,4,x,5,0,x,3,4,0,0,1,2/3,-1/3,5,x,2,6,0,1,0,1/2,0,3,x,1,4,1,0,0,-2/3,1/3,检验行,42,0,0,0,-1/2,-1,表3,解 先看有多少种裁料方案，再进行组合和选择。方案：,例,1,合理利用线材问题,现要做一百套钢管,每套要长为,2.9m,、,2.1m,和,1.5m,的钢管各一根。已知原料长,7.4m,，,问应如何下料，使用的原料最省。,设用方案,分别裁原料钢管,x,1,x,2,x,8,根,则：,Min z= x,1,+ x,2,+ x,3,+x,4,+ x,5,+x,6,+x,7,+x,8,2x,1,+ x,2,+x,3,+ x,4,100,2x,2,+x,3,+ 3x,5,+2x,6,+ x,7, 100,x,1,+ x,3,+3x,4,+2x,6,+3x,7,+4x,8, 100,x,1, x,2, x,3, x,4, x,5 ,x,6, x,7, x,8,0,例,2,某工厂要用三种原材料,C,P,H,混合调配出三种不同规格的产品,A,B,D,。,已知产品的规格要求、单价和原料的供应量、单价如下表。该厂应如何安排生产，能使利润最大？,根据产品要求有：,A,C,0.5A, A,P,0.25A,B,C,0.25B, B,P,0.5B,A,C,+A,P,+A,H,=A,B,C,+B,P,+B,H,=B,根据原料供应量有：,A,C,+B,C,+D,C,100,A,P,+B,P,+D,P,100,A,H,+B,H,+D,H,60,设,A,C,A,P,D,H,分别为,x,1,x,2,x,9,，,有,Max z=50(x,1,+x,2,+x,3,)+35(x,4,+x,5,+x,6,),+25(x,7,+x,8,+x,9,) - 65(x,1,+x,4,+x,7,),- 25(x,2,+x,5,+x,8,) - 35(x,3,+x,6,+x,9,),x,1,0.5(x,1,+ x,2,+ x,3,),x,2,0.25(x,1,+ x,2,+ x,3,),x,4,0.25(x,4,+ x,5,+ x,6,),x,5,0.5(x,4,+ x,5,+ x,6,),x,1,+ x,4,+ x,7,100,x,2,+ x,5,+ x,8,100,x,3,+ x,6,+ x,9,60,x,j,0, j=1,2,3,4,5,6,7,8,9,解：记产品,A,B,D,中,C,P,H,的含量分别为,A,C,A,P,A,H,B,C,B,P,B,H,D,C,D,P,D,H,。,例,3,成批生产企业年度生产计划的按月分配。,在年度计划按月分配时一般要考虑：从数量和品种上保证年度计划的完成；成批的产品尽可能集中在几个月内生产；由于技术方面的原因，某些产品在某个月后才能生产；某些产品要求年初交货；批量小的产品尽量集中在一个或几个月内生产出来，以便减少各月内的品种数量。考虑以上条件，使设备负荷均衡并使利用率最大化。,假定工厂有,m,类设备，用,i,表示,(i=1,2,m),；,生产,n,种产品，用,j,表示,(j=1,2,n),。,各产品的全年计划量用,d,j,表示。,用,a,ij,表示加工单位,j,种产品所需要的第,i,类设备的台时数，,b,ik,表示,k,月份第,i,类设备的生产能力,(,台时,)(k=1,2,12),。,再假定第,5,、,8,两种产品下半年投产，第,4,号产品要求二月底前完成全年计划。,如要对全年,12,个月同时考虑，会使模型非常复杂，我们根据上述条件从,1,月到,12,月份，一个月一个月地分别建模计算。设,k,月份计划生产,j,种产品的数量为,x,jk,。,一月份模型为：,m n m,Max z=(, a,ij,x,j1,) (b,i1,),i=1 j=1 i=1,n,a,ij,x,j1,b,i1,(i=1,2,m),j=1,x,j1,d,j,(j=1,2,n),x,51,=x,81,=0,x,j1,0 (j=1,2,n),二月份模型为：,m n m,Max z=(, a,ij,x,j2,) (b,i2,),i=1 j=1 i=1,n,a,ij,x,j2,b,i2,(i=1,2,m),j=1,x,j2,d,j,-x,j1,(j=1,2,n),x,52,=x,82,=0,x,j2,0 (j=1,2,n),例,4,连续投资问题。某单位有资金,10,万元，在今后,5,年内可考虑下列投资项目，已知：,项目,A,：,从第,1,到第,4,年每年初可投资，并于次年末回收本利,115%,；,项目,B,：第,3,年初需要投资，到第,5,年末回收本利,125%,，但最大投资额不超过,4,万元；,项目,C,：第,2,年初需要投资，到第,5,年末能回收本利,140%,，但最大投资额不超过,3,万元；,项目,D,：,5,年内每年初可购买公債，当年末回收本利,106%,。,问它应该如何安排每年的投资，使到,5,年末拥有的资金最多？,x,2A,+x,2C,+x,2D,=1.06x,1D,解：每年的投资额应不超过手中的资金。由于项目,D,每年都可投资，且当年末就可收回。所以该单位每年必然把资金全部投出去，即投资额等于手中的资金数。,设第,i,年投资各项目的资金为,x,iA,x,ib,x,iC,x,iD,。,数学模型为：,Max z=1.15x,4A,+1.4x,2C,+1.25x,3B,+1.06x,5D,x,1A,+x,1D,=10,x,3A,+x,3B,+x,3D,=1.15x,1A,+1.06x,2D,x,4A,+x,4D,=1.15x,2A,+1.06x,3D,x,5D,=1.15x,3A,+1.06x,4D,x,iA,x,ib,x,iC,x,iD,0,本章知识要点,1.,线性规划及数学模型；,2.,线性规划的标准型及如何化为标准型；,3.,线性规划问题的解,可行解、最优解、基、基向量与非基向量、基变量与非基变量、基解、基可行解、基最优解、最优基。,4.,解的几何意义,若,线性规划问题存在可行域，则是一个凸集,;,凸集的每个顶点对应于一个基可行解,;,若线性规划有有限最优解,必在可行域某顶点上达到,.,本章知识要点,5.,线性规划的求解方法,（,1,）,图解法（含,2,个决策变量）；,（,2,）单纯形法。,6.,单纯形法进一步讨论,（,1,）人工变量法（大,M,法）；,（,2,）两阶段法。,7.,最优性检验与解的判别（以极大化为例）,（,1,）唯一最优解；（,2,）无穷多最优解；,（,3,）无界解；（,4,）无可行解。,加入松弛变量,x,4,;,剩余变量,x,5,;,人工变量,x,6,x,7,例,1,：,C,j,-3,0,1,0,0,-M,-M,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,4,1,1,1,1,0,0,0,4,-M,x,6,1,-2,1,-1,0,-1,1,0,1,-M,x,7,9,0,3,1,0,0,0,1,3,-2M-3,4M,1,0,-M,0,0,0,x,4,3,3,0,2,1,1,-1,0,1,0,x,2,1,-2,1,-1,0,-1,1,0,-,- M,x,7,6,6,0,4,0,3,-3,1,1,6M-3,0,4M+1,0,3M,-4M,0,C,j,-3,1,1,0,0,M,M,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-3,x,1,1,1,0,2/3,1/3,1/3,-1/3,0,3,0,x,2,3,0,1,1/3,2/3,-1/3,1/3,0,-,-M,x,7,0,0,0,0,-2,1,-1,1,0,0,0,3,1-2M,1+M,-2M-1,0,-3,x,1,1,1,0,2/3,1,0,0,-1/3,3/2,0,x,2,3,0,1,1/3,0,0,0,1/3,9,0,x,5,0,0,0,0,-2,1,-1,1,-,0,0,3,3,0,-M,-M-1,（接上表）,最优解为,X,*,=(0,5/2,3/2,0,0,0,0) Z,*,=3/2,C,j,-3,1,1,0,0,M,M,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,1,x,3,3/2,3/2,0,1,3/2,0,0,-1/2,3,0,x,2,5/2,-1/2,1,0,-1/2,0,0,-,0,x,5,0,0,0,0,-2,1,-1,1,0,-9/2,0,0,-3/2,0,-M,1/2-M,（接上表）,此时，所有的检验数,已达到最优解，,两阶段法,(,将,LP,问题分成两个阶段来考虑,),第,I,阶段,:,不考虑原问题是否存在可行解，给原,LP,问题加入人工变量，并构造仅含人工变量的目标函数和要求最小化；然后用单纯形法求解，若得,w=0,，,则进行第二阶段计算，否则无可行解。,第,II,阶段,：,将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。,加入松弛变量,x,4,;,剩余变量,x,5,;,人工变量,x,6,x,7,解：第一阶段：,C,j,0,0,0,0,0,1,1,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,11,1,-2,1,1,0,0,0,11,1,x,6,3,-4,1,2,0,-1,1,0,3/2,1,x,7,1,-2,0,1,0,0,0,1,1,6,-1,-3,0,1,0,0,0,x,4,10,3,-2,0,1,0,0,-1,-,1,x,6,1,0,1,0,0,-1,1,-2,1,0,x,3,1,-2,0,1,0,0,0,1,-,0,-1,0,0,1,0,3,0,x,4,12,3,0,0,1,-2,2,-5,4,0,x,2,1,0,1,0,0,-1,1,-2,-,0,x,3,1,-2,0,1,0,0,0,0,-,0,0,0,0,0,1,1,此时，达到第一阶段的最优解，,W=0,C,j,-3,1,1,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,4,12,3,0,0,1,-2,4,1,x,2,1,0,1,0,0,-1,-,1,x,3,1,-2,0,1,0,0,-,-1,0,0,0,1,-3,x,1,4,1,0,0,1/3,-2/3,1,x,2,1,0,1,0,0,-1,1,x,3,9,0,0,1,2/3,-4/3,0,0,0,1/3,1/3,由于人工变量,x,6,=x,7,=0,所以（,0,1,1,12,0,）,T,是该线性规划问题的基可行解。于是转入第二阶段运算：,此时达到该,LP,问题的最优解：,x,1,=4,x,2,=1,x,3,=9;,目标函数值,Z=-2,。,11.,解：（,1,）,新的两个约束为：,C,j,a 2 1 -4,C,B,X,B,b,X,1,X,2,X,3,X,4,a,X,1,2,X,2,3+3b,1-b,1 0 1 -1,0 1 -1 0,0 0 3-a a-4,初始单纯形表为：,C,j,a 2 1 -4,C,B,X,B,b,X,1,X,2,X,3,X,4,a,X,1,2,X,2,3,1,1 0 1 -1,0 1 -1 0,0 0 3-a a-4,(2)b=0,若表中解为最优解，则检验数小于等于零。,C,j,3 2 1 -4,C,B,X,B,b,X,1,X,2,X,3,X,4,3,X,1,2,X,2,3+3b,1-b,1 0 1 -1,0