运筹学3 运输问题 PPT课件

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

确定初始可行解方法一：西北角 法
门市部 工厂
1
2
3
4 供应总计
9
12
9
6
1
50
7
3
7
7
2
60
6
5
9
11
3
50
需求总计 40 40 60 20
确定初始可行解方法一：西北角 法
门市部 工厂
1
2
3
4 供应总计
9
12
9
6
1
50
40 10
7
3
7
7
2
30 30
60
6
5
9
11
3
30 20
50
需求总计 40 40 60 20
2
34
9 12 9 6
1
40
10
U1
7
3
7
7
2
★
40
20
U2
3
6
5
9
11
40
10
U3
V1 V2 V3 V4
21 (7 6 9) (9 11 7) 5
继续求检验数
门市部
工厂
1
2
3
4
供应总 计
9 12 9 6
1
40 （12） （5）
10
50
7
3
7
7
2
(-5) 40
20 （-2） 60
3
6
计算检验数方法一：闭合回 路法
门市部 工厂
1
9 1
40
7 2
6 3
需求总计 40
2
3

• 三、沃格尔法（VOGLE）
用最小元素法确定例3-2初始调运方案
调 销地
运 量
B1
B2
B3
产量
产地
100 90
70 100100 200 100
A1
X11
X12
X13
80 150 65 100 75 250 100
A2
X21
100
销量
X22
X23
150
200
100 450
用西北角法确定例3-2初始调运方案
表3-3 运输问题作业表（运价表）
调 销地 运 量
产地
A1
A2
B1
c11
X11
c21
X21
销量
b1
B2
c12
X12
c22
X22
b2
B3
产量
c13
X13
c23
X23
b3
a1
a2
2
3
ai bj
i1
j1
3、举例
例3-2 甲、乙两个煤矿供应A、B、C 三个城市用煤，各煤矿产量及各城 市需煤量、各煤矿到各城市的运输 距离见表3-4，求使总运输量最少的 调运方案。
第五章 运输与指派问题
运输问题的表示
运输问题模型、运价表
运输问题的求解
表上作业法
指派问题
简述
运输、指派和转运问题，实际上都可以用 L.P. 模型加以描述，所以可以认为它们是 L.P. 的 特例 单列一章的原因在于：应用面极广，实践性 很强，而特有的数学结构使得人们设计出了 特别有效的方法对此类模型进行求解 本章的重点在：掌握表格化方法求解运输
提出问题

所有非基变量的检验数都大于等于，则运输方案 最优
求检验数的方法有三种： 闭回路法 位势法（▲）
运价矩阵法
9
运价矩阵法
3 11 （3）（10）
3 11 （3）（10）
（ 1） 9 （2）
8
行加（ 2）
10
（3）
9
7 （4） 10 （5）
12 （9） 15 （10）
1 2 （0）（0）
列减（ 0）
解：第1步 求初始方案，见下表所示。
总的运输费＝(3×1)+(6×4) +(4×3) +(1×2)+(3×10)+(3×5)=86元
B1
B2
B3 B4 产量
A1
4 37
3
11
3
10
A2
3
1
4
1
9
2
8
A3
7
6
4
10
39
5
销量 3
6
56
8
第2步 最优解的判别（检验数的求法）
求出一组基可行解后，判断是否为最优解，仍然是用检 验数来判断，记xij的检验数为λij由第一章知，求最小值的运 输问题的最优判别准则是：
的模型：
mn
min z
cij xij
i1 j 1
n
xij ai
i 1, , m
j1
s.t
m
xij
bj
j 1, , n
i1
x
ij
0,
i 1, , m; j 1, , n
4
变化： 1）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加

可利用价格表采用 西北角法 最小元素法 伏格尔法 等方法求平衡运输问题的初始调动方案 9
以例子说明表上作业算法 有如下表格描述的平衡运输问题
1
2
3
4
2
7
3
11
20
1 x11
x12
x13
x14
8
4
6
9
20
2 x21
x22
x23
x24
4
3
10
5
40
3 x31
x32
x33
x34
30
25
10
15
10
初始基础可行解—西北角法
15
x32=Min(a3,b2)=25 在三行二列填数25 调整行列供求 a3=25-25=0, b2 =40-25=15 划去已完全满足的第二15列
用同样的方法确定其它数字格的调运量
1
2
3
4
2
7
3
11 20 0
1 20
8
4
6
9 20 10 0
2
10
10
4
3
3 10
25
10
5
5 40 15 5 0
xlk=min(al,bk) （3）同时划去使行或列要求恰好满足的行 或列，调整行列供求量。
（4）重复（1）到（3）从而在m+n-1个方 格上填数字，构成运输问题的初始调运方 案
最小元素：min{cij}=c11=2
1
2
3
4
2
7
3
11 20 0
1 20
8
4
6
9 20
2
4
3
10

x11, x41, x43, x33, x32 , x12
A3
x32
x33
Ch3 Transportation Problem
2019年12月27日星期五 Page 9 of 11
【解】 设 xi j (i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，
则此问题的数学模型为
min Z 5x11 2x12 3x13 6x21 4x22 x23 7x31 3x32 4x33
2019年12月27日星期五 Page 14 of 11
x11 x12 x1n x21 x22 x2n xm1 xm2 xmn 1 11
1 11

A
1 11
1
1
1
1
1

1



1
1
1
中任意m+n阶子式等于零，取第一行到m+n－1行与
x1n，x2n，，xmn , x11, x12 ,, x1,n1
对应的列（共m+n-1列）组成的m+n－1阶子式
§3.2 基变量与闭回路 Ch3 Transportation Problem
Basis Variable and Closed Path
2019年12月27日星期五 Page 15 of 11
1
1 11
1



1
0
Basis Variable and Closed Path
2019年12月27日星期五 Page 13 of 11
【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变量
数为m+n-1。

定理： 若变量组 x ,x , i1j1 i2j2 ,xisjs
(s= m+n-1)是运输问题的基变量，xij是一个非
基变量，则变量组 xij,xi1j1,xi2j2, ,xisjs
中存在包含xij 的唯一闭回路。
14
§2 求解运输问题的表上作业法
运输问题是一种特殊的线性规划问题， 根据其特殊性设计的表上作业法，仍然重复 单纯形法的思想，但验证最优标准和可行性 的方法有些变化，其求解步骤如下： （1）给出初始基可行解； （2）检验是否是最优解，如果是最优解， 则计算结束；否则转入（3）； （3）确定进基变量和出基变量，求出新的 基可行解，返回（2）。
推论： 若变量组 xi1j1,xi2j2, ,xirjr
中有一个部分组构成闭回路，则该变量 组对应的系数列向量线性相关。
推论：m+n-1个变量构成基变量的充要 条件是不含闭回路。
13
若变量组中某一个变量是其所在行或所 在列中包含在该变量组中的唯一变量，则称 这个变量是变量组的孤立点。
不包含任何闭回路的变量组中必有孤立点。
n
xij ai
j 1
m行
1
1
1
1
1
1
1 1 1
m
xij b j
i 1
n行
1
1
1 1
1
1
1
1
7 1
该矩阵的元素全部是0或1。每一列 只有两个元素为1，其余为0。若用Pij表示 xij的系数列向量，则在Pij中第i个和第m+j 个元素为1，其余为0。即
0
1
5
产销平衡的运输问题
m
n
ai bj
i1
j 1

精选课件
2、求检验数--闭回路法: 例1
销地 产地
B1 3
B2 11
B3 3
B4
ai
10
注: 1)数字格检 验数均为0
A1
④
③
7 2)空格检验数
1
2
A2
③1
9
2
①
8
以某空格为起点，用水平或垂直
4 线往前划，每碰到一个数字格转
1
-1
90。，然后继续前进，直到回到起
7
4
10
5
A3
⑥
③
9 点。根据回路计算该空格对应变
精选课件
用网络优化软件
运费 一区1 一区2 二区 三区1 三区2 供应量
山西盂县 1.65 1.65 1.7 1.75 1.75 4000
河北临城 1.6 1.6 1.65 1.7
1.7 1500
假想地点 M
0
M
M
0
500
6000 需求量 2700 300 1000 1500 500
6000
精选课件
运输问题的表格表示
需求地
1
供应地
16
28
35
合计 13
2
7 4 9 21
3
5 2 10 9
4
3 7 6 7
合计
25 10 15
精选课件
运输问题线性规划模型
min z = 6x11 + 7x12 + 5x13 + 3x14 + 8x21 + 4x22 + 2x23 + 7x24 + 5x31 + 9x32 +10x33 + 6x34

第三章 运输问题
Transportation Problem
运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 西北角法、最小元素法 非基变量的检验数 闭回路法、位势法 确定进基变量，调整运量，确定离基变量
08.10.2020
1
一.运输问题的一般提法
人们在从事生产活动中，不可避免地要进行物资调运工作。如 某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到 需要这些物资的地区，根据各地的生产量和需要量及各地之间 的运输费用，如何制定一个运输方案，使总的运输费用最小。
n
供过于求：即产量大于销量时有ai bj
1
1
这两种情形都 a可 i 以 bj的 化形 为式来
求解
08.10.2020
8
二.运输问题的模型
产销平衡问题模型
m
n
M i n z a i j x i j
1
1
n
x ij a i
i 1,......m
j1
m
x ij b j j 1 , . . . . . . n
1.变量多（mn
1 1
个），但结构
简单。
11
技术系数矩阵
A
=
1
1
1 1 1
08.10.2020
11
1 11
系数矩阵的特点: (1)约束条件的系数矩阵的元素只有两个:0,1. (2)元素 xij 对应于每一个变量在前m个约束方程中(第i个 方程中)出现一次,在后n个约束方程中(第m+j 个方程中) 也出现一次. (3)产销平衡问题为等式约束. (4)产销平衡问题中各产地产量之和与各销售地点的销量 之和相等.
i1
j 1

动态规划模型
动态规划是一种数学方法，用于解决具有重叠子问题和最 优子结构的问题。在运输问题中，动态规划模型通常用于 解决具有时间序列或阶段性的运输问题。
动态规划模型将运输问题分解为一系列的子问题，并逐一 解决这些子问题以找到最优解。
启发式算法
启发式算法是一种基于经验或直观的 算法，用于在可接受的时间内找到近 似最优解。在运输问题中，启发式算 法通常用于解决大规模或复杂的运输 问题。
注意事项：载重优化需要考虑货物的特 点和限制条件，如易碎、易燃、易腐蚀 等货物需要特殊处理，同时需要关注货 物的安全性和稳定性，防止发生意外事
故。
时间优化
总结词
时间优化是运输问题中的关键策略，通过合理安排运输时间，降低运输延迟和提高运输效率。
详细描述
时间优化主要考虑如何将运输时间进行合理的安排和管理，以最小化运输延迟和提高运输效率。这需 要考虑运输需求的时间分布、交通状况、天气等多种因素，以及如何合理安排运输计划和调度。
分类
根据货物的需求量、运输能力、运输方式等因素，运输问题可以分为多种类型 ，如产销平衡运输问题、产销不平衡运输问题、多品种运输问题、多模式运输 问题等。
运输问题的特点
01
优化目标
最小化运输成本。
02
03
04
约束条件
货物的需求量、运输能力、时 间限制等。
决策变量
每个运输路线的运输量。
线性规划
运输问题的目标函数和约束条 件都是线性的，可以使用线性
04
运输问题的优化策略
路径优化
总结词
路径优化是运输问题中常用的策略，通 过合理规划运输路线，降低运输成本和 时间。
VS
详细描述
路径优化主要考虑如何选择最佳的运输路 径，以最小化运输时间和成本。这需要考 虑路况、距离、交通状况等多种因素，以 及如何合理安排车辆和人员，确保运输效 率最大化。

30
20
70
30
10
50
需求地区 化工厂
Ⅰ’ 16 14 19 M
Ⅰ’’ 16 14 19 0
Ⅱ 13 13 20 M
Ⅲ 22 19 23 0
Ⅳ’ 17 15 M M
Ⅳ’’ 17 15 M 0
12
A B C D
2015年6月10日星期三

第二步见表3-6，3-7
需求地区 化工厂
Ⅰ’ Ⅰ’’
Ⅱ
Ⅲ
Ⅳ’
cij xij
i 1 j 1
2015年6月10日星期三
5
满足：
n 1 xij ai j 1 m xij b j i 1 xij 0
m n n 1 j 1
由于这个模型中
i 1
ai b j bn 1 b j
0
0
5
-18
2015年6月10日星期三
20
3.表中还有负检验数。说明未得最优解，利用闭回路调 整法，见表3-21
需求地区 化工厂
Ⅰ’ Ⅰ’’
Ⅱ
Ⅲ
Ⅳ’
Ⅳ’’
A B C D 销量(万吨)
(-10) 30 10 10 (+10)
50 20 30 (-10) 0 (+10) 70 30 10 10
30
20
' cij cij,
' cij 0,
当 i=1,…，m，j=1,…，n时 当 i=1,„，m，j=n+1时
将其分别代入，得到
' ' min z ' cij xij cij xij ci' , n 1 i 1 j 1 m n i 1 j 1 i 1 m n 1 m n m