运筹学ppt课件.ppt

线性规划问题的四种主要类型1 资源分配问题 资源约束 2 成本收益平衡问题 收益约束 3 网络配送问题 确定需求约束 4 混合问题线性规划问题的建模与应用 第三章线性规划建模与应用 1 资源分配问题 LP模型中每一个函数约束均为资源约束 使用的资源数量 可用的资源数量问题中的三类数据 1 每种资源的可供量 2 单位活动消耗的资源量 3 每一种活动的单位利润 2 例1某公司是商务房地产开发项目的主要投资商 目前该公司有机会在三个项目中投资 项目1 高层办公楼 项目2 宾馆 项目3 购物中心 各项目都要求四期投资 定金 一年 二年 三年追加投资 单位 百万元 公司目前有2500万元资金可供投资 预计一年后又可获得2000万元 两年后获得另外2000万元 三年后还有1500万元可供投资 那么该公司要按多大比例投资 才能使投资组合获得最大宗净现值 3 这个问题要注意的是 前一期尚未使用的资金 可以在下一期使用 为了简化问题 不考虑资金的利息 因此 每一时间点的资金限制应该是累计的资金 前面的数据表应改为 单位 百万元 目标 总净现值最大 资源约束 各期可获得的资金限制决策变量 xi i 1 2 3表示各项目中的投资比例 4 计算结果 不投资办公楼项目 宾馆项目投资比例为16 5 购物中心项目的投资比例为13 11 总净现值为1811万元 5 成本收益平衡问题 LP模型中每一个函数约束均为收益约束 完成的水平 最低的可接受的水平问题中的三类数据 1 每种收益的最低的可接受的水平 管理决策 2 单位活动对每一种收益的贡献 3 每一种活动的单位成本 6 例2 排班问题 某航空公司准备增加中心机场的往来航班 需雇佣更多的服务人员 分析新的航班时刻表 以确定一天中不同时段为实现客户满意水平必须工作的服务人员数 每班8小时 分5班 各班时间安排 排班16 00 14 00 排班28 00 16 00 排班312 00 20 00 排班416 00 24 00 排班522 00 6 00 问题是 确定各排班的人数 以最小的成本提供令人满意的服务 不同时段在岗 工资不同 7 决策变量 设xi为各排班i的人数 i 1 5 目标函数 人员总费用最少约束条件 每个时段的在岗人数必须不少于最少需要人数 求解结果 总工资每天30610元早6点班48名早8点班31名中午班39名下午4点班43名晚上10点班15名 8 G7 SUMPRODUCT B7 F7 每班人数 总人数 SUM B19 F19 总成本 SUMPRODUCT 单位成本 每班人数 9 网络配送问题 LP模型中每一个函数约束均为确定需要的约束 提供的数量 需求的数量问题中的三类数据 1 需求约束 2 供应约束 3 单位配送成本 10 例3某公司在两个工厂生产某种产品 现收到三个顾客的下个月订单要购买这种产品 这些产品会被单独运送 已知每个顾客的订货量和每个工厂的生产量 以及每个工厂到每个顾客的单位运送成本 公司的物流经理如何组织产品运送 目标 公司的总运输成本最低约束条件 工厂发出的产品数等于产量 顾客收到的产品数等于订货量决策变量 xij为工厂i配送到顾客j的产品数量 11 12 计算结果 总运费20500元 实际运出 SUM B7 D7 实际收到 SUM B7 B8 总成本 SUMPRODUCT 单位运输成本 运输量 13 混合问题 例4 配料问题 某公司计划用A B C三种原料混合调制出三种不同规格的产品甲 乙 丙 产品的规格要求和单价 原料的供应量和单价等数据如表 问 该公司应如何安排生产 才能使总利润最大 决策变量 设xij表示原料i用于产品j的数量目标函数 利润 产品收入 原料支出 14 原料供应量限制 规格要求 非负 15 16 17 线性规划模型的应用 生产计划问题自行生产与外包 副产品 生产与库存问题等2 资金管理问题投资组合优化 连续投资 财务计划 资本预算等3 市场调查问题4 混合配料问题 18 例5某工厂生产甲乙丙三种产品 都有经过铸造 机加工和装配三个车间 甲乙两产品的铸件可以外包协作 也可自行生产 产品丙必须本厂铸造才能保证质量 问 甲乙丙各应生产多少件 甲乙两产品的铸件应由外包协作多少件 19 设x1 x2 x3分别为三道工序全由本公司加工的三种产品件数 x4 x5为外协铸造本公司机加工和装配的甲乙两产品的件数 目标 单位利润 售价 成本 最大 铸造工时限制机加工工时限制装配工时限制非负 将甲乙产品的件数分成有外协铸造 自行铸造两部分 20 总利润 SUMPRODUCT 单位利润 产量 单位利润 B7 SUM B4 B6 实际使用 SUMPRODUCT B11 F11 产量 21 例6某工厂生产A B两种产品 都需经过两道工序 每生产1吨A产品两道工序分别需要2小时 3小时 每生产1吨B产品两道工序分别需要3小时 4小时 可供利用的第一道工序工时为15小时 第二道工序工时为25小时 生产产品B的同时可产出副产品C 每生产1吨产品B 可同时得到2吨产品C而不需要外加任何费用 副产品一部分可以盈利 但剩下的只能报废 报废需要一定的费用 各项费用为 出售产品A每吨盈利400元 出售产品B每吨盈利800元 出售副产品C每吨盈利300元 报废剩余产品C每吨损失200元 市场预测 产品C的最大销量为5吨 问 如何安排A B两种产品的产量使工厂总盈利最大 22 设x1 x2 分别为A B两种产品产量 x3 x4为C产品的销售量和报废量 目标 总盈利最大 副产品C使问题复杂化 23 24 例7某公司根据订单进行生产 公司每月的生产能力为100 每月仓库容量为50 半年内对某产品的需求量 单位生产费用和单位存储费用如表 问 如何确定产品未来半年内每月最佳生产量 才能使总费用最少 决策变量 设每月生产量为xi 每月月末库存量为si目标函数 总费用 生产总费用 库存总费用 最小约束条件 上月库存 本月生产量 市场需求 本月末库存 25 每月生产能力 仓库容量 非负 26 27 28 例8投资组合优化问题 某公司董事会决定将20万元现金进行债券投资 经咨询 现有五种较好的投资对象 黄河汽车 长江汽车 华南电器 西南电器 缜山纸业 为减少风险 董事会要求 对汽车业投资不得超过12万元 对电器业投资不得超过8万元 其中对长江汽车的投资不得超过对汽车业投资的65 对纸业的投资不得低于对汽车业投资的20 该公司应如何投资 才能在满足董事会要求的前提下使得总回报额最大 29 目标值 1 399400X14 200000X27 800000X30 000000X45 600000X52 400000 30 例9连续投资问题 某部门在今后五年内考虑给下列项目投资 情况如下 项目A 从第一年到第四年每年年初度可以投资 并于次年年末收回本利115 项目B 第三年年初可以投资 到第五年末收回本利125 但规定最大投资额不超过4万元 项目C 第二年年初可以投资 到第五年末能收回本利140 但规定最大投资额不超过3万元 项目D 五年内每年年初都可以购买公债 于当年年末归还 并加利息6 该部门现有资金10万元 问应如何确定这些项目的每年投资额 使得第五年末拥有的资金的本利总额最大 31 决策变量 约束条件 手中不应有剩余的资金 目标函数 第五年末获得本利总额最大 32 max1 15x4A 1 25x3B 1 40 x2C 1 06x5Dx1A x1D 10 x2A x2C x2D 1 06x1Dx3A x3B x3D 1 15x1A 1 06x2Dx4A x4D 1 15x2A 1 06x3Dx5D 1 15x3A 1 06x4Dx3B 4x2C 3 33 34 35 36 由 影子价格 可知 第一年初增减投资1万元 将导致第五年末拥有资金的本利增减1 40万元 第二年初增减投资1万元 将导致第五年末拥有资金的本利增减1 32万元 同样 后三年增减投资1万元 将导致第五年末拥有资金的本利分别增减1 22万元 1 15万元 1 06万元 允许增量 和 允许减量 表明 保持影子价格不变的右端值的变化范围 例如第一年初少投资一万元 由表知影子价格不变 故可以由影子价格算出第五年末的本利总额为 14 38 10 9 1 40 14 38 1 40 12 98 万元 项目A的第四年 项目B的第三年 项目C的第二年 项目D的第五年投资在第五年末的回收本利的百分比在目标系数的变化范围内 最优解不能 注意其它变量的系数都为零 因为这些系数未在目标函数中出现 只在约束中贡献 无法作灵敏度分析 37 例10市场调查问题 市场调查公司受某厂的委托 调查消费者对某种新产品的反应情况 该厂对市场调查公司提出以下要求 1 共对500个家庭进行调查 其中至少有200个是没有孩子的家庭 同时至少有200个是有孩子的家庭 2 至少对300个被调查家庭采用问卷式书面调查 对其余家庭可采用口头调查 3 在有孩子的被调查家庭中 至少对50 的家庭采用问卷式书面调查 在没有孩子的被调查家庭中 至少对60 的家庭采用问卷式书面调查 市场调查费用表 问 市场调查公司应如何进行调查 使得在满足厂方要求的条件下 总调查费用最少 38 39 例11混合配料问题 某公司经营一个回收中心 专门从事四种固体废弃物的回收 并将回收物处理 混合成可销售的三种产品 根据混合时各种材料的比例 可将产品分成三种不同等级 A B C 它们的混合成本和售价也不同 回收中心可以从一定渠道收集到所需的固体废弃物 1 对于每种材料 每周必须至少收集并处理一半以上数量2 每周有3万元可用于处理这些材料 该公司是一家专门从事环保业务的公司 其收益全部用于环保事业 公司每周可获3万元的捐款 用于固体废弃物的处理 问公司如何实现每周的总利润最大 40 maxf 5 5 x11 x21 x31 x41 4 5 x12 x22 x32 x42 3 5 x13 x23 x33 x43 x110 4 x11 x21 x31 x41 x310 1 x12 x22 x32 x42 x42 0 1 x12 x22 x32 x42 x131500 x11 x12 x131000 x21 x22 x232000 x31 x32 x33500 x41 x42 x43 1000 决策变量 xij第i种材料 第j等级 混合规格 每周可获得材料量和最少要求处理量 处理成本 目标 总利润 总收入 总成本 41 maxf 5 5 y1 4 5 y2 3 5 y3 y1 x11 x21 x31 x41 y2 x12 x22 x32 x42 y3 x13 x23 x33 x43 x1 x11 x12 x13 x2 x21 x22 x23 x3 x31 x32 x33 x4 x41 x42 x43 x110 4 y1 x310 1 y2 x131500 x21000 x32000 x4500 决策变量 xij第j等级产品中第i种材料用量 混合规格 每周可获得材料量和最少要求处理量 处理成本 目标 总利润 总收入 总成本 各种材料实际处理量 各种等级实际产量 为了表达清晰 引进各种材料实际处理量和各种等级实际产量等七个新的决策变量 42 问题 作为一家专门从事环保事业的公司 公司有责任把每周可获得的四种固体废弃物全部收集并处理完 处理成本先由捐款支付 不够时从销售利润中支付 要求获利最大 43 maxf 5 5 y1 4 5 y2 3 5 y3 30000 3 x1 6 x2 4 x3 5 x4 3 x1 6 x2 4 x3 5 x4 30000 x1 3000 x2 2000 x3 4000 x4 1000 修改目标和成本约束 每周处理量 Objectivevalue 33000 00VariableValueY15000 000Y20 000000Y35000 000X13000 000X22000 000X34000 000X41000 000 X110 000000X212000 000X312000 000X411000 000X120 000000X220 000000X320 000000X420 000000X133000 000X230 000000X332000 000X430 000000 销售所得 5 5y1 3 5y3 45000处理成本 3x1 6x2 4x3 5x4 42000总利润 45000 30000 42000 33000 44 练习 1 某医院的护士分四个班次 每班工作12小时 上班的时间分别是早上6点 中午12点 下午6点和夜间12点 每班需要的人数分别为19人 21 18人和16人 问 每天最少需要派多少护士值班 如果早上6点和中午12点上班的人每月有480元加班费 下午6点和夜间12点上班的人每月分别有400元和600元加班费 那么应该如何安排上班人数 使得医院支付的加班费最少 45 2 某饲养场饲养动物 设每只动物每天至少需要70克蛋白质 3克矿物质 10毫克维生素 先由五种饲料可供选用 每只饲料每千克营养成分含量及单价如下表所示 试确定既能满足动物生长的营养要求 又能使费用最省的选择饲料的方案 46 3 某农场有150亩土地及12万元资金可用于发展生产 农场劳动力情况为秋冬季4000人日 春夏季4200人日 如劳动力本身用不了时可外出干活 春夏季收入15元 人日 秋冬季收入20元 人日 该农场种植三种