《之二运输问题》PPT课件

22
2021/7/26
表3.20
销地
产地
B1
B2
B3
B4
产量
A1
2
5
7
A2
1
3
4
A3
6
3
9
销量
3
6
5
6
表3.21
销地
产地
B1
B2
A1
A2
3-
A3
6
销量
3
6
B3
B4
产量
5
2-
7
1+
4
3
9
5
6
23
2021/7/26
例：用表上作业法求下列运输问题的最优解:
销地 B1
B2
B3 产量
产地
A1
5
1
8 12
10
2021/7/26
1.求初始基可行解 方法1：最小元素法
基本思想：就近供应，即 从运价最小的地方开始供 应（调运），然后次小， 直到供完为止.
A1 A2 A3 销量
B1
3
3
1
7
03
B2
11
9
6
4
06
B3
4
3
1
2
10
045
B4
3
10
8
3
5
6
产量 73 410 93
11
2021/7/26
1.求初始基可行解 方法2：Vogel法
j1
m
xij bj ( j 1, , n)
i1
xij
0
(i 1,
,m
j 1,

B1 B2 B3 产量
A1 6 4 6
200
A2 6 5 5 销量 250 200 200
300 500
650 23
B1 B2 B3
产量
A1

6
4
6
200
A2
6
5
5
销量 250 200 200
300 500
650
解：增
B1 B2 B3
加一个 A1 6 4 6
虚设的 A2 6 5 5
产地运 A3 0 0 0 输费用 销量 250 200 200
6
4 6 200
A2
6
5 5 300
销量 150 150 200
B1
B2
B3 产量
A1
x11
x12
x13 200
A2
x21
x22
x23 300
销量 150 150 200
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
A1 A2 销量
B1 6 6 150
B2 4 5 150
§2
运输问题的计算机求解
运行管理运筹学计算机软件：
点击运输问题模块
14
在日常生活中，随处都可以看到浪费 粮食的 现象。 也许你 并未意 识到自 己在浪 费，也 许你认 为浪费 这一点 点算不 了什么
§2
运输问题的计算机求解
点击新建
选择Min
输入3
输入4
点击确定
15
在日常生活中，随处都可以看到浪费 粮食的 现象。 也许你 并未意 识到自 己在浪 费，也 许你认 为浪费 这一点 点算不 了什么

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

❖ 建模：设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

在运输问题中，混合整数规划可以处理更为复 杂的约束条件和多阶段决策过程。
通过将问题分解为多个子问题，并应用分支定 界法等算法，可以找到满足所有约束条件的整 数解，实现运输资源的合理配置。
04运Leabharlann 问题的实际案例物资调拨案例
总结词
物资调拨案例是运输问题中常见的一种，主要涉及如何优化物资从供应地到需 求地的调配。
02
动态运输问题需要考虑运输过 程中的不确定性，如交通拥堵 、天气变化等，需要建立动态 优化模型来应对这些变化。
03
解决动态运输问题需要采用实 时优化算法，根据实际情况不 断调整运输计划，以实现最优 的运输效果。
多式联运问题
1
多式联运是指将不同运输方式组合起来完成一个 完整的运输任务，需要考虑不同运输方式之间的 衔接和配合。
生产计划案例
总结词
生产计划案例主要关注如何根据市场需求和生产能力制定合理的生产计划。
详细描述
生产计划案例需要考虑市场需求、产品特性、生产成本、生产周期等因素。通过 优化生产计划，可以提高生产效率、降低生产成本，并确保产品按时交付给客户 。
05
运输问题的扩展研究
动态运输问题
01
动态运输问题是指运输需求随 时间变化而变化的运输问题， 需要考虑时间因素对运输计划 的影响。
2
多式联运问题需要考虑不同运输方式的成本、时 间、能力等因素，需要建立多目标优化模型来平 衡这些因素。
3
解决多式联运问题需要采用混合整数规划或遗传 算法等算法，以实现多目标优化的效果。
逆向物流问题
1
逆向物流是指对废旧物品进行回收、处 理和再利用的物流活动，需要考虑废旧 物品的回收、分类、处理和再利用等环 节。
的情况。如果存在这些问题，就需要进行调整，直到找到最优解为止。

1
=
j
j = 1
(
(
这就是运输问题的数学模型，它包含 m·n 变量, m + n 个约束条件。如果用单纯形法求解，先得在各约 束条件上加入一个人工变量(以便求出初始基可行解)。 因此，即使是 m = 3 ， n = 4 这样的简单问题, 变量数 就有19个之多，计算起来非常复杂。因此，我们有必 要针对运输问题的某些特点，来寻求更为简单方便的 求解方法。
销地产地
B1
B2
B3
B4
A1
x11
x12
A2
x21
x24
A3
x32
x34
x11 、 x12 、 x32 、 x34 、 x24 、 x21 构成一个闭回路. 这里有： i1 = 1 ， i2 = 3 ， i3 = 2；j1 = 1 ，j2 = 2 ，j3 = 4. 若把闭回路 的顶点在表中画出, 并且把相邻两个变量用一条直线相连 (今后就称这些直线为闭回路的边)。
第二节 表上作业法1. 表上作业法的基本概念与重要结论针对运输问题的数学模型结构的特殊性，它的约束方 程组的系数矩阵具有如下形式( 具体见下一张幻灯片 )，该 矩阵中， 每列只有两个元素为1，其余都是0。根据这个特 点，在单纯形法的基础上，创造出一种专门用来求解运输 问题的方法，这种方法我们称为表上作业法。运输问题也是一个线性规划问题，当用单纯形法进 行求解时，我们首先应当知道它的基变量的个数；其次， 要知道这样一组基变量应当是由哪些变量来组成。由运输 问题系数矩阵的形式并结合第一章单纯形算法的讨论可以 知道: 运输问题的每一组基变量应由 m+n-1个变量组成。 (即基变量的个数 = 产地个数 + 销售地个数 – 1) 进一步我 们想知道, 怎样的 m+n-1个变量会构成一组基变量？

由于目标要求极小，因此，当所 有的检验数都大于或等于零时该调运 方案就是最优方案；否则就不是最优， 需要进行调整。
17
1、闭回路法
以最小元素法给出的初始基本可行解方案
为例，考察初始方案的一个非基变量x24。 地品就x加为14运了必B1减送保根4须个少的1持据使单。个初产1位x如单始销个14，果位平方单或例现给衡案位如在，，x，B3改44产就第x减，1变地必3 1那少初增须A行么始加使21的的为方个x1运产了案23单个输品保，减位单是量持把少；位不就产A而，运必销12 如那平须的往个衡销增果么产单，
27
由于有m + n 个变量（ ui , vj ）， m + n - 1 个方程（基变量个数），
故有一个自由变量，位势不唯一。
利用位势求检验数：
ij = cij - ui - vj i = 1, … , m ; j = 1, … , n
28
前例，位势法求检验数：
step 1 从任意基变量对应的 cij 开始, 任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 个 ui , vj 从 c14 = 10 开始
3
6
3 5
6
6
20
13
1、确 定 初 始 基 本 可 行 解：
B1
B2
A1
3
11
3
（1）西 北 角 法
B3
B4
10
产量 ai 7
3
4
A2
1
9
2
8
4
2
2
A3
7
4
10
5
9
销量 bj
3
6

3
B4 3
10
产量 7 4
1
9
2
8
A3
销量 3
7
6
6
4
10
3
6
5
9
5
空格
x11 x12
闭回路
x11—x13—x23—x21—x11 x12—x14—x34—x32—x12 x24—x23—x13—x14—x24 x33—x34—x14—x13—x33
检验数
1 2
x22
x24 x31 x33
x22—x23—x13—x14—x34—x32—x22 1
B1 A1 A2 A3 销量 3 3
3
B2
11
B3 4 (+1) 1 (-1)
3
B4 3 (-1) (+1) 3 6
10
产量 7 4 9
1
9
2
8
7
6 6
4
10
5
5
B1 A1 A2 A3 vj 0 3 9 3
3
B2 2 2 6 9
11
B3 5 1 12 3
3
B4 2 1 3 10
10
ui 0 -2 -5
一般运输问题的线性规划模型
min f cij xij
1 1 2 x11 x21 2 x12 x22
m n
… n
x1n x2n
产量 s1 s2
i 1 j 1
x
j 1 m
n
ij
s i , i 1,2, , m, d j , j 1,2,, n.
…
m xm1 xm2
1
9
2
8
7
4

10:27:41 2
运输问题
人们在从事生产活动中，不可避免地要进行物 资调运工作。如某时期内将生产基地的煤、钢 铁、粮食等各类物资，分别运到需要这些物资 的地区，根据各地的生产量和需要量及各地之 间的运输费用，如何制定一个运输方案，使总 的运输费用最小。这样的问题称为运输问题。
10:27:41
3
运输问题的特征 Characteristics of Transportation Problems
此时运价表上所有元素都划去了，相应地在产销平衡表上填了
（m+n-1）个数字格，即给出了（m+n-1）个基变量的值。
10:27:41 18
（2）这（m+n-1）个数字格对应的系数列向量线性无关。 证 若表中确定的第一个基变量为 xi j ，它对应的系数列向量为
1 1
Pi1 j1 ei1 e j1
销地 加工厂
B1 3 1 7
B2 11 9 4
B3 3 2 10
B4 10 8 5
产量
A1 A2 A3
需要量
10:27:41
7 4 9
3
6
5
6
7
设xij ( i =1,2,3；j =1,2,3,4)为i个产地运往第j个需求地的运量 ，这样得到下列运输问题的数学模型： min z = 3x11+ 2x12+ 6x13+ 3x14+ 5x21+ 3x22+ 8x23+ 2x24 + 4x31+ x32+ 2x33+ 9x34
OPERATIONAL RESEARCH
运筹学
——怎样把事情做得最好
OR2
1

66 « ¡
6¡ «
70
( )
年龄段
2.00 1.50 1.00 0.50 0.00
1.90 1.88 1.84 1.78 1.71 1.73 1.62 1.39 1.09 0.93 0.65 0.52 0.40 0.16
10
20
30
40
50
60
70
年龄段
6¡ «
« ¡
¡ «
« ¡
« ¡
« ¡ 56
A1 A2 A3 销量
12
0
0
0
4
SEU
产销不平衡问题
产地 销地 B1 4 3 8 B2 1 4 10 B3 2 3 5 产量 10 12 22 23 23-22 A1 A2 销量
产小于销 (供不应求)
• 增加一个产地
产地
销地
B1 4 3 0 8
B2 1 4 0 10
B3 2 3 0 5
产量 10 12 1 23 23
xij≥0 (i=1,2,3；j=1,2,3,4)
非负性约束
5
三、运输问题的三种类型
• 产销平衡
a b
i 1 i j 1
m
n
j
min Z cij xij
i 1 j 1 n
m
n
x
j 1 m
ij
ai , bj ,
i 1,2,...,m j 1,2,...,n
4
B1 6 7 3 2
B2 3 5 2 3
B3 2 8 9 1
B4 5 4 7 4
产量 5 2 3
• 运输问题的LP模型
(1)决策变量。设从Ai到Bj的运输量为xij， (2)目标函数