lesson42线性规划问题案例建模及讨论.ppt

五、线性规划问题案例建模及讨论 案例1.工业原料的合理利用 案例2.农场发展规划问题 案例3.最优的货轮装载方案 案例4.合理的仓库租借合同 案例5.招工方案的制定 案例6.配料问题 案例7.人员分配问题 案例8.最佳项目投资方案 案例9.客观评价学生的学习情况 案例1.工业原料的合理利用 要制作100套钢筋架子，每套有长2.9米、2.1米和1.5米的钢筋 各一根。已知原材料长7.4米，应如何切割使用原材料最省。 解 下面几种方案都是能节省材料的好方案（见下表）。 080302010料头（米） 6671727374合计（米） 1 3 1 22 2 2 1 1 3 29米 21米 15米 下料数 方案 长度 设方案用 x1 根，方案用 x2 根，方案用 x3 根， 方案用 x4 根，方案用 x5 根。 则线性规划模型为： 080302010料头（米） 6671727374合计（米） 1 3 1 22 2 2 1 1 3 29米 21米 15米 下料数 方案 长度 添加人工变量后，模型变为： 方案30根，方案10根，方案50根。 即只需90根原材料，就可以制造出100套钢筋架子。 余料16米。 用单纯形法求得的最优下料方案为： 用Lingo求解 约束条件不变，利用LINGO软件计算， 最优解为：方案下40根，方案下30根，方案下20根。 进一步讨论： 用Lingo求解 1.将目标函数变为所用原材料“根数最少”，即 2.约束条件的改进及完善 在求解线性规划问题时，若约束条件为等式约束， 则容易产生无可行解。 因此在建模的时候，尽量避免使用等式约束。 对于此例，如果条件改为“要求制作29套”钢筋架子， 目标函数仍然用“余料最少”，则相应的模型为： 无可行解 用Lingo求解 进一步讨论： 2.约束条件的改进及完善 在求解线性规划问题时，若约束条件为等式约束， 则容易产生无可行解。 对于本问题，可行的做法是 将所有约束条件改为“”，则相应的模型为： 用Lingo求解 结果为： 方案下100根， 方案下50根， 余料为10米！ 目标函数应该为 或者 用Lingo求解 返回 首页 进一步讨论： 3. 引进整数限制 对于此例，如果条件改为“要求制作111套”钢筋架子， 目标函数用“所用原材料根数最少”，则相应的模型为 ： 结果为： 方案下33.3根， 方案下11.1根， 方案下55.5根. 改为 返回 首页 结果为： 方案下32根， 方案下12根， 方案下55根， 方案下1根. 案例2.农场发展规划问题 实例2.某农场有100公顷土地及15000元资金可用于发展生产。 农场劳动力情况为秋冬季3500人天，春夏季4000人天。 如劳动力用不了时可外出干活。其净收入为: 春夏季为2.1元/人.天，秋冬季为1.8元/人.天。 该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。 种作物不需专门投资，而每头奶牛投资400元，每只鸡投资3元。 养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工: 秋冬季100人天，春夏季50人天，年净收入400元/头。 养鸡时不占土地，需人工喂每只鸡秋冬季需0.6人天， 春夏季0.3人天，年净收入为2元/每只鸡。 农场现有鸡舍允许最多养3000只鸡，牛栏允许最多养32头奶牛。 三种作物每年需要 的人工及收入情况 如右表所示。 试决定该农场的经营 方案，使年净收入为最大。 大豆玉米麦子 秋冬季需人天数 春夏季需人天数 年净收入（元/公顷） 20 50 175 35 75 300 10 40 120 大豆玉米麦子养牛养鸡秋冬打工春夏打工 限制 秋冬2035101000.613500 春夏507540500.314000 土地1111.5100 限制323000 投入400315000 净收入17530012040021.82.1 x1x7x6x5x4x3x2 土地限制： 资金限制： 劳动力限制： 牛栏限制:鸡舍限制: 用Lingo求解 大豆玉米麦子养牛养鸡 秋冬打工春夏打工劳动 力 土 地 资金 秋冬2035101000.613500 春夏507540500.314000 土地1111.5 限制32300010015000 投入4003 收入17530012040021.82.1 x1x7x6x5x4x3x2 Global optimal solution found at iteration: 4 Objective value: 20260.87 Variable Value Reduced Cost X1 0.000000 16.30435 X2 39.13043 0.000000 X3 0.000000 17.39130 X4 21.30435 0.000000 X5 0.000000 0.4000000 X6 0.000000 0.8086957 X7 0.000000 0.6826087 用Lingo求解 牛的数量 应该为整数 Objective value: 20241.80 Variable Value Reduced Cost X1 0.000000 25.00000 X2 39.31333 0.000000 X3 0.000000 40.00000 X4 21.00000 -200.0000 X5 5.000000 -0.8000000 X6 21.00000 -1.800000 X7 0.000000 1.900000 Objective value: 20230.70 Variable Value Reduced Cost X1 0.000000 -175.0000 X2 39.00000 -300.0000 X3 0.000000 -120.0000 X4 21.00000 -400.0000 X5 58.00000 -2.000000 X6 0.000000 -1.800000 X7 7.000000 -2.100000 用Lingo求解 建议种植玉米 为整数公顷 返回 首页 有一艘货轮，分前、中、后 三个舱位，它们的最大允许载 重量和容积如右表所示： 前舱中舱后舱 最大允许载重（吨） 容积（立方米） 2000 4000 3000 5400 1500 1500 现有三种货物待运，有关数据列于下表： 货物数量（件）每件体积（立方米件）每件重量（吨件）运价（元件） A B C 600 1000 800 10 5 7 8 6 5 1000 700 600 为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱 最大允许载重量的比例关系。具体要求： 前、后舱分别与中舱之间载重量比例上偏差不超过15%， 前、后舱不超过10%。 问该货轮应装载A、B、C各多少件，运费收入为最大？ 案例3.最优的货轮装载方案 前、后舱分别与中舱之间载重 量比例上偏差不超过15%；前 、后舱不超过10%。 舱位载重限制: 舱位体积限制: 商品数量限制: 平衡条件: 目标函数: 前舱中舱后舱 载重量 容积 2000 4000 3000 5400 1500 1500 货物数量体积件重量件运价件 A B C 600 1000 800 10 5 7 8 6 5 1000 700 600 前中后 Ax11x12x13 Bx21x22x23 Cx31x32x33 解 用i1，2，3分别代表商品A、B、C，用j1，2，3分别代表 前、中、后舱，设xij为装于j 舱位的第i 种货物的数量（件）， 则问题的线性规划模型为： Lingo求解 前中后 A25027575 B00150 C01600 货物数量体积件重量件运价件 A B C 600 1000 800 10 5 7 8 6 5 1000 700 600 前中后 Ax11x12x13 Bx21x22x23 Cx31x32x33 前舱中舱后舱 载重量 容积 2000 4000 3000 5400 1500 1500 Global optimal solution found at iteration: 10 Objective value: 801000.0 进一步讨论: 1.目标为总运费最小。 xj = 0，即不装运货物。 2.限制B至少装350件，C至少装300件，目标函数求最大。 前中后 A2503675 B0202150 C03000 Global optimal solution found at iteration: 336158 Objective value: 787400.0 01600C 15000B 75275250A 后中前 Global optimal solution found at iteration: 10 Objective value: 801000.0 Lingo求解 Lingo求解 进一步讨论: 1.目标为总运费最小。 xj = 0 2.限制B至少装350件，C至少装300件，目标函数求最大。 前中后 A2503675 B0202150 C03000 Global optimal solution found at iteration: 336158 Objective value: 787400.0 01600C 15000B 75275250A 后中前 Global optimal solution found at iteration: 10 Objective value: 801000.0 3.限制B至少装350件，C至少装300件，目标函数求最小。 Global optimal solution found at iteration: 10 Objective value: 425000.0 前中后 A000 B1831670 C1117182 Lingo求解 返回 首页 案例4.合理的仓库租借合同 工厂在今后四个月内需租用仓 库堆存物资。已知各个月所需 的仓库面积如右表所示。 月份1234 所需仓库面积 （平方百米） 15102012 仓库租借费用，当租借 合同期限越长时， 享受的折扣优待越大， 具体数字如右表所示。 合同租借期限1个月2个月3个月4个月 合同期内每平方百米 的租借费用（元） 280045006000 7300 租借仓库的合同每月初都可办理， 每份合同具体规定租用面积和期限。因此， 该厂可根据需要在任何一个月初办理租借合同， 且每次办理时可签一份， 也可同时签若干份租用面积和租借期限不同的合同， 目标是使所付的租借费用最小。试确定租用方案。 月份1234 所需面积15102012 合同租借期限1个月2个月3个月4个月 租借费用2800450060007300 第1个月的租用面积约束: 第2个月的租用面积约束: 第3个月的租用面积约束: 第4个月的租用面积约束: 目标函数: 租用期限 签合同月份 1234 1x11x12x13x14 2x21x22x23 3x31x32 4x41 xij 为第i个月签订租用期 限为j个月的合同的面积。 Lingo求解 Global optimal solution found at iteration: 4 Objective value: 118400.0 租用期限 签合同月份 1234 1x11x12x13x14 2x21x22x23 3x31x32 4x41 月份1234 所需面积15102012 合同租借期限1个月2个月3个月4个月 租借费用2800450060007300 租用期限 签合同月份 1234 1510 2 382 4 详细结果如下。 租用期限 签合同月份 1234 1x11x12x13x14 2x21x22x23 3x31x32 4x41 月份1234 所需面积15102012 租用期限 签合同月份 1234 1510 2 382 4 对结果做如下说明： （1）总租借费用为118400； （2）租借合同为：1月份签一份租借1个月5平方百米的合同； 1月份签一份租借4个月10平方百米的合同； 3月份签一份租借1个月8平方百米的合同； 3月份签一份租借2个月2平方百米的合同。 返回 首页 案例5.招工方案的制定 某公司有三项工作需分别招收技工和力工来完成。 第一项工作可由一个技工单独完成， 或由一个技工和两个力工组成的小组来完成。 第二项工作可由一个技工或一个力工单独完成。 第三项工作可由五个力工组成的小组完成， 或一个技工领着三个力工完成。 已知技工和力工每周工资分别为100元和80元， 每周每人实际的有效工作时间分别为42和36小时。 为完成这三项工作任务，该公司需要每周总有效工作小时数为： 第一项工作14000小时，第二项18000小时，第三项24000小时。 又能招收到的工人数为技工不超过700人，力工不超过1000人。 试确定招收技工和力工的人数，使总的工资支出为最少。 工作技工力工 需要 工时 11014000 12 21018000 01 30524000 13 小时人.周4236 人数限制7001000 工 资10080 x11 x21 x12 x22 x31 x32 问题的求解 决策变量假设如下： xij第i项工作的第j个方案 所派的组数 详见右表。 问题的数学模型为： 工作技工力工 需要 工时 11014000 12 21018000 01 30524000 13 小时人.周4236 人数限制7001000 工 资10080 x11 x21 x12 x22 x31 x32 Lingo求解 详细结果如下： 工作技工力工 实际 工时 11014004 12 21018000 01 30524000 13 小时人.周4236 招收人数478998 工资支出127640 工作技工力工 需要 工时 11014000 12 21018000 01 30524000 13 小时人.周4236 人数限制7001000 工 资10080 x11 x21 x12 x22 x31 x32 328 138 2 339 125 10 Global optimal solution found at iteration: 176 Objective value: 127640.0 返回 首页 案例6.配料问题 某染料厂用甲、乙、丙三种原料混合配制出 A、B、C三种不同的产品。 原料甲、乙、丙每天的最大供应量分别为100、100、60千克， 每千克单价分别为65、25、35元。 由于A、B、C三种产品的质量限制，要求 产品A中含原料甲不少于50%，含原料乙不超过25%； 产品B中含原料甲不少于25%，含原料乙不超过50%； 产品C的原料配比无限制，产品A、B含原料丙比例无限制。 产品A、B、C每千克的售价分别为50、35、25元。 问应如何安排生产，才能使所获利润达到最大。 表1-4 表1-5 甲乙丙售价（元/千克） A B C 50% 25% 25% 50% 50 35 25 单价（元/千克）652535 日供应量上限10010060 原料 产品 甲乙丙 A B C x11 x21 x31 x12 x22 x32 x13 x23 x33 其中xij 表示第i 种产品中含第 j 种原料的数量。 则此问题的数学模型为 原料配比约束 日供应量约束 原料 产品 甲乙丙 A B C x11 x21 x31 x12 x22 x32 x13 x23 x33 甲乙丙售价（元/千克） A B C 50% 25% 25% 50% 50 35 25 单价（元/千克）652535 日供应量上限10010060 Lingo求解 甲乙丙售价（元/千克） A B C 50% 25% 25% 50% 50 35 25 单价（元/千克）652535 日供应量上限10010060 Global optimal solution found at iteration: 10 Objective value: 500.0000 原料 产品 甲乙丙 A B C 100 0 0 50 0 0 50 0 0 根源： 定价偏低 原料过剩 利润太少 Lingo求解 甲乙丙售价（元/千克） A B C 50% 25% 25% 50% 50 35 25 单价（元/千克）652535 日供应量上限10010060 Global optimal solution found at iteration: 10 Objective value: 500.0000 甲乙丙售价（元/千克） A B C 50% 25% 25% 50% 60 45 35 单价（元/千克）652535 日供应量上限10010060 Global optimal solution found at iteration: 8 Objective value: 3000.000 原料 产品 甲乙丙 A B C 100 0 0 40 0 60 60 0 0 原料 产品 甲乙丙 A B C 100 0 0 50 0 0 50 0 0 适当提高定价 甲乙丙 售价 （元/千克） A B C 50% 25% 25% 50% 50 35 25 单价（元/千克）652535500 日供应量上限10010060 甲乙丙 售价 （元/千克） A B C 50% 25% 25% 50% 60 45 35 单价（元/千克）6525353000 日供应量上限10010060 原料 产品 甲乙丙 A B C 100 0 0 40 0 60 60 0 0 原料 产品 甲乙丙 A B C 100 0 0 50 0 0 50 0 0 规定:产品B至少生产50千克。 Lingo求解 不生产 B产品！ 甲乙丙 售价（元/ 千克） A B C 50% 25% 25% 50% 50 35 25 单价（元 /千克） 652535500 日供应 量上限 10010060 甲乙丙 售价（元/ 千克） A B C 50% 25% 25% 50% 60 45 35 单价（元/ 千克） 6525353000 日供应 量上限 10010060 原料 产品 甲乙丙 A B C 100 0 0 40 0 60 60 0 0 原料 产品 甲乙丙 A B C 100 0 0 50 0 0 50 0 0 原料 产品 甲乙丙 A B C 87 13 0 40 26 34 47 13 0 甲乙丙售价（元/千克） A B 50 C 50% 25% 25% 50% 60 45 35 单价（元/ 千克） 6525352870 日供应 量上限 10010060 返回 首页 案例7. 人员分配问题 某中型商场每周对售货员的需求如右下表。 售货员每周工资为300元。 为了保证售货员的休息，规定 每人每周工作5天，休息2天， 并且休息的2天是连续的。 问应该如何安排售货员的作息时间， 使得既满足工作需要， 又使支出最少？ 时 间所需售货员人数 星期日12人 星期一18人 星期二15人 星期三12人 星期四16人 星期五19人 星期六14人 时 间 所需售货 员人数 星期日12人 星期一18人 星期二15人 星期三12人 星期四16人 星期五19人 星期六14人 休息 人数 周日周一周二周三周四周五周六 周日x7x7 周一x1x1 周二x2x2 周三x3x3 周四x4x4 周五x5x5 周六x6x6 设决策变量 xi 表示：星期 i 开始休息的员工人数，详见下表。 则此问题的数学模型为： 时 间 所需售货 员人数 星期日12人 星期一18人 星期二15人 星期三12人 星期四16人 星期五19人 星期六14人 休息 人数 周日周一周二周三周四周五周六 周日x7x7 周一x1x1 周二x2x2 周三x3x3 周四x4x4 周五x5x5 周六x6x6 用Lingo求解 Global optimal solution found at iteration: 13 Objective value: 22.00000 Variable Value Reduced Cost X1 1.000000 1.000000 X2 5.000000 1.000000 X3 3.000000 1.000000 X4 2.000000 1.000000 X5 1.000000 1.000000 X6 7.000000 1.000000 X7 3.000000 1.000000 详细结果见下表。 时 间 所需售货 员人数 星期日12人 星期一18人 星期二15人 星期三12人 星期四16人 星期五19人 星期六14人 总人数22人 休息 人数 周日周一周二周三周四周五周六 周日33 周一11 周二55 周三33 周四22 周五11 周六77 工作 人数 12181614161914 返回 首页 案例8.最佳项目投资方案 某部门在今后五年内考虑给下列项目投资，已知： 项目1 从第一年到第四年的每年年初投资， 并于次年末回收本利115%； 项目2 第三年年初投资，到第五年末能回收本利125%， 但规定最大投资额不超过40万元； 项目3 第二年年初投资，到第五年末能回收本利140%， 但规定最大投资额不超过30万元； 项目4 五年内每年年初均可投资，并于本年末回收本利106%。 该部门现有资金100万元， 问如何确定投资方案， 使得到第五年末拥有资金的本利额最大？ 年份 项目 一二三四五 投资 上限 初末初末初末初末初末 1投x11x12x13x14 收 1.15x111.15x121.15x131.15x14 2投x2340 收 1.25x23 3投x3230 收 1.40x32 4投x41x42x43x44x45 收 1.06x411.06x421.06x431.06x441.06x45 资金 上限 100 设决策变量xij表示：项目i在第j年初的投资额，详见下表。 年份 项目 一二三四五投资 上限 初末初末初末初末初末 1投x11x12x13x14 收1.15x111.15x121.15x131.15x14 2 投x2340 收1.25x23 3 投x3230 收1.40x32 4投x41x42x43x44x45 收1.06x411.06x421.06x431.06x441.06x45 资金上限100 Lingo求解 此问题的 数学模型为： 且为整数 Objective value: 143.7500 Variable Value X14 0.00000 X23 40.00000 X32 30.00000 X45 48.82075 X11 71.69811 X41 28.30189 X12 0.000000 X42 0.000000 X13 42.45283 X43 0.000000 X44 0.000000 年份 项目 一二三四五 投资 上限 1 71.69 811 42.45 283 24040 33030 4 28.30 189 48.82 075 资金 上限 100 143.7 5 详细结果见下表。 返回 首页 案例9.客观评价学生 的学习情况 某专业30名学生连续两个 学期的专业综合成绩如右 表所示，请对这30人给出 客观、合理并具有激励、 鞭策作用的“综合排名”。 学生学期1学期2学生学期1学期2 19493167561 29295177581 39087187472 48978197373 58785207184 68790217055 78669226982 88583236870 98465246674 108386256547 118279266380 128076276253 137964285677 147772295257 157679304968 学 生 学期1 （ai） 学