当前位置：文档之家 › 运输问题(第三章线性规划5)

运输问题(第三章线性规划5)

  • 格式：ppt
  • 大小：1.30 MB
  • 文档页数：83

下载文档原格式

  / 83

合集下载

线性规划运输问题

线性规划运输问题

第四章 运输问题Chapter 4Transportation Problem§4.1 运输问题的定义设有同一种货物从m 个发地1，2，…，m 运往n 个收地1，2，…，n 。

第i 个发地的供应量（Supply ）为s i （s i ≥0），第j 个收地的需求量（Demand ）为d j （d j ≥0）。

每单位货物从发地i 运到收地j 的运价为c ij 。

求一个使总运费最小的运输方案。

我们假定从任一发地到任一收地都有道路通行。

如果总供应量等于总需求量，这样的运输问题称为供求平衡的运输问题。

我们先只考虑这一类问题。

图4.1.1是运输问题的网络表示形式。

运输问题也可以用线性规划表示。

设x ij 为从发地i 运往收地j 的运量，则总运费最小的线性规划问题如下页所示。

运输问题线性规划变量个数为nm 个，每个变量与运输网络的一条边对应，所有的变量都是非负的。

约束个数为m+n 个，全部为等式约束。

前m 个约束是发地的供应量约束，后n 个约束是收地的需求量约束。

运输问题约束的特点是约束左边所有的系数都是0或1，而且每一列中恰有两个系数是1，其他都是0。

运输问题是一种线性规划问题，当然可以用第一章中的单纯形法求解。

但由于它有特殊的结构，因而有特殊的算法。

在本章中，我们将在单纯形法原理的基础上，根据运输问题的特点，给出特殊的算法。

图4.1x x x x x x x x x d x x x d x x x d x x x s x x x s x x x s x x x .t .s x c x c x c x c x c x c x c x c x c z min mn2m 1m n22221n11211n mnn 2n122m 221211m 2111m mn2m 1m 2n222211n11211mn mn 2m 2m 1m 1m n 2n 222222121n 1n 112121111≥=++=++=++=++=+++=++=+++++++++++++=在运输问题线性规划模型中，令X =（x 11，x 12，…，x 1n ，x 21，x 22，…，x 2n ，……，x m1，x m2，…，x mn ）TC =（c 11，c 12，…，c 1n ，c 21，c 22，…，c 2n ，……，c m1，c m2，…，c mn ）T A =[a 11，a 12，…，a 1n ，a 21，a 22，…，a 2n ，……，a m1，a m2，…，a mn ]T=⎪⎪⎭⎪⎪⎬⎫⎪⎪⎭⎪⎪⎬⎫⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡行行n m 111111111111111111b =（s 1，s 2，…，s m ，d 1，d 2，…，d n ）T则运输问题的线性规划可以写成：min z=C TX s.t. AX =b X ≥0其中A 矩阵的列向量a ij =e i +e m+je i 和e m+j 是m+n 维单位向量，元素1分别在在第i 个分量和第m+j 个分量的位置上。

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

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

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

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

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

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

运筹学第三章 运输问题

运筹学第三章 运输问题

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

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

运输问题

运输问题

三、初始基础可行解的求法
• 1、西北角法 • 2、最小元素法
1、西北角法1 1 6 72 53 34 14
2
8
1 4 8
4
2
7
3
5
9
1 3
6
10 6
27
6
22 13 12 13
1 3
19
2、最小元素法（1）
1 6 1 8 2 5 3 22 9 4 7
2 5
3 3
4 14
2
7
12
10 6
27
15
运输问题系数矩阵的秩为m+n-1,即 基可行解只有m+n-1个变量
2、运输模型的特点
2) 对运输问题任一基B，其逆矩阵B 1必为一整数矩阵，若 ai , b j都为整数，则任一基可行解必为整数。 ( X B B 1b)
3) 对偶问题
max w ai ui b j v j
i 1 j 1 m n
19
0
最小元素法（6）
1 6 1 8 2 5 3 22 0 7
2 5
3 3
4 14 0
1
4 2 7
13 13
9 10
2 19
13 0
12
6
27
0
19 12 0 13 0
0
四、最优解的获得
1、检验数的求法：闭回路法
闭回路——从调运方案的某一空格出发，沿水平或垂直 的方向前进，遇到一个适当的数字格便按与前进方向垂 直的路径前进。经过若干次后，再回到原来出发的那个 格，由此形成的封闭折线称为闭回路。 闭回路的性质： 以空格出发的闭回路存在且唯一； 不存在所有顶点都为数字格的闭回路。

03运输问题


运 输 量 表
§2平衡运输问题的表上作业法
基本步骤： 1. 找一个初始基可行解;
方法: 西北角法/最小元素法
2. 最优解的判别（求非基变量的检验数）;
方法:闭回路法/位势法
3. 确定入基变量与出基变量，找出新的基可 行解；
方法:闭回路调整法
4. 重复2、3直到得到最优解
§2平衡运输问题的表上作业法
解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：
A1 A2 销量 B1 x11 x21 150 B2 x12 x22 150 B3 x13 x23 200 产量 200 300
运 输 费 用 表
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x + x = 150 s.t. x11 + x21 = 150 12 22 x13 + x23 = 200 xij ≥ 0 ( i = 1、2；j = 1、2、3）
A2
… Am 销量
x21
xm1 d1
x22
xm2 d2
…
x2n
xmn dn
s2
sm
运 输 量 表
§1 平衡的运输模型
例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地 的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示， 问：应如何调运可使总运输费用最小？
A1 A2 销量 B1 6 6 150 B2 4 5 150 B3 6 5 200 产量 200 300

运筹学 第三章 运输问题

（或者在同时划去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

第3章运输问题


ui + v j cij i = 1,2,..,m s.t. j = 1,..,n ui ,v j的符号不限
运输问题
解 的 最 优 性 检 验
检验数：目标函数的系数减去对偶变量之和
原问题检验数：σij=cij-(ui+vj) 特别对于m+n-1个基变量，有 σij=0
运输问题
B4 4 4 11 2 12 2 10 1 3 2 9 14 5 12 11 8 6 14 12 14
B2
B3 12
产量
16 10 22 48
ij 0, 此时的解为最优解。 z 8 2 14 5 12 4 4 11 2 9 8 6 244 246 2
运输问题
2.对偶变量法（位势法）
解 的 最 优 性 检 验
位势：设对应基变量xij的m+n-1个i、j ， 存 在 ui,vj 满 足 ui+vj=cij,i=1,2,..,m; j=1,2 ,… ,n称这些ui , vj 为该基本可 行解对应的位势。
运输问题
2.对偶变量法（位势法）
解 的 最 优 性 检 验
运输问题
最小元素法举例
A1 A2 A3
销量
B1 B2 B3 B4
4 12
产量
60 16 10 2 3 9 10 8 2 20 8 14 5 11 8 6 22 80 8 14 12 14 48 0 0 10 6 10
4
6
11
0
0
运输问题
最小元素法举例
A1 A2 A3
销量
B1 B2 B3 B4
4 12
2 列 罚 3 数 4
2
2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

m行
n行 n-1行
m列
n-1列
三、产销平衡运输问题的解法— 表上作业法
1、 表上作业法的流程图：
确定初始方案
判别 最优
否
是
得到最优方案
结束
调整方案
新方案
2、表上作业法的计算步骤
西北角法 Step1:确定初始方案— 最小元素法 Vogel法 Step2:判别方案是否最优--利用检验数来判别
20
50
2 3*
1 2
1
课堂练习2答案
销地 产地 甲 乙 丙 销量 A B C 产量
5
10 10
1 4
2
7
10 80 20 110 110
20 20
40
6
3
50
6
5
20
50
运费 f = 530
Step2 判别运输方案是否最优
•用判别数 ij 来判别
如何获得xij的判别数ij ?
•判别的规则如何？
所有ij 0, 方案为最优。
闭回路法 ij的求法 位势法
Step3:调整（或改进）方案--用闭回路调整法
运输问题实例
某公司经销甲产品。它下设三个加工厂 A1 、A2 、A3 ，其产量分别为7t ， 4t，9t。该公司把这些产品分别运往四个销售点 B1、B2、B3、B4，各销 售点销量为3t ，6t ，5t ，6t 。已知从各工厂到各销售点的单位运价为 下表所示。问该公司应如何调运产品，在满足各销售点的需要量的前 提下，使总运费为最少。
xij 0
运输问题数学模型的特征
1. m+n个约束条件，且每个约束条件都是等式 2. mn个变量 3. 系数矩阵A是一个 稀疏矩阵 其特点为:
（1）（2）（3）
4.系数矩阵A的秩为m+n-1 ， 即 R(A)=m+n-1
运输问题系数矩阵
x11 x12 x1n x21 x22 x2 n xm1 xm 2 xmn 1 A 1 11 1 1 1 1 1 1 1 1 1 1 11 1 1
乙
丙 销量（箱）
110 110
一般运输问题的数据表
产销平衡表
销地
运价表
产量
销地 产地
产地
B1
B2 … Bn
B1
B2 … Bn
A1 A2 … Am 销量 b1 b2 … bn
a1 a2 … am
A1 A2 … Am
c11 c12 … c1n c21 c22 … c2n … … … … cm1 cm2 … cmn
运费f ( x) cij xij 135
i 1 j 1
Step1
确定初始方案
2.最小元素法
销地 加工厂 A1 A2 A3 销量
B1 3
B2 11 4 9
B3 3 2 10 5
B4
产量 10 8 7 4 9
3
3
1 7 3
1
6
6
4
3
6
5
初始方案如下
销地 加工厂 A1 A2 A3 销量
销地 加工厂 A1 A2 A3 销量
B1 3
B2 11 4 9
B3 3 2 10 5
B4
产量 10 8 7 4 9
3
3
1 7 3
1
6
6
4
3
6
5
实例
销地 加工厂 A1 A2 A3 销 量
用闭回路法求判别数 产 量 7 4 9 20
B1
B2
B3
B4
1
+1
3
1
11
9
4
-1
3
3 10
8
3 -1
7
6
6
4
2 1 +1 10
用Vogel法求下列运输问题的初始方案 销地 产地 甲 乙
A
5 6
B
1 4
C
7 6
产量
10 80
丙
销量
3
40
2
20
5
50
20
110 110
课堂练习2解答
销地 产地 甲 乙 丙 销量 A B C 产量 行差额
— 4*
5
10 10
1 4
2
7
10 80 20 110 110
20 20
40
6
3
50
6
5
2 1
3 6 5 9
3 10
8 5
3
7
1
4 10
3
6
实例
销地 加工厂 A1 A2 A3 销 量
用闭回路法求判别数
B1
B2
B3
B4
产 量 7 4 9 20
3
11
4
3
2
1
1
2 1 6
3 6 5 9
3 10
8
3
7
1
4 10
-1
5
3
6
实例
销地 加工厂 A1 A2 A3 销 量
用闭回路法求判别数 产 量 7 4 9 20
3 5
6
3
5
实例
销地 加工厂 A1 A2 A3 销 量
用闭回路法求判别数
B1
B2
B3
B4
产 量 7 4 9 20
3
11
4
3
2
1
1
2
9
3 10
8 5
3
7 4
1
10
6
3 6 5
3
6
实例
销地 加工厂 A1 A2 A3 销 量
用闭回路法求判别数 产 量 7 4 9 20
B1
B2
B3
B4
3
11
4
3
2
1
1
2 1 6
销地 加工厂 A1 A2 A3
B1 3 1 7
B2 11 9 4
B3 3 2 10
B4 10 8 5
Step1
确定初始方案
1.西北角法
销地 加工厂 A1 A2 A3 销量
B1
B2 3 1 7
B3 11 9 4 3
B4 10 8 5 6
3 4
产量 7 4 9
3
4 2
2
2
3 10 6
5
3
6
m+n=7
有6个基变量
2 1
3
1 7
6
6
4 5
10 3
2.位势法求判别数（原理）
•对产销平衡的运输问题，若用u1，u2，…，um分别表示前 m个约束条件的对偶变量，用v1，v2，…，vn分别表示后n 个约束条件的对偶变量，即有对偶变量
j c j C B B 1 Pj 由于线性规划问题的变量xj对应的判别数
xm1+xm2+… +xmn = am x11 +x21 +… xm1 = b1 x12 +x22+…xm2 x +x +…x = b2 =b
……………………………………..
位势法求判别数（公式）
•对于基变量格（数字格）有：cij = ui + vj •令u1 = 0，和m + n – 1个基变量，就可以 求出ui和vj。 •利用公式 ij cij (ui v j ) ，就 可以求出所有非基变量的判别数。
0 -25
第三步迭代
基变量 xj
40
x1 1
x2
x3
x4 x5 0.5 0
b 15
x1
0 -0.5
0
x5
x2
0
0 0
0 -1.5 0.5 1
1 0.75 -0.25 0 0 -17.5 -7.5 0
9
7.5 -975
50
该问题的最优解为：X=(15, 7.5, 0, 0, 9)T
实例
用闭回路法求判别数 用最小元素法确定初始方案
0 ... m行 1 ... Pij 0 ... n行 1 ... 0
i行
m+j行
系数矩阵A的秩为m+n-1 ， 即 R(A)=m+n-1
x1n x2 n xmn x11 x12 x1n 1 1 0 0 0 1 0 0 0 1 A 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 11 0 0 0 0 0 0 1 0 1 0 0
销地 产地 A B C 产量
甲
乙 丙
8
9
5
7
4
4 3 11 11
4
4 6
2
1 3
2
2
3
销量 3 2
0
6
课堂练习答案
销地 产地 A B C 产量
甲
乙 丙
8
9
5
7
4
4 3 11 11
4
4 6
2
1 3
2
2
3
销量 3 2
0
6
运费 f = 51
退化的基可行解
Step1
确定初始方案
3.Vogel法（元素差额法）
用闭回路法求判别数 产 量 7 4 9 20
B1
B2
B3
B4
3
11
4
3
2
1
1
2 1 6
3 6 9
3 10
8
3
7