文档介绍：Chapter 3 运输问题
Transportation  Problem
运输问题是一种特殊的线性规划问题,用一种特殊的
方法(表上作业法)求解更为简单
运筹学
Operations Research
Mathematical Model of Transportation Problems
Variable and Closed path
Transportation Simplex Method
of Transportation Problems
11 十一月 2017
运输问题
人们在从事生产活动中,不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资,分别运到需要这些物资的地区,根据各地的生产量和需要量及各地之间的运输费用,如何制定一个运输方案,使总的运输费用最小。这样的问题称为运输问题。
11 十一月 2017
运输问题的特征
Characteristics of Transportation Problems
每一个出发地都有一定的供应量(supply)配送到目的地,每一个目的地都有需要从一定的需求量(demand),接收从出发地发出的产品。
需求假设(The Requirements Assumption)
可行解特性(The Feasible Solutions Property)
成本假设(The Cost Assumption)
整数解性质(Integer Solutions Property)
11 十一月 2017
需求假设(The Requirements Assumption):
每一个出发地都有一个固定的供应量,所有的供应量都必须配送到目的地。与之相类似,每一个目的地都有一个固定的需求量,整个需求量都必须由出发地满足,即
总供应量= 总需求量
可行解特性(The Feasible Solutions Property):
当且仅当供应量的总和等于需求量的总和时,运输问题才有可行解
11 十一月 2017
成本假设(The Cost Assumption):
从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系,因此这个成本就等于配送的单位成本乘以所配送的数量
整数解性质(Integer Solutions Property):
只要它的供应量和需求量都是整数,任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此,没有必要加上所有变量都是整数的约束条件
11 十一月 2017
【例1】现有A1,A2,A3三个产粮区,可供应粮食分别为10,8,5(万吨),现将粮食运往B1,B2,B3,B4四个地区,其需要量分别为5,7,8,3(万吨)。产粮地到需求地的运价(10万元/万吨)如表3-1所示,问如何安排一个运输计划,使总的运输费用最少。
钢铁厂
矿山
B1
B2
B3
B4
产量
A1
3
2
6
3
10
A2
5
3
8
2
8
A3
4
1
2
9
5
需要量
5
7
8
3
23
运价表(元/吨)
表3-1
11 十一月 2017
设xij ( i =1,2,3;j =1,2,3,4)为i个产粮地运往第j个需求地的运量,这样得到下列运输问题的数学模型:
运量应大于或等于零(非负要求),即
Min z = 3x11+ 2x12+ 6x13+ 3x14+ 5x21+ 3x22+ 8x23+ 2x24
+ 4x31+ x32+ 2x33+ 9x34
xij  0, i =1, 2, 3; j =1, 2, 3, 4
11 十一月 2017
有些问题表面上与运输问题没有多大关系,但经过转换,也可以建立与运输问题形式相同的数学模型
看一个例子:
【例2】有三台机床加工三种零件,计划第i台的生产任务为a i (i=1,2,3)个零件,第j种零件的需要量为bj (j=1,2,3),第i台机床加工第j种零件需要的时间为cij ,如表3-2所示。问如何安排生产任务使总的加工时间最少?
零件
机床
B1
B2
B3
生产任务
A1
5
2
3
50
A2
6
4
1
60
A3
7
3
4
40
需要量
70
30
50
150
表3-2
11 十一月 2017
【解】设 xi j (i=1,2,3;j=1,2,3,)为第i台机床加工第j种零件的数量,则此问题的数学模型为
11 十一月 2017
运输问题的数学模型
设有m个产地(记作A1,A2,A3,…,Am),生产某种物