第五章運輸問題和指派問題運輸問題和指派問題是兩類相互聯(lián)系的特殊線性規(guī)劃問題,它們的基本形屬于網(wǎng)絡配送問題。本章的學習目的如下：1.理解運輸和指派問題以及這些問題的各種變形的特征；2.掌握此類問題的建模方法和各種應用。第五章運輸問題和指派問題運輸問題和指派問題是兩類相互聯(lián)系1§5.2案例研究：P&T公司的配送問題P&T公司是一家由家族經(jīng)營的小公司。它收購生菜并在食品罐頭廠中把它們加工成罐頭，然后再把這些罐頭分銷到各地賣出去。公司下屬有三個罐頭廠，即貝林翰的罐頭廠1，尤基尼的罐頭廠2和艾爾貝·李的罐頭廠3。§5.2案例研究：P&T公司的配送問題P&T公司是一家由家族2公司要用卡車將3個罐頭廠的產(chǎn)品運送到四個分銷倉庫，地點在薩克拉門托，鹽湖城，賴皮特城和奧爾巴古。詳細信息如下表：罐頭加工廠產(chǎn)量倉庫分配量貝林翰尤基尼艾爾貝·李75125100薩克拉門托鹽湖城賴皮特城奧爾巴古80657085合計300合計300公司要用卡車將3個罐頭廠的產(chǎn)品運送到四個分銷倉庫，地點在薩克3P&T公司的單位卡車的運送成本（單位：美元）至從倉庫薩克拉門托鹽湖城賴皮特城奧爾巴古食品罐頭廠貝林翰尤基尼艾爾貝李464352995513416682654690388867791685P&T公司的單位卡車4至從倉庫薩克拉門托鹽湖城賴皮特城奧爾巴古食品罐頭廠貝林翰尤基尼艾爾貝李75500650055150085P&T公司的當前運送計劃

（單位：車）至從倉庫薩克拉門托鹽湖城賴皮特5公司當前的運輸策略依據(jù)：1.因為在貝林翰的罐頭廠距離倉庫較遠，所以把它的產(chǎn)品運送到最近的一個倉庫。也就是薩克拉門托的那個倉庫。如果還有剩余的話，就要運送到鹽湖城的倉庫中去。2.因為在奧爾巴古的倉庫距離食品廠最遠，所以就要從最近的一個罐頭廠（艾爾貝李的罐頭廠）中運送產(chǎn)品到奧爾巴古。公司當前的運輸策略依據(jù)：1.因為在貝林翰的罐頭廠距離倉庫較遠6如果還有剩余的話，就要運送到賴皮特城的倉庫中。3.用尤基尼的罐頭廠滿足其他倉庫的剩余需求。當前運輸計劃下的總運輸成本為：75（464）＋5（352）＋65（416）＋55（690）＋15（388）＋85（685）＝165595（美元）管理科學小組現(xiàn)在要做的工作就是檢查當前的運輸計劃，看看是否能夠制定出一個新的運輸計劃，使總運輸成本下降到一個絕對最小值。如果還有剩余的話，就要運送到賴皮特城的倉庫中。7§5.2運輸問題的特征1.有關概念產(chǎn)地（出發(fā)地），銷地（目的地）產(chǎn)量（供應量），銷量（需求量）單位運輸費用（單位配送成本）2.供求假設每一個出發(fā)地都有一個固定的供應量，所有的供應量都必須配送到目的地。與之相類似，每一個目的地都有一個固定的需求量，§5.2運輸問題的特征1.有關概念8整個需求量都必須由出發(fā)地滿足。在運輸問題的基本模型中，供應量＝需求量3.成本假設從任何一個出發(fā)地到任何一個目的地的貨物配送成本和所配送的數(shù)量成線性比例關系，因此這個成本就等于配送的單位成本乘以所配送的數(shù)量。4.運輸問題的代數(shù)模型（略）整個需求量都必須由出發(fā)地滿足。95.整數(shù)解性質(zhì)只要它的供應量和需求量都是整數(shù)，任何有可行解的運輸問題必然由所有決策變量都是整數(shù)的最優(yōu)解。因此，在求解時，沒有必要加上所有變量都是整數(shù)的約束條件。6.Excel電子表格模型Excel工作表\P&T公司的運輸問題.xls5.整數(shù)解性質(zhì)10§5.3各種運輸問題變體的建模P&T公司問題是一個典型的運輸問題，符合運輸問題的每一個條件。但是在現(xiàn)實生活中這種情況很少出現(xiàn)。一個或幾個特征不符合運輸問題條件的運輸問題在線性規(guī)劃問題中經(jīng)常出現(xiàn)。如：1.供應總量超出了需求總量（供過于求）;2.供應總量小于需求總量（供不應求）；3.一個目的地同時存在著最小需求和最大§5.3各種運輸問題變體的建模P&T公司問題是一個典型的運11需求，于是所有在這兩個數(shù)值之間的數(shù)量都是可以接受的；4.在配送中不能使用特定的出發(fā)地——目的地組合；5.目標是使與配送數(shù)量有關的總利潤最大而不是使成本最小。于是將具有上述一個或一些特征的運輸問題轉(zhuǎn)換為基本的運輸問題然后求解基本的運輸問題即可使問題得到解決。需求，于是所有在這兩個數(shù)值之間的數(shù)量都是可以接受的；12例1：求佳產(chǎn)品（BetterProductCo.）公司決定使用三個有生產(chǎn)余力的工廠進行四種新產(chǎn)品的生產(chǎn)制造。每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任一種產(chǎn)品的數(shù)量來衡量，有關參數(shù)列表如下：單位成本（美元）生產(chǎn)能力產(chǎn)品：1234工廠12341403727293028－27242321757545要求的產(chǎn)量20303040例1：求佳產(chǎn)品（BetterProd13電子表格模型的建立Excel工作表\求佳公司問題.xls例2：耐芙迪（Nifty）公司在三個工廠中專門生產(chǎn)一種產(chǎn)品。在未來四個月中，有四個處于國內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很有可能大量訂購。顧客1是公司最好的顧客，所以他的全部訂單都應該滿足；顧客2和3也是公司很重要的顧客，所以營銷經(jīng)理認為作為最低限度至少要滿足他們的訂單的1／3；對于顧客4，他認為并不需要進行特殊考慮。電子表格模型的建立14耐芙迪公司問題中的數(shù)據(jù)單位利潤（美元）產(chǎn)量顧客1234工廠123553729421859463251534835800050007000最小采購量要求采購量70007000300090002000600008000耐芙迪公司問題中的數(shù)據(jù)單位利潤（美元）產(chǎn)顧客1234工廠1515電子表格模型Excel工作表\耐芙迪公司問題.xls電子表格模型16§5.4運輸問題變形的其他一些應用例1：米德羅水管站（MetroWaterDistrict）是一個主管著廣闊地域的水資源分配的機構(gòu)。由于這個地域十分干燥，所以這個機構(gòu)需要從外地引水。這些引入的水來自科倫坡、賽克隆以及卡路里河這三條河流。引入這些水后，這個機構(gòu)把水轉(zhuǎn)賣給這個地區(qū)的用戶。它的主要客戶是布都、老斯戴維斯、圣哥以及豪利格拉斯等城市的供水部門。§5.4運輸問題變形的其他一些應用例1：米德羅水管站（Me17米德羅水管站的水資源數(shù)據(jù)每立方英尺的成本（美元）可供應量布都勞斯戴維斯圣哥豪斯格拉斯科倫坡河賽克隆河卡路里河160140190130130200220190230170150－565需求2541.5（百萬立方英尺）米德羅水管站的水資源數(shù)據(jù)每立方英尺18電子表格模型及求解Excel工作表\米德羅水管站問題.xls例2：北方飛機制造公司（NorthernAirplaneCompany）為全世界的航空公司生產(chǎn)各種商務飛機。制造過程的最后一步是生產(chǎn)噴氣式發(fā)動機并把它們安裝到已經(jīng)完成的飛機框架之中去（非常快的一個操作）。按照公司的一些訂單合同，不久公司要交付使用相當多數(shù)量的飛機。所以有必要制定今后四個月的生產(chǎn)計劃。電子表格模型及求解19北方飛機制造公司問題的生產(chǎn)進度安排數(shù)據(jù)月份計劃安裝量最大產(chǎn)量單位生產(chǎn)成本（百萬美元）單位存儲成本（美元）正常時間加班時間正常時間加班時間1234101525202030255101510101.081.111.101.131.101.121.111.15150001500015000北方飛機制造公司問題的生產(chǎn)進度安排數(shù)據(jù)月份計劃安裝量最大產(chǎn)量20電子表格模型及求解Excel工作表\北方飛機制造公司問題.xls例3：米德爾城學區(qū)（MiddletownSchoolDistrict)開辦了第三所中學，需要為每一所學校重新劃定這個城市內(nèi)的服務區(qū)域。在初步的計劃中，這個城是被分為擁有大致相同數(shù)量人口的九個區(qū)域。學區(qū)管理者認為劃分入學區(qū)域界線的適當目標是要使學生到學校的平均路程最短。在這個初步的計劃之中，他們要確定為了實現(xiàn)這一目標每一個區(qū)域內(nèi)有多少學生要安排到每一所學校中去。電子表格模型及求解21米德爾學區(qū)問題的數(shù)據(jù)距離學校的距離（英里）高中學生數(shù)量123區(qū)域1234567892.21.40.51.20.91.12.71.81.51.91.31.80.30.71.60.71.21.72.51.71.12.01.00.61.50.80.7500400450400500450450400500最小招生數(shù)最大招生數(shù)120018001100170010001500米德爾學區(qū)問題的數(shù)據(jù)距離學校的距離（英里）高中學生數(shù)量12322電子表格模型及求解Excel工作表\米德爾學區(qū)問題.xls例4：源豐公司（EnergeticCompany)需要為新的建筑物建立起能源系統(tǒng)。建筑物的能源需求主要來自于下面三個方面（1）電，（2）熱水，（3）建筑物內(nèi)取暖。每天這三類用途的能源需求（以相同的單位衡量）分別是10個單位、20個單位和30個單位。點的需求只能通過購電來滿足。但是對于其他的兩種能源需求來說，可以通過這三個能量來源中的一個或者是幾個組合得到滿足。電子表格模型及求解23電子表格模型及求解Excel工作表\源豐公司問題.xls電子表格模型及求解24§5.5特賽格公司的選址問題特賽格公司（TexagoCorporation）是一家設在美國本土的大型一體化石油公司。這家公司大部分的石油在公司自己的油田中生產(chǎn)，所需的其他部分從中東地區(qū)進口。公司擁有大型配送網(wǎng)絡，把石油運送到公司的煉油廠，然后再把石油產(chǎn)品從煉油廠運送到公司的配送中心。特賽格公司正在持續(xù)增加其幾種主要產(chǎn)品的市場占有率。因此管理層決定建立§5.5特賽格公司的選址問題特賽格公司（TexagoC25一個新的煉油廠來增加公司的產(chǎn)量，同時增加從中東地區(qū)進口石油的數(shù)量。接下來所要作出的決策就是確定在什么地方建設新的煉油廠。新煉油廠的加入對整個配送系統(tǒng)都將產(chǎn)生巨大的影響,其中包括要確定從每個出發(fā)地運輸?shù)綗捰蛷S的原油數(shù)量,以及從每一個煉油廠運送石油到每一個配送中心的數(shù)量.因此,管理者選擇新煉油廠建設地點的三個關鍵因素是:1.從出發(fā)地運送原油到所有煉油廠(包括新一個新的煉油廠來增加公司的產(chǎn)量，同時增加從中東地區(qū)進口石油的26煉油廠）的成本;2.從所有煉油廠（包括新煉油廠）運送石油制品到每一個配送中心的成本;3.新的煉油廠的運作成本,包括勞動力成本、稅賦、原料（不包括原油）成本、能源成本、保險成本，等等。（資金成本并不是一個所要關注的因素，因為任何地點的資金成本幾乎都是一樣的）。我們現(xiàn)在的問題是要確定新的煉油廠的位置（地址），使得總成本最小。煉油廠）的成本;27特賽格公司問題的解決辦法收集必要的數(shù)據(jù)Excel工作表\特賽格公司的數(shù)據(jù)表.doc計算新煉油廠的每個位置選擇帶來的總的原油運輸成本;例1若新的煉油廠設在洛杉磯，則有如下的運輸問題Excel工作表\特賽格公司的選址問題.xls特賽格公司問題的解決辦法收集必要的數(shù)據(jù)28計算新煉油廠的每個位置選擇帶來的總石油制品運輸成本。例2若新的煉油廠設在洛杉磯，則有如下的運輸問題Excel工作表\特賽格公司的選址問題.xls計算特賽格公司每一個備選廠址所帶來的年變動成本。例3特賽格煉油廠每一個備選廠址所帶來的年變動成本列表如下：Excel工作表\特賽格公司的數(shù)據(jù)表.doc計算新煉油廠的每個位置選擇帶來的總石油制品運輸成本。29§5.6指派問題的特征指派問題就是給定一組任務和一組人,所需要確定的就是哪個人完成哪個任務。指派問題的基本模型，需要滿足下面的假設：1.被指派者的數(shù)量和任務的數(shù)量是相同的；2.每一個被指派者只完成一項任務；3.每一項任務只能由一個被指派者來完成；4.每一個被指派者和每一項任務的組合都會有一個相關的成本；5.問題的目標是要確定怎樣進行指派才能使得總成本達到最小。§5.6指派問題的特征指派問題就是給定一組任務和一組人,所30塞爾默（Sellmore)公司的問題塞爾默公司的營銷經(jīng)理將要主持召開一年一度的有營銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會議。為了更好地安排這次會議，他雇用了四個臨時工（安、伊安、瓊、肖恩），每一個人負責完成下面的一項任務：1.書面陳述的文字處理；2.只作口頭和書面陳述的電腦圖；3.會議材料的準備，包括書面材料的抄寫和組織；4.處理與會者的提前和當場注冊報名。現(xiàn)在他需要確定要將那一項任務指派給那一個人。塞爾默（Sellmore)公司的問題31塞爾默公司問題的有關數(shù)據(jù)塞爾默公司問題的電子表格模型Excel工作表\塞爾默公司問題.xls臨時工每一項任務所需要的時間（小時）每小時工資（美元）文字處理繪圖材料準備記錄安伊恩瓊肖恩3547393241455651273236254051434614121315塞爾默公司問題的有關數(shù)據(jù)臨時工每一項任務所需要的時間（小時）32§5.7對指派問題變形的建模當問題本身是一個指派的問題,但上一節(jié)基本的指派問題模型中的一個或多個假設不成立時,稱它們?yōu)橹概蓡栴}的變形。我們考慮下面一些特征：1.有一些被指派者并不能進行某一些的人物。2.雖然每一個被指派者完成一項任務，但是任務比被指派者多。所以其中某些任務并沒有得到執(zhí)行。§5.7對指派問題變形的建模當問題本身是一個指派的問題,但333.雖然每一項任務只由一個被指派者完成，但是這里被指派者比要完成的任務多。所以，其中有一些被指派者沒有指派到任務。4.每一個被指派者可以同時被派給多于一個任務。5.每一項任務都可以有多個被指派者共同完成。3.雖然每一項任務只由一個被指派者完成，但是這里被指派者比要34例1嬌普肖普（JobShoCompany)購買了三種不同類型的新設備。但是在車間里卻有五個不同的地點可供安裝。其中某些地點比其他的地點更為需要某些設備，原因是他們十分接近工作中心，流入和流出這些設備的工作很多。因此該問題的目標是把這些設備安裝到有效的地點上，使物料處理成本達到最小。例1嬌普肖普（JobShoCompany)購買了三種35嬌普肖普公司問題中的原料處理成本數(shù)據(jù)嬌普肖普問題的電子表格模型Excel工作表\嬌普肖普問題模型.xls位置每小時成本（美元）12345機器1231315416－71213101420615167嬌普肖普公司問題中的原料處理成本數(shù)據(jù)位置每小時成本（美元）136例2現(xiàn)在我們再來看一下§5.3節(jié)所講到的例子。求佳產(chǎn)品公司需要安排三個工廠來生產(chǎn)四種新產(chǎn)品。我們得到的最優(yōu)結(jié)果是：第一個廠生產(chǎn)第二和第三種產(chǎn)品各30單位，第二個廠只生產(chǎn)第四種產(chǎn)品15單位，第三個廠生產(chǎn)第一和第四種產(chǎn)品分別為20，25單位，成本為$3260美元。從結(jié)果中可以看出，第四種產(chǎn)品分到了兩個廠生產(chǎn)，這樣會增加隱性成本。所以，我們加進一些新的要求：每個工廠至少完成一種產(chǎn)品，一種產(chǎn)品不能分到兩個或兩個以上的廠中生產(chǎn)。這樣，就得到了新的模型：Excel工作表\求佳公司問題.xls例2現(xiàn)在我們再來看一下§5.3節(jié)所講到的例子。求佳產(chǎn)品公司37例3現(xiàn)在我們再回到§5.4節(jié)中的米德爾城學區(qū)劃分學生入學區(qū)域問題,從結(jié)果中可以看出,第五區(qū)域的學生被分配到兩個學校;另外,容量最大的學校卻被派去了最少的學生,雖然也可以接受,但是向這個學校指派更多的學生會更受歡迎。現(xiàn)在我們要求每個區(qū)域的學生只能去一所學校，每一所學校要接受三個區(qū)域的學生。這時問題又變了!電子表格模型Excel工作表\米德爾學區(qū)問題.xls例3現(xiàn)在我們再回到§5.4節(jié)中的米德爾城學區(qū)劃分學生入學區(qū)38案例5.2項目選擇Excel工作表\案例5.2項目選擇.xlsExcel工作表\案例5.2項目選擇（二）.xls案例5.2項目選擇Excel工作表\案例5.2項目選擇.xl39第五章-運輸問題和指派問題課件40第五章-運輸問題和指派問題課件41第五章-運輸問題和指派問題課件42第五章-運輸問題和指派問題課件43第五章-運輸問題和指派問題課件44第五章運輸問題和指派問題運輸問題和指派問題是兩類相互聯(lián)系的特殊線性規(guī)劃問題,它們的基本形屬于網(wǎng)絡配送問題。本章的學習目的如下：1.理解運輸和指派問題以及這些問題的各種變形的特征；2.掌握此類問題的建模方法和各種應用。第五章運輸問題和指派問題運輸問題和指派問題是兩類相互聯(lián)系45§5.2案例研究：P&T公司的配送問題P&T公司是一家由家族經(jīng)營的小公司。它收購生菜并在食品罐頭廠中把它們加工成罐頭，然后再把這些罐頭分銷到各地賣出去。公司下屬有三個罐頭廠，即貝林翰的罐頭廠1，尤基尼的罐頭廠2和艾爾貝·李的罐頭廠3。§5.2案例研究：P&T公司的配送問題P&T公司是一家由家族46公司要用卡車將3個罐頭廠的產(chǎn)品運送到四個分銷倉庫，地點在薩克拉門托，鹽湖城，賴皮特城和奧爾巴古。詳細信息如下表：罐頭加工廠產(chǎn)量倉庫分配量貝林翰尤基尼艾爾貝·李75125100薩克拉門托鹽湖城賴皮特城奧爾巴古80657085合計300合計300公司要用卡車將3個罐頭廠的產(chǎn)品運送到四個分銷倉庫，地點在薩克47P&T公司的單位卡車的運送成本（單位：美元）至從倉庫薩克拉門托鹽湖城賴皮特城奧爾巴古食品罐頭廠貝林翰尤基尼艾爾貝李464352995513416682654690388867791685P&T公司的單位卡車48至從倉庫薩克拉門托鹽湖城賴皮特城奧爾巴古食品罐頭廠貝林翰尤基尼艾爾貝李75500650055150085P&T公司的當前運送計劃

（單位：車）至從倉庫薩克拉門托鹽湖城賴皮特49公司當前的運輸策略依據(jù)：1.因為在貝林翰的罐頭廠距離倉庫較遠，所以把它的產(chǎn)品運送到最近的一個倉庫。也就是薩克拉門托的那個倉庫。如果還有剩余的話，就要運送到鹽湖城的倉庫中去。2.因為在奧爾巴古的倉庫距離食品廠最遠，所以就要從最近的一個罐頭廠（艾爾貝李的罐頭廠）中運送產(chǎn)品到奧爾巴古。公司當前的運輸策略依據(jù)：1.因為在貝林翰的罐頭廠距離倉庫較遠50如果還有剩余的話，就要運送到賴皮特城的倉庫中。3.用尤基尼的罐頭廠滿足其他倉庫的剩余需求。當前運輸計劃下的總運輸成本為：75（464）＋5（352）＋65（416）＋55（690）＋15（388）＋85（685）＝165595（美元）管理科學小組現(xiàn)在要做的工作就是檢查當前的運輸計劃，看看是否能夠制定出一個新的運輸計劃，使總運輸成本下降到一個絕對最小值。如果還有剩余的話，就要運送到賴皮特城的倉庫中。51§5.2運輸問題的特征1.有關概念產(chǎn)地（出發(fā)地），銷地（目的地）產(chǎn)量（供應量），銷量（需求量）單位運輸費用（單位配送成本）2.供求假設每一個出發(fā)地都有一個固定的供應量，所有的供應量都必須配送到目的地。與之相類似，每一個目的地都有一個固定的需求量，§5.2運輸問題的特征1.有關概念52整個需求量都必須由出發(fā)地滿足。在運輸問題的基本模型中，供應量＝需求量3.成本假設從任何一個出發(fā)地到任何一個目的地的貨物配送成本和所配送的數(shù)量成線性比例關系，因此這個成本就等于配送的單位成本乘以所配送的數(shù)量。4.運輸問題的代數(shù)模型（略）整個需求量都必須由出發(fā)地滿足。535.整數(shù)解性質(zhì)只要它的供應量和需求量都是整數(shù)，任何有可行解的運輸問題必然由所有決策變量都是整數(shù)的最優(yōu)解。因此，在求解時，沒有必要加上所有變量都是整數(shù)的約束條件。6.Excel電子表格模型Excel工作表\P&T公司的運輸問題.xls5.整數(shù)解性質(zhì)54§5.3各種運輸問題變體的建模P&T公司問題是一個典型的運輸問題，符合運輸問題的每一個條件。但是在現(xiàn)實生活中這種情況很少出現(xiàn)。一個或幾個特征不符合運輸問題條件的運輸問題在線性規(guī)劃問題中經(jīng)常出現(xiàn)。如：1.供應總量超出了需求總量（供過于求）;2.供應總量小于需求總量（供不應求）；3.一個目的地同時存在著最小需求和最大§5.3各種運輸問題變體的建模P&T公司問題是一個典型的運55需求，于是所有在這兩個數(shù)值之間的數(shù)量都是可以接受的；4.在配送中不能使用特定的出發(fā)地——目的地組合；5.目標是使與配送數(shù)量有關的總利潤最大而不是使成本最小。于是將具有上述一個或一些特征的運輸問題轉(zhuǎn)換為基本的運輸問題然后求解基本的運輸問題即可使問題得到解決。需求，于是所有在這兩個數(shù)值之間的數(shù)量都是可以接受的；56例1：求佳產(chǎn)品（BetterProductCo.）公司決定使用三個有生產(chǎn)余力的工廠進行四種新產(chǎn)品的生產(chǎn)制造。每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任一種產(chǎn)品的數(shù)量來衡量，有關參數(shù)列表如下：單位成本（美元）生產(chǎn)能力產(chǎn)品：1234工廠12341403727293028－27242321757545要求的產(chǎn)量20303040例1：求佳產(chǎn)品（BetterProd57電子表格模型的建立Excel工作表\求佳公司問題.xls例2：耐芙迪（Nifty）公司在三個工廠中專門生產(chǎn)一種產(chǎn)品。在未來四個月中，有四個處于國內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很有可能大量訂購。顧客1是公司最好的顧客，所以他的全部訂單都應該滿足；顧客2和3也是公司很重要的顧客，所以營銷經(jīng)理認為作為最低限度至少要滿足他們的訂單的1／3；對于顧客4，他認為并不需要進行特殊考慮。電子表格模型的建立58耐芙迪公司問題中的數(shù)據(jù)單位利潤（美元）產(chǎn)量顧客1234工廠123553729421859463251534835800050007000最小采購量要求采購量70007000300090002000600008000耐芙迪公司問題中的數(shù)據(jù)單位利潤（美元）產(chǎn)顧客1234工廠1559電子表格模型Excel工作表\耐芙迪公司問題.xls電子表格模型60§5.4運輸問題變形的其他一些應用例1：米德羅水管站（MetroWaterDistrict）是一個主管著廣闊地域的水資源分配的機構(gòu)。由于這個地域十分干燥，所以這個機構(gòu)需要從外地引水。這些引入的水來自科倫坡、賽克隆以及卡路里河這三條河流。引入這些水后，這個機構(gòu)把水轉(zhuǎn)賣給這個地區(qū)的用戶。它的主要客戶是布都、老斯戴維斯、圣哥以及豪利格拉斯等城市的供水部門。§5.4運輸問題變形的其他一些應用例1：米德羅水管站（Me61米德羅水管站的水資源數(shù)據(jù)每立方英尺的成本（美元）可供應量布都勞斯戴維斯圣哥豪斯格拉斯科倫坡河賽克隆河卡路里河160140190130130200220190230170150－565需求2541.5（百萬立方英尺）米德羅水管站的水資源數(shù)據(jù)每立方英尺62電子表格模型及求解Excel工作表\米德羅水管站問題.xls例2：北方飛機制造公司（NorthernAirplaneCompany）為全世界的航空公司生產(chǎn)各種商務飛機。制造過程的最后一步是生產(chǎn)噴氣式發(fā)動機并把它們安裝到已經(jīng)完成的飛機框架之中去（非常快的一個操作）。按照公司的一些訂單合同，不久公司要交付使用相當多數(shù)量的飛機。所以有必要制定今后四個月的生產(chǎn)計劃。電子表格模型及求解63北方飛機制造公司問題的生產(chǎn)進度安排數(shù)據(jù)月份計劃安裝量最大產(chǎn)量單位生產(chǎn)成本（百萬美元）單位存儲成本（美元）正常時間加班時間正常時間加班時間1234101525202030255101510101.081.111.101.131.101.121.111.15150001500015000北方飛機制造公司問題的生產(chǎn)進度安排數(shù)據(jù)月份計劃安裝量最大產(chǎn)量64電子表格模型及求解Excel工作表\北方飛機制造公司問題.xls例3：米德爾城學區(qū)（MiddletownSchoolDistrict)開辦了第三所中學，需要為每一所學校重新劃定這個城市內(nèi)的服務區(qū)域。在初步的計劃中，這個城是被分為擁有大致相同數(shù)量人口的九個區(qū)域。學區(qū)管理者認為劃分入學區(qū)域界線的適當目標是要使學生到學校的平均路程最短。在這個初步的計劃之中，他們要確定為了實現(xiàn)這一目標每一個區(qū)域內(nèi)有多少學生要安排到每一所學校中去。電子表格模型及求解65米德爾學區(qū)問題的數(shù)據(jù)距離學校的距離（英里）高中學生數(shù)量123區(qū)域1234567892.21.40.51.20.91.12.71.81.51.91.31.80.30.71.60.71.21.72.51.71.12.01.00.61.50.80.7500400450400500450450400500最小招生數(shù)最大招生數(shù)120018001100170010001500米德爾學區(qū)問題的數(shù)據(jù)距離學校的距離（英里）高中學生數(shù)量12366電子表格模型及求解Excel工作表\米德爾學區(qū)問題.xls例4：源豐公司（EnergeticCompany)需要為新的建筑物建立起能源系統(tǒng)。建筑物的能源需求主要來自于下面三個方面（1）電，（2）熱水，（3）建筑物內(nèi)取暖。每天這三類用途的能源需求（以相同的單位衡量）分別是10個單位、20個單位和30個單位。點的需求只能通過購電來滿足。但是對于其他的兩種能源需求來說，可以通過這三個能量來源中的一個或者是幾個組合得到滿足。電子表格模型及求解67電子表格模型及求解Excel工作表\源豐公司問題.xls電子表格模型及求解68§5.5特賽格公司的選址問題特賽格公司（TexagoCorporation）是一家設在美國本土的大型一體化石油公司。這家公司大部分的石油在公司自己的油田中生產(chǎn)，所需的其他部分從中東地區(qū)進口。公司擁有大型配送網(wǎng)絡，把石油運送到公司的煉油廠，然后再把石油產(chǎn)品從煉油廠運送到公司的配送中心。特賽格公司正在持續(xù)增加其幾種主要產(chǎn)品的市場占有率。因此管理層決定建立§5.5特賽格公司的選址問題特賽格公司（TexagoC69一個新的煉油廠來增加公司的產(chǎn)量，同時增加從中東地區(qū)進口石油的數(shù)量。接下來所要作出的決策就是確定在什么地方建設新的煉油廠。新煉油廠的加入對整個配送系統(tǒng)都將產(chǎn)生巨大的影響,其中包括要確定從每個出發(fā)地運輸?shù)綗捰蛷S的原油數(shù)量,以及從每一個煉油廠運送石油到每一個配送中心的數(shù)量.因此,管理者選擇新煉油廠建設地點的三個關鍵因素是:1.從出發(fā)地運送原油到所有煉油廠(包括新一個新的煉油廠來增加公司的產(chǎn)量，同時增加從中東地區(qū)進口石油的70煉油廠）的成本;2.從所有煉油廠（包括新煉油廠）運送石油制品到每一個配送中心的成本;3.新的煉油廠的運作成本,包括勞動力成本、稅賦、原料（不包括原油）成本、能源成本、保險成本，等等。（資金成本并不是一個所要關注的因素，因為任何地點的資金成本幾乎都是一樣的）。我們現(xiàn)在的問題是要確定新的煉油廠的位置（地址），使得總成本最小。煉油廠）的成本;71特賽格公司問題的解決辦法收集必要的數(shù)據(jù)Excel工作表\特賽格公司的數(shù)據(jù)表.doc計算新煉油廠的每個位置選擇帶來的總的原油運輸成本;例1若新的煉油廠設在洛杉磯，則有如下的運輸問題Excel工作表\特賽格公司的選址問題.xls特賽格公司問題的解決辦法收集必要的數(shù)據(jù)72計算新煉油廠的每個位置選擇帶來的總石油制品運輸成本。例2若新的煉油廠設在洛杉磯，則有如下的運輸問題Excel工作表\特賽格公司的選址問題.xls計算特賽格公司每一個備選廠址所帶來的年變動成本。例3特賽格煉油廠每一個備選廠址所帶來的年變動成本列表如下：Excel工作表\特賽格公司的數(shù)據(jù)表.doc計算新煉油廠的每個位置選擇帶來的總石油制品運輸成本。73§5.6指派問題的特征指派問題就是給定一組任務和一組人,所需要確定的就是哪個人完成哪個任務。指派問題的基本模型，需要滿足下面的假設：1.被指派者的數(shù)量和任務的數(shù)量是相同的；2.每一個被指派者只完成一項任務；3.每一項任務只能由一個被指派者來完成；4.每一個被指派者和每一項任務的組合都會有一個相關的成本；5.問題的目標是要確定怎樣進行指派才能使得總成本達到最小。§5.6指派問題的特征指派問題就是給定一組任務和一組人,所74塞爾默（Sellmore)公司的問題塞爾默公司的營銷經(jīng)理將要主持召開一年一度的有營銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會議。為了更好地安排這次會議，他雇用了四個臨時工（安、伊安、瓊、肖恩），每一個人負責完成下面的一項任務：1.書面陳述的文字處理；2.只作口頭和書面陳述的電腦圖；3.會議材料的準備，包括書面材料的抄寫和組織；4.處理與會者的提前和當場注冊報名。現(xiàn)在他需要確定要將那一項任務指派給那一個人。塞爾默（Sellmore)公司的問題75塞爾默公司問題的有關數(shù)據(jù)塞爾默公司問題的電子表格模型Excel工作表\塞爾默公司問題.xls臨時工每一項任務所需要的時間（小時）每小時工資（美元）文字處理繪圖材料準備記錄安伊恩瓊肖恩