第3讲线性规划

第三讲线性规划模型哈尔滨金融学院《数学建模》基础教研部：夏冰数学规划模型

x~决策变量f(x)~目标函数gi(x)0~约束条件分类：线性规划模型整数规划与0－1规划模型非线性规划模型

重点：模型的建立和结果的分析哈尔滨金融学院《数学建模》某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？哈尔滨金融学院《数学建模》例1最优生产计划问题产品资源甲乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润(元/件)

403050表1产品资源消耗哈尔滨金融学院《数学建模》哈尔滨金融学院《数学建模》限制条件：1、设备的加工能力各为200台；2、可供材料分别为360、300公斤。问题分析：目标：总的利润收入最大。其中每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元。符号说明：设x1、x2、x3

分别为甲、乙、丙三种产品的产量；Z为总的利润收入。产品

资源甲

乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润(元/件)403050哈尔滨金融学院《数学建模》建立模型：1、总的利润收入2、加工能力限制为200台3、可供材料分别为360、300公斤应用Lingo软件求得：X=(50,30,10)时,maxZ=3400哈尔滨金融学院《数学建模》综上所述，建立线性规划模型：模型求解：例2食用油加工计划

加工一种食用油需要精炼若干种原油并把它们混合起来。原油来源有两类共5种：植物油(VEG1，VEG2)、非植物油（OIL1，OIL2，OIL3），购买每种原油的价格（镑/吨）见表1：

VEG1VEG2OIL1OIL2OIL3110120130110115表1：

最终产品以150镑/吨价格出售。植物油和非植物油需要在不同的生产线上进行精炼。每月能够精炼的植物油不超过200吨，非植物油不超过250吨；在精炼过程中，重量没有损失，精炼费用可忽略不计。哈尔滨金融学院《数学建模》最终产品要符合硬度的技术条件。按照硬度计量单位，它必须在3—6之间。假定硬度的混合是线性的，而原油的硬度见表2：表2VEG1VEG2OIL1OIL2OIL38.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），y03．确定目标函数目标是使利润最大，即出售产品的收入扣除原油成本之后所得最大：150y110x1

120x2

130x3

110x4

115x5

最大。哈尔滨金融学院《数学建模》建立线性规划模型：

哈尔滨金融学院《数学建模》于是月采购与生产计划为：原油VEG1VEG2OIL1OIL2OIL3采购量159.259340.740702500生产量：450总利润：1.7593104某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如下表所示。问：商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少？星期需要人数星期需要人数一300五480二300六600三350日550四400哈尔滨金融学院《数学建模》练习1雇用营业员解：设Xj(j=1，2，…，7)为休息2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为哈尔滨金融学院《数学建模》安排生产计划,满足每周的需求,使4周总费用最小。存贮费:每周每千箱饮料0.2千元。例3饮料厂的生产与检修计划在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?

周次需求量(千箱)生产能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合计100135

某种饮料4周的需求量、生产能力和成本哈尔滨金融学院《数学建模》问题分析除第4周外每周的生产能力超过每周的需求；生产成本逐周上升；前几周应多生产一些。周次需求能力11530225403354542520合计100135成本5.05.15.45.5

哈尔滨金融学院《数学建模》饮料厂在第1周开始时没有库存；从费用最小考虑,第4周末不能有库存；周末有库存时需支出一周的存贮费，存贮费:0.2(千元/周•千箱)

；每周末的库存量等于下周初的库存量。模型假设

哈尔滨金融学院《数学建模》x1~x4：第1~4周的生产量y1~y3：第1~3周末库存量符号说明

目标函数约束条件产量、库存与需求平衡

能力限制非负限制

建立模型哈尔滨金融学院《数学建模》模型求解

4周生产计划的总费用为528(千元)最优解：

x1~x4：15，40，25，20；

y1~y3：

0，15，5.周次需求能力11530225403354542520成本5.05.15.45.5产量15402520库存01550哈尔滨金融学院《数学建模》思考：在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?

哈尔滨金融学院《数学建模》某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7(m)，这些轴需要用同一种圆钢来做，圆钢长度为4m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？哈尔滨金融学院《数学建模》练习2合理用料问题

方案规格12345678910需求量y1(根)22111000001000y210210432101000y3

01023012451000余料(m)00.30.50.10.400.30.60.20.5解：这是一个条材下料问题，设切口宽度为零。设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式1.5y1+y2+0.7y3≤4表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解共有10组，也就是有10种下料方式，如表所示。哈尔滨金融学院《数学建模》设xj(j=1,2…,10)为第j种下料方案所用圆钢的根数，则用料最少数学模型为:哈尔滨金融学院《数学建模》如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？课后练习：汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。小型中型大型现有量钢材（吨）1.5

3

5600劳动时间（小时）280