Chapter 05 Trans.ppt

文档介绍：管理运筹学
主讲教师:李愉心
第七章运输问题
问题提出
在经济建设中,经常遇到大宗物资的调运问题,如煤、钢材、粮食等。如果在我们考虑范围之内有若干个生产基地和若干消费地点,根据已有的交通网络,如何制定调运方案,使总的运费达到最小,这就是运输问题.
运输问题是特殊的线性规划问题,故可以用单纯形法来求解,又因为它具有特殊性,因而它还具有比单纯形法更为简便的解法,这就是我们专门研究运输问题的目的.
运输问题
典型背景——单一物资运输调度问题
设某种物品有:
m个产地:
产量:
n个销地:
销量:
从产地到销地的单位运价是。
求总运费最小的调度方案。
决策变量表示由到的物品数量。
销地
产地
销量
产量
运输问题
产销平衡问题——总产量=总销量
即
产销不平衡问题——总产量≠总销量
运输问题
产销平衡问题的数学模型
运输问题
运输问题数学模型的特点
运输问题有有限最优解
运输问题约束条件的系数矩阵(下页)
约束条件系数矩阵每一列只有两个1,其余为0;
对产销平衡问题
约束条件均为等式,且产量之和=销量之和;
约束条件的独立方程最多有m+n-1个,即
运输问题
m
n
9
例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?
§1 运输模型
10
解: 产销平衡问题: 总产量= 总销量
设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表:
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)