现代物流学-第54章

按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！



Σ（m）　xij　=　bj　
（　j　=　1；。。。；　n）　

i=1　

Σ（n）　bj　
=Σ（m）　ai　


j=1　i=1　

xij　
≥　
0（i　
=　
1；。。。；　m；　j　
=　
1；。。。；　n）　

12。1。1。2　表上作业法求解　
12…1　



上述模型是一种线性规划模型，自然可以用单纯形法求解，但是根据其特殊结构而建
立的表上作业法比起用单纯形法要简单得多。其思路为：由初始运输方案开始，通过检
验、改进，最后获得最优运输方案。　
下面结合例12…1具体说明表上作业法的步骤和方法：　

例12…1设有两个煤矿供应三个城市用煤，煤矿A　1和A2的日产量分别为a　1=200吨；a　2=250
吨。三城市（B　1；B2；B3）的日销量分别为b　1=100吨，b　2=150吨，b　3=200吨。假定每吨货物的
社会运输费与出行公里线性有关，取cij代表煤矿I至城市j的最短距离。已知c　11=90公里，　
c12=70公里，c　13=100公里，c　21=80公里，c　22=65　公里，c　23=80公里。问如何安排运输使运输
费用最省？　

解：设xij为煤矿I运往j的煤量，根据每个煤矿产煤总量和城市的用煤总量，　
xij（I=1；2；j=1；2；3）必须满足下列条件：　

x11＋x12＋x13=200　

x21＋x22＋x23=250　

x11＋x21=100　

x12＋x22=150　

x13＋x23=200　

目标函数为：minz=90x11＋70x12＋100x13＋80x21＋65x22＋80x23

1。列运输平衡表　
列表时要求表内供销平衡，并将运费标入表内空格，如下表12…1所示：　
表　12…1　运输平衡表　


B1　B2　B3供应量　
A1　X11　X12　X13　200　
A2　X21　X22　X23　250　
需求量　100　150　200　450　
需　
供　
90　70　100　
80　65　80　
2。建立初始调运方案　
鉴于最好运输方案是使总运费最小，采用最小元素法，即在平衡表中挑取运价最小或
较小的供需点格子尽量优先分配的调运方法。一行（或一列）满足了，就划去一行（或一
列），如果运费相等时可任选一个，直到全部分配完为止。分配时注意一个问题，即分配
数字的格数要为“行数＋列数…1”，若分配完时出现规定数时，应在适当的空格补零，这个
补零的格子在数量上是零，但要当成非零数字格对待。如表12…2所示：　

　表　12…2　初始调运方案表　

B1　B2　B3供应量　
A1　0　200　200　
需　
供　
90　70　100　
80　65　80　
12…2　



A2　100　150　250　
需求量　100　150　200　450　

表12…2先从A　2；B2（c22最小）开始，确定c22=150；划去余下的B　2　列，然后确定x21=100（c21
为剩下方格中最小运价），划去余下的B　1列，A2的供应量也同时得到满足，故此时余下的A　2
也被划去，最后确定x12为200，形成初始调运方案。　

3。方案的检验和调整　
（1）闭回路
从调运方案的任意空格出发，沿水平方向或垂直方向前进，而遇到填有数字的方格，
折转90度前进，当然可以直接穿过数字格和空格，但只能遇有数字的格才能折转，只能水
平、垂直方向前进，不能对角线移动，这样经过多次折转直到回到原来出发的空格，形成
一条闭回路。　

（2）位势法检验　
①由方案表列出检验表。表中行列数与方案表一样，运价在每个格的右上角，原方案
表中的空格填写检验数，原方案表中的数字格为检验表中的空格，原方案表中的供应量、
需求量格填写行与列的位势，称为行或列位势格。　
②求位势。记第i行位势为u　i　，第j列位势为vj，可任选一个位势格填任意数，通常取0
作为该格的位势。其它位势格的位势由下列法则求出：每个空格右上角的运价c　ij等于该行
位势与该列位势之和，即cij=ui＋vj。　例如在表12…2中，任取左下端的位势格为0，由上述法
则求出其它4个位势格的位势；如表12…3。　
表12…3　位势表　

B1　B2　B3　Vj　
A1　0　200　90　
A2　100　150　80　
Ui　0　…15　10　
需　
供　
90　70　100　
80　65　80　
③求检验数。若空格位于第i行第j列，则其检验数σij按下式求出：　
σ=　
c　
。　
u　
。　
v

ij　
ijij　


例如由表12…3可求出1行2列空格的检验数σ　12=70＋15…90=…5，其它如检验数表12…4所
示。　
表12…4　检验数表　

B1　B2　B3　vj　
A1　…5　90　
供　
需　
90　70　100　
80　65　80　
12…3　



A2　…10　80　
ui　0　…15　10　

由表12…4知，有负的检验数存在，这表明12…2所给的运输方案不是最优的，需要进行
调整。　

（3）调整运输方案。当运输表对应的检验表中有负的检验数时，需在运输方案表上对
运输方案进行调整。　
①确定闭回路。在需调整的运输方案表上选取对应的检验数为负的格作为调整格，　
若有两个以上格的检验数为负，选其中检验数绝对值最大的格为检验格，从检验格出发在
运输方案表上作闭回路。　
例如在表12…4中，A2B3格的检验数是…10，为绝对值最大的负检验格，故选取此格为调
整格，并用虚线在运输方案表上作闭回路，如表　12…5所示。　
表12…5　闭回路表　

B1　B2　B3供应量需　
A1　0　200　
200　
A2　100　150　
250　
需求量　100　150　200　450　
90　
供　
70　100　
80　65　80　
②在闭回路上作运输量最大的调整；得出新的运输方案。从空格开始，沿闭回路在各偶
数格中挑选运量最小的作为调整量，调整闭回路各点的运输量。　
例如在表12…5中，闭回路上偶数格最小运输量为min（200；100）=100；调整闭回路各点运
输量，得表12…6。　
表12…6　新运输方案1表　

B1　B2　B3供应量　
A1　100　100　
200　
A2　150　100　
250　
需求量　100　150　200　450　
需　
供　
90　70　100　
80　65　80　
（4）返回（2），对新运输方案进行位势法检验。若无负检验数，则此方案为最优方
案，否则继续进行调整。　
例如对于表12…6，得检验表12…7。　
12…4　



表12…7　新运输方案1检验表　

B1　B2　B3　vj　
A1　…15　90
供　
需　
90　70　100　
A2　
10　
70　
ui　0　…5　10　
80　65　80　
表12…7中有负得检验数，继续进行调整，得新运输方案表12…8。　
表12…8　新运输方案2表　

B1　B2　B3
供应量　
A1　100　100　200　
A2　50　200　250　
需求量　100　150　200　450　
对表12…8进行检验，得检验表12…9　
表12…9　新运输方案2检验表　
需　
供　
90　70　100　
80　65　80　
B1　B2　B3　Vj　
A1　15　90　
A2　…5　85　
ui　0　…20　…5　
表中有负检验数，继续进行调整，得新运输方案表12…10　
表12…10　新运输方案3表　
供　
需　
90　70　100　
80　65　80　
B1　B2　B3
供应量　
A1　50　150　200　
90　70　100　
80　65　80　
需　
供　
12…5　



A2　50　200　250
需求量　100　150　200　450　

对此运输方案进行检验，得检验表12…11　
表12…11　新运输方案3检验表　

B1　B2　B3　Vj
供　
需　
A1　10　90　
A2　5　80　
Ui　0　…20　0　
90　70　100　
80　65　80　
从表12…11中可以看到，检验数全是正数，因此表12…10中的运输方案为最优方案，即
应确定A1向B1、B2调运煤数量分别为50、150；A2向B1、B3调运数量分别为50、200。　

二。产销不平衡时的运输问题　
（一）产大于销的运输问题　

对于产量大于销量即Σ（n）　bj　
Σ（m）　a　
的运输问题，必然有一些销地不能得到满足，发生

i　
j=1　i=1　

缺货，此时引入虚拟供应点，并设其相应运价为0。这样，就可以用产销平衡的表上作业法
求解销大于产的运输问题。　

12。2　分配运输问题
在运输过程中经常遇到这样的问题，需完成几条运输线路的任务，恰好有几个运输单
位可承担这些任务。由于每个单位的情况各不相同，其完成各项任务的效率（或效益）也
不同，如何安排这些运输单位去完成任务，使效率（或效益）也最高，这一类问题统称为
分配问题。　

12。1。1　模型分析　
例12…2某材料厂有B　1、B2、B3三台叉车可分配给A　1、A2、A3三个仓库进行搬运作业，其
中任一叉车都可以在任一仓库中进行搬运工作，只是搬运作业费不同，各台叉车相应作业
费Cij如表12…12所示，要求一台叉车只分配给一个仓库使用，试求搬运作业费用最小的分配
方案。　

12…6　



表12…12　效率矩阵表　

叉车　
cij
仓库　
B1　B2　B3　
A1　25　15　22　
A2　31　20　19　
A3　35　24　17　

对应于每个分配问题，　都有类似于表　12…12　的数字表，称之为效率矩阵，其元素　c　ij＞0（i；j=1；2；。。。；n）表示分配第i个单位去完成第j项任务时的效率（或时间、成本等）。根
据问题引入变量xij，并按以下规定取值：　

1第i个单位被分配去完成第j项任务　
xij　
0　第i个单位不去完成第j项任务其中i=1；2；。。。；n；　j=1；2；。。。；n


当问题要求极小时；有数学模型：　

min　z　
=Σ（n）　Σ（n）　

cij　
xij

i==j

11　

st。　

。。
。　


=

。　
。。。
。


n　


xij　
1；j　
1；2；。。。；　n　


in　
1　（12。2）　

xij　
1；　i　
1；2；。。。；　n　


=
=　
j　
1　

=　


=　


=　


Σ=　
Σ

　上述模型中；约束条件1表明第j项任务只能由1个单位去完成；约束条件2则说明第i个单
位只能完成1项任务。对于求极大问题时，可转化cij为c’ij；即令c’ij=cij…max｛cij｝；将原maxz=　
ΣΣcijxij转化为minz’=　c’ijxij求解。　

12。2。2　匈牙利算法
可以看到，分配问题是0…1规划问题，对于几个单位分配几项任务的分配问题，总共有
n！种可能的分配方案，若用隐枚举法求解，当n较大时，计算量是很大的。由匈牙利数学
家考尼格给出的匈牙利算法，是一种求解分配问题最简单、最有效的方法。　
匈牙利法的主要依据是，在效率矩阵的任何行或列中，加上或减去同一常数，并不改
变最优分配。利用此性质，可使原效率矩阵变换为含有很多0元素的新效率矩阵，找出在其
中的位于不同行、不同列的n个独立的0元素，将其取值为1，其它元素取值为0，即得原分
配问题的最优解。　
以下通过求解例12…2的分配问题，介绍匈牙利算法　
已知其效率矩阵为：　


。

2515　22

。　


。　
。　
。　
。。

。　
。　
。。

35　

　第一步　变换效率矩阵，使其每一行和每一列都至少有一个0元素，具体通过减去每行、每
列的最小元素，如下：　

10　
18　

。　
。　
。。


31　20　19　


24　17　


07　


007


。
。


。


。

。　
。　
。　
。。

2515　22　…15　
35　

。　
。　
。。


。　
。　
。。


。　
。　
。。


。　
。　
。。


12　1　0　


210


31　20　19　


　…19　→


　→　


70　


870


24　17　


…17　


。10　


12…7　



第二步　试求最优分配方案。　

（1）从1行开始，依次检查各行，找出只有一个未标记的0元素的行，并将该元素用
“0”表示，与该元素同行同列的其它0元素用“Ф”表示，其含义为，0元素对应的任

务仅由所对应的单位去完成，此单位不再去完成其它任务，这项任务也不再由其它单位

完成。0和Ф称为已标记的0元素。重复此过程，直到每一行没有一个尚未标记的0元

素，或至少有两个未标记的0元素。

（2）依次检查各列，找出只有一个未标记的0元素的列，将该元素标以0，并与该元
素同行同列的其它未标记0元素标以Ф，直到每列没有一个尚未标记的0元素，或至少有
两个未标记的0元素。　

（3）重复上述步骤，直到效率矩阵中没有未标记的0元素为止，若n行n列效率矩阵中
恰有n个0元素，就得到最优分配方案，否则，仍需进行效率矩阵调整，本例中为：　

。　
。　
。　
。。


0　Ф　7　
2　1　0　
8　7　Ф

。　
。　
。　
。。　


第三步　继续调整效率矩阵　

（1）对每个0元素划一条水平线或垂直线，使这些线覆盖所有0元素。直线个数与0元
素个数相同。本例中为：　

。


。　
。　
。。


。。。
。
。0　Ф　7　
2　1　0　
8　7　Ф