第3章运输问题祥解.ppt

最优方案表为 B1 B2 B3 B4 库 产量 A1 A2 A3 4 5 3 2 2 4 4 7 8 9 销量 4 5 5 6 4 最小运费为: 例1 设有产量分别为30，50，60的三个原料产地Ａ1，Ａ2，Ａ3。 要将原料运往需求量分别为15，10，40，45的四个销售地Ｂ1，Ｂ2， Ｂ3，Ｂ4。单位运价表如表。试求总运费最省的调运方案。 A1 A2 A3 　 3 5 8 4　 　 7 4 8 6 　10 3 5 2 销地 产地 解：总产量　　　　　　　　 　总销量 为总产量大于总销量的不平衡的运输问题。因此增加一个虚拟的销地B5，需求量b5=140-110=30，且单位运价c15＝c25＝c35＝0。 由此可得产销平衡的运输表 30 B5 45 40 10 15 销量 60 A3 50 A2 30 A1 B4 B3 B2 B1 销售地 加工厂 产量 3 7 5 8 4 8 4 6 3 10 5 2 0 0 0 对上述产销平衡运输表，可用表示作业法求解。 30 45 40 10 15 销量 60 0 2 45 5 5 3 10 10 A3 50 0 6 8 20 4 7 A2 30 0 4 8 15 5 3 15 A1 产量 B5 B4 B3 B2 B1 销售地 加工厂 首先利用最小元素法确定初始基本可行解 -15 -45 -10 -15 -5 ① ③ ② ④ ⑤ 得初始基本可行解 总运费Z＝470 30 45 10 15 销量 60 0 2 5 3 10 A3 50 0 6 8 4 7 A2 30 0 4 8 5 3 A1 产量 B5 B4 B3 B2 B1 销售地 加工厂 首先利用最小元素法确定初始基本可行解 15 15 20 30 10 5 45 40 利用位势法求解非基变量检验数，以判断初始基本可行解 是否最优。 v5 v4 v3 v2 v1 u3 0 3 2 45 5 5 3 10 10 10 A3 u2 0 30 6 1 8 20 4 -2 7 4 A2 u1 0 0 4 -1 8 15 5 -1 3 15 A1 B5 B4 B3 B2 B1 销售地 加工厂 由表可知， 为最小的负检验数。因此可将 作为换入变量，从 出发，作出其他顶点均为基变量的闭回路。 ＝０ ＝3 ＝8 ＝０ ＝０ ＝-3 ＝5 ＝6 销售地 加工厂 B1 B2 B3 B4 B5 产量 A1 15 3 5 15 8 4 0 30 A2 7 -2 4 20 8 6 30 0 50 A3 10 10 3 5 5 45 2 0 60 销量 15 10 40 45 30 　　从 出发的闭回路中，偶顶点 ，调整量　 　　　　　　　　且取 　为换出变量。可得改进后的基本可行解 　　总运费Z＝450，比初始解　　优。 +10 +10 -10 -10 再利用位势法求解非基变量检验数，以判断改进后的基本可行解 　　是否最优。 v5 v4 v3 v2 v1 u3 0 3 2 45 5 15 3 2 10 10 A3 u2 0 30 6 1 8 10 4 10 7 4 A2 u1 0 0 4 -1 8 15 5 1 3 15 A1 B5 B4 B3 B2 B1 销售地 加工厂 由表可知， 为负检验数。因此可将 作为换入变量，从 出发，作出其他顶点均为基变量的闭回路。 ＝０ ＝3 ＝8 ＝０ ＝０ ＝-3 ＝5 ＝4 销售地 加工厂 B1 B2 B3 B4 B5 产量 A1 15 3 5 15 8 -1 4 0 30 A2 7 10 4 10 8 6 30 0 50 A3 10 3 15 5 45 2 0 60 销量 15 10 40 45 30 　　从 出发的闭回路中，偶顶点 ，调整量　 　　　　　　　　且取 　为换出变量。可得改进后的基本可行解