Chapter 6. Transportation and Assignment Problems

Presentation on theme: "Chapter 6. Transportation and Assignment Problems"— Presentation transcript:

1 Chapter 6. Transportation and Assignment Problems
第六章. 运输问题和指派问题

2 Table of Contents (主要内容)
The P&T Company Distribution Problem (Section 6.1)(P&T公司的配送问题) Characteristics of Transportation Problems (Section 6.2)(运输问题的特征) Variants of Transportation Problems: Better Products (Section 6.3)(运输问题的变形：求佳产品公司问题)

3 Table of Contents (主要内容)
Variants of Transportation Problems: Nifty (Section 6.3)(运输问题的变形：耐芙迪公司问题) Applications of Transportation Problems: Metro Water (Section 6.4)(运输问题的应用：米德罗水管站问题) Applications of Transportation Problems: Northern Airplane (Section 6.4)(运输问题的应用：北方飞机制造公司问题)

4 Table of Contents (主要内容)
Applications of Transportation Problems: Middletown (Section 6.4)(运输问题的应用：米德尔学区问题) Applications of Transportation Problems: Energetic (Section 6.4)(运输问题的应用：源丰公司问题) A Case Study: Texago Corp. Site Selection Problem (Section 6.5)(运输问题的应用：特赛格公司的选址问题)

5 Table of Contents (主要内容)
Characteristics of Assignment Problems: Sellmore (Section 6.6)(指派问题的特征：塞尔默公司问题) Variants of Assignment Problems: Job Shop (Section 6.7)(指派问题的变形：娇普肖普公司问题) Variants of Assignment Problems: Better Products (Section 6.7)(指派问题的变形：求佳产品公司问题) Variants of Assignment Problems: Revised Middletown (Section 6.7)(指派问题的变形：米德尔学区的新问题)

6 P&T Company Distribution Problem
罐头厂1-贝林翰 罐头厂2-尤基尼 仓库3-赖皮特城 罐头厂3-艾尔贝 仓库2-盐湖城 仓库1-萨克拉门托 仓库4-奥尔巴古

7 P&T Company Distribution Problem
贝林翰先满足萨克拉门托，剩余的运送到盐湖城 艾尔贝先满足奥尔巴古，剩余的运送到赖皮特 尤基尼满足剩余需求

8 Shipping Data

9 Shipping Cost per Truckload

10 P&T Company Distribution Problem
当前的配送结果是什么？总配送成本是多少？

11 Current Shipping Plan Total shipping cost = 75($464) + 5($352) + 65($416) + 55($690) + 15($388) + 85($685) = $165,595

12 P&T Company Distribution Problem
试建立该网络配送问题的数学模型？

13 运输问题关心的是以最低的总配送成本把出发地的任何产品运送到每一个目的地

14 Terminology for a Transportation Problem

15 Characteristics of Transportation Problems
The Requirements Assumption (需求假设) Each source has a fixed supply of units, where this entire supply must be distributed to the destinations. (每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地) Each destination has a fixed demand for units, where this entire demand must be received from the sources. (每一个目的地都有一个固定的需求量，所有的需求量都必须由出发地满足)

16 Characteristics of Transportation Problems
The Feasible Solutions Property (可行解特性) A transportation problem will have feasible solutions if and only if the sum of its supplies equals the sum of its demands. (当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解)

17 Characteristics of Transportation Problems
The Cost Assumption (成本假设) The cost of distributing units from any particular source to any particular destination is directly proportional to the number of units distributed. (从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系) This cost is just the unit cost of distribution times the number of units distributed. (这个成本就等于配送的单位成本乘以所配送的数量)

18 The Transportation Model
Any problem (whether involving transportation or not) fits the model for a transportation problem if (任何满足下述两个条件的问题都可以建模成运输问题) It can be described completely in terms of a table like Table 6.5 that identifies all the sources, destinations, supplies, demands, and unit costs, and (完全描述成如表6.5所示的参数表形式，明确出发地、目的地、供应量、需求量和单位成本)

19 The Transportation Model
satisfies both the requirements assumption and the cost assumption. (同时满足需求假设和成本假设) The objective is to minimize the total cost of distributing the units. (目标就是要使配送总成本最小)

20 The P&T Co. Transportation Problem
运输问题模型参数表(供应量、需求量和单位成本)

21 Spreadsheet Formulation

22 Network Representation

23 运输问题的网络表述 忽略出发地和目的地在地理上的布局 左边一列为出发地(S)，旁边的数字代表供应量 右边一列为目的地(D)，旁边的数字代表需求量 箭头表示可能的运输途径，其上面的数字代表单位运输成本

24 The Transportation Problem is an LP
Let xij = the number of truckloads to ship from cannery i to warehouse j (假设xij是从第i个罐头加工厂运送到第j个仓库的车数) (i = 1, 2, 3; j = 1, 2, 3, 4) Minimize Cost = $464x11 + $513x12 + $654x13 + $867x14 + $352x21 + $416x22 + $690x23 + $791x24 + $995x31 + $682x32 + $388x33 + $685x34

25 The Transportation Problem is an LP
subject to (约束) Cannery 1: x11 + x12 + x13 + x14 = 75 Cannery 2: x21 + x22 + x23 + x24 = 125 Cannery 3: x31 + x32 + x33 + x34 = 100 Warehouse 1: x11 + x21 + x31 = 80 Warehouse 2: x12 + x22 + x32 = 65 Warehouse 3: x13 + x23 + x33 = 70 Warehouse 4: x14 + x24 + x34 = 85 and xij ≥ 0 (i = 1, 2, 3; j = 1, 2, 3, 4)

26 Integer Solutions Property
As long as all its supplies and demands have integer values, any transportation problem with feasible solutions is guaranteed to have an optimal solution with integer values for all its decision variables. Therefore, it is not necessary to add constraints to the model that restrict these variables to only have integer values.

27 整数解性质 只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件

28 求解(最优化)算法 单纯形法 网络单纯形法 运输单纯形法 算法的适应范围越小，求解效率越高

29 Distribution System at Proctor and Gamble
Proctor and Gamble needed to consolidate and re-design their North American distribution system in the early 1990’s. (Proctor & Gamble公司需要巩固并再设计其九十年代早期在北美建立起来的配送系统) 50 product categories (50个产品种类) 60 plants (60家工厂) 15 distribution centers (15个配送中心) 1000 customer zones (1000个客户区) 获奖作品

30 Distribution System at Proctor and Gamble
Solved many transportation problems (one for each product category). (解决大量运输问题，每个产品种类都存在一个运输问题) Goal: find best distribution plan, which plants to keep open, etc. (目标：寻找最优的配送方案，哪些工厂保持开放) Closed many plants and distribution centers, and optimized their product sourcing and distribution location. (关闭许多工厂和配送中心，优化产品来源和配送点) Implemented in Saved $200 million per year. (1996年实施，北美工厂数减少20%，每年给公司节约2亿美金)

31 Modeling Variants of Transportation Problem
The sum of the supplies exceeds the sum of the demands. (供应总量超过需求总量) The sum of the supplies is less than the sum of the demands. (供应总量小于需求总量) A destination has both a minimum demand and a maximum demand. (一个目的地同时存在最小需求和最大需求) Certain source-destination combinations cannot be used for distributing units. (在配送中不能使用特定的出发地-目的地组合) The objective is to maximize the total profit. (目标是最大化总利润)

32 Better Products (Assigning Plants to Products)
The Better Products Company has decided to initiate the product of four new products, using three plants that currently have excess capacity. (求佳产品公司决定使用三个有生产余力的工厂进行四种新产品的生产制造)

33 Better Products (Assigning Plants to Products)
生产能力 产品 1 2 3 4 工厂 41 27 28 24 75 40 29 - 23 37 30 21 45 需求的产量 20 表示不存在数据的单元格

34 Transportation Problem Formulation

35 Better Products (Assigning Plants to Products)
Which plants should produce which products? 哪个工厂应该生产哪种产品？

36 Spreadsheet Formulation

37 Nifty Co. (Choosing Customers)
The Nifty Company specializes in the production of a single product, which it produces in three plants. (耐芙迪公司在3个工厂中专门生产一种产品) Four customers would like to make major purchases. There will be enough to meet their minimum purchase requirements, but not all of their requested purchases. (订单主要来自四个客户，公司能够满足他们的最低购买要求，但是无法满足他们的所有购买要求)

38 Nifty Co. (Choosing Customers)
Due largely to variations in shipping cost, the net profit per unit sold varies depending on which plant supplies which customer. (主要是由于运输成本的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪个客户)

39 Data for the Nifty Company

40 Nifty Co. (Choosing Customers)
How many units should Nifty sell to each customer and how many units should they ship from each plant to each customer? 耐芙迪公司应该销售给每个客户多少产品？应该从每个工厂运送多少产品至每个客户？

41 Spreadsheet Formulation

42 Metro Water (Distributing Natural Resources)
Metro Water District is an agency that administers water distribution in a large geographic region. The region is arid, so water must be brought in from outside the region. (米德罗水管站是一个主管着广阔地域的水资源分配机构，由于这个地域十分干燥，所以这个机构需要从外地引水)

43 Metro Water (Distributing Natural Resources)
Sources of imported water: Colombo, Sacron, and Calorie rivers. (水源主要有：科伦坡河、塞克隆河和卡路里河) Main customers: Cities of Berdoo, Los Devils, San Go, and Hollyglass. (主要的客户有：布都城、劳斯戴维斯城、圣哥城和豪利格拉斯城)

44 Metro Water (Distributing Natural Resources)

45 Metro Water (Distributing Natural Resources)
How much water should Metro take from each river, and how much should they send from each river to each city? 应该从每条河里获取多少水资源？应该从每条河里向各个城市输送多少水资源？

46 Spreadsheet Formulation

47 Northern Airplane (Production Scheduling)
Northern Airplane Company produces commercial airplanes. The last stage in production is to produce the jet engines and install them. (北方飞机制造公司为全世界的航空公司生产各种商务飞机。制造过程的最后一步是生产喷气发动机并把它们安装到已经完成的飞机框架上去)

48 Northern Airplane (Production Scheduling)
The company must meet the delivery deadline indicated in column 2. (公司必须满足交货期的限制) Production and storage costs vary from month to month. (生产和存储成本每个月都有可能发生变化)

49 Northern Airplane (Production Scheduling)

50 Northern Airplane (Production Scheduling)
How many engines should be produced in each of the four months so that the total of the production and storage costs will be minimized? 每个月各生产多少航空发动机可以使生产和存储总成本最低？

51 Spreadsheet Formulation

52 Optimal Production at Northern Airplane

53 Middletown School District
Middletown School District is opening a third high school and thus needs to redraw the boundaries for the area of the city that will be assigned to the respective schools. (米德尔城学区开办了第三所中学，需要为每一所学校重新划定这个城市内的服务区域) The city has been divided into 9 tracts with approximately equal populations. (这个城市被分成了拥有大致相同数量人口的9个区域)

54 Middletown School District
Each school has a minimum and maximum number of students that should be assigned. (每一所中学都有一个最小和最大的学生数目的要求) The school district management has decided that the appropriate objective is to minimize the average distance that students must travel to school. (学区管理者认为划分学区界限的适当目标是使学生到学校的平均路程最短)

55 Data for the Middletown School District

56 Middletown School District
How many students from each tract should be assigned to each school? 各个区域应该有多少学生被分配到各个学校？

57 Spreadsheet Formulation

58 Energetic (Meeting Energy Needs)
The Energetic Company needs to make plans for the energy systems for a new building. (源丰公司需要为新的建筑物建立起能源系统)

59 Energetic (Meeting Energy Needs)
The energy needs fall into three categories: (能源需求主要来源于三个方面) electricity (20 units) (电，20个单位) heating water (10 units) (热水，10个单位) heating space (30 units) (建筑物内取暖，30个单位)

60 Energetic (Meeting Energy Needs)
The three possible sources of energy are (满足这些需求的三个可能的能源来源是) Electricity (电) natural gas (天然气) solar heating unit (limited to 30 units because of roof size) (安装在屋顶上的太阳能加热装置，由于屋顶大小的限制，太阳能的能源量只有30个单位)

61 Cost Data for Energetic

62 Energetic (Meeting Energy Needs)
How should Energetic meet the energy needs for the new building? 源丰公司应该如何来满足新建筑的能源需求？

63 Spreadsheet Formulation

64 当需求大于供应时，供应前用“=”，需求前用“<=”； 当供应大于需求时，需求前用“=”，供应前用“<=”；
使用符号的总结 当需求大于供应时，供应前用“=”，需求前用“<=”； 当供应大于需求时，需求前用“=”，供应前用“<=”； 当告知范围时，则按要求直接给定相应的符号即可

65 案例研究：特塞格公司的选址问题 特塞格公司(Texago)是一家设在美国本土的大型一体化石油公司，包括多个油田、炼油厂和配送中心
为了满足持续增长的市场需求，公司决定新建一个炼油厂，有3个备选地点 自产原油不够时可从中东地区购买

66 案例研究：特塞格公司的选址问题 需要确定新炼油厂的位置，以及从每一个原油供应点到每一个炼油厂的原油供应量，从每一个炼油厂到每一个配送中心的成品油配送量，以使总运作成本最低 成本包括：原油配送成本、成品油配送成本、炼油厂运营成本 可把问题分解成两种(原油配送和成品油配送)6(=2*3)个运输问题

67 Location of Texago’s Facilities

68 Potential Sites for Texago’s New Refinery

69 Production Data for Texago

70 Cost Data for Shipping to Refineries

71 Cost Data for Shipping to Distribution Centers

72 Estimated Operating Costs for Refineries

73 Basic Spreadsheet for Shipping to Refineries

74 Shipping to Refineries, Including Los Angeles

75 Shipping to Refineries, Including Galveston

76 Shipping to Refineries, Including St. Louis

77 Basic Spreadsheet for Shipping to D.C.’s

78 Shipping to D.C.’s When Choose Los Angeles

79 Shipping to D.C.’s When Choose Galveston

80 Shipping to D.C.’s When Choose St. Louis

81 当前最优决策是选择在St. Louis(圣路易斯)建厂。但是还有很多其它因素值得进一步考虑！
Annual Variable Costs 当前最优决策是选择在St. Louis(圣路易斯)建厂。但是还有很多其它因素值得进一步考虑！

82 Sellmore Company Assignment Problem
The marketing manager of Sellmore Company will be holding the company’s annual sales conference soon. (塞尔默公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议) 指派问题

83 Sellmore Company Assignment Problem
He is hiring four temporary employees: (他雇用了四个临时员工) Ann (安) Ian (伊恩) Joan (琼) Sean (肖恩)

84 Sellmore Company Assignment Problem
Each will handle one of the following four tasks: (每一个人负责完成下面的一项任务) Word processing of written presentations (书面陈述的文字处理) Computer graphics for both oral and written presentations (制作口头和书面陈述的计算机图形)

85 Sellmore Company Assignment Problem
Preparation of conference packets, including copying and organizing materials (会议材料的准备，包括书面材料的抄写和组织) Handling of advance and on-site registration for the conference (处理与会者的提前和当场注册报名)

86 Data for the Sellmore Problem

87 Sellmore Company Assignment Problem
Which person should be assigned to which task? 哪个人应该负责哪项工作？

88 Spreadsheet Formulation
增加0-1变量表示任务的分配

89 The Model for Assignment Problems
Given a set of tasks to be performed and a set of assignees who are available to perform these tasks, the problem is to determine which assignee should be assigned to each task. (给定了一系列所要完成的任务以及一系列完成任务的被指派者，所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务)

90 The Model for Assignment Problems
To fit the model for an assignment problem, the following assumptions need to be satisfied: (为了符合指派问题的模型，需要满足下面的一些假设) The number of assignees and the number of tasks are the same. (被指派者的数量和任务的数量是相同的) Each assignee is to be assigned to exactly one task. (每一个被指派者只完成一项任务)

91 The Model for Assignment Problems
Each task is to be performed by exactly one assignee. (每一项任务只能由一个被指派者来完成) There is a cost associated with each combination of an assignee performing a task. (每一个被指派者和每一项任务的组合都会有一个相关的成本) The objective is to determine how all the assignments should be made to minimize the total cost. (问题的目标是要确定怎样进行指派才能使得总成本达到最小)

92 The Network Representation

93 需要选择箭头，从每一个被指派者指向每一项任务 每一个箭头旁边的数字代表如果这个指派被选中的话，其成本的大小
指派问题的网络表示法 所有指派者都按照次序排列在左边 需要完成的任务都排列在右边 箭头代表每一个可能的指派 需要选择箭头，从每一个被指派者指向每一项任务 每一个箭头旁边的数字代表如果这个指派被选中的话，其成本的大小

94 指派问题是一种特殊的运输问题 被指派者：出发地 任务：目的地 每一个出发地的供应量都为1 每一个目的地的需求量都为1

95 指派问题的变形 某些被指派者不能进行某些任务 任务比被指派者多 被指派者比任务多 每一个被指派者可以被指派给多于一个的任务 每一项任务可以由多个被指派者共同完成

96 Job Shop (Assigning Machines to Locations)
The Job Shop Company has purchased three new machines of different types. (娇普肖普公司购买了三种不同类型的新设备) There are five available locations where the machine could be installed. (车间里有五个不同的地点可供安装)

97 Job Shop (Assigning Machines to Locations)
Some of these locations are more desirable for particular machines because of their proximity to work centers that will have a heavy work flow to these machines. (其中某些地点比其他地点更为适合某些机器，因为他们十分接近工作中心，流入和流出这些设备的工作很多)

98 Materials-Handling Cost Data

99 Job Shop (Assigning Machines to Locations)
How should the machines be assigned to locations? 设备应该安装到什么位置更加合理？

100 Spreadsheet Formulation

101 产品生产分解将产生隐性成本：额外的设置、配送和管理费用等
求佳产品公司问题再研究 产品生产分解将产生隐性成本：额外的设置、配送和管理费用等 新问题：已知如表6.6所示的数据，使把每一个工厂指派给至少一个新产品(每一种新产品只能在一个工厂生产)的总成本最小

102 Better Products (No Product Splitting)

103 米德尔城学区问题再研究 区域5被分割的问题 学生在学校间的分布不均衡的问题
新问题：已知如表6.12所示的数据，当每一个区域都完全指派给一所学校(没有区域分割)且每一所学校都被指派了三个区域之后，所有学生到达学校的总路程最短

104 Middletown School District (No Tract Splitting)

105 本章小结 运输问题、指派问题；网络配送问题；线性规划问题 运输问题 指派问题

106 The end of chapter 6