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

《线性规划的概念及图解法幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性规划的概念及图解法幻灯片.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划的概念及图解法线性规划的概念及图解法第1页，共25页，编辑于2022年，星期一 例例1 1：某中药厂用当归作原料制成当归丸与当归膏，生产某中药厂用当归作原料制成当归丸与当归膏，生产1 1盒当归丸需要盒当归丸需要5 5个劳动工时，使用个劳动工时，使用2kg2kg当归原料，销售后当归原料，销售后获得利润获得利润160160元；生产元；生产1 1盒当归膏需要盒当归膏需要2 2个劳动工时，使用个劳动工时，使用5kg5kg当归原料，销售后获得利润当归原料，销售后获得利润8080元；工厂现有可供利用元；工厂现有可供利用的劳动工时为的劳动工时为40004000工时，可供使用的当归原料为工时，可供使用

2、的当归原料为5800kg5800kg，为避免当归原料存放时间过长而变质，要求把，为避免当归原料存放时间过长而变质，要求把5800kg5800kg当当归原料都用掉。问工厂如何安排生产，才能使得两种归原料都用掉。问工厂如何安排生产，才能使得两种产品销售后获得的总利润最大？产品销售后获得的总利润最大？一、概念的引出一、概念的引出第2页，共25页，编辑于2022年，星期一解解 设工厂生产设工厂生产x1盒当归丸与盒当归丸与x2瓶当归膏，瓶当归膏，可建立以下数学模型：可建立以下数学模型：第3页，共25页，编辑于2022年，星期一目标函数为：目标函数为：约束条件为：约束条件为：决策变量为：决策变量为：x1,

3、x2第4页，共25页，编辑于2022年，星期一 例例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个加工小时。又知道每吨个加工小时

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

5、0 350 x x1 1 125 125 2 x 2 x1 1+x+x2 2 600 600 x x1 1 ,x ,x2 2 0 0 s.t.是是subject to的缩写。意思为的缩写。意思为“满足于，满足于，受约束于受约束于”决策变量为：决策变量为：x1,x2第6页，共25页，编辑于2022年，星期一数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条件约束条件数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划第7页，共25页，编辑于2022年，星期一线性规划问题（线性规划问题（LP）：）：一组线性

6、不等式约束下求线性目标函数一组线性不等式约束下求线性目标函数的极大值或极小值问题。的极大值或极小值问题。决策变量的一组取值便构成了线性规划问题的一个决策变量的一组取值便构成了线性规划问题的一个解解；满足约束条件的解称为满足约束条件的解称为可行解可行解；所有可行解构成的集合称为所有可行解构成的集合称为可行解集可行解集；使目标函数达到所追求极值的可行解称为使目标函数达到所追求极值的可行解称为最优解最优解；最优解所对应的目标函数值称为最优解所对应的目标函数值称为最优值最优值。相关定义：相关定义：第8页，共25页，编辑于2022年，星期一二、线性规划的表现形式二、线性规划的表现形式一般形式：目标函数和

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 第9页，共25页，编辑于2022年，星期一基本线性规划形式基本线性规划形式目标函数目标函数：Max（Min)S =c1 x1+c2 x2+cn xn 约束条件：约束条件：s.t.a11 x1+a12 x2+a1n

8、 xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1，x2，xn 0，bi 0第10页，共25页，编辑于2022年，星期一建模过程建模过程1.理解要解决的问题，了解解题的目标和条件；理解要解决的问题，了解解题的目标和条件；2.定义决策变量（定义决策变量（x1，x2，xn），每一组值），每一组值表示一个方案；表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程用一组决策变量的等式或不等式表示解决问题

9、过程中必须遵循的约束条件中必须遵循的约束条件第11页，共25页，编辑于2022年，星期一三、线性规划问题的数学模型三、线性规划问题的数学模型生生产产安安排排原原料料搭搭配配问问题题条条件件下下料料问问题题物物资资运运输输问问题题第12页，共25页，编辑于2022年，星期一 某家具厂需要长某家具厂需要长80cm80cm的角钢与长的角钢与长60cm60cm的角钢，它们皆从长的角钢，它们皆从长210cm210cm的角钢截得。的角钢截得。现在对长现在对长80cm80cm角钢的需要量为角钢的需要量为150150根，根，对长对长60cm60cm角钢的需要量为角钢的需要量为330330根。问工根。问工厂应如

10、何下料，才能使得用料最省？厂应如何下料，才能使得用料最省？写出数学模型。写出数学模型。条件下料问题条件下料问题1第13页，共25页，编辑于2022年，星期一 分析：分析：共有三种下料方式，共有三种下料方式，第一种第一种是将是将1 1根长根长210210的角钢截得的角钢截得2 2根长根长80cm80cm的角钢；的角钢；第二第二种是将种是将1 1根长根长210210的角钢截得的角钢截得1 1根长根长80cm80cm和和2 2根根60cm60cm的角钢；的角钢；第三种第三种是将是将210cm210cm的角钢截得的角钢截得3 3根长根长60cm60cm的角钢。的角钢。现这三种下料方式应该混合使用。现这

11、三种下料方式应该混合使用。第14页，共25页，编辑于2022年，星期一 解：解：设设第一种第一种下料方式用掉下料方式用掉x x1 1根角钢；根角钢；第二种第二种下料方式用掉下料方式用掉x x2 2根角钢；根角钢；第三第三种种下料方式用掉下料方式用掉x x3 3根角钢；变量根角钢；变量x x1 1 x x2 2 x x3 3即为决策变量。即为决策变量。第15页，共25页，编辑于2022年，星期一数学模型为：数学模型为：第16页，共25页，编辑于2022年，星期一 某车间有一批长度为某车间有一批长度为7.4m7.4m的同型钢管，的同型钢管，因生产需要，需将其截成长因生产需要，需将其截成长2.9m2

12、.9m、2.1m2.1m、1.5m1.5m三种不同长度的管料。若三种不同长度的管料。若三种管料各需三种管料各需100100根，问应如何下料，根，问应如何下料，才能使得用料最省？写出数学模型。才能使得用料最省？写出数学模型。条件下料问题条件下料问题2第17页，共25页，编辑于2022年，星期一 分析：分析：第18页，共25页，编辑于2022年，星期一 解：解：设设第一种第一种下料方式用掉下料方式用掉x x1 1根管料；根管料；第二种第二种下料方式用掉下料方式用掉x x2 2根管料；根管料；第三第三种种下料方式用掉下料方式用掉x x3 3根管料；根管料；第四种第四种下下料方式用掉料方式用掉x x4

13、 4根管料；根管料；第五种第五种下料方下料方式用掉式用掉x x5 5根管料；变量根管料；变量x x1 1 x x2 2 x x3 3 x x4 4 x x5 5即即为决策变量。为决策变量。第19页，共25页，编辑于2022年，星期一数学模型为：数学模型为：第20页，共25页，编辑于2022年，星期一例例1.目标函数：目标函数：Max S=50 x1+100 x2 约束条件：约束条件：s.t.x1+x2 300 2 x1+x2 400 x 2 250 x1 0 x2 0四图四图 解解 法法 对于只有对于只有两个两个决策决策变量的线性规划问题，可变量的线性规划问题，可以在平面直角坐标系上作以在平面

14、直角坐标系上作图表示线性规划问题的有图表示线性规划问题的有关概念，并求解。关概念，并求解。第21页，共25页，编辑于2022年，星期一四图四图 解解 法法 (1)(1)分别取决策变量分别取决策变量X X1 1,X,X2 2 为坐标向量建立直角坐标系。取各为坐标向量建立直角坐标系。取各约束条件的公共部分约束条件的公共部分x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1第22页，共25页，编辑于2022年，星期一（2）目标函数）目标函数z=50 x1+100 x2，当，当z取某一固定值时得到一条直取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数

15、值，称之为线，直线上的每一点都具有相同的目标函数值，称之为“等值等值线线”。平行移动等值线，当移动到。平行移动等值线，当移动到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 x2CBADE第23页，共25页，编辑于2022年，星期一重要结论重要结论1：当线性规划问题的可行域非空时，

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