《运筹学》第三章 运输问题资料讲解

A2
B1
B2
B3
B4
产量
6 4 2 1
5
3
4
3
4 7
1
5 3
4 6
A3 销量 2
7
3
4
6
3
5
4
8
3 13
x23检验数为 7-3+4-5=3
销地 产地 A1
A2
B1
B2
B3
B4
产量
6 4 2 1
5
3
4
3
4 7
1
5 3
4 6
A3 销量 2
7
3
4
6
3
5
4
8
3 13
x31检验数为 7-4+4-5=1
销地 产地 A1
销地 产地 A1
A2
B1
B2
B3
B4
产量
6
5 3
3 1
4
4
4
2 1
4 6
3
4 3
7
3
5
6
A3
销量 2
7
5
4
8
3 13
σ11=-3, σ12=-2,σ23=-4, σ31=-1,σ33=1, σ34=-1
销地 产地 A1
A2
B1
B2
B3
B4
产量
6
5 0
3 4
4
4
4
2 4
4 6
3
4 3
7
0
5
6
A3
销量 2
2、位势法 当运输问题变量的格数较多时，用闭 回路法计算检验数比较麻烦，而位势法比 较简便。 对于运输问题 minf=CX AX=b X≥0 设B为其一个可行基，则xij的检验数为 σ ij=CBB-1Pij-Cij

产销平衡运输问题的数学模型可表示如下：
§1运 输 问 题 及 其 数 学 模 型
二、运输问题数学模型的特点： 运输问题一定有最优解；基变量的个数=m+n-1 运输问题约束条件的系数矩阵：
x1m
x2m
xm1
xmm
x11
x12
…
x21
x22
…
xm2
…
…
m行
n行
§1运 输 问 题 及 其 数 学 模 型
解 的 最 优 性 检 验
运输问题及其数学模型
用表上作业法求解运输问题
运输问题的进一步讨论
应用问题举例
本章内容
3运输问题进一步讨论
01.
产销不平衡的运输问题 有转运的运输问题
02.
1.当产大于销时，即 产销不平衡问题 平衡后的数学模型为： 加入假想销地（假想仓库），销量为 ，由于实际并不运 送，它们的运费为 = 0；
解 的 最 优 性 检 验
解 的 最 优 性 检 验
销地产地
B1
B2
B3
B4
产量
ui
A1
16
u1(1)
A2
10
u2(0)
A3
22
u3(-4)
销量
8
14
12
14
48
vj
v1(2)
v2(9)
v3(3)
v4(10)
4
2
8
12
5
4
10
11
3
9
6
11
表3-9
1.增加一位势列和位势行并计算位势
其中
8
10
2
6
8
产量
A1

【定理 3】m+n － 1 个变量组构成基变量的充要条件 是它不包含任何闭回路。
定理 3 告诉了一个求基变量的简单方法，同时 也可以判断一组变量是否可以作为某个运输问题的 基变量。这种方法是直接在运价表中进行的，不需 要在系数矩阵 A 中去寻找，从而给运输问题求初始 基可行解带来极大的方便。
例 3-3 ： m=3,n=4 ，在运价表 Cij 的格子的右上 方填上相应的xij，如表3-5所示。
表3－4 B1 B2 x12 B3
A1
A2 A3 A4
x11
x11 , x41 , x43 , x33 , x32 , x12
例如变量组 A x21 , x22 , x33 , x31 , x11 , x12 ;
x32
x33 x43
x41
A不能组成一条闭回路，但A中包含有闭回路
B的变量数是奇数，显然不是闭回路，也不含有闭回路；
Ai
Bj
表 3－ 5
B1 x11 C11 x21
B2 x12 C12 x22 C22 x31 x32 C32 b2
…
B1 x11 x21 c11 c21
B2 x12 x22
…
Bn x1n x2n c1n c2n
产量 a1 a2
…
c12
c22
Am 销量
xm1 b1
cm1
xm2 b2
cm2 …
xmn bn
cmn
am
设xij(i=1,2,…，m；j=1,2,…,n)为第i个产地到 第j个销地的运量，产销平衡运输问题的数学模型为：
（2）所有结构约束条件都是等式约束 （3）各产地产量之和等于各销地销量之和
（4)运输问题约束条件的系数矩阵特点

7 4 9 3 6 5 6
2.1 确定初始基可行解
• 这与一般线性规划问题不同，产 销平衡的运输问题总是存在可行解。 因有
b a
i 1 j i 1
m
m
i
d
必存在 0≤ xij,i=1,…,m,j=1,…,n 是可行解。又因 0≤xij≤min(a1,bj) • 故运输问题的可行解和最优解必存在。 • 确定初始可行解的方法有很多，一般 希望的方法即简便又尽可能接近最优解。 下面介绍两种方法：最小元素法和伏格 尔（Vogel）法。（其它如西北角法等）
例1
• 某公司经销甲产品，它下设三个加工厂。每 日的产量分别为： • A1——7吨，A2——4吨，A3——9吨。该公 司把这些产品分别运往四个销售点。各销售 点每日的销量为：B1——3吨，B2——6吨， • B3——5吨，B4——6吨。已知从各工厂到各 销售点的单位产品的运价为表3-3所示，问该 公司应如何调运产品，在满足各销点的需要 量的前提下，使总运费为最少。
运价表与行差和 列差的计算
表3-10 伏格尔法
伏格尔法基可行解， 总运费为85，恰好得 到最优解
销地 B1 B2 B3 B4 行 产 差 量 产地
销地 B1 B2 B3 B4 产地 A1 A2
A1
A2 A3
3
1 7
11 3
9 4 5 6 2 1 5
10 0
8 3 6 1 1
7
4 9
10 5
列差 2 销量 3
A3
表3-13
B1 销地 加工厂 A1 A2 A3 销量 ห้องสมุดไป่ตู้2 B3 B4 产量
5 3 6 3 6 5
2 1 3 6
7 4 9