第二章-线性规划ppt课件.ppt

《第二章-线性规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第２章　线性规划（LinearProgramming）第２章　线性规划2.1线性规划的模型与图解法2.2单纯形法2.3对偶问题与灵敏度分析2.4运输问题2.5线性整数规划2.1线性规划的模型与图解法2.1.1问题的引入（１）生产安排问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。资源单耗　　产品资源甲乙资源限量煤电油9445310360200300单位产品价格712甲乙资源限量煤(t)94360电（kw·h)45200油（t）310300单价（万元）712（

2、２）配料问题如何合理地搭配（混合）材料，以最经济的方式，达到配比要求。（营养配餐问题）假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？各种食物的营养成分表解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minZ=14x1+6x2+3x3+2x41000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x480

3、0x1，x2，x3，x40（3）下料问题如何截取原材料，在达到截取要求的情况下，使废料最少．料长7.4米，截成2.9、2.1、1.5米各200根,方案如下表。如何截取余料最少？方案料型123452.9米2.1米1.5米120100022131203合计残料7.47.37.27.16.600.10.20.30.8解：设xj(j=1,2,3,4,5)为采用第j种方案截取的原料根数，则下料问题的线性规划模型为：minZ=0x1+0.1x2+0.2x3+0.3x4+0.8x5x1+2x2+x42002x3+2x4+x52003x1+x2+2x3+3x5200xj0(j=1,2

4、,3,4,5)练习1：某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有M、N两种。有关数据如下：试决定买M与N二种饲料各多少公斤而使支出的总费用为最少？410售价0.40.62.01.7牲畜每日每头需要量00.10.20.1N0.100.10.2M每公斤含营养成分ABCD饲料解：设购买M、N饲料各为，则2.1.2线性规划的一般模型与标准型一、一般模型规划问题的数学模型包含三个组成要素：（1）决策变量：指决策者为实现规划目标采取的方案措施，是问题中要确定的未知量。（2）目标函数：指问题要达到的目的要求，表示为决策变量的函数。（3）约束条件：指决策

5、变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。一般地，线性规划模型：简记为：矩阵表示为：例1：二、线性规划问题的标准形式标准形式要求：（1）目标最大化（max）（2）约束是“=”约束（3）右端项非负（4）所有变量非负标准型化标准型：(1)minZ=2x1+4x2(令Z’=-Z)maxZ’=-2x1-4x2(2)-x1+x2+4x3≤2(引入松弛变量x4)-x1+x2+4x3+x4=2松弛变量的意义：未被充分利用的资源（c4=0）(3)-x1+x2+4x3≥2(引入剩余变量x5)-x1+x2+4x3-x5=2剩余变量的意义：超用的资源（c5=0）(4)xj≤

6、0(令xj’=-xj)xj’≥0(5)xj为自由变量(令xj=xj’-xj’’)xj’≥0,xj’’≥0例2：将下面的线性规划模型化为标准型思考题：1、松弛变量的实际意义是什么？2、松弛变量在目标函数中的系数是多少？练习：将下面的线性规划模型化为标准型x1,x2,x3为实际变量x5为松弛变量x4为剩余变量广义松弛变量2.1.3线性规划模型的图解法（适用于2个变量的一般型）一、线性规划问题的解的概念设线性规划问题的一般型为（1）可行解：满足全部约束条件的决策变量X为可行解；全部可行解的集合R称为可行解域。（2）最优解：使目标函数为最大（或最小）的可行解X*。二、线性规划的图解法图

7、解法步骤：（1）根据约束条件画出可行解域；（2）画出目标函数的等值线；（3）求出最优解。x1x209040405030100Dl1l2l3例3用图解法求解下列线性规划问题可行域目标函数等值线A有唯一最优解（顶点D）解直线l2,l3组成的线性方程组得：X*=(20,24)T——最优生产方案Z*=7×20+12×24=428——最大收入(2)在模型(1)中，目标函数改为maxZ=3x1+10x2，其他不变。易知，目标函数等值线与直线l3平行，故线段AD上的点均为最优解。有无穷多最优解x20904