天津大学运筹学2.4运输问题.pptx

文档介绍：运输问题
运输问题的表示
网络图、线性规划模型、运输表
初始基础可行解
西北角法、最小元素法
非基变量的检验数
闭回路法、位势法
确定进基变量,调整运量,确定离基变量
§ 运输问题
一、运输问题的提出
生产某种产品,
m个产地:A1,…,Am,产量:a1,…,am
n个销地:B1,…,Bn,销量:b1,…,bn
已知:Ai至Bj的运输单价为cij
问题:确定Ai运往Bj的数量xij,使总运费最低?
二、运输问题的表示
网络图
运输表
线性规划模型
典型范例
各工厂应分別运送多少数量至各配送中心,才能使总的运输成本最低?
供给及需求单位:1卡车的量
单位运输成本:千元
工厂
配送中心
供给
W1
W2
W3
W4
P1
6
7
5
3
14
P2
8
4
2
7
27
P3
5
9
10
6
19
需求
22
13
12
13
60
运价表
2
3
2
1
3
4
1
运输问题网络图
s2=27
s3=19
d1=22
d2=13
d3=12
d4=13
s1=14
供应量
供应地
运价
需求量
需求地
6
7
5
3
8
4
2
7
5
9
10
6
运输问题线性规划模型
供应地约束
需求地约束
设xij(i=1,2,3;j=1,2,3,4)为i个工厂运往第j个配送中心的运量,这样得到下列运输问题的数学模型:
运输问题的表格表示
运输问题线性规划模型
产量约束
销量约束
三、运输问题的分类
产销平衡问题:∑ai= ∑bj
产销不平衡问题:
供大于求:∑ai >∑bj
供不应求:∑ai <∑bj
四、产销不平衡问题
1. 产大于销( )
模型:
增加
松弛变量
运输表:
B1
…
Bn
Bn+1
A1
x11
…
x1n
x1,n+1
a1
…
…
…
…
…
…
Am
xm1
…
xmn
xm,n+1
am
b1
…
bn
bn+1
实际意义:
虚设一个销地
运价为零