运输问题 运输问题的表示 网络图、线性规划模型、运输表 区初始基础可行解 西北角法、最小元素法 求解方法 闭回路法、对偶变量法 ● 特殊形式运输问题 不平衡问题、转运问题
运输问题 运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 西北角法、最小元素法 求解方法 闭回路法、对偶变量法 特殊形式运输问题 不平衡问题、转运问题
运输问题网络图 供应地 运价 需求地 d1=22 S1=14 67 5 2 d2-13 供应量 S2=27 2 S3=19 3 8+28步06 需求量 3 d3=12 4 d4=13
23 2 1 341 运输问题网络图 s2=27 s3=19 d 1=22 d 2=13 d3=12 d4=13 s 1=14 供应量 供应地 运价 需求量 需求地 675 3842759 106
运输问题线性规划模型 mnZ=6x11+7x12+5x13+3x14+8x21+4x22+2x23+7x24+5x31+9X32+10x33+6x34 S.tX1+X12+X13+X14 =14 X21+X22+X23+X24 =27 X31+X32+X3+X34 =19 供应地约束 X 十X21 +X31 =22 +X22 +X32 -15 X13 十X3 +X33 =12 需求地约束 X14 +X24 +X34 =13 X11X12X13X14X21X2X23 X24X31X32X3X34 ≥0 min 一般情形：有m x20 =∑%，∑4cx) 各供应地，n个 5t. 需求地，则有 ∑%xy=ayj=1,2,…,n ∑x)=b,i=12,…,m
运输问题线性规划模型 x x x x x x x x x x x x 0 x x x 13 x x x 12 x x x 13 x x x 22 x x x x 19 x x x x 27 s.t. x x x x 14 min z 6x 7x 5x 3x 8x 4x 2x 7x 5x 9x 10x 6x 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 1 4 2 4 3 4 1 3 2 3 3 3 1 2 2 2 3 2 1 1 2 1 3 1 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 + + = + + = + + = + + = + + + = + + + = + + + = = + + + + + + + + + + + 供应地约束需求地约束 一般情形：有 m 各供应地， n 个 需求地，则有 x b i m s t x a j n z c x i nj i j i mi i j mi nj i j i j xij , 1,2, , . . , 1,2, , min = 11 1 1 0 = = = = == = =
运输问题的表格表示—运输表 需求地 2 3 4 供应地 供应量 6 7 5 3 1 4 X12 X13 X14 8 4 2 7 2 27 X21 X22 X23 X24 5 9 10 6 3 19 X31 X32 X33 X34 60 需求量 22 13 12 13 60
运输问题的表格表示——运输表 需求地 供应地 1 2 3 4 供 应 量 1 6 7 5 3 14 x11 x12 x13 x14 2 8 4 2 7 27 x21 x22 x23 x24 3 5 9 10 6 19 x31 x32 x33 x34 需求量 22 13 12 13 60 60
初始基础可行运输方案一西北角法 1 2 3 4 6 7 5 3 14 14 8 2 7 2 27 8 13 6 5 9 10 6 3 19 6 +13 22 13 12 13
初始基础可行运输方案—西北角法 8 13 13 14 6 6 1 2 3 4 1 6 7 5 3 14 2 8 4 2 7 27 3 5 9 10 6 19 22 13 12 13
初始可行解运输方案确定一最小元素法 依运费从小到大的次序安排运输方案，知道所有限制满足 3 6 7 5 3 13 9 2 271520 13 12 5 10 6 19 19 13 12 13 2320 0 0
初始可行解运输方案确定—最小元素法 1 2 3 4 1 6 7 5 3 14 2 8 4 2 7 27 3 5 9 10 6 19 22 13 12 13 12 0 15 13 0 1 13 0 2 19 3 1 0 2 0 2 0 0 依运费从小到大的次序安排运输方案, 知道所有限制满足 !
空格改进指数计算一闭▣路法(1) 2 3 4 6 5 3 14 14王 (5 8 4 2 7 2 27 8- -13 6 5 9 10 6 3 19 6 13 22 13 12 13 单位费用变化：7+8一6一4=5
1 2 3 4 6 7 5 3 1 14 14 8 4 2 7 2 8 13 6 27 5 9 10 6 3 6 13 19 22 13 12 13 5 空格改进指数计算—闭回路法(1) 单位费用变化：7＋8－6－4＝5 + + − −
闭回路法(2 1 2 3 4 6 7 5 3 1 14 一14 8 4 2 7 2 27 + 8- 6 5 9 10 6 3 19 6 13 22 13 12 13 单位费用变化：5+8一6一2=5
1 2 3 4 6 7 5 3 1 14 14 8 4 2 7 2 8 13 6 27 5 9 10 6 3 6 13 19 22 13 12 13 5 闭回路法(2) 5 + + − − 单位费用变化：5＋8－6－2＝5
闭回路法(3) 2 3 4 6 7 5 3 1 14 —14 8 4 2 7 2 27 8- 4】 5 9 10 6 3 19 十6 13 22 13 12 13 单位费用变化：3+10+8一6一2一6=7
1 2 3 4 6 7 5 3 1 14 14 8 4 2 7 2 8 13 6 27 5 9 10 6 3 6 13 19 22 13 12 13 5 闭回路法(3) 5 7 + − + − + − 单位费用变化：3＋10＋8－6－2－6＝7
闭回路法(4) 1 2 3 4 6 7 5 3 14 14 5 5 8 4 2 7 2 27 8 13 5 9 10 6 3 19 +6 13 22 13 12 13 单位费用变化：7+10一6一2=9
1 2 3 4 6 7 5 3 1 14 14 8 4 2 7 2 8 13 6 27 5 9 10 6 3 6 13 19 22 13 12 13 5 闭回路法(4) 9 5 7 单位费用变化：7＋10－6－2＝9 + + − −