Transportation Problem

Presentation on theme: "Transportation Problem"— Presentation transcript:

1 Transportation Problem
第四章 运输问题 Transportation  Problem

2 Contents §4.1 运输问题的数学模型 §4.2 求解运输问题的表上作业法 §4.3 表上作业法的特殊情况 §4.4 运输问题的应用

3 §4.4 运输问题的应用 例6 某工厂专造飞机发动机，根据合同，1—4月份交货量以及工厂的最大生产能力如表4-1，由于技术上的原因，生产发动机的成本波动，其变化情况见表4-1。 表 飞机发动机交货量与生产能力 月份 1月 2月 3月 4月 交货台数 10 15 25 20 工厂的最大生产能力 35 30 每台发动机成本（万元） 1.08 1.11 1.10 1.13 由于生产成本的变化，可能在某个月成本低时多生产些留到以后用，但每台发动机存贮一个月要0.015(万元)(包括成本的利息等)。现要制定一个进度表，每月安排生产多少台可使总成本最小？

4 §4.4 运输问题的应用 解： 由于有存贮费, 因此1月份生产每台的成本1.08万元,
§4.4 运输问题的应用 解： 由于有存贮费, 因此1月份生产每台的成本1.08万元, 如果2月份才卖出,那么成本为 =1.095万元; 若留到3、4月份才卖出，相应的成本分别为1.11万元和1.125万元。其余的成本计算与此类似。 但是, 2月生产的不能在1月份供应, 3月份生产的不能在1、2月份供应, 4月份生产的不能在1、2、3月份供应, 为了阻止这种行为发生，我们将对应的成本定为一个充分大的正数M。 由于生产能力的产量大于需求量，构造一个虚的需要地，其需要量为 =30。则可列表如表4-2.

5 §4.4 运输问题的应用 表4-2 飞机发动机交货量与生产能力的平衡表 取M=1000用计算机软件可求得最优解如表1-89，
§4.4 运输问题的应用 表4-2 飞机发动机交货量与生产能力的平衡表 1月 2月 3月 4月 未生产 产量 10 15 25 1.08 1.095 1.11 1.125 5 30 35 M 1.140 1.10 1.115 1.130 需要量 20 100 取M=1000用计算机软件可求得最优解如表1-89， Z=77.3万元。

6 §4.4 运输问题的应用 用LINDO程序为： min 1.08x x x x x x22 +1.125x x x x32+1.1x x34 +1000x x x x44 st x11+x12+x13+x14<25 x21+x22+x23+x24<35 x31+x32+x33+x34<30 x41+x42+x43+x44<10 x11+x21+x31+x41=10 x12+x22+x32+x42=15 x13+x23+x33+x43=25 x14+x24+x34+x44=20 end

7 §4.4 运输问题的应用 LP OPTIMUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST x x x x x x x x x x x x x x x x 运行结果为：

8 表4-3 三个化肥厂供应四个地区的化肥的平衡表与运价表
§4.4 运输问题的应用 例7 设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同，各化肥厂年产量、各地区年需要量以及从各化肥厂到各地区的单位化肥运价如表4-3。试求出总的运费最省的化肥调拨方案。 表4-3 三个化肥厂供应四个地区的化肥的平衡表与运价表 Ⅰ Ⅱ Ⅲ Ⅳ 产量 A 50 16 13 22 17 B 60 14 19 15 C 20 23 — 最低需求 30 70 10 最高需求 不限

9 §4.4 运输问题的应用 解: 这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求不限，第Ⅳ个地区最多能分到60万吨，这样最高需求为210万吨，大于产量。为了平衡，在产销平衡表中，增加一个虚构的化肥厂D，其产量为50万吨。由于各地区的需求包括两部分，最低需求是要保证的，就不能由D供应，令相应的运价为M（充分大的正数），而另一部分满足或不满足都可以，因此可由假设的化肥厂供应，令相应的运价等于0。对凡是包含两部分的均可以作为两个地区对待，这样该问题的平衡表及运价表为表4-4：

10 表4-4 三个化肥厂供应四个地区的化肥的最优平衡表
§4.4 运输问题的应用 表 三个化肥厂供应四个地区的化肥的最优平衡表 Ⅰ I′ Ⅱ Ⅲ Ⅳ Ⅳ′ 产量 A 50 16 13 22 17 B 20 10 30 60 14 19 15 C 23 M D 销量 70 210 用软件求解，就不必这么复杂，只需要用不等式来表示即可。

11 §4.4 运输问题的应用 min 16x11+13x12+22x13+17x14+14x21+13x22+19x23
§4.4 运输问题的应用 min 16x11+13x12+22x13+17x14+14x21+13x22+19x23 +15x24+19x31+20x32+23x x34 st x11+x12+x13+x14=50 x21+x22+x23+x24=60 x31+x32+x33+x34=50 x11+x21+x31>=30 x11+x21+x31<=50 x12+x22+x32=70 x13+x23+x33<=30 x14+x24+x34>=10 end

12 §4.4 运输问题的应用 LP OPTIMUM FOUND AT STEP 10 OBJECTIVE FUNCTION VALUE
§4.4 运输问题的应用 LP OPTIMUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST x x x x x x x x x x x x

13 §4.4 运输问题的应用 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -15.000000
§4.4 运输问题的应用 ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) 5) 6) 7) 8) 9) NO. ITERATIONS=

14 §4.4 运输问题的应用 于是可得到总运费最省的化肥调拨方案如4-5所示: 当然，如果用LINGO直接编程求解也是很方便的。
§4.4 运输问题的应用 于是可得到总运费最省的化肥调拨方案如4-5所示: 表 三个化肥厂供应四个地区的化肥的计划表 Ⅰ Ⅱ Ⅲ Ⅳ 产量 A 50 16 13 22 17 B 20 40 60 14 19 15 C 23 — 最低需求 30 70 10 最高需求 不限 当然，如果用LINGO直接编程求解也是很方便的。

15 Thank You!