Chapter06運(yùn)輸問題簡化版2010

1、Chapter06運(yùn)輸問題簡化版2010The P&T Company Distribution Problem (Section 6.1)(P&T公司的配送問題)Characteristics of Transportation Problems (Section 6.2)(運(yùn)輸問題的特征)Variants of Transportation Problems: Better Products (Section 6.3)(運(yùn)輸問題的變形：求佳產(chǎn)品公司問題)Table of Contents (主要內(nèi)容)Variants of Transportation Problems: Nifty (S

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

3、用：米德爾學(xué)區(qū)問題)Applications of Transportation Problems: Energetic (Section 6.4)(運(yùn)輸問題的應(yīng)用：源豐公司問題)A Case Study: Texago Corp. Site Selection Problem (Section 6.5)(運(yùn)輸問題的應(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貝林翰先滿足薩克拉門托，剩余的運(yùn)送到鹽湖城艾爾貝先滿足奧爾巴古，剩余的運(yùn)送到賴皮特尤基尼滿足剩余需求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é)模型？運(yùn)輸問題運(yùn)輸問題關(guān)心的是以最低的總配送本錢把出發(fā)地的任何產(chǎn)品運(yùn)送到每一個(gè)目的地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. (每一個(gè)出發(fā)地都有一個(gè)固定的供

6、給量，所有的供給量都必須配送到目的地)Each destination has a fixed demand for units, where this entire demand must be received from the sources. (每一個(gè)目的地都有一個(gè)固定的需求量，所有的需求量都必須由出發(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)供給量的總和等于需求量的總和時(shí)，運(yùn)輸問題才有可行解)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. (從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送本錢和所配送的數(shù)量成線性比例關(guān)系)This cost is just the unit cost of distribution times the number of units distributed. (這個(gè)本錢就等于配送的單位本錢乘以所配送的數(shù)量)The Transportation ModelAny problem (whether involving transportation or not) fits the model for a transportation problem if (任何滿足下述兩個(gè)條件的

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

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

16、). (解決大量運(yùn)輸問題，每個(gè)產(chǎn)品種類都存在一個(gè)運(yù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)品來源和配送點(diǎ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. (一個(gè)目的地同時(shí)存在最小需求和最大需求)

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)品公司決定使用三個(gè)有消費(fèi)余力的工廠進(jìn)展四種新產(chǎn)品的消費(fèi)制造)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?哪個(gè)工廠應(yīng)該消費(fèi)哪種產(chǎn)品？Spreadsheet FormulationThe Nifty Company specializes in the production of a single product, which it produces in three plants. (耐芙迪公司在3個(gè)工廠中專門消費(fèi)一種產(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. (訂單主要來自四個(gè)客戶，公司可以滿足他們的最低購置要求，但是無法滿足他們的所有購置要求)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. (主要是由于運(yùn)輸本錢的差異，銷售一個(gè)產(chǎn)品得到的凈利潤也不同，很大程度上取決于哪個(gè)工廠供給哪個(gè)客戶)Nifty Co.

22、 (Choosing Customers)Data for the Nifty CompanyNifty Co. (Choosing Customers)耐芙迪公司應(yīng)該銷售給每個(gè)客戶多少產(chǎn)品？應(yīng)該從每個(gè)工廠運(yùn)送多少產(chǎn)品至每個(gè)客戶？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è)主管著廣闊地域的水資源分配機(jī)構(gòu)，由于這個(gè)地域非?？菰铮赃@個(gè)機(jī)構(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)該從每條河里向各個(gè)城市輸送多少水資源？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. (北方飛機(jī)制造公司為全世界的航

26、空公司消費(fèi)各種商務(wù)飛機(jī)。制造過程的最后一步是消費(fèi)噴氣發(fā)動(dòng)機(jī)并把它們安裝到已經(jīng)完成的飛機(jī)框架上去)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èi)和存儲本錢每個(gè)月都有可能發(fā)生變化)Northern Airplane (Production Scheduling)Northern Airpl

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

29、n School DistrictEach school has a minimum and maximum number of students that should be assigned. (每一所中學(xué)都有一個(gè)最小和最大的學(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?各個(gè)區(qū)域應(yīng)該有多少學(xué)生被分配到各個(gè)學(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: (能源需求主要來源于三個(gè)方面)electricity (20 units) (電，20個(gè)單位)heating water (10 units) (熱水，10個(gè)單位)heating space (30 units) (建筑物內(nèi)取暖，30個(gè)單位)Energetic (Meeting Energy Needs)The three possible sources of energy are (滿足這些需求的三個(gè)可能的能源來源是)Electricity (電)natural gas (天然氣)solar heating unit (limited to 30 units because of roof size) (安裝在屋頂上的太陽能加熱裝置，由于屋頂大小的限制，太陽能的能源量只有30個(gè)單位)Cost Data for EnergeticEnergetic (Meeting Energy Needs)How should Energeti