线性规划数学模型.pptx

1第一节 线性规划问题的提出线性规划是运筹学的一个重要分支，主要用于研究解决有限资源的最佳分配问题，即如何对有限资源做出最佳方式的调配和最有利的使用，以便最充分地发挥资源的效能，以获取最佳经济效益。它的适用领域非常广泛，从工业、农业、商业、交通运输业、军事的计划和管理及决策到整个国民经济计划的最优方案的提出，都有它的用武之地，是现代管理科学的重要基础和手段之一。第1页/共48页2第一节 线性规划问题的提出线性规划研究的问题主要有以下两类。(1)给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大任务。（如资金、设备、原标材料、人工、时间等）(2)给定一项任务，如何运筹规划，合理安排，以最少资源来完成它。（如产品量最多、利润最大.）线性规划要研究的两类问题中都有一个限制条件：第一类问题是给出一定量的人力、物力和财力等资源；第二类问题是给定一项任务。第2页/共48页3第二节 线性规划问题的数学模型当用线性规划的方法对实际问题进行优化时，必须把这个实际问题用恰当的数学形式表达出来，这个表达的过程，就是建立数学模型的过程。数学模型的建立需要经验和技巧以及有关的专业知识，只有通过大量的实践，在建立模型时才能得心应手。初学时可从题目中所给出的限制条件和目标入手，由限制条件建立起线性方程组，由目标得到目标函数。下面，结合若干个实际问题讨论数学模型的建立。第3页/共48页4一、投资问题的数学模型解（参见教材P15）第4页/共48页5二、配料问题的数学模型解（参见教材P16）第5页/共48页二、配料问题的数学模型 某化工厂要用三种原料某化工厂要用三种原料 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第6页/共48页二、配料问题的数学模型一、决策变量决策变量 设以 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第7页/共48页二、配料问题的数学模型改写成 -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第8页/共48页二、配料问题的数学模型三、目标函数三、目标函数 总产值总产值(据表表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)以上三项之和即以上三项之和即总成本总成本。第9页/共48页二、配料问题的数学模型 目标函数目标函数为：为：总利润总利润总利润总利润=总产值总产值-总成本总成本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第10页/共48页配料问题练习：某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有A，B，C三种化学成分，其含量(%)是:甲为12，2，3；乙为3，3，15。按合同规定，产品中三种化学成分的含量(%)不得低于4，2，5。甲、乙原料成本为每千克3，2元。厂方希望总成本达到最小，则应如何配制该产品？第11页/共48页配料问题 成分含量(%)(%)原 料 化学成分 甲甲 乙乙 产品成分 最低含量(%)(%)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第12页/共48页13三、人力资源问题的数学模型解（参见教材P17）第13页/共48页三、人力资源问题的数学模型练习：练习：某昼夜服务的公交线路每天各时间段内某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：所需司机和乘务人员人数如下表所示：班次班次时间时间所需人员所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少足工作需要，又使配备司机和乘务人员的人数减少?第14页/共48页三、人力资源问题的数学模型解：设xi表示第i班次时开始上班的司机和乘务人员人数。此问题最优解：此问题最优解：x150，x220，x350，x40，x520，x610，一共需要司机和乘务员，一共需要司机和乘务员150人。人。第15页/共48页16四、合理下料问题的数学模型合理下料问题是机械工业常遇到的问题。毛坯车间经常要在长度一定的条形材料或面积一定的板材上切割若干个具有一定形状、尺寸的毛坯。在一般情况下，材料不可能被完全利用，会有边角余料，造成浪费。因此，如何最大限度地减少边角余料，提高材料利用率，使得切割规定数量的毛坯所用材料最少就是合理下料问题所要研究的。例2-5 某车间有一批长度为180cm的钢管(数量充分多)，为了制造零件的需要，要将其截成三种不同长度的管料：70cm、52cm、35cm。规定这三种管料的需要量分别不少于100根、150根和100根。问：应如何下料能使消耗的钢管数量最少？解（参见教材P18）第16页/共48页四、合理下料问题的数学模型 练习：制造某种机床制造某种机床，需要需要 A,B,C三种轴件三种轴件，其规格其规格与数量如表所示与数量如表所示，各类轴件都用各类轴件都用5.5米长的同一种圆钢米长的同一种圆钢下料下料。若计划生产若计划生产100台机床台机床，最少需要用多少根圆钢最少需要用多少根圆钢？第17页/共48页四、合理下料问题的数学模型轴类 规格：长度（米）每台机床所需轴件数 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第18页/共48页四、合理下料问题的数学模型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 根。第19页/共48页四、合理下料问题的数学模型例：现有一批某种型号的圆钢长例：现有一批某种型号的圆钢长8米，需要截取米，需要截取2.5米米长的毛坯长的毛坯100根，长根，长1.3米的毛坯米的毛坯200根。问如何才能根。问如何才能既满足需要，又能使总的用料最少？既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出的，为此可以设计出4种下料方案以供套裁用。种下料方案以供套裁用。2.5m32101.3m0246料头料头00.40.30.2第20页/共48页四、合理下料问题的数学模型设按方案设按方案、下料的原材料根数分别为下料的原材料根数分别为xj(j=1，2,3,4)，可列出下面的数学模型：，可列出下面的数学模型：第21页/共48页22五、运输问题的数学模型问题的提出：某类产品有若干个产地，已知每个生产地的产量；这类产品有若干个消费地，已知每个消费地的需要量。假设总的产量等于总的需要量。问题是如何编制一个最优的运输计划，使从产地到消费地的运输费用最小。解（参见教材P20）第22页/共48页六、产品配比问题的数学模型例例 某厂拟生产甲、乙两种产品，每件利润分别为3 3、5 5百元。甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、乙产品的部件分别需要A、B车间的生产能力1 1、2 2工时。两件产品的部件最后都要在C车间装配，装配每件甲、乙产品分别需要3 3、4 4工时，三车间每天可用于生产这两种产品的工时分别为8 8、1212、3636，问应如何安排生产这两种产品才能获利最多？第23页/共48页产品配比问题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第24页/共48页线性规划问题的数学模型练习：练习：某企业计划生产甲、乙两种产品。这些产品分某企业计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？设设 备备产产 品品 A B C D利润（元）利润（元）甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12第25页/共48页线性规划问题的数学模型解：设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第26页/共48页七、生产计划问题的数学模型 某企业拟用某企业拟用m种资源生产种资源生产n种产品种产品，已知第已知第i种种资源的数量为资源的数量为bi,其单价为其单价为pi,每生产一个单位第每生产一个单位第j种种产品所提供的产值为产品所提供的产值为vj,所消耗的第所消耗的第i种资源的数量种资源的数量为为aij。第第j种产品的合同与指令性计划的产量指标为种产品的合同与指令性计划的产量指标为ej,最高需求量为最高需求量为dj。该企业应如何拟定生产计划该企业应如何拟定生产计划？第27页/共48页 一、决策变量决策变量 设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第28页/共48页七、生产计划问题的数学模型 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第29页/共48页七、生产计划问题的数学模型某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A、B两道工序加工。设两道工序加工。设A工序可分别在设备工序可分别在设备A1和和A2上完成，有上完成，有B1、B2、B3三种设备可用于完成三种设备可用于完成B工工序。已知产品序。已知产品可在可在A、B任何一种设备上加工；任何一种设备上加工；产品产品可在任何规格的可在任何规格的A设备上加工，但完成设备上加工，但完成B工序时，只能在工序时，只能在B1设备上加工；产品设备上加工；产品只能在只能在A2与与B2设备上加工。加工单位产品所需工序时设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。使该厂获利最大。第30页/共48页七、生产计划问题的数学模型设备设备产品产品设备有效设备有效台时台时设备加工费设备加工费（单位小时）（单位小时）A15106000300A27910 000321B168124000250B247000783B37114000200原料费（每件）原料费（每件）0.250.350.5售价（每件）售价（每件）1.252.002.8第31页/共48页七、生产计划问题的数学模型解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：第32页/共48页七、生产计划问题的数学模型目标是利润最大化，即利润的计算公式如下：带入数据整理得到：带入数据整理得到：第33页/共48页七、生产计划问题的数学模型因此该规划问题的模型为：第34页/共48页 有有n种食品种食品,每种食品中含有每种食品中含有m种营养成分种营养成分。食品用食品用 j=1,2,n表示表示，养分用养分用 i=1,2,m表示表示。已知第已知第 j 种种食品单价为食品单价为 cj,每天最大供量为每天最大供量为 dj;而每单位第而每单位第 j种食品所含种食品所含第第 i 种养分的数量为种养分的数量为 aij。假定某种生物每天对第假定某种生物每天对第 i 种养分的种养分的需求量至少为需求量至少为 bi,而每天进食数量限定在而每天进食数量限定在 h1,h2 范围内范围内。试求该生物的食谱试求该生物的食谱，使总成本为最小使总成本为最小。八、食谱问题的数学模型第35页/共48页八、食谱问题的数学模型 设 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第36页/共48页八、食谱问题的数学模型配料问题例：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），例：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？要、又使总费用最省？2 1.5原料单价1.007.5010.00 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最 低需要量 甲 乙含量 食物成分第37页/共48页八、食谱问题的数学模型解：设Xj 表示Bj 种食物用量第38页/共48页九、产品配套问题的数学模型 某厂制造某种部件，由某厂制造某种部件，由2个个B1零件零件,3个个B2零件配套零件配套组装而成组装而成。该厂有该厂有A1,A2,A3三种机床可加工这两种零三种机床可加工这两种零件件，每种机床的台数每种机床的台数，以及每台机床的生产率如下表所以及每台机床的生产率如下表所示示。求产量最大的生产方案求产量最大的生产方案。第39页/共48页九、产品配套问题的数学模型 一、决策变量一、决策变量 设以xij表示每台Ai(i=1,2,3)机床每个工作日加工Bj(j=1,2)零件的时间(单位单位:工作日)；z为B1,B2零件按 2:3 的比例配套的数量(套/日)。机床机床种类种类机床机床台数台数每台每台每台每台机床生产率机床生产率(件件/日日)零件零件B1零件零件B2A1320203030A2235354545A3410101818x11x12x21x22x31x32第40页/共48页九、产品配套问题的数学模型 二、约束条件二、约束条件 工时约束工时约束 配套约束配套约束机床机床种类种类总总总总生产率生产率(件件/日日)零件零件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第41页/共48页九、产品配套问题的数学模型则该问题的数学模型为: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第42页/共48页线性规划问题的数学模型线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量 Decision variables Decision variables 目标函数目标函数 Objective functionObjective function约束条件约束条件 ConstraintsConstraints其特征是：其特征是：（1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性函数，通常是求最大值或最小值；函数，通常是求最大值或最小值；（2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性不等式或等式。不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？第43页/共48页线性规划问题的数学模型目标函数：目标函数：约束条件：约束条件：线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：一般LP模型的三类参数三类参数三类参数三类参数：价值系数价值系数价值系数价值系数c c j j，消耗系数消耗系数消耗系数消耗系数a a ij ij，右端常数右端常数右端常数右端常数b b i i.LP模型的三要素三要素三要素三要素：决策变决策变决策变决策变量量量量，目标函数目标函数目标函数目标函数，约束条件约束条件约束条件约束条件.第44页/共48页线性规划问题的数学模型向量形式：向量形式：其中：其中：第45页/共48页线性规划问题的数学模型矩阵形式：矩阵形式：其中：其中：第46页/共48页47第47页/共48页48感谢您的观看！第48页/共48页