线性规划的概念及图解法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性规划（,Linear Programing,）,第五章 线性规划问题的概念与图解法,例1：,某中药厂用当归作原料制成当归丸与当归膏，生产1盒当归丸需要5个劳动工时，使用2kg当归原料，销售后获得利润160元；生产1盒当归膏需要2个劳动工时，使用5kg当归原料，销售后获得利润80元；工厂现有可供利用的劳动工时为4000工时，可供使用的当归原料为5800kg，为避免当归原料存放时间过长而变质，要求把5800kg当归原料都用掉。问工厂如何安排生产，才能使得两种产品销售后获得的总利润最大？,一、概念的引出,解 设工厂生产x,1,盒当归丸与x,2,瓶当归膏，可建立以下数学模型：,目标函数为：,约束条件为：,决策变量为：,x,1,x,2,例2,某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？,解：,设购买A种原料为x,1，,B种原料为x,2，,可建立以下数学模型：,目标函数：,Min S=2x,1,+3 x,2,约束条件,：,s.t.x,1,+x,2,350,x,1,125,2 x,1,+x,2,600,x,1,x,2,0,s.t.是subject to的缩写。意思为“满足于，受约束于”,决策变量为：,x,1,x,2,Max S=50 x1+100 x2,用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；,一般来说，这说明模型有错，忽略了一些必要的约束条件；,目标函数：Max（Min)S =c1 x1+c2 x2+cn xn,但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。,三、线性规划问题的数学模型,一般形式：目标函数和所有的约束条件都是设计变量的线性函数.,解：设第一种下料方式用掉x1根角钢；,第三种下料方式用掉x3根管料；,数学规划模型,实际问题中,的优化模型,x,决策变量,f,(,x,)目标函数,g,i,(,x,),0,约束条件,数学规划,线性规划,非线性规划,整数规划,线性规划问题（LP）：,一组线性不等式约束下求线性目标函数的极大值或极小值问题。,决策变量的一组取值便构成了线性规划问题的一个,解,；,满足约束条件的解称为,可行解,；,所有可行解构成的集合称为,可行解集,；,使目标函数达到所追求极值的可行解称为,最优解,；,最优解所对应的目标函数值称为,最优值,。,相关定义：,二、线性规划的表现形式,一般形式：,目标函数和所有的约束条件都是设计变量的线性函数.,目标函数：,Max(Min）z=c,1,x,1,+c,2,x,2,+c,n,x,n,约束条件：,s.t.,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,（=,）b,2,a,m1,x,1,+,a,m2,x,2,+,a,mn,x,n,（=,）b,m,x,1,，x,2,，x,n,0,基本线性规划形式,目标函数,：,Max（Min)S =c,1,x,1,+c,2,x,2,+c,n,x,n,约束条件：s.t.,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,b,2,a,m1,x,1,+,a,m2,x,2,+,a,mn,x,n,b,m,x,1,，x,2,，x,n,0，b,i,0,建模过程,1.,理解要解决的问题，了解解题的目标和条件；,2.定义决策变量（x,1,，x,2,，x,n,），每一组值表示一个方案；,3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；,4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件,三、线性规划问题的数学模型,生产安排,原料搭配问题,条件下料问题,物资运输问题,决策变量为：x1,x2,所有可行解构成的集合称为可行解集；,Max S=50 x1+100 x2,目标函数：Max（Min)S =c1 x1+c2 x2+cn xn,三、线性规划问题的数学模型,x1，x2，xn 0,三、线性规划问题的数学模型,现在对长80cm角钢的需要量为150根，对长60cm角钢的需要量为330根。,一组线性不等式约束下求线性目标函数的极大值或极小值问题。,是subject to的缩写。,A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,Max S=50 x1+100 x2,用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；,解：设购买A种原料为x1，B种原料为x2，可建立以下数学模型：,x2 0,某家具厂需要长80cm的角钢与长60cm的角钢，它们皆从长210cm的角钢截得。现在对长80cm角钢的需要量为150根，对长60cm角钢的需要量为330根。问工厂应如何下料，才能使得用料最省？写出数学模型。,条件下料问题1,分析：,共有三种下料方式，,第一种,是将1根长210的角钢截得2根长80cm的角钢；,第二,种是将1根长210的角钢截得1根长80cm和2根60cm的角钢；,第三种,是将210cm的角钢截得3根长60cm的角钢。现这三种下料方式应该混合使用。,解：,设,第一种,下料方式用掉x,1,根角钢；,第二种,下料方式用掉x,2,根角钢；,第三种,下料方式用掉x,3,根角钢；变量x,1,x,2,x,3,即为决策变量。,数学模型为：,某车间有一批长度为7.4m的同型钢管，因生产需要，需将其截成长2.9m、2.1m、1.5m三种不同长度的管料。若三种管料各需100根，问应如何下料，才能使得用料最省？写出数学模型。,条件下料问题2,分析：,解：,设,第一种,下料方式用掉x,1,根管料；,第二种,下料方式用掉x,2,根管料；,第三种,下料方式用掉x,3,根管料；,第四种,下料方式用掉x,4,根管料；,第五种,下料方式用掉x,5,根管料；变量x,1,x,2,x,3,x,4,x,5,即为决策变量。,数学模型为：,例1.目标函数：,Max S=50 x,1,+100 x,2,约束条件：,s.t.,x,1,+x,2,300,2 x,1,+x,2,400,x,2,250,x,1,0,x,2,0,四图 解 法,对于只有,两个,决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。,四图 解 法,(1)分别取决策变量X,1,X,2,为坐标向量建立直角坐标系。取各约束条件的公共部分,x,1,x,2,x,2,=0,x,1,=0,x,2,=250,x,1,+x,2,=300,2x,1,+x,2,=400,图2-1,（2）目标函数z=50 x,1,+100 x,2,，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,x,1,x,2,z=20000=50 x,1,+100 x,2,图2-2,z=27500=50 x,1,+100 x,2,z=0=50 x,1,+100 x,2,z=10000=50 x,1,+100 x,2,C,B,A,D,E,重要结论1：,当线性规划问题的可行域非空时，它是有界或无界的凸多边形（凸集）;,如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；,无穷多个最优解。若将例1中的目标函数变为max z=50 x,1,+50 x,2,，则线段BC上的所有点都代表了最优解；,重要结论2：,无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；,无可行解。若在例1的数学模型中再增加一个约束条件4x,1,+3x,2,1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。,