线性规划数学模型课件

第二章 线 性 规 划（L Linearinear P Programmingrogramming）线性性规划划问题是目是目标函数和函数和约束条件均束条件均为线性的最性的最优化化问题。自从自从1947年丹捷格年丹捷格(Dantzig)提出求解提出求解线性性规划的划的单纯形方法以形方法以来，来，线性性规划在理划在理论上上趋向成熟。特向成熟。特别是在是在计算机能算机能处理成千理成千上万个上万个约束条件和决策束条件和决策变量的量的线性性规划划问题之后，之后，线性性规划的划的适用适用领域更域更为广泛，已成广泛，已成为现代管理中代管理中经常采用的基本方法之常采用的基本方法之一。一。线性性规划是最划是最优化化问题中的重要中的重要领域之一，很多运筹学中域之一，很多运筹学中的的实际问题都可以用都可以用线性性规划来表述。很多其他种划来表述。很多其他种类的最的最优化化问题算法也都可以分拆成算法也都可以分拆成线性性规划子划子问题，然后求解。，然后求解。通通过学学习本章，本章，应当了解当了解线性性规划的有关概念，掌握划的有关概念，掌握线性性规划划模型的建立及模型的建立及优化方法，会用化方法，会用计算机算机对大型大型线性性规划模型划模型问题进行求解和分析。本章的行求解和分析。本章的难点点为单纯形形计算方法。算方法。1第一节 线性规划问题的提出线性性规划是运筹学的一个重要分支，主要用于研究解划是运筹学的一个重要分支，主要用于研究解决有限决有限资源的最佳分配源的最佳分配问题，即如何，即如何对有限有限资源做出源做出最佳方式的最佳方式的调配和最有利的使用，以便最充分地配和最有利的使用，以便最充分地发挥资源的效能，以源的效能，以获取最佳取最佳经济效益。效益。它的适用它的适用领域非常广泛，从工域非常广泛，从工业、农业、商、商业、交通、交通运运输业、军事的事的计划和管理及决策到整个国民划和管理及决策到整个国民经济计划的最划的最优方案的提出，都有它的用武之地，是方案的提出，都有它的用武之地，是现代管代管理科学的重要基理科学的重要基础和手段之一。和手段之一。2第一节 线性规划问题的提出线性性规划研究的划研究的问题主要有以下两主要有以下两类。(1)给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大任务。（如资金、设备、原标材料、人工、时间等）(2)给定一项任务，如何运筹规划，合理安排，以最少资源来完成它。（如产品量最多、利润最大.）线性性规划要研究的两划要研究的两类问题中都有一个限制条件：第中都有一个限制条件：第一一类问题是是给出一定量的人力、物力和出一定量的人力、物力和财力等力等资源；源；第二第二类问题是是给定一定一项任任务。3第二节 线性规划问题的数学模型当用当用线性性规划的方法划的方法对实际问题进行行优化化时，必必须把把这个个实际问题用恰当的数学形式表达出用恰当的数学形式表达出来，来，这个表达的个表达的过程，就是建立数学模型的程，就是建立数学模型的过程。数学模型的建立需要程。数学模型的建立需要经验和技巧以及有关和技巧以及有关的的专业知知识，只有通，只有通过大量的大量的实践，在建立模践，在建立模型型时才能得心才能得心应手。初学手。初学时可从可从题目中所目中所给出出的限制条件和目的限制条件和目标入手，由限制条件建立起入手，由限制条件建立起线性方程性方程组，由目，由目标得到目得到目标函数。函数。下面，下面，结合若干个合若干个实际问题讨论数学模型的建数学模型的建立。立。4一、投资问题的数学模型解（参见教材P15）5二、配料问题的数学模型解（参见教材P16）6二、配料问题的数学模型 某化工厂要用三种原料某化工厂要用三种原料 A，B B，C C 混合配制三种不同规格混合配制三种不同规格的产品的产品 X，Y，Z。有关数据如下有关数据如下：产品产品规规 格格单价单价(元元/kg)X原料原料D不少于不少于50%原料原料P不超过不超过25%50Y原料原料D不少于不少于25%原料原料P不超过不超过50%35Z不不 限限25原料原料最大供量最大供量(kg/天天)单价单价(元元/kg)A1006565B1002525C603535应如合配制应如合配制，才能使利润达到最大才能使利润达到最大？表表2-3表表2-4二、配料问题的数学模型一、决策变量决策变量 设以设以 xij 表示每天生产的表示每天生产的第第i 种产品中所含第种产品中所含第j 种原料种原料的数量的数量(kg，右表右表)。ji A B CXYZx11 x12 x13x21 x22 x23x31 x32 x33二、约束条件二、约束条件 规格约束规格约束(据据表表2-3)x11+x12+x13x11 0.50 x11+x12+x13x12 0.25x11+x12+x13x21 0.25x11+x12+x13x22 0.50二、配料问题的数学模型改写成改写成 -x11 +x12 +x13 0-x11+3 x12 -x13 0-3 x21 +x22 +x23 0 x21 +x22 -x23 0 资源约束资源约束(据据表表2-4)x11+x21 +x31 100 x12+x22+x32 100 x13+x23 +x33 60二、配料问题的数学模型三、目标函数三、目标函数 总产值总产值(据据表表2-3)产品产品X的产值的产值:50(x11+x12 +x13)产品产品Y的产值的产值:35(x21+x22+x23)产品产品Z的产值的产值:25(x31+x32 +x33)以上三项之和即以上三项之和即总产值总产值。总成本总成本(据据表表2-4)原料原料A的成本的成本:6565(x11+x21 +x31)原料原料B的成本的成本:2525(x12+x22+x32)原料原料C的成本的成本:3535(x13+x23 +x33)以上三项之和即以上三项之和即总成本总成本。二、配料问题的数学模型 目标函数目标函数为：为：总利润总利润总利润总利润=总产值总产值-总成本总成本max z z=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 该问题的数学模型为:s.t.-x11 +x12+x13 0 -x11+3x12 -x13 0 -3x21+x22 +x23 0 x21+x22 -x23 0 x11 +x21 +x31 100 x12 +x22 +x32 100 x13 +x23 +x33 60 xij 0，i=1,2,3；j=1,2,3配料问题配料问题练习：练习：某化工厂根据一项合同要为用户生产一种某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有乙两种原料都含有A，B，C三种化学成分三种化学成分，其含量其含量(%)是是:甲为甲为12，2，3；乙为乙为3，3，15。按合同规按合同规定定，产品中三种化学成分的含量产品中三种化学成分的含量(%)不得低于不得低于4，2，5。甲、乙原料成本为每千克甲、乙原料成本为每千克3，2元。元。厂方希望厂方希望总成本达到最小总成本达到最小，则应如何配制该产品则应如何配制该产品？配料问题配料问题 成分含量成分含量(%)(%)原原 料料 化学成分化学成分 甲甲 乙乙 产品成分产品成分 最低含量最低含量(%)(%)A B C 12 3 2 3 3 15 4 2 5 成本（元成本（元/千克）千克）3 2 x x1 1x x2 2min z z=3x1+2x2 12 x1 +3x2 4 2 x1 +3x2 2s.t.3 x1+15x2 5 x1 +x2=1 x1,x2 0配料平衡条件配料平衡条件z z三、人力资源问题的数学模型解（参见教材P17）14三、人力资源问题的数学模型练习：练习：某昼夜服务的公交线路每天各时间段内某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：所需司机和乘务人员人数如下表所示：班次班次时间时间所需人员所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少足工作需要，又使配备司机和乘务人员的人数减少?三、人力资源问题的数学模型解：解：设xi表示第表示第i班次班次时开始上班的司机和乘开始上班的司机和乘务人人员人数。人数。此问题最优解：此问题最优解：x150，x220，x350，x40，x520，x610，一共需要司机和乘务员，一共需要司机和乘务员150人。人。四、合理下料问题的数学模型合理下料合理下料问题是机械工是机械工业常遇到的常遇到的问题。毛坯。毛坯车间经常要在常要在长度一定的条形材料或面度一定的条形材料或面积一定的板材上切割一定的板材上切割若干个具有一定形状、尺寸的毛坯。在一般情况下，若干个具有一定形状、尺寸的毛坯。在一般情况下，材料不可能被完全利用，会有材料不可能被完全利用，会有边角余料，造成浪角余料，造成浪费。因此，如何最大限度地减少因此，如何最大限度地减少边角余料，提高材料利用角余料，提高材料利用率，使得切割率，使得切割规定数量的毛坯所用材料最少就是合理定数量的毛坯所用材料最少就是合理下料下料问题所要研究的。所要研究的。例2-5 某车间有一批长度为180cm的钢管(数量充分多)，为了制造零件的需要，要将其截成三种不同长度的管料：70cm、52cm、35cm。规定这三种管料的需要量分别不少于100根、150根和100根。问：应如何下料能使消耗的钢管数量最少？解（参见教材P18）17四、合理下料问题的数学模型 练习：制造某种机床制造某种机床，需要需要 A,B,C三种轴件三种轴件，其规格其规格与数量如表所示与数量如表所示，各类轴件都用各类轴件都用5.5米长的同一种圆钢米长的同一种圆钢下料下料。若计划生产若计划生产100台机床台机床，最少需要用多少根圆钢最少需要用多少根圆钢？四、合理下料问题的数学模型轴类轴类 规格：长度（米）规格：长度（米）每台机床所需轴件数每台机床所需轴件数 A 3.1 1 B 2.1 2 C 1.21.2 4 余料余料 j j 1.21.2找出全部找出全部省料截法省料截法一根圆钢所截各类轴件数一根圆钢所截各类轴件数 截法截法轴类轴类 轴轴 件件 需要量需要量 A(3.1)100 B(2.1)200 C(1.2)400 余料余料(米米)234511100.310200210.1 0 0 1 0 2 4 1 0.7四、合理下料问题的数学模型min z=x1+x2+x3+x4+x5s.t.x1+x2 100 x1 +2x3 +x4 200 2x2 +x3+2x4+4x5 400 x1，x2，x3，x4，x5 0则该问题的数学模型为则该问题的数学模型为:设第设第 j 种截法下料种截法下料 xj 根。根。四、合理下料问题的数学模型例：现有一批某种型号的圆钢长例：现有一批某种型号的圆钢长8米，需要截取米，需要截取2.5米米长的毛坯长的毛坯100根，长根，长1.3米的毛坯米的毛坯200根。问如何才能根。问如何才能既满足需要，又能使总的用料最少？既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出的，为此可以设计出4种下料方案以供套裁用。种下料方案以供套裁用。2.5m32101.3m0246料头料头00.40.30.2四、合理下料问题的数学模型设按方案设按方案、下料的原材料根数分别为下料的原材料根数分别为xj(j=1，2,3,4)，可列出下面的数学模型：，可列出下面的数学模型：五、运输问题的数学模型问题的提出：某的提出：某类产品有若干个品有若干个产地，已知每个生地，已知每个生产地的地的产量；量；这类产品有若干个消品有若干个消费地，已知每个消地，已知每个消费地的需要量。假地的需要量。假设总的的产量等于量等于总的需要量。的需要量。问题是如何是如何编制一个最制一个最优的运的运输计划，划，使从使从产地到消地到消费地的运地的运输费用最小。用最小。解（参见教材P20）23六、产品配比问题的数学模型六、产品配比问题的数学模型例例 某厂拟生产甲、乙两种产品，每件利润分别为某厂拟生产甲、乙两种产品，每件利润分别为3 3、5 5百元。百元。甲、乙产品的部件各自在甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、两个车间分别生产，每件甲、乙产品的部件分别需要乙产品的部件分别需要A、B车间的生产能力车间的生产能力1 1、2 2工时。两件工时。两件产品的部件最后都要在产品的部件最后都要在C车间装配，装配每件甲、乙产品分别车间装配，装配每件甲、乙产品分别需要需要3 3、4 4工时，三车间每天可用于生产这两种产品的工时分别工时，三车间每天可用于生产这两种产品的工时分别为为8 8、1212、3636，问应如何安排生产这两种产品才能获利最多？，问应如何安排生产这两种产品才能获利最多？产品配比问题产品配比问题z z x1 x2决策变量决策变量z z=3x1+5x2maxmax0目标函数目标函数x1 8 2x2 12 3x1 +4x2 36 函数约束函数约束 x1 ，x2 0 非负性约束非负性约束s.t.s.t.甲甲 乙乙1030 2 4 8 12 36A B C车间车间产品产品单耗（工时单耗（工时/件）件）最大生产能力最大生产能力（工时（工时/天）天）单位利润单位利润（百元（百元/件）件）3 5线性规划问题的数学模型练习：练习：某企业计划生产甲、乙两种产品。这些产品分某企业计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？设设 备备产产 品品 A B C D利润（元）利润（元）甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12线性规划问题的数学模型解：解：设x1、x2分分别为甲、乙两种甲、乙两种产品的品的产量，量，则数学模型数学模型为：max Z=2xmax Z=2x1 1+3x+3x2 2 x x1 1 0,x 0,x2 2 0 0s.t.s.t.2x 2x1 1+2x+2x2 2 12 12 x x1 1+2x+2x2 2 8 8 4x 4x1 1 16 16 4x 4x2 2 12 12七、生产计划问题的数学模型七、生产计划问题的数学模型 某企业拟用某企业拟用m种资源生产种资源生产n种产品种产品，已知第已知第i种种资源的数量为资源的数量为bi,其单价为其单价为pi,每生产一个单位第每生产一个单位第j种种产品所提供的产值为产品所提供的产值为vj,所消耗的第所消耗的第i种资源的数量种资源的数量为为aij。第第j种产品的合同与指令性计划的产量指标为种产品的合同与指令性计划的产量指标为ej,最高需求量为最高需求量为dj。该企业应如何拟定生产计划该企业应如何拟定生产计划？一、决策变量决策变量 设设xj为第为第j种产品的计划产量种产品的计划产量 二、约束条件约束条件 指标约束指标约束 xj ej,j=1,2,n 需求约束需求约束 xj dj,j=1,2,n 资源约束资源约束 三、目标函数目标函数 总产值总产值七、生产计划问题的数学模型七、生产计划问题的数学模型 j=1naijxj bi,i=1,2,m j=1nm i=1z2=pi(aij xj)总成本总成本z1=vj xj nj=1七、生产计划问题的数学模型七、生产计划问题的数学模型 i=1=vj xj-pi(aij xj)j=1nmj=1n=(vj-pi aij)xjj=1n i=1m令令 cj=vj-pi aij i=1mxj ej,j=1,2,nxj djaijxj bi,i=1,2,m j=1nmax z=cj xjj=1n s.t.则则 总利润总利润 z=z1-z2七、生产计划问题的数学模型七、生产计划问题的数学模型某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A、B两道工序加工。设两道工序加工。设A工序可分别在设备工序可分别在设备A1和和A2上完成，有上完成，有B1、B2、B3三种设备可用于完成三种设备可用于完成B工工序。已知产品序。已知产品可在可在A、B任何一种设备上加工；任何一种设备上加工；产品产品可在任何规格的可在任何规格的A设备上加工，但完成设备上加工，但完成B工工序时，只能在序时，只能在B1设备上加工；产品设备上加工；产品只能在只能在A2与与B2设备上加工。加工单位产品所需工序时间及设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使其他各项数据如下表，试安排最优生产计划，使该厂获利最大。该厂获利最大。七、生产计划问题的数学模型七、生产计划问题的数学模型设备设备产品产品设备有效设备有效台时台时设备加工费设备加工费（单位小时）（单位小时）A15106000300A27910 000321B168124000250B247000783B37114000200原料费（每件）原料费（每件）0.250.350.5售价（每件）售价（每件）1.252.002.8七、生产计划问题的数学模型七、生产计划问题的数学模型解：解：设xijk表示表示产品品i在工序在工序j的的设备k上加工上加工的数量。的数量。约束条件有：束条件有：七、生产计划问题的数学模型七、生产计划问题的数学模型目目标是利是利润最大化，即利最大化，即利润的的计算公式如下：算公式如下：带入数据整理得到：带入数据整理得到：七、生产计划问题的数学模型七、生产计划问题的数学模型因此因此该规划划问题的模型的模型为：有有n种食品种食品,每种食品中含有每种食品中含有m种营养成分种营养成分。食品用食品用 j=1,2,n表示表示，养分用养分用 i=1,2,m表示表示。已知第已知第 j 种种食品单价为食品单价为 cj,每天最大供量为每天最大供量为 dj;而每单位第而每单位第 j种食品所含种食品所含第第 i 种养分的数量为种养分的数量为 aij。假定某种生物每天对第假定某种生物每天对第 i 种养分的种养分的需求量至少为需求量至少为 bi,而每天进食数量限定在而每天进食数量限定在 h1,h2 范围内范围内。试求该生物的食谱试求该生物的食谱，使总成本为最小使总成本为最小。八、食谱问题的数学模型八、食谱问题的数学模型八、食谱问题的数学模型八、食谱问题的数学模型 设设 xj 为每天提供给该生物食用的第为每天提供给该生物食用的第 j 种食品的数量，种食品的数量，则该问题的数学模型为则该问题的数学模型为:s.t.0 xj dj,j=1,2,nmin z=cj xjj=1nj=1 h1 xj h2nj=1 aij xj bi,i=1,2,m n八、食谱问题的数学模型八、食谱问题的数学模型配料配料问题例：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），例：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？要、又使总费用最省？2 1.5原料单价1.007.5010.00 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最 低需要量 甲 乙含量 食物成分八、食谱问题的数学模型八、食谱问题的数学模型解：解：设Xj 表示表示Bj 种食物用量种食物用量九、产品配套问题的数学模型九、产品配套问题的数学模型 某厂制造某种部件，由某厂制造某种部件，由2个个B1零件零件,3个个B2零件配套零件配套组装而成组装而成。该厂有该厂有A1,A2,A3三种机床可加工这两种零三种机床可加工这两种零件件，每种机床的台数每种机床的台数，以及每台机床的生产率如下表所以及每台机床的生产率如下表所示示。求产量最大的生产方案求产量最大的生产方案。九、产品配套问题的数学模型九、产品配套问题的数学模型 一、决策变量一、决策变量 设以设以xij表示每台表示每台Ai(i=1,2,3)机床每个工作日加工机床每个工作日加工Bj(j=1,2)零件的时间零件的时间(单位单位:工作日工作日)；z为为B1,B2零件按零件按 2:3 的比例配套的数量的比例配套的数量(套套/日日)。机床机床种类种类机床机床台数台数每台每台每台每台机床生产率机床生产率(件件/日日)零件零件B1零件零件B2A1320203030A2235354545A3410101818x11x12x21x22x31x32九、产品配套问题的数学模型九、产品配套问题的数学模型 二、约束条件二、约束条件 工时约束工时约束 配套约束配套约束机床机床种类种类总总总总生产率生产率(件件/日日)零件零件B1零件零件B2A160609090A270709090A340407272x11x12x21x22x31x32z=min (60 x11+70 x21+40 x31),(90 x12+90 x22+72x32)1213z (60 x11+70 x21+40 x31)12z (90 x12+90 x22+72x32)13非线性，等价改写成：非线性，等价改写成：或或x11+x12=1x21+x22=1x31+x32=1z-35x11-35x21-20 x31 0z-30 x12-30 x22-24x32 0九、产品配套问题的数学模型九、产品配套问题的数学模型则该问题的数学模型为则该问题的数学模型为:max z s.t.x11 +x12 =1 x21 +x22 =1 x31 +x32 =1z 35x11 35x21 20 x31 0z 30 x12 30 x22 24x32 0z,x11,x12,x21,x22,x31,x32 0线性规划问题的数学模型线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量 Decision variables Decision variables 目标函数目标函数 Objective functionObjective function约束条件约束条件 ConstraintsConstraints其特征是：其特征是：（1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性函数，通常是求最大值或最小值；函数，通常是求最大值或最小值；（2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性不等式或等式。不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？线性规划问题的数学模型目标函数：目标函数：约束条件：约束条件：线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：一般一般LP模型的模型的三类参数三类参数三类参数三类参数：价值系数价值系数价值系数价值系数c c j j，消耗系数消耗系数消耗系数消耗系数a a ij ij，右端常数右端常数右端常数右端常数b b i i.LP模型的模型的三要素三要素三要素三要素：决策变决策变决策变决策变量量量量，目标函数目标函数目标函数目标函数，约束条件约束条件约束条件约束条件.线性规划问题的数学模型向量形式：向量形式：其中：其中：线性规划问题的数学模型矩阵形式：矩阵形式：其中：其中：谢谢观看！谢谢观看！48