Chapter06运输问题简化版2010

1、Chapter06运输问题简化版2010The 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)(运输问题的变形：求佳产品公司问题)Table of Contents (主要内容)Variants of Transportation Problems: Nifty (S

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

3、用：米德尔学区问题)Applications of Transportation Problems: Energetic (Section 6.4)(运输问题的应用：源丰公司问题)A Case Study: Texago Corp. Site Selection Problem (Section 6.5)(运输问题的应用：特赛格公司的选址问题)Table of Contents (主要内容)P&T Company Distribution Problem罐头厂1-贝林翰罐头厂2-尤基尼罐头厂3-艾尔贝仓库1-萨克拉门托仓库2-盐湖城仓库3-赖皮特城仓库4-奥尔巴古P&T Company Dis

4、tribution Problem贝林翰先满足萨克拉门托，剩余的运送到盐湖城艾尔贝先满足奥尔巴古，剩余的运送到赖皮特尤基尼满足剩余需求Shipping DataShipping Cost per TruckloadP&T Company Distribution Problem当前的配送结果是什么？总配送本钱是多少？Current Shipping PlanTotal shipping cost = 75($464) + 5($352) + 65($416) + 55($690) + 15($388) + 85($685) = $165,595P&T Company Distribution

5、Problem试建立该网络配送问题的数学模型？运输问题运输问题关心的是以最低的总配送本钱把出发地的任何产品运送到每一个目的地Terminology for a Transportation ProblemCharacteristics of Transportation ProblemsThe Requirements Assumption (需求假设)Each source has a fixed supply of units, where this entire supply must be distributed to the destinations. (每一个出发地都有一个固定的供

6、给量，所有的供给量都必须配送到目的地)Each destination has a fixed demand for units, where this entire demand must be received from the sources. (每一个目的地都有一个固定的需求量，所有的需求量都必须由出发地满足)Characteristics of Transportation ProblemsThe Feasible Solutions Property (可行解特性)A transportation problem will have feasible solutions if an

7、d only if the sum of its supplies equals the sum of its demands. (当且仅当供给量的总和等于需求量的总和时，运输问题才有可行解)Characteristics of Transportation ProblemsThe Cost Assumption (本钱假设)The cost of distributing units from any particular source to any particular destination is directly proportional to the number of units

8、distributed. (从任何一个出发地到任何一个目的地的货物配送本钱和所配送的数量成线性比例关系)This cost is just the unit cost of distribution times the number of units distributed. (这个本钱就等于配送的单位本钱乘以所配送的数量)The Transportation ModelAny problem (whether involving transportation or not) fits the model for a transportation problem if (任何满足下述两个条件的

9、问题都可以建模成运输问题)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所示的参数表形式，明确出发地、目的地、供给量、需求量和单位本钱)The Transportation Modelsatisfies both the requirements assumption and the cost assumption.

10、(同时满足需求假设和本钱假设)The objective is to minimize the total cost of distributing the units. (目的就是要使配送总本钱最小)The P&T Co. Transportation Problem运输问题模型参数表(供给量、需求量和单位本钱)Spreadsheet FormulationNetwork Representation运输问题的网络表述忽略出发地和目的地在地理上的布局左边一列为出发地(S)，旁边的数字代表供给量右边一列为目的地(D)，旁边的数字代表需求量箭头表示可能的运输途径，其上面的数字代表单位运输本钱Th

11、e Transportation Problem is an LPLet 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+ $690 x23 + $791x24 + $995x31 + $682x32 + $388x33 + $685x34The

12、 Transportation Problem is an LPsubject to (约束)Cannery 1:x11 + x12 + x13 + 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 =

13、1, 2, 3; j = 1, 2, 3, 4)Integer Solutions PropertyAs 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 constr

14、aints to the model that restrict these variables to only have integer values.整数解性质只要它的供给量和需求量都是整数，任何有可行解的运输问题必然有所有变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件求解(最优化)算法单纯形法网络单纯形法运输单纯形法算法的适应范围越小，求解效率越高Distribution System at Proctor and GambleProctor and Gamble needed to consolidate and re-design their North Amer

15、ican distribution system in the early 1990s. (宝洁公司需要稳固并再设计其九十年代早期在北美建立起来的配送系统)50 product categories (50个产品种类)60 plants (60家工厂)15 distribution centers (15个配送中心)1000 customer zones (1000个客户区)获奖作品Distribution System at Proctor and GambleSolved many transportation problems (one for each product category

16、). (解决大量运输问题，每个产品种类都存在一个运输问题)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 1996. Saved $200 million per year

17、. (1996年施行，北美工厂数减少20%，每年给公司节约2亿美金)Modeling Variants of Transportation ProblemThe 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. (一个目的地同时存在最小需求和最大需求)

18、Certain source-destination combinations cannot be 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 thr

19、ee plants that currently have excess capacity. (求佳产品公司决定使用三个有消费余力的工厂进展四种新产品的消费制造)Better Products (Assigning Plants to Products)生产能力产品1234工厂1412728247524029-237533730272145需求的产量20303040表示不存在数据的单元格Transportation Problem FormulationBetter Products (Assigning Plants to Products)Which plants should produ

20、ce which products?哪个工厂应该消费哪种产品？Spreadsheet FormulationThe 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

21、not all of their requested purchases. (订单主要来自四个客户，公司可以满足他们的最低购置要求，但是无法满足他们的所有购置要求)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. (主要是由于运输本钱的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供给哪个客户)Nifty Co.

22、 (Choosing Customers)Data for the Nifty CompanyNifty 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?Spreadsheet FormulationMetro Water (Distributing Natural Resources

23、)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. (米德罗水管站是一个主管着广阔地域的水资源分配机构，由于这个地域非常枯燥，所以这个机构需要从外地引水)Metro Water (Distributing Natural Resources)Sources of imported water: Colo

24、mbo, Sacron, and Calorie rivers. (水源主要有：科伦坡河、塞克隆河和卡路里河)Main customers: Cities of Berdoo, Los Devils, San Go, and Hollyglass. (主要的客户有：布都城、劳斯戴维斯城、圣哥城和豪利格拉斯城)Metro Water (Distributing Natural Resources)Metro Water (Distributing Natural Resources)应该从每条河里获取多少水资源？应该从每条河里向各个城市输送多少水资源？How much water should

25、Metro take from each river, and how much should they send from each river to each city?Spreadsheet FormulationNorthern Airplane (Production Scheduling)Northern Airplane Company produces commercial airplanes. The last stage in production is to produce the jet engines and install them. (北方飞机制造公司为全世界的航

26、空公司消费各种商务飞机。制造过程的最后一步是消费喷气发动机并把它们安装到已经完成的飞机框架上去)Northern Airplane (Production 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 Airpl

27、ane (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?Spreadsheet FormulationOptimal Production at Northern AirplaneMiddletown School DistrictMiddletown School Distr

28、ict 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个区域)Middletow

29、n School DistrictEach 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. (学区管理者认为划分学区界限的适当目的是使学生到学校的平均路

30、程最短)Data for the Middletown School DistrictHow many students from each tract should be assigned to each school?各个区域应该有多少学生被分配到各个学校？Middletown School DistrictSpreadsheet FormulationEnergetic (Meeting Energy Needs)The Energetic Company needs to make plans for the energy systems for a new building. (源丰

31、公司需要为新的建筑物建立起能源系统)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个单位)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个单位)Cost Data for EnergeticEnergetic (Meeting Energy Needs)How should Energeti