当前位置：文档之家 › 《运筹学》第三章 运输问题

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

  • 格式：ppt
  • 大小：1.04 MB
  • 文档页数：48

下载文档原格式

  / 48

合集下载

运筹学胡运权第三版第三章运输问题

运筹学胡运权第三版第三章运输问题

产销平衡运输问题的数学模型可表示如下：
§1运 输 问 题 及 其 数 学 模 型
二、运输问题数学模型的特点： 运输问题一定有最优解；基变量的个数=m+n-1 运输问题约束条件的系数矩阵：
x1m
x2m
xm1
xmm
x11
x12
…
x21
x22
…
xm2
…
…
m行
n行
§1运 输 问 题 及 其 数 学 模 型
解 的 最 优 性 检 验
运输问题及其数学模型
用表上作业法求解运输问题
运输问题的进一步讨论
应用问题举例
本章内容
3运输问题进一步讨论
01.
产销不平衡的运输问题 有转运的运输问题
02.
1.当产大于销时，即 产销不平衡问题 平衡后的数学模型为： 加入假想销地（假想仓库），销量为 ，由于实际并不运 送，它们的运费为 = 0；
解 的 最 优 性 检 验
解 的 最 优 性 检 验
销地产地
B1
B2
B3
B4
产量
ui
A1
16
u1(1)
A2
10
u2(0)
A3
22
u3(-4)
销量
8
14
12
14
48
vj
v1(2)
v2(9)
v3(3)
v4(10)
4
2
8
12
5
4
10
11
3
9
6
11
表3-9
1.增加一位势列和位势行并计算位势
其中
8
10
2
6
8
产量
A1
运筹学第3章：运输问题-数学模型及其解法

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


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

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


闭合回路法的优点是能够找到全局最 优解，适用于大型复杂运输问题。但 该方法的计算复杂度较高，需要较长 的计算时间。
商位法
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
运筹学-第三章-运输问题ppt课件

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

45
46
首先建立电子表格
47
区域名称
产量 单位运价 实际产量 实际销量 销量 运输量 总费用
单元格 I9:I11 C4:F6 G9:G11 C12:F12 C14:F14 C9:F11
I14
48
49
Excel 求解结果为：
50
9
§3-2 表上作业法(运输单纯形法)
表上作业法的计算步骤： 1. 确定初始方案，即找出初始基可行解； 2. 求非基变量检验数，判断最优； 3. 用闭回路法调整； 4. 重复2, 3 ，直至求出最优解。
10
一、确定初始基可行解(两种方法)
1. 最小元素法(“就近调运”) 1)找到运价中最小的元素，确定供销关系；
34
解：
v 该问题要求满足不同顾客的需求(采购量)，即最小采购 量实际供给量最大采购量。三个工厂的总产量为20000件， 4个顾客的最低采购量为12000件，最高采购量为30000件， 大于总产量。为保持产销平衡，虚拟一个工厂4，其产量 为10000件。
v 由于每个顾客的需求分为必须满足和不一定满足两部分， 故将其视为两个顾客。必须满足的顾客其采购量不能由虚 拟工厂提供，令其单位利润为M (M为任意大正数)，不 一定满足的顾客其采购量能由虚拟工厂提供，令其单位利 润为0。由此可得该问题的产销平衡及单位利润表，如表324所示。
§3-1 运输问题的数学模型
一、示例 例1
4
二、运输问题描述
v 有m 个产地Ai ，产量为 ai, i=1,2, …m (sources) v 供n 个销地 Bj , 需求量 bj, j=1,2, …n (destinations)
v 已知 Ai到 Bj的单位运价为 cij v 问如何调运使总运费最小？
运筹学 第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生产实际中的一般的运输问题可用以下数学语言描述。

运筹学 第三章 运输问题

运筹学 第三章 运输问题

• 设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

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


销量 3 6 5 6
A1 A2 A3
销量
B1 B1 B3 B4
2 1
6
5
3 3
3656
产量
7 4 9
精品课件
24
例：
B1 B2 B3 B4 产量
A1 (1) (2) 4 2 6 A2 3 (1) 2 (-1) 5 A3 (10) 6 (12) 3 9 销量 3 6 6 5
B1 B2 B3 B4 产量
(3) 在进行调运方案改进时，若沿闭合回路出现多个可作为 调出变量的数字格（即闭回路上的数字格最小值有多 个），此时，任选一个为调出变量，其余的填0，保证调 整后的调运方案中仍有m+n-1个数字格。
精品课件
23
例：
B1 B1 B3 B4 产量
A1 (0) (2) 5 2 7 A2 3 (2) (1) 1 4 A3 (9) 6 (12) 3 9
产 销 平 衡 表
单 位 运 价 表
精品课件
7
一般模 型表示 (ai=bj)
精品课件
8
三、模型的特点
1.变量数：mn个 2.约束方程数：m+n个
最大独立方程数：m+n-1 3.系数列向量结构：
0
Pij= 1 ——第i个分量
1 ——第m+j个分量 0
…… …
精品课件
9
······
······
x11 x12 ······ x1n x21 x22 ······ x2n ,············, xm1 xm2 ······ xmn
第3章 运输问题
精品课件
1
3.1 运输问题的典例和数学模型 3.2 运输问题的求解方法：表上作业 法 3.3 几类特殊的运输问题

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


一、典例
某食品公司经营糖果业务，公司下设三个工厂A1、A2、 A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产 量、销售量及调运时的单位运输费用情况。问：如何调运可 使总费用最小？
生产量：A1——7吨， A2 —— 4吨， A3 —— 9吨
销售量：B1 —— 3吨，B2 —— 6吨，B3 —— 5吨，B4 —— 6吨
销地
产地
B1
B2
A1
3
11
A2
1
9
A3
7
4
B3
B4
3
10
2
8
10
5
精品课件
4
7吨 A1
产 4吨 A2 地
调运示意图
x11
B1 3吨
B2 6吨
销
B3 5吨
地
9吨 A3
x34
B4 6吨
精品课件
5
二、建立模型
设 xij——第i产地到第j销地之间的调运量，则有
34
Min z =
cij· xij i=1 j=1
销量 3 6 5 6
单位运价表
B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5
△z=c11-c13+c23-c21=1=11 △z=c12-c14+c34-c32=2=12
ห้องสมุดไป่ตู้
B1 B2 B3 B4 产量
A1 (0) (2) 5 2 7 A2 3 (2) (1) 1 4 A3 (9) 6 (12) 3 9 销量 3 6 5 6
j=1 0 ······ 0
·· ·· ···· ·· ··
·· ·· ··

运筹学第3章运输问题

运筹学第3章运输问题第1节运输问题的数学模型第2节表上作业法钱颂迪制作运筹学（第三版）《运筹学》教材编写组第3章运输问题清华大学出版社第3章运输问题第1节运输问题的数学模型第2节表上作业法第3节产销不平衡的运输问题及其求解方法第4节应用举例第1节运输问题的数学模型已知有m个生产地点Ai,i=1,2,…，m。

可供应某种物资，其供应量(产量)分别为ai，i=1，2，…，m，有n个销地Bj，j=1,2,…,n，其需要量分别为bj，j=1,2,…,n，从Ai到Bj运输单位物资的运价(单价)为cij，这些数据可汇总于产销平衡表和单位运价表中，见表3-1，表3-2。

有时可把这两表合二为一。

表3-1销地产地1 2 ┉ n产量12┆mA 1A2┆Am销量B1 B2 ┈ BNn表3-2若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型这就是运输问题的数学模型。

它包含m×n个变量，(m+n)个约束方程。

其系数矩阵的结构比较松散，且特殊。

该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。

即Pij=(0,… ,1,0,…,0,1,0,…,0)T=ei+em+j对产销平衡的运输问题，由于有以下关系式存在：第2节表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。

但具体计算和术语有所不同。

可归纳为：(1) 找出初始基可行解。

即在(m×n)产销平衡表上用西北角法或最小元素法，Vogel法给出m+n-1个数字，称为数字格。

它们就是初始基变量的取值。

(2) 求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。

如已是最优解，则停止计算，否则转到下一步。

(3) 确定换入变量和换出变量，找出新的基可行解。

在表上用闭回路法调整。

(4) 重复(2)，(3)直到得到最优解为止。

例 1 某公司经销甲产品。

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


3
4 总供应量60吨
第三章 运输问题
d4=13 总需求量60吨
2
供求平衡的运输问题
一、运输问题线性规划模型
1、运输问题的一般提法 、
收点 发点
B1 9 11 14 4
B2 18 6 12 9
B3 1 8 2 7
B4 10 18 16 5
发量
A1 A2 A3
收量
9 10 6
（供需平衡） 供需平衡） 问：如何合理调运，才能使总运费最少？ 如何合理调运，才能使总运费最少？
第三章 运输问题
3
为发点运往收点的运输量.i=1,2,3 设Xij 为发点运往收点的运输量.i=1,2,3 j=1,2,3,4
minZ=9X11+18X12+X13+10X14+11X21+6X22+8X23+18X24+14X31+12X32+2X33+16X34 供 应 s.t X11+X12+X13+X14 = 9 地 约 X21+X22+X23+X24 = 束 X11 X12 X13 X14 +X21 +X22 +X23 +X24 X31+X +X31 32+X33+X34 ==46 求 地 约 束 +X32 +X33 = 9 = 7 需
4
-5
2
-5
7
-7
8
9
13
10
6
6
-9
27
6
13 12 13
13
19
z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9

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

j 1
m
s.t.
xij bj ( j 1, 2,L , n)
i 1
xij 0
2.产量小于销量（
m

ai
n
＜
bj ）
i 1
j 1
mn
min z
cij xij
i 1 j 1
n
xij ai (i 1, 2,L , m)
j 1
m
s.t.
xij bj ( j 1, 2,L , n)
方法:最小元素法,即对单位运价最小的变量先分 配运输量.
例、食品公司有三个生产面包的分厂A1，A2，A3，有四个销 售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司 每日的销量以及各分厂到各销售公司的单位运价如表所示， 在表中产量与销量的单位为吨，运价的单位为百元/吨。问 该公司应如何调运产品在满足各销点的需求量的前提下总运 费最少？
季度 生产能力(台) 单位成本(万元)
1
25
10.8
2
35
11.1
3
30
11.0
4
10
11.3
解: 设xij为第i季度生产的第j季度交货的柴油机的数目 Cij为第i季度生产的第j季度交货的每台柴油机的 实际成本.
j
i
1
2
3
4
1
10.8 10.95 11.10 11.25
2
11.10 11.25 11.40
25
销量
60 40 20 15
销地 产地
A B C 销量
甲
4 2 8
8
乙
12 10 5
14
丙
4 3 11
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
一、典例
某食品公司经营糖果业务，公司下设三个工厂A1、A2、 A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产 量、销售量及调运时的单位运输费用情况。问：如何调运可 使总费用最小？
生产量：A1——7吨， A2 —— 4吨， A3 —— 9吨 销售量：B1 —— 3吨，B2 —— 6吨，B3 —— 5吨，B4 —— 6吨
最优否？
Y
STOP
N
新的基可行解
12
表上作业法步骤:
初始运输方案最优性检验改进运输方案
一、初始方案的确定
1.最小元素法 2.Vogel法 二、最优性检验 1.闭回路法 2.位势法 三、方案改进方法 在闭回路内改进。
13
最小元素法
产销平衡表 单位运价表
B1 B2
B3
B4 产量 3 3 6
A1 A2 A3
b2
┈
bn
aibj
32
2销产(bj>ai)
Min z= cij·xij
i=1j=1
m n
Min z= cij· xij +0xm+1,j
i=1 j=1 j=1
m
n
n
x a
j 1 ij
n
i
(i 1,2,...,m)
x a
j 1 ij
n
i
(i 1,2,...,m,m 1)
19
注: 只要求的基变量是正确的，并且数目为m+n-1个，那么 每个非基变量的闭回路存在且唯一，因此，检验数唯一。
20
位势法
位势表:
单位运价表
B1 B1
B3
B4 行位势ui
A1 A2 A3
列位势vj
(2) (9) 3 10 1 (8) 2 (9) (-3) 4 (-2) 5
1 0 -4
A1 A2 A3
销量
B1 B2 B3 B4 10 5 0 10 15 5 5 15 15 10
15 25 5
A1 A2 A3
B1 10 12 2 8 -
B2 1 7 14 6 6 6
B3 20 9 16 7 11 -
B4 11 9 10 10 20 2 2 13 18 12 - 7 9 9
28
表 上 作 业 法 步 骤
销量
3 3 6 6
4 1
5
7 4 9
A1 A2 A3
B1 3 1 7
B2 B3 11 3 9 2 4 10
B4 10 8 5
14
Vogel法
例 A1 A2 B1 B2 8 2 5 1 15
产量
10 20
销量 15
最小元素法：z=8×10+2×5+1×15=105
Vogel法：z=10×5+15×2+5×1=85
最小元素法
产销平衡表 单位运价表 产量
A1 A2 A3
销量
B1 B2 B3 B4 0 15 0 15 10 5 5 15 15 10
15 25 5
A1 A2 A3
B1 10 12 2
B2 1 7 14
B3 20 9 16
B4 11 20 18
27
Vogel法
产销平衡表 单位运价表 产量
A1 A2 A3
15
Vogel法
产销平衡表
B1 B2 B3 B4 产量 A1 A2 A3 销量 5 3 2 1 3 5 6 7 4 9 A1 A2 A3 列两 最小 元素 之差 B1 B2 B3 B4 行两最小元素之差 3 1 7 2 11 3 10 9 2 8 4 10 5 5 1 3 0 0 07 1 1 16 1 2 --
x
ij
0
(i 1, ..., m ; j 1,...,n)
x
ij
0
31
产＞销问题单位运价表
产地
销地
B1 C11 C21 ┆ Cm1
B2 C12 C22 ┊ Cm2
┈ ┈ ┈ ┈ ┈
Bn C1n C2n ┊ Cmn
Bn+1 ０ ０ ┆ ０
产量
A1 A2 ┊ Am
销量
a1 a2 ┊ am
b1
· · · · · · · · · · · · · ·
· · · · · ·0
· · · · · ·
j=n
0 0 · · · · · · 1
0 0 · · · · · ·1
· · · · · · · · · · · · 0 0 · · · · · · 1
17
例
产销平衡表 单位运价表
B3 B4 产量 0 A1 20 20 10 A2 10 A3 10 25 15 50 销量 30 25 10 15 B1 B2
A1 A2 A3
B1 2 8 4
B2 7 4 3
B3 3 6 10
B4 11 9 5
18
产销平衡表
单位运价表
闭 回 路 法
B1 B2 B3 B4 产量 A1 (1) (2) 4 3 7 A2 3 (1) 1 (-1) 4 A3 (10) 6 (12) 3 9 6 5 6 销量 3
产地
销地
B1 C11 C21 ┆ Cm1 0 b1
B2 C12 C22 ┊ Cm2 0 b2
┈ ┈ ┈ ┈ ┈ ┈ ┈
Bn C1n C2n ┊ Cmn 0 bn
B1 B2
B3 6 0
B4 产量 2 3 5
A1 A2 A3
销量
3 3 6 6
6 5 9
25
6
练习
产销平衡表 单位运价表
B1 B2
B3
B4 产量
A1 A2 A3
销量
15 25 5
5 15 15 10
A1 A2 A3
B1 10 12 2
B2 1 7 14
B3 20 9 16
B4 11 20 18
26
10
关于运输模型的几个结论：
(1)设有m个产地，n个销地且产销平衡的运输问题，则基变 量数是m+n-1； (2)若变量组B包含有闭回路，则B中变量对应的列向量线性 相关； (3)m+n-1个变量组构成基变量的充要条件是它不包含任何闭 回路。
11
3.2 运输问题的求解方法：表上作业法
初始基可行解 单 纯 形 法 求 解 思 路
6
3 6
2 2
-
-
1 1
1
3 2
2
16
针对最小元素法和vogel法，需要说明的几点：
(1) 任何运输问题都有基可行解，且有最优解； (2) 如果供应量和需求量都是整数，那么一定可以得到整数 形式的最优解; (3) 用最小元素法和vogel法得到的是运输问题的一个基可行 解，数字格对应基变量； (4) 若在中途同时有行列要求得到满足，将同时划掉一行一 列，最后数字格个数将少于m+n-1个。为使数字格的个数恰 好等于m+n-1，在同时划去的行列中，任选（或选其价 格系数最小元素对应的）空格，填上数字0作为特殊的数字 格（即基变量）。
1 1 · · · · · ·1
· · · · · · · · · · · · 0 0 · · · · · · 0
· · · · · · · · · · · · · · · · · ·
i=m j=1 j=2
0 0
· · · · · · 0
0 0
· · · · · ·0
· · · · · · · · · · · · 1 1 · · · · · · 1
B1 3 1 7
B1 B3 11 3 9 2 4 10
B4 10 8 5
1
8
2
9
3.计算空格处位势； ij=ui+vj 4.计算空格处检验数： ij=cij- ij
21
1.数字格处上添上对应的运价；
2.计算行位势和列位势；
令v1=1，则依cij=ui+vj 计算各 ui和vj
检验数表 B1 B1 A1 A2 A3 销量 B3 B4 产量 7 4 9
· · · · · · · · · · · ·
i=1
i=2
1 1
· · · · · · · · · · · ·
· · · · · · 1
· · · · · ·
· · · · · ·0
· · · · · ·
· · · · · · · · · · · · 0 0 · · · · · · 0
0 0 · · · · · · 0
1 0 · · · · · · 0
0 1
· · · · · · · · · · · ·
1 0 · · · · · ·0
0 1
· · · · · · · · · · · ·
· · · · · · · · · · · · 1 0 · · · · · · 0
· · · · · · · · · · · · 0 1 · · · · · · 0
xij b j (j 1,2 ,..., n)
i 1
m
x
i 1
m 1
ij
b j (j 1,2 ,..., n) (i 1, ..., m,m 1 ; j 1,...,n)
x
ij
0
(i 1, ..., m ; j 1,...,n)
x
ij
0
33
销＞产问题单位运价表
23
例：
B3 A1 (0) (2) 5 A2 3 (2) (1) A3 (9) 6 (12) 销量 3 6 5
B1 B1
B4 2 1 3 6
产量 7 4 9
B1 B1 A1 A2 A3 销量 2 1 3