Chapter06运输问题简化版2010.ppt

1、Chapter 6. Transportation and Assignment Problems,第六章. 运输问题和指派问题,The P j = 1, 2, 3, 4) Minimize Cost = $464x11 + $513x12 + $654x13 + $867x14 + $352x21 + $416x22+ $690 x23 + $791x24 + $995x31 + $682x32 + $388x33 + $685x34,The Transportation Problem is an LP,subject to (约束)Cannery 1:x11 + x12 + x13 +

2、x14 = 75Cannery 2:x21 + x22 + x23 + x24 = 125Cannery 3:x31 + x32 + x33 + x34 = 100Warehouse 1:x11 + x21 + x31 = 80Warehouse 2:x12 + x22 + x32 = 65Warehouse 3:x13 + x23 + x33 = 70Warehouse 4:x14 + x24 + x34 = 85and xij 0 (i = 1, 2, 3; j = 1, 2, 3, 4),Integer Solutions Property,As long as all its supp

3、lies 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 val

4、ues.,整数解性质,只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件,求解(最优化)算法,单纯形法 网络单纯形法 运输单纯形法 算法的适应范围越小，求解效率越高,Distribution System at Proctor and Gamble,Proctor and Gamble needed to consolidate and re-design their North American distribution system in the early 1990s. (宝洁公司需要巩固并再设计其九十年代早

5、期在北美建立起来的配送系统) 50 product categories (50个产品种类) 60 plants (60家工厂) 15 distribution centers (15个配送中心) 1000 customer zones (1000个客户区),获奖作品,Distribution System at Proctor and Gamble,Solved many transportation problems (one for each product category). (解决大量运输问题，每个产品种类都存在一个运输问题) Goal: find best distributio

6、n plan, which plants to keep open, etc. (目标：寻找最优的配送方案，哪些工厂保持开放) Closed many plants and distribution centers, and optimized their product sourcing and distribution location. (关闭许多工厂和配送中心，优化产品来源和配送点) Implemented in 1996. Saved $200 million per year. (1996年实施，北美工厂数减少20%，每年给公司节约2亿美金),Modeling Variants o

7、f 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

8、 used for distributing units. (在配送中不能使用特定的出发地-目的地组合) The objective is to maximize the total profit. (目标是最大化总利润),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.

9、 (求佳产品公司决定使用三个有生产余力的工厂进行四种新产品的生产制造),Better Products (Assigning Plants to Products),表示不存在数据的单元格,Transportation Problem Formulation,Better Products (Assigning Plants to Products),Which plants should produce which products? 哪个工厂应该生产哪种产品？,Spreadsheet Formulation,The Nifty Company specializes in the prod

10、uction 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. (订单主要来自四个客户，公司能够满足他们的最低购买要求，但是无法满足他们的所有购买要求),Nifty Co. (

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

12、个客户多少产品？应该从每个工厂运送多少产品至每个客户？,How many units should Nifty sell to each customer and how many units should they ship from each plant to each customer?,Spreadsheet Formulation,Metro Water (Distributing Natural Resources),Metro Water District is an agency that administers water distribution in a large ge

13、ographic region. The region is arid, so water must be brought in from outside the region. (米德罗水管站是一个主管着广阔地域的水资源分配机构，由于这个地域十分干燥，所以这个机构需要从外地引水),Metro Water (Distributing Natural Resources),Sources of imported water: Colombo, Sacron, and Calorie rivers. (水源主要有：科伦坡河、塞克隆河和卡路里河) Main customers: Cities of

14、Berdoo, Los Devils, San Go, and Hollyglass. (主要的客户有：布都城、劳斯戴维斯城、圣哥城和豪利格拉斯城),Metro Water (Distributing Natural Resources),Metro Water (Distributing Natural Resources),应该从每条河里获取多少水资源？应该从每条河里向各个城市输送多少水资源？,How much water should Metro take from each river, and how much should they send from each river to

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

16、tion Scheduling),The company must meet the delivery deadline indicated in column 2. (公司必须满足交货期的限制) Production and storage costs vary from month to month. (生产和存储成本每个月都有可能发生变化),Northern Airplane (Production Scheduling),Northern Airplane (Production Scheduling),每个月各生产多少航空发动机可以使生产和存储总成本最低？,How many engi

17、nes should be produced in each of the four months so that the total of the production and storage costs will be minimized?,Spreadsheet Formulation,Optimal Production at Northern Airplane,Middletown School District,Middletown School District is opening a third high school and thus needs to redraw the

18、 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个区域),Middletown School District,Each school has a minimum and maximum numbe

19、r 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. (学区管理者认为划分学区界限的适当目标是使学生到学校的平均路程最短),Data for the Middletown School District,How many stude

20、nts from each tract should be assigned to each school? 各个区域应该有多少学生被分配到各个学校？,Middletown School District,Spreadsheet Formulation,Energetic (Meeting Energy Needs),The Energetic Company needs to make plans for the energy systems for a new building. (源丰公司需要为新的建筑物建立起能源系统),Energetic (Meeting Energy Needs),

21、The energy needs fall into three categories: (能源需求主要来源于三个方面) electricity (20 units) (电，20个单位) heating water (10 units) (热水，10个单位) heating space (30 units) (建筑物内取暖，30个单位),Energetic (Meeting Energy Needs),The three possible sources of energy are (满足这些需求的三个可能的能源来源是) Electricity (电) natural gas (天然气) so

22、lar heating unit (limited to 30 units because of roof size) (安装在屋顶上的太阳能加热装置，由于屋顶大小的限制，太阳能的能源量只有30个单位),Cost Data for Energetic,Energetic (Meeting Energy Needs),How should Energetic meet the energy needs for the new building? 源丰公司应该如何来满足新建筑的能源需求？,Spreadsheet Formulation,使用符号的总结,当需求大于供应时，供应前用“=”，需求前用“=”； 当供应大于需求时，需求前用“=”，供应前用“=”； 当告知范围时，则按要求直接给定相应的符号即可,案例研究：特塞格公司的选址问题,特塞格公司(Texago)是一家设在美国本土的大型一体化石油公司，包括多个油田、炼油厂和配送中心 为了满足持续增长的市场需求，公司决定新建一个炼油厂，有3个备选地点 自产原油不够时可从中东地区购买,案例研究：特塞格公司的选址问题,需要确定新炼油厂的位置，以及从每一个原油供应点到每一个炼油厂