第3章 运 输 问 题 3 内容提要  运输问题模型的特点  产销平衡运输问题的表上作业法  产销不平衡运输问题的转化

Presentation on theme: "第3章 运 输 问 题 3 内容提要  运输问题模型的特点  产销平衡运输问题的表上作业法  产销不平衡运输问题的转化"— Presentation transcript:

1 第3章 运 输 问 题 3 内容提要  运输问题模型的特点  产销平衡运输问题的表上作业法  产销不平衡运输问题的转化
第3章 运 输 问 题 CHAPTER 内容提要  运输问题模型的特点  产销平衡运输问题的表上作业法  产销不平衡运输问题的转化  表上作业法在物流管理中的典型应用

2 3.1 运输问题模型 第2章中讨论了有关物资调运的问题，即运输问题。有时候为了书写简便，运输问题也被写做TP（Transportation Problem）。

3 3.1 运输问题模型 对某种物资，设有m个产地A1, A2, …, Am，称它们为发点，其对应产量为a1, a2, …, am，称它们为产量；另有n个销地B1, B2, …, Bn，称它们为收点，其对应销量为b1, b2, …, bn，称它们为销量。又知，从产地（发点）Ai运至销地（收点）Bj，该种物资每单位的运价为ci j（ci j≥0）。 试问：应如何安排调运方案，在满足一定要求的前提下，使总运费最低？

4 3.1 运输问题模型 根据上述参量的意义列出产销运价，如表3.1所示。 表3.1 产销运价表 销地 产地 B1 B2 … Bn 产量 A1
3.1 运输问题模型 根据上述参量的意义列出产销运价，如表3.1所示。 表3.1 产销运价表 销地 产地 B1 B2 … Bn 产量 A1 c11 c12 c1n a1 A2 c21 c22 c2n a2 Am cm1 cm2 cmn am 销量 b1 b2 bn ai bj

5 3.1 运输问题模型 表中：ai的单位为吨、公斤、件等；bj的单位为吨、公斤、件等；cij的单位为元/吨等。ai, bj, cij的单位应该一致（i1, 2, …, m；j1, 2, …, n）。

6 3.1 运输问题模型 表的右下角 ai表示各产地产量的总和，即总产量或总发量； bj表示各销地销量的总和，即总销量或总收量。这里有两种可能：
3.1 运输问题模型 表的右下角 ai表示各产地产量的总和，即总产量或总发量； bj表示各销地销量的总和，即总销量或总收量。这里有两种可能： （1） ai bj（总产量总销量），即产销平衡问题。 （2） ai≠ bj（总产量≠总销量），即产销不平衡问题。它又可分为两种情况：产大于销，即 ai＞ bj ；销大于产，即 ai＜ bj。 下面先讨论产销平衡问题，再讨论产销不平衡问题。

7 3.1 运输问题模型 令xij表示某物资从发点Ai到收点Bj的调拨量（运输量），可以列出产销平衡表如表3.2所示。 表3.2 产销平衡表
3.1 运输问题模型 令xij表示某物资从发点Ai到收点Bj的调拨量（运输量），可以列出产销平衡表如表3.2所示。 表3.2 产销平衡表 销 地产 地 B1 B2 … Bn 产 量 A1 x11 x12 x1n a1 A2 x21 x22 x2n a2 Am xm1 xm2 xmn am 销量 b1 b2 bn ai bj

8 3.1 运输问题模型 将表3.1和表3.2两个表合在一起，得到的一个新表，被称为运输表（或称为产销矩阵表），如表3.3所示。
3.1 运输问题模型 将表3.1和表3.2两个表合在一起，得到的一个新表，被称为运输表（或称为产销矩阵表），如表3.3所示。 表3.3 运输表（产销矩阵表） 销地 产地 B1 B2 … Bn 产量 A1 X11 c11 x12 c12 x1n c1n a1 A2 x21 c21 x22 c22 x2n c2n a2 Am xm1 cm1 xm2 cm2 xmn cmn am 销量 b1 b2 bn ai bj

9 3.1 运输问题模型 根据产销矩阵表，求上述问题的解等于求下面数学模型的解，即求：
3.1 运输问题模型 根据产销矩阵表，求上述问题的解等于求下面数学模型的解，即求： xij（i1, 2, …, m；j1, 2, …, n） （3-1）

10 3.1 运输问题模型 （3-2）

11 3.1 运输问题模型 从上述这一特殊的线性规划（LP）问题，可以得到下列三条结论。
3.1 运输问题模型 从上述这一特殊的线性规划（LP）问题，可以得到下列三条结论。 （1）该问题的基变量有mn1个。 （2）该问题一定有最优解。 （3）如果ai，bj全是整数，则该问题一定有整数最优解。 由于对这类问题的研究最早从运输问题开始，故这类问题统称为运输问题。

12 3.2 运输问题的表上作业法 3.2.1 产销平衡运输问题的表上作业法
3.2 运输问题的表上作业法 产销平衡运输问题的表上作业法 从上面的运输问题的数学模型中可以看到，它包含mn个变量，mn个约束条件。如果用单纯形法求解，应先在每个约束方程中引进一个人工变量。这样一来，即使是m3，n4这样简单的运输问题，变量数就有12个，显然计算起来非常繁杂；而用表上作业法来求解运输问题则比较简便。

13 3.2.1产销平衡运输问题的表上作业法 用表上作业法求解运输问题时，同单纯形法类似，首先要求出一个初始方案（即线性规划问题的初始基本可行解）。 一般来讲这个方案不一定是最优的，因此需要给出一个判别准则，并对初始方案进行调整、改进。

14 3.2.1产销平衡运输问题的表上作业法 每进行一次调整，我们就得到一个新的方案（基本可行解），而这个新方案一般比前一个方案要合理些，也就是对应的目标函数z值比前一个方案要小些。 经过若干次调整，我们就得到一个使目标函数达到最小值的方案——最优方案（最优解），而这些过程都可在产销矩阵表（运输表）上进行，故称为表上作业法。

15 3.2.1产销平衡运输问题的表上作业法 下面以煤的调运问题为例介绍表上作业法的计算过程。
例3.1 设有三个产煤基地A1、A2、A3，四个销煤基地B1、B2、B3、B4，产地的产量，销地的销量和从各产地至各销地煤炭的单位运价列于表3.4中，试求出使总运费最低的煤炭调拨方案。

16 3.2.1产销平衡运输问题的表上作业法 表3.4 产销运价表 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 A1 3 11 10
表3.4 产销运价表 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 A1 3 11 10 7 A2 1 9 2 8 4 A3 5 销 量 6 20 20

17 3.2.1产销平衡运输问题的表上作业法 （1）列出运输问题的产销矩阵表。 根据表3.4，可列出产销矩阵表（也称为运输表），如表3.5所示。

18 3.2.1产销平衡运输问题的表上作业法 表3.5 产销矩阵表 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 A1 x11 3
表3.5 产销矩阵表 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 A1 x x x x 7 A2 x x x x 4 A3 x x x x 9 销 量 3 6 5 20

19 3.2.1产销平衡运输问题的表上作业法 其中：xij为产地Ai到销地Bj的运量（i1, 2, 3；j1, 2, 3, 4），而将Ai到Bj的单位运价cij用小型字写在每格的右上角，以便直观地制定和修改调运方案。从表3.5的数据可知，例3.1是个满足产销平衡条件的产销平衡问题。 （2）初始方案确定的方法——最小元素法。

20 3.2.1产销平衡运输问题的表上作业法 在应用最小元素法确定初始方案时，必须注意以下两点。
（1）当选定最小元素（不妨假定为cst）后，如果发现该元素所在行的产地的产量as恰好等于它所在列的销地的销量bt（即asbt），这时，可在产销矩阵表上xst处填上一个数as，并画上圈。为了保证调运方案中画圈的数字为mn1个，只能在s行的其他格上都打上“×”（或在t列的其他格上都打上“×”），不可以同时把s行和t列的其他格子都打上“×”。

21 3.2.1产销平衡运输问题的表上作业法 （2）当最后只剩下一行（或一列）还存在没有填数和打“×”的格子时，规定只允许填数，不允许打“×”，其目的也是为保证画圈数字的个数恰为mn

22 3.2.1产销平衡运输问题的表上作业法 所谓闭回路，就是从调运方案的某一个打“×”处（xij）处作为一个起点出发，在表格里向纵的或横的方向一直走，碰到有圈数字的格才可以拐弯，这样拐了几个弯以后，再回到起点处，就画出一条封闭的折线（由水平和铅直的直线所组成）

23 3.2.1产销平衡运输问题的表上作业法 它所有的转角处（通常称为闭回路的顶点或转角点）除该打“×”处以外，其余的都必须是画圈的数字，这样的一条封闭折线成为过xij处的闭回路（简称回路）。 例如，表3.9中的直线表示的闭折线分别是过x11处和过x24处的闭回路。

24 3.2.1产销平衡运输问题的表上作业法 可以证明，过xij处的闭回路一定存在，而且是唯一的（证明略）。
下面我们简单说明用闭回路法来检验调运方案的原理。表3.9中x11的打“×”处表示A1生产的煤不调运给B1。

25 3.2.1产销平衡运输问题的表上作业法 我们假定把调运方案改变一下，让A1生产的煤调运1（万吨）给B1，观察过x11处的回路，为了保持新的平衡，就要依次在x13处减少1（万吨），x23处增加2（万吨），x21处减少1（万吨），即总运费增加33211 （万元）。

26 3.2.1产销平衡运输问题的表上作业法 这说明把A1生产的煤调运给B1 1（万吨），总运费比原方案增加1万元，是不合算的。我们把通过x11处的回路改变的运费数1（万元）称为x11处的检验数，记为111。如果所有的打“×”处检验数都大于或等于0，表明对调运方案作任何改变都将导致总的运费增加，没有比已给定方案更好的方案了，即给定的方案就是最优方案。

27 3.2.1产销平衡运输问题的表上作业法 否则，如某一打“×”处的检验数为负，则表明对调运方案做出调整后，运费就会减少，即给定方案不是最优方案。因此，利用闭回路求得检验数的正或负可以判别调运方案是否最优。

28 3.2.1产销平衡运输问题的表上作业法 这样，用闭回路法检验某调运方案是否最优，可按下面两步进行。
① 求检验数。从某xij的打“×”处出发，沿着它的闭回路前进（顺时针或逆时针都可以）。将这个打“×”处对应的单位运价加上正号，而下面首先遇到的一个顶点作为第一个顶点的对应的单位运价加上负号，再将第二个遇到的顶点处对应的单位运价加上正号，正负交错，依次类推。

29 3.2.1产销平衡运输问题的表上作业法 最后将这些带有正负号的运费相加而得到的总和称为xij处的检验数ij。例如，表3.9中x24处的检验数2 4沿它的闭回路（按顺时针）计算如下： 24 c24c23c13c14823101 因为过xij的回路是唯一的，所以它的检验数ij也是唯一的。

30 3.2.1产销平衡运输问题的表上作业法 ② 根据检验数进行判别。判别准则是：若所有的检验数都是非负的，即ij≥0，则所检查的调运方案为最优方案；否则，若存在负的检验数．则所检查的调运方案不是最优的。

31 3.2.1产销平衡运输问题的表上作业法 下面给出对表3.9调运方案检验的全过程。 11c11c13c23c2133211
解 ① 求检验数。 11c11c13c23c2133211 12c12c14c34c321110542 22c22c23c13c14c34c3292310541 24c24c23c13c14823101 31c31c21c23c13c14c34712310510 33c33c13c14c3410310512 将所有打“×”处的检验数填入表中，得到检验数表，如表3.12所示。

32 3.2.1产销平衡运输问题的表上作业法 ② 根据检验数进行判别。因为241＜0，所以调运方案Ⅰ不是最优的。 表3.12 检验数表 销地
表3.12 检验数表 销地 产地 B1 B2 A1 1 B3 A2 B4 A3 10 2

33 3.2.1产销平衡运输问题的表上作业法 （4）调运方案的调整——闭回路法。如果所得到的调运方案不是最优的，就必须调整。根据前面讲过的闭回路的原理，表3.6调运方案Ⅰ中241＜0，因此设法使x24不为零，就能使总运费减少，所以应对它作最大可能的调整。

34 3.2.1产销平衡运输问题的表上作业法 观察过x24的闭回路如表3.9所示，为了把A2生产的煤调运给B4，就要相应减少A2调运给B3的煤运量和A1调运给B4的煤运量，只有这样才能得到新的平衡，这两个格内较小的运量是1，即min（1，3）1，因此A2最多只能将1（万吨）煤调运给B4，经这样调整后可得到一个新的调运方案Ⅱ，如表3.13所示。

35 3.2.1产销平衡运输问题的表上作业法 方案Ⅱ的总运费z85万元，显然85＜86（万元）。
对方案Ⅱ进行检验，经计算所有打“×”处的检验数都是非负数（请同学自己作为练习），所以它是最优方案。可见，用闭回路法来调整调运方案是行之有效的。

36 3.2.1产销平衡运输问题的表上作业法 表3.13 调运方案Ⅱ 万吨，万元 销 地 产 地 B1 B2 B3 B4 产量 A1 3 × 11
表3.13 调运方案Ⅱ 万吨，万元 销 地 产 地 B1 B2 B3 B4 产量 A1 3 × 11 ⑤ 10 ② 7 A2 1 ③ 9 2 8 ① 4 A3 ⑥ 5 销 量 6 20

37 3.2.1产销平衡运输问题的表上作业法 一般地，调运方案的调整可分三步进行。
① 在检验数表中确定一个绝对值最大的负检验数st，作出过xst处的闭回路。 ② 从xst所在的格出发，沿着它的闭回路前进，在各奇数次顶点（画圈的数字）中选出最小的一个数（运量）记为d。 ③ 将d填在xst处，并画上圈，同时将闭回路上其他奇数次顶点的运量都减去d，在偶数次顶点的运量都加上d，这样就得到一个新的调运方案。

38 3.2.1产销平衡运输问题的表上作业法 一般说来，经过一次调整后，对新方案进行检验，可能还会出现负的检验数，那就需要再进行调整，直至所有检验数st≥0为止。 这里还需指出，有时在闭回路的调整过程中，奇数次顶点的画圈数字中有两个或两个以上相等的最小运量，这样在调整时，为了产销矩阵表上画圈数字的个数仍然保持mn1个，以便用表上作业法继续进行计算，规定在奇数次顶点最小运量处只打上一个“×”，其余的地方都填上“0”，并画上圈。画圈的0仍当做有圈的数字看待。

39 3.2.2产销平衡运输问题表上作业法步骤 第一步， 求初始调运方案（用最小元素法）。 它保证有调运量的格子个数（基变量个数）等于mn1。

40 3.2.2产销平衡运输问题表上作业法步骤 最小元素法的步骤如下。
（1）从没有“×”的运价格子中，找出最小运价（若同时有若干个相同最小运价则可任选一个），在它的左下角填入最大可能调运量（能够供应的数量和尚需数量的最小值），转步（2）。

41 3.2.2产销平衡运输问题表上作业法步骤 （2）若无“×”的格子只剩一行或一列， 转（1）；
否则，“×”去调运量已满足的行或列中其运价处没有填数和没有划“×”的格中的左下角填“×”，（只能在一行或一列中填“×”）， 转步骤（1）。

42 3.2.2产销平衡运输问题表上作业法步骤 第二步，求检验数。
若所有ij≥0，则最优解已求得，计算终止。填有调运量的格子为最优调运方案（未填调运量的格子，调运量为0），计算各调运量与对应格子运价之积，再求它们的和就是最低总运费。若至少有某个ij＜0，转第三步。

43 3.2.2产销平衡运输问题表上作业法步骤 第三步，调整。
（1）从最小负检验数的对应格子出发画直线，碰到有调运量的适当格子转角，做出惟一的一条闭回路（理论证明的结果）。 （2）在这个闭回路上，令画“×”处格子为偶数转角点，依次（无论沿顺时针方向还是沿逆时针方向）排出各转角点的奇偶性，再求调整量min（各奇数转角点调运量）。

44 3.2.2产销平衡运输问题表上作业法步骤 （3）按“偶点处加调整量，奇点处减调整量”的方法，重新安排回路上转角点处的调运量，将奇数转角点处调运量变为0的一个（仅能一个）格子右上角打“×”，回到第二步。

45 3.2.2产销平衡运输问题表上作业法步骤 注意：① 如遇到发量已发完，且收量已满足的格子还需要填入调运量时，就填入数字0；② 在最优解中若非基变量（画“×”处）的检验数为0，仍可从该格子处出发作唯一的闭回路，再按第三步调整可得另一最优解，此时目标函数最小值不改变。

46 3.2.2产销平衡运输问题表上作业法步骤 例3.2 工地有3个高地A1、A2、A3和4个洼地B1、B2、B3、B4，我们想把高地土方有计划地去填洼地。设各个高地的出土量和各个洼地的填土量如表3.14所示，各个高地与各个洼地之间的距离如表3.15所示。试用表上作业法制定最合理的调运方案。

47 3.2.2产销平衡运输问题表上作业法步骤 解（1）将运量表与距离表合并为产销矩 阵表，如表3.16所示。
解（1）将运量表与距离表合并为产销矩 阵表，如表3.16所示。 （2）用最小元素法求出初始调运方案Ⅰ，如表3.17所示。 （3）利用闭回路法求得检验数表Ⅰ，如表3.18所示。 因为检验数表中的检验数有负数，必须进行调整。

48 表3.14 运 量 表 10土方 洼地 高地 B1 B2 B3 B4 出 土 A1 70 A2 20 A3 10 填土 50 25 15
表3.14 运 量 表 土方 洼地 高地 B1 B2 B3 B4 出 土 A1 70 A2 20 A3 10 填土 50 25 15 100

49 表3.15 距 离 表 米 洼地高地 B1 B2 B3 B4 A1 10 5 2 3 A2 4 1 A3 6

50 表3.16 产销矩阵表 10土方，100米 洼地 高地 B1 B2 B3 B4 出 土 A1 10 5 2 3 70 A2 4 1 20
表3.16 产销矩阵表 土方，100米 洼地 高地 B1 B2 B3 B4 出 土 A1 10 5 2 3 70 A2 4 1 20 A3 6 填土 50 25 15 100

51 表3.17 调运方案Ⅰ 10土方，100米 洼地 高地 B1 B2 B3 B4 出 土 A1 10 5 × 2 ⑤ 3 70 A2 × 4
表3.17 调运方案Ⅰ 土方，100米 洼地 高地 B1 B2 B3 B4 出 土 A1 10 5 × ⑤ 70 A2 × × ⑩ ⑩ 20 A3 ⑩ × 填土 50 25 15 100

52 表3.18 检验数表Ⅰ 洼地 高地 B1 B2 B3 B4 A1 A2 5 1 A3 6

53 3.2.2产销平衡运输问题表上作业法步骤 （4）在检验数表Ⅰ中， 较大，所以过调运方案Ⅰ（表3.17）中x21处做出它的闭回路，进行调整得到调运方案Ⅱ，如表3.19所示。 （5）求调运方案Ⅱ的检验数表，如表3.20所示。因为调运方案Ⅱ检验数表中的检验数有负数，必须进行调整。

54 min z2010255102153204105520（土方公里）
3.2.2产销平衡运输问题表上作业法步骤 （6）因为135＜0，所以过调运方案（Ⅱ）（表3.19）中x13处做出它的闭回路，进行调整得到调运方案Ⅲ，如表3.21所示。 （7）再求出方案（Ⅲ）的检验数表Ⅲ，如表3.22所示。由于检验数全部为正数，所以调运方案Ⅲ为最优方案。 （8）目标函数值为： min z2010255102153204105520（土方公里）

55 表3.19 调运方案Ⅱ 10土方，100米 洼地 高地 B1 B2 B3 B4 出 土 A1 10 5 × 2 3 70 A2 4 × 3
表3.19 调运方案Ⅱ 土方，100米 洼地 高地 B1 B2 B3 B4 出 土 A1 10 5 × 3 70 A2 4 × 1 20 A3 × × 填土 50 25 15 100

56 表3.20 检验数表Ⅱ 洼地 高地 B1 B2 B3 B4 A1 5 A2 4 5 A3 6 1

57 表3.21 调运方案Ⅲ 10土方，100米 洼地 高地 B1 B2 B3 B4 出 土 A1 10 5 2 3 70 A2 4 × 3
表3.21 调运方案Ⅲ 土方，100米 洼地 高地 B1 B2 B3 B4 出 土 A1 10 5 2 3 70 A2 4 × × × 20 A3 × × 填土 50 25 15 100

58 表3.22 检验数表Ⅲ 洼地 高地 B1 B2 B3 B4 A1 A2 4 5 A3 6

59 用位势法求检验数 上面看到，要判别一个方案是否最优，需要过每一个打“×”处做出它的闭回路，再根据回路求出所有的检验数。当一个运输问题的产地和销地个数很多时，用这个方法计算检验数的工作量十分繁重。下面介绍一种更为简便的求检验数的方法——位势法。我们仍用煤的调运问题作为例子来介绍这种方法。

60 用位势法求检验数 表3.23给出了这个例子用最小元素法确定的初始调运方案。我们用位势法求检验数时，第一步先在表3.23中添加新的一列ui列（i的个数等于产地的个数）和新的一行vj行（j的个数等于销地的个数），如表3.24所示。

61 表3.23 初始调运方案 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 A1 × 3 × 11 ④ 3 ③ 10 7 3 A2
表3.23 初始调运方案 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 A1 × × ④ ③ A2 ③ × ① × A3 × ⑥ × ③ 销量 3 6 5 20

62 表3.24 初始调运方案（第一步） 万吨，万元 销地 产地 B1 B2 B3 B4 产量 ui A1 × 3 × 11 ④ 3 ③ 10 7
表3.24 初始调运方案（第一步） 万吨，万元 销地 产地 B1 B2 B3 B4 产量 ui A1 × × 11 ④ ③ 10 7 u1 A2 ③ × ① × 4 u2 A3 × ⑥ × 10 ③ 9 u3 销 量 3 6 5 20 vj v1 v2 v3 v4

63 用位势法求检验数 这里的ui和vj分别称为第i行和第j列的位势（i1, 2, …, m；j列的位势（i1, 2, …, m；j1, 2, …, n），并规定它们与表中画圈数字所在的格对应的单位运价有如下关系： （3-3）

64 用位势法求检验数 第二步是确定ui和vj的数值，由于这些ui和vj的数值相互是有关联的，所以只要任意给定其中的一个；根据关系式（3-3），很容易将其他所有的位势的数值求出。例如，在表3.24中，先令v11，则可由

65 3.2.3 用位势法求检验数 u2v11 u20 u2v32 v32 u1v33 u11 u1v410 v49
用位势法求检验数 u2v11 u20 u2v32 v32 u1v33 u11 u1v4 v49 u9v45 u34 u3v24 v28 把这些数分别填入表3.24的ui列和vj行，得到表3.25。

66 表3.25 初始调运方案（第二步） 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 ui A1 × 3 × 11 ④ 3 ③ 10
表3.25 初始调运方案（第二步） 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 ui A1 × 3 × 11 ④ ③ 10 7 1 A2 ③ × ① × 8 4 A3 × ⑥ × ③ 5 9  4 销量 3 6 5 20 vj 8 2

67 3.2.3 用位势法求检验数 第三步，求出位势后可以根据下面的原理求“×”处格子的检验数（即非基变量的检验数）。
用位势法求检验数 第三步，求出位势后可以根据下面的原理求“×”处格子的检验数（即非基变量的检验数）。 令ij表示xij处的检验数。例如，31可由闭回路法计算得到： 31c31c34c14c13c23c21c31（u3v4）（u1v4）（u1v3）（u2v3）（u2v1）c31（u3v1）

68 用位势法求检验数 其中c31是x31处对应的单位运价，（u3v1）恰好就是该打“×”处所在行和列的位势之和。类似地，可以得出任一打“×”处（xij处）的检验数，即 ij  cij(uivj) （3-4）

69 3.2.3 用位势法求检验数 根据式（3-4），很容易求出表3.25中所有打“×”处的检验数，即 113–111
用位势法求检验数 根据式（3-4），很容易求出表3.25中所有打“×”处的检验数，即 113–111 1211182 229081 248091 317 (4) 110 3310 (4) 212

70 用位势法求检验数 显然，求得的6个检验数与用闭回路求得的检验数（见表3.12）完全一致。如果检验数中出现了负数，对方案进行调整的方法同前面闭回路法一样。 最后再指出一点，有无可能在计算位势时出现中断或某一行或某一列可能得出两个不同的位势值的情况。答案是否定的，对给定的初始方案，只要首先给出一个位势，则其他行与其他列的位势存在且惟一。

71 3.2.3 用位势法求检验数 例3.3 对表3.19调运方案Ⅱ，用位势法求检验数。
用位势法求检验数 例3.3 对表3.19调运方案Ⅱ，用位势法求检验数。 解 （1）在表3.19中添加新的ui列和vj行得表3.26。 （2）令u15，用各有圈数字所在格的单位运价，按关系式cij(uivj)依次求出各位势值填入表3.26。

72 表3.26 调运方案Ⅱ 10土方，100米 洼地 B1 B2 B3 B4 出 土 ui A1 10 5 × 2 3 70 A2 4 × 3
表3.26 调运方案Ⅱ 土方，100米 洼地 高地 B1 B2 B3 B4 出 土 ui A1 10 5 × 3 70 A2 4 × 1 20 1 A3 × × 填土 50 25 15 vj 2 2

73 用位势法求检验数 （3）利用打“×”处的单位运价，按式（3-4），即可间接求得相应的检验数表Ⅱ，如表3.27所示。

74 表3.27 检验数表Ⅱ 洼地 高地 B1 B2 B3 B4 A1 5 A2 4 5 A3 6 1

75 确定初始方案的其他方法 对于运输问题的初始方案的确定，除了可用最小元素法之外，还可以用其他的方法。例如，西北角法和沃格尔法（Vogel法，也称为元素差额法）等，下面介绍这两种方法。

76 确定初始方案的其他方法 1．西北角法 西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足产销矩阵表中西北角（即左上角）上空格的供销需求，优先满足供应。 下面讨论表3.28所表示的例子。

77 表3.28 西北角法例子数据 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 A1 ⑧ 4 ⑧ 12 × 4 × 11 16 8
表3.28 西北角法例子数据 万吨，万元 销地 产地 B1 B2 B3 B4 产 量 A1 ⑧ ⑧ × × 16 8 A2 × ⑥ ④ × 10 4 A3 × × ⑧ 6 22 14 销量 8 14 12 48

78 确定初始方案的其他方法 由表3.28可知，该表左上角的空格是（A1，B1），在使用西北角法时先在（A1，B1）格中填入数字xijmin（a1，b1）min（16，8）8。因为B1的销量已经满足，所以B1所在列的格内x21、x31处打“×”，A1的可供量变为1688。在产销矩阵表尚未填数和打“×”的部分中，左上角格子变为（A1，B2）。由于min（a1–8，6）min（8，14）8，故在（A1，B2）格子中填入8。

79 确定初始方案的其他方法 因为A1的可供量已经用完，所以A1所在行的格内x13、x14处打“×”，B2的需求量由b214变为1486。这时（A2，B2）是产销矩阵表剩下部分的左上角格子。因min（a2，b8）6，在（A2，B2）中填入数字6，并在B2所在列的格内x32处打“×”，A2的可供量变为1064。如此继续下去，在（A2，B3）格中填入4，在（A3，B3）格中填入8，最后在（A3，B4）格中填入14，同时在A3行和B4列中的其他格中填“×”。寻求初始调运方案的过程示于表3.28中。

80 3.2.4 确定初始方案的其他方法 至此得到初始方案解为 x118，x128，x226，x234，x338，x3414
确定初始方案的其他方法 至此得到初始方案解为 x118，x128，x226，x234，x338，x3414 其他变量均等于0。 它所对应的目标函数z值为：z8481261043811146372

81 3.2.4 确定初始方案的其他方法 2．沃格尔法 沃格尔法（Vogel法）也称为元素差额法。
确定初始方案的其他方法 2．沃格尔法 沃格尔法（Vogel法）也称为元素差额法。 初看起来，最小元素法十分合理；但是，有时按某一最小单位运价优先安排物品调运时．却可能导致不得不采用运费很高的其他供销点对，从而使整个运输费用增加。对每一个供应地（或销售地），均可由它到各销售地（或各供应地）的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地（或销售地）的罚数（也称为差额）。

82 确定初始方案的其他方法 如果罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。

83 3.2.4 确定初始方案的其他方法 下面结合表3.28所表示的例子说明这种方法。
确定初始方案的其他方法 下面结合表3.28所表示的例子说明这种方法。 首先计算产销矩阵表中每一行和每一列的次小单位运价和最小单位运价之间的差值，并分别称之为行罚数和列罚数。将算出的行罚数填入位于表右侧行罚数栏的左边第一列的相应格子中，列罚数填入位于表下边列罚数栏的第一行的相应格子中，如表3.29所示。

84 表3.29 沃格尔法例子数据 销地 产地 B1 B2 B3 B4 产 量 行罚数 1 2 3 4 5 A1 × 4 × 12 ④ 11 16
表3.29 沃格尔法例子数据 销地 产地 B1 B2 B3 B4 产 量 行罚数 1 2 3 4 5 A1 × 4 × 12 ④ 11 16 ⑦ A2 ⑧ 2 × 10 × 3 ② 9 10 6 A3 × 8 × 11 ⑧ 6 22 销量 8 14 12 列 罚 数 ⑤ ③ ②

85 确定初始方案的其他方法 例如，A1行中的次小和最小单位运价均为4，故其行罚数等于0；A2行中的次小和最小单位运价分别为3和2，其行罚数等于321；B1列中的次小单位运价和最小单位运价分别为4和2，其列罚数等于2。如此进行，计算出本A1、A2和A3行的行罚数分别为0、1和1、B1、B2、B3和B4列的列罚数分别为2、5、1和3。

86 确定初始方案的其他方法 在这些罚数中，最大者为5（在表3.29中用小圆圈示出），它位于B2列。由于B2列中的最小单位运价是位于（A3，B2）格中的5，故在（A3，B2）格中填入尽可能大的运量14，此时B2的需要量得到满足，在B2列的其他格中填“×”。

87 确定初始方案的其他方法 在尚未填数和填入“×”的各行和各列中，按上述方法重新计算各行罚数和列罚数，并分别填入行罚数栏的第2列和列罚数栏的第2行。例如，在A3行中剩下的次小单位运价和最小单位运价分别为8和6，故其罚数等于2。由表3.29中填入这一轮计算出的各罚数可知，最大者等于3位于B4列，由于B4列中的最小单位运价为6，故在其相应的格中填入这时可能的最大调运量8，在A3行的其他格中填“×”。

88 确定初始方案的其他方法 用上述方法继续做下去，依次算出每次迭代的行罚数和列罚数，根据其最大罚数值的位置在表中的适当格中填入一个尽可能大的运输量，并在对应的一行或一列的其他格中填“×”。在本例中，依次在表中填入运输量x3214，x348，x218，x1312，x242，并相应地依次在B2列、A3行、B1列、B3列、A2行中填“×”。最后未画“×”的格仅为（A1，B4），在这个格中填入数字4，并同时在A1行和B4列中填“×”。

89 3.2.4 确定初始方案的其他方法 用这种方法得到的初始方案的解为
确定初始方案的其他方法 用这种方法得到的初始方案的解为 x1312，x144，x218，x242，x3214，x348 其他变量的值等于零。 这个解的目标函数值为 z124411822914586244

90 确定初始方案的其他方法 比较上述最小元素法、西北角法和沃格尔法三种方法给出的初始方案的解，以沃格尔法给出的解的目标函数值最小，最小元素法次之，西北角法解的目标函数值最大。一般说来，沃格尔法得出的初始解的质量较好，常用来作为运输问题最优解的近似解。

91 3.3 产销不平衡的运输问题 对于产销不平衡的运输问题，可分为总供给量（总产量）＞总需求量（总销量）（即 ai＞ bj）或总需求量（总销量）超过总供给量（总产量）（即 ai＜ bj）两种情形，关键是按具体情况虚设收点或虚设发点，其收量或发量是两类总量的差数，并按实际意义决定各新增格子上的单位运价，这样就把它们转化为产销平衡的运输问题。

92 3.3 产销不平衡的运输问题 下面举例说明上述方法。 例3.4 求下面运输问题的最优调拨方案，其产销运价表如表3.30所示。

93 表3.30 例3.4产销运价表 销地 产地 B1 B2 B3 B4 产 量 A1 2 11 3 4 7 A2 10 5 9 A3 8 1 销量 6 19 15

94 3.3 产销不平衡的运输问题 解 通过对右下角总供给、总需求的计算，发现 ai＞ bj，产量有剩余，应虚设一收点，叫做库存。任何发点到库存的单位运价设为0，收点“库存”的收量等于：总发量总收量19154，这就建立了一个平衡的运输问题，如表3.31所示。

95 表3.31 例3.4产销运价表（平衡方案） 销地 产地 B1 B2 B3 B4 B0 产 量 A1 2 ② 11 × 3 × 4 ③ 7
表3.31 例3.4产销运价表（平衡方案） 销地 产地 B1 B2 B3 B4 B0 产 量 A1 2 ② 11 × 3 × 4 ③ 7 A2 10 3 5 9 A3 8 1 ④ 销量 6 19

96 3.3 产销不平衡的运输问题 但是，在用最小元素法寻找初始调运方案时，每次不要考虑（新增）库存这一列的单位运价，否则一开始就去满足库存而不是实际的需要，会使初始方案离最优方案距离更远，会增加以后调整的工作量。 按最小元素法做出的初始调运方案（请读者重新做一遍并与此题结果核对）如上表所示。经检验，它就是最优调拨方案。 由于130，还可有另外的最优调拨方案但总运费不会再下降。

97 3.3 产销不平衡的运输问题 例3.5 设有3个化肥厂供应4个地区的化肥，并设等量的化肥在这些地区使用效果相同，各化肥厂年产量、各地年需求量，以及化肥的单位运价如表3.32所示，其中（3，4）处的M表示运价非常高。试求使总运费最低的调拨方案。

98 表3.32 例3.5产销运价表 30 70 10 不限 销地 产地 Ⅰ Ⅱ Ⅲ Ⅳ 产量/万吨 A 16 13 22 17 50 B 14
表3.32 例3.5产销运价表 销地 产地 Ⅰ Ⅱ Ⅲ Ⅳ 产量/万吨 A 16 13 22 17 50 B 14 19 15 60 C 20 23 M 最低需求/万吨 30 70 10 160 110 最高需求/万吨 不限

99 3.3 产销不平衡的运输问题 解 从满足各地最低需求角度，这是一个总产量大于总销量的运输问题，但从市场或支农角度，应尽量满足各地对化肥的最高需求，所以这又是一个总销量大于总产量的运输问题。

100 3.3 产销不平衡的运输问题 由于第Ⅳ地最高需求不限，但总产量只有160万吨，故第Ⅳ地的最高需求量是可以计算的，它等于从总产量中扣除其他各地最低需求量后的剩余，即160（30700）60。 于是所有各地最高需求量总和为；50703060210（万吨）。它超出总产量21016050（万吨），应虚拟一个产地D，其产（发）量为50。

101 3.3 产销不平衡的运输问题 由于各地最低需求量必须满足，故不能用虚拟发点D的发量去满足。为此，必须把最高需求比最低需求量多的收点分成两个。例如，销地II'I"，其中I'表示最低需求，I"表示超过最低需求的部分。由于D不能供给I'，相交处运价填M；由于D可以供给I"，但D是虚拟发点，即使对应格子填有正的调运量也不至于产生运费，因此交点处单位运价填0。其他仿此，我们做出下面平衡的产销矩阵表，如表3.33所示。

102 3.3 产销不平衡的运输问题 在用最小元素法确定初始运输方案时，首先不考虑虚拟发点D所在行的运价，而应先在运价最小的格子（A1，B3）处填入50，第一行中其他格子打“×”；接着填格子（A2，B3），只能填20，列中其他格子打“×”。这两个格子的调运量填好后，看到Ⅳ'的需求10单位必须由B处剩余产量满足，所以应先填（A2，B5）处的10。尽管其单位运价还不是最低的，否则会造成初始调拨方案与最优调拨方案相距甚远。余下格子填数的方法从略。本例调运量未加“〇”而用“（）”表示。如表3.34所示。

103 表3.33 例3.5产销矩阵表（一） 销 地 产 地 Ⅰ' Ⅰ" Ⅱ Ⅲ Ⅳ' Ⅳ" 产量/万吨 A 16 13 22 17 50 B 14
表3.33 例3.5产销矩阵表（一） 销 地 产 地 Ⅰ' Ⅰ" Ⅱ Ⅲ Ⅳ' Ⅳ" 产量/万吨 A 16 13 22 17 50 B 14 19 15 60 C 20 23 M D 需求量/万吨 30 70 10 160

104 表3.34 例3.5产销矩阵表（二） Ⅰ' Ⅰ" Ⅱ Ⅲ Ⅳ' Ⅳ" 产量/万吨 A 16 13 (50) 22 17 50 B 14
表3.34 例3.5产销矩阵表（二） 销地 产地 Ⅰ' Ⅰ" Ⅱ Ⅲ Ⅳ' Ⅳ" 产量/万吨 A 16 13 (50) 22 17 50 B 14 (10) (20) 19 15 60 C 20 23 (30) M D (0) 需求量/万吨 30 70 10 160

105 3.3 产销不平衡的运输问题 求出的初始调拨方案如表3.34所示。
3.3 产销不平衡的运输问题 求出的初始调拨方案如表3.34所示。 计算出行位势ui、列位势vj，再计算检验数后发现1617（018） 1＜0，26 3＜0，从（A2，B6）出发作闭回路，其转角点为（A2，B6）偶，（A4，B6）奇，（A4，B4）偶，（A3，B4）奇，（A3，B1）偶，（A2，B1）奇，（A2，B6）偶。 调整量min（50，30，10）10，按第三步调整结果如表3.35所示。

106 表3.35 例3.5产销矩阵表（三） 销地 产地 Ⅰ' Ⅰ" Ⅱ Ⅲ Ⅳ' Ⅳ" 产量/万吨 A 16 13 (50) 22 17 50 B
表3.35 例3.5产销矩阵表（三） 销地 产地 Ⅰ' Ⅰ" Ⅱ Ⅲ Ⅳ' Ⅳ" 产量/万吨 A 16 13 (50) 22 17 50 B 14 (20) 19 15 (10) 60 C (30) 20 23 M D (40) 需求量/万吨 30 70 10 160

107 3.3 产销不平衡的运输问题 3219（814）3＜0，它是最小负检验数。从（A3，B2）出发作闭合回路，找出：调整量min（20，40，20）20，并在回路上调整后得表3.36。

108 表3.36 例3.5产销矩阵表（四） 销地 产地 Ⅰ' Ⅰ" Ⅱ Ⅲ Ⅳ' Ⅳ" 产量/万吨 A 16 13 (50) 22 17 50 B
表3.36 例3.5产销矩阵表（四） 销地 产地 Ⅰ' Ⅰ" Ⅱ Ⅲ Ⅳ' Ⅳ" 产量/万吨 A 16 13 (50) 22 17 50 B 14 (0) (20) 19 15 (10) (30) 60 C 20 23 M D 需求量/万吨 30 70 10 160

109 3.3 产销不平衡的运输问题 对于表3.36所示的调运方案，经检验未发现负检验数，故它是最优调运方案。由于2114（013）0，还可能做出另一最优方案，但因从（A2，B1）出发的闭回路上，奇数的角点最小调运量为0，故不能产生实质性的另一最优方案。 最低总运费为2460，最优调运方案请读者补出。

110 3.4 运输问题应用案例 例3.6 （最大元素法）某公司进口一批商品，共有900万件。计划在A1港卸货100万件，A2港卸货400万件，A3港卸货400万件，然后再运往B1、B2、B3三个城市进行销售。已知三个城市的需要量分别为300万件、200万件、400万件。从港口运往各城市每万件销售利润由表3.37给出，问应如何因地制宜安排调运计划，才使总销售利润最多。

111 表3.37 例3.6销售利润表 元/万件 城市 港口 B1 B2 B3 A1 700 500 480 A2 850 600 A3 400 300

112 3.4 运输问题应用案例 解 本问题是求总销售利润最多的解，所以用最大元素法来进行研究。 首先说一下什么叫最大元素法。它与最小元素法的区别主要表现在：确定初始方案时将最小元素中的“小”字改为“大”字；用检验数判别方案时，若所有ij≤0，最优解已获得；若某个检验数ij＞0时，还要进行调整。ij＞0的经济意义是调整1个单位利润收入的增加值。 现采用最大元素法进行求解。为此做一个产销矩阵表，如表3.38所示。

113 表3.38 例3.6产销矩阵表（一） 元/万件 城市 港口 B1 B2 B3 A1 700 × 500 (100) 480 ( 0 )
表3.38 例3.6产销矩阵表（一） 元/万件 城市 港口 B1 B2 B3 卸货量/万 A1 700 × 500 (100) 480 ( 0 ) 100 A2 850 (300) 600 400 A3 300 (400) 需要量/万 200

114 3.4 运输问题应用案例 第一个应填“调运量”的格子为（A2，B1），因为它的销售收入850最大。因min（300，400）300，故填入300，此处未用“〇”圈上而用“（）”表示。它的经济意义，是从港口A2运到城市B1后销售收入最高，就尽可能多地优先安排调运。这只是一种局部观点，即还未在全局上进行考察和协调。

115 3.4 运输问题应用案例 接着在B1城市其他收入处左下角空格打“×”，因为B1城市的需要已满足。以后的步骤不一一重述，初始方案安排如表3.38所示。

116 3.4 运输问题应用案例 现在求检验数，方法同前。
3.4 运输问题应用案例 现在求检验数，方法同前。 因为11c11（u1v1）700（0650）50＞0，其他各格没有正检验数。 从（A1，B1）出发作闭回路，其转角点为（A1，B1）偶，（A2，B1）奇，（A2，B2）偶，（A1，B2）奇。奇数转角点的销售收入总和8505001 350，而偶数转角点的销售收入总和7007001400。

117 3.4 运输问题应用案例 因此当每个奇数的转角点上的计划数减少1万件时，总销售收入将减少1 350元；而每个偶数转角点上的计划数增加1万件时，总销售收入将增加1 400元。如作这种安排，总收入将增加50元，这正是1150的经济意义。 于是上述回路上的调整量min（300, 100）100，调整结果如表3.39所示。

118 表3.39 例3.6产销矩阵表（二） 元/万件 城市 港口 B1 B2 B3 卸货量/万 A1 700 (100) 500 × 480
表3.39 例3.6产销矩阵表（二） 元/万件 城市 港口 B1 B2 B3 卸货量/万 A1 700 (100) 500 × 480 (0) 100 A2 850 (200) 600 400 A3 300 (400) 需要量/万 200

119 A1 →B1（表示由港口A1运到城市B1销售100万件，下同）
3.4 运输问题应用案例 通过计算，发现在每个有“×”的格子里，它们的检验数都是负的，所以这是一个最优方案，即100 A1 →B1（表示由港口A1运到城市B1销售100万件，下同） A2 → B1， A2 → B2， A3 → B3 这种安排可获得最大的总收入为 z（700×100）（850×200）（700×200）（500×400）58 000（元）

120 3.4 运输问题应用案例 由于在变量个数相等的情况下，表上作业的计算远比单纯形法简单得多；所以在解决生产管理的实际问题时，人们常常尽可能把某些线性规划问题（表面上看来并不是运输问题）进行适当处理后转化为运输问题的数学模型，再用表上作业法来求解。下面我们举一个例子来说明。

121 3.4 运输问题应用案例 例3.7 （生产计划问题）某造船厂按订货合同必须在当年每季度末分别提供15、30、20、25条同一类型的驳船。已知该厂每个季度的生产能力及生产每条驳船的成本如表3.40所示；又若生产出来的驳船当季度不交货，每条驳船积压一个季度需支出存储、维护等费用0.4万元。试问在完成合同的情况下，该厂的生产计划应任何安排，才能使全年的生产费用最少？最少费用为多少？

122 表3.40 例3.7数据表 季度 一 二 三 四 生产能力/条 30 25 18 成本/万元 20 20.6 20.4 21

123 3.4 运输问题应用案例 解 用运输问题的方法求解。
3.4 运输问题应用案例 解 用运输问题的方法求解。 把当年中的4个季度当成4个收点，收量就是每季度的需求量；每季度的生产当成一个发点，共有4个发点，发量分别为生产能力。 4个季度的生产总能力 30302518103 4个季度需求量总和 1530202590

124 3.4 运输问题应用案例 这是个供给量大于总需求量的运输问题，应虚设“库存”或“不生产”这个收点B，其收量1039013（条）。它的对应运费（这里应是单条驳船的生产成本）都等于0（它表示有能力生产，但实际上不需要生产的驳船数）。

125 3.4 运输问题应用案例 另外，在每个季度，生产供给需求的“单件运费”实际上也是单件的生产成本费。由于每季度的产量不能供应前面季度的需求（例如，第四季度的产量就不能满足第一至第三季度的需求）；所以，这里的产销矩阵表（也应叫做产销—成本表）表中左下角所有格子成本数字应为M（见表3.41），这里的M是一个很大很大的数，而右上角元素按实际意义计算。

126 3.4 运输问题应用案例 例如，（A1，B1）处的成本就是第一季度生产单条船的成本值20，（A1，B2）处为第一季度生产船供给第二季度的需求，除了生产成本外，应添上单件存储、维护费用0.4，故为200.420.40。（A1，B3）处为第一季度生产船供给第三季度的需求，除了生产成本外，应添上二个季度的单件存储、维护费用0.420.8，故为200.820.80。右上角其他格子处“运价”同此计算，其结果如表3.41所示。

127 表3.41 例3.7产销矩阵表（一） 销地 产地 一 二 三 四 B 产量 20 20.4 20.8 21.2 30 M 20.6 21
表3.41 例3.7产销矩阵表（一） 销地 产地 一 二 三 四 B 产量 20 20.4 20.8 21.2 30 M 20.6 21 21.4 25 18 需求量 15 13

128 3.4 运输问题应用案例 因此，表3.41中数据的计算结果有很强的规律性，最小元素的位置也是有规律的，作检验数也可利用规律而少算不少数据。
3.4 运输问题应用案例 因此，表3.41中数据的计算结果有很强的规律性，最小元素的位置也是有规律的，作检验数也可利用规律而少算不少数据。 利用表上作业法可以求得这个问题的最优方案，如表3.42所示。请读者写出此问题的求解过程。

129 表3.42 例3.7产销矩阵表（二） 销地 产地 一 二 三 四 B 产 量 20 (15) 20.4 20.8  21.2 30 M
表3.42 例3.7产销矩阵表（二） 销地 产地 一 二 三 四 B 产 量 20 (15) 20.4 20.8  21.2 30 M 20.6 21 21.4 (2) (13) (20) (5) 25 (18) 18 需求量 15 13

130 3.4 运输问题应用案例 由上述最优方案可得该厂全年最小的生产费用为
3.4 运输问题应用案例 由上述最优方案可得该厂全年最小的生产费用为 minz201520.41520.61521.4220.42020.852118 （万元） 最后我们指出，这个问题的最优方案不是惟一的。

131 3.4 运输问题应用案例 例 某公司承担4条航线的运输任务，已知：① 各条航线的起点城市和终点城市及每天的航班数如表3.43所示；② 各城市间的航行时间，如表3.44所示；③ 所有航线都使用同一种船只，每次装船和卸船时间均为1天。问该公司至少应配备多少条船才能满足所有航线运输的需要？

132 表3.43 起点城市、终点城市及航班数 航 线 起点城市 终点城市 每天的航班数 1 E D 3 2 B C A F 4

133 表3.44 各城市间的航行时间 至 从 A B C D E F 1 2 14 7 3 13 8 15 5 17 20

134 3.4 运输问题应用案例 解 所需船只可分为两部分。
3.4 运输问题应用案例 解 所需船只可分为两部分。 （1）航线航行、装船、卸船所占用的船只。对各航线逐一分析，所需船只数列入表3.45中，累计共需91条船。

135 表3.45 例3.8数据分析表（一） 1 17 19 3 57 2 5 10 7 9 4 13 15 航线 装船天数 卸船天数 航行天数
表3.45 例3.8数据分析表（一） 航线 装船天数 卸船天数 航行天数 小计 航 班 数 所需船数 1 17 19 3 57 2 5 10 7 9 4 13 15

136 3.4 运输问题应用案例 （2）各港口之间调度所需船只数。这由每天到达某一港口的船只数与它所需发出的船只数不相等而产生。各港口城市每天到达船只数、需求船只数及其差额列于表3.46中。

137 表3.46 例3.8数据分析表（二） 城 市 A B C D E F 每天到达 1 2 3 每天需要 余缺数 1 3

138 3.4 运输问题应用案例 将船由多余船只的港口调往需用船只的港口为空船行驶，应采用合理的调度方案，以使“调运量”最小。为此，建立表3.47所示的运输问题，其单位运价取为相应一对港口城市间的航行时间（天数）。

139 表3.47 数据分析表（三） 至 从 A B E 多余船数 C 2 3 5 D 14 13 17 F 7 8 1 缺少船数

140 3.4 运输问题应用案例 用表上作业法求解这一运输问题，可得如下两个最优解： xCE2，xDA1，xDB1，xFE1
3.4 运输问题应用案例 用表上作业法求解这一运输问题，可得如下两个最优解： xCE2，xDA1，xDB1，xFE1 xCA1，xCE1，xDB1，xDE1，xFE1 按这两个方案调运多余船只，其目标函数值等于40，说明各港口之间调度所需船只至少为40艘。 综合以上两个方面的要求，在不考虑维修、储备等情况下，该公司至少要配备131条船，才能满足4条航线正常运输的需要。

141 3.5 指派问题 指派问题及其数学模型 指派问题（Assignment Problem）是运筹学中一个具有理论意义又很有实用价值的问题。其一般提法是：设有n个人，需要分派他们去做n件工作。由于每人的专长不同，各人做何种工作的效率可能不同，因而创造的价值也不同，所以应研究如何安排才能使创造的总价值最大。

142 指派问题及其数学模型 例3.9 现有4辆装载不同货物的待卸车，派班员要分派给4个装卸班组，每个班组卸一辆。由于各个班组的技术专长不同，各个班组卸不同车辆所需时间（h）如表3.48所示。问派班员应如何分配卸车任务，才能使卸车所花的总时间最少？

143 表3.48 例3.9数据表 装卸组 待卸车（P1） 待卸车（P2） 待卸车（P3） 待卸车（P4） Ⅰ 4 3 1 Ⅱ 2 6 5 Ⅲ Ⅳ

144 指派问题及其数学模型 类似的例子很多：如有n项加工任务，如何分派到n台机床上加工使总费用最低；有n条航线，怎样指定n艘船去航行等。对应于每个指派问题，所给出的类似于表3.48那样的表格称为系数矩阵，其元素cij（cij≥0; i=1, 2, …, n; j1, 2, …, n）根据实际问题的不同，可表示时间、费用、距离等。

145 3.5.1 指派问题及其数学模型 解 为求解此类问题，引入0—1变量xij。并令 当指派第i人去完成第j项任务
指派问题及其数学模型 解 为求解此类问题，引入0—1变量xij。并令 当指派第i人去完成第j项任务 当不指派第i人去完成第j项任务

146 指派问题及其数学模型 这样，指派问题的数学模型就可表示为 （3-5） （3-6） （3-7） （3-8）

147 匈牙利法 我们知道，指派问题都要给出系数矩阵。例3.9中的系数矩阵为

148 3.5.2 匈牙利法 求出指派问题一个可行解并不难，问题是如何求出最优解。
匈牙利法 求出指派问题一个可行解并不难，问题是如何求出最优解。 指派问题的最优解具有这样的性质：若从系数矩阵（cij）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（bij），那么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。

149 3.5.2 匈牙利法 下面利用这个性质并结合例3.9，讨论指派问题的一般解法。 第一步 对系数矩阵进行变换，使各行各列中都出现0元素。
匈牙利法 下面利用这个性质并结合例3.9，讨论指派问题的一般解法。 第一步 对系数矩阵进行变换，使各行各列中都出现0元素。 （1）从系数矩阵的每行元素中减去该行的最小元素。 （2）再从所得系数矩阵的每列元素中减去该列的最小元素。

150 匈牙利法 若某行（列）已有0元素，就不必再减了。例3.9的计算为 总共减去的数为1232210。

151 匈牙利法 第二步 试求最优解。 经过第一步的变换后，矩阵的每行每列都有了0元素。我们的目的是找出n个位于不同行和不同列的0元素，并以这样的0元素对应的xij1，令其他的xij0。这样得出的解对变换后的系数矩阵（bij）来说，其目标函数值为零，故为（bij）问题的最优解，根据上述性质，它也是原问题的最优解。

152 3.5.2 匈牙利法 在（bij）中找位于不同行和不同列的0元素可按下述方法进行。
匈牙利法 在（bij）中找位于不同行和不同列的0元素可按下述方法进行。 （1）从行开始，遇到每行只有一个0元素就用括号括上， 记做（0），然后划去所在列的其他0元素，用 表示，遇到有两个及其以上的0元素的行先放下。 （2）进行列检验，给只有一个0元素的列中的0元素用括号括上，记做（0），然后划去所在行的其他0元素，用 表示。

153 3.5.2 匈牙利法 （3）反复进行第（1）步和第（2）步。
匈牙利法 （3）反复进行第（1）步和第（2）步。 （4）若仍存在没有括上的0元素，而且同行（列）的0元素至少有两个，这时可以从有0元素最少的行（列）开始，比较这行（列）各0元素所在列（行）中0元素的数目，选择0元素少的那列（行）的这个0元素加括号。然后划掉同行同列的其他元素。如此反复进行，直到所有的0元素都已括上和划掉为止。

154 匈牙利法 （5）若（0）元素的数目等于系数矩阵的阶数n，那么该指派问题的最优解已经得到。否则转入第（3）步。

155 匈牙利法 在例3.9中，第一行只有一个0元素。就在0处做出标号（0），表示第4辆车已分配给第1组工人卸车，因此，第四列其他元素如有0就不能再分派。同理，第二行有一个0元素，做出标号（0）。第三行有两个0元素，先放下。第四行有一个0元素，做出标号（0）同时划去同列的0元素，作标号 。得到

156 匈牙利法

157 匈牙利法 然后进行列检验，第一、第二、第四列已没有未做标号的0，第三列有一个0，标上括号，表示第3个车辆分派给第3组工人卸车。于是得到

158 匈牙利法 此时（0）元素的数目等于系数矩阵的阶数4，故该指派问题的最优解已得到，最优解的矩阵形式为

159 3.5.2 匈牙利法 其目标函数值为 zc14c21c33c42125210。
匈牙利法 其目标函数值为 zc14c21c33c42125210。 注意，此值与前面在求（bij）的过程中所减去的数值相等。

160 匈牙利法 例3.10 求如下所示系数矩阵（cij）的指派问题的最优解。

161 匈牙利法 解 第一步，对原系数矩阵进行变换，即 → →

162 匈牙利法 第二步，试求最优解，按上述步骤运算，得到矩阵，如式（3-9）所示。 （0） （0） 1 （0） 2 （3-9）

163 3.5.2 匈牙利法 这里（0）的个数为3，而n4，所以还未求出最优解，应转入第三步。
匈牙利法 这里（0）的个数为3，而n4，所以还未求出最优解，应转入第三步。 第三步，作最少的直线但要求覆盖所有0元素，能覆盖所有0元素的最少直线数等于在0处做出标号（0）的最多个数。方法如下：

164 3.5.2 匈牙利法 （1）对没有（0）的行打√号； （2）对打√号的行上的所有有0元素的列打√号；
匈牙利法 （1）对没有（0）的行打√号； （2）对打√号的行上的所有有0元素的列打√号； （3）再对打√号的列上有（0）的行打√号； （4）重复（2）、（3）项，直到得不出新的打√号的行和列为止； （5）对没有打√号的行画横线，所有打√号的列画纵线，这就是能覆盖所有0元素的最少的直线集合。

165 3.5.2 匈牙利法 在例3.10中，对矩阵（3-9）按以下次序进行： （3-10） √
匈牙利法 在例3.10中，对矩阵（3-9）按以下次序进行： 先对第四行打√号，接着对第一列打√号，再对第二行打√号。对第一行、第三行、第一列画直线，得矩阵（3-10） √ √ （3-10）

166 匈牙利法 第四步，再对系数矩阵进行变换，以增加0元素。为此，在没有被直线覆盖的部分中找出最小元素。然后对没有画直线的行，各元素都减去这个最小元素；而对画直线的列，各元素都加上这最小元素，以保待原来0元素不变。这样得到新的系数矩阵（它的最优解与原问题相同）。对新的系数矩阵进行第二步，若能求出n个不同行、不同列的0元素，则已得最优解；否则回到第三步重复进行。

167 匈牙利法 在矩阵（3-10）中，没有被直线覆盖部分的最小元素为1，于是第二行、第四行都减去1；第一列加上1，得到新的矩阵，如式（3-11）所示。 （3-11）

168 匈牙利法 进行第二步，先在第三列的0元素处标（0），并划去同行的0元素。此时，余下的每行、每列中都有两个0元素，可在第二行两个0元素中任选一个标（0）。例如，在第二行第一列处标（0）。再往下进行，得矩阵如式（3-12）所示。

169 匈牙利法 该矩阵中，具有n个位于不同行和不同列的0元素，这就得到了最优解。相应的解矩阵为 目标函数值为 z755320

170 匈牙利法 当指派问题的系数矩阵经过变换后，出现每行、每列都有两个或两个以上0元素时，可任选一行（列）中某一个0元素标（0），再划去同行（列）的其他0元素。这种情况下原问题有重解。例3.10就属于这种情况

171 3.5.3 对匈牙利法的两点说明 （1）指派问题中人数和工作任务数不相等时应如何处理？
对匈牙利法的两点说明 （1）指派问题中人数和工作任务数不相等时应如何处理？ 在例3.9中，待卸车的数量（m）与装卸班组的数目（n）是相同的，符合这一条件的指派问题称为标准指派问题。如果n与m不相同时，则称为非标准指派问题。遇到非标准指派问题时，应先把它转化成标准指派问题，然后再求解。例如，例3.9中如果装卸班组的数量多于待卸车的数量，即n＞m，这时可以虚构nm个待卸车。使装卸班组与待卸车数目相同，并令虚构的待卸车的卸车时间都为0，这样目标函数保持不变。

172 3.5.3 对匈牙利法的两点说明 （2）如果要求目标函数值的最大值，应如何处理？
对匈牙利法的两点说明 （2）如果要求目标函数值的最大值，应如何处理？ 匈牙利法只限于求解最小化问题。对于求目标函数值最大的向题，不能采用改变目标函数系数符号的方法，因为匈牙利法要求系数矩阵中每个元素都是非负的。对于求最大值问题

173 对匈牙利法的两点说明 可作一个新矩阵 使得 其中M是一个足够大的常数（如取cij中最大的元素即可），以保证 ≥ ，使之符合匈牙利法的条件。这时解问题 所得的最小值解就是原问题的最大值解。