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

1、五、线性规划问题案例建模及讨论,案例1.工业原料的合理利用,案例2.农场发展规划问题,案例3.最优的货轮装载方案,案例4.合理的仓库租借合同,案例5.招工方案的制定,案例6.配料问题,案例7.人员分配问题,案例8.最佳项目投资方案,案例9.客观评价学生的学习情况,案例1.工业原料的合理利用 要制作100套钢筋架子，每套有长2.9米、2.1米和1.5米的钢筋 各一根。已知原材料长7.4米，应如何切割使用原材料最省。,解 下面几种方案都是能节省材料的好方案（见下表）。,设方案用 x1 根，方案用 x2 根，方案用 x3 根， 方案用 x4 根，方案用 x5 根。,则线性规划模型为：,添加人工变量后

2、，模型变为：,方案30根，方案10根，方案50根。 即只需90根原材料，就可以制造出100套钢筋架子。 余料16米。,用单纯形法求得的最优下料方案为：,用Lingo求解,约束条件不变，利用LINGO软件计算， 最优解为：方案下40根，方案下30根，方案下20根。,进一步讨论：,用Lingo求解,1.将目标函数变为所用原材料“根数最少”，即,2.约束条件的改进及完善 在求解线性规划问题时，若约束条件为等式约束， 则容易产生无可行解。 因此在建模的时候，尽量避免使用等式约束。 对于此例，如果条件改为“要求制作29套”钢筋架子， 目标函数仍然用“余料最少”，则相应的模型为：,无可行解,用Lingo求

3、解,进一步讨论：,2.约束条件的改进及完善 在求解线性规划问题时，若约束条件为等式约束， 则容易产生无可行解。 对于本问题，可行的做法是 将所有约束条件改为“”，则相应的模型为：,用Lingo求解,结果为： 方案下100根， 方案下50根， 余料为10米！,目标函数应该为,或者,用Lingo求解,返回 首页,进一步讨论：,3. 引进整数限制 对于此例，如果条件改为“要求制作111套”钢筋架子， 目标函数用“所用原材料根数最少”，则相应的模型为：,结果为： 方案下33.3根， 方案下11.1根， 方案下55.5根.,改为,返回 首页,结果为： 方案下32根， 方案下12根， 方案下55根， 方案

4、下1根.,案例2.农场发展规划问题,实例2.某农场有100公顷土地及15000元资金可用于发展生产。 农场劳动力情况为秋冬季3500人天，春夏季4000人天。 如劳动力用不了时可外出干活。其净收入为: 春夏季为2.1元/人.天，秋冬季为1.8元/人.天。 该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。 种作物不需专门投资，而每头奶牛投资400元，每只鸡投资3元。 养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工: 秋冬季100人天，春夏季50人天，年净收入400元/头。 养鸡时不占土地，需人工喂每只鸡秋冬季需0.6人天， 春夏季0.3人天，年净收入为2元/每只鸡。 农场现有鸡舍允许最

5、多养3000只鸡，牛栏允许最多养32头奶牛。 三种作物每年需要 的人工及收入情况 如右表所示。 试决定该农场的经营 方案，使年净收入为最大。,土地限制：,资金限制：,劳动力限制：,牛栏限制:,鸡舍限制:,用Lingo求解,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.

6、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 valu

7、e: 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求解,建议种植玉米 为整数公顷,返回 首页,有一艘货轮，分前、中、后 三个舱位，它们的最大允许载 重量和容积如右表所示：,现有三种货物待运，有关数据列于下表：,为了航运安全，要求前、中、后舱在实际载重

8、量上大体保持各舱 最大允许载重量的比例关系。具体要求： 前、后舱分别与中舱之间载重量比例上偏差不超过15%， 前、后舱不超过10%。 问该货轮应装载A、B、C各多少件，运费收入为最大？,案例3.最优的货轮装载方案,前、后舱分别与中舱之间载重量比例上偏差不超过15%；前、后舱不超过10%。,舱位载重限制:,舱位体积限制:,商品数量限制:,平衡条件:,目标函数:,解 用i1，2，3分别代表商品A、B、C，用j1，2，3分别代表 前、中、后舱，设xij为装于j 舱位的第i 种货物的数量（件）， 则问题的线性规划模型为：,Lingo求解,Global optimal solution found at

9、 iteration: 10 Objective value: 801000.0,进一步讨论: 1.目标为总运费最小。,xj = 0，即不装运货物。,2.限制B至少装350件，C至少装300件，目标函数求最大。,Global optimal solution found at iteration: 336158 Objective value: 787400.0,Lingo求解,Lingo求解,进一步讨论: 1.目标为总运费最小。,xj = 0,2.限制B至少装350件，C至少装300件，目标函数求最大。,Global optimal solution found at iteration:

10、336158 Objective value: 787400.0,3.限制B至少装350件，C至少装300件，目标函数求最小。,Global optimal solution found at iteration: 10 Objective value: 425000.0,Lingo求解,返回 首页,案例4.合理的仓库租借合同 工厂在今后四个月内需租用仓 库堆存物资。已知各个月所需 的仓库面积如右表所示。,仓库租借费用，当租借 合同期限越长时， 享受的折扣优待越大， 具体数字如右表所示。,租借仓库的合同每月初都可办理， 每份合同具体规定租用面积和期限。因此， 该厂可根据需要在任何一个月初办理租

11、借合同， 且每次办理时可签一份， 也可同时签若干份租用面积和租借期限不同的合同， 目标是使所付的租借费用最小。试确定租用方案。,第1个月的租用面积约束:,第2个月的租用面积约束:,第3个月的租用面积约束:,第4个月的租用面积约束:,目标函数:,xij 为第i个月签订租用期 限为j个月的合同的面积。,Lingo求解,Global optimal solution found at iteration: 4 Objective value: 118400.0,详细结果如下。,对结果做如下说明： （1）总租借费用为118400； （2）租借合同为：1月份签一份租借1个月5平方百米的合同； 1月份签一

12、份租借4个月10平方百米的合同； 3月份签一份租借1个月8平方百米的合同； 3月份签一份租借2个月2平方百米的合同。,返回 首页,案例5.招工方案的制定 某公司有三项工作需分别招收技工和力工来完成。 第一项工作可由一个技工单独完成， 或由一个技工和两个力工组成的小组来完成。 第二项工作可由一个技工或一个力工单独完成。 第三项工作可由五个力工组成的小组完成， 或一个技工领着三个力工完成。 已知技工和力工每周工资分别为100元和80元， 每周每人实际的有效工作时间分别为42和36小时。 为完成这三项工作任务，该公司需要每周总有效工作小时数为： 第一项工作14000小时，第二项18000小时，第三项

13、24000小时。 又能招收到的工人数为技工不超过700人，力工不超过1000人。 试确定招收技工和力工的人数，使总的工资支出为最少。,问题的求解 决策变量假设如下： xij第i项工作的第j个方案 所派的组数 详见右表。 问题的数学模型为：,Lingo求解,详细结果如下：,328,138,2,339,125,10,Global optimal solution found at iteration: 176 Objective value: 127640.0,返回 首页,案例6.配料问题 某染料厂用甲、乙、丙三种原料混合配制出 A、B、C三种不同的产品。 原料甲、乙、丙每天的最大供应量分别为10

14、0、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,其中xij 表示第i 种产品中含第 j 种原料的数量。 则此问题的数学模型为,Lingo求解,Global optimal solution found at iteration: 10 Objective valu

15、e: 500.0000,根源： 定价偏低,原料过剩,利润太少,Lingo求解,Global optimal solution found at iteration: 10 Objective value: 500.0000,Global optimal solution found at iteration: 8 Objective value: 3000.000,适当提高定价,规定:产品B至少生产50千克。,Lingo求解,返回 首页,案例7. 人员分配问题 某中型商场每周对售货员的需求如右下表。 售货员每周工资为300元。 为了保证售货员的休息，规定 每人每周工作5天，休息2天， 并且休息

16、的2天是连续的。 问应该如何安排售货员的作息时间， 使得既满足工作需要， 又使支出最少？,设决策变量 xi 表示：星期 i 开始休息的员工人数，详见下表。,则此问题的数学模型为：,用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.00

17、0000 X6 7.000000 1.000000 X7 3.000000 1.000000,详细结果见下表。,返回 首页,案例8.最佳项目投资方案 某部门在今后五年内考虑给下列项目投资，已知： 项目1 从第一年到第四年的每年年初投资， 并于次年末回收本利115%； 项目2 第三年年初投资，到第五年末能回收本利125%， 但规定最大投资额不超过40万元； 项目3 第二年年初投资，到第五年末能回收本利140%， 但规定最大投资额不超过30万元； 项目4 五年内每年年初均可投资，并于本年末回收本利106%。 该部门现有资金100万元， 问如何确定投资方案， 使得到第五年末拥有资金的本利额最大？,设决策变量xij表示：项目i在第j年初的投资额，详见下表。,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.0