运筹学线性规划模型与图解法.pptx

《运筹学线性规划模型与图解法.pptx》由会员分享，可在线阅读，更多相关《运筹学线性规划模型与图解法.pptx（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.1 线性规划的模型与图解法2.1.1 问题的引入（）生产安排问题l 如何合理使用有限的人力、物力和资金，使得收到最好的经济效益。第1页/共23页 例1：某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。资源单耗产品资源单耗产品 资源资源甲甲 乙乙资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 12第2页/共23页 甲甲 乙乙 资源限量资源限量 煤煤(t)9 4 360 电（电（kwh)4 5 200 油（油（t）3 10 300 单价（万元）单价（万元）7 12解：设甲乙产品产量分别为

2、x x1 1和x x2 2 kgkg，决策变量总收入为z z万元。则 max z=7xmax z=7x1 1+12x+12x2 2 目标函数 9x 9x1 1+4x+4x2 2 360 360 4x 4x1 1+5x+5x2 2 200 200 3x 3x1 1+10 x+10 x2 2 300 300 x x1 1，x x2 200s.t.约束条件第3页/共23页（）配料问题l 如何合理地搭配（混合）材料，以最经济的方式，达到配比要求。例例2 2 2 2：（营养配餐问题）：（营养配餐问题）假定一个成年人每天假定一个成年人每天需要从食物中获得需要从食物中获得3000300030003000千卡

3、的热量、千卡的热量、55555555克蛋白克蛋白质和质和800800800800毫克的钙。如果市场上只有四种食品毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？养的前提下使购买食品的费用最小？第4页/共23页各种食物的营养成分表第5页/共23页解：设x xj j(j=1,2,3,4)(j=1,2,3,4)为第j j种食品每天的购入量，z z为每天购买食品的总费用，则配餐问题的线性规划模型为：min z=14xmin z=

4、14x1 1+6x+6x2 2+3x+3x3 3+2x+2x4 4 1000 x 1000 x1 1+800 x+800 x2 2+900 x+900 x3 3+200 x+200 x4 4 3000 3000 50 x 50 x1 1+60 x+60 x2 2+20 x+20 x3 3+10 x+10 x4 4 55 55 400 x 400 x1 1+200 x+200 x2 2+300 x+300 x3 3+500 x+500 x4 4 800 800 x x1 1,x,x2 2,x,x3 3,x,x4 4 0 0第6页/共23页（3 3）下料问题l 如何截取原材料，在达到截取要求的情况

5、下，使废料最少。例3 3：料长7.47.4米，截成2.92.9、2.12.1、1.51.5米各200200根,方案如下表。如何截取余料最少？方案料型 1 2 3 4 5 2.9米 2.1米 1.5米 1 2 0 1 0 0 0 2 2 1 3 1 2 0 3 合计 残料 7.4 7.3 7.2 7.1 6.6 0 0.1 0.2 0.3 0.8第7页/共23页解：设x xj j(j=1,2,3,4,5)(j=1,2,3,4,5)为采用第j j种方案截取的原料根数，z z为截取后的余料总米数，则下料问题的线性规划模型为：min z=0 xmin z=0 x1 1+0.1x+0.1x2 2+0.2

6、x+0.2x3 3+0.3x+0.3x4 4+0.8x+0.8x5 5 x x1 1+2x+2x2 2 +x+x4 4 200200 2x 2x3 3+2x+2x4 4+x+x5 5 200 200 3x 3x1 1+x+x2 2+2x+2x3 3 +3x+3x5 5 200200 x xj j 0(j=1,2,3,4,5)0(j=1,2,3,4,5)第8页/共23页2.1.2 线性规划的模型 一、LP模型的三要素 规划问题的数学模型包含三个组成要素：（1）决策变量：指决策者为实现规划目标采取的方案措施，是问题中要确定的未知量。（2）目标函数：指问题要达到的目的要求，表示为决策变量的函数。（3

7、）约束条件：指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。第9页/共23页二、LP模型的一般式一般地，线性规划模型：1、决策变量：x x1 1,x,xn n2 2、目标函数：3 3、约束条件：第10页/共23页 简记为：第11页/共23页三、三、LP模型的矩阵式模型的矩阵式 表示为：表示为：第12页/共23页例如：第13页/共23页练习练习1 1：某畜牧厂每日要为牲畜购买饲料以使其获取某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有四种养分。市场上可选择的饲料有M、N两两种。有关数据如下：种。有关数据如下：试决定买试决定买M与与N二

8、种饲料各多少公斤而使支出的总费用二种饲料各多少公斤而使支出的总费用为最少？为最少？410售价 0.4 0.6 2.0 1.7牲畜每日需要量 0 0.1 0.2 0.1N 0.1 0 0.1 0.2 M每公斤含营养成分 A B C D饲料第14页/共23页2.1.3 线性规划模型的图解法（适用于2个变量的一般型）一、线性规划问题的解的概念 设线性规划问题的一般型为（1）可行解：满足全部约束条件的决策变量X为可行解；全部可行解的集合R称为可行解域。（2）最优解：使目标函数为最大（或最小）的可行解X*。第15页/共23页二、线性规划的图解法l 图解法步骤：1、根据约束条件画出可行解域；（1）先作非负

9、约束（2）再作资源限制约束（3）各约束的公共部分即该LP的约束的图形（可行域）2、画出目标函数的等值线；（1）任给z两个不同的值，作相应两条直线（2）将目标直线向增大的方向移，直至可行域的边界，交点X*即最优解。3、求出最优解。由交点二直线联立求解出最优解X*的值。第16页/共23页x1x209040405030100Dl1l2l3例1 用图解法求解下列线性规划问题。可行域目标函数等值线X*有唯一最优解（顶点D）解直线l2,l3组成的线性方程组得：X*=(20,24)T最优生产方案Z*=720+1224=428最大收入第17页/共23页（2）在模型（1）中，目标函数改为 max z=3x1+1

10、0 x2，其它不变。09040405030100Dl1l2l3AX1易知，目标函数等值线与直线l3平行。X2故线段AD上的点均为最优解。有无穷多最优解第18页/共23页x1x204可行域无界，在可行域上没有使目标函数值为有限的最优解。无有限最优解（无界解）第19页/共23页1x2012x1-1不存在所有约束条件的公共范围无可行解第20页/共23页小结：1、线性规划问题第21页/共23页2、两个重要结论1）线性规划的可行域是凸多面体。2）线性规划的最优解在可行域的角点（顶点）上。凸多面体凸多面体凹多面体角点（顶点）思考题：约束条件不等式的几何意义是什么？怎样做图？第22页/共23页感谢您的观看！第23页/共23页