运筹学（第2版）课件 第二章 运输问题.pptx

运筹学

南京航空航天大学经济与管理学院

第二章运输问题

前面讨论了一般线性规划问题的数学模型的建立和求解方法，但在实际工作中，往往碰到有些线性规划问题，它们的约束条件系数矩阵具有特殊结构，这就使我们有可能找到比单纯形法更为简单的求解方法，从而节约大量的计算时间和费用。本章所讨论的运输问题就是属于这样一类特殊的线性规划问题。

在日常生产和经营管理过程中，常常遇到这样一类问题：公司有若干个生产单位与销售单位，根据各生产单位的产量及销售单位的销售量，并且知道各生产单位到各销售单位之间的运输单价，该公司应如何将产品运到各销售单位而使总的运输费用最小?

运输问题是特殊的线性规划问题，它是早期的线性网络最优化的一个例子。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。运输问题是极具实际意义的研究。

运输问题中最有名的一个实例是罗马尼亚薪柴配送问题。当时的研究条件相当艰苦，整个罗马尼亚只有一台计算机和两位程序员。在没有计算机的帮助下，巴拉斯硬是和八名学生一起通过手算的方式，利用线性规划技术成功解决了当时罗马尼亚交通领域的大难题—一薪柴配送问题,为整个罗马尼亚节约了8%的运输成本，这在当时引起了极大轰动。小有成就后，巴拉斯进入了木材工业设计院工作，领导院里的线性规划小组。

发展简史

#1941年，美国学者希奇柯克(Hitchcock)在研究生产组织和铁路运输方面的线性规划

问题时提出运输问题的基本模型。

#从上世纪40年代早期开始，列奥尼德·康托罗维奇(LeonidV.Kantorovich)围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或康脱洛维奇问题。

#1947年，柯普曼(Koopmans)独立地提出运输问题并详细地对此问题加以讨论。

#1951年，丹齐格(GeorgeBernardDantzig)提出的单纯形法作为求解运输问题的最初单纯形方法(PrimalSimplexTranspotationMethod.PSTM)。

#1954年，亚伯拉罕·查恩斯(AbrahamCharnes)与威廉·库珀(WilliamW.Cooper)

发展了逐级算法(Stepping-StoneMethod,SSM),该算法提供了决定单纯形方法信息的

可选择途径。

列奥尼德·康托罗维奇

(LeonidV.Kantorovich,1912-1986)

万哲先(1927-今)

建国初期，全国工业与抗美援朝导致铁路交通运输资源十分紧张，运输方案的制定越来越复杂，运输部门为了比较两个方案，往往需要通宵达旦地计算。在大量实践的基础上，形成了一些经验性的图上作业法。万哲先等人专门去运输部门研究如何应用和推广线性规划，万哲先对图上作业法给出了理论证明，并进行了推广应用。另外，数学家越民义对国外提出的 表上作业法也给了理论证明。

销地

产地

B₁

B₂

B₃

B₄

产量

A₁

3

11

3

10

7

A₂

1

9

2

8

4

A₃

7

4

10

5

9

销量

3

6

5

6

2.1运输问题的数学模型

例2.1某公司有3个生产同类产品的生产地点(以后称为产地),运往4个销售地(以后称为销地)销售，各产地的生产量、各销地的销售量以及各产地到各销地的单位产品运价如表2.1所示。问该公司应如何调运产品，在满足各销地的需要量的前提下，使总的运费为最小。

表2.1单位：吨

可见运输问题就是解决如何把某种产品从若干个产地调运到若干个销地，在每个产地的

产量和每个销地的需求量已知及各地之间运输单价已知的前提下，如何调运使得运输费用最小?

假设x;;表示从A;到B;的运量，Z表示的运输费用，从而得到其数学模型：

minZ=3x₁+11x₁₂+3x₁₃+10x₁4+x₂₁+9x₂₂+2x₂3+8x₂4+7x31+4x3₂+10x₃3+5x₃4

xn=3(1)

x₂=6(2)

在该模型中，目标函数要求其极小化；前4个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量；第(5),(6),(7)这3个约束条件表示由某一产地运往各销地的物品数量之和等于该产地的产量；最后一个约束条件表示决策变量的非负条件。

可见运输问题是一种线性规划问题。

对于一般情况，假设有m个生产地点，可以供应某种物资(以后称为产地),用Ai表示，i=1,2,…,m;