运筹学04_运输问题.ppt

* 先作如下分析：（1）总产量为180，B1，…，B4的最低需求量 20+50+35+45=150，这时属产大于销； （2）B1，…，B4的最高需求是60+70+35+45=210，这时属销大于产 （3）虚设一个产地A5，产量是210－180=30，A5的产量只能供应B1或B2。 （4）将B1与B2各分成两部分 的需求量是20， 的需求量是40， 的需求量分别是50与20，因此 必须由A1，…，A4供应， 可由 A1、…、A5供应。 （5）上述A5不能供应某需求地的运价用大M表示，A5到 、 的运价为零。得到下表的产销平衡表。 B3 B4 ai A1 5 5 9 9 2 3 60 A2 M M 4 4 7 8 40 A3 3 3 6 6 4 2 30 A4 4 4 8 8 10 11 50 A5 M 0 M 0 M M 30 bj 20 40 50 20 35 45 210 得到这样的平衡表后，计算得到最优方案表5-29。 表5-28 * ? B3 B4 ai A1 ? ? ? ? 35 25 60 A2 ? ? 40 ? ? ? 40 A3 0 ? 10 ? ? 20 30 A4 20 30 ? ? ? ? 50 A5 ? 10 ? 20 ? ? 30 bj 20 40 50 20 35 45 210? 表中：x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。 * 运输模型的应用 * DF公司在接下来的三个月内每月都要按照销售合同生产出两种产品。表中给出了在正常时间（Regular Time，缩写为RT）和加班时间（Over Time，缩写为OT）内能够生产这两种产品的总数。 月 最大生产总量 产品1/产品2 销售 产品1/产品2 单位生产成本(1000元/件) 单位储存成本（1000元/件） RT OT RT OT 1 2 3 10 8 10 3 2 3 5/3 3/5 4/4 15/16 17/15 19/17 18/20 20/18 22/22 1/2 2/1 （1）对这个问题进行分析，描述成一个运输问题的产销平衡表，使之可用运输单纯形法求解． （2）建立总成本最小的数学模型并求出最优解 * 【解】表中括号内的数据为产品序号 i ↓ j→ 1 2 3 4 5 6 生产能力 ai 1月(1) 1月(2) 2(1) 2(2) 3(1) 3(2) 1 1月RT x11 x12 x13 x14 x15 x16 10 2 1月OT x21 x22 x23 x24 x25 x26 3 3 2月RT x33 x34 x35 x36 8 4 2月OT x43 x44 x45 x46 2 5 3月RT x55 x56 10 6 3月OT x65 x66 3 需要量bj 5 3 3 5 4 4 * 1月(1) 1月(2) 2(1) 2(2) 3(1) 3(2) 剩余能力 生产能力 1月RT 15 16 16 18 18 19 0 10 1月OT 18 20 19 22 21 23 0 3 2月RT M M 17 15 19 16 0 8 2月OT M M 20 18 22 19 0 2 3月RT M M M M 19 17 0 10 3月OT M M M M 22 22 0 3 需要量 5 3 3 5 4 4 12 36 例如x35表示第2月正常时间内生产的产品1用于第3月交货的数量，第1种单位产品的成本是17（千元），在第3月交货单位产品的储存成本是2（千元），因此单位产品总成本c35等于19（千元）， * 数学模型为： 1月(1) 1月(2) 2月(1) 2月(2) 3月(1) 3月(2) 剩余能力 生产能力 1月RT 5 3 2 10 1月OT 3 3 2月RT 1 5 2 8 2月OT 2 2 3月RT 4 2 4 10 3月OT 3 3 需要量 5 3 3 5 4 4 12 36 * 最优生产计划是：第1个月正常时间内生产第1种产品7件，当月交货5件，第2个月交货2件；生产第2种产品3件，当月交货，总产量10件，不加班． 第2个月正常时间内生产第1种产品1件，当月交货1件；生产第2种产品7件，当月交货5件，第3个月交货2件，总产量8件，不加班． 第3个月正常时间内生产第1种产品4件，当月交货；生产第2种产品2件，当月交货，总产量