Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 Data Model and decisions 数据、模型与决策 第六章 Transportation and Assignment Problems 运输问题和指派问题 RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 Data, Model and Decisions 数据、模型与决策 第六章 Transportation and Assignment Problems 运输问题和指派问题
Chapter 6 Transportation and Assignment Problems 本章内容T OpIcs 运输问题和指派问题 The Transportation Problem 运输问题及其数学模型 Transportation Problem example 运输问题举例 Characteristics of Transportation Problems运输问题的特征 An Award-Winning Application 运输问题的一个获奖应用 Variants of Transportation Problems 各种运输问题变体 The assignment problem 指派问题 The model for assignment problem 指派问题模型 Variants ofassignment problem 指派问题的变形 pplications of assignment problem 指派问题的应用 案例63项目选择(指派问题) RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 本章内容Topics ▪ The TransportationProblem 运输问题及其数学模型 ▪ Transportation ProblemExample 运输问题举例 ▪ Characteristics of TransportationProblems 运输问题的特征 ▪ An Award-WinningApplication 运输问题的一个获奖应用 ▪ Variants of TransportationProblems 各种运输问题变体 ▪ The Assignment Problem 指派问题 ▪ The Model for AssignmentProblem 指派问题模型 ▪ Variants of Assignment Problem 指派问题的变形 ▪ Applications of Assignment Problem 指派问题的应用 ▪ 案例6.3 项目选择（指派问题）
Chapter 6 Transportation and Assignment Problems The Transportation Problem运输问题和指派问题 运输问题 物流中的一个普遍问题是如何以尽可能小的成本把货 物从一系列起始地( sources)(如工厂、仓库)运输 到一系列目的地( destinations)(如仓库、顾客) ources Destination ) RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 The Transportation Problem 运输问题 • 物流中的一个普遍问题是如何以尽可能小的成本把货 物从一系列起始地（sources）（如工厂、仓库）运输 到一系列目的地（destinations）（如仓库、顾客） Sources Destinations
Chapter 6 Transportation and Assignment Problems Transportation Network运输问题和指派问题 运输问题的网络表示 供应地 运价 需求地 d1=13 6 S1=25 3 2)d2=21 供应量一 10(2 2 需求量 15(310 6 d4=7 RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 Transportation Network 运输问题的网络表示 2 3 2 1 3 4 1 s2=10 s3=15 d1=13 d2=21 d3=9 d4=7 s1=25 供 应 量 供应地 运价 需 求 量 需求地 6 7 5 3 8 4 2 7 5 9 10 6
Chapter 6 Transportation and Assignment Problems The Transportation Problem 运输问题和指派问题 Model运输问题的数学模型 设在若干个地点(发点)A1A2,Am集中了同 一种类的物资,其发出量分别为a1a2…,a 现在要把这些物资调运给其它若干个需要这种 物资的地点(收点)B1,B2Bn,设这些地点 的需要量分别为b12b2,bno 已知从A运送一个单位物资到B的运费为c。问 怎样制定运输方案,才能使总运费最少? RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 The Transportation Problem Model 运输问题的数学模型 • 设在若干个地点（发点）A1 ,A2 ,…Am集中了同 一种类的物资，其发出量分别为a1 ,a2 ,…,am • 现在要把这些物资调运给其它若干个需要这种 物资的地点（收点）B1 ,B2 ,….Bn，设这些地点 的需要量分别为b1 ,b2 ,…,bn。 • 已知从Ai运送一个单位物资到Bj的运费为cij。问 怎样制定运输方案，才能使总运费最少？
Chapter 6 Transportation and Assignment Problems The Transportation Problem 运输问题和指派问题 Model运输问题的数学模型(续) 1当a(=1,2…m)b(=12…m)满足条件∑a=∑ 时,称为平衡运输问题(总产量=总销量) 2、用x;表示从A运到B的物资数量,则x;应满足约束条件: ∑ a1(i=12,…,m)∑x x;≥0(非负)(i=1,2,…,m;j=1,2,,,n) 3、运输问题为:求x1满足1,2,并使总运费C=∑∑cx 达到最小 RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 The Transportation Problem Model 运输问题的数学模型（续） 1、当ai（i=1,2,…m） bj（j=1,2,…,n） 满足条件 时，称为平衡运输问题（总产量＝总销量） 2、用xij表示从Ai运到Bj的物资数量，则xij应满足约束条件： xij0（非负）(i=1,2,…,m;j=1,2,…,n) 3、运输问题为：求xij满足1，2，并使总运费 达到最小 1 1 m n i j i j a b = = = 1 ( 1,2,..., ) n ij i j x a i m = = = 1 ( 1,2,..., ) m i j j i x b j n = = = 1 1 c m n ij ij i j C x = = =
Chapter 6 Transportation and Assignment Problems The transportation Problem运输问题和指派问题 Mode运输问题的数学模型(续) 于是得平衡运输问题的数学模型为 Min ∑∑cn m)从A运送出去的量=供应量a, n)收点B收到的量=需求量b 其中ai和b满足∑a=∑b平衡运输条件 这就是平衡运输问题的数学模型,它包含了m×n个决策变量x1,…,xm x2,3….x2n…,xmn,xn2,…,m,还包含了mtn个等式(确定需求)约束, 以及平衡运输条件。 RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 The Transportation Problem Model 运输问题的数学模型（续） 于是得平衡运输问题的数学模型为： 其中 ai和bj满足 这就是平衡运输问题的数学模型，它包含了m×n个决策变量x11,…,x1n, x21,…x2n,… xm1,xm2,…xmn，还包含了m+n个等式（确定需求）约束， 以及平衡运输条件。 1 1 m n i j i j a b = = = 平衡运输条件 1 1 i 1 j j 1 Min c 1, 2, , ) a s.t. ( 1, 2, , B b 0 (i=1,2, ,m; j=1,2, ,n) m n ij ij i j n ij i j m ij j i ij C x x a i m x b j n x = = = = = = = = = ( 从Ai运送出去的量＝供应量 ) 收点 收到的量＝需求量 非负
Chapter 6 Transportation and Assignment Problems The Transportation Problem运输问题和指派问题 Mode运输问题的数学模型(续) 注意:1、平衡运输问题有最优解 2、运输问题有各种变体:主要是由于不满足条件 称为不平衡运输问题。 当产大于销,即∑a>∑b这时,运输问题的数学模型为: Min c x 在 Excel,只需根据“产量> 销量”或“产量<销量"将 l 原来的“a约束=a;改为 "<=a1"”或“b约束"=b s. t 改为<=b ≥0(=1,2 当供不应求(产小于销),处理方法类似 RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 The Transportation Problem Model 运输问题的数学模型（续） 注意：1、平衡运输问题有最优解 2、运输问题有各种变体：主要是由于不满足条件 称为不平衡运输问题。 当产大于销，即 这时，运输问题的数学模型为： 当供不应求（产小于销），处理方法类似 1 1 m n i j i j a b = = = 1 1 m n i j i j a b = = 1 1 1 1 Min C c 1, 2, , s.t. 1, 2, , ) 0 ( 1, 2, , ; 1, 2, , ) m n ij ij i j n ij i j m ij j i ij x x a i m x b j n x i m j n = = = = = = = = = = （ ） （ 在Excel,只需根据“产量> 销量”或“产量<销量"将 原来的“ai约束"=ai "改为 "<=ai "”或“bj约束"=bj " 改为"<=bj
Chapter 6 Transportation and Assignment Problems 61P& T Company Distribution Proble问题和指派间题 案例研究:P&T公司的配送问题P189 P&T公司是一家由家族经营的小公司。它收购生菜并在食品罐 头厂中把它们加工成为罐头,然后再把这些罐头食品分销到各地 卖出去。 这个公司的一个主要产品是豌豆罐头。这些豌豆罐头在三个食品 罐头厂(靠近华盛顿的贝林翰;俄勒冈州的尤基尼;明尼苏达州 的艾尔贝李)加工,然后用卡车把它们运送到美国西部的四个 分销仓库(加利福尼亚州的萨克拉门托;犹他州盐湖城;南达科 他州赖皮特城;新墨西哥州澳尔巴古)。 许多年来,公司一直根据经验,有一套从每个罐头加工工厂运送 到各个仓库的运输方案 但总觉得可以改进,主要原因是因为近期的运营成本正在迅速增 长,而利润却没有得到同样的增长。 RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 6.1 P&T Company Distribution Problem 案例研究： P&T公司的配送问题P189 • P&T公司是一家由家族经营的小公司。它收购生菜并在食品罐 头厂中把它们加工成为罐头，然后再把这些罐头食品分销到各地 卖出去。 • 这个公司的一个主要产品是豌豆罐头。这些豌豆罐头在三个食品 罐头厂（靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州 的艾尔贝·李）加工，然后用卡车把它们运送到美国西部的四个 分销仓库(加利福尼亚州的萨克拉门托；犹他州盐湖城；南达科 他州赖皮特城；新墨西哥州澳尔巴古)。 • 许多年来，公司一直根据经验，有一套从每个罐头加工工厂运送 到各个仓库的运输方案。 • 但总觉得可以改进，主要原因是因为近期的运营成本正在迅速增 长，而利润却没有得到同样的增长
Chapter 6 Transportation and Assignment Problems P&T公司运输问题的网络表述P195运输问题和指派问题 供应中心称为出发地( Source)l在左边,接收中心称为目的地 destinations在右边,旁边的数字表示供应量和需求量。箭头表示运 输的可能途径,旁边的数字表示单位运输成本。比较形象、直观。 Supplies De mands Dest inations our es 464 180(Sacramento) (Bellingham)75(S D2)65( Salt Lake City (Eugene)125(S 0 99 682 D3)70(Rapid City) 388 (Albert Lea)oo( s D485(Albuquerque) RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 P&T公司运输问题的网络表述P195 • 供应中心[称为出发地（Source）]在左边，接收中心[称为目的地 (destinations)]在右边，旁边的数字表示供应量和需求量。箭头表示运 输的可能途径，旁边的数字表示单位运输成本。比较形象、直观。 S1 S2 S3 D4 D2 D1 D3 75 125 100 80 65 70 85 Supplies Demands Sources Destinations (Bellingham) (Eugene) (Albert Lea) (Sacr amento) (Salt Lake City) (Rapid City) (Albuquerque) 464 513 654 867 352 416 690 791 995 682 685 388