§ 1．运输问题的典例和数学模型
§ 2．表上作业法
§ 3．产销不平衡的运输问题及其应用
第三章 运输问题
§ 1．运输问题的典例和数学模型
例 1 某食品公司经销主要产品之一是糖果，它下面
设有三个加工厂，每天的糖果生产量分别为：,
, 。该公司把这些糖果分别运往四个地区
的门市部销售，各地区每天的销售量为：,,
, 。已知从每个加工厂到各销售门市部每
吨糖果的运价如下表,
tA 71 ?
tA 42 ? tA 93 ?
tB 31 ? tB 62 ?
tB 53 ? tB 64 ?
单位：元 /t
现在把问题概括一下，在线性规划中我们研究这样
一类运输问题：有某种物资需要调运，这种物资的计量
单位可以是重量、包装单位或其他。已知有 m个地点可以
供应该种物资（以后通称产地，用 表示），
有 n个地点需要该种物资（以后通称销地，用
表示），又知这 m个产地的可供量（以后通称产量）为
（可通写为 ）,n个销地的需要量（以后
通称销量）分别为 （通写为 ）,从第 i个产地
到第 j个销地的单位物资运价为 。
mi,,1 ??
nj,,1 ??
maaa,,,21 ? i
a
nbbb,,,21 ? jb
ijc
产销平衡表
单位运价表
如果用 xij 代表从第 i 个产地调运给第 j 个销地的
物资的单位数量,那么在产销平衡的条件下，使总运
费支出最小，其数学模型如下,
? ?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
?
?
? ?
?
?
? ?
0
,,1
,,1
m i n
1
1
1 1
ij
m
i
iij
i
n
j
ij
m
i
n
j
ijij
x
njbx
miax
xcz
?
?
§ 2．表上作业法
用表上作业法求解运输问题时,首先 给出一个初始方案,其
次 给出一个判别准则,然后 对初始方案进行调整，直到求出最优
解。
由上节例子来具体说明表上作业法的步骤，首先列出产销平
衡表和单位运价表。
一、初始方案的给定
初始方案的给定方法很多，这里介绍两种,
1,最小元素法
基本思想是就近供应，即从单位运价表中最小的运
价处开始确定供销关系，依次类推，直到求出全部方案
第一步,
第二步,
第三步,
第四步,
第五步,
第六步,
这时单位运价表中所有元素已经都划掉了，产销平
衡表中数字就是一个调运方案，这个方案的总费用为,
865310321344613 ????????????
在选定最小元素后，如果该元素所在行的产量与
所在列的销量相同，这时须同时划掉一行一列，并在
该行或列上最小元素对应位置之外添加一个 0。 即下
述例题表格中红色的零，需要选择且仅选择一个保留。
2,Vogel 法
用最小元素法给定初始方案只从局部观点考虑就近供
应，可能造成总体的不合理。
Vogel 法的步骤,
1,从运价表上分别找出每行与每列的最小的两个元
素之差；
2,从差值最大的行或列中找到最小运价确定供需关
系和供应数量；
3,当产地或削地中有一方数量上供应完毕或得到满
足时，划去运价表中对应的行或列；
4,重复步骤 1,2,3，直到划去所有元素为止。
二、最优性检验与方案的调整
1.闭回路法
闭回路是指调运方案中由一个空格，和有数字的格，
用水平和竖直连线包围成的封闭回路。
利用前面最小元素法得到的初始方案为例,
计算 x11的检验数
1)1(1)1(2)1(3)1(3 ????????????
将上述检验数填入检验数表中,
计算 x31 的检验数
10)1(5)1(10)1(3)1(2)1(1)1(7 ??????????????????
计算 x12 的检验数
以此类推，算出所有检验数,
如果检验数表中，所有数字大于等于零，则此时为最
优解，如果有小于零的，在该格所对应的调运方案表中按
闭回路进行调整。
闭回路调整,
由此得新的调运方案,
计算得该方案运费为 85元。 需要对该方案每一空格
重新求出检验数，判断是否最优，如果不是最优，需继续
调整，计算后可知该方案为最优。
2.位势法
仍以上例中最小元素法确定的初始调运方案为例。
第一步,将调运方案中有数字的格内数字改
换为单位运价表中对应格的运价。即由下述两
表,
得,
第二步,在表格下方和右方增加一行和一列，并填
上一些数字，使得格中数字正好等于它所在行与所在列数
字之和。
依次计算填入各数,
最终得,
将 vi 与 uj 相加求出空格处数字,
用单位运价表中数字减掉上表中对应数字，得,
该表即检验数表，与闭回路法求出的检验数表相同。
当所得检验数不全非负的时候，仍然需要对方案进行
调整，调整方法与前面提到的相同。
§ 3,产销不平衡的运输
问题及其应用
例 2 设有 A1,A2,A3三个产地生产某种物资，其产
量分别为 7t,5t,7t, B1,B2,B3,B4 四个销地需要该种
物资，销量分别为 2t,3t,4t,6t,又知各产销地之间的
单位运价如下表，试决定总运费最少的调运方案。
解,产地总产量为 19t,销地总销量为 15t,所以这
是一个产大于销的运输问题。此时我们假想一个销地，
这个销地的销量等于前面的总产量与总销量的差 4t,我
们也可视其为库存量，这样使得产销达到平衡。这时对
它的运费为 0，现在我们建立与之对应的产销平衡表和单
位运价表。
单 位 运 价 表
产 销 平 衡 表
利用表上作业法求解得,
例 3 设有三个化肥厂供应四个地区的农用化肥，假
定等量的化肥在这些地区使用效果相同，已知各化肥厂
年产量，各地区年需要量及从各化肥厂到各地区单位化
肥的运价表如下，试决定使总的运费最节省的化肥调拨
方案。
解,这是一个产销不平衡的运输问题，总产量为
160万 t，四个地区 最低需求 为 110万 t,最高需求为无限。
当其它地区都是满足最低需求时，第 Ⅳ 地区每年最多能
分配到 60万 t,这样 最高需求 就是 210万 t，大于产量。
产 销 平 衡 表
为建立产销平衡表，在表中增加一假想化肥厂 D,
其年产量为 50万 t 。并把各地区的最低需求和额外需求
区分开来，建立产销平衡表。
当一个产地的产量不能运往某一个销地的时候，认为
运价为 M(表示任意大正数 )。额外需求部分的销量，由于
是否满足都可以，所以假想厂运往这些销地的运价定为 0。
单 位 运 价 表
利用表上作业法求解得,
例 4 某食品公司经销主要产品之一是糖果，它下面
设有三个加工厂，每天的糖果生产量分别为：,
, 。该公司把这些糖果分别运往四个地区
的门市部销售，各地区每天的销售量为：,,
, 。
tA 71 ?
tA 42 ? tA 93 ?
tB 31 ? tB 62 ?
tB 53 ? tB 64 ? 如果假定,
（ 1）每个工厂生产的糖果不一定直接发运到销售点，
可以将其中几个产地的糖果集中起来一起运。
（ 2）运往各销地的糖果可以先运给其中几个销地，
再转运给其他销地。
（ 3）除产地、销地外，中间还可以有几个转运站，
在产地之间、销地之间或产地与销地之间转运。
已知各产地、销地、中间转运站之间的单位运价，
求如何在各地之间进行调运，使总的运费最小。
产地、销地、中间转运站间运价表,
首先通过该表建立单位运价表，由于各个地点间糖
果可以相互运送，因此都可以作为产地，也都可以作为
销地来考虑，将产地和销地都扩大为 11个，不能够直接
运送到的地点间运价设为 M,运送到本地的运价设为 0。
单 位 运 价 表
下面考虑如何建立产销平衡表,
1,中间转运站产、销量的确定
由于中间转运站所有的糖果都不保留，所以我们认
为产量等于销量，同时因为在运费最小时不可能出现一
批糖果在两地见来回倒运的现象，并且已知
总产量 =总销量 =20t,
所以每个转运站的转运数不能超过 20t,因此可以规定产
量和销量都是 20t 。而实际转运量是 20t减掉运给自身的运
量。
2,原来产地和销地的产、销量调整
由于原来的产地和销地也都起到转运站的作用，所
以同样需要在原来的产量和销量上加 20t 。
建立产销平衡表,
最后利用表上作业法求解。
§ 2．表上作业法
§ 3．产销不平衡的运输问题及其应用
第三章 运输问题
§ 1．运输问题的典例和数学模型
例 1 某食品公司经销主要产品之一是糖果，它下面
设有三个加工厂，每天的糖果生产量分别为：,
, 。该公司把这些糖果分别运往四个地区
的门市部销售，各地区每天的销售量为：,,
, 。已知从每个加工厂到各销售门市部每
吨糖果的运价如下表,
tA 71 ?
tA 42 ? tA 93 ?
tB 31 ? tB 62 ?
tB 53 ? tB 64 ?
单位：元 /t
现在把问题概括一下，在线性规划中我们研究这样
一类运输问题：有某种物资需要调运，这种物资的计量
单位可以是重量、包装单位或其他。已知有 m个地点可以
供应该种物资（以后通称产地，用 表示），
有 n个地点需要该种物资（以后通称销地，用
表示），又知这 m个产地的可供量（以后通称产量）为
（可通写为 ）,n个销地的需要量（以后
通称销量）分别为 （通写为 ）,从第 i个产地
到第 j个销地的单位物资运价为 。
mi,,1 ??
nj,,1 ??
maaa,,,21 ? i
a
nbbb,,,21 ? jb
ijc
产销平衡表
单位运价表
如果用 xij 代表从第 i 个产地调运给第 j 个销地的
物资的单位数量,那么在产销平衡的条件下，使总运
费支出最小，其数学模型如下,
? ?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
?
?
? ?
?
?
? ?
0
,,1
,,1
m i n
1
1
1 1
ij
m
i
iij
i
n
j
ij
m
i
n
j
ijij
x
njbx
miax
xcz
?
?
§ 2．表上作业法
用表上作业法求解运输问题时,首先 给出一个初始方案,其
次 给出一个判别准则,然后 对初始方案进行调整，直到求出最优
解。
由上节例子来具体说明表上作业法的步骤，首先列出产销平
衡表和单位运价表。
一、初始方案的给定
初始方案的给定方法很多，这里介绍两种,
1,最小元素法
基本思想是就近供应，即从单位运价表中最小的运
价处开始确定供销关系，依次类推，直到求出全部方案
第一步,
第二步,
第三步,
第四步,
第五步,
第六步,
这时单位运价表中所有元素已经都划掉了，产销平
衡表中数字就是一个调运方案，这个方案的总费用为,
865310321344613 ????????????
在选定最小元素后，如果该元素所在行的产量与
所在列的销量相同，这时须同时划掉一行一列，并在
该行或列上最小元素对应位置之外添加一个 0。 即下
述例题表格中红色的零，需要选择且仅选择一个保留。
2,Vogel 法
用最小元素法给定初始方案只从局部观点考虑就近供
应，可能造成总体的不合理。
Vogel 法的步骤,
1,从运价表上分别找出每行与每列的最小的两个元
素之差；
2,从差值最大的行或列中找到最小运价确定供需关
系和供应数量；
3,当产地或削地中有一方数量上供应完毕或得到满
足时，划去运价表中对应的行或列；
4,重复步骤 1,2,3，直到划去所有元素为止。
二、最优性检验与方案的调整
1.闭回路法
闭回路是指调运方案中由一个空格，和有数字的格，
用水平和竖直连线包围成的封闭回路。
利用前面最小元素法得到的初始方案为例,
计算 x11的检验数
1)1(1)1(2)1(3)1(3 ????????????
将上述检验数填入检验数表中,
计算 x31 的检验数
10)1(5)1(10)1(3)1(2)1(1)1(7 ??????????????????
计算 x12 的检验数
以此类推，算出所有检验数,
如果检验数表中，所有数字大于等于零，则此时为最
优解，如果有小于零的，在该格所对应的调运方案表中按
闭回路进行调整。
闭回路调整,
由此得新的调运方案,
计算得该方案运费为 85元。 需要对该方案每一空格
重新求出检验数，判断是否最优，如果不是最优，需继续
调整，计算后可知该方案为最优。
2.位势法
仍以上例中最小元素法确定的初始调运方案为例。
第一步,将调运方案中有数字的格内数字改
换为单位运价表中对应格的运价。即由下述两
表,
得,
第二步,在表格下方和右方增加一行和一列，并填
上一些数字，使得格中数字正好等于它所在行与所在列数
字之和。
依次计算填入各数,
最终得,
将 vi 与 uj 相加求出空格处数字,
用单位运价表中数字减掉上表中对应数字，得,
该表即检验数表，与闭回路法求出的检验数表相同。
当所得检验数不全非负的时候，仍然需要对方案进行
调整，调整方法与前面提到的相同。
§ 3,产销不平衡的运输
问题及其应用
例 2 设有 A1,A2,A3三个产地生产某种物资，其产
量分别为 7t,5t,7t, B1,B2,B3,B4 四个销地需要该种
物资，销量分别为 2t,3t,4t,6t,又知各产销地之间的
单位运价如下表，试决定总运费最少的调运方案。
解,产地总产量为 19t,销地总销量为 15t,所以这
是一个产大于销的运输问题。此时我们假想一个销地，
这个销地的销量等于前面的总产量与总销量的差 4t,我
们也可视其为库存量，这样使得产销达到平衡。这时对
它的运费为 0，现在我们建立与之对应的产销平衡表和单
位运价表。
单 位 运 价 表
产 销 平 衡 表
利用表上作业法求解得,
例 3 设有三个化肥厂供应四个地区的农用化肥，假
定等量的化肥在这些地区使用效果相同，已知各化肥厂
年产量，各地区年需要量及从各化肥厂到各地区单位化
肥的运价表如下，试决定使总的运费最节省的化肥调拨
方案。
解,这是一个产销不平衡的运输问题，总产量为
160万 t，四个地区 最低需求 为 110万 t,最高需求为无限。
当其它地区都是满足最低需求时，第 Ⅳ 地区每年最多能
分配到 60万 t,这样 最高需求 就是 210万 t，大于产量。
产 销 平 衡 表
为建立产销平衡表，在表中增加一假想化肥厂 D,
其年产量为 50万 t 。并把各地区的最低需求和额外需求
区分开来，建立产销平衡表。
当一个产地的产量不能运往某一个销地的时候，认为
运价为 M(表示任意大正数 )。额外需求部分的销量，由于
是否满足都可以，所以假想厂运往这些销地的运价定为 0。
单 位 运 价 表
利用表上作业法求解得,
例 4 某食品公司经销主要产品之一是糖果，它下面
设有三个加工厂，每天的糖果生产量分别为：,
, 。该公司把这些糖果分别运往四个地区
的门市部销售，各地区每天的销售量为：,,
, 。
tA 71 ?
tA 42 ? tA 93 ?
tB 31 ? tB 62 ?
tB 53 ? tB 64 ? 如果假定,
（ 1）每个工厂生产的糖果不一定直接发运到销售点，
可以将其中几个产地的糖果集中起来一起运。
（ 2）运往各销地的糖果可以先运给其中几个销地，
再转运给其他销地。
（ 3）除产地、销地外，中间还可以有几个转运站，
在产地之间、销地之间或产地与销地之间转运。
已知各产地、销地、中间转运站之间的单位运价，
求如何在各地之间进行调运，使总的运费最小。
产地、销地、中间转运站间运价表,
首先通过该表建立单位运价表，由于各个地点间糖
果可以相互运送，因此都可以作为产地，也都可以作为
销地来考虑，将产地和销地都扩大为 11个，不能够直接
运送到的地点间运价设为 M,运送到本地的运价设为 0。
单 位 运 价 表
下面考虑如何建立产销平衡表,
1,中间转运站产、销量的确定
由于中间转运站所有的糖果都不保留，所以我们认
为产量等于销量，同时因为在运费最小时不可能出现一
批糖果在两地见来回倒运的现象，并且已知
总产量 =总销量 =20t,
所以每个转运站的转运数不能超过 20t,因此可以规定产
量和销量都是 20t 。而实际转运量是 20t减掉运给自身的运
量。
2,原来产地和销地的产、销量调整
由于原来的产地和销地也都起到转运站的作用，所
以同样需要在原来的产量和销量上加 20t 。
建立产销平衡表,
最后利用表上作业法求解。
