25
2
8
10
125
11 5 5 300 10
0
1
175
11 12
175
200
200 7
75
100 8
275
-3
2018/8/17
25
Step4 确定格子（1，1）的闭合回路（也即确定了进基变量）；确定该闭
合回路的负号格，得到负号格的最小运量；确定出基变量。
am
销量
b1
b2
…
bn
模型一般形式：
min Z cij xij
i 1 j 1 m n
s.t.
等 式 约 束
xij ai (i 1, m) j 1 m xij b j ( j 1,, n) i 1 xij 0(i 1, m, j 1,, n) m n ai b j
第二章 运输问题
(Transportation

Problem , TP)


运输问题的数学模型(单一物品的调 度运输问题。) 运输问题的求解 产销平衡的运输问题求解 产销不平衡的运输问题求解 应用举例 软件应用
2018/8/17
1
2.1 运输问题的数学模型
例1 现需将三个供应地Kansas City、Omaha、Des Moines的物品
175
275
200
100
300
600
2018/8/17
2
设 xij (i 1,2,3; j 1,2,3) ，从供应地调往需求地的运输量.
min f 6 x11 8 x12 10x13 7 x21 11x22 11x23 4 x31 5 x32 12x33 s.t. x11 x12 x13 150 x21 x22 x23 175 x31 x32 x33 275 x11 x21 x31 200 x x x 100 12 22 32 x13 x23 x33 300 xij 0.(i 1,2,3; j 1,2,3)

求初始基本可行解----伏格尔法
对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价 之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运 费。而最小元素法有可能出现“顾此失彼”的坏事情。
To
From
Kansas City Omaha Des Moines Demand
2018/8/17

Step4 选择出基变量。



寻找闭合回路 选择负号格最小的运量为调整运量 它对应的变量出基，也即它从数字格变为空格

Step5 修正表格，得到一新的基本可行解。转入 step2
2018/8/17
22
例1： Step1： 用最小元素法得到的初始基本可行解开始
To
From Kansas City 7 Omaha Des Moines Demand 200 4 75 5 Chicago 6 St. Louis 25 8 11 Cincinnati 125 175 10 11 12 Supply 150 175 275
Chicago 6 7 4
St. Louis 8
Cincinnati 10 150
Supply 150
175 25 200
11 5
11 12
175
275
4
100 100
150
300
特点：数字格=行数+列数-1(基变量)，其余空格(非基变量)
11
求初始方案-方法3:
单位 销地 运价 产地
伏格尔(Vogel)法
检验数的求法-- --方法1: 闭回路法
可见这调整的方案使运费增加 (+1)×3+(−1)×3+(+1)×2+(− 1)×１=1(元) 这表明若这样调整运量将增加运费。将“1”这个数填入(A1，B1)格， 这就是检验数。按以上所述，可找出所有空格的检验数，见表3-15。
其他空格的检验数：
σ12=11-4+5-10=2
优先满足运输表中西北角(即左上角)上空格的供销需求.
100
25 275 300
特点：数字格=行数+列数-1(基变量)，其余空格(非基变量)
2018/8/17 9

求初始基本可行解---最小元素法
就近供应，即从单位运价最小的地方开始供应（调运）， 然后次小，直到最后供完为止。
To
From
Kansas City
7 4
9
3
6
5
5
6
3
该方案的总运费: (1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元

求最优解

闭合回路法—阅读教科书

位势法
2018/8/17
15
检验数的求法-- --方法1: 闭回路法


闭回路：从空格(非基变量)出发，用水平或垂直线向前划 ，当碰到一数字格时可以转90°后，继续前进，直到回 到起始空格为止。 从该空格出发， 沿闭回路依次加减其运价，所得的值即 为检验数。 注：（1） 每一空格有且仅有一条闭回路；且有偶数个顶点。
12
275
-3
300
vj
Step2
2018/8/17
7
8
10
计算各点位势值
24
Step3 计算各个空格的检验数，判断是否最优？
To
From Kansas City Omaha Des Moines Demand Chicago St. Louis Cincinnati Supply 150
6
-1 -1 7 4
200
100
300
600
2018/8/17
23
To From Kansas City
Chicago
6
St. Louis 25 8
Cincinnati 125 10
Supply 150
ui
0 1
-1
7
11
Omaha
4 Des Moines Demand 200 200 75 100 5
175
11
175
7
3
4
6
6
10
5
5
6
3
9
σ33=10-5+10-3=12
闭回路法计算检验数的经济解释为：在已给出初始解的表3-9中，可从任一空格出发，如(A1， B1)。若让A1的产品调运1吨给B1。为了保持产销平衡，就要依次作调整： 在(A1，B2)处减少1 吨，(A2，B3)处增加1吨，(A1，B3)处 减少1吨，即构成了以(A1，B1)空格为起点，其他为数字 格的闭回路。如表中的虚线所示。在这表中闭回路各顶点所在格的右下角数字是单位运价。
2018/8/17
总供应量 =600 总需要量Fra bibliotek3设 xij 为从产地 Ai 运往销地 Bj 的运输量
销地 产地
A1 A2
B1
x21
B2
x22
…
…
Bn 产量
x1n c1n x2n a1 a2
x11 c11 x12
c21
c12 … c22
…
c2n
…
… Am
…
…
… xmn cmn
xm1 cm1 xm2 cm2 …
m+n-1个是独立的。因此有一个是多余的。 注：上述定理说明：解中非零变量的个数不超过m+n-1.
因此：非基变量的个数为：mn-(m+n-1)
定理2 运输问题一定有最优解。 原因：有可行解xij=aibj/Q. 且有下界.
2.2 运输问题的求解--表上作业法

产销平衡的运输问题求解
针对运输问题的特点，设计了一个方法--表上作业法。它是一 种求解运输问题的特殊方法，其实质是单纯形法。
min Z cij xij
i 1 j 1
m
n
s.t. n xij ai j 1 m xij b j i 1 xij 0
maxW ai ui b j v j
m n i 1 j 1
DLP
s.t. ui v j cij ui , v j 无限制 i 1 m, j 1 n
(cij ui v j ) xij 0
1 B T
C C CB A A C Y A cij cij ui v j
2018/8/17 20
位势法步骤：

Step1 确定初始基本可行解（西北角法，最小元素 法，伏格尔法）。 Step2 检验。


计算各点位势值

i 1
i

j 1
j
2018/8/17
8

求初始基本可行解---西北角法
To From Kansas City Omaha Des Moines Demand 200 100 Chicago 150 50 6 7 4 St. Louis 8 11 5 Cincinnati 10 11 12 Supply 150 175 275 600
σ22=9-2+3-10+5-4=1 σ24=8-10+3-2= -1<0 (说明这个方案不是最优的。) σ31=7-5+10-3+2-1=10
检验数的求法-- --方法2: 对偶变量法（位势法）
用闭回路法求检验数时，需给每一空格（mn-(m+n-1)
个）找一条闭回路。当产销点很多时，这种计算很繁 。下面介绍较为简便的方法——位势法。