第3讲线性规划

1、第三讲第三讲 线性规划模型线性规划模型基础教研部：夏冰基础教研部：夏冰数学规划模型数学规划模型 mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x决策变量决策变量f(x)目标函数目标函数gi(x) 0约束条件约束条件分类：线性规划模型分类：线性规划模型 整数规划与整数规划与01规划模型规划模型 非线性规划模型非线性规划模型 重点：模型的建立和结果的分析重点：模型的建立和结果的分析 某企业在计划期内计划生产甲、乙、丙三种产品。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要在设备这些产品分别需要在设备A、B上加工，需要消耗材料上加工，需要消

2、耗材料C、D，按工艺资料规定，单件产品在不同设备上加工，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表及所需要的资源如表1所示。已知在计划期内设备的加所示。已知在计划期内设备的加工能力各为工能力各为200台时，可供材料分别为台时，可供材料分别为360、300公斤；公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分每生产一件甲、乙、丙三种产品，企业可获得利润分别为别为40、30、50元，假定市场需求无限制。企业决策元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润者应如何安排生产计划，使企业在计划期内总的利润收入最大？收入最大？ 例例1 最优生产计划问题

3、最优生产计划问题 产品产品 资源资源甲甲 乙乙丙丙现有资源现有资源设备设备A A 3 3 1 1 2 2 200 200设备设备B B 2 2 2 2 4 4 200 200材料材料C C 4 4 5 5 1 1 360 360材料材料D D 2 2 3 35 5 300 300利润利润(元元/ /件件) 40 40 30 305050表表1 产品资源消耗产品资源消耗限制条件：限制条件：1、设备的加工能力各为、设备的加工能力各为200台；台；2、可供材料分别为、可供材料分别为360、300公斤。公斤。问题分析：问题分析：目标：总的利润收入最大。目标：总的利润收入最大。其中每生产一件甲、乙、丙三

4、种产品，企业可获得其中每生产一件甲、乙、丙三种产品，企业可获得利润分别为利润分别为4040、3030、5050元。元。符号说明：符号说明：设设x1、x2、x3 分别为甲、乙、丙三种产品的产量；分别为甲、乙、丙三种产品的产量；Z为为总的利润收入。总的利润收入。12312332200224200 xxxxxx 产品产品 资源资源甲甲 乙乙丙丙现有现有资源资源设备设备A A3 31 12 2200200设备设备B B2 22 24 4200200材料材料C C4 45 51 1360360材料材料D D2 23 35 5300300利润利润( (元元/ /件件) ) 4040 30305050建立模

5、型：建立模型：1 1、总的利润收入、总的利润收入123403050Zxxx 2 2、加工能力限制为、加工能力限制为200200台台3 3、可供材料分别为、可供材料分别为360360、300300公斤公斤12312345360235300 xxxxxx 321503040maxxxxZ1231231231231233220022420045360. .235300000 xxxxxxxxxs txxxxxx ，应用应用Lingo软件求得：软件求得：X=(50,30,10)时时,maxZ=3400综上所述，建立线性规划模型：综上所述，建立线性规划模型：模型求解：模型求解：例例2 2 食用油加工计划

6、食用油加工计划 加工一种食用油需要精炼若干种原油并把它们混合起来。原油来源有两类共5种：植物油(VEG1，VEG2)、 非植物油（OIL1，OIL2，OIL3），购买每种原油的价格（镑/吨）见表1： VEG1VEG2OIL1OIL2OIL3110120130110115表1： 最终产品以150镑/吨价格出售。 植物油和非植物油需要在不同的生产线上进行精炼。每月能够精炼的植物油不超过 200吨，非植物油不超过 250 吨；在精炼过程中，重量没有损失，精炼费用可忽略不计。最终产品要符合硬度的技术条件。按照硬度计量单位，它必须在 36 之间。假定硬度的混合是线性的，而原油的硬度见表 2： 表 2VE

7、G1 VEG2OIL1OIL2OIL38.86.12.04.25.0问：为使利润最大，应该怎样制定它的月采购和加工计划？1确定决策变量 设 x1，x5 分别代表需要采购的 5 种原油的吨数，y 代表需要加工的成品油的吨数。2确定约束条件 关于植物油：x1 + x2 200关于非植物油：x3 + x4 + x5 250硬度上限：8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 6y硬度下限：8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 3y连续性（均衡性）：x1 + x2 + x3 + x4 + x5 = y非负性：xi 0（i =1, , 5），y 03

8、确定目标函数 目标是使利润最大，即出售产品的收入扣除原油成本之后所得最大：150y 110 x1 120 x2 130 x3 110 x4 115x5 最大。 建立线性规划模型： 于是月采购与生产计划为：原油 VEG1VEG2OIL1OIL2OIL3采购量159.259340.740702500生产量：450总利润：1.7593104 某商场决定：营业员每周连续工作某商场决定：营业员每周连续工作5 5天后连续天后连续休息休息2 2天，轮流休息。根据统计，商场每天需要的天，轮流休息。根据统计，商场每天需要的营业员如下表所示。营业员如下表所示。问：商场人力资源部应如何安排每天的上班问：商场人力资源

9、部应如何安排每天的上班人数，使商场总的营业员最少？人数，使商场总的营业员最少？ 星期星期需要人数需要人数星期星期需要人数需要人数一一300300五五480480二二300300六六600600三三350350日日550550四四400400练习练习1 1 雇用营业员雇用营业员123456714567125671236712347123452345634567min300300350400. .4806005500,1,2,7jZxxxxxxxxxxxxxxxxxxxxxxxxxxxs txxxxxxxxxxxxxxxxj 解：设解：设XjXj( ( j j=1=1，2 2，7)7)为休息为休息

10、2 2天后星期一到星期天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为日开始上班的营业员，则这个问题的线性规划模型为 安排生产计划安排生产计划, 满足每周的需求满足每周的需求, 使使4周总费用最小。周总费用最小。存贮费存贮费: :每周每千箱饮料每周每千箱饮料 0.2千元。千元。 例例3 3 饮料厂的生产与检修计划饮料厂的生产与检修计划 在在4周内安排一次设备检修，占用当周周内安排一次设备检修，占用当周15千箱生产能千箱生产能力，能使检修后每周增产力，能使检修后每周增产5千箱，检修应排在哪一周千箱，检修应排在哪一周? ? 周次周次需求量需求量(千箱千箱)生产能力生产能力(千箱千箱)

11、成本成本(千元千元/千箱千箱)115305.0225405.1335455.4425205.5合计合计100135 某种饮料某种饮料4周的需求量、生产能力和成本周的需求量、生产能力和成本问题分析问题分析 除第除第4周外每周的生产能力超过每周的需求；周外每周的生产能力超过每周的需求； 生产成本逐周上升；生产成本逐周上升； 前几周应多生产一些。前几周应多生产一些。 周次周次需求需求能力能力11530225403354542520合计合计100135成本成本5.05.15.45.5 饮料厂在第饮料厂在第1周开始时没有库存；周开始时没有库存； 从费用最小考虑从费用最小考虑, , 第第4周末不能有库存；

12、周末不能有库存； 周末有库存时需支出一周的存贮费，周末有库存时需支出一周的存贮费， 存贮费存贮费:0.2 (千元千元/周周千箱千箱) ； 每周末的库存量等于下周初的库存量。每周末的库存量等于下周初的库存量。 模型假设模型假设 x1 x4：第：第14周周的生产量的生产量y1 y3：第：第13周末周末库存量库存量符号说明符号说明 目标函数目标函数约束条件约束条件产量、库存与需求平衡产量、库存与需求平衡 )( 2 . 05 . 54 . 51 . 50 . 53214321yyyxxxxzMin1511 yx25212yyx35323yyx2534 yx20,4540,304321xxxx能力限制能

13、力限制非负限制非负限制 0,3214321yyyxxxx建立模型建立模型模型求解模型求解 4周生产计划的总费用为周生产计划的总费用为528 (千元千元) 最优解：最优解： x1 x4：15，40，25，20； y1 y3： 0，15，5 .周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5产量产量15402520库存库存01550思考：思考：在在4 4周内安排一次设备检修，占用当周内安排一次设备检修，占用当周周1515千箱生产能力，能使检修后每周增产千箱生产能力，能使检修后每周增产5 5千千箱，检修应排在哪一周箱，检修应排在哪一周? ? 某汽车需要

14、用甲、乙、丙三种规格的轴各一某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是根，这些轴的规格分别是1.5，1，0.7(m)，这些轴，这些轴需要用同一种圆钢来做，圆钢长度为需要用同一种圆钢来做，圆钢长度为4 m。现在要。现在要制造制造1000辆汽车，最少要用多少圆钢来生产这些辆汽车，最少要用多少圆钢来生产这些轴？轴？ 练习练习2 2 合理用料问题合理用料问题 方案方案规格规格1 12 23 34 4 5 56 67 78 89 91010需求需求量量y y1 1( (根根) ) 2 22 21 1 1 11 1 0 0 0 00 00 00 010001000y y2 2 1 10

15、02 2 1 10 0 4 4 3 32 21 10 010001000y y3 3 0 01 10 0 2 23 3 0 0 1 12 24 45 510001000余料余料( (m m) )0 0 0.30.3 0.50.5 0.10.1 0.40.4 0 0 0.30.3 0.60.6 0.20.20.50.5解：这是一个条材下料问题解：这是一个条材下料问题 ，设切口宽度为零。，设切口宽度为零。 设设一根圆钢切割成甲、乙、丙三种轴的根数分别为一根圆钢切割成甲、乙、丙三种轴的根数分别为y y1 1，y y2 2，y y3 3, ,则切割方式可用不等式则切割方式可用不等式1.51.5y y1

16、 1+ +y y2 2+0.7+0.7y y3 344表示，求表示，求这个不等式关于这个不等式关于y y1 1，y y2 2，y y3 3的非负整数解。象这样的非的非负整数解。象这样的非负整数解共有负整数解共有1010组，也就是有组，也就是有1010种下料方式，如表所种下料方式，如表所示。示。10112345134678924578910min221000243210002324510000,1,2,10jjjZxxxxxxxxxxxxxxxxxxxxxj 设设xj ( j = 1,2,10)为第为第 j 种下料方案所用圆钢种下料方案所用圆钢的根数，则用料最少数学模型的根数，则用料最少数学模型 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆， 那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？课后练习：课后练习： 汽车厂生产计划汽车厂生产计划 汽车厂