运输问题的求解方法
——表上作业法
产销平衡表与单位运价表
表上作业法
一、产销平衡表与单位运价表
运输问题还可用产销平衡表与单位运价表进行描述。
假设某种物资有m个生产地点Ai（i=1，2，…，m），其产量（供应量）分别为ai（i=1，2，…，m），有n个销地Bj（j=1，2，…，n），其销量（需求量）分别为bj（j=1，2，…，n）。从Ai到Bj运输单位物资的运价（单价）为Cij。将这些数据汇总可以得到产销平衡表和单位运价表5.3.1。
表5.3.1 产销平衡表与单位运价表
二、表上作业法
运输这一类特殊问题可用更加简便的求解方法———表上作业法求解，实质仍是单纯形法，步骤如下：
（1）确定初始调运方案，即找出初始基可行解,在产销平衡表上给出m+n-1个数字格。
（2）求非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解：是否存在负的检验数？如果存在负的检验数，则初始调运方案不是最优方案；如果所有检验数都非负，则初始调运方案已经是最优方案了。如果已经得到最优调运方案，则停止计算，否则转入下一步。
（3）确定换入变量和换出变量，找出新的调运方案（新的基可行解），即在表上用闭回路法进行调整。
(4）重复（1）～（2），直到求出最优解为止。
（一）确定初始可行基的方法
最小元素法
从单位运价表中最小的运价开始确定供销关系，然后考虑运价次小的，一直到给出初始基可行解为止。
伏格尔法
采用最小元素法可能造成其他处的更多浪费，伏格尔法考虑最小运费与次小运费之间的差额，差额越大，就按次小运费调运。 （二）最优解的判别
计算非基变量（空格）的检验数,当所有的检验数 时，为最优解。
求空格检验数的方法有：
闭回路法
以某一空格为起点找一条闭回路，用水平或垂直线向前划，每碰到一数字格转900后，继续前进，直到回到起始空格为止。
表上作业法和图上作业法
表上作业法
定义；表上作业法是指用列表的方法求解线性规划问题中运输模型的计算方法。是线性规划一种求解方法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭合回路法、位势法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。
表上作业法: 建立在运输费用矩阵的求解运输问题的方法。
表上作业法求解运输问题的思想和单纯形法完全类似：
确定一个初始基本可行解 —— 根据最优性判别准则来检查这个基本可行解是不是最优的？
如果是，则计算结束；
如果不是，则进行换基。
—— 直至求出最优解为止
图上作业法
定义；图上作业法是将配送运输量任务反应在交通图上，通过对交通图初始调运方案的调整，求出最优配送车辆运行调度方法。运用这种方法时，要求交通图上没有货物对流现象，以运行最短路、最低运费或最高行程利用率为优化目标。
返程或起程空驶的解决方案或措施是:
1) 顺路运输.发布返程或起程空驶信息,寻找搭载.
2) 加收运费; 对单程运输加收运费.
3) 建立联系; 与相关单位或同业建立互通有无的合作关系,联合行动
图上作业法训练
设有A1、A2、A3三个配送点分别有化肥40t、30t、30t，需送往四个客户点B1、B2、B3、B4，而且已知各配送点和客户点的地理位置及它们之间的距离，可据此制出相应的交通调运图，并比较最终方案与初始方案的优劣。 (假设断开的是A3—B3)
第一步：判断
全圈长=40+40+50+60+20=210
半圈长=210÷2=105
里圈长=40+40+50+60=190
外圈长=0
综上所述，由于里圈长>半圈长，不是最优方案，需调整。
(20)
(50) (40) A330 B110 A140
B440 B330
B220
A230 （40） （30）
(60)
(50) ×
× ×
×
A330 B110 A140
B440 B330
B220
A230 ×
× ×
× 30 40
60
50 20
20 第二步：调整
全圈长=40+40+50+60+20=210
半圈长=210÷2=105
里圈长=40+40+60=140
外圈长=20
综上所述，由于里圈长>半圈长，不是最优方案，需再调整。
第三步：再调整
全圈长=40+40+50+60+20=210
半圈长=210÷2=105
里圈长=40+60=100
外圈长=70
综上所诉，外圈长和里圈长都小于半圈长，为最优方案。 A330 B110 A140
B440 B330
B220
A230 ×
× ×
× 20 10
40
20 40
30
A330 B110 A140
B440 B330
B220
A230 ×
× ×
× 30
30
20 40
20
10
第
卷
第
期
!∀
年#
月数
学学报
∃%
&∋(&)
&(∗
+)&(,∋&−,∃,∋&.%/
122
!∀
图上
作业法
的改
进3
管梅谷
4
山
东师范学
院5
编者按6
这篇文
章利
用表上作
业法
来歌明图
上作业法
的被检查圈
可以大大减少,
实际上,
图上作
业法与
表上作
业法是等价的作者所获得的桔
输也可由图
上作业法的性盾道接征明
和本文相
反,我们也
可叔一切从图
上作业法出
发,
然后再弓/出
表上作
业法的性盾来
一般歌
来从
图形出发
靓明
教筒,
因
为有蛟多的几何
直观性
号
前言
图上作
业法70 〕已
在实践中被征明是一
种好方
法但屯也有一个
缺
点就是
在圈数
较
多时,
很难
运用
例如下面
图
中4
图中每
个弧的
长度都假定为
公里
5这样的图形是不
难
遇到的,
但是这个图中的圈
实在太多
了估豁起来至少有
几
千个,
在这种情
况下要检
查一
个流向图
是否最优用
图上
作
业法的
原
理来检查每个
圈的
内外圈
流向
之长是否超
过圈长的
一半实
际上是行不通的
为了
解决这个
矛盾本
文提
出了一种改进了的方法这种
方法的
最
大特点
在于
指出了检查一
个流向图是否
最优不必
检查每一个圈,
而只要检
查少数几个圈
就
够了
以下将看到
要检查的圈
数等于图中的“
小圈”4
即内部不含有弧的圈5的个数
次只需检查#
个圈就够了##
#
8
##
图
例如在图
的情
况下
每
9#
基本流向图
改进了的方
法中
最重要的
概念是
基本流向图
首
先声明
一下我
们把“
图”理解成平
面上的一个
速通修
性图所胡
擒性图是指满足
下述条件的有限
个点尸:;<
/,
尸#,
…,
尸
打与
有限
个弧=:;/
#
…/>?
的
集合6
/5每一
八
〔=
都有两个不同的
端点
且都
属于<
#5
尸的
每一
对<
,与<,4≅
手≅5最
多只
能
作为一个=
的
弧的
端点
5
任一尸‘
〔Α
不能
作为
任一人〔=
的内点
斗5若
=
的
两
个弧八与
肠有共同
点则必为
某一尸的
点
若一个
袋性图还满足
95就称为
速通的
的对于尸的
任一对
点尸,与尸≅
一定存在一系
列<
的点6
尸、:
Α≅
。尸≅
…Α≅
‘二尸,
使得每一对
Α≅,尸侠十4
反:
…才
一5都是=
