第1章：线性规划.ppt

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章：线性规划,1.1,线性规划,(Linear,Programing,-L.P.),概述,一、,L.P.,概念：,L.P.,是目前应用最广泛的一种系统优化方法。其理论已十分成熟，广泛应用于工农业生产,和经济管理等领域。,以数学为工具，在一定资源条件下，如何合理安排，取得最大经济效果。,二、发展史：,30,年代末,(,苏,),康特罗维奇书“生产组织与计划中的数学方法”，,为,L.P.,建立数学模型和求解奠定了基础。,1,、,(,美,),库普曼,(T.C.,Koopmans,),建立了,L.P.,数学模型，获诺贝经济奖。,2,、,(,美,),丹泽,(G.B.,Dantzig,),在,1947,年,提出求解,L.P.,数模的通用方法,-,单纯形法。,1946,年，世界上第一台计算机问世，使单纯形法处理大规模,L.P.,数模成为可能。,三、,L.P.,问题的求解过程,1,、将实际问题转化为数学模型,(,数学公式,),：建模。,2,、求解数学模型：,图解法：适合于,2,个变量的,L.P.,数学模型。,单纯形法：适合于任意个变量的,L.P.,数学模型。,3,、利用数学模型的最优解获得原问题的最优决策方案。,1,1.2,线性规划及其数学模型,一、,L.P.,问题,例：,某厂生产甲、乙两种产品，均需在,A,、B,、,C,三种不同的设备上加工，产品加工所需工时、,销售后能获得的利润及设备有效工时数如下表。问：如何安排生产计划，才能使该厂获,得总利润最大？,解,:,设,甲、乙产品产量分别为,x,1,、,x,2,公斤,决策变量，简称变量,设总利润为,Z,，,则,Max Z=70,x,1,30 x,2,目标函数,设备可用工时数限制,约束条件,s.t.3x,1,+9x,2,540 A,设备,可用工时,约束,5x,1,+5x,2,450 B,设备,可用工时,约束,9x,1,+3x,2,720 C,设备,可用工时,约束,x,1,x,2,0,非负约束,设备,产品,A,B,C,利润,(,元,/,公斤,),甲,乙,3,9,5,5,9,3,70,30,限制工时,540,450,720,单耗,2,二,、,L.P.,数学模型的经济含义,1,、数学模型的三要素,:,.,有一组待确定的决策变量。如,(x,1,x,2,),为一个具体行动方案。,.,有一个明确的目标要求,(Max,或,Min),。,如要求利润最大。,.,存在一组约束条件。如设备,A,、,B,、,C,三种资源的约束。,2,、数学模型中系数的含义,:,.,目标函数中决策变量的系数,70,30 -,叫价值系数，表单位产品提供的利润,(,元,/,件,),；,.,约束条件左边决策变量的系数,-,叫约束条件系数或单耗,(,台时、,kg,、,kg/,件,),；,.约束条件右边常数,540,450,720 -,叫限制常数，表现有的资源限量。,三、线性规划数学模型的解,1,、可行解：满足约束条件,、,、,、,的所有解。,2,、可行解域：所有可行解的集合，上图阴影部分。,3,、最优解：满足目标函数,的可行解。,4,、基本解：所有约束条件直线的交点对应的解，,即上图所有的实心点和空心点对应的解。,5,、基本可行解：既是基本解又是可行解，,即上图所有的实心点对应的解。,它满足两个,条件：,其一是约束条件直线的交点对应的解；,其二是可行解，即满足所有的约束条件，,在可行解域内。,o,X,1,X,2,a,h,b,k,Max Z=70,x,1,30 x,2,s.t.3x,1,+9x,2,540 ,5x,1,+5x,2,450 ,9x,1,+3x,2,720 ,x,1,x,2,0 ,3,1,、,线性规划模型：如果以上数学模型中的方程均是线性方程，,则该数模称为线性规划数模。,2,、,非线性规划模型：如果以上数学模型中的方程至少有一个方程是非线性方程，,则该数模称为非线性规划数模。,四,、,L.P.,的一般形式,Max(Min)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,a,21,x,1,+a,22,x,2,+-+a,2n,x,n,(,=)b2,s.t.-,a,m1,x,1,+a,m2,x,2,+-+,a,mn,x,n,(,=),b,m,x,j,0,j=1-n,4,1.3,线性规划问题的建模,确定决策变量；确定目标函数；列出约束条件。,一、运输问题建模,:,编制最优运输计划,使总运费最少,例：某地有三个有色金属矿,A1,、,A2,、,A3,，,生产同一种金属矿石，,A1,矿的年产量为,100,万吨，,A2,矿为,80,万吨，,A3,矿为,50,万吨。矿石全部供应四个冶炼厂，,B1,厂的全部需求量为,50,万吨，,B2,厂,70,为万吨，,B3,厂为,80,万吨，,B4,厂为,30,万吨。产量恰好等于总需求量，矿石由各矿山,运到冶炼厂的单位运价已知，如下表。问如何安排运输，使各矿山的矿石运到冶炼厂，,满足各厂的需要，且运输费用最小，,试建立该问题的数学模型,？,.,确定决策变量,:,设,x,ij,为从第,i,个矿山到第,j,个冶炼厂,的矿石运输量,(,万,t).,.,确定目标,函数,:,设总运费为,Z,则,Min Z=1.5x,11,+2x,12,+0.3x,13,+3x,14,+,7x,21,+0.8x,22,+1.4x,23,+2x,24,+1.2x,31,+0.3x,32,+2x,33,+2.5x,34,.,确定约束条件,:,x,11,+x,12,+x,13,+x,14,=100,s.t.x,21,+x,22,+x,23,+x,24,80,x,31,+x,32,+x,33,+x,34,=50,x,11,+x,21,+x,31,=50,x,12,+x,22,+x,32,=70,x,13,+x,23,+x,33,=80,x,14,+x,24,+x,34,=30,x,ij,0 ,i=13;j=14.,5,二、合理下料问题建模,:,寻求最佳下料方式,使余料最少,.,例 有一批长度为,180,公分的钢管,需截成,70,、,52,和,35,公分三种管料。它们的需求量应分别不少于,100,、,150,和,100,个。问应如何下料才能使钢管的余料为最少,?,解,:,.,确定决策变量,:,设,x,j,为第,j,种下料方式所用的钢管根数,.确定目标,函数,:,设总余料为,Z,则,Min Z=5x,1,+6x,2,+23x,3,+5x,4,+24x,5,+6x,6,+23x,7,+5x,8,(,公分,),.,确定约束条件,:,2x,1,+x,2,+x,3,+x,4,100,s.t.2x,2,+x,3,+3x,5,+2x,6,+x,7,150,x,1,+x,3,+3x,4,+2x,6,+3x,7,+5x,8,100,x,j,0 ,且为整数,.,6,三、人员分派问题建模,:,合理分派人员,使总效率最大,.,例：,设有四件工作分派给四个人来做，每项工作只能由一人来做，每个人只能做一项工作。,希望适当安排人选，发挥各人特长又能使总的效率最大,(,或完成最快,或费用最少,),。,表,1.5,表示各人对各项工作所具有的工作效率。,.,确定决策变量,:,设,x,ij,为分派第,i,个人从事第,j,项工作,x,ij,=1,0(,分派与否,),.,确定目标,函数,:,设总效率为,Z,则,Max Z=0.6x,11,+0.2x,12,+0.3x,13,+0.1x,14,+0.7x,21,+0.4x,22,+0.3x,23,+0.2x,24,+0.8x,31,+1.0 x,32,+0.7x,33,+0.3x,34,+0.7x,41,+0.7x,42,+0.5x,43,+0.4x,44,.,确定约束条件,:,x,11,+x,12,+x,13,+x,14,=1,s.t.x,21,+x,22,+x,23,+x,24,=1,x,31,+x,32,+x,33,+x,34,=1,x,41,+x,42,+x,43,+x,44,=1,x,11,+x,21,+x,31,+x,41,=1,x,12,+x,22,+x,32,+x,42,=1,x,13,+x,23,+x,33,+x,43,=1,x,14,+x,24,+x,34,+x,44,=1,x,ij,=1,0 ,i=14;j=14.,7,四、投资方案选择问题建模,:,合理选择方案,使总收益最大,.,例：,某炼油公司为提高炼油能力和增加企业经济效益,经研究有五种技术改造的投资方案可供选择，,它们所需的投资费用年收益如下表所示,。,其中,:,方案,1,和方案,2,只能选择其中一种，不能兼而实现，,并且，如选择方案,2,，则方案,3,必须同时选择，或者都不选择,。,现该公司可供支配的资金总额为：第一年有,650,万元，第二年仅有,460,万元,。技术改造的结果,要求至少应增加出油能力,500,桶,/,天，但又不得超过,1100,桶,/,天，试确定该公司总经济效益最大的,投资方案。,8,.,确定决策变量,:,设,x,j,为第,j,方案的取舍，,x,j,=1,0(,取舍,),.,确定目标,函数,:,设总经济效率为,Z,则,Max Z=100 x,1,+200 x,2,+50 x,3,+30 x,4,+20 x,5,(,万元,),.,确定约束条件,:,200 x,1,+300 x,2,+150 x,3,+100 x,4,+50 x,5,650,s.t.200 x,1,+150 x,2,+50 x,3,+70 x,4,+40 x,5,460,500 x,1,+1000 x,2,+100 x,3,+50 x,4,+20 x,5,500,500 x,1,+1000 x,2,+100 x,3,+50 x,4,+20 x,5,1100,x,1,+x,2,1,-x,2,+x,3,=0,x,j,=0,1,j=15.,9,五、选点决策问题,:,合理选点,使总利率最大,.,例：,某公司拟在,A,、B,、,C,、,D,、,E,五个城市中建立若干产品经销联营点，各处设点都需资金、人力、设备等，需求量以及能提供的利润各处不同，有些点可能亏本，但却能获得贷款和人力等。假设数据已知，见下表，为使总利润最大，问厂方应作何种最优选点决策？,.,确定决策变量：要求从五个城市中选择最优,产品经销联营点，设决策变量,x,j,(j,=1,2,5),表示第,j,个城市的取舍，所以决策变量,xj,的取,值仅有,1,和,0,两种值。,.,确定目标,函数,：要求公司总利润,Z,最大，则,Max Z,4.5x,1,3.8x,2,9.5x,3,2x,4,1.5x,5,.,确定约束条件,:,4x,1,6x,2,12x,3,8x,4,x,5,20,s.t.5x,1,4x,2,12x,3,3x,4,8,x,5,15,x1,x2,x3 2,x,j,0,、,1,，,j=1,5,资源,城市,应投资,(,百万元,),应投人力,（人）,应投设备,（套）,利润,(,万元,),A,4,5,1,45,B,6,4,1,38,C,12,12,1,95,D,-8,3,0,-2,E,1,-8,0,-1.5,资源限量,20,15,2,10,1.4,线性规划图解法,一、,适用范围：,二个变量的数学模型。,二、,求解步骤：,Max Z=70,x,1,30 x,2,s.t.3x,1,+9x,2,540 ,5x,1,+5x,2,450 ,9x,1,+3x,2,720 ,x,1,x,2,0 ,o,X,1,X,2,a,h,b,k,70,30,(75,15),最优解,为：,X*=(,75,，,15,),T,Z*=5700,第二步：确定可行解域，即所有约束方程图形的公共部分；,第三步：绘出目标函数直线，根据目标函数的要求以及与决策变量的关系，找出直线移动方向。,第五步：确定最优解及最优目标函数值。,第一步：将所有约束方程用图形绘出；,第四步：,目标函数直线向着可行解域的右上方平行移动，直至与可行解域相切为止，,这个切点就是最优点，对应的解就是最优解。,所以，产品,甲、乙分别安排产量,75Kg,、,15Kg,，可使工厂获利最大为,5700,元11,三、,LP,几何意义,o,X,1,X,2,a,h,b,k,1,、闭合的可行解域是凸多边形,(,凸集,),。,2,、可行解域有若干个顶点：,O,、,a,、,h,、,k,、,b,。,对应的解叫基本,可行,解,。,3,、最优解若唯一存在，则必是顶点中的某一个。,12,四、特殊的数学模型,1,、有无穷多个最优解：若有两个最优解，则必有无穷多个最优解。如下例数学模型：,Max Z=,x,1,2x,2,s.t.x,1,+x,2,6,x,1,+2x,2,8,x,2,3,x,1,x,2,0,O,X,1,X,2,Q,1,Q,2,Q,3,Q,4,此线性规划问题的最优解在,Q,2,Q,3,线段上，如上图所示，即线段,Q,2,Q,3,上任意一点都使,Z,取得相同的最大值，这个线性规划问题有无穷多最优解。,因此，若有两个最优解，则必有无穷多个最优解。,13,四、特殊的数学模型,2,、解无界：可行解域无界，目标值无限增大。如下例数学模型：,Max Z=,x,1,x,2,s.t,.-2x,1,+x,2,4,x,1,-5x,2,2,x,1,x,2,0,O,X,1,X,2,用图解法求解结果见上图所示，从图中可以看到，该问题可行解域无界，目标函数值可,以增大到无究大，称这种情况为无界解或无最优解。,14,四、特殊的数学模型,3,、无可行解域：约束条件相互矛盾。如下例数学模型,Max Z=3,x,1,4x,2s.t.x,1,+x,2,6,x,1,2,x,2,3,x,1,x,2,0,2,O,X,1,X,2,6,3,6,该问题可行解域为空集，如上图所示，即无可行解域，当然也无最优解。,15,1.5,线性规划单纯形法,一、,适用范围,任意个变量的数学模型。,二、原理,从一初始顶点,(,初始基本可行解,),出发，沿可行解域的边缘逐个验算遇到的顶点,(,基本可行解,),，,直至找最优点,(,最优解,),为止。,Max Z=70,x,1,30 x,2,s.t.3x,1,+9x,2,540 ,5x,1,+5x,2,450 ,9x,1,+3x,2,720 ,x,1,x,2,0 ,o,X,1,X,2,a,h,b,k,最优解,为：,X*=(,75,，,15,),T,Z*=5700,16,三、,LP,数模的标准型,条件一,:,具有等式约束方程组；,条件二,:,右边常数非负；,条件三,:,变量非负；,条件四,:,目标函数为,Max,型。,Max Z=70,x,1,30 x,2,s.t.3x,1,+9x,2,540 ,5x,1,+5x,2,450 ,9x,1,+3x,2,720 ,x,1,x,2,0 ,对设备,A,：,3x,1,+9x,2,540,，,引入非负松弛变量,x,3,，,加到不等式的左边得,3x,1,+9x,2,+,x,3,=540,实际使用的,空闲工时,(,0),限制工时,工时数,(,起松弛作用,叫松弛变量,),Max Z=70,x,1,30 x,2,s.t.3x,1,+9x,2,+,x,3,=540,5x,1,+5x,2,+,x,4,=450,9x,1,+3x,2,+,x,5,=720,x,j,0,，,j=1,5,则原数模的标准型为：,对设备,B,：,5x,1,+5x,2,450,，,引入非负松弛变量,x,4,，,加到不等式的左边得,5x,1,+5x,2,+,x,4,=450,实际使用的,空闲工时,(,0),限制工时,工时数,(,起松弛作用,叫松弛变量,),对设备,C,：,9x,1,+3x,2,720,，,引入非负松弛变量,x,4,，,加到不等式的左边得,9x,1,+3x,2,+,x5,=720,实际使用的,空闲工时,(,0),限制工时,工时数,(,起松弛作用,叫松弛变量,),17,四、,LP,数模的规范型,条件一,:,具有,标准型,；,条件二,:,约束方程组系数矩阵中含有至少一个单位,子矩阵,(,对应的变量叫基变量,),；,条件三,:,目标函数中不含基变量。,Max Z=70,x,1,30 x,2,s.t.3x,1,+9x,2,+,x,3,=540,5x,1,+5x,2,+,x,4,=450,9x,1,+3x,2,+,x,5,=720,x,j,0,，,j=1,5,；,x,3,x,4,x,5,为基变量,则原数模的规范型为：,Max Z=70,x,1,30 x,2,s.t3x,1,+9x,2,+,x,3,=540,5x,1,+5x,2,+,x,4,=450,9x,1,+3x,2,+,x,5,=720,x,j,0,，,j=1,5,x,3,x,4,x,5,3 9 1 0 0 1 0 0,A=5 5 0 1 0,中有,B=0 1 0 =,（,3,、,4,、,5,）,=,E,9 3 0 0 1 0 0 1,一组,基,1,2,3,4,5,x,1,x,2,x,3,x,4,x,5,非基变量 基变量,基的作用是,:,可以得到初始基本可行解,(,即初始顶点,-,通常是原点,O),是单纯行迭代的基础。,18,五、最优解寻求步骤,第一步、,确定初始基本可行解：利用,规范型数模，令非基变量,x,1,、,x,2,=0,，,求出,基变量,x,3,、,x,4,、,x,5,。,得初始基本可行解为：,X,(1)=,（,x,1,x,2,x,3,x,4,x,5,）,T,=(,0,0,540,450,720,),T,甲 乙,设备,A,设备,B,设备,C,空闲工时,Z,(1)=,0,，,利润为,0,未生产,，,资源全部闲置,(,对应原点,O,),(x,1,、,x,2,为非,基变量，,x,3,、,x,4,、,x,5,为,基变量,),第二步、,判断,X,(1),是否最优：检查用非,基变量表达的目标函数中,非,基变量前的系数,(,叫检验数,),。,Max Z =,70,x,1,+,30,x,2,因为,检验数,70,、,30,0,，所以当,x,1,和,x,2,从,0,增大时，,Z,也会增大。,故,当前解非最优。当前解须改进，寻求更好的解。,o,X,1,X,2,a,h,b,k,Max Z=70,x,1,30 x,2,s.t.3x,1,+9x,2,+,x,3,=540,5x,1,+5x,2,+,x,4,=450,9x,1,+3x,2,+,x,5,=720,x,j,0,，,j=1,5,；,x,3,x,4,x,5,为基变量,19,第三步、,确定改进的非基变量及其上界,:,选择使目标,Z,值改变得最快的,非基变量优先改进。,(1),、,确定非基变量,x,1,优先改进：因为从目标函数,Max Z =,70,x,1,+,30,x,2,可以看出,x,1,增加,1,，可使目标,Z,增加,70,；,x,2,增加,1,，目标,Z,能增加,30,。,(2),、,x,1,增加的上界是,80,：,因为从约束方程组,可以得出,(,从资源最优利用考虑，令,x,3,、,x,4,、,x,5,=0,),x,1,=180-3 x,2,-(1/3)x,3,=180 -,目前可用的设备,A,台时数最多可生产甲产品,180Kg,。,x,1,=90 -x,2,-(1/5)x,4,=90 -,目前可用的设备,B,台时数最多可生产甲产品,90Kg,。,x,1,=80 -(1/3)x,2,-(1/9)x,5,=80 -,目前可用的设备,C,台时数最多可生产甲产品,80Kg,。,取最小值即,非基变量,x,1,增加的上界是,80 -,最小比值规则。此时,x,2,=0,。,第四步、,确定新解：将,x,1,=80,，,x,2,=0,代入约束方程组中求出,x,3,、,x,4,、,x,5,的值。,得新基本可行解为：,X,(2)=,（,x,1,x,2,x,3,x,4,x,5,）,T,=,（,80,0,300,50,0,）,T,甲 乙,设备,A,设备,B,设备,C,空闲工时,(,对应点,a,),Z,(2)=,5600,，,利润为,5600 (x,2,、,x,5,为非,基变量，,x,1,、,x,3,、,x,4,为,基变量,),Max Z=70,x,1,30 x,2,s.t.3x,1,+9x,2,+,x,3,=540,5x,1,+5x,2,+,x,4,=450,9x,1,+3x,2,+,x,5,=720,x,j,0,，,j=1,5,；,x,3,x,4,x,5,为基变量,o,X,1,X,2,a,h,b,k,20,第五步、,判断,X,(2),是否最优：检查用非,基变量表达的目标函数中,非,基变量前的系数,(,叫检验数,),。,Max Z =,70,x,1,+,30,x,2,=,70,80-(1/3)x,2,-(1/9)x,5,+,30,x,2,=,5600,+,(,20/3,),x,2,-,(,70/9,),x,5,因为,检验数,20/3,0,，所以当,x,2,从,0,增大时，,Z,也会增大。,故,当前解非最优。当前解须改进，寻求更好的解。,第六步、,确定改进的非基变量及其上界,:,选择使目标,Z,值改变得最快的,非基变量优先改进。,(1),、,确定非,基变量,x,2,改进：因为目标函数,中只有一个正,检验数,。,(2),、,x,2,增加的上界是,15,：,因为从约束方程组,可以得出,(,从资源最优利用考虑，令,x,3,、,x,4,、,x,5,=0,),x,2,=60 -(1/3)x,1,-(1/9)x,3,=60-(1/3)x,1,x,2,=37.5,x,2,=90 -x,1,-x,4,=90 -x,1,x,2,=15,x,2,=240-3x,1,-(1/3)x,5,=240-3x,1,x,1,=80-(1/3)x,2,代入上面二式,取前二式的最小值即,非基变量,x,2,增加的上界是,15 -,最小比值规则。此时,x,1,=75,。,Max Z=70,x,1,30 x,2,s.t.3x,1,+9x,2,+,x,3,=540,5x,1,+5x,2,+,x,4,=450,9x,1,+3x,2,+,x,5,=720,x,j,0,，,j=1,5,；,x,3,x,4,x,5,为基变量,o,X,1,X,2,a,h,b,k,21,第七步、,确定新解：将,x,1,=75,，,x,2,=15,代入约束方程组中求出,x,3,、,x,4,、,x,5,的值。,得新基本可行解为：,X,(3),=,（,x,1,x,2,x,3,x,4,x,5,）,T,=,（,75,15,180,0,0,）,T,甲 乙,设备,A,设备,B,设备,C,空闲工时,Z,(3)=,5700,，,利润为,5700 (x,4,、,x,5,为非,基变量，,x,1,、,x,2,、,x,3,为,基变量,)(,对应点,h,),第八步、,判断,X,(3),是否最优：检查用非,基变量表达的目标函数中,非,基变量前的系数,(,叫检验数,),。,Max Z =,70,x,1,+,30,x,2,=,5700 -,2,x,4,-(,20/3,),x,5,由,5x,1,+5x,2,+,x,4,=450,9x,1,+3x,2,+,x,5,=720,解,得,x,1,=75+(1/10),x,4,-,(,1/6,),x,5,，,x,2,=15-(3/10),x,4,+,(,1/6,),x,5,，代入,目标函数中得,Max Z =,70,x,1,+,30,x,2,=,70,75+(1/10),x,4,-,(,1/6,),x,5,+,30,15-(3/10),x,4,+,(,1/6,),x,5,=,5700 -,2,x,4,-(,20/3,),x,5,因为,检验数,-2,、,-20/3,0,，,原最优解基将发生变化，,原最优解不再是最优解，只须在原最优表上继续用单纯形法求新的最优解。,此时原最优表变为：,39,基,x,1,x,2,x,3,x,4,x,5,b,x,3,0,0,1,-12/5,1,180,x,2,0,1,0,3/10,-1/6,15,x,1,1,0,0,-1/10,1/6,75,-Z,0,0,0,1,-35/3,-7950,50,x,3,0,8,1,0,-1/3,300,x,4,0,10/3,0,1,-5/9,50,x,1,1,1/3,0,0,1/9,80,-Z,0,-10/3,0,0,-100/9,-5840,原最优解变为：,X,*,=(80,，,0,，,300,，,50,，,0),T,Z,*,=,5840,40,