运输问题(运筹学).ppt

运筹学
王莉莉
四川农业大学数学系
2012年10月
学****目标
理解运输问题的特点;
掌握表上作业法;
掌握确定初始调运方案的方法;
掌握最优解的检验法
掌握调运方案的改进法.
第四章—运输问题
引言
在生产经营活动中,经常碰到大宗物质的调运问题.
如煤炭、钢铁、木材、粮食等等物质,在全国有若干个生产基地,根据已有的交通网,应如何制定调运方案,将这些物质运到消费地点,而总运费要最小.
运输问题的提法
m 个产地 Ai 输出某种货物,其量为 ai ( i =1,2,…,m ). n 个销地 Bj ,收到某种货物,其量为 bj ( j =1,2,…,n ) . 从Ai 到 Bj 单位货物运价为 Cij ,问题是在尽量满足销地的需求时总运价最小.
2
3
1
2
3
4
1
供求平衡的运输问题
B1=22
B2=13
B3=12
B4=13
A2=27
A3=19
A1=14
供应地
运价
需求地
6
7
5
3
4
8
2
7
5
9
10
6
供应量
需求量
总供应量60吨
总需求量60吨
供求平衡的运输问题
13
12
13
22
销量
19
6 /x34
10 /x33
9 /x32
5 /x31
A3
27
7 /x24
2 /x23
4 /x22
8 /x21
A2
14
3 /x14
5 /x13
7 /x12
6 /x11
A1
运量
B4
B3
B2
B1
销地
产地
单位 利润
供应地约束
需求地约束
运输问题约束条件系数矩阵特点
系数矩阵元素松散,只有1和0;
系数矩阵每列仅有两个1,其余均为0
运输问题
1、平衡运输问题:总产量=总销量
2、产大于销运输问题:总产量≥总销量
3、产小于销运输问题:总产量≤总销量
平衡运输问题的数学模型
设xij 表示从Ai 到Bj 的运量
产大于销运输问题的数学模型
设xij 表示从Ai 到Bj 的运量