第1讲：线性规划问题及其数学模型

第1讲线性规划问题及其数学模型浙江工业大学经贸管理学院曹柬一、几个现实问题例1(P11)、美佳公司计划制造甲、乙两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序时间以及每天可用于这两种家电的能力、各售出一件时的获利情况，如下表：甲乙每天可用能力设备A(h)0515设备B(h)6224调试工序(h)115单位产品获利(元)21问题：该公司每天应制造两种家电各多少件，使公司获利最多？生产计划安排问题！运筹学第1讲：线性规划问题及其数学模型线性规划模型:设生产甲产品x1个单位、生产乙产品x2个单位,z为总收益，则目标函数：maxz=2x1+x2约束条件：s.t.5x1≤156x1+2x2≤24x1+x2≤5x1,x2≥0运筹学第1讲：线性规划问题及其数学模型例2(2-9)、某公司由于生产需要，共需要A，B两种原料至少350吨(A,B两种材料有一定替代性)，其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？物料购置(供应)问题！运筹学第1讲：线性规划问题及其数学模型解：设购买A、B两种原料各x1，x2件，z为购买总成本，则该问题的线性规划模型为：minz=2x1+3x2s.t.x1+x2≥350x1≥1252x1+x2≤600x1≥0,x2≥0。运筹学第1讲：线性规划问题及其数学模型例3(2-6)、某建筑工程施工中需要制作10000套钢筋，每套钢筋由2.9m、2.1m和1.5m三种不同长度的钢筋各一根组成，它们的直径和材质相同。目前在市场上采购到的同类钢筋的长度每根均为7.4m，问应购进多少根这种钢筋才能满足工程的需要？方案1方案2方案3方案4方案5方案6方案7方案82.9m120101002.1m002211301.5m31203104合计7.47.37.27.16.66.56.36.0剩余料头00.10.20.30.80.91.11.4裁料问题！运筹学第1讲：线性规划问题及其数学模型例4(2-10)、某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，已知产品的规格要求、产品的单价、每天能供应的原料数量及原料单价，分别见下表。问：该厂应如何安排生产，使利润收入为最大？产品名称规格要求单价（元/kg）甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料名称每天最多供应量单价（元/kg）11006521002536035配料问题！运筹学第1讲：线性规划问题及其数学模型解：设xij表示第i（i=1,2,3，1=甲，2=乙，3=丙）种产品中原料j(j=1,2,3)的含量。如x23就表示乙产品中第3种原材料的含量。maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33s.t.0.5x11-0.5x12-0.5x13≥0-0.25x11+0.75x12-0.25x13≤00.75x21-0.25x22-0.25x23≥0-0.5x21+0.5x22-0.5x23≤0x11+x21+x31≤100x12+x22+x32≤100x13+x23+x33≤60xij≥0,i=1,2,3;j=1,2,3。最优值:500最优解：x11=100,x12=50,x13=50,其余xij=0.运筹学第1讲：线性规划问题及其数学模型例5(P11-例2)、某公司在今后4个月内需租用仓库堆放物资。每个月所需的仓库面积分别为：租赁问题！月份1234所需面积/(100m2)15102012租借合同期限越长，则享受的折扣优惠也越大，如下所示：合同租借期限1个月2个月3个月4个月每100m2租借费/元2800450060007300租借合同每月初都可办理，每份合同具体规定租用面积数和期限。因此该公司可根据需要，在任何一个月初办理租借合同。每次办理可签一份、也可签若干份租用面积和租用期限不同的合同。试求出一个所付租借费最小的租借方案。运筹学第1讲：线性规划问题及其数学模型LP的数学模型一般式LP模型的简写式LP模型的向量式二、LP问题的数学模型运筹学第1讲：线性规划问题及其数学模型LP的数学模型一般式112211112211211222221122maxmin..0,1,2,,nnnnnnmmmnnmjzcxcxcxaxaxaxbstaxaxaxbaxaxaxbxjn或或＝，或＝，或＝，LP模型的简写式11maxmin,1,2,,..0,1,2,,njjjnijjijjzcxaxbimstxjn或或＝，LP模型的向量式maxmin..0,zCXstAXbX或或＝，121212111212122212×,,,,,,,,,TnnTnnnmmmnmnXxxxCcccbbbbaaaaaaAaaa为列向量；为行向量；为列向量；为系数矩阵。例6：将P11-例1的LP模型表示为向量式例7：习题2-4，并将模型表示为向量式[人员安排问题]：某宾馆每天各时间段（每4h为一个时间段）所需的服务员人数如下表所示，这些服务员在某一时段开始上班后要连续工作8h，问该宾馆至少需要多少名服务员才能满足需要。班次时间段所需人数班次时间段所需人数16:00–10:0060418:00–22:0050210:00–14:0070522:00–2:0020314:00–18:006062:00–6:0030作业：习题2-3，习题2-5*运筹学第1讲：线性规划问题及其数学模型习题2-5[选址问题]：考虑甲、乙、丙三地，每地都出产一定数量的原料，也消费一定数量的产品，如下表所示。已知制成每吨产品需3t原料，各地之间地距离如右下图所示。假定每万吨原料每公里的运价是5000元，每万吨产品每公里的运价为6000元。由于地区条件的差异，在不同地点设厂的生产费用也不同，如下表所示。问究竟在哪些地方设厂，规模多大，才能使总费用最小？另外，由于其他条件限制，在乙地建厂的规模（生产的产品数量）不能超过5万吨。运筹学第1讲：线性规划问题及其数学模型地点年产原料(万吨)年消费产品(万吨)生产费用(万元/万吨)甲207150乙1613120丙240100150km丙乙甲100km200km