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)(運輸問題的變形：求佳產(chǎn)品公司問題)Table of Contents (主要內(nèi)容)Variants of Transportation Problems: Nifty (S

2、ection 6.3)(運輸問題的變形：耐芙迪公司問題)Applications of Transportation Problems: Metro Water (Section 6.4)(運輸問題的應(yīng)用：米德羅水管站問題)Applications of Transportation Problems: Northern Airplane (Section 6.4)(運輸問題的應(yīng)用：北方飛機制造公司問題)Table of Contents (主要內(nèi)容)Applications of Transportation Problems: Middletown (Section 6.4)(運輸問題的應(yīng)

3、用：米德爾學(xué)區(qū)問題)Applications of Transportation Problems: Energetic (Section 6.4)(運輸問題的應(yīng)用：源豐公司問題)A Case Study: Texago Corp. Site Selection Problem (Section 6.5)(運輸問題的應(yīng)用：特賽格公司的選址問題)Table of Contents (主要內(nèi)容)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當(dāng)前的配送結(jié)果是什么？總配送本錢是多少？Current Shipping PlanTotal shipping cost = 75($464) + 5($352) + 65($416) + 55($690) + 15($388) + 85($685) = $165,595P&T Company Distribution

5、Problem試建立該網(wǎng)絡(luò)配送問題的數(shù)學(xué)模型？運輸問題運輸問題關(guān)心的是以最低的總配送本錢把出發(fā)地的任何產(chǎn)品運送到每一個目的地Terminology for a Transportation ProblemCharacteristics of Transportation ProblemsThe Requirements Assumption (需求假設(shè))Each source has a fixed supply of units, where this entire supply must be distributed to the destinations. (每一個出發(fā)地都有一個固定的供

6、給量，所有的供給量都必須配送到目的地)Each destination has a fixed demand for units, where this entire demand must be received from the sources. (每一個目的地都有一個固定的需求量，所有的需求量都必須由出發(fā)地滿足)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. (當(dāng)且僅當(dāng)供給量的總和等于需求量的總和時，運輸問題才有可行解)Characteristics of Transportation ProblemsThe Cost Assumption (本錢假設(shè))The cost of distributing units from any particular source to any particular destination is directly proportional to the number of units

8、distributed. (從任何一個出發(fā)地到任何一個目的地的貨物配送本錢和所配送的數(shù)量成線性比例關(guān)系)This cost is just the unit cost of distribution times the number of units distributed. (這個本錢就等于配送的單位本錢乘以所配送的數(shù)量)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所示的參數(shù)表形式，明確出發(fā)地、目的地、供給量、需求量和單位本錢)The Transportation Modelsatisfies both the requirements assumption and the cost assumption.

10、(同時滿足需求假設(shè)和本錢假設(shè))The objective is to minimize the total cost of distributing the units. (目的就是要使配送總本錢最小)The P&T Co. Transportation Problem運輸問題模型參數(shù)表(供給量、需求量和單位本錢)Spreadsheet FormulationNetwork Representation運輸問題的網(wǎng)絡(luò)表述忽略出發(fā)地和目的地在地理上的布局左邊一列為出發(fā)地(S)，旁邊的數(shù)字代表供給量右邊一列為目的地(D)，旁邊的數(shù)字代表需求量箭頭表示可能的運輸途徑，其上面的數(shù)字代表單位運輸本錢Th

11、e Transportation Problem is an LPLet xij = the number of truckloads to ship from cannery i to warehouse j (假設(shè)xij是從第i個罐頭加工廠運送到第j個倉庫的車數(shù)) (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.整數(shù)解性質(zhì)只要它的供給量和需求量都是整數(shù)，任何有可行解的運輸問題必然有所有變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件求解(最優(yōu)化)算法單純形法網(wǎng)絡(luò)單純形法運輸單純形法算法的適應(yīng)范圍越小，求解效率越高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. (寶潔公司需要穩(wěn)固并再設(shè)計其九十年代早期在北美建立起來的配送系統(tǒng))50 product categories (50個產(chǎn)品種類)60 plants (60家工廠)15 distribution centers (15個配送中心)1000 customer zones (1000個客戶區(qū))獲獎作品Distribution System at Proctor and GambleSolved many transportation problems (one for each product category

16、). (解決大量運輸問題，每個產(chǎn)品種類都存在一個運輸問題)Goal: find best distribution plan, which plants to keep open, etc. (目的：尋找最優(yōu)的配送方案，哪些工廠保持開放)Closed many plants and distribution centers, and optimized their product sourcing and distribution location. (關(guān)閉許多工廠和配送中心，優(yōu)化產(chǎn)品來源和配送點)Implemented in 1996. Saved $200 million per year

17、. (1996年施行，北美工廠數(shù)減少20%，每年給公司節(jié)約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. (在配送中不能使用特定的出發(fā)地-目的地組合)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. (求佳產(chǎn)品公司決定使用三個有消費余力的工廠進展四種新產(chǎn)品的消費制造)Better Products (Assigning Plants to Products)生產(chǎn)能力產(chǎn)品1234工廠1412728247524029-237533730272145需求的產(chǎn)量20303040表示不存在數(shù)據(jù)的單元格Transportation Problem FormulationBetter Products (Assigning Plants to Products)Which plants should produ

20、ce which products?哪個工廠應(yīng)該消費哪種產(chǎn)品？Spreadsheet FormulationThe Nifty Company specializes in the production of a single product, which it produces in three plants. (耐芙迪公司在3個工廠中專門消費一種產(chǎn)品)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. (主要是由于運輸本錢的差異，銷售一個產(chǎn)品得到的凈利潤也不同，很大程度上取決于哪個工廠供給哪個客戶)Nifty Co.

22、 (Choosing Customers)Data for the Nifty CompanyNifty Co. (Choosing Customers)耐芙迪公司應(yīng)該銷售給每個客戶多少產(chǎn)品？應(yīng)該從每個工廠運送多少產(chǎn)品至每個客戶？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. (米德羅水管站是一個主管著廣闊地域的水資源分配機構(gòu)，由于這個地域非?？菰铮赃@個機構(gòu)需要從外地引水)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)應(yīng)該從每條河里獲取多少水資源？應(yīng)該從每條河里向各個城市輸送多少水資源？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、空公司消費各種商務(wù)飛機。制造過程的最后一步是消費噴氣發(fā)動機并把它們安裝到已經(jīng)完成的飛機框架上去)Northern Airplane (Production Scheduling)The company must meet the delivery deadline indicated in column 2. (公司必須滿足交貨期的限制)Production and storage costs vary from month to month. (消費和存儲本錢每個月都有可能發(fā)生變化)Northern Airplane (Production Scheduling)Northern Airpl

27、ane (Production Scheduling)每個月各消費多少航空發(fā)動機可以使消費和存儲總本錢最低？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. (米德爾城學(xué)區(qū)創(chuàng)辦了第三所中學(xué)，需要為每一所學(xué)校重新劃定這個城市內(nèi)的效勞區(qū)域)The city has been divided into 9 tracts with approximately equal populations. (這個城市被分成了擁有大致一樣數(shù)量人口的9個區(qū)域)Middletow

29、n School DistrictEach school has a minimum and maximum number of students that should be assigned. (每一所中學(xué)都有一個最小和最大的學(xué)生數(shù)目的要求)The school district management has decided that the appropriate objective is to minimize the average distance that students must travel to school. (學(xué)區(qū)管理者認(rèn)為劃分學(xué)區(qū)界限的適當(dāng)目的是使學(xué)生到學(xué)校的平均路

30、程最短)Data for the Middletown School DistrictHow many students from each tract should be assigned to each school?各個區(qū)域應(yīng)該有多少學(xué)生被分配到各個學(xué)校？Middletown School DistrictSpreadsheet FormulationEnergetic (Meeting Energy Needs)The Energetic Company needs to make plans for the energy systems for a new building. (源豐

31、公司需要為新的建筑物建立起能源系統(tǒng))Energetic (Meeting Energy Needs)The energy needs fall into three categories: (能源需求主要來源于三個方面)electricity (20 units) (電，20個單位)heating water (10 units) (熱水，10個單位)heating space (30 units) (建筑物內(nèi)取暖，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