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

第章线性规划第章线性规划2.1 线性规划的模型与图解法线性规划的模型与图解法2.2 单纯形法单纯形法2.3 对偶问题与灵敏度分析对偶问题与灵敏度分析2.4 运输问题运输问题2.1 线性规划的模型与图解法线性规划的模型与图解法2.1.1 问题的引入问题的引入（）生产安排问题（）生产安排问题l 如何合理使用有限的人力、物力和资金，如何合理使用有限的人力、物力和资金，使得收到最好的经济效益。使得收到最好的经济效益。例例1 1：某工厂可生产甲、乙两种产品，需消耗煤、：某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。试拟订使总收入最大的生产方案。资源单耗产品资源单耗产品 资源资源甲甲 乙乙资源限量资源限量煤煤电电油油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万元。万元。则则 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.约束条件约束条件（）配料问题（）配料问题l 如何合理地搭配（混合）材料，以最如何合理地搭配（混合）材料，以最经济的方式，达到配比要求。经济的方式，达到配比要求。例例例例2 2 2 2：（营养配餐问题）：（营养配餐问题）：（营养配餐问题）：（营养配餐问题）假定一个成年人每天假定一个成年人每天假定一个成年人每天假定一个成年人每天需要从食物中获得需要从食物中获得需要从食物中获得需要从食物中获得3000300030003000千卡的热量、千卡的热量、千卡的热量、千卡的热量、55555555克蛋白克蛋白克蛋白克蛋白质和质和质和质和800800800800毫克的钙。如果市场上只有四种食品毫克的钙。如果市场上只有四种食品毫克的钙。如果市场上只有四种食品毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分可供选择，它们每千克所含的热量和营养成分可供选择，它们每千克所含的热量和营养成分可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营和市场价格见下表。问如何选择才能在满足营和市场价格见下表。问如何选择才能在满足营和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？养的前提下使购买食品的费用最小？养的前提下使购买食品的费用最小？养的前提下使购买食品的费用最小？各种食物的营养成分表各种食物的营养成分表解解：设设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 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）下料问题）下料问题l 如何截取原材料，在达到截取要求的如何截取原材料，在达到截取要求的情况下，使废料最少。情况下，使废料最少。例例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解解：设设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.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模型的三要素模型的三要素 规划问题的数学模型包含三个组成要素：规划问题的数学模型包含三个组成要素：（1）决策变量）决策变量：指决策者为实现规划目标采指决策者为实现规划目标采取的方案措施，是问题中要确定的未知量。取的方案措施，是问题中要确定的未知量。（2）目标函数：）目标函数：指问题要达到的目的要求，指问题要达到的目的要求，表示为决策变量的函数。表示为决策变量的函数。（3）约束条件：）约束条件：指决策变量取值时受到的各指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等种可用资源的限制，表示为含决策变量的等式或不等式。式或不等式。二、二、LP模型的一般式模型的一般式一般地，线性规划模型：一般地，线性规划模型：1、决策变量：、决策变量：x x1 1,x,xn n2、目标函数：、目标函数：3、约束条件：、约束条件：简记为：简记为：三、三、LP模型的矩阵式模型的矩阵式 表示为：表示为：例如：练习练习1 1：某畜牧厂每日要为牲畜购买饲料以使其获取某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有四种养分。市场上可选择的饲料有M、N两两种。有关数据如下：种。有关数据如下：试决定买试决定买M与与N二种饲料各多少公斤而使支出的总费用二种饲料各多少公斤而使支出的总费用为最少？为最少？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饲料2.1.3 线性规划模型的图解法线性规划模型的图解法（适用于（适用于2个个变量的一般型）变量的一般型）一、线性规划问题的解的概念一、线性规划问题的解的概念 设线性规划问题的一般型为设线性规划问题的一般型为（1）可行解：满足全部约束条件的决策变量）可行解：满足全部约束条件的决策变量X为可行解；为可行解；全部可行解的集合全部可行解的集合R称为可行解域。称为可行解域。（2）最优解：使目标函数为最大（或最小）的可行解）最优解：使目标函数为最大（或最小）的可行解X*。二、线性规划的图解法二、线性规划的图解法l 图解法步骤：图解法步骤：1、根据约束条件画出可行解域；、根据约束条件画出可行解域；（1）先作非负约束）先作非负约束（2）再作资源限制约束）再作资源限制约束（3）各约束的公共部分即该）各约束的公共部分即该LP的约束的图形（可行域）的约束的图形（可行域）2、画出目标函数的等值线；、画出目标函数的等值线；（1）任给）任给z两个不同的值，作相应两条直线两个不同的值，作相应两条直线（2）将目标直线向增大的方向移，直至可行域的边界，）将目标直线向增大的方向移，直至可行域的边界，交点交点X*即最优解。即最优解。3、求出最优解。、求出最优解。由交点二直线联立求解出最优解由交点二直线联立求解出最优解X*的值。的值。x1x209040405030100Dl1l2l3例例1 用图解法求解下列线性规划问题。用图解法求解下列线性规划问题。可行域可行域目标函数等值线目标函数等值线X*有唯一最优解（顶点有唯一最优解（顶点D）解直线解直线l2,l3组成的线性方组成的线性方程组得：程组得：X*=(20,24)T最优生产方案最优生产方案Z*=720+1224=428最大收入最大收入（2）在模型（）在模型（1）中，目标函数改为）中，目标函数改为 max z=3x1+10 x2，其它不变。，其它不变。09040405030100Dl1l2l3AX1易知，目标函数等值易知，目标函数等值线与直线线与直线l l3 3平行。平行。X2故线段故线段ADAD上的点均为上的点均为最优解。最优解。有无穷多最优解有无穷多最优解x1x204可行域无界，在可行域上没可行域无界，在可行域上没有使目标函数值为有限的最有使目标函数值为有限的最优解。优解。无有限最优解（无界解）无有限最优解（无界解）1x2012x1-1不存在所有约束条件的不存在所有约束条件的公共范围公共范围无可行解无可行解小结：1、线性规划问题2、两个重要结论、两个重要结论1）线性规划的可行域是凸多面体。）线性规划的可行域是凸多面体。2）线性规划的最优解在可行域的角点（顶点）上。）线性规划的最优解在可行域的角点（顶点）上。凸多面体凸多面体凹多面体角点（顶点）思考题：约束条件不等式的几何意义是什么？思考题：约束条件不等式的几何意义是什么？怎样做图？怎样做图？