运筹学第三版之第三章 运输问题.ppt

文档介绍：运输问题(Transportation Problem)(Hitchcock),后来由柯普曼(Koopman)详细加以讨论。
在第一章线性规划模型的应用中,我们介绍了运输问题,建立了其数学模型,这类问题属线性规划问题,当然可以使用单纯形法进行求解,但是,由于运输问题的约束系数矩阵有其特殊的结构和性质,因而有比单纯形法更有效的方法来求解。
第三章运输问题
运输问题的数学模型
表上作业法
产销不平衡的运输问题
求初始基可行解的方法:西北角法、最小元素法、元素差额法
基可行解的改进方法:闭回路调整法、位势法
例:某运输问题的资料如下:
单位销地
运价
产地
产量
2
9
10
7
9
1
3
4
2
5
8
4
2
5
7
销量
3
8
4
6
一、运输问题的数学模型
试制定一个调运方案,使得总运费最省?
数学模型的一般形式

已知资料如下:
单位销
运价地
产地
产
量
销量
当产销平衡时,其模型如下:
()
当产大于销时,其模型是:
()
当产小于销时,其模型是:
()
运输问题的特征:
1、平衡运输问题必有可行解,也必有最优解;
证设
m行
n行
第i行
第m+j行