运筹学课件第三章运输问题

n m ai b j j 1 i 1
产销平衡条件
第10页
产销平衡的运输问题的特点与性质
min z
c
i 1 j 1
m
n
ij
xij
1.约束条件都是等式约束 2.总产量＝总销量
n i 1, , m xij ai 1 jm s.t. xij b j j 1, , n i 1 xij 0, i 1, m; j 1, , n
10
22 48
第30页
14
12
14
例四
最 小 元 素 法
B1 A1
4
B2
8 10 14 5 2 8
B3
10 50 3 11
B4
6 8 40 9 6
产量 16
A2
A3 销量
运价：880
8
2
10
22 48 产量
8 B1
14 B2
4 2 8 8 6 8 10 5 4 8
12 B3
50 3 11
14 B4
16 9 10 6 22 48
2
x21
10
x22
3
x23
x24
A3
销 量
8
x31 x32
5
x33
11
x34
8
14
12
14
第28页
销地
产地
B1
4
B2
12
B3
4
B4
11
9
产 量
A1
A2
2 8 8 8 10
10
3
2
11
6 16
10

闭合回路法的优点是能够找到全局最 优解，适用于大型复杂运输问题。但 该方法的计算复杂度较高，需要较长 的计算时间。
商位法
01
商位法是一种基于商位划分的优化算法，用于解决运输问题。该方法通过将供 应点和需求点划分为不同的商位，并最小化总运输成本。
02
商位法的计算步骤包括：根据地理位置和货物需求量，将供应点和需求点划分 为不同的商位；根据商位的地理位置和货物需求量，计算总运输成本；通过比 较不同商位的总运输成本，确定最优的配送路线。
80%
线性规划法
通过建立线性规划模型，利用数 学软件求解最优解，得到最小化 总成本的运输方案。
100%
启发式算法
采用启发式规则逐步逼近最优解 ，常用的算法包括节约算法、扫 描算法等。
80%
遗传算法
基于生物进化原理的优化算法， 通过模拟自然选择和遗传机制来 寻找最优解。
02
运输问题的数学模型
变量与参数
约束条件
供需平衡
每个供应点的供应量等于对应 需求点的需求量，这是运输问 题的基本约束条件。
非负约束
运输量不能为负数，即每个供 应点对每个需求点的运输量都 应大于等于零。
其他约束条件
根据实际情况，可能还有其他 约束条件，如运输能力的限制 、运输路线的限制等。
03
运输问题的求解算法
表上作业法
总结词
直到达到最优解。这两种方法都可以通过构建线性规划模型来求解最优解。
04
运输问题的优化策略
节约法
节约法是一种基于节约里程的优化算法，用于解决 运输问题。该方法通过比较不同配送路线的距离和 货物需求量，以最小化总运输距离为目标，确定最 优的配送路线。
节约法的计算步骤包括：计算各供应点到需求点的 距离，找出最短路径；根据最短路径和货物需求量 ，计算节约里程；按照节约里程排序，确定最优配 送路线。

第三章 运 输 问 题
§3.1 运输问题及其数学模型 §3.2 运输问题的求解
----表上作业法 §3.3 产销不平衡的运输问题 §3.4 运输问题应用
1
§3.1 、运输问题模型及其数学模型
问题的提出 一般的运输问题就是要解决把某种产品从若
干个产地调运到若干个销地，在每个产地的供应 量与每个销地的需求量已知，并知道各地之间的 运输单价的前提下，如何确定一个使得总的运输 费用最小的方案。
1、求初始方案：最小元素法、西北角法、伏格尔法
22
方法1：最小元素法
基本思想是就近供应，即从运价最小的地方开始供应（调 运），然后次小，直到最后供完为止。
A1 A2 A3 销量
B1 3
1
3
7
3
B2
B3
B4
11
3 10
43
9
2
8
1
4
6
6
10 5
3
5
6
产量 7
4
9
总的运输费＝(3×1)+(6×4) +(4×3) +(1×2)+(3×10)+(3×5)=86元
步。
空格
(3) 对方案进行改善，找出新的调运方案。（表上闭回
路法调整）
(4) 重复（2）、（3），直到求得最优调运方案。
20
表上作业法是一种求解运输问题的特殊方法，其 实质是单纯形法。
步骤
描述
方法
最小元素法、 第一步 求初始基行可行解（初始调运方案） 西北角法、
伏格尔法
第二步
求检验数并判断是否得到最优解当非 基变量的检验数σi j全都非负(求min) 时得到最优解，若存在检验数σi j <0， 说明还没有达到最优，转第三步。

❖ 建模：设xij为从产地Ai运往销地Bj的物资数量（i=1， …m；j=1，…n。
销地 B1
B2
...
Bn
产量
产地
A1
X11 X12
...
X1n
a1
A2
X21 X22
...
X2n
a2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Am
Xm1 Xm2
...
Xmn
am
销量
b1
b2
...
bn
则运输问题的数学模型如下：
产销平衡表
销地 B1
B2
...
Bn
产量
产地
A1
a1
A2
a2
.
.
.
.
.
.
Am
am
销量
b1
b2
...
bn
单位运价表
销地
B1
B2
...
Bn
产地
A1
c11
c12
...
c1n
A2
c21
c22
...
c2n
.
.
.
.
.
.
.
.
.
.
.
.
Am
cm1
cm2
...
cmn
❖ 若总产量等于总销量（产销平衡），试确定总运费最省 的调运方案。
Table14 检验数表
销地
B1
B2
B3
B4
产地
A1