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.2 求解运输问题的表上作业法 表上作业法是一类比较特殊的单纯形法。它必须首先确定一个初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对初始方案加以改进，直到找出最优方案。

4 运输问题求解思路图 §4.2 求解运输问题的表上作业法 是 确定初始方案 判定是否 ( 初 始 最 优？ 结 束 基本可行解) 否 最优方案
§4.2 求解运输问题的表上作业法 运输问题求解思路图 判定是否 最 优？ 是 结 束 确定初始方案 ( 初 始 基本可行解) 改进调整 （换基迭代） 否 最优方案

5 例 甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表，求使总运输量最少的调运方案。

6 有关信息表 450 200 150 100 日销量 （需求量） 250 75 65 80 乙 70 90 甲 日产量 （供应量） C B A
运距 城市 煤矿

7 数学模型

8 分别使用最小元素法和西北角法求出初始方案。
& 最小元素法的基本思想是“就近供应” ； & 西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同 ；

9 用最小元素法确定初始调运方案 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65
调 销地 运 量 产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 150 450 100 100 100 150 100 100 100

10 得到初始调运方案为： x11=100，x13=100，x22=150，x23=100

11 用西北角法确定初始调运方案 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65
调 销地 运 量 产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 150 450 100 100 100 50 200 200 50

12 得到初始调运方案为： x11=100，x12=100，x22=50，x23=200

13 3、Vogel法 基本思路是：从全局考虑。其方法是从运价表上分别找出每行与每列最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量。 当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中的行或列，再重复上述步骤。直到找出最佳调运方案。

14 Table3 产销平衡表 2 5 1 3 6 3 Table4 单位运价表 销地 产地 B1 B2 B3 B4 产 量 A1 A2 A3 7
产 量 A1 A2 A3 7 4 9 销 量 2 5 1 3 6 3 Table4 单位运价表 销地 产地 B B B B4 两最小元素之差 ① ② ③ ④ ⑤ A1 A2 A3 1 2 两最小元素 之差 ①②③④ ⑤ 2

15 例 某种物资有3个产地、4个销地，各产地的产量、销地的销量以及各产销地之间的运价如表2-1，求最优的调运方案。
表 运输问题的平衡表与运价表 平衡表(单位：t) 运价表 B1 B2 B3 B4 发量 A1 4 6 5 3 A2 7 A3 8 收量 2 13

16 §4.2 求解运输问题的表上作业法 表 运输问题的初始调运方案 表中, 有数字的格子(包括0)对应的是基变量, 空格所对应的变量是非基变量。
§4.2 求解运输问题的表上作业法 表 运输问题的初始调运方案 平衡表 运价表 B1 B2 B3 B4 发量 A1 3 1 4 6 5 A2 2 7 A3 8 收量 13 表中, 有数字的格子(包括0)对应的是基变量, 空格所对应的变量是非基变量。

17 §4.2 求解运输问题的表上作业法 显然，任何一个产销平衡的运输问题都可以用最小元 素法求出一个初始调运方案，又因为运输问题目标函
§4.2 求解运输问题的表上作业法 显然，任何一个产销平衡的运输问题都可以用最小元 素法求出一个初始调运方案，又因为运输问题目标函 数必然有下界（且非负），所以平衡运输问题一定有 最优解。人们可能认为用最小元素法得到的初始方案 一定是最优的，其实不然。该方案对应的运费等于 Z=3×3+1×4+2×4+4×4+0×6+3×8=61, 但该运输问 题的最小费用为55。

18 §4.2 求解运输问题的表上作业法 2.2 求检验数、最优性判别 对于每一个非基变量（空格）都对应一个检验数， 则有以下最优性准则：
§4.2 求解运输问题的表上作业法 求检验数、最优性判别 对于每一个非基变量（空格）都对应一个检验数， 则有以下最优性准则： 定理1.4.1 (最优性判别准则) 在运输问题的某个可行方案中，如果对应于每一个非基变量xij (即空格) 的检验数lij ≥0，则该基可行解为最优解，对应的调运方案为最优方案。 为了说明如何在表上作业法的过程中求出非基变量的检验数，下面介绍闭回路的概念。

19 §4.2 求解运输问题的表上作业法 闭回路：在调运方案中，从一个空格出发，沿水平或垂直方向前进，遇到一个适当的有数字的格子，则转向90°前进，这样必会又遇到一个适当的有数字的格子，同样再转向90°前进；经若干次后，必然会回到出发的那个空格，这样就形成一条由水平与垂直线构成的封闭折线，我们称这样的封闭折线为该空格的闭回路。该空格（非基变量）对应的检验数就等于该闭回路上所有偶次拐点的运价之和减去所有奇次拐点的运价之和。 在例1中： ①闭回路: 检验数 ②闭回路: 检验数

20 §4.2 求解运输问题的表上作业法 ③闭回路: 检验数 ④闭回路: 检验数 ⑤闭回路: 检验数 ⑥闭回路: 检验数
§4.2 求解运输问题的表上作业法 ③闭回路: 检验数 ④闭回路: 检验数 ⑤闭回路: 检验数 ⑥闭回路: 检验数 初学者可能感到这样求检验数比较麻烦,但它反映了检验数的本质。我们也可以用位势法来求检验数。

21 §4.2 求解运输问题的表上作业法 位势法：将运价表中基变量所对应的运价打“*” 号或者将数字画圈“○”，然后对运价表每一行、每一列同时加上或减去同一个数，当基变量对应的检验数（打“*”号的或画圈“○”的）等于零，其余各数就是各个非基变量所对应的检验数。 对例1，采用位势法求检验数过程如下 最后的数阵中没有标记*的数字就是非基变量的检验数。

22 §4.2 求解运输问题的表上作业法 2.3 求出调整量、在闭回路上进行调整
§4.2 求解运输问题的表上作业法 求出调整量、在闭回路上进行调整 从一个可行方案调整到另一个可行方案, 也就是从一个基可行解换基迭代到另一个基可行解, 且使目标函数值不断下降。运输问题表上作业法的换基迭代实际上是在调运表上负检验数对应的空格所在的闭回路上进行的. 第一个检验数小于零l24 =-1<0的空格所对应的非基变量为进基变量，并使这个非基变量的值由零增加到调整量。 调整量：该闭回路上所有奇次拐点调运量的最小值。

23 §4.2 求解运输问题的表上作业法 调整方法： 闭回路上每个奇次拐点的调运量都减去调整量 (其中有一个且仅允许有一个调运量为0变为空格成为非基变量，其他变为0的仍然要填上0)，各偶次拐点的调运量均加上调整量，其中有一个由非基变量(空格)变为基变量。 对例1，取 表2-3 运输问题调运方案调整表 B1 B2 B3 B4 发量 A1 3 1 4 A2 2 4-3→ → ●+3↓ 6 A3 0+3↑ ← ←3-3 收量 13

24 §4.2 求解运输问题的表上作业法 使用位势法求检验数，过程如下： 有检验数l33 =-1<0, 继续调整量, 取
§4.2 求解运输问题的表上作业法 使用位势法求检验数，过程如下： 有检验数l33 =-1<0, 继续调整量, 取 表2-4 运输问题调运方案调整表 B1 B2 B3 B4 发量 A1 3-3 → 1+3↓ 4 A2 2 ← ↑ ←3-3 6 A3 ●+3 ↑ 3 收量 13

25 §4.2 求解运输问题的表上作业法 注意：这里经调整以后，有3个基变量x13, x24, x31同时变为零！但只能有一个x13成为非基变量(空格)，另外两个x24, x31仍为基变量，其对应的调运量等于0。 继续求检验数： 此时所有检验数全部非负，因此对应的调运方案是最优的。 min Z=4×4+2×4+4×4+3×5=55。

26 §4.2 求解运输问题的表上作业法 例2 求表2-5对应的运输问题的最优解： 解：首先用最小元素法求初始调运方案，见表2-6。 总费用Z=
§4.2 求解运输问题的表上作业法 表 运输问题的平衡表与运价表 例2 求表2-5对应的运输问题的最优解： B1 B2 B3 B4 发量 A1 7 3 11 10 A2 4 1 9 2 8 A3 5 收量 6 20 解：首先用最小元素法求初始调运方案，见表2-6。 表 运输问题的初始调运方案 总费用Z= 4×3+3×10+3×1+1×2+6×4+3×5=86 B1 B2 B3 B4 发量 A1 4 3 7 11 10 A2 1 9 2 8 A3 6 5 收量 20

27 §4.2 求解运输问题的表上作业法 采用位势法求检验数： 有检验数为负,非最优方案,需要进行方案的调整,见表2-7。
§4.2 求解运输问题的表上作业法 采用位势法求检验数： 有检验数为负,非最优方案,需要进行方案的调整,见表2-7。 表 运输问题的调运方案调整表 B1 B2 B3 B4 发量 A1 4↓+1 ←3-1 7 5 2 A2 3 1→-1 ●↑+1 4 1 A3 6 9 收量 20 总费用Z=5×3+2×10+3×1+1×8+6×4+3×5=85

28 §4.2 求解运输问题的表上作业法 采用位势法求检验数： 所有检验数全部非负,此方案是最优的调运方案。
§4.2 求解运输问题的表上作业法 采用位势法求检验数： 所有检验数全部非负,此方案是最优的调运方案。 最小费用Z=5×3+2×10+3×1+1×8+6×4+3×5=85。 由于非基变量x11的检验数l11 =0, 该运输问题可能有不止一个最优方案。进行调整见表1-79，该表对应另一个最优方案。

29 §4.2 求解运输问题的表上作业法 最小费用Z=2×3+5×3+1×1+3×8+6×4+3×5=85 表2-8 运输问题的调运方案调整表
§4.2 求解运输问题的表上作业法 表 运输问题的调运方案调整表 B1 B2 B3 B4 发量 A1 ● →+2 → 5 → ↓2-2 7 2 5 A2 ↑3-2 ← ←1+2 4 1 3 A3 6 9 收量 20 最小费用Z=2×3+5×3+1×1+3×8+6×4+3×5=85

30 §4.2 求解运输问题的表上作业法 对例2用LINDO软件进行求解，程序如下：
§4.2 求解运输问题的表上作业法 对例2用LINDO软件进行求解，程序如下： min 3x11+11x12+3x13+10x14+x21+9x22 +2x23+8x24+7x31+4x32+10x33+5x34 st x11+x12+x13+x14=7 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x11+x21+x31=3 x12+x22+x32=6 x13+x23+x33=5 x14+x24+X34=6 end

31 §4.2 求解运输问题的表上作业法 结果如下： LP OPTIMUM FOUND AT STEP 6
§4.2 求解运输问题的表上作业法 结果如下： LP OPTIMUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST xX x x x x x x x x x x x

32 §4.2 求解运输问题的表上作业法 ROW SLACK OR SURPLUS DUAL PRICES
§4.2 求解运输问题的表上作业法 ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) 5) 6) 7) 8) NO. ITERATIONS=

33 §4.2 求解运输问题的表上作业法 用LINGO求解的基本程序如下 model: !3发点4收点运输问题; sets:
§4.2 求解运输问题的表上作业法 用LINGO求解的基本程序如下 model: !3发点4收点运输问题; sets: warehouses/wh1..wh3/: capacity; vendors/v1..v4/: demand; links(warehouses,vendors): cost, volume; endsets !目标函数; cost*volume); !需求约束; @for(vendors(J): @sum(warehouses(I): volume(I,J))=demand(J)); !产量约束;

34 §4.2 求解运输问题的表上作业法 @for(warehouses(I):
§4.2 求解运输问题的表上作业法 @for(warehouses(I): @sum(vendors(J): volume(I,J))<=capacity(I)); !这里是数据; data: capacity=7,4,9; demand=3,6,5,6; cost=3,11,3,10,1,9,2,8,7,4,10,5; enddata end

35 Variable Value Reduced Cost
§4.2 求解运输问题的表上作业法 运行结果(部分)如下 Objective value: Variable Value Reduced Cost VOLUME( WH1, V1) VOLUME( WH1, V2) VOLUME( WH1, V3) VOLUME( WH1, V4) VOLUME( WH2, V1) VOLUME( WH2, V2) VOLUME( WH2, V3) VOLUME( WH2, V4) VOLUME( WH3, V1) VOLUME( WH3, V2) VOLUME( WH3, V3) VOLUME( WH3, V4)

36 §4.2 求解运输问题的表上作业法 ★使用表上作业法，有以下特殊情况需要注意
§4.2 求解运输问题的表上作业法 ★使用表上作业法，有以下特殊情况需要注意 ⑴在用最小元素法作初始调运方案时，当出现供需相等时，这时可以(也只能)满足一家！另一家供(需)量相应地改为0；在下一次供应时，0也要进行供应或需求(如例1用最小元素法作初始调运方案)。 ⑵在方案的调整过程中，若奇次拐点的调运量有不止一个等于调整量，调整以后，有几个同时变为0，这时只允许一个变为空格成为非基变量，其余的仍为基变量，对应的调运量等于0，不能是空格。（如例1，方案的调整） ⑶在方案的调整过程中，如果调整量等于0，这时也要作形式上的调整，只是0与空格的位置互换罢了。

37 表3-1 产销不平衡时运输问题的平衡表与运价表
§4.2 求解运输问题的表上作业法 ⑷产销不平衡问题 ①若供大于求，即 ，则可以增加一个虚的销地(仓库), 其需要量为 并且各个产地到仓库的运价等于0。 例3 某建材公司有3个分厂，均生产水泥预制板，其产销情况及运价如表3-1所示，求运费最省的调运方案。 表 产销不平衡时运输问题的平衡表与运价表 B1 B2 B3 B4 发量 A1 220 3 11 10 A2 300 1 9 2 8 A3 400 7 4 5 收量 240 260 110

38 表3-2 化为产销平衡运输问题的平衡表与运价表
§4.2 求解运输问题的表上作业法 由于总发量920吨，收量为830吨，产销不平衡，发量比收量多90吨。如果把这90吨看成是库存的需求量，因此可在运价表中虚加一列，运价表也相应地增加一列，但各发点到库存的运价全为零，于是得到产销平衡的运输问题(表3-2)。 解 表 化为产销平衡运输问题的平衡表与运价表 B1 B2 B3 B4 库存 发量 A1 220 3 11 10 A2 300 1 9 2 8 A3 400 7 4 5 收量 240 260 110 90 920 其最优解(最小运输费)为：

39 §4.2 求解运输问题的表上作业法 若用LINDO或LINGO进行求解，就不必化成产销平衡的情况，可直接求解。 model: sets:
§4.2 求解运输问题的表上作业法 若用LINDO或LINGO进行求解，就不必化成产销平衡的情况，可直接求解。 model: sets: warehouses/wh1..wh3/: capacity; vendors/v1..v4/: demand; links(warehouses,vendors): cost, volume; endsets cost*volume); @for(vendors(J): @sum(warehouses(I): volume(I,J))=demand(J)); @for(warehouses(I): @sum(vendors(J): volume(I,J))<=capacity(I)); data: capacity=220,300,400; demand=220,240,260,110; cost=3,11,3,10,1,9,2,8,7,4,10,5; enddata end

40 §4.2 求解运输问题的表上作业法 部分输出结果如下(与输入信息重复的和无用信息不再列出)：
§4.2 求解运输问题的表上作业法 部分输出结果如下(与输入信息重复的和无用信息不再列出)： Global optimal solution found at iteration: Objective value: Variable Value Reduced Cost VOLUME( WH1, V1) VOLUME( WH1, V2) VOLUME( WH1, V3) VOLUME( WH1, V4) VOLUME( WH2, V1) VOLUME( WH2, V2) VOLUME( WH2, V3) VOLUME( WH2, V4) VOLUME( WH3, V1) VOLUME( WH3, V2) VOLUME( WH3, V3) VOLUME( WH3, V4)