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

运筹学 第3章运输问题

  • 格式：ppt
  • 大小：1.55 MB
  • 文档页数：47

下载文档原格式

  / 47

合集下载

运筹学--第三章运输问题

运筹学--第三章运输问题
并设Xij----第i个盐产地运往第j个盐销地的运量。 目标函数为：
minS=3 x11 3 x12 4 x13 5 x14 6 x21 ...... 2x34
运出量等于产量：
x11＋x12＋x13＋x14＝70 x21＋x22＋x23＋x24＝80 x31＋x32＋x33＋x34＝100
P13 e1 e6 P14 e1 e7 P21 e2 e4 P23 e2 e6 P32 e3 e5 P34 e3 e7
后面 有理 论探 讨。
即不存在一组不全为零的数 k1 , k2 ,..., k6使得：
k1 P13 k2 P14 ... k6 P34 0成立
u1 u2 u3 v1 v2 v3 v4
x11 1
x12 1
x13 1
x14 1
1
0 1
0 1
0
x21 0 1 0 1
x22 0 1 0 0 1
x23 0 1 0 0 1
x24 0 1 0 0
x31 0 0 1 1
x32 0 0 1 0 1
x33 0 0 1 0 0 1
1
1
x34 0 0 1 0 0 0 1
3 2 2
1 4 5
销地 产地 A1 A2 A3 销量
3 4
B1 x11 x21 x31 3
B2 x12 x22 x32 6
B3 x13 x23 x33 5
B4 x14 x24 x34 6
产量 7 4 9 20
回顾
min z cij xij
i 1 j 1
如何求初始可行解？
约束方程 m n 7个， 模型中有变量 m n 12个，

运筹学第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
销量

(典型例题)《运筹学》运输问题

(典型例题)《运筹学》运输问题
第四天送洗：y451200
xj0，yij0，zij0，（i=1,┈,4；j=1,┈,5）
2008/11
--22--
--《Ⅵ 产量
新购 1 第一天 M 第二天 M 第三天 M
第四天 M
1 1 1 1 0 5200
0.2 0.1 0.1 0.1 0 1000
2008/11
--21--
建立模型：
--《运筹学》 运输问题--
设 xj—第j天使用新毛巾的数量；yij—第i天送第j天使用快洗 餐巾的数量；zij—第i天送第j天使用慢洗餐巾的数量；
Min z=∑xj+∑∑0.2yij+∑∑0.1zij
第一天：x1=1000
需 第二天：x2+y12=700
求 约
m1
xij b j (j 1,2,...,n)
i1
x 0 (i 1,...,m,m 1; j 1,...,n) ij
2008/11
--16--
--《运筹学》 运输问题--
销＞产问题单位运价表
产地销地 B1 B2 ┈
A1
C11 C12 ┈
A2
C21 C22 ┈
┊ ┆┊┈
Am Cm1 Cm2 ┈
2008/11
--8--
产销平衡表
--《运筹学》 运输问题--
单位运价表
B1 B2 B3 B4 产量
A1 (1) (2) 4 3 7 A2 3 (1) 1 (-1) 4 A3 (10) 6 (12) 3 9 销量 3 6 5 6
B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5
Ⅰ Ⅱ
示。又如果生产出来的柴
Ⅲ

运筹学第三章 运输问题

运筹学第三章 运输问题

销地 产地 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章 运输问题


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 确定初始基可行解
等所示。
23
2.2 最优解的判别
从每一空格出发一定存在和可以找到唯一的闭回路。因(m+n-1)个数字 格(基变量)对应的系数向量是一个基。任一空格(非基变量)对应的系数 向量是这个基的线性组合。如Pij, i,j∈N可表示为 Pij ei em j ei emk emk el el ems ems eu eu em j (ei emk ) (el emk ) (el ems ) (eu ems ) (eu em j ) Pik Plk Pls Pus Puj
mn
mபைடு நூலகம்n z
cij xij
i1 j1
m
xij bj j 1, 2,, n
i=1 n
s.t. xij ai i 1, 2,, m
j1
xij
0
(3 1) (3 2)
4
第1节 运输问题的数学模型
这就是运输问题的数学模型。它包含m×n个变量，(m+n) 个约束方程，其系数矩阵的结构比较松散，且特殊。
在给出调运方案的计算表上，如表3-
销 地 B1 B2 B3 B4 产
13，从每一空格出发找一条闭回路。 加工厂
量
它是以某空格为起点。用水平或垂直
A1

【运筹学 精品培训讲义】第三章运输问题


cij xij
i1 j1
n
xij ai
j1
i=1,2, ,m
m
xij b j
i 1
j=1,2, ,n
xij 0, i = 1,2, , m; j = 1, , n
2.运输问题的模型
x11 x12
x1n x21 x22
x2n
xm1 xm2 xmn
1 1
1
11
1
A＝1
1
11
1
1
1
1
1
1
1
i 1
j1
s.t. ui v j cij
对偶变量 xij
i = 1,2, , m; j 1,2, , n
ui, v j 无约束 i = 1,2, , m; j = 1, , n
运输问题例子
销售商 Boston Chicago St. Louis Lexington
供应商CleveΒιβλιοθήκη and3Bedford
S. t.
x11 +x 12 +x 13 +x 14
≤ 5000
x21 +x 22 +x 23 +x 24
≤ 6000
x31 +x 32 +x 33 +x 34 ≤2500
x 11
+x 21
+x 31
= 6000
x 11
+x 21
+x 31
= 4000
x 11
+x 21
+x 31
= 2000
x 11
7
York
2
需求量(吨) 6,000

运筹学 第三章 运输问题

（或者在同时划去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
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

检 验 数 表
最 优 方 案 判 别 准 则
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
表3-3
销地
产地
B1
3
B2
11
B3
3
B4
10
发量 （T）
7
A1
A2
A3
1
7
9
4
2
10
8
5
4
9
收量（T）
3
6
5
6
9
1、最小元素法
思路：为了减少运费，应优先考虑单位运价最小(或 运距最短)的供销业务，最大限度地满足其供销量。在可 供物品已用完的产地或需求已全部满足的销地，以后将不 再考虑。然后，在余下的供、销点的供销关系中，继续按 上述方法安排调运，直至安排完所有供销任务，得到一个 完整的调运方案(完整的解)为止。这样就得到了运输问题 的一个初始基可行解(初始调运方案)。 由于该方法基于优先满足单位运价(或运距)最小的供 销业务，故称为最小元素法。
表3-7
产
销 A1 A2 A3
B1 3
B2
B3 5
B4 2 1 3 6
供量 7 4 9
6 3 6 5
销量
19
计算最小元素法得到的初始基可行解的检验数 表3-8
销地 产地 A1 A2 B1
(+1)
B2
B3
B4
3
1
11
9 6
4 (-1) 1 (+1)
3
2
3
10
8
3 (-1)
A3
7
4
10
3
5
调整后总运费增加： (+1)×3+(-1)×3+(+1)×2+(-1)×1=1
33
如下例中σ11检验数是 0，经过调整，可得到另一个最优解。
销地 产地 A1
4 2
B1
(0)
12 10 5
B2
(2)
(2) 4 3 11
B3
12
(1) (12) 6 11 9
B4
4
产量 16
8
(9)
2
8
A2
A3
8
14
10
22
销量
8
14
12
14
其中绿色是非基变量检验数，红色为分配量。
34
例：用最小元素法求初始可行解
11
2. 沃格尔法
最小元素法，有时按某一最小单位运价优先安排
物品调运时，却可能在其他供销点多花几倍的运费，
从而使整个运输费用增加。 沃格尔法考虑到： 一个产地的产品假如不能按照最小 运费就近供应，就考虑次小运费，这就有个差额。 如果差 额不大，当不能按最小单位运价安排运输时造成的运费损 5 失不大；反之，如果差额很大，不按最小运价组织运输就 会造成很大损失，故应尽量按最小单位运价安排运输。沃 5 格尔法就是基于这种考虑提出来的。 5 5
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
从(p,q)空格开始画闭回路，其它转角点都是 填有运量的方格，并从(p,q)空格开始给闭回路上 的点按+1，-1，+1，-1编号，-1格的最小运量为 调整量。 表3-13
销地 产地 A1 A2 A3 销量 B1 B2 B3 B4 产量 7 4 9
3 3 6 6
4(+1)… …3(-1) ┇ ┇ 1(-1)… …(+1) 3 5 6
空格处 检验数 为1
20
表3-9
销地 产地 A1 A2
B1
B2
B3
B4
3
1 3 (-1)
11
9 6
4 (-1) 2 1 (+1)
3
3 (+1)
10
8
A3
7
(+1)
4
10
3 (-1)
5
调整后总运费增加： 7-5+10-3+2-1=10
空格处 检验数 为10
21
检验数表
销地 产地 B1 B2 B3
表3-10
Chapter3 运输问题
( Transportation Problem )
本章主要内容：
运输问题的数学模型
表上作业法 运输问题的应用
问题的提出
从m个发点 A1 , A2 , Am 向n个收点
B1 , B2 , Bn 发送某种货物. Ai 发点的发
量为 a i ， B j 收点的收量为 b j 。由 Ai 运
表3-5
B1 B2 B3 B4 产量
Z=85
5 3 6
3
B1 3 B2 11 9
2 1 3
6
B4 10 8
7 4 9
6
5
B3
表3-6
两最小元素之差
[3 ]
2 10
[ 1]
7
① ② ③ ④
2 2 2
[4 ] 5
1 1 1 1
[5 ] 3 3 2 2
①②③④ 0 0 0 7 1 1 1 6 1 2
14
1 若有两个以上相同的最大差值，可任取其 一。 2 剩下一行或者一列有空格，填数字，不能 划掉。 3 计算行差，列差时，已经划去的列或者行 不再考虑。
12
沃格尔法计算步骤：
1) 分别算出各行、各列的最小运费与次小运费的差额。 2) 从行、列中选出差额最大者，选择它所在行、列中的 最小元素，进行运量调整。 3) 对剩余行、列再分别计算各行、列的差额。返回1)、
2)。
13
2.伏格尔法
销地 产地 A1 A2 A3 销量
产地 A1 A2 A3 两最小 元素 之差 销地
实际中，往往遇到产销不平衡的运输问题
1.产大于销（供过于求）
a b
i 1 i j 1
m
n
j
2.销大于产（供不应求）
a b
i 1 i j 1
m
n
j
36
产销不平衡运输问题向产销平衡运输问题的转化
产大于销的运输问题： ai b j
i 1 j 1 m n
数学模型
min z cij xij
往 B j 单位货物的运费为 ci j ，问如何调配，
才能使运费最省？
若 ai b j，称此运输问题为平衡运输问题， 否则称为非平衡运输问题.
2
上述数据可以汇总于 表格中,如下:
表1 产销平衡表
销地 产地 1 2 ┆ m 销量
1
2
…
n
产量 a1 a2 ┆ am
b1
b2
…
bn
销地 产地 1 2 ┆ m
列位势:关于需求点Bj的约束对应的对偶变量，记为vj, j = 1,2,…,n。
23
定理：运输问题变量xij的检验数
ij cij ui v j
证明：
0 1 ij cij C B B 1 Pij cij ( u1 , ...um , v1 , ...vn ) cij ui v j 1 0
24
位势法 求检验数的步骤:
1. 在表中下面和右面增加一行和一列 , 列中添入 ui, 行中添入vj ,令u1=0, 按照 Cij ui v j , 根据表中已有 的数字确定所有的ui及vj ; 2.计算所有空格处的检验数.
ij Cij ( ui v j )
25
表3-12
m行
n行
1. 矩阵A是一个m+n行mn列的矩阵，它的秩为m+n-1。 2. 运输问题应该有m+n-1个基变量。 3. xij的系数列向量为：