Chapter運輸問題和指派問題

1、Chapter 6. Chapter 6. Transportation and Transportation and Assignment ProblemsAssignment Problems 第六章第六章. . 運輸問運輸問 題和指派問題題和指派問題 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 2 The P j = 1, 2, 3, 4) Minimize Cost = $464x11 + $513x12 + $654x13 + $867x14 + $352x21 + $416x22 + $690 x23 + $791x24 + $995x31 + $

2、682x32 + $388x33 + $685x34 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 27 The Transportation Problem is an LPThe 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 =

3、 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) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 28 Integer Solutions PropertyInteger Solutions Property As long as all its supplies and demands have integer values, a

4、ny 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. Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌

5、學(xué)運籌學(xué) 29 整數(shù)解性質(zhì)整數(shù)解性質(zhì) 只要它的供應(yīng)量和需求量都是只要它的供應(yīng)量和需求量都是 整數(shù)，任何有可行解的運輸問整數(shù)，任何有可行解的運輸問 題必然有所有變量都是整數(shù)的題必然有所有變量都是整數(shù)的 最優(yōu)解。因此，沒有必要加上最優(yōu)解。因此，沒有必要加上 所有變量都是整數(shù)的約束條件所有變量都是整數(shù)的約束條件 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 30 求解求解( (最優(yōu)化最優(yōu)化) )算法算法 單純形法單純形法 網(wǎng)絡(luò)單純形法網(wǎng)絡(luò)單純形法 運輸單純形法運輸單純形法 算法的適應(yīng)范圍越小，算法的適應(yīng)范圍越小， 求解效率越高求解效率越高 Copyright 2007

6、 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 31 Distribution System at Proctor and GambleDistribution System at Proctor and Gamble Proctor and Gamble needed to consolidate and re-design their North American distribution system in the early 1990s. (Proctor & Gamble(Proctor & Gamble公司需公司需 要鞏固并再設(shè)計其九十年代早期在北美建要鞏固并再設(shè)計其九十年代早期

7、在北美建 立起來的配送系統(tǒng)立起來的配送系統(tǒng)) ) l50 product categories (50(50個產(chǎn)品種類個產(chǎn)品種類) ) l60 plants (60(60家工廠家工廠) ) l15 distribution centers (15(15個配送中心個配送中心) ) l1000 customer zones (1000(1000個客戶區(qū)個客戶區(qū)) ) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 32 Distribution System at Proctor and GambleDistribution System at Proctor and

8、 Gamble Solved many transportation problems (one for each product category). (解決大量運輸問題，解決大量運輸問題， 每個產(chǎn)品種類都存在一個運輸問題每個產(chǎn)品種類都存在一個運輸問題) Goal: find best distribution plan, which plants to keep open, etc. (目標(biāo)：尋找最優(yōu)的配送方案，目標(biāo)：尋找最優(yōu)的配送方案， 哪些工廠保持開放哪些工廠保持開放) Closed many plants and distribution centers, and optimized

9、 their product sourcing and distribution location. (關(guān)閉許多工廠和配送中心，關(guān)閉許多工廠和配送中心， 優(yōu)化產(chǎn)品來源和配送點優(yōu)化產(chǎn)品來源和配送點) Implemented in 1996. Saved $200 million per year. (1996年實施，北美工廠數(shù)減少年實施，北美工廠數(shù)減少20%，每年，每年 給公司節(jié)約給公司節(jié)約2億美金億美金) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 33 Modeling Variants of Transportation ProblemModeling V

10、ariants of Transportation Problem The sum of the supplies exceeds the sum of the demands. (供應(yīng)總量超過需求總量供應(yīng)總量超過需求總量) The sum of the supplies is less than the sum of the demands. (供應(yīng)總量小于需求總量供應(yīng)總量小于需求總量) A destination has both a minimum demand and a maximum demand. (一個目的地同時存在一個目的地同時存在 最小需求和最大需求最小需求和最大需求) C

11、ertain source-destination combinations cannot be used for distributing units. (在配送中在配送中 不能使用特定的出發(fā)地不能使用特定的出發(fā)地-目的地組合目的地組合) The objective is to maximize the total profit. (目目 標(biāo)是最大化總利潤標(biāo)是最大化總利潤) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 34 Better Products (Assigning Plants to Products)Better Products (Assig

12、ning 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. ( (求佳求佳 產(chǎn)品公司決定使用三個有生產(chǎn)余力的工產(chǎn)品公司決定使用三個有生產(chǎn)余力的工 廠進行四種新產(chǎn)品的生產(chǎn)制造廠進行四種新產(chǎn)品的生產(chǎn)制造) ) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 35 Better Products (A

13、ssigning Plants to Products)Better Products (Assigning Plants to Products) 生產(chǎn)能力生產(chǎn)能力 產(chǎn)品產(chǎn)品1234 工廠工廠24029-2375 33730272145 需求的產(chǎn)量需求的產(chǎn)量20303040 表示不存在數(shù)據(jù)的單元格 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 36 Transportation Problem FormulationTransportation Problem Formulation Copyright 2007 深圳大學(xué)管理學(xué)院深圳

14、大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 37 Better Products (Assigning Plants to Products)Better Products (Assigning Plants to Products) Which plants should produce which products? 哪個工廠應(yīng)該生產(chǎn)哪種哪個工廠應(yīng)該生產(chǎn)哪種 產(chǎn)品？產(chǎn)品？ Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 38 Spreadsheet FormulationSpreadsheet Formulation Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理

15、學(xué)院 運籌學(xué)運籌學(xué) 39 The Nifty Company specializes in the production of a single product, which it produces in three plants. (耐芙迪公司在耐芙迪公司在3 個工廠中專門生產(chǎn)一種產(chǎn)品個工廠中專門生產(chǎn)一種產(chǎn)品) Four customers would like to make major purchases. There will be enough to meet their minimum purchase requirements, but not all of their requ

16、ested purchases. (訂單主要來自四個訂單主要來自四個 客戶，公司能夠滿足他們的最低購買要求，客戶，公司能夠滿足他們的最低購買要求， 但是無法滿足他們的所有購買要求但是無法滿足他們的所有購買要求) Nifty Co. (Choosing Customers)Nifty Co. (Choosing Customers) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 40 Due largely to variations in shipping cost, the net profit per unit sold varies depending o

17、n which plant supplies which customer. (主要是由于運輸成本主要是由于運輸成本 的差異，銷售一個產(chǎn)品得到的凈利的差異，銷售一個產(chǎn)品得到的凈利 潤也不同，很大程度上取決于哪個潤也不同，很大程度上取決于哪個 工廠供應(yīng)哪個客戶工廠供應(yīng)哪個客戶) Nifty Co. (Choosing Customers)Nifty Co. (Choosing Customers) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 41 Data for the Nifty CompanyData for the Nifty Company Copyr

18、ight 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 42 Nifty Co. (Choosing Customers)Nifty Co. (Choosing Customers) 耐芙迪公司應(yīng)該銷售給耐芙迪公司應(yīng)該銷售給 每個客戶多少產(chǎn)品？應(yīng)每個客戶多少產(chǎn)品？應(yīng) 該從每個工廠運送多少該從每個工廠運送多少 產(chǎn)品至每個客戶？產(chǎn)品至每個客戶？ How many units should Nifty sell to each customer and how many units should they ship from each plant to each customer? Co

19、pyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 43 Spreadsheet FormulationSpreadsheet Formulation Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 44 Metro Water (Distributing Natural Resources)Metro Water (Distributing Natural Resources) Metro Water District is an agency that administers water distribution in a large g

20、eographic region. The region is arid, so water must be brought in from outside the region. (米德羅水管站米德羅水管站 是一個主管著廣闊地域的水資源分是一個主管著廣闊地域的水資源分 配機構(gòu)，由于這個地域十分干燥，配機構(gòu)，由于這個地域十分干燥， 所以這個機構(gòu)需要從外地引水所以這個機構(gòu)需要從外地引水) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 45 Metro Water (Distributing Natural Resources)Metro Water (Distri

21、buting Natural Resources) lSources of imported water: Colombo, Sacron, and Calorie rivers. (水源主要有：科倫坡河、水源主要有：科倫坡河、 塞克隆河和卡路里河塞克隆河和卡路里河) lMain customers: Cities of Berdoo, Los Devils, San Go, and Hollyglass. (主要的客戶有：主要的客戶有： 布都城、勞斯戴維斯城、圣哥城布都城、勞斯戴維斯城、圣哥城 和豪利格拉斯城和豪利格拉斯城) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運

22、籌學(xué)運籌學(xué) 46 Metro Water (Distributing Natural Resources)Metro Water (Distributing Natural Resources) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 47 Metro Water (Distributing Natural Resources)Metro Water (Distributing Natural Resources) 應(yīng)該從每條河里獲取多應(yīng)該從每條河里獲取多 少水資源？應(yīng)該從每條少水資源？應(yīng)該從每條 河里向各個城市輸送多河里向各個城市輸送多 少水資源？少水資

23、源？ How much water should Metro take from each river, and how much should they send from each river to each city? Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 48 Spreadsheet FormulationSpreadsheet Formulation Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 49 Northern Airplane (Production Scheduling)Northern Airpla

24、ne (Production Scheduling) Northern Airplane Company produces commercial airplanes. The last stage in production is to produce the jet engines and install them. (北方飛機制造公司為北方飛機制造公司為 全世界的航空公司生產(chǎn)各種商務(wù)飛全世界的航空公司生產(chǎn)各種商務(wù)飛 機。制造過程的最后一步是生產(chǎn)噴機。制造過程的最后一步是生產(chǎn)噴 氣發(fā)動機并把它們安裝到已經(jīng)完成氣發(fā)動機并把它們安裝到已經(jīng)完成 的飛機框架上去的飛機框架上去) Copyright

25、2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 50 Northern Airplane (Production Scheduling)Northern Airplane (Production Scheduling) lThe company must meet the delivery deadline indicated in column 2. (公司必須滿足交貨期公司必須滿足交貨期 的限制的限制) lProduction and storage costs vary from month to month. (生生 產(chǎn)和存儲成本每個月都有可能發(fā)產(chǎn)和存儲成本每個月都有可能發(fā)

26、生變化生變化) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 51 Northern Airplane (Production Scheduling)Northern Airplane (Production Scheduling) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 52 Northern Airplane (Production Scheduling)Northern Airplane (Production Scheduling) 每個月各生產(chǎn)多少航空每個月各生產(chǎn)多少航空 發(fā)動機可以使生產(chǎn)和存發(fā)動機可以使生產(chǎn)和存

27、儲總成本最低？儲總成本最低？ 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? Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 53 Spreadsheet FormulationSpreadsheet Formulation Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 54 Optimal Production

28、 at Northern AirplaneOptimal Production at Northern Airplane Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 55 Middletown School DistrictMiddletown 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

29、 to the respective schools. (米德爾城學(xué)區(qū)開辦了米德爾城學(xué)區(qū)開辦了 第三所中學(xué)，需要為每一所學(xué)校重新劃定這第三所中學(xué)，需要為每一所學(xué)校重新劃定這 個城市內(nèi)的服務(wù)區(qū)域個城市內(nèi)的服務(wù)區(qū)域) The city has been divided into 9 tracts with approximately equal populations. (這個城市被分成了擁有大致相同數(shù)量人口這個城市被分成了擁有大致相同數(shù)量人口 的的9個區(qū)域個區(qū)域) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 56 Middletown School Distri

30、ctMiddletown School District Each school has a minimum and maximum number of students that should be assigned. (每一所中學(xué)都有每一所中學(xué)都有 一個最小和最大的學(xué)生數(shù)目的要求一個最小和最大的學(xué)生數(shù)目的要求) The school district management has decided that the appropriate objective is to minimize the average distance that students must travel to sc

31、hool. (學(xué)區(qū)管理者認(rèn)為劃分學(xué)區(qū)界限學(xué)區(qū)管理者認(rèn)為劃分學(xué)區(qū)界限 的適當(dāng)目標(biāo)是使學(xué)生到學(xué)校的平均路程的適當(dāng)目標(biāo)是使學(xué)生到學(xué)校的平均路程 最短最短) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 57 Data for the Middletown School DistrictData for the Middletown School District Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 58 How many students from each tract should be assigned to each s

32、chool? 各個區(qū)域應(yīng)該有多少學(xué)生被各個區(qū)域應(yīng)該有多少學(xué)生被 分配到各個學(xué)校？分配到各個學(xué)校？ Middletown School DistrictMiddletown School District Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 59 Spreadsheet FormulationSpreadsheet Formulation Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 60 Energetic (Meeting Energy Needs)Energetic (Meeting Energy Needs) Th

33、e Energetic Company needs to make plans for the energy systems for a new building. (源豐公司需源豐公司需 要為新的建筑物建立起能源要為新的建筑物建立起能源 系統(tǒng)系統(tǒng)) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 61 Energetic (Meeting Energy Needs)Energetic (Meeting Energy Needs) The energy needs fall into three categories: (能源需求主能源需求主 要來源于三個方面要來

34、源于三個方面) lelectricity (20 units) (電，電，20個個 單位單位) lheating water (10 units) (熱水，熱水， 10個單位個單位) lheating space (30 units) (建筑建筑 物內(nèi)取暖，物內(nèi)取暖，30個單位個單位) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 62 Energetic (Meeting Energy Needs)Energetic (Meeting Energy Needs) The three possible sources of energy are (滿足這些需求的

35、三滿足這些需求的三 個可能的能源來源是個可能的能源來源是) lElectricity (電電) lnatural gas (天然氣天然氣) lsolar heating unit (limited to 30 units because of roof size) (安裝安裝 在屋頂上的太陽能加熱裝置，由于在屋頂上的太陽能加熱裝置，由于 屋頂大小的限制，太陽能的能源量屋頂大小的限制，太陽能的能源量 只有只有30個單位個單位) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 63 Cost Data for EnergeticCost Data for Energe

36、tic Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 64 Energetic (Meeting Energy Needs)Energetic (Meeting Energy Needs) How should Energetic meet the energy needs for the new building? 源豐公司應(yīng)該如何來滿足新源豐公司應(yīng)該如何來滿足新 建筑的能源需求？建筑的能源需求？ Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 65 Spreadsheet FormulationSpreadsheet Formu

37、lation Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 66 使用符號的總結(jié)使用符號的總結(jié) 當(dāng)需求大于供應(yīng)時，供應(yīng)前當(dāng)需求大于供應(yīng)時，供應(yīng)前 用用“=”“=”，需求前用，需求前用“=”“=”； 當(dāng)供應(yīng)大于需求時，需求前當(dāng)供應(yīng)大于需求時，需求前 用用“=”“=”，供應(yīng)前用，供應(yīng)前用“=”“=”； 當(dāng)告知范圍時，則按要求直當(dāng)告知范圍時，則按要求直 接給定相應(yīng)的符號即可接給定相應(yīng)的符號即可 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 67 案例研究：特塞格公司的選址問題案例研究：特塞格公司的選址問題 特塞格公司特塞格公司( (Te

38、xago)Texago)是一家設(shè)是一家設(shè) 在美國本土的大型一體化石在美國本土的大型一體化石 油公司，包括多個油田、煉油公司，包括多個油田、煉 油廠和配送中心油廠和配送中心 為了滿足持續(xù)增長的市場需為了滿足持續(xù)增長的市場需 求，公司決定新建一個煉油求，公司決定新建一個煉油 廠，有廠，有3 3個備選地點個備選地點 自產(chǎn)原油不夠時可從中東地自產(chǎn)原油不夠時可從中東地 區(qū)購買區(qū)購買 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 68 案例研究：特塞格公司的選址問題案例研究：特塞格公司的選址問題 需要確定新煉油廠的位置，以及從需要確定新煉油廠的位置，以及從 每一個原油供應(yīng)點

39、到每一個煉油廠每一個原油供應(yīng)點到每一個煉油廠 的原油供應(yīng)量，從每一個煉油廠到的原油供應(yīng)量，從每一個煉油廠到 每一個配送中心的成品油配送量，每一個配送中心的成品油配送量， 以使總運作成本最低以使總運作成本最低 成本包括：原油配送成本、成品油成本包括：原油配送成本、成品油 配送成本、煉油廠運營成本配送成本、煉油廠運營成本 可把問題分解成兩種可把問題分解成兩種( (原油配送和成原油配送和成 品油配送品油配送)6(=2)6(=2* *3) 3)個運輸問題個運輸問題 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 69 Location of Texagos Facilit

40、iesLocation of Texagos Facilities Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 70 Potential Sites for Texagos New RefineryPotential Sites for Texagos New Refinery Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 71 Production Data for TexagoProduction Data for Texago Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 72 Cost D

41、ata for Shipping to RefineriesCost Data for Shipping to Refineries Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 73 Cost Data for Shipping to Distribution CentersCost Data for Shipping to Distribution Centers Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 74 Estimated Operating Costs for RefineriesEstimated Operat

42、ing Costs for Refineries Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 75 Basic Spreadsheet for Shipping to RefineriesBasic Spreadsheet for Shipping to Refineries Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 76 Shipping to Refineries, Including Los AngelesShipping to Refineries, Including Los Angeles Copyright 2

43、007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 77 Shipping to Refineries, Including GalvestonShipping to Refineries, Including Galveston Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 78 Shipping to Refineries, Including St. LouisShipping to Refineries, Including St. Louis Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 79 Basic Sprea

44、dsheet for Shipping to D.C.sBasic Spreadsheet for Shipping to D.C.s Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 80 Shipping to D.C.s When Choose Los AngelesShipping to D.C.s When Choose Los Angeles Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 81 Shipping to D.C.s When Choose GalvestonShipping to D.C.s When Cho

45、ose Galveston Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 82 Shipping to D.C.s When Choose St. LouisShipping to D.C.s When Choose St. Louis Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 83 Annual Variable CostsAnnual Variable Costs 當(dāng)前最優(yōu)決策是選擇在當(dāng)前最優(yōu)決策是選擇在St. Louis(St. Louis(圣圣 路易斯路易斯) )建廠。但是還有很多其它建廠。但是還有很多其它 因素值得進

46、一步考慮！因素值得進一步考慮！ Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 84 Sellmore Company Assignment ProblemSellmore Company Assignment Problem The marketing manager of Sellmore Company will be holding the companys annual sales conference soon. (塞爾默塞爾默 公司的營銷經(jīng)理將要主持召開一公司的營銷經(jīng)理將要主持召開一 年一度的由營銷區(qū)域經(jīng)理以及銷年一度的由營銷區(qū)域經(jīng)理以及銷 售人員參

47、加的銷售協(xié)商會議售人員參加的銷售協(xié)商會議) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 85 Sellmore Company Assignment ProblemSellmore Company Assignment Problem He is hiring four temporary employees: (他雇用了四個臨時他雇用了四個臨時 員工員工) lAnn (安安) lIan (伊恩伊恩) lJoan (瓊瓊) lSean (肖恩肖恩) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 86 Sellmore Compa

48、ny Assignment ProblemSellmore Company Assignment Problem Each will handle one of the following four tasks: (每一個人負(fù)每一個人負(fù) 責(zé)完成下面的一項任務(wù)責(zé)完成下面的一項任務(wù)) lWord processing of written presentations (書面陳述的文字處理書面陳述的文字處理) lComputer graphics for both oral and written presentations (制作口制作口 頭和書面陳述的計算機圖形頭和書面陳述的計算機圖形) Cop

49、yright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 87 Sellmore Company Assignment ProblemSellmore Company Assignment Problem lPreparation of conference packets, including copying and organizing materials (會會 議材料的準(zhǔn)備，包括書面材料的議材料的準(zhǔn)備，包括書面材料的 抄寫和組織抄寫和組織) lHandling of advance and on- site registration for the conference

50、(處理與會者的提前處理與會者的提前 和當(dāng)場注冊報名和當(dāng)場注冊報名) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 88 Data for the Sellmore ProblemData for the Sellmore Problem Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 89 Sellmore Company Assignment ProblemSellmore Company Assignment Problem Which person should be assigned to which task? 哪個人應(yīng)該

51、負(fù)責(zé)哪項哪個人應(yīng)該負(fù)責(zé)哪項 工作？工作？ Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 90 Spreadsheet FormulationSpreadsheet Formulation 增加增加0-10-1變變 量表示任量表示任 務(wù)的分配務(wù)的分配 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 91 The Model for Assignment ProblemsThe Model for Assignment Problems Given a set of tasks to be performed and a set of

52、assignees who are available to perform these tasks, the problem is to determine which assignee should be assigned to each task. (給定了一系列所 要完成的任務(wù)以及一系列完成任務(wù)的被 指派者，所需要解決的問題就是要確定 出哪一個人被指派進行哪一項任務(wù)) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 92 The Model for Assignment ProblemsThe Model for Assignment Problems T

53、o fit the model for an assignment problem, the following assumptions need to be satisfied: (為了符合指派問題的模型， 需要滿足下面的一些假設(shè)) 1. The number of assignees and the number of tasks are the same. (被指派 者的數(shù)量和任務(wù)的數(shù)量是相同的) 2. Each assignee is to be assigned to exactly one task. (每一個被指派者只完 成一項任務(wù)) Copyright 2007 深圳大學(xué)管理學(xué)

54、院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 93 The Model for Assignment ProblemsThe Model for Assignment Problems 3. Each task is to be performed by exactly one assignee. (每一項任務(wù)只能由一個被指 派者來完成) 4. There is a cost associated with each combination of an assignee performing a task. (每一個被指派者和每一項任務(wù)的組 合都會有一個相關(guān)的成本) 5. The objective is

55、 to determine how all the assignments should be made to minimize the total cost. (問題的目標(biāo)是要確定怎樣進 行指派才能使得總成本達到最小) Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 94 The Network RepresentationThe Network Representation Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 95 指派問題的網(wǎng)絡(luò)表示法指派問題的網(wǎng)絡(luò)表示法 所有指派者都按照次序排列在所有指派者都按照次序排列在 左邊左邊

56、 需要完成的任務(wù)都排列在右邊需要完成的任務(wù)都排列在右邊 箭頭代表每一個可能的指派箭頭代表每一個可能的指派 需要選擇箭頭，從每一個被指需要選擇箭頭，從每一個被指 派者指向每一項任務(wù)派者指向每一項任務(wù) 每一個箭頭旁邊的數(shù)字代表如每一個箭頭旁邊的數(shù)字代表如 果這個指派被選中的話，其成果這個指派被選中的話，其成 本的大小本的大小 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 96 指派問題是一種特殊的運輸問題指派問題是一種特殊的運輸問題 被指派者：出發(fā)地被指派者：出發(fā)地 任務(wù)：目的地任務(wù)：目的地 每一個出發(fā)地的供每一個出發(fā)地的供 應(yīng)量都為應(yīng)量都為1 1 每一個目的地的需

57、每一個目的地的需 求量都為求量都為1 1 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 97 指派問題的變形指派問題的變形 某些被指派者不能進行某某些被指派者不能進行某 些任務(wù)些任務(wù) 任務(wù)比被指派者多任務(wù)比被指派者多 被指派者比任務(wù)多被指派者比任務(wù)多 每一個被指派者可以被指每一個被指派者可以被指 派給多于一個的任務(wù)派給多于一個的任務(wù) 每一項任務(wù)可以由多個被每一項任務(wù)可以由多個被 指派者共同完成指派者共同完成 Copyright 2007 深圳大學(xué)管理學(xué)院深圳大學(xué)管理學(xué)院 運籌學(xué)運籌學(xué) 98 Job Shop (Assigning Machines to Loca