文档介绍:运筹学运筹学刘新旺刘新旺博士博士副教授副教授研究领域研究领域: :物流与供应链管理、不确定决策与优化讲授课程讲授课程: :运筹学、现代企业管理系统、供应链管理单单位位: :东南大学经济管理学院(管理科学与工程系) E-mail E-mail : : xwliu xwliu ***@seu. 电电话话: : 83794008(H) 83794849 (O) 2 第三章第三章运输问题运输问题?运输问题是线性规划问题的特例。??产地产地:货物发出的地点。??销地销地:货物接收的地点。??产量产量:各产地的可供货量。??销量销量:各销地的需求数量。?运输问题就是研究如何组织调运,既满足各销地的需求,又使总运费最小。 3 网络表示网络表示供应商 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 32762 7534 2 554 第一节第一节运输模型运输模型某饮料在国内有三个生产厂,分布在城市 A 1、A 2、A 3, 其一级承销商有 4 个,分布在城市 B 1、B 2、B 3、B 4, 已知各厂的产量、各承销商的销售量及从 A i到B j 的每吨饮料运费为 C ij, 为发挥集团优势,公司要统一筹划运销问题,求运费最小的调运方案。一、运输问题举例 3 2 5 3 B 21 9 8 2 B 34 7 4 5 B 43 3A 32 7A 22销量 5 6A 1产量 B 1销地产地 5 第一节第一节运输模型运输模型(1) (1) 决策变量决策变量。设从 A i到B j的运输量为 x ij, (2) (2) 目标函数目标函数 minZ =6 x 11 +3 x 12 +2 x 13 +5 x 14 +7 x 21 +5 x 22 +8 x 23 +4 x 24+3x 31 +2 x 32 +9 x 33 +7 x 34 (3) (3) 约束条件约束条件。产量之和等于销量之和,故要满足: ?供应平衡条件 x 11+x 12+x 13+x 14 =5 x 21+x 22+x 23+x 24 =2 x 31+x 32+x 33+x 34 =3 ?销售平衡条件 x 11+x 21+x 31 =2 x 12+x 22+x 32 =3 x 13+x 23+x 33 =1 x 14+x 24+x 34 =1 ?非负性约束 x ij≥0 ( i =1,2,3 ;j =1,2,3,4) ?运输问题的 LP模型 6 第一节第一节运输模型运输模型销地产地二、表式运输模型 A m… A 2A 1a m… a 2a 1产量 B n… B 2B 1b n… b 2b 1销地 c mn … c m2 c m1………… c 2n… c 22c 21c 1n… c 12c 11x mn x m2 x m1 x 2n x 22x 21 x 1n x 12 x 117 第一节第一节运输模型运输模型?产销平衡三、运输问题的三种类型????? mi nj jiba 110 ,..., 2,1, ,..., 2,1, min 1 1 11?????????????? ij mi j ij nj i ij mi nj ij ijx njbx miax xcZ8 第一节第一节运输模型运输模型?产大于销????? mi nj jiba 110 ,..., 2,1, ,..., 2,1, min 1 1 11?????????????? ij mi j ij nj i ij mi nj ij ijx njbx miax xcZ9 第一节第一节运输模型运输模型?产小于销????? mi nj jiba 110 ,..., 2,1, ,..., 2,1, min 1 1 11?????????????? ij mi j ij nj i ij mi nj ij ijx njbx miax xcZ10 第一节第一节运输模型运输模型决策变量 m? n 约束方程 m+n 系数矩阵的结构如下: 四、运输模型的特点???????????????????????????????1 1 1 1 1 11 1 1 111 111 111?????????????? A x mn… x m2x m1………… x 2n… x 22x 21x 1n… x 12x 11 m行n列