高等运筹刘巍大连海事大学.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,高等运筹学,大连海事大学,刘巍,第二篇 运筹学中的数学规划,第三章 线性规划,第四章 非线性规划,第五章 锥规划,第六章 矩阵规划,第七章 变分不等式与互补问题,第八章 整数规划,第九章 动态规划,第十章 向量优化（多目标优化）,线性规划模型,若干决策变量：如,x1,x2,xn,目标函数：关于决策变量的线性函数,约束条件：关于决策变量的线性不等式（或等式）,目的：在满足约束条件的决策变量中找出一组使目标函数达到最优的决策变量！,线性规划的一般模式,目标函数：,max(min)Z=c,1,x,1,+c,2,x2,+c,3,x,3,+c,n,x,n,约束条件：,a,11,x,1,+a,12,x,2,+a,13,x,3,+a,1n,x,n,(=)b,1,a,21,x,1,+a,22,x,2,+a,23,x,3,+a,2n,x,n,(=)b,2,a,m1,x,1,+a,m2,x,2,+a,m3,x,3,+a,mn,x,n,(=)b,n,非负性约束：,x,1,0,x,2,0,x,s,0,线性规划问题的数学模型,目标函数：,约束条件：,简写为：,向量形式：,其中：,矩阵形式：,其中：,线性规划问题的解,求解线性规划问题，就是从满足约束条件,(2),、,(3),的方程组中找出一个解，使目标函数,(1),达到最大值。,可行解,：满足约束条件、的解为可行解。所有可行解的集合为可行域。,最优解,：使目标函数达到最大值的可行解。,基：,设,A,为约束条件的,mn,阶系数矩阵,(mn),，其秩为,m,，,B,是矩阵,A,中,m,阶满秩子矩阵（,B0,），称,B,是规划问题的一个基。设：,称,B,中每个列向量,P,j,(j=1 2,m),为基向量。与基向量,P,j,对应的变量,x,j,为,基变量,。除基变量以外的变量为,非基变量,。,基解：,某一确定的基,B,，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非,0,值的个数不大于方程数,m,，基解的总数不超过,基可行解：,满足变量非负约束条件的基本解，简称基可行解。,可行基：,对应于基可行解的基称为可行基。,非可行解,可,行,解,基解,基可行解,线性规划的求解,自,1939,年苏联数学家康托罗维奇提出线性规划间题和,1947,年美国数学家丹齐格求解线性规划问题的通用方法一单纯形法以来，线性规划可以说是研究得最为透彻的一个研究方向。单纯形法统治线性规划领域达,40,年之久，而且至今仍是最好的应用最广泛的算法之一。虽然它在最坏情况具有指数复杂性，但在平均意义下已经证明是一个多项式算法。,目前，关于单纯形算法的研究主要在于如何选取主元。另一大类算法是内点法，它起源于,1979,年苏联数学家卡奇扬提出的多项式椭球算法，而因,1984,年美籍印度裔数学家卡玛卡提出的多项式时间算法而迅速成为国际热点，各式各样的算法大量涌现,:,仿射变换法、势函数方法、对数罚函数法、路径跟踪法、原始对偶法、不可行内点法等等。,目前线性规划的内点法也趋于成熟，这方面的研究者们目前大都致力于以线性规划作为特例的锥规划，以及如何利用线性规划松弛求解整数规划等方面的研究。然而，就线性规划而言，是否存在强多项式算法仍然是一个重要且困难的理论问题。,连接几何形体中任意两点的线段仍完全在该几何形体之中。,有限个凸集的交集仍然是凸集。,单纯形法基本原理,单纯形法基本原理,凸集：如果集合,C,中任意两个点,X,1,、,X,2,，其连线上的所有点也都是集合C,中的点，称,C,为凸集。,凸集,凸集,不是凸集,顶 点,顶点：如果凸集,C,中不存在任何两个不同的点,X,1,，,X,2,，使,X,成为这两个点连线上的一个点,单纯形法基本原理,定理,1,：若线性规划问题存在可行解，则该问题的可行域是凸集。,定理,2,：线性规划问题的基可行解,X,对应可行域,(,凸集,),的顶点。,定理,3,：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）,单纯形法的计算步骤,单纯形法的思路,找出一个初始可行解,是否最优,转移到另一个基本可行解,（找出更大的目标函数值）,最优解,是,否,循,环,核心是：变量迭代,结束,单纯形法的进一步讨论人工变量法人工变量法：,前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为,人工变量,，构成的可行基称为,人工基,，用,大,M,法,或,两阶段法,求解，这种用人工变量作桥梁的求解方法称为,人工变量法,。,二、线性规划应用,应用问题,线性规划的应用,1,人力资源分配的问题,2,生产计划的问题,3,套裁下料问题,4,配料问题,5,投资问题,人力资源分配的问题,例,1,某昼夜服务的公交线路每天各时间段内所需司机,和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并,连续工作八小时，问该公交线路怎样安排司机和乘务人员，,既能满足工作需要，又配备最少司机和乘务人员,?,人力资源分配的问题,解：设,x,i,表示第,i,班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。,目标函数：,Min Z=,x,1,+,x,2,+,x,3,+,x,4,+,x,5,+,x,6,约束条件：,s.t.,x,1,+,x,6,60,x,1,+,x,2,70,x,2,+,x,3,60,x,3,+,x,4,50,x,4,+,x,5,20,x,5,+,x,6,30,x,1,x,2,x,3,x,4,x,5,x,6,0,2,生产计划的问题,例,2,某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,生产计划的问题,解：设,x,1,x,2,x,3,分别为三道工序都由本公司加工的甲、乙、丙三种,产品的件数，,x,4,x,5,分别为由外协铸造再由本公司加工和装配的甲、乙两,种产品的件数。,求,x,i,的利润：利润,=,售价,-,各成本之和,产品甲全部自制的利润,=23-(3+2+3)=15,产品甲铸造外协，其余自制的利润,=23-(5+2+3)=13,产品乙全部自制的利润,=18-(5+1+2)=10,产品乙铸造外协，其余自制的利润,=18-(6+1+2)=9,产品丙的利润,=16-(4+3+2)=7,可得到,x,i,（,i=1,2,3,4,5,）的利润分别为,15,、,10,、,7,、,13,、,9,元。,生产计划的问题,通过以上分析,可建立如下的数学模型,:,目标函数,：,Max f=15,x,1,+10,x,2,+7,x,3,+13,x,4,+9,x,5,约束条件,：,5,x,1,+10,x,2,+7,x,3,8000,6,x,1,+4,x,2,+8,x,3,+6x,4,+4,x,5,12000,3,x,1,+2,x,2,+2,x,3,+3,x,4,+2,x,5,10000,x,1,x,2,x,3,x,4,x,5,0,3,套裁下料问题,例,5,某工厂要做,100,套钢架，每套用长为,2.9 m,2.1 m,1.5 m,的圆钢各,一根。已知原料每根长,7.4 m,，问：应如何下料，可使所用原料最省？,解：共可设计下列,5,种下料方案，见下表,设,x,1,x,2,x,3,x,4,x,5,分别为上面,5,种方案下料的原材料根数。这样我们建立如下的数学模型。,目标函数：,Min z=,x,1,+,x,2,+,x,3,+,x,4,+,x,5,约束条件：,s.tx,1,+2,x,2,+,x,4,100,2,x,3,+2,x,4,+,x,5,100,3,x,1,+,x,2,+2,x,3,+3,x,5,100,x,1,x,2,x,3,x,4,x,5,0,用计算软件计算得出最优下料方案：按方案,1,下料,30,根；按方案,2,下料,10,根；按方案,4,下料,50,根。,即,x,1,=30;,x,2,=10,；,x,3,=0,；,x,4,=50,；,x,5,=0,；,只需,90,根原材料就可制造出,100,套钢架。,注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。,套裁下料问题,4,配料问题,例,6,某工厂要用三种原料,1,、,2,、,3,混合调配出三种不同规格的,产品甲、乙、丙，数据如右表。,问：该厂应如何安排生产，使利,润收入为最大？,解：设,x,ij,表示第,i,种（甲、乙、丙）产品中原料,j,的含量。这样我们建立数学模型时，要考虑：,对于甲：,x,11,，,x,12,，,x,13,；,对于乙：,x,21,，,x,22,，,x,23,；,对于丙：,x,31,，,x,32,，,x,33,；,对于原料,1,：,x,11,，,x,21,，,x,31,；,对于原料,2,：,x,12,，,x,22,，,x,32,对于原料,3,：,x,13,，,x,23,，,x,33,；,目标函数：利润最大，利润,=,收入,-,原料支出,约束条件：规格要求,4,个；,供应量限制,3,个。,配料问题,利润,=,总收入,-,总成本,=,甲乙丙三种产品的销售单价*产品数量,-,甲乙丙使用的原料单价*原料数量，故有,目标函数,Max f=50,（,x,11,+,x,12,+,x,13,）,+35,（,x,21,+,x,22,+,x,23,）,+25,（,x,31,+,x,32,+,x,33,）,-65,（,x,11,+,x,21,+,x,31,）,-25,（,x,12,+,x,22,+,x,32,）,-35,（,x,13,x,23,+,x,33,）,=-15,x,11,+25,x,12,+15,x,13,-30,x,21,+10,x,22,-40,x,31,-10,x,33,约束条件：,从第,1,个表中有：,x,11,0.5(,x,11,+,x,12,+,x,13,),x,12,0.25(,x,11,+,x,12,+,x,13,),x,21,0.25(,x,21,+,x,22,+,x,23,),x,22,0.5(,x,21,+,x,22,+,x,23,),配料问题,从第,2,个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有,(,x,11,+,x,21,+,x,31,)100,(,x,12,+,x,22,+,x,32,)100,(,x,13,+,x,23,+,x,33,)60,通过整理，得到以下模型：,配料问题,例,6,（续）,目标函数：,Max f=-15,x,11,+25,x,12,+15,x,13,-30,x,21,+10,x,22,-40,x,31,-10,x,33,约束条件：,s.t.0.5,x,11,-0.5,x,12,-0.5,x,13,0,（原材料,1,不少于,50%,）,-0.25,x,11,+0.75,x,12,-0.25,x,13,0,（原材料,2,不超过,25%,）,0.75,x,21,-0.25,x,22,-0.25,x,23,0,（原材料,1,不少于,25%,）0.5,x,21,+0.5,x,22,-0.5,x,23,0,（原材料,2,不超过,50%,）,x,11,+,x,21,+,x,31,100 (,供应量限制）,x,12,+,x,22,+,x,32,100 (,供应量限制）,x,13,+,x,23,+,x,33,60 (,供应量限制）,x,ij,0 ,i=1,2,3;j=1,2,3,例,8,某部门现有资金,200,万元，今后五年内考虑给以下的项目投资。已知：项,目,A,：从第一年到第五年每年年初都可投资，当年末能收回本利,110%,；项目,B,：从第,一年到第四年每年年初都可投资，次年末能收回本利,125%,，但规定每年最大投资额,不能超过30,万元；项目,C,：需在第三年年初投资，第五年末能收回本利,140%,，但规,定最大投资额不能超过,80,万元；项目,D,：需在第二年年初投资，第五年末能收回本,利,155%,，但规定最大投资额不能超过,100,万元。,据测定每万元每次投资的风险指数如右表：,问：,a,）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？,b,）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在,330,万元的基础上使得其投资总的风险系数为最小？,解：,1,）,确定决策变量：连续投资问题,设,x,ij,(i=1,5,，,j=1,4),表示第,i,年初投资于,A(j=1),B(j=2),、,C(j=3),、,D(j=4),项目的金额。这样我们建立如下的决策变量：,A x,11,x,21,x,31,x,41,x,51,B x,12,x,22,x,32,x,42,C,x,33,D,x,24,投资问题,2,）约束条件：,第一年：,A,当年末可收回投资，故第一年年初应把全部资金投出去，于是,x,11,+,x,12,=200,；,第二年：,B,次年末才可收回投资，故第二年年初有资金,1.1,x,11,，于是,x,21,+,x,22,+,x,24,=1.1,x,11,；,第三年：年初有资金,1.1,x,21,+1.25,x,12,，于是,x,31,+,x,32,+,x,33,=1.1,x,21,+1.25,x,12,；,第四年：年初有资金,1.1,x,31,+1.25,x,22,，于是,x,41,+,x,42,=1.1,x,31,+1.25,x,22,；,第五年：年初有资金,1.1,x,41,+1.25,x,32,，于是,x,51,=1.1,x,41,+1.25,x,32,；,B,、,C,、,D,的投资限制：,x,i2,30(i=1,、,2,、,3,、,4),，,x,33,80,，,x,24,100,3,）目标函数及模型：,a),Max z=1.1,x,51,+1.25,x,42,+1.4,x,33,+1.55,x,24,s.t.,x,11,+,x,12,=200,x,21,+,x,22,+,x,24,=1.1,x,11,；,x,31,+,x,32,+,x,33,=1.1,x,21,+1.25,x,12,；,x,41,+,x,42,=1.1,x,31,+1.25,x,22,；,x,51,=1.1,x,41,+1.25,x,32,；,x,i2,30(i=1,、,2,、,3,、,4),，,x,33,80,，,x,24,100,x,ij,0 (i=1,、,2,、,3,、,4,、,5,；,j=1,、,2,、,3,、,4,）,投资问题,b),所设变量与问题,a,相同，目标函数为风险最小，有,Min f=,x,11,+,x,21,+,x,31,+,x,41,x,51,+3(,x,12,+,x,22,+,x,32,+,x,42,)+4,x,33,+5.5,x,24,在问题,a,的约束条件中加上,“,第五年末拥有资金本利在,330,万元,”,的条件，,于是模型如下：,Min f=(,x,11,+,x,21,+,x,31,+,x,41,+,x,51,)+3(,x,12,+,x,22,+,x,32,+,x,42,)+4,x,33,+5.5,x,24,s.t.,x,11,+,x,12,=200,x,21,+,x,22,+,x,24,=1.1,x,11,；,x,31,+,x,32,+,x,33,=1.1,x,21,+1.25,x,12,；,x,41,+,x,42,=1.1,x,31,+1.25,x,22,；,x,51,=1.1,x,41,+1.25,x,32,；,x,i2,30(i=1,、,2,、,3,、,4),，,x,33,80,，,x,24,100,1.1,x,51,+1.25,x,42,+1.4,x,33,+1.55,x,24,330,x,ij,0 (i=1,、,2,、,3,、,4,、,5,；,j=1,、,2,、,3,、,4,）,投资问题,三、线性规划的对偶问题,再谈招聘总经理,案 例 （一）,泰山股份公司可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,目前生产现状：,不生产产品,A,，生产产品,B,每天,30,，获利,3600,产品,A,产品,B,资源限量,设 备,劳动力,原材料,9,4,3,4,5,10,360,200,300,利润,元,/kg,70,120,招聘总经理！,约翰：我应聘！,在现有资源状况下，可以使利润达到,4200,以上！,方案是：生产,A,产品,20,，生产,B,产品,24,可行性：,9*20+4*24=276,0,c,s,Min,j,/a,sj,a,sj,0,b,r,Min-b,i,/a,ir,a,ir,0,灵敏度分析（续）,A,中元素发生变化,（只讨论,N,中某一列变化情况）,与增加变量,x,n+1,的情况类似，假设,p,j,变化。那么，重新计算出,B,-1,p,j,j,=,c,j,-c,ri,a,ri j,填入最优单纯形表，若,j,0,则最优解不变；否则，进一步用单纯形法求解。,灵敏度分析（续）,可得最优解：,x*=(3.2,0.8,0,0,2.4),T,f*=15.2,灵敏度分析（续）,灵敏度分析小结：,1 C,i,发生变化,2 B,j,发生变化,3 A,中元素发生变化,返回目录,第二讲结束,