凌晨: 第一节运输问题 运输问题及其常规解法 3、模型(运输问题的LP) min∑∑c;X S t x1+x12+x13+x14≤5000 O x21+x22+x23+x24≤6000 X31+x32+x33+x34≤2500 11 21 6000 X12+X22×32 4000 X13+x23+x33=2000 ODDDD 14 1500 X1;≥0
Ling Xueling 一、运输问题及其常规解法 3 、模型 ( 运输问题的 L.P.) min ∑∑ c i j x i j s.t. x11 + x12 + x13 + x14 ≤ 5000 O1 x21 + x22 + x23 + x24 ≤ 6000 O2 x31 + x32 + x33 + x34 ≤ 2500 O3 x11 + x21 + x31 = 6000 D1 x12 + x22 + x32 = 4000 D2 x13 + x23 + x33 = 2000 D3 x14 + x24 + x34 = 1500 D4 xi j ≥ 0 第一节 运输问题 凌晨: 凌晨:
凌晨: 第一节运输问题 运输问题及其常规解法 4、计算机求解及其特点 11-3500 12=1500 2=2500 23=2000 X24=1500 31=2500 其余x=0 o.f.=39500 注意:最优解值都是整数!巧合? 5、定理 若所有起运点的供货量和目的地的需求量都是整 数的话,运输、指定、转运问题的解也总是整数 值
Ling Xueling 一、运输问题及其常规解法 4 、计算机求解及其特点 x11 = 3500 x12 = 1500 x22 = 2500 x23 = 2000 x24 = 1500 x31 = 2500 其余 xij = 0 o.f. = 39500 注意：最优解值都是整数！巧合？ 5、定理 若所有起运点的供货量和目的地的需求量都是整 数的话，运输、指定、转运问题的解也总是整数 值。 第一节 运输问题 凌晨: 凌晨:
凌晨: 第一节运输问题 运输问题及其常规解法 6、特殊情况及其处理 1)∑0≠∑D (1)S>D:不必修改模型,过剩供给会在最优解中以 松弛反应出来 (2)S<D:必须修改模型,(a)引入一个虚拟起运 点其供给量=D-S (b)从虚拟起点到任意 个目的地D之运输成本指定为0(不影响o.f.) 2)求最大化 若c1;表示的是单位利润和收入,只需相应改变o.f即可 3)有的路径无法使用:取消相关的x;即可
Ling Xueling 一、运输问题及其常规解法 6 、特殊情况及其处理 1） （1）S > D：不必修改模型，过剩供给会在最优解中以 松弛反应出来 （2）S < D：必须修改模型， （a）引入一个虚拟起运 点其供给量 ＝ D －S （b）从虚拟起点到任意 一个目的地 Dj 之运输成本指定为 0 （不影响 o.f. ） 2）求最大化 若 cij 表示的是单位利润和收入，只需相应改变 o.f. 即可 3）有的路径无法使用：取消相关的 xij 即可。 第一节 运输问题 凌晨: 凌晨: Oi Dj
凌晨: 第一节运输问题 运输问题及其常规解法 7、运输问题一般LP.模型 min∑∑cnxn st ∑x≤O(=12…m)供方结点 D j=1,2…)需方结点 ≥0
Ling Xueling 一、运输问题及其常规解法 7 、运输问题一般 L.P. 模型 供方结点 需方结点 第一节 运输问题 凌晨: 凌晨: 0 ( 1,2...... ) ( 1,2...... ) . . min 1 1 = = = = = i j m i i j j n j i j i i j i j x x D j n x O i m st c x
凌晨: 第一节运输问题 运输问题及其特殊的表格作业法求解 1、方法比较 1)LP方法一一只能使用于小、中型问题(若有100个起 运点和1000个目的地时,变量将有10000个) 2)特殊解法—一可以简化计算,对大型问题更有效率 2、特殊解法的思路 首先将问题用表格形式予以表达→>随意求一个初始可行解 然后进行迭代以改善解→直到求出最优解为止 3、例子及其表格作业法求解 1)例子 Foster公司3个 origins和4个 destinations之例
Ling Xueling 二、运输问题及其特殊的表格作业法求解 1、方法比较 1）L.P. 方法－－只能使用于小、中型问题（若有 100 个起 运点和 1000 个目的地时，变量将有 100,000 个） 2）特殊解法－－可以简化计算，对大型问题更有效率 2、特殊解法的思路 首先将问题用表格形式予以表达 → 随意求一个初始可行解 → 然后进行迭代以改善解 → 直到求出最优解为止 3、例子及其表格作业法求解 1）例子 Foster 公司 3 个 origins 和 4 个 destinations之例。 第一节 运输问题 凌晨: 凌晨: