线性规划数学模型学习教案

1、线性规划线性规划(xin xn u hu)数学模型数学模型第一页，共48页。第1页/共48页第二页，共48页。第2页/共48页第三页，共48页。第3页/共48页第四页，共48页。第4页/共48页第五页，共48页。第5页/共48页第六页，共48页。 某化工厂要用三种原料某化工厂要用三种原料 A，B，C 混合配制三种不同规混合配制三种不同规格格(gug)的产品的产品 X，Y，Z。有关数据如下：。有关数据如下： 产品产品规规 格格单价单价(元元/kg)X原料原料D不少于不少于50%原料原料P不超过不超过25%50Y原料原料D不少于不少于25%原料原料P不超过不超过50%35Z不不 限限25原料原料最

2、大供量最大供量(kg/天天)单价单价(元元/kg)A100B100C60应如合配制，才能使利润应如合配制，才能使利润(lrn)达到最大？达到最大？表表2-3表表2-4第6页/共48页第七页，共48页。一、决策(juc)变量 设以 xij 表示每天生产的第i 种产品中所含第j 种原料的数量(kg，右表)。ji A B CXYZx11 x12 x13x21 x22 x23x31 x32 x33二、约束条件二、约束条件 规格规格(gug)约束约束(据表据表2-3)x11+ x12 + x13x11 0.50 x11+ x12 + x13x12 0.25x11+ x12 + x13x21 0.25x1

3、1+ x12 + x13x22 0.50第7页/共48页第八页，共48页。改写改写(gixi)成成 - - x11 + x12 + x13 0 - - x11+ 3 x12 - -x13 0- -3 x21 +x22 + x23 0 x21 +x22 - - x23 0 资源资源(zyun)约束约束(据表据表2-4)x11+ x21 + x31 100 x12+ x22 + x32 100 x13+ x23 + x33 60第8页/共48页第九页，共48页。三、目标三、目标(mbio)函数函数 总产值总产值(据据表表2-3)产品产品(chnpn)X的产值的产值: 50(x11+ x12 + x

4、13 )产品产品(chnpn)Y的产值的产值: 35(x21+ x22 + x23 )产品产品(chnpn)Z的产值的产值: 25(x31+ x32 + x33 )以上三项之和即以上三项之和即总产值总产值。 总成本总成本(据据表表2-4)原料原料A的成本的成本: (x11+ x21 + x31 )原料原料B的成本的成本: (x12+ x22 + x32 )原料原料C的成本的成本: (x13+ x23 + x33 )以上三项之和即以上三项之和即总成本总成本。第9页/共48页第十页，共48页。 目标函数目标函数(hnsh)为：为： 总利润总利润 = 总产值总产值 - 总成本总成本max =- -1

5、5x11+25x12+15x13- -30 x21+10 x22- -40 x31- -10 x33 该问题该问题(wnt)(wnt)的数学模型为的数学模型为: :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页第十一页，共48页。第11页/共48页第十二页，共48页。 成分含量成分含量(

6、%)(%) 原原 料料 化学成分化学成分 甲甲 乙乙 产品成分产品成分 最低含量最低含量(%)(%)A B C 12 3 2 3 3 15 4 2 5 成本（元成本（元/ /千克）千克） 3 2 min = 3x1+2x2 12 x1 +3x2 4 2 x1 +3x2 2s.t. 3 x1+15x2 5 x1 +x2 = 1 x1 , , x2 0配料配料(pi lio)(pi lio)平衡条件平衡条件第12页/共48页第十三页，共48页。第13页/共48页第十四页，共48页。练习：练习： 某昼夜服务的公交线路每天各时间段内某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数所需司机和乘务

7、人员人数(rn sh)如下表所示：如下表所示：班次班次时间时间所需人员所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工设司机和乘务人员分别在各时间段开始时上班，并连续工作作8小时，问该公交线路应怎样安排司机和乘务人员，即能小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要满足工作需要(xyo)，又使配备司机和乘务人员的人数减，又使配备司机和乘务人员的人数减少少?第14页/共48页第十五页，共48页。 0,302050607060

8、.min654321655443322161654321xxxxxxxxxxxxxxxxxxtsxxxxxx此问题最优解：此问题最优解：x150， x220， x350， x40， x520， x610，一共一共(ygng)需要司机和乘务员需要司机和乘务员150人。人。第15页/共48页第十六页，共48页。第16页/共48页第十七页，共48页。 练习： 制造某种机床，需要 A,B,C三种轴件，其规格与数量如表所示，各类轴件都用5.5米长的同一种圆钢下料。 若计划(jhu)生产100台机床，最少需要用多少根圆钢？第17页/共48页第十八页，共48页。轴类轴类 规格：长度（米）规格：长度（米） 每

9、台机床所需轴件数每台机床所需轴件数 A 3.1 1 B 2.1 2 C 4 余料余料 找出全部找出全部(qunb)省料截法省料截法一根圆钢所截各类轴件数一根圆钢所截各类轴件数 截法截法轴类轴类 轴轴 件件 需要量需要量 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页第十九页，共48页。min z = x1 + x2 + x3 + x4 + x5s.t.x1 +x2 100 x1 +2x3 +x4 200 2x2 +x3 +2x4 +4x5 400 x1， x2

10、， x3， x4， x5 0则该问题则该问题(wnt)的数学模型的数学模型为为:设第设第 j 种截法下料种截法下料 xj 根。根。第19页/共48页第二十页，共48页。例：现有一批某种型号的圆钢例：现有一批某种型号的圆钢(yun n)长长8米，需要截米，需要截取取2.5米长的毛坯米长的毛坯100根，长根，长1.3米的毛坯米的毛坯200根。问如何才根。问如何才能既满足需要，又能使总的用料最少？能既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次其次(qc)要求这些方案的总体能裁下所有

11、各种规格的圆钢，以满足对各要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出种不同规格圆钢的需要并达到省料的目的，为此可以设计出4种下料方案种下料方案以供套裁用。以供套裁用。2.5m32101.3m0246料头料头00.40.30.2第20页/共48页第二十一页，共48页。 )4.3.2.1(020064210023min4323214321jxxxxxxxxxxxZj设按方案设按方案(fng n)、下料的原材料根数分别为下料的原材料根数分别为xj (j=1，2,3,4)，可列出下面的数学模型：，可列出下面的数学模型：第21页/共48页第

12、二十二页，共48页。第22页/共48页第二十三页，共48页。例例 某厂拟生产甲、乙两种产品某厂拟生产甲、乙两种产品(chnpn)(chnpn)，每件利润分，每件利润分别为别为3 3、5 5百元。百元。甲、乙产品甲、乙产品(chnpn)(chnpn)的部件各自在的部件各自在A A、B B两个车间分别生产，两个车间分别生产，每件甲、每件甲、乙产品乙产品(chnpn)(chnpn)的部件分别需要的部件分别需要A A、B B车间的生产能力车间的生产能力1 1、2 2工工时。两件时。两件产品产品(chnpn)(chnpn)的部件最后都要在的部件最后都要在C C车间装配，装配每件甲、车间装配，装配每件甲、

13、乙产品乙产品(chnpn)(chnpn)分别分别需要需要3 3、4 4工时，三车间每天可用于生产这两种产品工时，三车间每天可用于生产这两种产品(chnpn)(chnpn)的工时分别的工时分别为为8 8、1212、3636，问应如何安排生产这两种产品，问应如何安排生产这两种产品(chnpn)(chnpn)才能才能获利最多？获利最多？第23页/共48页第二十四页，共48页。 x1 x2决策决策(juc)变变量量 = 3x1 +5x20目标目标(mbio)函数函数x1 8 2x2 12 3x1 + 4x2 36 函数约束函数约束 x1 ， x2 0 非负性约束非负性约束甲甲 乙乙1030 2 4 8

14、 12 36A B C车间车间产品产品单耗（工时单耗（工时/ /件）件）最大生产能力最大生产能力（工时（工时/ /天）天）单位利润单位利润（百元（百元/ /件）件） 3 5第24页/共48页第二十五页，共48页。练习：某企业计划生产练习：某企业计划生产(shngchn)甲、乙两种产品。这些甲、乙两种产品。这些产品分别要在产品分别要在A、B、C、D、四种不同的设备上加工。按工、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产下表所示，企业决策者应如何安排生产(shngchn)计划，计划

15、，使企业总的利润最大？使企业总的利润最大？ 设设 备备产产 品品 A B C D利润（元）利润（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12第25页/共48页第二十六页，共48页。第26页/共48页第二十七页，共48页。 某企业拟用m种资源生产n种产品(chnpn)，已知第i种资源的数量为bi,其单价为pi,每生产一个单位第j种产品(chnpn)所提供的产值为vj, 所消耗的第i种资源的数量为aij。第j种产品(chnpn)的合同与指令性计划的产量指标为ej, 最高需求量为dj。 该企业应如何拟定生产计划？第27页/共48页第二十八页，

16、共48页。 一、决策变量 设xj为第j种产品的计划产量 二、约束条件 指标约束 xj ej , j = 1,2, ,n 需求约束 xj dj , j = 1,2, ,n 资源(zyun)约束 三、目标函数 总产值 j=1naijxj bi, , i = 1, ,2, , ,m j=1nm i=1z2=pi(aij xj) 总成本总成本z1=vj xj nj=1第28页/共48页第二十九页，共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,

17、 , , ,nxj djaijxj bi, , i =1, ,2, , ,m j=1nmax z=cj xjj=1n s.t.则则 总利润总利润(lrn)(lrn) z = z1 -z2第29页/共48页第三十页，共48页。某厂生产某厂生产(shngchn)、三种产品，三种产品，都分别经都分别经A、B两道工序加工。设两道工序加工。设A工序可分别在设工序可分别在设备备A1和和A2上完成，有上完成，有B1、B2、B3三种设备可用于三种设备可用于完成完成B工序。已知产品工序。已知产品可在可在A、B任何一种设备上任何一种设备上加工；产品加工；产品可在任何规格的可在任何规格的A设备上加工，但完设备上加工

18、，但完成成B工序时，只能在工序时，只能在B1设备上加工；产品设备上加工；产品只能在只能在A2与与B2设备上加工。加工单位产品所需工序时间设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产及其他各项数据如下表，试安排最优生产(shngchn)计划，使该厂获利最大。计划，使该厂获利最大。第30页/共48页第三十一页，共48页。设备设备产品产品设备有效设备有效台时台时设备加工费设备加工费（单位小时）（单位小时）27910 000321B168124000250B247000783B37114000200原料费（每件）原料费（每件）0.250.350.5

19、售价（每件）售价（每件）1.252.002.8第31页/共48页第三十二页，共48页。）（上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品设备设备设备设备）（设备（设备）（设备（设备设备设备3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(60001053223122212122111231221211121111233221222211213

20、12212112211111 kjixxxxxxxxxxxxxxxxxxxxxijk第32页/共48页第三十三页，共48页。 5131)()(ii该该设设备备实实际际使使用用台台时时每每台台时时的的设设备备费费用用该该产产品品件件数数销销售售单单价价原原料料单单价价利利润润带入数据整理带入数据整理(zhngl)得到：得到：12332212222112131221221111211135. 023. 1448. 05 . 0375. 0915. 136. 115. 1775. 075. 0maxxxxxxxxxxx 第33页/共48页第三十四页，共48页。 ）（3,2,1;2,1;3,2,104

21、000770001144000861000012976000105.35.023.1448.05.0375.0915.136.115.1775.075.0max322312221212211123122121112111123322122221121312212112211111123322122221121312212211112111kjixxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxijk第34页/共48页第三十五页，共48页。 有有n种食品种食品, 每种食品中含有每种食品中含有m种营养成分。食品用种营养成分。食品用 j = 1,2, ,n表示，养分用表示，养分用 i

22、 = 1,2, ,m表示。已知第表示。已知第 j 种种食品单价为食品单价为 cj, 每天最大供量为每天最大供量为 dj; 而每单位而每单位(dnwi)第第 j种食品所含种食品所含第第 i 种养分的数量为种养分的数量为 aij。 假定某种生物每天对第假定某种生物每天对第 i 种养分种养分的的需求量至少为需求量至少为 bi, 而每天进食数量限定在而每天进食数量限定在 h1, h2 范围内。范围内。 试求该生物的食谱，使总成本为最小。试求该生物的食谱，使总成本为最小。 第35页/共48页第三十六页，共48页。 设设 xj 为每天提供给该生物为每天提供给该生物(shngw)食用的第食用的第 j 种食品

23、的数量，种食品的数量，则该问题的数学模型为则该问题的数学模型为: 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页第三十七页，共48页。例：某人每天食用例：某人每天食用(shyng)甲、乙两种食物（如猪肉、鸡蛋），甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用其资料如下：问两种食物各食用(shyng)多少，才能既满足需多少，才能既满足需要、又使总费用最省？要、又使总费用最省？ 2 1.5原料单价1.007.5010.00 0.1

24、0.15 1.7 0.75 1.10 1.30A1A2A3 最 低需要量 甲 乙含量 食物成分第37页/共48页第三十八页，共48页。 0,00.1030.110.150.775.070.100.115.010.05.12min2121212121xxxxxxxxxxZ第38页/共48页第三十九页，共48页。 某厂制造某种部件，由2个B1零件, 3个B2零件配套(pi to)组装而成。该厂有A1, A2, A3三种机床可加工这两种零件，每种机床的台数，以及每台机床的生产率如下表所示。 求产量最大的生产方案。第39页/共48页第四十页，共48页。 一、决策变量一、决策变量 设以设以xij表示每台

25、表示每台Ai (i=1, 2, 3)机床每个工作日机床每个工作日加工加工Bj( j = 1, 2 )零件零件(ln jin)的时间的时间(单位单位:工作日工作日)； z为为B1, B2零件零件(ln jin)按按 2: 3 的比例配套的比例配套的数量的数量(套套/日日)。机床机床种类种类机床机床台数台数机床生产率机床生产率( 件件/日日 )零件零件B1零件零件B2A13A22A34x11x12x21x22x31x32第40页/共48页第四十一页，共48页。 二、约束条件二、约束条件 工时工时(gngsh)约束约束 配套配套(pi to)约束约束机床机床种类种类生产率生产率( 件件/日日 )零件零件B1零件零件B2A1A2A3x11x12x21x22x3