2013-8-4 14
B1
B2 11 3
B3
B4 10
产量
A1
A2 A3
3
7
4
1 9 2 8
3
4 9
3
7 4 10
1
5
6
销量 3 6 5 6
3
总的运输费用＝（3×1）＋（6×4） ＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元
2013-8-4 15
2.西北角法（或左上角法）： 此法是纯粹的人为规定，没有理论依据和实际背景， 但它易操作，特别适合在计算机上编程计算，因而受 欢迎。方法如下： 3 4 2 6 6 2 0 0 0 2 3 5 5 5 5 3 0 7 4 0 0 0 0 4 4 4 2 0 0 6 9 9 9 9 9 0 6 6 3 4 0 0 6 0 2 2 0 6 0 0 3 6 6 总的运费＝(3×3)＋(4×11)＋(2×9) 0 ＋(2×2)＋(3×10)＋(6×5)＝135元
2013-8-4 17
表4-1
销 地 产地 A1 A2 A3 列差额 3 1 7 2 11 9 4 5 3 2 10 1 10 8 5 3 0 1 1 B1 B2 B3 B4 行差额
第二步：从行或列差额中选出最大者，选择它所 在行或列中的最小元素。在表4-1中B2列是最大 差额所在列。B2列中最小元素为4，可确定A3 的产品先供应B2的需要。得表4-2：
⑵.位势法
运输问题的约束条件共有m+n个，其中：m 是产地产量的限制；n是销地销量的限制。 其对偶问题也应有m+n个变量，据此： σij=cij －(ui+vj) ,其中前m个计为ui（i=1.2…m）,前n个 计为vj （j=1.2…n） 由单纯形法可知，基变量的σij＝ 0 ∴ cij－(ui+vj) ＝0 因此ui ,vj可以求出。
6
4 9
产销平 衡
13
一 初始基可行解的确定
确定初始基可行解的方法很多，有西北角法， 最小元素法和沃格尔(Vogel)法等，一般希望的 方法是既简便，又尽可能接近最优解。下面分别 予以介绍： 1. 最小元素法 此方法的基本思想是就近供应，即从单位运价 表中最小的运价开始确定供销关系，然后次 小，…，一直到给出初始基可行解为止。以上例 进行讨论得下表：
2013-8-4
8
运输问题数学模型的特点
该系数矩阵中对应于某一变量的系数向量， 其分量中除第i个和第m+j个为1以外，其余的都为零， 在约束条件中，前m个约束条件的含义是：由某一产地 运往各销地的产品数量之和等于该产地的产量；后n 个约束条件的含义是：由各产地运往某一销地的产品 数量之和等于该销地的销量。

2013-8-4 12
例题
例：某食品公司下属的A1、A2、A3 ，3个厂生产方便食品，要运输到B1、 B2、B3、B4 ，4个销售点，数据如下： 求最优运输方案。
单位 产地 销地 运价
B1 B2 B3 B4
3 11 3 10
产量
A1 A2 A3
销量
2013-8-4
7
1 7
3
9 4
6
2 10
5
8 5
6 6
产 量 7 4 9
5
20
说明

由以上可见：沃格尔法同最小元素法除在确定 供求关系的原则上不同外，其余步骤相同。沃 格尔法给出的初始解比用最小元素法给出的初 始解更接近最优解。
本例用沃格尔法给出的初始解就是最优解。

2013-8-4
21
二 最优解的判别
最优性检验就是检查所得到的方案是不是
19
第三步：对表4-3中未划去的元素再分别计算出各行、 各列的最小运费和次小运费的差额，并填入该表的最 右列和最下行，重复第一、二步，直到给出初始解为 止。用此法给出上例的初始解列于表4-4（下表）。
销 地 B1 加工厂 A1 A2 3 A3 销量 3
2013-8-4
B2
B3 5
B4 2 1 3 6
2013-8-4
6
运输问题数学模型的一般形式

若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总 运费最小的调运方案，其数学模型为 m n
m inZ cij xij
i 1 j 1
xij ai xij b j x 0 ij
2013-8-4
16
3 0 0 0 0 0
2013-8-4
3. 沃格尔法
最小元素法的缺点是：为了节省一处的费用， 有时造成在其他处要多花几倍的运费。沃格尔法 考虑到，一产地的产品假如不能按最小运费就近 供应，就考虑次小运费，这就有一个差额。差额 越大，说明不能按最小运费调运时，运费增加越 多。因而对差额最大处，就应当采用最小运费调 运。 沃格尔法的步骤是： 第一步：在原表中分别计算出各行和各列的最 小运费和次小运费的差额，并填入该表的最右列 和最下行，见表4-1
( ai b j )
7
运输问题数学模型的特点


1.运输问题有有限个最优解 2.运输问题约束条件的特点：运输问题的数学模型包含 m×n个变量，(m+n)个约束方程，其系数矩阵的结构比 较松散且特殊。
x11 x12 x1n x21 x22 x2 n xm1 xm 2 xmn u1 1 1 1 u2 1 1 1 um v1 1 1 v2 1 1 vn 1 1 1 1 1 1 1 1 m行 n行
2013-8-4
4
表4-1 产销平衡表
销地 产地
A1 A2 B1 B2
┉ Bn
产量
┆
Am
a1 a2 ┆ am b1 b2 ┈ bn
销量
2013-8-4
5
表4-2 单位运价表
销地 产地 A1 A2 ┆ Am c11 c12 ┈ c1n c21 c22 ┈ c2n ┇ cm1 cm2 ┈ cmn B1 B2 ┉ Bn
仍以上面的例子说明。 第一步：按最小元素法给出表的初始解，然后做 下表：即在对应表的数字格处填入单位运价：
销 地 加工厂 A1 A2 A3
2013-8-4
B1
B2
B3 3 2
B4 10 5
28
1 4
第二步：在上表中增加一行一列，在列中填 入ui，在行中填入vj，得下表：
销 地 加工厂 A1 A2 A3 vj B1 B2 B3 3 2 4 9 3 B4 10 5 10 ui 0 -1 -5
加工厂 A1 A2 A3 销量 5 3 3 6 6 5 2 1 3 6 量 7 4 9
2013-8-4
23

闭回路法计算检验数的经济解释为：在已给出初始解的表中， 可从任一空格出 发，如(A1，B1)，若让A1的产品调运1吨给B1。为了保持产销平衡，就要依次 作调整： 在(A1，B3)处减少1吨，(A2，B3)处增加1吨，(A2，B1)处减少1吨，即 构成了以(A1，B1)空格为起点，其他为数字格的闭回路，如下表虚线所示。在 这表中闭回路各顶点所在格的右上角数字是单位运价
2013-8-4 18
表4-2
销 地 B1 产地 A1 A2 A3 销量
销 地 加工厂 A1 A2 A3 列差额
2013-8-4
B2
B3
B4
3
B1 3 1 7 2
6 6
B2 11 9 4
产 量 7 4 9
5
B3 3 2 10 1
6
B4 10 8 5 3 行差额 0 1 2
同时将运价表中的B2列数字划去。如表4-3所示（表4-3）：
最优方案。检查的方法与单纯形方法中的 原理相同，即计算检验数。由于目标要求 极小，因此，当所有的检验数都大于或等 于零时该调运方案就是最优方案；否则就 不是最优，需要进行调整。下面介绍两种 求检验数的方法：
1.闭回路法； 2.位势法
2013-8-4 22
1 闭回路法
在给出调运方案的计算表上，如上例表，从每一空格出发找一条闭回路。 它是以某空格为起点，用水平或垂直线向前划，当碰到一数字格时可以 转90°后，继续前进，直到回到起始空格为止。闭回路如图(a),(b),(c) 等所示。 销 地 B1 B2 B3 B4 产
2013-8-4 11
第2节 表上作业法
表上作业法是单纯形法在求解运输问题时的一种简化方法， 其实质是单纯形法,但具体计算和术语有所不同，其步骤 可归纳为： (1) 找出初始基可行解：即在(m×n)产销平衡表上用西北角 法或最小元素法、Vogel法给出m+n-1个数字，称为数 字格，它们就是初始基变量的取值。 (2) 求各非基变量的检验数，即在表上计算空格的检验数， 判别是否达到最优解。如已是最优解，则停止计算，否则 转到下一步。 (3) 确定换入变量和换出变量，找出新的基可行解。在表上 用闭回路法调整。 (4) 重复(2)，(3)直到得到最优解为止。
2013-8-4
9
运输问题的对偶问题

运输问题的对偶问题可按照前面写线性规划问题 的对偶问题的方法给出（略）
2013-8-4
10
运输问题的解
运输问题也是一个线性规划问题，其求解时仍然可 以先找一个基可行解，进行解的最优性检验，若 不是最优，就进行迭代，继续检验和调整直到最 优，因此要求每步得到的解都是基可行解，需满 足(1)满足所有约束条件；(2)基变量对应的系数 列向量线性无关；(3)解中非零变量的个数不能大 于m+n-1个，原因是运输问题中虽有m+n个约 束条件，但由于总产量等于总销量，故只有 m+n-1个约束条件是线性独立的；(4)保持基变 量的个数在迭代过程中为m+n-1个。