华东理工大学：《运筹学动态规划》 运输问题讲义

云云 筹 公 输问题 学

Page:1 QSC 华东理工大学 工商经济学院 运筹学

经典运输问题 销售商 生产能力 供应商 Boston Chicago St Louis Lexington 吨 Cleveland Bedford York 372 255 635 5,00 6,000 2.500 需求量吨)6004002,001500 每吨运输成本($/吨

Page:2 QSC 华东理工大学 工商经济学院 运筹学 经典运输问题 销售商 供应商 Boston Chicago St. Louis Lexington 生产能力 (吨) Cleveland 3 2 7 6 5,000 Bedford 7 5 2 3 6,000 York 2 5 4 5 2,500 需求量(吨) 6,000 4,000 2,000 1,500 每吨运输成本(＄/吨)

网络表示 销售商 6,000 供应商 00 Cleveland 2 6 7 Icago 4,000 6,000 Bedford 2,000 2,500 York 1,500

Page:3 QSC 华东理工大学 工商经济学院 运筹学 网络表示 供应商 1 Cleveland 2 Bedford 3 York 2 Chicago 1 Boston 3 St. Louis 4 Lexington 销售商 5,000 2,500 6,000 6,000 1,500 2,000 4,000 3 2 6 7 2 7 5 3 4 2 5 5

线性规划模型 Min za +2x,+7x 13+614+7x 21+5x22+2x23+3x24+2x31+5x32+4x3+5x34 S. t 22 X31+x2+X33+x34 21 0

Page:4 QSC 华东理工大学 工商经济学院 运筹学 线性规划模型 Min Z= 3x11 +2x 12 +7x 13 +6x 14 +7x 21 +5x 22 +2x 23 +3x 24 +2x 31 +5x 32 +4x 33 +5x 34 S. t. x11 +x 12 +x 13 +x 14 ≤5000 x21 +x 22 +x 23 +x 24 ≤6000 x31 +x 32 +x 33 +x 34 ≤2500 x11 +x 21 +x 31 = 6000 x11 +x 21 +x 31 = 4000 x11 +x 21 +x 31 = 2000 x11 +x 21 +x 31 = 1500 xij 0

运输问题线性规划的一般形式 m n Minz=∑∑ n St.供应: ∑x1=S1i=1,2 需求: ∑x n m,J n

Page:5 QSC 华东理工大学 工商经济学院 运筹学 运输问题线性规划的一般形式 = = m i 1 n j 1 ij ij Min z = c x x s i =1,2, ,m n j 1  i j i  = = x d j =1,2, ,n m i 1  i j j  = = xi j  0, i =1,2, ,m; j =1, ,n st. 供应： 需求：

供求平衡问题的特征 基变量的个数=m+n-1

Page:6 QSC 华东理工大学 工商经济学院 运筹学 供求平衡问题的特征 s d n j 1 j m i 1  i  = = ➢ = ➢ 基变量的个数=m+n-1

初始基本可行解的构造

Page:7 QSC 华东理工大学 工商经济学院 运筹学 初始基本可行解的构造

西北角方法 Boston Chicago S. Louis Lexington供应量 Cleveland s}③ 2 中… 5,09Q 00 B editor d 000 4000 1000 YOrk 5 00 1000 1500 1500 需求量6,004,002,001,500

Page:8 QSC 华东理工大学 工商经济学院 运筹学 西北角方法 供应量 3 2 7 6 7 5 2 3 2 5 4 5 需求量 Boston Chicago St. Louis Lexington Cleveland 5,000 Bedford 6,000 York 2,500 6,000 4,000 2,000 1,500 5000 1000 0 1000 0 5000 4000 0 1000 1000 0 1000 1000 0 1500 1500

最小元素法 Boston Chicago S. Louis Lexington供应量 Cleveland 5,009 1000400 Bedford 6,009 1500 400 2500 2000 2500 York 5 4…-5-2,50 2500 需求量6,04,002,001,500 3509 2500

Page:9 QSC 华东理工大学 工商经济学院 运筹学 最小元素法 供应量 3 2 7 6 7 5 2 3 2 5 4 5 需求量 Boston Chicago St. Louis Lexington Cleveland 5,000 Bedford 6,000 York 2,500 6,000 4,000 2,000 1,500 4000 0 1000 2500 2000 1500 3500 0 0 2500 2500 4000 0 0 2500 1000

运输问题的特殊解法 闭回路方法 检验数:非基变量增加一个单位引起的成本变化量

Page:10 QSC 华东理工大学 工商经济学院 运筹学 运输问题的特殊解法 ——闭回路方法 检验数：非基变量增加一个单位引起的成本变化量