❖ 计算ui+vj，填于空格处
OR2
16
检验数计算： σij=cij-(ui+vj)
σ 21=-1
OR2
17
方案调整：
❖ σij < 0 处，增加运输量，可节约运费。故做如
下调整：
OR2
18
新方案：
此方案费用为：13+1 4+3 5+51+2 2+4 2=39
OR2
19
新方案检验
❖ 新方案相应的运费填于表上,给定位势初值， 计算各位势值。
❖ AB：QM软件包，在module中选择 transportation,在file中点击new,输入数据，点 击solve,出现结果。
OR2
33
4.5 运输模型的应用
❖ 例题4：某机床厂定下一年合同分别于各 季度末交货。已知各季度生产成本不同， 允许存货，存储费0.12万元/台季，三、 四季度可以加班生产，加班生产能力8台 /季，加班费用3万元/台
OR2
22
例题2.供大于求的运输问题
❖ 运费及产销量表
OR2
23
例2 解：
❖ 引入虚拟销地B4，（或理解为仓库）， 就地“销售”，运费为零
OR2
24
例2 求初始方案：（P128）
用最小元素法，但零视为最大元素。（？）
OR2
25
例2 初始方案：
.
OR2
26
例2检验初始方案
❖ 计算位势ui+vj
❖ 最优性检验与单纯形法原理一致，计算方法 有位势法和闭回路法，这里讲位势法。
❖ 位势法是任意给出一组数ui和vj，称之为位势， 有数字的格满足：ui+vj=cij
没数字的格计算： σij=cij-(ui+vj)
OR2
15
位势计算： ui+vj
❖ 先填写初始方案相应的运费，任意给出一个
ui或vj值，推出其它位势值。
圈定C31
OR2
9
例1初始方案（续2）
❖ 圈定C13
OR2
10
例1 初始方案（续3）
❖ 圈定C32
OR2
11
例1 初始方案（续4）
❖ 圈定C23
OR2
12
例1 初始方案（续5）
❖ 圈定C22
OR2
13
例1初始方案——初始基可行解
❖ 中心数字为分配的运输量
此方案费用为40
OR2
14
4.2.2 最优性检验
产量=销量。 ❖ 处理办法：设想一个虚拟煤矿D，生产50万吨，但
这个产量只能供应可有可无的最高需求部分，于是 各地的需求也应分为两个部分：基本需求、机动需 求 O❖R2虚运拟费产为量无穷的大运。输费用为零，但它对于基本需求来讲，30
例题3：建模：
1
OR2
31
例题3：最优解：
1
OR2
32
4.4运输问题的计算机求解
OR2
41
例五 问题分析（续2）
❖ 所需91条货船要经调度而来，有的可在一个 港口卸货后装运（如一条船从E到D后再起程 赴B）。若港口没有空船，则要从其它港口调 度而来。（规模效益）
例四.建模：
.
OR2
36
例四 结果：
.
OR2
37
例题5 航运调度问题
❖ 某航运公司承担六个城市A、B、C、D、E、F之间 的四条航线，已知各航线的起点、终点及每天所需 的航班数如下表。又知各城市之间的航行天数，假 定船只型号相同，装卸货时间各一天，问该公司至
少要配备多少条船才能满足需要？
OR2
第四章 运输问题
本章要求： 掌握运输问题的数学模型 掌握运输问题的求解方法 化产销不平衡问题为平衡问题 学会用计算机求解
OR2
1
4.1运输问题的数学模型
❖ 运输问题一般表述为：
某企业有m个产地（生产厂）Ai，其产量分别 为ai, i=1,2,…m, n个销地（销售商）Bj，其销 售量分别为bj, j=1,2,…n,从Ai到Bj的每单位物 资的运费为Cij.要求拟定总运费最小的调运方 案。
38
例5 城市之间航行天数表
.
OR2
39
例5 问题分析
问题要求的是在保证需要的前提下，至少 需要多少船只。
所需船只包括两个部分：载货船、空驶船 。
OR2
40
例5 问题分析（续1）
❖ 上表显示：载货船共需91条，此船何来？
A
B
1
2
1
F
调度中心
C
E3
D
若无空驶，则91条船刚好够用，但虚线 箭头都是空驶
在运费表中找出最小元素，尽最大可能
用完一个厂的产量，或满足一个商家的销量。 得到满足者用线划去。
逐次寻找最小元素，直至分配完毕
注意：如填写一个数字同时满足了一厂
一商，则需在同行或同列中填写一个数字0，
OR2以保证恰好有m+n-1个数字。
7
例1 之初始方案（P119）
最小元素法：圈定C24
OR2
8
例1初始方案（续1）
OR2
2
.
OR2
运输表
3
运输问题的数学模型
设从Ai 到Bj的运输量为xij,（假定产销平衡）
nm
则总运费： minZn= ∑∑ Cj=ij1xi=ij1 产量约束： ∑xij = jma=1i i=1,2,…m, 销量约束： ∑xij =i=b1j j=1,2,…n, 非负性约束： xij ≥0
OR2
20
新方案检验
❖ 计算空格处（即非基变量）的检验数，
σij=cij-(ui+vj)，所有σij ≥0 ，已得最优解。

OR2
21
4.3产销不平衡问题
❖ 产销不平衡是最常见的现象，此类问题可以 转化为产销平衡的模型，而后求解。
❖ 运输问题产销平衡模型，实质上就是一个求 解运输问题的标准型。
❖ 解决的办法是：增加一个虚拟的产地或销地， 从而变成标准型——产销平衡问题。
OR2
34
例四.分析：
❖可用线性规划，但用运输问题更简单
❖要决策的问题是各季度生产量和交货量设
xij表示第i季度生产第j季度交货的台数
❖因加班时间生产成本不同，故要区别开来， 三四季度可加班，视同增加两个季度
❖需求量合计115台，生产能力合计126台， 供需不平衡，因此，增加一项闲置能力。
OR2
35
OR2
4
4.2表上作业法
❖ 计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2
OR2
5
例题1
❖ 某建材公司有三个水泥厂A1、A2、A3， 四个经销商B1、B2、B3、B4，其产量、 销量、运费如下表：
OR2
6
4.2.1求初始调运方案
❖ 用最小元素法（也可用西北角法或vogel法） 给出初始基可行解：
OR2
27
例2计算检验数
❖ σij=cij-(ui+vj), 所有σij ≥0 ，已得最优解。
OR2
28
例题3：弹性需求问题
❖ 设有三煤矿供应四地区，资料如下：
OR2
29
例题3：解题思路：
❖ 设法转化为标准型 ❖ 本题产量160万吨，最低需求110万吨，最高需求无
限。实质上比较现实的最高需求210万吨 ❖ 产量大于最小需求；小于最大需求。而标准型是：