产销平衡问题 产销不平衡问题
产大于销 销大于供
当产销平衡时，其模型如下：
当产大于销时，其模型是：
mn
min Z
cij xij
i1 j1
xij ai xij bj
xij
0
( ai bj)
当销大于产时，其模型是：
min Z
cij xij
xij ai xij bj
可行解的方法
Review
二、表上作业法的步骤
Step1.找出初始基本可行解（在m*n产销平衡 表上寻找初始调运方案，一般m+n-1个数字 格），用最小元素法、西北角法、伏格尔法；
Step2.求出各非基变量的检验数，判别是否达 到最优解。如果是停止计算，否则转入下一步， 用闭回路或位势法计算；
Step3.改进当前的基本可行解（确定换入、 换出变量），用闭合回路法调整； Step4.重复2. 3，直到找到最优解为止。
（3）运输问题的解
定义1. 闭回路
x x x x x x 闭回路是能折成 i1 j1, i1 j2 , i2 j2 , i2 j3 ,..., isjs , isj1
形式的变量组集合。其中 i1 , i2 , …， is 互不相同，j1 , j2 , …， js 互不相 同。每个变量称为闭回路的顶点，连接闭回路相邻两顶点的直线段叫做闭
统计学院
运筹学－第三章 运输问题
张红历
本章内容
1.运输问题及其数学模型 2.表上作业法 3.运输问题的进一步讨论
4.应用问题举例
第一节 运输问题及其数学模型
一、运输问题的提出
例：某运输问题的资料如下：
单位 销地 运价
产地
A1 A2 A3
销量
B1 B2 B3 B4
2
9 10 2
1
3
4
2
8
4
2
5
2 9 3 10
u1＝0 u2 ＝－1 u3 ＝－5
v1＝2 v2 ＝9 v3 ＝3 v4 ＝10
按σij=cij－(ui+vj) 计算检验数，并以σij≥0 检验，或用 (ui+vj) －cij ≤0 检验。
cij
B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5
1.求初始方案（寻找初始基可行解）
Step1. 选择一个xij，
对xij的选择采用不同的规则就形成各种不同 的方法，比如每次总是在作业表剩余的格子中选 择运价（或运距）最小者对应的xij，则构成最小 元素法，若每次都选择左上角格子对应的xij就形 成西北角法（也称左上角法）。
Step2. 调整产销剩余数量：从ai和bj中分别减去xij的 值，若ai-xij=0，则划去产地Ai所在的行，即该产地 产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai； 若bj-xij =0，则划去销地Bj所在的列，说明该销地需 求已得到满足，而产地Ai尚有存余量ai-bj；
基本思想 ：
就近供应。按单位运价的大小决定供应 的先后，优先满足单位运价最小者的供
销要求。
步 骤：
从单位运价表中选最小元素，然后比较 产量和销量，如果产>销，则划去列，若销 >产，则划去行； 修改ai或bj的值； 再从划去一列和一行后的单位运价表中 找最小元素，……，继续下去； 直到单位运价表的所有元素划去为止。
(ui+vj)
B1 B2 B3 B4
A1 2 9 3 10
－
A2 1 8 2 9
A3 －3 4 -2 5
B1 B2 B3 B4
＝σij
A1 1 2 0 0 A2 0 1 0 －1
A3 10 0 12 0
到的检验数是唯一的（位势可能不同）。
成本表Cij
B1 B2 B3 B4
A1
3 10 u1
A2 1
2
u2
A3
4
5 u3
v1 v2 v3 v4
u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令： u1＝0
(ui+vj)
B1 B2 B3 B4 A1 2 9 3 10 0 A2 1 8 2 9 －1 A3 －3 4 －2 5 －5
3
8
4
6
产量
9 5 7
21
二、数学模型的一般形式
1. 已知资料如下：
设某种物品有m个产地A1，A2，…，Am，产 量
分别是 a1，a2，…，am个单位 有n个销地B1，B2，…，Bn，销量分别为b1，
b2，…bn个单位； 从Ai 到Bj运输单位物品
的运价是cij；
2. 运输问题的几种类型：
ij
ij
ik
lk
ls
xlk
xls
c c
us
uj
xij
xik
检验数
ij =（闭回路上奇数次顶点运距或运价之和）-
（闭回路上偶数次顶点运距或运价之和）
• 对调运方案中每一空格按闭回路法求出检验数 • 若所有检验数大于等于零，则此方案为最优方案； • 若存在检验数小于零，则需对此方案进行调整。
供销
西北角法
基本思想： 优先满足运输表中左上角（即西北 角）空格的供销要求。
供销
B1
B2
B3
B4
产量
A1
3
34
11
3
A2
12
92
2
10 7 4
2
8 42
4
A3
7
43
10 6
5 96
6
销量 3
62
53
6
1
3
5
6
Z 33 411 29 22 310 65 135
伏格尔法（Vogel 逼近法. VAM）
例
单位 销地 运价
产地
A1 A2 A3
销量
B1 B2 B3 B4
3 11 3 10 19 28 7 4 10 5 36 56
产量
7 4 9
供销
B1
B2
B3
B4
产量
A1
3
11 4
3
3
10
3
7
6
A2
31
91 2
8 41 2
A3
76 4
10 3 5 9 3 5
销量 3
6
54
63
1
4
3
6
Z 43 310 31 12 64 35 86
回路的边。
例：x11，x12，x32，x34，x24，x21 就是一个闭回路。
B1 A1 x11
B2
B3
B4
x12
A2 x21
x24
A3 x32
x34
闭回路的特点：
1.每一个顶点都有两条边与之相接，一条是水平的，一条是铅直的； 2.每一个顶点都是转角点，与之相邻的两个顶点，分别在它的水平和铅直方向； 3.每一行（列）如果有闭回路的顶点，则必出现一对，顶点总个数是偶数； 4.从任何一个顶点出发，沿任何一个方向到它的位于同一行或同一列的相邻 顶点，如此继续下去，经过闭回路的所有顶点和边，最后又回到开始的顶点， 但每一定和边在闭回路中只经过一次。
0 ...
1... Aij 0 = ...
1... 0
第 i分量
第 m+j分 量
❖矩阵的元素均为1或0； 每一列只有两个元素为1，其 余元素均为0； ❖ 列向量Pij =(0,…，0，1， 0，…,0,1,0,…0)T，其中两 个元素1分别处于第i行和第 m+j行。 ❖ 将该矩阵分块，特点是：前 m行构成m个m×n阶矩阵， 而且第k个矩阵只有第k行元素 全为1，其余元素全为0 （k=1，…，m）；后n行构 成m个n阶单位阵。
3
5
93
1
— 2 2——
63 2 20
3
3
Z=53+210+31
2
+1 8+64+ 35
2
= 85
2
6
2. 解的最优性检验
判别的方法是计算空格(非基变量)的检验数，因 运输问题的目标函数是要求实现最小化，故当所有 的检验数≥0时，为最优解。 常用两种求空格检验数的方法为：闭回路法和位 势法。
（1）闭回路法
在求一个可行解的过程中注意到包含在矩阵模型中 的成本信息。它通过建立“罚数”来达到此目的。 罚数表示对一方格不进行分配的可能的成本罚款。
步 骤：
Step1. 给定一个平衡的运输矩阵，分别计算行罚数和列罚数；
Step2. 确定具有最大罚数的行或列，然后在罚数所在行（或 列）中选择最小价格元素，将可能的最大单位数分配 给此方格，将相应的行（或列）的供应量和需求量减 去这个量，并划去完全满足的行（或列）；
31
31
21
23
13
14
34
c c c c 10 5 10 3 12
33
33
34
14
13
不是最优解
（2）对偶变量法（位势法）
运输问题的基可行解 X ( xi1 j1 , xi2 j2 , , ximn1 jmn1 )T 在这一组基变量下，建立求解ui，vj的方程组：
ui1 v j1 ci1 j1 ui2 v j2 ci2 j2
• 最小元素法的缺点：为了节省一处的费用，有时造成在其
它处要多花几倍的运费。若不能按最小运费就近供应，就选 择次最小运费，差额越大，说明不能按最小运费调运时，运 费增加越多。
• 每行（列）中次最小价格元素与最小价格元素的数值之差，