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

第三章 运输问题

  • 格式：ppt
  • 大小：131.50 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

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

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

产销平衡运输问题的数学模型可表示如下：
§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
第三章--运输问题

第三章--运输问题


A1 A2 A3 销量
B1 B2 B3 B4 产量
3 11 3 10
7
1928
4
7 4 10 5
9
3
6
5
6
20
A1 A2 A3 A1 0 1 3 A2 1 0 M A3 3 M 0
B1
B2
B3
B4
B1
0142
B2
1021
B3
4203
B4
2130
A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 T1 2 3 1 0 1 3 2 2 8 4 6 T2 1 5 M 1 0 1 1 4 5 2 7 T3 4 M 2 3 1 0 2 1 8 2 4 T4 3 2 3 2 1 2 0 1 M 2 6
A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 产量 A1 0 1 3 2 1 4 3 3 1 3 10 27
1
A2 1 0 M 3 5 M 2 1 9 2 8 24 A3 3 M 0 1 M 2 3 7 4 10 5 29 T1 2 3 1 0 1 3 2 2 8 4 6 20 T2 1 5 M 1 0 1 1 4 5 2 7 20 T3 4 M 2 3 1 0 2 1 8 2 4 20 T4 3 2 3 2 1 2 0 1 M 2 6 20 B1 3 1 7 2 4 1 1 0 1 4 2 20 B2 11 9 4 8 5 8 M 1 0 2 1 20 B3 3 2 10 4 2 2 2 4 2 0 3 20 B4 10 8 5 6 7 4 6 2 1 3 0 20 销量 20 20 20 20 20 20 20 23 2 25 26
– 产地和销地之间虽有直达路线，但直达运输的费用或 运输距离分别比经过某些中转站还要高或远。
广工管理运筹学第三章运输问题

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


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

第三章运输问题

计算过程如下：
找出初始基本可行解,即在(mn)产销平衡表上给
出m+n-1个独立的数字格。
求各非基变量的检验数，即在表上计算空格的
检验数。判别是否达到最优解。如已是最优解， 则停止计算，否则转到下一步。
确定换入变量和换出变量，找出新的基本 可行解，在表上用闭合回路法调整。 注: m+n-1个变量构成基变量的充要条件是它 们不构成闭回路。 重复2、3直到得到最优解为止。 以上运算都可以在表上完成。下面通过例 子说明表上作业法的计算步骤。
10
表中带圈的数字是非基变量的检验数，可 知所有检验数都大于等于零（基变量的检 验数都等于零），此解是最优解，这时最 小总运费为85元，具体的运输方案如下： A1分厂运5吨到销售公司B3，运2吨给销售 公司B4；A2分厂运3吨给销售公司B1，运 1吨给销售公司B4；A3分厂运6吨给销售公 司B2，运3吨给销售公司B4。
第二步：从行或列差额中选择最大者，选择它所 在行或列中的最小元素 B1 B2 B3 B4 产量 A1 7 A2 4 A3 销量
3
6 6
9
5
6
A1 A2 A3
B1 B2 B3 B4 3 1 7 11 9 4 3 2 10 10 8 5
Chapter 3 运输问题
第三步：对表中未划去的元素部分再分别计算出 各行、各列的最小运费和次最小运费的差额，并 填入该表的最右列和最下行。重复第一、第二步， 直到给出初始解为止。用此法给出例题的初始解 列于下表。 B1 A1 A2 A3 3 6 B2 B3 5 B4 2 1 3 产量 7 4 9
销地 产地 A1 A2 A3
销量
B1
B2
B3 5
B4 2 1 3 6
产
运筹学 第三章 运输问题

运筹学 第三章 运输问题

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

第三章运输问题-


13 12
7 27
5
9
10
6
A3
19
19
销量 22 13 12 13
二、表上作业法 第三章
2、解的最优性检验－－闭回路法 思路：要判定运输问题的某个解是否为最优解，可
仿照一般单纯形法，检验这个解的各非基变量(对应于运 输表中的空格)的检验数，若有某空格(Ai,Bj)的检验数为 负，说明将xij变为基变量将使运输费用减少，故当前这 个解不是最优解。若所有空格的检验数全非负，则不管 怎样变换解均不能使运输费用降低，即目标函数值已无 法改进，这个解就是最优解。
3
9
A2
64
10
8
5
11
6
A3
8
14
22
销量
8
14
12
14
48
所以，初始基可行解为：……目标函数值Z＝372
二、表上作业法 第三章
练习
销地
产地
B1
6 A1 14
8 A2 8
5 A3
销量 22
B2 7
4 13
9
13
B3 B4 产量
5
3
14
2 6
7 27106来自19613
12 13
二、表上作业法 第三章
i1
j1
ui vj cij
i 1,2,...m
j 1,2,...n ui , vj符号不限
考虑原问题变量xj的检验数为：
j cj zj cj C B B 1 P j cj Yj P
Pij ei emj
二、表上作业法
则运输问题变量xij的检验数为： ij cij zij cij YPij
运筹学-第三章-运输问题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 问如何调运使总运费最小？
第三章 运输问题

第三章 运输问题


10 8
8 40
3 20
• 新基可行解的位势方程组为 u2+v1=2 u1+v1=3 u1+v4=4 u2+v3=3 • 取u1=0，解上述方程组得 u1=0 v1=3 u2=－1 v2=－1 u3=4 • 各非基变量的检验数为 σ12 =7－（0－1）= 8>0 σ13 =6－（0+4）= 2>0 σ22 =4－（－1－1）= 6>0 σ24 =3－（－1+4）= 0 σ31 =8－（4+3）= 1>0 σ34 =9－（4+4）= 1>0
B1 A1 A2 A3 x11 x21 x31 B2 x12 x22 x32 B3 x13 x23 x33 B4 x14 x24 x34 B5 x15 x25 x35 B6 x16 x26 x36 B7 x17 x27 x37
闭回路有如下特点： ①每个顶点都是转角； ②每行或每列只有且仅有两个顶点； ③每个顶点的连线都是水平的或垂直的。
u3+v2=3 u3+v3=8 v3=4 v4=4
由于所有非基变量的检验数均大等于零，故从表3—11 中得到最优解为 x11=25，x14=25，x21=15，x23=5， x32=20，x33=10，其它xij=0
f*=3×25+4×25+2×15+3×5+3×20+8×10=360
此外，由于σ24 = 0，故此问题有另一最优基可行解。具
x11 x12 x1n x21 x22 x2n xm1 xm2 xmn
1 1 ... 1 1 1 1 1 ... 1 1 1 ... 1 1 1 1 1 1 1 1 m行 n行
运筹学 第三章 运输问题

运筹学 第三章 运输问题

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

第三章运输问题


5
设 xij 为 从 产 地 Ai 运 往 销 地 Bj 的 物 资 数 量 （i=1，…m；j=1，…n），由于从Ai运出的物资 总量应等于Ai的产量ai，因此xij应满足：
x
j 1
n
ij
ai
i 1,2, , m
6
运到Bj的物资总量应该等于Bj的销量bj，所以xij还 应满足：
m
第三章 运输问题
本章包含三部分的内容 运输问题及其数学模型 运输问题的表上作业法 运输问题的进一步研究
1
§1 运输问题及其数学模型
日常生活中，人们经常需要将某些物品由一个空间 位置移动到另一个空间位置，这就产生了运输，如 何判定科学的运输方案，使运输所需的总费用最少， 就是运输问题的模型需要解决的问题。
25
调 运
销地 量 B1
B2 90 150
X12
B3 70 100
X13
产量 200 250
产地
50
A1
X11
A2
销 量
50 80 X21
65
X22
200 75
X23
100
150
200
450
26
注：
能够作为表上作业法的基可行解的必要条件是
1. 基变量的个数为m+n-1个； 2. 在基可行解中不存在以非零元素为顶点的闭回 路。
5. 所有约束条件都是等式约束；
6. 各产地产量之和等于各销地销量之足所有约束条件
2. 基变量对应的约束方程组的系数列向量线性 无关。
3. 解中非零变量的个数≤m+n-1个 4. 为使迭代顺利进行，基变量的个数在进行迭 代过程中保持为m+n-1个 5. 将基可行解中基变量的值填入运输表中，非 基变量对应的格不填入数字，称为空格。

运输问题模型与性质

量为该闭回路的顶点；其中 i1 , i2 ,, is 互不
相同, j1 , j2 ,, js 互不相同。
例3-1 设m=3，n=4，决策变量xij表示从产地 Ai到销地Bj的调运量，列表如下，给出闭回路
{x11, x13 , x33 , x34 , x24 , x21} 在表中的表示法——
用折线连接起来的顶点变量。
三、运输问题的求解方法
1、单纯形法（为什么？） 2、表上作业法
由于问题的特殊形式而采用 的更简洁、更方便的方法
ai bj
i1
j 1
产销平衡条件
二、运输问题的特点与性质
1．约束方程组的系数矩阵具有特殊的结构
写出式（3-1）的系数矩阵A，形式如下：
x11, x12 ,, x1n ; x21, x22 ,x2n ,,,,, xm1 , xm2 ,xmn
1 1 1
111
m行
1
1
1
1
1
1
n行 1
A 的秩小于m+n； ？
由 A 的第二至m+n行和前n列及 x21, x31,, xm1
对应的列交叉处元素构成m+n-1阶方阵D 非奇 异； ？
因此 A 的秩恰好等于m+n-1，又D本身就含于 A中，故A的秩也等于m+n-1
x11, x12 ,, x1n ; x21, x22 ,x2n ,,,,, xm1, xm2 ,xmn
关系：
Pi1 j1 Pi1 j2 Pi2 j2 Pi2 j3 Pis js Pis j1 0
注意：列向量Pij =(0,…,0,1,0,…,0,1,0,…0)T中两 个元素1分别处于第i行和第m+j行，直接计算 即可得到结果。

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


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)。
存在以上情况的运输问题，统称为转运问题。
• 2）解题步骤：解决中转问题的思路是把它化 为无转运的平衡运输问题。
–首先根据具体问题求出最大可能中转量Q –纯中转站可视为输出量和输入量为Q的一个产地和 销地 –兼中转站的产地可视为一个输入量为Q的销地及一 个产量为a+Q的产地 –兼中转站的销地可视为一个输出量为Q的产地及一 个销量为b+Q的销地 –在此基础上，列出各产地的输入量。各销地的输 入量及各产销地之间的运价表，最后可用表上作 业法求解。
第三章 运输问题
第一节 运输问题及模型
• 一公司有三个加工厂A1、 A2、A3 生产某种产品，每日 的产量分别为7吨、4吨、9吨， 该公司把这些产品分别运往 四个销地B1、B2、B3、B4， 各销售点每日销量分别为3吨、 6吨、5吨、6吨，从各工厂到 各销售点的单位产品运价如 表所示，问该公司应如何调 运产品，才能在满足各销售 点需求的前提下，使总运费 最少？
销地
产地
B1 B2 B3 B4 产量 3 11 3 12 1 9 2 8 7 4 10 5 3 6 5 6 7 4 9
20 20
A1 A2 A3
销量
第二节 表上作业法
• 运输问题的求解方法——表上作业法
• 步骤：
– 1.确定初始调运方案——最小元素法 – 原则：根据运价最低的原则安排运量 – 方法：选择最小运价进行调运，同时划掉被满足的 行或列，但只能划一次，同时标注剩余运量。 – 检验：有数字格的数量=行数+列数-1=划线数量
• 例题：已知某物资的产量和销量及运价， 另外还假定这些物资在三个产地之间可以 互相调运，在四个销地之间可以互相调运， 运价如表所示，另外再假定还有四个纯中 转站，他们到各产地、销地及中转站之间 的运价如表所示，问在考虑到产销地之间 直接运输和非直接转运的各种可能方案的 情况下，怎样将三个产地的物资运往销地 总运费最省。
A1
B1 3
B2 11
B3 3
B4 10
产量 7
A2 A3
销量 A1 0
1 7 3
A2 1
9 4 6
A3 3
2 10 5
8 5 6
4 9 20
A1
A2 A3
1 3
0 M
M 0
B1 B1 0
B2 1
B3 4
B4 2
B2 B3 B4
1 4 2
0 2 1
2 0 3
1 3 0
T1 T2 T3 T4
A1 A2 A3 T1 2 3 1 0 1 4 3 5 M 2 M 2 3 1 3 2
T1 2 3
1 0 1 3 2 2 8 4 6
T2 1 5
M 1 0 1 1 4 5 2 7 20
T3 4 M
2 3 1 0 2 1 8 2 4 20
T4 B1 B2 B3 B4 产量 3 3 11 3 10 27 2 1 9 2 8 24
3 2 1 2 0 1 M 2 6 7 2 4 1 1 0 1 4 2 4 8 5 8 M 1 0 2 1 10 4 2 2 2 4 2 0 3 5 6 7 4 6 2 1 3 0 29 20 20 20 20 20 20 20 20
• 2.判断方案是否最优——乘数法
– 原则：无数字格的检验数都小于等于0 – 方法：1）对每一行设一个乘数ui，每一列设一 个乘数vj – 2）列出所有数字格的乘数方程ui+vj=cij（运 价），求出ui和 vj – 3）计算空格的检验数
• 3.方案调整
第三节 产销不平衡运输问题
• 1、直达运输问题
B2 11 B3 3 B4 10
销量
20 20 20 20
20 23 26 25 26
作业：用表上作业法求解下列运输问题
销地 产地 A B 甲 乙 丙 丁 产量 8 8 甲 4 1 乙 1 2 丙 4 5 丁 6 0
C 销量 6 5 6 3
4 20
3
7
5
1
T2 1 0 1 1
T3 3 1 0 2
T4 B1 B2 B3 B4 2 2 8 4 6 1 2 0 4 1 1 5 8 M 2 2 2 7 4 6
A1 A2 A3 T1 T2 T3 T4 B1
A1 A2 A3 0 1 3 1 0 M
3 2 1 4 3 3 M 3 5 M 2 1 9 2 8 0 1 M 2 3 7 4 10 5
– 求解思路：通过增加虚拟点，使产销不平衡问 题变为产销平衡问题，再进行求解。
2、可中转的运输问题
• 1）问题的提出：
– 产地和销地之间没有直达路线，货物从产地到销地必 须通过某中转站转运
– 某些产地既输出货物，也吸收一部分货物；某销地既 吸收货物，又输出部分货物，即产地和销地可以起中 转站的作用，或者既是产地，又是销地。 – 产地和销地之间虽有直达路线，但直达运输的费用或 运输距离分别比经过某些中转站还要高或远。