《数学》第四册181线性规划的概念课件.ppt

1、 例例1 1：某中药厂用当归作原料制成当归丸与当归膏，某中药厂用当归作原料制成当归丸与当归膏，生产生产1 1盒当归丸需要盒当归丸需要5 5个劳动工时，使用个劳动工时，使用2kg2kg当归原当归原料，销售后获得利润料，销售后获得利润160160元；生产元；生产1 1盒当归膏需要盒当归膏需要2 2个劳动工时，使用个劳动工时，使用5kg5kg当归原料，销售后获得利润当归原料，销售后获得利润8080元；工厂现有可供利用的劳动工时为元；工厂现有可供利用的劳动工时为40004000工时，工时，可供使用的当归原料为可供使用的当归原料为5800kg5800kg，为避免当归原料，为避免当归原料存放时间过长而变质

2、，要求把存放时间过长而变质，要求把5800kg5800kg当归原料都当归原料都用掉。问工厂如何安排生产，才能使得两种产品用掉。问工厂如何安排生产，才能使得两种产品销售后获得的总利润最大？销售后获得的总利润最大？一、概念的引出一、概念的引出解解 设工厂生产设工厂生产x1盒当归丸与盒当归丸与x2瓶当归膏，瓶当归膏，可建立以下数学模型：可建立以下数学模型：）2,1（i,0 x5800 x5x24000 x2x5x80 x160Smaxi212121整数目标函数为：目标函数为：约束条件为：约束条件为：21x80 x160Smax）2,1（i,0 x5800 x5x24000 x2x5i2121整数决策

3、变量为：决策变量为：x1,x2 例例2 2 某公司由于生产需要，共需要某公司由于生产需要，共需要A A，B B两种原料至少两种原料至少350350吨（吨（A A，B B两种材料有一定替代性），其中两种材料有一定替代性），其中A A原料至少原料至少购进购进125125吨。但由于吨。但由于A A，B B两种原料的规格不同，各自所两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨需的加工时间也是不同的，加工每吨A A原料需要原料需要2 2个小时，个小时，加工每吨加工每吨B B原料需要原料需要1 1小时，而公司总共有小时，而公司总共有600600个加工小个加工小时。又知道每吨时。又知道每吨A

4、A原料的价格为原料的价格为2 2万元，每吨万元，每吨B B原料的价原料的价格为格为3 3万元，试问在满足生产需要的前提下，在公司加万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买工能力的范围内，如何购买A A，B B两种原料，使得购进成两种原料，使得购进成本最低？本最低？解：解：设购买设购买A种原料为种原料为x1，B种原料为种原料为x2，可建立以下数可建立以下数学模型：学模型：目标函数：目标函数：Min S=2xMin S=2x1 1+3 x+3 x2 2约束条件约束条件：s.t.xs.t.x1 1+x+x2 2 350 350 x x1 1 125 125 2 x 2 x1

5、 1+x+x2 2 600 600 x x1 1 ,x ,x2 2 0 0 s.t.是是subject to的缩写。意思为的缩写。意思为“满足满足于，受约束于于，受约束于”决策变量为：决策变量为：x1,x2数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型mixgtsxxxxfzMaxMiniTn,2,1,0)(.),(),()(1或x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条件约束条件数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划线性规划问题（线性规划问题（LP）：）：一组线性不等式约束下求线性目标函数一组线性不等式约束下求线性目标函数的

6、极大值或极小值问题。的极大值或极小值问题。决策变量的一组取值便构成了线性规划问题的一个决策变量的一组取值便构成了线性规划问题的一个解解；满足约束条件的解称为满足约束条件的解称为可行解可行解；所有可行解构成的集合称为所有可行解构成的集合称为可行解集可行解集；使目标函数达到所追求极值的可行解称为使目标函数达到所追求极值的可行解称为最优解最优解；最优解所对应的目标函数值称为最优解所对应的目标函数值称为最优值最优值。相关定义：相关定义：二、线性规划的表现形式二、线性规划的表现形式一般形式：一般形式：目标函数和所有的约束条件都是设计变量的目标函数和所有的约束条件都是设计变量的线性函数线性函数.目标函数：

7、目标函数：Max(Min）z=c1 x1+c2 x2+cn xn 约束条件：约束条件：s.t.a11 x1+a12 x2+a1n xn （=,）b1 a21 x1+a22 x2+a2n xn （=,）b2 am1 x1+am2 x2+amn xn （=,）bm x1，x2，xn 0 基本线性规划形式基本线性规划形式目标函数目标函数：Max（Min)S =c1 x1+c2 x2+cn xn 约束条件：约束条件：s.t.a11 x1+a12 x2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1，x2，xn 0，bi 0建模过

8、程建模过程1.理解要解决的问题，了解解题的目标和条件；理解要解决的问题，了解解题的目标和条件；2.定义决策变量（定义决策变量（x1，x2，xn），每一组值），每一组值表示一个方案；表示一个方案；3.用决策变量的线性函数形式写出目标函数，确用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件过程中必须遵循的约束条件三、线性规划问题的数学模型三、线性规划问题的数学模型 生产安排生产安排 原料搭配问题原料搭配问题 条件下料问题条件下料问题 物资运输问题物资运输问

9、题 某家具厂需要长某家具厂需要长80cm80cm的角钢与长的角钢与长60cm60cm的角钢，它们皆从长的角钢，它们皆从长210cm210cm的角钢截的角钢截得。现在对长得。现在对长80cm80cm角钢的需要量为角钢的需要量为150150根，对长根，对长60cm60cm角钢的需要量为角钢的需要量为330330根。问工厂应如何下料，才能使得用根。问工厂应如何下料，才能使得用料最省？写出数学模型。料最省？写出数学模型。条件下料问题条件下料问题1 分析：分析：共有三种下料方式，共有三种下料方式，第一种第一种是将是将1 1根长根长210210的角钢截得的角钢截得2 2根长根长80cm80cm的角钢；的角

10、钢；第第二二种是将种是将1 1根长根长210210的角钢截得的角钢截得1 1根长根长80cm80cm和和2 2根根60cm60cm的角钢；的角钢；第三种第三种是将是将210cm210cm的角钢的角钢截得截得3 3根长根长60cm60cm的角钢。现这三种下料方式的角钢。现这三种下料方式应该混合使用。应该混合使用。解：解：设设第一种第一种下料方式用掉下料方式用掉x x1 1根角钢；根角钢；第二种第二种下料方式用掉下料方式用掉x x2 2根角钢；根角钢；第三第三种种下料方式用掉下料方式用掉x x3 3根角钢；变量根角钢；变量x x1 1 x x2 2 x x3 3即为决策变量。即为决策变量。数学模型

11、为：数学模型为：）（ixxxxxxxxSi3,2,1,0330321502min3121321整数 某车间有一批长度为某车间有一批长度为7.4m7.4m的同型钢管，的同型钢管，因生产需要，需将其截成长因生产需要，需将其截成长2.9m2.9m、2.1m2.1m、1.5m1.5m三种不同长度的管料。若三种不同长度的管料。若三种管料各需三种管料各需100100根，问应如何下料，根，问应如何下料，才能使得用料最省？写出数学模型。才能使得用料最省？写出数学模型。条件下料问题条件下料问题2 分析：分析：解：解：设设第一种第一种下料方式用掉下料方式用掉x x1 1根管料；根管料；第二种第二种下料方式用掉下料

12、方式用掉x x2 2根管料；根管料；第三第三种种下料方式用掉下料方式用掉x x3 3根管料；根管料；第四种第四种下下料方式用掉料方式用掉x x4 4根管料；根管料；第五种第五种下料方下料方式用掉式用掉x x5 5根管料；变量根管料；变量x x1 1 x x2 2 x x3 3 x x4 4 x x5 5即即为决策变量。为决策变量。数学模型为：数学模型为：）（ixxxxxxxxxxxxxxxxSi5,4,3,2,1,0100323100221002min532154342154321整数整数例例1.目标函数：目标函数：Max S=50 x1+100 x2 约束条件：约束条件：s.t.x1+x2

13、300 2 x1+x2 400 x 2 250 x1 0 x2 0四图四图 解解 法法 对于只有对于只有两个两个决决策变量的线性规划问策变量的线性规划问题，可以在平面直角题，可以在平面直角坐标系上作图表示线坐标系上作图表示线性规划问题的有关概性规划问题的有关概念，并求解。念，并求解。四图四图 解解 法法 (1)(1)分别取决策变量分别取决策变量X X1 1,X,X2 2 为坐标向量建立直角坐标为坐标向量建立直角坐标系。取各约束条件的公共部分系。取各约束条件的公共部分x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1（2）目标函数）目标函数z=50 x1+1

14、00 x2，当，当z取某一固定值时得到一取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称条直线，直线上的每一点都具有相同的目标函数值，称之为之为“等值线等值线”。平行移动等值线，当移动到。平行移动等值线，当移动到B点时，点时，z在可行域内实现了最大化。在可行域内实现了最大化。A，B，C，D，E是可行域是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的顶点，对有限个约束条件则其可行域的顶点也是有限的。的。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x

15、2CBADE 重要结论重要结论1：当线性规划问题的可行域非空时，它是当线性规划问题的可行域非空时，它是有界或无界的凸多边形（凸集）有界或无界的凸多边形（凸集）;如果线性规划有最优解，则一定有一个如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；可行域的顶点对应一个最优解；无穷多个最优解。若将例无穷多个最优解。若将例1中的目标函中的目标函数变为数变为max z=50 x1+50 x2，则线段，则线段BC上上的所有点都代表了最优解；的所有点都代表了最优解；重要结论重要结论2：无界解。即可行域的范围延伸到无穷远，无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必来说，这说明模型有错，忽略了一些必要的约束条件；要的约束条件；无可行解。若在例无可行解。若在例1的数学模型中再增的数学模型中再增加一个约束条件加一个约束条件4x1+3x21200，则可行，则可行域为空域，不存在满足约束条件的解，域为空域，不存在满足约束条件的解，当然也就不存在最优解了。当然也就不存在最优解了。