当前位置：文档之家 › 运筹学第3章-运输问题特殊的线性规划

运筹学第3章-运输问题特殊的线性规划

  • 格式：ppt
  • 大小：1.24 MB
  • 文档页数：42

下载文档原格式

  / 42

合集下载

运筹学(第四版)：第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) 用最小元素法给出的初始解，是从单位运价表中逐次地

运筹学第3章：运输问题-数学模型及其解法

运筹学第3章：运输问题-数学模型及其解法

整数规划模型
01
整数规划模型是线性规划模型 的扩展，它要求所有变量都是 整数。
02
整数规划模型适用于解决离散 变量问题，例如车辆路径问题 、排班问题等。
03
在运输问题中，整数规划模型 可以用于解决车辆调度、装载 等问题，以确保运输过程中的 成本和时间效益达到最优。
混合整数规划模型
混合整数规划模型是整数规划和线性规划的结合，它同时包含整数变量和 连续变量。
运筹学第3章：运输问题-数学模 型及其解法
目录
• 引言 • 运输问题的数学模型 • 运输问题的解法 • 运输问题的应用案例 • 结论
01 引言
运输问题的定义与重要性
定义
运输问题是一种线性规划问题，主要 解决如何将一定数量的资源（如货物 、人员等）从起始地点运送到目标地 点，以最小化总运输成本。
总结词
资源分配优化是运输问题在资源管理 领域的应用，主要解决如何将有限的 资源合理地分配到各个部门或项目， 以最大化整体效益。
详细描述
资源分配优化需要考虑资源的数量、 质量、成本等多个因素，通过建立运 输问题的数学模型，可以找到最优的 资源分配方案，提高资源利用效率， 最大化整体效益。
05 结论
运输问题的发展趋势与挑战
生产计划优化
总结词
生产计划优化是运输问题在生产领域的应用，主要解决如何合理安排生产计划， 满足市场需求的同时降低生产成本。
详细描述
生产计划优化需要考虑原材料的采购、产品的生产、成品的销售等多个环节，通 过建立运输问题的数学模型，可以找到最优的生产计划和调度方案，提高生产效 率，降低生产成本。
资源分配优化
发展趋势
随着物流行业的快速发展，运输问题变得越来越复杂，需要更高级的数学模型和算法来 解决。同时，随着大数据和人工智能技术的应用，运输问题的解决方案将更加智能化和

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

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

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

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

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

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

运筹学第三章 运输问题

运筹学第三章 运输问题

销地 产地 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

运筹学 第三章 运输问题

运筹学 第三章 运输问题
（或者在同时划去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

运筹学【运输问题】考研必备

运筹学【运输问题】考研必备

22
13
12 0
最小元素法(2)
1 6 1 8 2 5 3 22 9 4 7
2 5
3 3
4 14 1
132 712来自10 62715
19 13 12 0 13 0
最小元素法(3)
1 6 1 8 2 5 3 22 9 4 7
2 5
3 3
4 14 1
13
2 7
13
10
12
6
27
2
19 13 0 12 0 13 0
解: 西北角法
销地 产地
B1 6 4 7 2
B2 5 4 6 4
B3 3 7 5 3
B4 4 5 8 4
产量
A1 A2 A3
销量
4 6 3 13
(1) 从图的西北角开始, 填入a1与b1较小的值,b1=2, 即从A1运 给B1(2吨)B1已满足, 划去b1列, 并将a1=4-2=2
销地 产地
B1 26 4 7 2-2
例2
供应地 运价 销售地 1 a1=14 供 应 量 1 6 7 5
b1=22
a2=27
2
a3=19
3
3 8 4 2 7 5 9 10 6
2
b2=13
销 售 量
3
b3=12
4
b4=13
解:
初始基础可行解—最小元素法(1)
1 1 6 7
2 5
3 3
4 14
2
8
4
2
7
27
15
12
3 5 9 10 6 19 13
如何调运产品才能使总运费最小？
销地 产地
B1 6 4 7 2
B2 5 4 6 4

运筹学：运输问题

运筹学：运输问题

运输问题运输问题（transportation problem）一般是研究把某种商品从若干个产地运至若干个销地而使总运费最小的一类问题。

然而从更广义上讲，运输问题是具有一定模型特征的线性规划问题。

它不仅可以用来求解商品的调运问题，还可以解决诸多非商品调运问题。

运输问题是一种特殊的线性规划问题，由于其技术系数矩阵具有特殊的结构，这就有可能找到比一般单纯形法更简便高效的求解方法，这正是单独研究运输问题的目的所在。

§1运输问题的数学模型[例4-1] 某公司经营某种产品，该公司下设A、B、C三个生产厂，甲、乙、丙、丁四个销售点。

公司每天把三个工厂生产的产品分别运往四个销售点，由于各工厂到各销售点的路程不同，所以单位产品的运费也就不同案。

各工厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如表4-1所示。

问该公司应如何调运产品，在满足各销售点需要的前提下，使总运费最小。

表4-1设代表从第个产地到第个销地的运输量（；），用代表从第个产地到第个销地的运价，于是可构造如下数学模型：（；运出的商品总量等于其产量）（；运来的商品总量等于其销量）通过该引例的数学模型，我们可以得出运输问题是一种特殊的线性规划问题的结论，其特殊性就在于技术系数矩阵是由“1”和“0”两个元素构成的。

将该引例的数学模型做一般性推广，即可得到有个产地、个销地的运输问题的一般模型。

注意：在此仅限于探讨总产量等于总销量的产销平衡运输问题，而产销不平衡运输问题将在本章的后续内容中探讨。

（；运出的商品总量等于其产量）（；运来的商品总量等于其销量）供应约束确保从任何一个产地运出的商品等于其产量，需求约束保证运至任何一个销地的商品等于其需求。

除非负约束外，运输问题约束条件的个数是产地与销地的数量和，即；而决策变量个数是二者的积，即。

由于在这个约束条件中，隐含着一个总产量等于总销量的关系式，所以相互独立的约束条件的个数是个。

运筹学教材编写组《运筹学》章节题库-运输问题(圣才出品)

运筹学教材编写组《运筹学》章节题库-运输问题(圣才出品)

需进行进一步调整。
利用闭回路法进行解的改进。
在初始方案表中以（丙，A）出发作一闭回路，利用闭回路进行调整，得到的结果如表
3-4 所示：
表 3-4
A
B
C
D
供应量
甲
7
6
483Leabharlann M145 / 41
圣才电子书 十万种考研考证电子书、题库视频学习平台

乙
10 5
6
6
8
M
16
丙
0
3
四、简答题 1．用表上作业法解运输问题时，在什么情况下会出现退化解?当出现退化解时如何处理? 答：当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中 间有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。 当出现退化时，为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的 一行或一列中的某个格中填入数字 0，表示这个格中的变量是取值为 0 的基变量，使迭代过 程中基变量个数恰好为（m+n-1）个。
采用最小元素法得初始调运方案如表 3-2 所示：（因为基格个数=7-1=6 个，故在一空
格中填入 0）
表 3-2
A
B
C
D
供应量
甲
7
6
48
3
M
14
乙
10 5
6
6
8
M
16
丙
3
50
8 15 7
15
4 / 41
圣才电子书 十万种考研考证电子书、题库视频学习平台

需求量
10
12
2．一个运输问题，如果其单位运价表的某一行元素分别加上一个常数，最优调运方案 是否发生变化，试说明理由(用表或直接用公式)；[武汉大学 2007 研]

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

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

二、表上作业法
计算步骤：
(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

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

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

供 = 5 应 地 = 2 约 = 3 束 = 2 = 3 需 求 = 1 地 = 4 约 束 ≥ 0
第二节 表上作业法求初始解、 初始值 一、西北角法 （梯形下降）
运价 收点
（元/吨）
B1 B2 B3 B4
4 18 30 0 14 4 4
发量 （吨）
4
0 0 0
发点
A1
2
12 5 20 25
10
015 4 20
4
第二节 表上作业法求初始解、 初始值 初始解： 初始值：
X12=4吨 • S0=4×12+4×10+1×25+6×15 X14=4吨 • +4×14+1×18 X22=1吨 X23=6吨 •=48+40+25+90+56+18 X31=4吨 X32=1吨 • =277元<329元（起点优于西北角法） 变量个数=行数加列数减1 20吨
发量 5 （吨）
3 1 0《产大于需》增加源自5虚拟收点B1 B2 B3 B4 B
2 1
（元/吨）
4
A1 A2 A3
收 量（吨）
2 10 7
0
311
3
2 4
4
3 9 3 2 6 0
0 7 0 5 0 7
0
2
0
3 8
0
5 1
3 0
2 4
0
2
3
4
19
初 始 可 行 解 ： 初 始 值 ： S0=22+41+04+33+92+14 C 23 X11=2吨 +23=45元 C12 X14=1吨 =11-4+9-3>0； = 5-9+2-1=C 25 C13 3 X15=4吨 C 21 X22=3吨 =3-4+2-1=0 C31 ； = 0-0+4-9=5 C 32 C 35 X24=2吨 Cij C25 5； X25 进基 X33=4吨 =10-2+4-9>0； =7-2+4-2>0 X34=3吨

运筹学 第3章 运输问题

运筹学 第3章 运输问题

第三章运输问题在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。

这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。

但由于其模型结构特殊，学者们提供了更为简便和直观的解法—-表上作业法。

此外,有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。

第一节运输问题及其数学模型首先来分析下面的问题。

例3。

1农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。

三个收购站A1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70kt和70kt。

已知各收购站到各纺织厂的单位运价如表3-1所示（单位：千元/kt)，问如何安排运输方案，使得经销公司的总运费最少?设x ij表示从A i运往B j的棉花数量，则其运输量表如下表所示。

表3—2由于总供应量等于总需求量，因此，一方面从某收购站运往各纺织厂的总棉花数量等该收购站的供应量，即x11+x12+x13 = 50x21+x22+x23 = 45x31+x32+x33 = 65另一方面从各收购站运往某纺织厂的总棉花数量等该纺织厂的需要量,即x 11+x 21+x 31 = 20 x 12+x 22+x 32 = 70 x 13+x 23+x 33 = 70因此有该问题的数学模型为min f= 4x 11+8x 12+5x 13+6x 21+3x 22+6x 23+2x 31+5x 32+7x 33x 11+x 12+x 13 = 50 x 21+x 22+x 23 = 45 x 31+x 32+x 33 = 65 x 11+x 21+x 31 = 20 x 12+x 22+x 32 = 70 x 13+x 23+x 33 = 70x ij ≥0，i=1，2，3；j=1，2，3 生产实际中的一般的运输问题可用以下数学语言描述。

管理运筹学讲义 第3章 运输问题(6学时)

管理运筹学讲义 第3章 运输问题(6学时)
m行 n行
... 1
其系数列向量的结构是：
A ij (0,..., 0,1, 0,..., 0,1, 0,..., 0) T , 除第i个和第（m j）个分量为 1外，其他分量全等于零。因此，运输问题具有以下特点： 约束条件系数矩阵的元素为0或1； 约束矩阵每一列都有两个非零元素，这对应于每一个变量在 前m个约束方程中出现一次，在后n个约束方程中出现一次。
Ai
Bj
表 3－ 5
B1 x11 C11 x21
B2 x12 C12 x22 C22 x31 x32 C32 b2
运价表（元/吨） B4 产量
A3
需要量
3 5 4 5
2 3 1 7
6 8 2 8
3 2 9 3
10 8 5 23
解:设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 x11 x12 x13 x14 10 x11 x21 x31 5 x x x 7 12 22 32 x x x x 8 21 22 23 24 x13 x23 x33 8 x x x x 5 31 32 33 34 x14 x24 x34 3
下表中填有数字的格为基变量，它们对应的约束 方程组的系数列向量线型无关：
B1
4
B2
12

管理运筹学

管理运筹学
第三章 运输问题
3.1 运输问题的数学模型 3.2 表上作业法 3.3 不平衡的运输问题 3.4 运输问题的实际案例
概 述： 运输问题(The Transportation Problem, TP)是 运输问题 是 一类特殊而且极其典型的线性规划问题。 一类特殊而且极其典型的线性规划问题。 运输问题可用单纯形法来求解。 运输问题可用单纯形法来求解。由于运输问题 数学模型具有特殊的结构， 数学模型具有特殊的结构，存在一种更简便的 计算方法 表上作业法——实质仍是单纯形法。 实质仍是单纯形法。 表上作业法 实质仍是单纯形法 从运输问题的解决及表上作业法的理论解释， 从运输问题的解决及表上作业法的理论解释， 我们可更充分体会到单纯形法的魅力。 我们可更充分体会到单纯形法的魅力。
3.1 运输问题的数学模型
运输问题的数学模型； 运输问题的数学模型； 运输问题数学模型的特点； 运输问题数学模型的特点； 运输问题解的情况. 运输问题解的情况
一、运输问题的数学模型 1、实际案例 、 设某种物资有3个产地 设某种物资有 个产地 A1，A2，A3， 生产量分别 个销地B 为9，5，7;有4个销地 1，B2，B3，B4 ，销售量分 ， ， 有 个销地 别为3， ， ， 已知从 已知从A 别为 ，8，4，6 ;已知从 i到Bj 物资的单位运价见 下表。求总运费最小的调运方案。 下表。求总运费最小的调运方案。 B1 A1 A2 A3 销量 2 1 8 3 B2 9 3 4 8 B3 10 4 2 4 B4 7 2 5 6 产量 9 5 7
x11 x12 x1n 1 1 1 D= Ａ= 1 1 1
x21 x22 x2n ... xm1 xm2 xmn 1 1 1 1 1 1 1 1 1 1 1 1
a1 a2 am b 1 b2 bn

运筹学 第三章 运输问题

运筹学 第三章 运输问题
判别的方法是计算空格（非基变量）的检 验数，若所有的检验数都大于等于0，为最优 解。
1）闭环回路法： 在给出的初始调运方案表上，从每一空格 出发找一条闭环回路，它是以某空格为起点 ，用水平或垂直线向前划，每碰到一数字格 转90°后（回路的转角点必须是一个基变量 ） ，继续前进，直到回到起始空格为止。 从每一空格出发一定存在且只有唯一的闭 环回路。 从空格开始加减闭环各个顶点的运输单价 ，可得每个空格对应的检验数。
《运筹学》
第三章 运输问题
Slide 16
销地
B1
产地
A1
A2
3
A3
销量 3
B2 B3
4 1 6
65
B4 产量
37
4
39
6
销地
产地
B1 B2 B3 B4
A1
3 11 3 10
A2
19 2 8
A3
7 4 10 5
空格 (11) (12) (22) (24) (31) (33)
闭环回路 (11)－(21)－(23)－(13)－(11) (12)－(32)－(34)－(14)－(12) (22)－(32)－(34)－(14)－(13) －(23)－(22) (24)－(14)－(13)－(23)－(24) (31)－(34)－(14)－(13)－(23) －(21)－(31) (33)－(34)－(14)－(13)－(33)
基变量：
X13 U1+V3=C13=3
X14 U1+V4=C14=10
X21 U2+V1=C21=1
1
3 10 U1=0
2
U2=-1
X23 U2+V3=C23=2
4

管理运筹学讲义 第3章 运输问题

管理运筹学讲义 第3章 运输问题

21
石家庄经济学院
管理科学与工程学院
§3.2.1 初始基本可行解的确定
与一般线性规划问题不同，产销平衡运输问题总是存在 可行解。不难验证
xij ai b j d
≥
0 (i 1,2,, m; j 1,2,, n; d ai b j )
i 1 j 1
m
n
就是模型（3-1）的可行解。又因，目标函数值有下界， 故产销平衡的运输问题必有最优解。
A1、 A2、 A3 ，有四个销售点 B1、 B2、B3、 B4 销售
这种化工产品。各产地的产量、各销地的销量和各
产地运往各销地每吨产品的运费（百元）如下表所
示。
30 石家庄经济学院 管理科学与工程学院
产销平衡表
运价表
销 产
A1 A2
B1
B2
B3
B4
产量 75 40
B1 3 2
B2 8 9
B3 5 4
27
石家庄经济学院
管理科学与工程学院
销地 产地 A1 A2 A3 销量
B1 3 1 7 3
B2 11 9 4 6
B3 3 2 10 5
B4 10 8 5 6
产量 7 4 9 20 （产销平衡）
问应如何调运，可使得总运输费最小?
28
石家庄经济学院
管理科学与工程学院
产销平衡表
运价表
销 产 A1 A2 A3 需求
B4 9 8
A3
需求 35 40 55 65
80
195
6
3
7
5
问应如何调运，可使得总运输费最小?
31 石家庄经济学院 管理科学与工程学院
解：用西北角法求初始基本可行解

运筹学第3章

运筹学第3章
§3.1 §3.2 §3.3 §3.4 §3.5 运输问题模型 表上作业法 特殊情况的处理 图上作业法 指派问题
§3.2 表上作业法
运输表上任何有序的至少四个以上 不同格被称为圈, 如果它们满足:
任何两个接续格在同一行或同一列； 在同一行或同一列不存在三个或三个 以上的接续格; 最后一个格应和第一个格在同一行或 同一列。
§3.3 特殊情况的处理
例3·：某农场有四种土壤，面积分别为 6 500亩、1000亩、600亩和500亩，准备将不 同的三个小麦品种播在这四种土壤上。根据 市场需求和本场的具体情况，确定这三个品 种的播种面积分别为400亩、1000亩和1200 亩，又根据过去的生产规律和未来气候的变 化以及生产物资供应的保证情况，用多元回 归方程预测得不同品种的小麦播在不同土壤 上的亩产量（公斤）如后表所示，问怎样安 排播种才能使小麦的总产量最高？
x21 x22 x23 27
s.t.
xij 0, (i 1, 2; j 1, 2,3)
例3·：一般运输问题 2 一般的运输问题可以描述为: 有 m 个供应点, n 个需求点, 第 i 个供应点的 供应量 ai ,第 j 个需求点的需求量 bj , 从 i 到 j的运费为 cij, 求费用最小的运输方 案。
6
35 10
5
0 2
工厂2 25
10
12
7
vj
8
仓库一
5
仓库三
仓库二
ui
工厂1 工厂2
7
15 10
17 +
- 174 0 6
6 12
18 35 - 10+ 27
5
5 7
0 2
25 8
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
（1）选择一个xij，令xij= min{ai，bj}=
baij第满i足个第产j地个的销产地量需全求部运到第j个销地
将具体数值填入xij在表中的位置；
（2）调整产销剩余数量：从ai和bj中分别减去 xij的值，若ai-xij=0，则划去产地Ai所在的行，即 该产地产量已全部运出无剩余，而销地Bj尚有 需求缺口bj-ai；若bj-xij =0，则划去销地Bj所在 的列，说明该销地需求已得到满足，而产地Ai 尚有存余量ai-bj；
1、闭回路法
以确定了初始调运方案的作业表为基础，以一个非 基变量作为起始顶点，寻求闭回路。
该闭回路的特点是：除了起始顶点是非基变量外， 其他顶点均为基变量（对应着填上数值的格）。
可以证明，如果对闭回路的方向不加区别，对于每 一个非基变量而言，以其为起点的闭回路存在且唯 一。
闭回路法计算非基变量xij检验数的公式： ij =（闭回路上奇数次顶点运距或运价之和）-
-（闭回路上偶数次顶点运距或运价之和）
位势法计算非基变量xij检验数的公式
ij cij ui v j
四、方案调整
当至少有一个非基变量的检验数是负值时， 说明作业表上当前的调运方案不是最优的，应 进行调整。
若检验数 ij 小于零，则首先在作业表上以xij
为起始变量作出闭回路，并求出调整量ε：
输问题，再用表上作业法求出最优调运方
案。
如何转化 ？
第一步，将产地、转运点、销地重新编排， 转运点既作为产地又作为销地；
第二步，各地之间的运距（或运价）在原 问题运距（运价）表基础上进行扩展：从 一地运往自身的单位运距（运价）记为零， 不存在运输线路的则记为M（一个足够大 的正数）；
第三步，由于经过转运点的物资量既 是该点作为销地的需求量，又是该点 作为产地时的供应量，但事先又无法 获取该数量的确切值，因此通常将调 运总量作为该数值的上界。
3、举例
例1： 产量：A1-7t，A2-4t，A3-9t 销量：B1-3t，B2-6t，B3-5t，B4-6t ； 求使总运输量最少的调运方案。
Bj B1 B2 B3 B4 产量
Ai
A1
3
11
3
10
7
A2
1
9
2
8
4
A3
7
4
10
5
9
需量 3
6
5
6
20
1、最小元素法: 求出初始方案。
& 最小元素法的基本思想是“就近供应”
A2
c21 c22 … c2n
┆
… ……
Am
cm1 cm2 … cm n
产量
a1 a2 ┆ am
销量
b1 b2 … bn
m
n
ai bj
i 1
j 1
单位根据具体问题选择确定。
2、运输问题的数学模型
设xij为从产地Ai运往销地Bj的物资数量 （i=1，…m；j=1，…n），由于从Ai 运出的物资总量应等于Ai的产量ai，因此 xij应满足：
例1：产量：A1-7t，A2-4t，A3-9t 销量：B1-3t，B2-6t，B3-5t，B4-6t
Bj B1 B2 B3 B4 产量
Ai
A1
3
11
3
10
7
A2
1
9
2
8
4
A3
7
4
10
5
9
需量 3
6
5
6
20
产销平衡、单位运价表（表3-1）
单位 运价 销 或运距 地
产地
B1 B2 … Bn
A1
c11 c12 … c1 n
（10
6 5 6 20
）
需 3 6 5 6 20
量
检验数
B1 B2 B3 B4 产量
A1
×
×
4
3
7
（1） （2）
A2
3
×
1
×
4
（1）
（－1）
A3
×
6
×
3
9
（10）
（12）
需量
3
6
5
6
20
2、位势法
以例1初始调运方案为例，设置位势变量
和 ui ， v j 在初始调运方案表的基础上增
加一行和一列。
Bj Ai
改进调整 （换基迭代）
最优方案
图3-1 运输问题求解思路图
二、 初始方案的确定
1、作业表（产销平衡表） 初始方案就是初始基本可行解。 将运输问题的有关信息表和决策变量——调运 量结合在一起构成“作业表”（产销平衡表）。 表3-2是两个产地、三个销地的运输问题作业表。
表3-2 运输问题作业表（产销平衡表）
3.2 运输问题的表上作业法
一、表上作业法的基本思想是:先设法给出 一个初始方案,然后根据确定的判别准则对初 始方案进行检查、调整、改进，直至求出最 优方案，如图3-1所示。
表上作业法和单纯形法的求解思想完全一致， 但是具体作法更加简捷。
确定初始方案 (初始
基本可行解)
判定是否 最 优？
否
是 结束
对于产地和销地也作类似的处理。
P101:3.1
作业
Thanks for Attention!
Q and A
Ai
B 2
B 3
B 4
产 量
A1 3 11 3 10 7
A ×× 5 2 7
A2 1 9 2 8 4
1 A 3 ×× 1 4
A3 7 4 10 5 9
2
需量 3 6 5 6 2 0
A×6×3 9 3
列差
需 3 6 5 6 20
额
量
三、最优性检验
检查当前调运方案是不是最优方案的过 程就是最优性检验。检查的方法：计算非基 变量（未填上数值的格，即空格）的检验数 （也称为空格的检验数），若全部大于等于 零，则该方案就是最优调运方案，否则就应 进行调整。
方案调整—闭回路法
B1 B2 B3 B4 产量
A1
×
×
4
3
7
（1） （2）
A2
3
×
1
×
4
（1）
（－1）
A3
×
6
×
3
9
（10）
（12）
需量
3
6
5
6
20
调整结果
B1 B2 B3 B4 产量
A1
×
×
5
2
7
（0） （2）
A2
3
×
×
1
4
（2） （1）
A3
×
6
×
3
9
（9）
（12）
需量
3
6
5
6
20
复习比较检验数计算的两种方法 闭回路法计算非基变量xij检验数的公式： ij =（闭回路上奇数次顶点运距或运价之和）
m行 n行
1 1 1
11 1
1 1 1
1
1
1
1
1
1
1
1
1
❖ 矩阵的元素均为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阶单位阵。
用最小元素法确定例1初始调运方案
Bj B1
Ai
A1
3
A2 3 1
A3
7
需量 3
B2 B3
11 9 64 6
43 12
10 45
B4
3 10 8
35 36
产量
7
3
41 39
20
最小元素法实施步骤口诀 《运价表》上找最小，《平衡表》上定产销；
满足销量划去“列”，修改“行产”要记牢； （满足产量划去“行”，修改“列销”要记牢） 划去列(行)对《运价》， 修改“行产(列销)”在《产销》； 余表再来找最小，方案很快就找到。
j1
s.t. m xij b j
j 1, , n
i1
xij 0, i 1, m; j 1, , n
m
n
ai bj
i1
j 1
产销平衡条件
二、运输问题的特点与性质
1．约束方程组的系数矩阵具有特殊的结构
写出式（3-1）的系数矩阵A，形式如下：
x11, x12 , , x1n ; x21, x22 , x2n , , , , , xm1 , xm2 , xmn
B1
B2
B3
B4
ui
A1
3
11
3
10
u1
A2
1
9
2
8
u2
A3
7
4
10
5
u3
vj
v1

v2
v3
v4
检验数
各空格的检验数，令 ij 代表空格（Ai ,Bj）
的检验数。
ij cij ui v j
①当检验数还存在负检验数时，说明未得到最 优解，还可以改进。 ②如果表中出现有负的检验数时，对方案进行 改进和调整的方法同前面闭回路法调整一样。
n
xij ai
j 1
i 1,2, , m
同理，运到Bj的物资总量应该等于Bj 的销量bj，所以xij还应满足：
m
xij bj
i 1
j 1, , n
总运费为：