运筹学 第二章线性规划模型与图解法精选文档.ppt

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

1、运筹学 课件第二章线性规划模型与图解法本讲稿第一页，共二十四页第章线性规划第章线性规划2.1 线性规划的模型与图解法线性规划的模型与图解法2.2 单纯形法单纯形法2.3 对偶问题与灵敏度分析对偶问题与灵敏度分析2.4 运输问题运输问题本讲稿第二页，共二十四页2.1 线性规划的模型与图解法线性规划的模型与图解法2.1.1 问题的引入问题的引入（）生产安排问题（）生产安排问题 如何合理使用有限的人力、物力和资金，使如何合理使用有限的人力、物力和资金，使得收到最好的经济效益。得收到最好的经济效益。本讲稿第三页，共二十四页 例例1 1：某工厂可生产甲、乙两种产品，需消耗煤、电、：某工厂可生产甲、乙两种

2、产品，需消耗煤、电、油三种资源。现将有关数据列表如下：油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。试拟订使总收入最大的生产方案。资源单耗产品资源单耗产品 资源资源甲甲 乙乙资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 12本讲稿第四页，共二十四页 甲甲 乙乙 资源限量资源限量 煤煤(t)9 4 360 电（电（kwh)4 5 200 油（油（t）3 10 300 单价（万元）单价（万元）7 12解：设甲乙产品产量分别为解：设甲乙产品产量分别为x x1 1和和x x2 2 kgkg，决策变量决策变量总收入为总收入为z z万元

3、。万元。则则 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.约束条件约束条件本讲稿第五页，共二十四页（）配料问题（）配料问题 如何合理地搭配（混合）材料，以最经济如何合理地搭配（混合）材料，以最经济的方式，达到配比要求。的方式，达到配比要求。例例例例2 2 2 2：（营养配餐问题）：（营养配餐问题）假定一个成年人每天需要假定一个成年人每天需要从食物中获得从食物中

4、获得30003000千卡的热量、千卡的热量、55555555克蛋白质和克蛋白质和克蛋白质和克蛋白质和800800800800毫克的钙。如果市场上只有四种食品可供选择，它毫克的钙。如果市场上只有四种食品可供选择，它毫克的钙。如果市场上只有四种食品可供选择，它毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。们每千克所含的热量和营养成分和市场价格见下表。们每千克所含的热量和营养成分和市场价格见下表。们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的问如何选择才能在满足营养的前提下使购买食品的问如何选择才能在满足营养的前

5、提下使购买食品的问如何选择才能在满足营养的前提下使购买食品的费用最小？费用最小？费用最小？费用最小？本讲稿第六页，共二十四页各种食物的营养成分表各种食物的营养成分表本讲稿第七页，共二十四页解解：设设x xj j(j=1,2,3,4)(j=1,2,3,4)为为第第j j种种食食品品每每天天的的购购入入量量，z z为为每每天天购购买买食食品品的的总总费费用用，则则配配餐餐问题的线性规划模型为：问题的线性规划模型为：min z=14xmin z=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

6、 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本讲稿第八页，共二十四页（3 3）下料问题）下料问题 如何截取原材料，在达到截取要求的情况如何截取原材料，在达到截取要求的情况下，使废料最少。下，使废料最少。例例3 3：料长：料长7.47.4米，截成米，截成2.92.9、2.12

7、.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本讲稿第九页，共二十四页解解：设设x xj j(j=1,2,3,4,5)(j=1,2,3,4,5)为为采采用用第第j j种种方方案案截截取取的的原原料料根根数数，z z为为截截取取后后的的余余料料总总米米数数，则则下料问题的线性规划模型为：下料问题的线性规划模型为：m

8、in z=0 xmin z=0 x1 1+0.1x+0.1x2 2+0.2x+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)本讲稿第十页，共二十四页2.1.2 线性规划的模型线性规划的模型 一、一、LP模型的三要素模型的三要素 规划问题的数学模型包含三个组成要素：规划问题的数学模型包含三个组成要

9、素：（1）决策变量）决策变量：指决策者为实现规划目标采指决策者为实现规划目标采取的方案措施，是问题中要确定的未知量。取的方案措施，是问题中要确定的未知量。（2）目标函数：）目标函数：指问题要达到的目的要求，指问题要达到的目的要求，表示为决策变量的函数。表示为决策变量的函数。（3）约束条件：）约束条件：指决策变量取值时受到的各指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等种可用资源的限制，表示为含决策变量的等式或不等式。式或不等式。本讲稿第十一页，共二十四页二、二、LP模型的一般式模型的一般式一般地，线性规划模型：一般地，线性规划模型：1、决策变量：、决策变量：x x1 1,x,

10、xn n2、目、目标标函数：函数：3、约约束条件：束条件：本讲稿第十二页，共二十四页 简记为：简记为：本讲稿第十三页，共二十四页三、三、LP模型的矩阵式模型的矩阵式 表示为：表示为：本讲稿第十四页，共二十四页例如：本讲稿第十五页，共二十四页练习练习1 1：某畜牧厂每日要为牲畜购买饲料以使其获取某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有四种养分。市场上可选择的饲料有M、N两种。有关数据两种。有关数据如下：如下：试决定买试决定买M与与N二种饲料各多少公斤而使支出的总费用为最少二种饲料各多少公斤而使支出的总费用为最少？410售价 0.4 0.6 2.0 1.7

11、牲畜每日需要量 0 0.1 0.2 0.1N 0.1 0 0.1 0.2 M每公斤含营养成分 A B C D饲料本讲稿第十六页，共二十四页2.1.3 线性规划模型的图解法线性规划模型的图解法（适用于（适用于2个变量个变量的一般型）的一般型）一、线性规划问题的解的概念一、线性规划问题的解的概念 设线性规划问题的一般型为设线性规划问题的一般型为（1）可行解：满足全部约束条件的决策变量）可行解：满足全部约束条件的决策变量X为可行解；为可行解；全部可行解的集合全部可行解的集合R称为可行解域。称为可行解域。（2）最优解：使目标函数为最大（或最小）的可行解）最优解：使目标函数为最大（或最小）的可行解X*。

12、本讲稿第十七页，共二十四页二、线性规划的图解法二、线性规划的图解法 图解法步骤：图解法步骤：1、根据约束条件画出可行解域；、根据约束条件画出可行解域；（1）先作非负约束）先作非负约束（2）再作资源限制约束）再作资源限制约束（3）各约束的公共部分即该）各约束的公共部分即该LP的约束的图形（可行域）的约束的图形（可行域）2、画出目标函数的等值线；、画出目标函数的等值线；（1）任给）任给z两个不同的值，作相应两条直线两个不同的值，作相应两条直线（2）将目标直线向增大的方向移，直至可行域的边界，）将目标直线向增大的方向移，直至可行域的边界，交点交点X*即最优解。即最优解。3、求出最优解。、求出最优解。

13、由交点二直线联立求解出最优解由交点二直线联立求解出最优解X*的值。的值。本讲稿第十八页，共二十四页x1x209040405030100Dl1l2l3例例1 用图解法求解下列线性规划问题。用图解法求解下列线性规划问题。可行域可行域目标函数等值线目标函数等值线X*有唯一最优解（顶点有唯一最优解（顶点D）解直线解直线l2,l3组成的线性方程组成的线性方程组得：组得：X*=(20,24)T最优生产方案最优生产方案Z*=720+1224=428最大收入最大收入本讲稿第十九页，共二十四页（2）在模型（）在模型（1）中，目）中，目标标函数改函数改为为 max z=3x1+10 x2，其它不，其它不变变。09

14、040405030100Dl1l2l3AX1易知，目易知，目标标函数等函数等值线值线与直与直线线l l3 3平行。平行。X2故故线线段段ADAD上的点均上的点均为为最最优优解。解。有无有无穷穷多最多最优优解解本讲稿第二十页，共二十四页x1x204可行域无界，在可行域上没有可行域无界，在可行域上没有使目标函数值为有限的最优解。使目标函数值为有限的最优解。无有限最优解（无界解）无有限最优解（无界解）本讲稿第二十一页，共二十四页1x2012x1-1不存在所有约束条件的公共不存在所有约束条件的公共范围范围无可行解无可行解本讲稿第二十二页，共二十四页小结：1、线性规划问题本讲稿第二十三页，共二十四页2、两个重要结论、两个重要结论1）线性规划的可行域是凸多面体。）线性规划的可行域是凸多面体。2）线性规划的最优解在可行域的角点（顶点）上。）线性规划的最优解在可行域的角点（顶点）上。凸多面体凸多面体凹多面体角点（顶点）思考题：约束条件不等式的几何意义是什么？怎样思考题：约束条件不等式的几何意义是什么？怎样做图？做图？本讲稿第二十四页，共二十四页