凌晨 第一节运输问题 运输问题及其特殊的表格作业法求解 3、例子及其表格作业法求解 2)运输表 形如下列形式的表格称为运输表:(注:空格对应于12条路径) 目的地 起运点 D4 可供量 目的地需求量6 2000
Ling Xueling 二、运输问题及其特殊的表格作业法求解 3、例子及其表格作业法求解 2）运输表 形如下列形式的表格称为运输表：（注：空格对应于12 条路径） 第一节 运输问题 凌晨: 凌晨: 目的地 起运点 D1 D2 D3 D4 可供量 3 2 7 6 O1 5000 7 5 2 3 O2 6000 2 5 4 5 O3 2500 目的地需求量 6000 4000 2000 1500 13,500
凌晨: 第一节运输问题 二、运输问题及其特殊的表格作业法求解 3、例子及其表格作业法求解 3)运输表的意义 (1)方便收集资料/数据 2)保持运算轨迹 4、(最小成本法)求初始可行解 1)思路 )对最小成本路径,安排尽可能多的货物 2)若有相同的最低成本路径,优先选择运量最大的方 格一一路径
Ling Xueling 二、运输问题及其特殊的表格作业法求解 3、例子及其表格作业法求解 3）运输表的意义 （1）方便收集资料 / 数据 （2）保持运算轨迹 4、（最小成本法）求初始可行解 1）思路 1) 对最小成本路径，安排尽可能多的货物 2) 若有相同的最低成本路径，优先选择运量最大的方 格－－路径。 第一节 运输问题 凌晨: 凌晨:
且t 凌晨 第一节运输问题 二、运输问题及其特殊的表格作业法求解 4、(最小成本法)求初始可行解 2)表上作业 可得运输方案及相关成本如下 从 至 运输单位 单位成本 成本 1-- d 1000 3 3000 1---d2 4000 2 8000 2500 17500 02 2000 4000 2 1500 4500 03 2500 5000 总成本:42000
Ling Xueling 二、运输问题及其特殊的表格作业法求解 4、（最小成本法）求初始可行解 2）表上作业 可得运输方案及相关成本如下： 总成本：42000 第一节 运输问题 凌晨: 凌晨: 从 至 运输单位 单位成本 成本 o1 ---------- d1 1000 3 3000 o1 ---------- d2 4000 2 8000 o2 -----------d1 2500 7 17500 o2 ---------- d3 2000 2 4000 o2 ----------- d4 1500 3 4500 o3 ----------- d1 2500 2 5000
凌晨: 第一节运输问题 二、运输问题及其特殊的表格作业法求解 4、(最小成本法)求初始可行解 3)求初始可行解要保证利用m+n-1条路径 (1)例子 日的地 起运点 DI D2 D4 可供量 02 15 目的地需求量10 10 60
Ling Xueling 二、运输问题及其特殊的表格作业法求解 4、（最小成本法）求初始可行解 3）求初始可行解要保证利用 m + n－1 条路径 （1）例子 第一节 运输问题 凌晨: 凌晨: 目的地 起运点 D1 D2 D3 D4 可供量 6 8 3 10 O1 30 2 9 5 7 O2 15 7 8 6 4 O3 15 目的地需求量 10 25 10 15 60
凌晨: 第一节运输问题 4、(最小成本法)求初始可行解 3)求初始可行解要保证利用m+n-1条路径 (2)为什么 求出初始可行解以后向最优解进行迭代之必须 (3)调整方法 上例中,最后一次运输安排时剩余的行供量和列需量同时 减为零,若此情形发生在安排最后路径以前,则所得初始 可行解所利用的路径就会不足m+n-1。可调整如下 (i)将出问题的行和列分别用横、竖直线划去 ⅱ)额外指定一个零单位运输计划到所划横或竖线上的任意 个空格
Ling Xueling 4、（最小成本法）求初始可行解 3）求初始可行解要保证利用 m + n－1 条路径 （2）为什么 求出初始可行解以后向最优解进行迭代之必须 （3）调整方法 上例中，最后一次运输安排时剩余的行供量和列需量同时 减为零，若此情形发生在安排最后路径以前，则所得初始 可行解所利用的路径就会不足 m + n－1。可调整如下： ( i ) 将出问题的行和列分别用横、竖直线划去 ( ii ) 额外指定一个零单位运输计划到所划横或竖线上的任意 一个空格。 第一节 运输问题 凌晨: 凌晨: