2021年-运输问题.ppt

运输问题
运输问题的数学模型
　运输问题的表上作业法
*
-运输问题
*
运输规划问题的数学模型
例1. 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
B1
B2
B3
产量
A1
6
4
6
200
A2
6
5
5
300
销量
150
150
200
*
-运输问题
*
解：产销平衡问题：总产量 = 总销量＝500
设 xij 为从产地 Ai 运往销地 Bj 的运输量，得到下列运输量表：
B1
B2
B3
产量
A1
x11
x12
x13
200
A2
x21
x22
x23
300
销量
150
150
200
运输规划问题的数学模型
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
. x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
xij ≥ 0 ( i = 1、2；j = 1、2、3）
*
-运输问题
*
运输问题数学模型的一般形式
A1、 A2、…、 Am 表示某物资的 m 个产地； B1、B2、…、Bn 表示某物质的 n 个销地；ai 表示产地 Ai 的产量； bj 表示销地 Bj 的销量； cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价。设 xij 为从产地 Ai 运往销地 Bj 的运输量：
运输规划问题的数学模型
产销平衡
*
-运输问题
*
*
产大于销
例2. 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
运输规划问题的数学模型
增加一个
虚设的销地
运输费用为0
*
-运输问题
*
*
产大于销
例2. 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
运输规划问题的数学模型
增加一个
虚设的销地
运输费用为M(P128E2)
*
-运输问题
*
*
销大于产
例3. 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
运输规划问题的数学模型
增加一个
虚设的产地
运输费用为0
*
-运输问题
*
*
销大于产
例3. 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
运输规划问题的数学模型
增加一个
虚设的产地
运输费用为M
M
M
M
*
-运输问题
*
产销不平衡的运输问题
例4. 石家庄北方研究院有三个区,即一区,二区,三区,每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：
由于需大于供，经院研究决定一区供应量可减少 0 ~ 300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。
运输规划问题的数学模型
*
-运输问题
*
产销不平衡的运输问题
例4. 由于需大于供，经院研究决定一区供应量可减少0~300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。
解： 根据题意，作出产销平衡与运价表：
运输规划问题的数学模型
这里 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0
*
-运输问题
*