按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
示。
表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 Ф
（2）在直线不穿过的所有元素中找出最小元素。
（3）在没有水平线的各行减去此最小元素；有垂直线的各列加上此最小元素；得新的效率
矩阵。
本例中，所求最小元素为1，计算过程为：
。。。
。
。
。。。
。
。0 Ф 7
2 1 0
8 7 0
。
008
。
…1 →
…1
。
。
。。
100
760
。
。
。。
＋1
第四步 回第二步；直到求出最优分配方案。
本例中，对修改后的效率矩阵重复第二步得：
Ф 8
1 0 Ф
7 6 0
。
0
。
。
。
。。
。
。
。。
已经得3个0元素，故得最优分配方案为：
Σ
A1→B1，A2→B2，A3→B3
根据原效率矩阵，3叉车总搬运作业费为：
25＋20＋17=62元
12。2。3 巡回运输问题（旅行商问题）
在单网点配送中，物流网点向所属用户送货，各用户的需求量bi（i=1；2； …；n），货
车载重量为Q，若满足bi
≤
Q
，则该网点只需一辆货车巡回送货即可。显然，在这种情
况下使费用最省的方案就是合理安排货车访问各用户的顺序，使货车的巡回线路的总距离
最短，这也就是旅行商问题。
12…8
例12…3已知5用户间距离如表12…13，其中d（i；j）=∝表示从第i个用户到第j个用户是
没有意义的； 用户1为物流网点所在位置，如果只考虑将每个用户都当作一个出发用户；每
个用户都当作一个到达用户；则对每个出发用户都要选择一个到达用户；而每个到达用户只
能有一个出发用户到达该地；将问题变成了一个分配问题；可用匈牙利法求解。
表12…13 用户间距表
到达
出发
1 2 3 4 5
1 ∝ 1 7 4 3
2 2 ∝ 6 3 43 1 6 ∝ 2 1
4 1 5 4 ∝ 6
5 7 5 4 5 ∝
以例12…13说明求解步骤
第一步 令d（i；i）=∝；不存在通路的也记为∝；得距离阵；通常d（i；j）与d（j；i）不一定
相同；即矩阵不一定对称。
第二步 对距离矩阵用匈牙利法求解；若得到无环路的路线；则就是最优路线；若路线有
环路；就不是最优路线；但所走总距离给出了旅行商问题总距离的下界。
在本例中，匈牙利法求解过程为：
∞
1743
∞
0632
∞
622
。
。
。
。
。
。
…1
0
。
。
。
。
。
。。
。。。。。
。
。
。
。
。
。
。。
。
。
。
。
。
。。
。
。
。
。
。
。。
→
。
。
。
。
。
。。
φ
2
∞
634
0
∞
412
∞
4
2
…2
0
…1
φ
φ
16
∞
21