当前位置：文档之家 › 管理运筹学 第三章运输问题.

管理运筹学 第三章运输问题.

  • 格式：ppt
  • 大小：3.94 MB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

管理运筹学第3章-运输规划1

管理运筹学第3章-运输规划1

6
9 u2=-2
5
9
10
6
3
-11
-3
6
13 u3=6
v1=10
v2=6
v3=4
v4=0
c32 - z32= c32 – (u3+v2)= 9 – 6-6=-3
3.3 迭代规则 运算方法—闭回路调整法
调整的步骤如下： （1）先确定最小检验数：； （2）找出以空格为一个顶点，其余顶点全是数字
-----退化解出现
3.3 迭代规则 运算方法—闭回路调整法
1
2
3
4
6
7
1
14
5
5
3
5
u1=-4
7
8
4
2
7
2
8
13
6
9 u2=-2
5
9
10
6
3
-11
-3
6
13 u3=6
v1=10
v2=6
v3=4
v4=0
x31进基, min{x21,x33}=min{8,6}=6, x33离基
转轴运算,重新计算检验数,确定进基、离基变量
第三章 运输问题
运输问题及其数学模型 运输问题表上作业法
3.1 运输问题及其数学模型
一、一般运输问题
设某种货物有m个产地A1，A2，…,Am,产量分 别为a1,a2,…,am,有n个销地B1,B2,…,Bn,销量分 别为b1,b2,…,bn，而且从Ai到Bj的单位运价为 Cij。若产销平衡（ ai= bj），问如何制定调 运方案，可以使总运费最小？
v3=4
4 3
u1
7 u2=-2
6
13 u3=6

运筹学(第四版)：第3章 运输问题

运筹学(第四版)：第3章 运输问题

x11 x12 x1n x21 x22 x2n xm1 xm2 xmn
u1 1 1 1
u2
um
1
1
1
1
1
1
m行
v1 1
1
1
v2 1
vn
1
1
1
1
1
n行
5
第1节 运输问题的数学模型
该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和 第m+j个为1以外，其余的都为零。即
21
2.2 最优解的判别
判别的方法是计算空格(非基变量)的检验数cij−CBB-1Pij， i,j∈N。因运输问题的目标函数是要求实现最小化，故当 所有的cij−CBB-1Pij≥0时，为最优解。下面介绍两种求空格 检验数的方法。 1.闭回路法； 2.位势法
22
2.2 最优解的判别
1.闭回路法
2.1 确定初始基可行解
第二步：从行或列差额中选出最大者，选择它所在行或列 中的最小元素。在表3-10中B2列是最大差额所在列。B2列 中最小元素为4，可确定A3的产品先供应B2的需要。得表311
销 地 B1 B2 B3 B4 产
加工厂
量
A1
7
A2
4
A3
6
9
销量 3 6 5 6
18
2.1 确定初始基可行解
销 地 B1 B2 B3 B4 产
加工厂
量
A1
A2
3
43 7
1
4
A3
6
39
销量
36 56
12
2.1 确定初始基可行解
用最小元素法给出的初始解是运输问题的基可行解，其理由为： (1) 用最小元素法给出的初始解，是从单位运价表中逐次地

广工管理运筹学第三章运输问题

广工管理运筹学第三章运输问题

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

运筹学-3运输问题

运筹学-3运输问题
产销平衡问题 产销不平衡问题
产大于销 销大于供
当产销平衡时，其模型如下：
当产大于销时，其模型是：
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
销量

运筹学第三章 运输问题

运筹学第三章 运输问题

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

运筹学 第3章运输问题

运筹学 第3章运输问题

检 验 数 表
最 优 方 案 判 别 准 则
B1 3 A1 A2 7 A3 vj
B2 11
B3 3 2
B4 10 8
ui
1
1Байду номын сангаас
2
9
0
1
4 10
-1
5
-1 -5
10
2 9
12
3 10
24=-1＜0，当前方案 不是最优方案。
26
2.3
闭回路调整法改进方案
min ij 0 pq
xpq 为换入变量
min
z cij xij
i 1 j 1
s.t.
n xij ai 1 jm xij b j i 1 xij 0
i 1,, m j 1,, n
4
运输问题的约束方程组系数矩阵及特征
x11 x12 .... x1n 1 1.......1 A 1 1 1 x21 x22 .... x2 n ...... xm1 xm 2 .... xmn 1 1.......1 ......... 1 1.......1 1 1 1 .......... 1 1 1
10
1. 最小元素法 （思想：就近供应） 不 能 同 时 划 去 行 和 列
销 产 A1 1 A2 A3 销量 3 9 B1 3 B2 11 B3 3 B4
表3-4
产量 10 7 8 5
4
2
3
3
7 4
1
10
6
6 5
3
6
保证填 4 有运量 的格子 9 为m+n1
该方案总运费： Z=4×3+3×10+3×1+1×2+6×4+3×5=86

运筹学 第三章 运输问题

（或者在同时划去Ai行与Bj列时，在该行或该列的任意空格处填加一 个0。）
这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为 m+n-1个。
2021/3/14
14
2.Vogel法
Vogel法的思想是:一地的产品如果不能按照最小运
费就近供应，就考虑次小运费，这就有差额，差额越大， 说明不能按最小运费调运时，运费增加得越多。因而差 额越大处，就应当采用最小运费调运。
同理可以求得 v4=10，u2= -1，等等见上表。
检验数的求法，即用公式 ijciju，i vj
如 1 1 c 1 1 u 1 v 1 3 0 2 1 。
2021/3/14
23
位势法计算检验数：
检验数： ijcijCBB1Pij
cijYiP jcij(u1,..u.m , ,v1,.v.n.)Pij
3
B4
ui
3 10
0
-1 8
-1
35
-5
10
B1
3
31
7
2
B2
11 9
64
9
B3
4(+1) 3 1 (-1) 2
10
3
B4
ui
3(-1) 10
0
+1 8
-1
35
-5
10
2021/3/14
26
调整运量后的新方案：
销地
产地
B1
A1
A2
3
A3
B2
B3
5
6
销量
3
6
5
B4
产量
2
7
1
4
3
9

运筹学 第三章 运输问题

• 设xij表示产地 i 运往销地 j 的物资量, cij表示对应的单位运费, 则我们有运输问题的数学模型如下:
mn
Min Z = cij xij i1 j1 m xij =ai （i=1, ..., m）产量约束 i 1 n xij =bj（j=1, ..., n）销量约束 j1
xij ≥ 0（i=1, ..., m；j=1, ..., n）
15
2. 伏格尔法（Vogel）
例5
销地 产地
A1
B1 3
②
B2
B3
11
3
⑤
B4
ai
10 7 0 0 0 0
1
A2
①
9
2③ 8 4 1 1 1 1
A3
7
4
⑥
10
③
5 9 12 - -
bj
3
6
5
6 20
2513
2 - 13
2 - 12
2-1-
Z＝2×3 ＋1×1＋6×4＋5×3＋3×8＋3×5＝85 16
0
2.决策变量xij的系数列向量为:
1
i位 置
aij
1
m
j位 置
3. 线性无关的行数为m+n-1.
0
5
四、闭回路
1. 概念
例3
销地 产地
A1
A2
A3 bj
B1
B2
B3
B4
ai
3
11 ④
3 ③
10 7
1 ③
9
2
①
84
7
4
⑥
10 ③
59
3
6
5
6 20
1) 数字格 2) 空格

《运筹学》第三章 运输问题


二、表上作业法
计算步骤：
(1) 找出初始调运方案。即在(m×n)产销平衡表 上给出m+n-1个数字格。(最小元素法、西北角法 或伏格尔法） 确定m+n-1个基变量 (2) 求检验数。（闭回路法或位势法） 判别是 否达到最优解。如已是最优解，则停止计算，否 则转到下一步。 空格 (3)对方案进行改善，找出新的调运方案。 （表上闭回路法调整） (4) 重复（2）、（3），直到求得最优调运方案。
B1 A1 A2 A3 销量 3 1
B2 2
B3 4
B4 3
产量 7 4
3
6 6
1
3 5 6
9
B1 A1 A2 A3 销量 3 1
B2 2
B3 4
B4 3
产量 7 4 9
3
6 6
1
-1
3
5
6
B1 A1 A2 A3 销量 3 1 3
B2 2 1 6 6
B3 4 1
B4 3 -1 3
产量 7 4 9
(ui+vj)
－ B2 9 8 4 B3 3 2 -2 B4 10 9 5
A3 －3
σij
B1 ＝ A1 A2 A3 1 0 10 B2 2 1 0 B3 B4 0 0 0 －1 12 0
表中还有负数，说明 还未得到最优解，应 继续调整。 用位势法与用闭回路法 算出的检验数？ 相同
3、解的改进
——闭合回路调整法（原理同单纯形法一样） 上例： min( σ ij 0 ) pq
m
n
系数列向量的结构： A ij ( 0， 0， 0 ，， 0， 0 ) 1， 0 1，
第 i个
第 ( m j )个

运筹学第三章 运输问题

则称该运输问题为产销平衡问题；否则，称 产销不平衡。首先讨论产销平衡问题。
8
1.运输问题模型及有关概念
表4-3 运输问题数据表
销地
产地
A1 A2
┇
Am
销量
B1 B2 … Bn
c11
c12 … c1n
c21
c22 … c2n
┇ ┇ ┇┇
cm1
cm2 … cmn
b1
b2 … bn
产量
a1 a2
┇
am
设 xij 为从产地 Ai 运往销地 Bj 的运
式（4-8）中的变量称为这个闭回路的顶点。
22
1.运输问题模型及有关概念
例如，x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是闭回路。
若把闭回路的各变量格看作节点， 在表中可以画出如下形式的闭回路：
得到下列运输量表：
4
1.运输问题模型及有关概念
Min Z s.t.
= 6x11+4x12+6x13+6x21+5x22+5x23 x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
2.每列只有两个 1，其余为 0，分别 表示只有一个产地和一个销地被使用。
7
1.运输问题模型及有关概念
一般运输问题的线性规划模型及求解思路
一般运输问题的提法：
假设 A1, A2,…,Am 表示某物资的m个 产地；B1,B2,…,Bn 表示某物资的n个销地； ai表示产地 Ai 的产量；bj 表示销地 Bj 的 销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价（表4-3）。如果 a1 + a2 + … + am = b1 + b2 + … + bn
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
（其中
a b ）
i 1 i j 1 j
m
n
运输问题的约束方程组系数矩阵及特征
x11 x12 .... x1n 1 1.......1 A 1 1 1 x21 x22 .... x2 n ...... xm1 xm 2 .... xmn 1 1.......1 ......... 1 1.......1 1 1 1 .......... 1 1 1
例1： 某集团新购进一批钢材，分别存储在三个仓库，现在 要将这批钢材运到分布在各地的四个工厂。各仓库的库存量、 各工厂的需求量以及从各仓库往各个工厂每运送一吨钢材所 需的费用见下表，问如何调运才能使总运费降到最低？ 工厂 B1 仓库A1 仓库A2 仓库A3 2 1 8 工厂 B2 9 3 4 工厂 B3 10 4 2 工厂 B4 7 2 5 库存量 9 5 7
B1
A1 A2 … Am 需求量 c11 c21 … cm1 b1
B2
c12 c22 … cm2 b2
…
… … … … …
Bn
c1n c2n … cmn bn
供应量
a1 a2 … am
2. 运输问题的数学模型
min z cij xij
i 1 j 1 m n
n xij ai ( i 1, 2, ......m ) j 1 m s.t . xij b j ( j 1, 2, ......n) i 1 xij 0, i 1, 2, ......m , j 1, 2, ......n
B1
B2
B3
X13
B4
B5
X15
A1 A2 A3 A4
X31 X41
X33 X45
B1 A1 A2 A3 A4
B2
X12
B3
B4
X14
B5
X32
X34
B1 A1 A2 A3 A4
B2
B3
X13
B4
B5
X15
X31 X41 X43
X35
B1
A1 A2 A3 A4
X11 X21
B2
X12 X22
m行
n行
1. 2. 3. 4.
矩阵A是一个m+n行mn列的矩阵，它的秩为m+n-1。 运输问题应该有m+n-1个基变量。 系数矩阵非常稀疏。 xij的系数列向量为：
Pij (0....1...0....1...0)T ei em j
3. 运输问题的特征
特征1：运输问题一定有可行解； 特征2：运输问题一定有最优解； 特征3：运输问题每一组基对应 m+n-1个基变量； 特征4：运输问题的 m+n-1个基变量构成的变量组不含 闭回路； 特征5：任意一个非基变量和 m+n-1个基变量组成的变 量组中必定存在一条并且只存在唯一一条闭回路； 特征6：如果运输问题中的供应量和需求量都是整数， 则任一基解中各变量的取值也都是整数。
3 Vogel 法
西北角法(左上角法)
B1 A1 A2 2 9
B2
B3 10 7 2
B4
库存量 9 5
-3 -6
3
1 3
6
4
-2 -3
2
A3
需求量
3
2 5 7
-1 -6
8
3
-3
4
8
1
-6 -2 -3 -1
6
-6
4
6
对应的总运费为
z 1= 2×3 + 9×6 + 3×2 + 4×3 + 2×1 + 5×6 = 110
北京物资学院运筹学教学课件
第三章 运输问题
北京物资学院信息学院 2017年4月
本章主要内容
第一节 运输问题的数学模型及其特征
第二节 运输问题的求解—表上作业法
第三节 产销不平衡的运输问题及应用
第一节

运输问题的数学模型及其特征
运输问题的定义
2. 运输问题的数学模型
3. 运输问题的特征
1. 运输问题的定义
第一步：编制初始调运方案 要求得运输问题的初始基可行解，必须保证找到 m+n–1 个基变量.
运输问题的任意m+n-1个变量构成一组基变量的充要条 件是变量组中不含闭回路.
关键:找出m+n-1个不含闭回路的变量。 问题：如何使得一个选定的变量不包含在闭回路中？ 1 西北角法（左上角法）
2 最小元素法
B3
B4
X24
B5
X42
X44
（1）每个顶点都是转折点；
（ 2 ）闭回路是一条闭合的折线，每一条边都是水 平或垂直的；
（3）闭回路上同一行（列）的顶点有偶数个。
闭回路上的点对应的系数列向量线性相关。
Plk
Pij Puj 由于 Pik
Pls
Pus
Pij ei em j
Pij Pik Plk Pls Pus Puj 0
容易证明
第二节 运输问题的求解--表上作业法
表上作业法的基本步骤：
第一步：编制初始调运方案，即寻找第一个基可行解；
第二步：计算各非基变量的检验数；
第三步：判断当前的调运方案是否是最优方案，如果已经 是最优，则算法结束，问题已经解决；否则，转第四步；
第四步：确定进基变量和出基变量，调整非最优的调运 方案，获得更好的调运方案；转第二步。
最小元素法
B1 B2 B3 B4 库存量
A1 A2
A3 需求量
2 1
9
10
7
9 -4
-5
5
3 4
2
4
2 5 -3-2
3
8 3 4 5
2
7 -4 6
-3
3
-3 -3
-5
4
-4
8
4
-2
-4
对应的总运费为
z 2= 9×5 + 7×4 + 1×3 + 2×2 + 4×3 + 2×4 = 100
闭回路
定义：凡是能够排列成下列序列的一组变量的集合就 称为运输问题的一个闭回路。
xi1 j1 , xi1 j2 , xi2 j2 , xi2 j3 ,
或
, xis js , xis j1
xi1 j1 , xi2 j1 , xi2 j2 , xi3 j2 ,
, xis js , xi1 js
并称集合中每一个变量为此闭回路的一个顶点；称连 接相邻两个变量（顶点）以及连接最后一个顶点和第 一个顶点的线段为此闭回路的边。
需求量
3
8
4
6
运输问题：有 m 个供应点向 n 个需求点供应某种物资，这 m 个供应点A1、A2、…...Am的供应量分别为a1、a2、…...am；n 个需求点 B1、B2、…...Bn 的需求量分别为 b1、b2、…...bn； 已知从任一供应点Ai向任一需求点Bj运输一个单位物资的费 用为cij。问采取什么样的物资调运方案才能使总运费最省？