运筹学教案(运 输问题).ppt

文档介绍：运筹学教案
运输问题
1
运输问题的描述及特点
描述运输问题的方式有三种:
网络图方式
数学模型方式(即线性规划模型)
数据表格方式(运输表)
网络图方式
以图示方式描述运输问题,涉及:供应地、供应量、需求地、需求量、运输单价等概念与数量。
2
A1
B1
Ai
Am
Bj
Bn
c11 c1j c1n cij cmn
供应量: a1 ai am
需求量:b1 bj bn
单位运价:
若∑ai = ∑bj 则称为平衡运输问题
3
运输问题的分类:
分为有转运与无转运运输问题。
无转运的运输问题:
平衡运输问题: 条件∑ai = ∑bj 成立
非平衡运输问题: 上述条件不成立。
若: ∑ai ≥∑bj 则为产大于销情况
∑ai ≤∑bj 则为销大于产情况
对于不平衡运输问题,可转化为平衡运输问题处理,而有转运问题可化为无转运问题处理。
4
平衡运输问题的数学模型
5
运输问题的表格描述
运输问题可以用一张表格描述
……
……
……
……
6
运输问题的特点
(1)仍然为一线性规划问题
(2)有m+n个方程,但平衡运输问题加上一
相容性条件之后只有m+n-1个独立方程,故运
输问题的基变量为m+n-1个
(3)平衡运输问题一定有最优解
(4)由于运输问题结构系数矩阵为一特殊稀
疏矩阵(元素为1),故有其特殊求解方法:
表上作业法。
7
运输问题的表上作业法
表上作业法是求解运输间题时的一种简化方法。其实质是单纯形法。: (1)找出初始基可行解。即在(m x n)产销平衡表上给出m+n-1个数字格,
(2)求各非基变量的检验数,,则停止计算,否则转到下—步。
(3)确定换入变量和换出变量,。
8
(4)重复(2),(3)直到得到最优解为止。
。
初始方案的确定
可利用价格表采用
西北角法
最小元素法
伏格尔法
等方法求平衡运输问题的初始调动方案
9
以例子说明表上作业算法
有如下表格描述的平衡运输问题
10