Transportation Problem 第四章 运输问题 Transportation Problem
Contents §4.1 运输问题的数学模型 §4.2 求解运输问题的表上作业法 §4.3 表上作业法的特殊情况 §4.4 运输问题的应用
§4.4 运输问题的应用 例6 某工厂专造飞机发动机，根据合同，1—4月份交货量以及工厂的最大生产能力如表4-1，由于技术上的原因，生产发动机的成本波动，其变化情况见表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 运输问题的应用 解： 由于有存贮费, 因此1月份生产每台的成本1.08万元, §4.4 运输问题的应用 解： 由于有存贮费, 因此1月份生产每台的成本1.08万元, 如果2月份才卖出,那么成本为1.08+0.015=1.095万元; 若留到3、4月份才卖出，相应的成本分别为1.11万元和1.125万元。其余的成本计算与此类似。 但是, 2月生产的不能在1月份供应, 3月份生产的不能在1、2月份供应, 4月份生产的不能在1、2、3月份供应, 为了阻止这种行为发生，我们将对应的成本定为一个充分大的正数M。 由于生产能力的产量大于需求量，构造一个虚的需要地，其需要量为25+35+30+10-10-15-25-20=30。则可列表如表4-2.
§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万元。
§4.4 运输问题的应用 用LINDO程序为： min 1.08x11+1.095x12+1.11x13+1.125x14+1000x21+1.11x22 +1.125x23+1.14x24+1000x31+1000x32+1.1x33+1.115x34 +1000x41+1000x42+1000x43+1.13x44 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
§4.4 运输问题的应用 LP OPTIMUM FOUND AT STEP 8 OBJECTIVE FUNCTION VALUE 1) 77.30000 VARIABLE VALUE REDUCED COST x11 10.000000 0.000000 x12 10.000000 0.000000 x13 5.000000 0.000000 x14 0.000000 0.000000 x21 0.000000 998.905029 x22 5.000000 0.000000 x23 0.000000 0.000000 x24 0.000000 0.000000 x31 0.000000 998.929993 x32 0.000000 998.914978 x33 20.000000 0.000000 x34 10.000000 0.000000 x41 0.000000 998.914978 x42 0.000000 998.900024 x43 0.000000 998.885010 x44 10.000000 0.000000 运行结果为：
表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 最高需求 不限
§4.4 运输问题的应用 解: 这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求不限，第Ⅳ个地区最多能分到60万吨，这样最高需求为210万吨，大于产量。为了平衡，在产销平衡表中，增加一个虚构的化肥厂D，其产量为50万吨。由于各地区的需求包括两部分，最低需求是要保证的，就不能由D供应，令相应的运价为M（充分大的正数），而另一部分满足或不满足都可以，因此可由假设的化肥厂供应，令相应的运价等于0。对凡是包含两部分的均可以作为两个地区对待，这样该问题的平衡表及运价表为表4-4：
表4-4 三个化肥厂供应四个地区的化肥的最优平衡表 §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 用软件求解，就不必这么复杂，只需要用不等式来表示即可。
§4.4 运输问题的应用 min 16x11+13x12+22x13+17x14+14x21+13x22+19x23 §4.4 运输问题的应用 min 16x11+13x12+22x13+17x14+14x21+13x22+19x23 +15x24+19x31+20x32+23x33+1000x34 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
§4.4 运输问题的应用 LP OPTIMUM FOUND AT STEP 10 OBJECTIVE FUNCTION VALUE §4.4 运输问题的应用 LP OPTIMUM FOUND AT STEP 10 OBJECTIVE FUNCTION VALUE 1) 2460.000 VARIABLE VALUE REDUCED COST x11 0.000000 4.000000 x12 50.000000 0.000000 x13 0.000000 7.000000 x14 0.000000 2.000000 x21 0.000000 2.000000 x22 20.000000 0.000000 x23 0.000000 4.000000 x24 40.000000 0.000000 x31 50.000000 0.000000 x32 0.000000 0.000000 x33 0.000000 1.000000 x34 0.000000 978.000000
§4.4 运输问题的应用 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -15.000000 §4.4 运输问题的应用 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -15.000000 3) 0.000000 -15.000000 4) 0.000000 -22.000000 5) 20.000000 0.000000 6) 0.000000 3.000000 7) 0.000000 2.000000 8) 30.000000 0.000000 9) 30.000000 0.000000 NO. ITERATIONS= 10
§4.4 运输问题的应用 于是可得到总运费最省的化肥调拨方案如4-5所示: 当然，如果用LINGO直接编程求解也是很方便的。 §4.4 运输问题的应用 于是可得到总运费最省的化肥调拨方案如4-5所示: 表4-5 三个化肥厂供应四个地区的化肥的计划表 Ⅰ Ⅱ Ⅲ Ⅳ 产量 A 50 16 13 22 17 B 20 40 60 14 19 15 C 23 — 最低需求 30 70 10 最高需求 不限 当然，如果用LINGO直接编程求解也是很方便的。
Thank You!