运筹学-第四章-运输问题 (1)

1、运输问题 v运输问题及其数学模型 v运输问题的表上作业法 v运输问题的进一步讨论 例1：某部门有3个生产同类产品的工厂（产地），生产的产品 由4个销售点（销地）出售，各工厂的生产量、各销售点的销售 量（假定单位均为t）以及各工厂到各销售点的单位运价（元/t） 示于下表中 要求研究产品如何调运才能使总运费最小 4.1 运输问题及其数学模型 单位 销地 运价 产地 产量 291029 13425 84257 销量3846 4321 BBBB 3 2 1 A A A A2 A3 B2 A1 B3 B4 B1 s2=5 s3=7 d1=3 d2=8 d3=4 d4=6 s1=9 供应量 供应地运价 需

2、求量 需求地 2 9 10 2 1 3 4 2 8 4 2 5 运输问题网络图运输问题网络图 )4 . 3 . 2 . 1, 3 . 2 . 1(0 6 4 8 3 7 5 9 524824 371092min 342414 332313 322212 312111 34333231 24232221 14131211 343332312423 222114131211 jix xxx xxx xxx xxx xxxx xxxx xxxx xxxxxx xxxxxxZ x ij ij 约约束束条条件件： 目目标标函函数数： 为为运运量量设设 产量约束 销量约束 运输问题的一般提法是：设某种物资

3、有 个产地m, 1 A, 2 A , , m A 各产地的产量是;, 21m aaa有 个销地 , 1 B, 2 B, n Bn 各销地的销量是., 21n bbb假定从产地 ), 2, 1(miAi 到销地), 2 , 1(njB j 运输单位物品的运价是 ，问ij c 怎样调运这些物品才能使总运费最小？ 销地 产地 产 量 销 量 1 A 2 A m A 1 B 2 B n B 11 c 12 c n c1 11 x 12 x n x1 21 c 22 c n c2 21 x 22 xn x2 1m c 2m c mn c 1m x 2m x mn x 1 b 2 b n b 1 a 2

4、a m a 运价表 ) ( 0 min 11 ij jijij iij m i n j ijij x babx ax xcZ 当产销平衡时，其模型如下： 0,0,0 ijij abc假设： 当产大于销时，其模型是： ) ( 0 min 11 ij jijij iij m i n j ijij x babx ax xcZ 当产小于销时，其模型是： min () 0 ijij iji ijjij ij Zc x xa xbab x 1 1、平衡运输问题必有可行解，也、平衡运输问题必有可行解，也 必有最优解；必有最优解； 运输问题数学模型的特点运输问题数学模型的特点 证明 记 . 11 dba m

5、i n j ji 则令 d ba x ji ij ), 2 , 1;, 2 , 1(njmi 则 为运输问题的一个可行解。事实上： ij x n j ij i n j n j ji ij ab d a d ba x 111 ), 2 , 1(mi m i ji j m i m i ji ij ba d b d ba x 111 ), 2 , 1(nj 又因. 0, 0 ji ba所以. 0 ij x故 是一组可行解。 ij x 又因为总费用不会为负值（存在下界）。这说明，运输问题 既有可行解，又必然有下界存在，因此一定有最优解存在。 2 2、运输问题约束条件的系数矩阵、运输问题约束条件的系数矩

6、阵 运输问题数学模型的特点运输问题数学模型的特点 对运输问题数学模型的结构约束加以整理，可 知其系数矩阵具有下述形式： m行 n行 1运输问题是一个具有mn个变量和n+m个等型约束的线性 规划问题。 （41） mnmmnn xxxxxxxxx,;, 212222111211 jmiij eep ), 2 , 1;, 2 , 1(njmi () 1() 1() 1 000 110 000 101 000 ijimj mnmnmn pee 2运输问题约束方程组的系数矩阵是一个只有0和1两个数值 的稀疏矩阵,其中1的总数为 2mn 个。 3、约束条件系数矩阵的每一列有两个非零元素，这对应于 每一个变

7、量在前m个约束方程中出现一次，在后n个约束方 程中也出现一次 4、约束条件系数矩阵的秩是m+n-1。即运输问题的基变量总 数是m+n-1 证明：因A的前m行对应元素的和与后n行对应元素的和相等， 恰好都是： nm E ) 1 , 1 , 1 ( 1 所以A的行向量是线性相关 的。从而 r(A)m+n. 去掉A的第一行，并取如下m+n-1列，得到m+n-1阶子式 1112121311 | 000100 000010 000001 10 100111 010000 001000 nm Dp pp ppp 所以 r(A)=m+n-1. 对于产销平衡运输问题，除了上述特点外，还有以下特点： 1 所有结

8、构约束条件都是等式约束 2 各产地产量之和等于各销地销量之和 3 3、运输问题的解、运输问题的解 运输问题数学模型的特点运输问题数学模型的特点 运输问题是一种线性规划问题。前面讲述的单纯形法是 求解线性规划问题十分有效的一般方法，因而可用单纯 形法求解运输问题。 但是当用单纯形法求解运输问题时，先得在每个约束条件 中引入一个人工变量，这样一来，即使对于m=3、n=4这样 简单的运输问题，变量数目也会达到19个之多。 因此，我们利用运输问题数学模型的特点，引入了表上 作业法来求解运输问题 4.2 用表上作业法求解运输问题 表上作业法的基本思想： 先设法给出一个初始方案,然后根据确定的判别准则对初

9、始 方案进行检查、调整、改进，直至求出最优方案，如下图 所示。 初始化 最优性检验 迭代 （Iteration） 最优？ yes STOP no 这和单纯形法的求解思想完全一致， 但是具体的作法则更加简捷。 例1 某部门有3个同类型的工厂（产地），生产的产品由4个 销售点出售，各工厂的生产量、各销售点的销售量（假定单 位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2 中，问如何调运才能使总运费最小？ 销地 产地 产 量 412411 16 21039 10 85116 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 4-2 11 x 12

10、 x 13 x 14 x 21 x 22 x23 x 24 x 31 x 32 x 33 x 34 x 34333231242322 21 3 1 4 1 14131211 611589310 2114124min xxxxxxx xxxxxxcz ij ijij 4 , 3 , 2 , 1; 3 , 2, 1, 0 14 12 14 8 22 10 16 342414 332313 322212 312111 34333231 24232221 14131211 jix xxx xxx xxx xxx xxxx xxxx xxxx ij 该运输问题的数学模型为： 可以证明：约束矩阵的秩 r

11、(A) = m +n -1. 基变量的个数为 m+n-1. 表上作业法 v计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2 表上作业法 v计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2 下面介绍三种常用的方法。 一、给出运输问题的初始可行解（初始调运方案） l最小元素法 l西北角法 l沃格尔(Vogel)法 1。最小元素法 思想：优先满足运价（或运距）最小的供销业务。 销地 产地 产 量 412411 16 1039 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表

12、3-2 22 8 8 10 销地 产地 产 量 412411 16 2109 10 85116 22 销 量 8141448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2 10 12 8 销地 产地 产 量 41211 2109 10 85116 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2 10 4 16 10 6 8 销地 产地 产 量 41211 8 2109 10 8116 销 量 8121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2 10 4 16 10

13、 6 5 14 22 14 8 销地 产地 产 量 41211 8 2109 10 811 销 量 81248 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2 10 4 16 10 6 5 14 22 14 86 146 销地 产地 产 量 412 8 2109 10 811 销 量 81248 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 3 2 10 4 16 10 6 5 14 22 14 8 6 146 11 此时得到一个初始调运方案（初始可行解）：,10 13 x , 6 14 x, 8 21 x, 2 23 x,14 32 x, 8

14、 34 x 其余变量全等于零。 总运费为（目标函数值） 3 1 4 1ij ijijx cz 246685143228116410 此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6). 西北角法 西北角法是优先满足运输表中西北角（左上角）上空格的供 销需求。 销地 产地 产 量 412411 21039 10 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 11 x 销地 产地 产 量 412411 21039 10 85116 22 销 量 14121448 1 A 2 A 1 B

15、 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 销地 产地 产 量 412411 21039 10 85116 22 销 量 121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 12 x 14 销地 产地 产 量 412411 21039 10 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 销地 产地 产 量 412411 21039 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2

16、 8 16 8 8 6 22 x 10 销地 产地 产 量 412411 21039 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 销地 产地 产 量 412411 21039 85116 22 销 量 141448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 23 x 12 销地 产地 产 量 412411 21039 85116 22 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8

17、 16 8 8 6 10 6 4 8 销地 产地 产 量 412411 21039 85116 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 32 x 8 22 销地 产地 产 量 412411 21039 85116 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 8 22 8 14 销地 产地 产 量 412411 21039 85116 销 量 141248 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2

18、 8 16 8 8 6 10 6 4 8 22 8 14 34 x 14 销地 产地 产 量 412411 21039 85116 销 量 14121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 8 16 8 8 6 10 6 4 8 22 8 14 此时得到一个初始调运方案（初始可行解）：, 8 11 x , 8 12 x, 6 22 x, 4 23 x, 8 33 x,14 34 x 其余变量全等于零。 总运费为（目标函数值） 3 1 4 1ij ijijx cz 3726141183410612848 此解满足所有约束条件，且基变量（非零变量）的个数为6 （

19、等于m+n-1=3+4-1=6). 沃格尔（Vogel)法 初看起来，最小元素法十分合理。但是，有时按某一最小 单位运价安排物品调运时，却可能导致不得不采用运费很 高的其他供销点，从而使整个运输费用增加。 沃格尔法的思想： 对每一个供应地或销售地，均可由它到各销售地或 到各供应地的单位运价中找出最小单位运价和次小单位运 价，并称这两个单位运价之差为该供应地或销售地的罚数。 若罚数的值不大，当不能按最小运价安排运输时造成的运 费损失不大；反之，如果罚数的值很大，不按最小运价组 织运输就会造成很大的损失，故应尽量按最大罚数安排运 输。 销 地 产地 产 量 行罚数 123 412411 160 2

20、1039 101 8116 1 销 量 8121448 列 罚 数 12513 2 3 1 A 2 A 1 B 2 B 3 B 4 B 3 A 5 14 22 14 8 销 地 产地 产 量 行罚数 123 412411 1600 21039 1011 8511 2212 销 量 8141248 列 罚 数 12513 2213 3 1 A 2 A 1 B 2 B 3 B 4 B 3 A 8 14 6 14 6 销 地 产地 产 量 行罚数 123 412411 16000 1039 111 8511 2212 销 量 141248 列 罚 数 12513 2213 321 1 A 2 A 1

21、 B 2 B 3 B 4 B 3 A 8 14 6 14 6 2 8 10 8 2 销 地 产地 产 量 行罚数 456 41211 7 1039 6 8511 22 销 量 1448 列 罚 数 412 5 6 1 A 2 A 1 B 2 B 3 B 4 B 3 A 8 14 6 14 6 2 8 10 8 2 4 12 16 12 4 销 地 产地 产 量 行罚数 456 41211 70 103 60 8511 22 销 量 1448 列 罚 数 412 5 2 6 1 A 2 A 1 B 2 B 3 B 4 B 3 A 8 14 6 14 6 2 8 10 8 2 4 12 16 12

22、 4 9 4 此时得到一个初始调运方案（初始可行解）：,12 13 x , 4 14 x, 8 21 x, 2 24 x 32 14,x, 8 34 x 其余变量全等于零。 总运费为（目标函数值） 3 1 4 1ij ijijx cz 244685149228114412 此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6). 比较上述三种方法给出的初始基可行解，以沃格尔法给出 的解的目标函数值最小，最小元素法次之，西北角法解的 目标函数值最大。 一般说来，沃格尔法得出的初始解的质量最好，常用 来作为运输问题最优解的近似值。 销地 产地 产 量 4146 8

23、 1250 8 3751 4 销 量 656320 1 A 2 A 1 B 2 B 3 B 4 B 3 A 课堂练习课堂练习 表上作业法 v计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2 二、解的最优性检验 前面得到了初始基可行解，一般来说此解并非最优。下面介绍 最优性检验的两种方法。 1 闭回路法(Cycle method) 2 对偶变量法（dual variable method）也称为位势法 闭回路法（cycle method) 下面用最小元素法所确定的初始基本可行解来说明。 与单纯性原理相同，现目标是运费最少，故检验每一个非 基变量（对应于运输表中

24、的空格）的检验数是否. 0 ij ? ij 若所有空格的检验数全非负，则不管怎样均不能使运输费 用降低，即目标函数值已无法改进，这个解就是最优解 销地 产地 产 量 412 10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 3 A 1 B 2 B 3 B 4 B 考虑空格(A1,B1),设想由产地A1供应一个单位的物品给销地B1，为 使运入销地B1的物品总量不大于它的销量，应将A2运到B1的物品数 量减1，即将格子（A2,B1）中填入的数字8改为7； 另一方面，为使产地A2运出的物品数量正好等于它的产量(保证新 得

25、到的解仍为基可行解)，应将A2运到B3的物品数量增1。 同理A1运往B3的物品数量减1，A1运出的物品数量正好等于其产量 按照上述设想，由产地A1供给1个单位物品给销地B1,由此 引起的总运费变化是： 11212313 c -c +c -c= 4-2+3-4 =1 根据检验数的定义，它正是非基变量x11(或者说空格 (A1,B1)的检验数 定义1： 基变量（有数字的）对应的格为基格；非基变量（空格） 对应的顶点为非基格。 定义2： 从每一空格（非基格）出发，沿水平或垂直方向前进，每 碰到数字格转90o（有些情况也可以不改变方向）继续前 进，直到回到出发的空格为止，由此形成的封闭的折线称 为闭回

26、路。 规定：起始顶点的空格为第一顶点，则 =闭回路上奇数次顶点运价之和 闭回路上偶数次顶点运价之和 ij 销地 产地 产 量 412 10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 14324 1323211111 cccc 1 销地 产地 产 量 412 10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 2116512 14343

27、21212 cccc 2 1 销地 产地 产 量 412 10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 134116510 23131434322222 cccccc 1 2 1 销地 产地 产 量 412 10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 134119 2313142424 cccc 1 1 2 1 销地 产地

28、产 量 412 10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 106114328 34141323213131 cccccc 10 2 1 1 1 销地 产地 产 量 412 10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 12411611 1314343333 cccc 12 10 1 1 2 1 销地 产地 产 量 412

29、10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 1 2 11 1012 检验数中有负数，说明原方案不是最优解。 对偶变量法（位势法）(dual variable method) 用闭回路法判定一个运输方案是否最优，需要找出所 有空格的闭回路，并计算其检验数。当运输问题的产地和销 地很多时，空格的数目很大，计算检验数的工作量很大，而 用对偶变量法就简便得多。 nmvvvuuuY.2121 对产销平衡运输问题，若用u1,u2,um分别表示前m 个约束等式相对应的对偶

30、变量，用v1,v2vn 分别表示后n 个等式相对应的对偶变量，即有对偶向量 这时可将运输问题的对偶规划写成： 的符号不限ji ijji n j jj m i ii vu nj mi cvu st vbuaZ , ,.1 ,.1 . max 11 前面学习知道，线性规划问题变量xj的检验数可表示为： 1 jjjBjjjj czcc B PcYP 由此可写出运输问题某变量xij(对应于运输表中(Ai,Bj)的 检验数如下： 1212(,., ,.) () ijijijij ijm ij ij j j ni i czcYP cu uuv vvP cuv 其中 分别称为行位势、列位势。 ji vu ,

31、 有基变量所对应的检验数为零，可从m+n-1个等式 0)( jiij vuc （2.2） 解出所有的行位势、列位势。 （2.1） 可以证明，不论令 为何值， 始终不变。 avi)( ji vu 即 将不会随 的取值而改变。 ij i v 为此，在求解方程组（2.2）时，为计算简便，可指定一个位 势等于一个较小的整数或零。 销地 产地 产 量 412 10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 i u j v 1 0 4 10 3 9 2 jiij vuc 行

32、位势 列位势 设u1=1 当然，也可用采用解方程组的办法来求位势： 13 14 21 23 32 34 4 11 2 3 5 6 uv uv uv uv uv uv 两种方法任选一种 销地 产地 产 量 412 10 4 6 11 16 8 210 2 39 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 i u j v 1 0 4 10 3 9 2 12 1 1 1012 )( jiijij vuc 三。解的改进（用闭回路法调整） 选择进基变量的原则： , min|0 N klijij i j J 即选择非

33、基变量中检验数最小的一个进基。 在进基格点所对应的闭回路上，定义顶点的序号：自进基 格点起选定一个方向（比如顺时针方向），依次为第一 格、第二格、 在奇数格点上增加调整量 ，在偶数格点上减少调整量 。 其中调整量为 ),( |minjixij为闭回路中偶数格点 销地 产地 产 量 412411 16 8 21039 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 i u j v 1 0 4 10 3 9 2 12 1 1012 2 106 0 2 2 2 2 销地 产地 产 量 412 12 4 4 11 1

34、6 8 2103 2 9 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 i u j v 1 4 10 3 9 2 2 1 12 1 3 0 9 jiij vuc)( jiijij vuc 四。表上作业法计算中的两个问题 无穷多个最优解 若在最优解中，某个非基变量的检验数为零，则该问题有 无穷多个最优解 此时得到一个最优解：,12 13 x, 4 14 x, 8 21 x, 2 24 x ,14 32 x, 8 34 x其余变量全等于零。 总运费为（目标函数值） 3 1 4 1ij ijijx cz 2446

35、85149228114412 销地 产地 产 量 412 12 4 4 11 16 8 2103 2 9 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 i u j v 1 4 10 3 9 2 2 1 12 1 3 0 9 销地 产地 产 量 412 12 411 16 21039 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 i u j v 1 4 10 3 9 1 3 4 28 4 44 4 销地 产地 产 量 4

36、412 12 411 16 4 2103 6 9 10 8 14 511 8 6 22 销 量 814121448 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-2 i u j v 1 4 10 3 9 2 2 1 12 1 3 9 0 此时得另一个最优解：, 4 11 x,12 13 x, 4 21 x, 6 24 x ,14 32 x, 8 34 x其余变量全等于零。 总运费为（目标函数值） 3 1 4 1ij ijijx cz 24468514962441244 退化情况 与一般LP问题类似，运输问题也可能出现退化了的基本可 行解。有以下两种情况： （1）在确定初始基本

37、可行解时，若已确定在空格 处),(ji 要添上调运量 ，而此时发点的当前可发送量与收点的当 前需求量恰好相等。即发点的当前发送量已全部用完，而收 点的需求量已全部满足。因此应同时划掉发送的行及接受的 列。为了使调运表上确保有(m+n-1)个基变量的值，就需要在 所划掉的行（或列）的任一空格添上调运量0。这样就得到有 一个基变量取值为0的基本可行解退化解。 ij x 例如：下表给出一个34运输的运价及发送量与需求量。 试用最小元素法求该问题的一个初始基本可行解。 销地 产地 产 量 31145 7 7738 12106 9 销 量 365648 1 A 2 A 1 B 2 B 3 B 4 B 3

38、 A 表 4-2 6 0 1 1 6 3 4 此时得到一个退化了的初始基本可行解：, 0 12 x , 1 13 x, 6 14 x, 4 23 x, 3 31 x, 6 32 x 其余变量全等于零。 在用闭回路调整当前基本可行解时，有多个偶数格值相 等且都是极小值点 。此时只能取一个离基，其余的仍作为 基格。 例如：下表给出一个34运输问题的基本可行解及发送量 与需求量、基本可行解的检验数。试用闭回路法对其做出 调整。 销地 产地 产 量 3 17 3 39 销 量 364648 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 4-5 14 11 2 3 1 1 6 3 3 3

39、3 3 3 3 3 销地 产地 产 量 3 47 3 69 销 量 364648 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 4-5 14 11 2 1 1 0 3 3 3 运输问题的进一步讨论 一、产销不平衡运输问题 对产销不平衡问题，可转化为平衡问题，然后按表上作业 法求解。转换办法： 若产大于销，增加一个假想的销地（可视为库存地）其销 量设定为余量，相应的运价设为0。 若销大于产，增加一个虚拟的产地，其产量设定为不足 量，相应的运价也设为0。 例4 某市有3个造纸厂 ， 和 ，有4个集中用户 和 ，各工厂的生产量、各用户的需用量以及各 工厂到用户的单位运价（元/t）示于表

40、3-14中，问如何调运 才能使总运费最小？ 1 A 2 A 3 A 1 B , 2 B, 3 B 4 B 销地 产地 产 量 31234 8 11259 5 6715 9 销 量 4356 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-14 22 18 可增加一个假想的销地 5 B 销地 产地 产 量 312340 8 112590 5 67150 9 销 量 43564 1 A 2 A 1 B 2 B 3 B 4 B 3 A 表 3-14 5 B 补充：闭回路的数学定义 定义： 凡是能排成 1 11222231 1 12 122321 ,., ,., sss sss i j

41、i ji ji ji ji j i ji ji ji ji ji j xxxxxx xxxxxx 或 形式的变量的集合称为一个闭回路，并将这些变量称为这 个闭回路的顶点。 由此可以看出闭回路的几何特点： 闭回路都是一条封闭折线，每个顶点格子都是转角点 每一行或每一列只有且仅有两个顶点格子 1. 每两个顶点格子的连线都是水平的或垂直的。 可以证明的一个重要结论： m+n-1个变量构成基变量的充要条件是它不含闭回路，即 不存在以这些变量为顶点的闭回路 例题例题5：弹性需求问题：弹性需求问题 v设有三煤矿供应四地区，资料如下：设有三煤矿供应四地区，资料如下： 运价运价 地区地区 煤矿煤矿甲甲乙乙丙丙

42、丁丁 产量产量 A B C 16 14 19 13 13 20 22 19 23 17 15 25 50 60 50 最低需求最低需求 最高需求最高需求 30 50 70 70 0 30 10 不限不限 解题思路： v设法转化为标准型设法转化为标准型 v本题产量本题产量160万吨，最低需求万吨，最低需求110万吨，最高需求无万吨，最高需求无 限。实质上比较现实的最高需求限。实质上比较现实的最高需求210万吨万吨 v产量大于最小需求；小于最大需求。而标准型是：产量大于最小需求；小于最大需求。而标准型是： 产量产量=销量。销量。 v处理办法：设想一个虚拟煤矿处理办法：设想一个虚拟煤矿D，生产，生产

43、50万吨，但万吨，但 这个产量只能供应可有可无的最高需求部分，于是这个产量只能供应可有可无的最高需求部分，于是 各地的需求也应分为两个部分：基本需求、机动需各地的需求也应分为两个部分：基本需求、机动需 求求 v虚拟产量的运输费用为零，但它对于基本需求来讲，虚拟产量的运输费用为零，但它对于基本需求来讲， 运费为无穷大。运费为无穷大。 建模： 运价 地区 煤矿甲1甲2乙丙丁1丁2 产量 A B C D 16 14 19 M 16 14 19 0 13 13 20 M 22 19 23 0 17 12 25 M 17 12 25 0 50 60 50 50 需求量302070301050 210 2

44、10 最优解： 运价 地区 煤矿甲1甲2乙丙丁1丁2 产量 A B C D 3020 50 20 0 30 1030 20 50 60 50 50 需求量302070301050 210 210 运输模型的应用运输模型的应用 v例题例题5：某机床厂定下一年：某机床厂定下一年 合同分别于各季度末交货。合同分别于各季度末交货。 已知各季度生产成本不同，已知各季度生产成本不同， 允许存货，存储费允许存货，存储费0.12万元万元 /台季，三、四季度可以加台季，三、四季度可以加 班生产，加班生产能力班生产，加班生产能力8台台/ 季，加班费用季，加班费用3万元万元/台台 季 度 正常生 产能力 单位成本

45、（万元） 交货 台数 1 2 3 4 30 32 20 28 10.55 10.8 11 11.1 25 30 15 45 分析：分析： v可用线性规划，但用运输问题更简单可用线性规划，但用运输问题更简单 v要决策的问题是各季度生产量和交货量设要决策的问题是各季度生产量和交货量设xij 表示第表示第i季度生产第季度生产第j季度交货的台数季度交货的台数 v因加班时间生产成本不同，故要区别开来，因加班时间生产成本不同，故要区别开来， 三四季度可加班，视同增加两个季度三四季度可加班，视同增加两个季度 v需求量合计需求量合计115台，生产能力合计台，生产能力合计126台，供台，供 需不平衡，因此，增加一项闲置能力。需不平衡，因此，增加一项闲置能力。 建模：建模： 成本成本 交货交货 生产生产 闲置闲置 1 2 3 4 能力能力 产量产量 1季度正常生产季度正常生产 2季度正常生产季度正常生产 3季度正常生产季度正常生产 3季度加班生产季度加班生产 4季度正常生产季度正常生产 4季度加班生产季度加班生产 10.55 10.67 10.79 10.91 0 M 10.8 10.92 11.04 0 M M 11 11.12 0 M M 14 14.12 0 M M M 11.1 0 M M M 14.1 0 30 32 20 8 2