第五章 運(yùn)輸問題與指派問題ppt課件

1、運(yùn)輸問題和指派問題是兩類相互聯(lián)絡(luò)的特殊線性規(guī)劃問題,它們的根本形屬于網(wǎng)絡(luò)配送問題。本章的學(xué)習(xí)目的如下：1.了解運(yùn)輸和指派問題以及這些問題的各種變形的特征；2.掌握此類問題的建模方法和各種運(yùn)用。P&T公司是一家由家族運(yùn)營的小公司。它收買生菜并在食品罐頭廠中把它們加工成罐頭，然后再把這些罐頭分銷到各地賣出去。公司下屬有三個罐頭廠，即貝林翰的罐頭廠1，尤基尼的罐頭廠2和艾爾貝李的罐頭廠3。公司要用卡車將3個罐頭廠的產(chǎn)品運(yùn)送到四個分銷倉庫，地點(diǎn)在薩克拉門托，鹽湖城，賴皮特城和奧爾巴古。詳細(xì)信息如下表：罐頭加工廠 產(chǎn)量倉庫分配量貝林翰尤基尼艾爾貝李75125100薩克拉門托鹽湖城賴皮特城奧爾巴古

2、80657085合計(jì)300合計(jì)300 P&T公司的單位卡車 的運(yùn)送本錢單位：美圓 至 從倉庫薩克拉門托 鹽湖城 賴皮特城奧爾巴古食品罐頭廠貝林翰尤基尼艾爾貝李464352995513416682654690388867791685 至 從倉庫薩克拉門托 鹽湖城賴皮特城奧爾巴古食品罐頭廠貝林翰尤基尼艾爾貝李755006500551500851.由于在貝林翰的罐頭廠間隔倉庫較遠(yuǎn)，所以把它的產(chǎn)品運(yùn)送到最近的一個倉庫。也就是薩克拉門托的那個倉庫。假設(shè)還有剩余的話，就要運(yùn)送到鹽湖城的倉庫中去。2.由于在奧爾巴古的倉庫間隔食品廠最遠(yuǎn)，所以就要從最近的一個罐頭廠艾爾貝李的罐頭廠中運(yùn)送產(chǎn)品到奧爾巴古。

3、假設(shè)還有剩余的話，就要運(yùn)送到賴皮特城的倉庫中。3.用尤基尼的罐頭廠滿足其他倉庫的剩余需求。當(dāng)前運(yùn)輸方案下的總運(yùn)輸本錢為：75464535265416556901538885685165595美圓 管文科學(xué)小組如今要做的任務(wù)就是檢查當(dāng)前的運(yùn)輸方案，看看能否可以制定出一個新的運(yùn)輸方案，使總運(yùn)輸本錢下降到一個絕對最小值。1.有關(guān)概念產(chǎn)地出發(fā)地，銷地目的地產(chǎn)量供應(yīng)量，銷量需求量單位運(yùn)輸費(fèi)用單位配送本錢2.供求假設(shè)每一個出發(fā)地都有一個固定的供應(yīng)量，一切的供應(yīng)量都必需配送到目的地。與之相類似，每一個目的地都有一個固定的需求量，整個需求量都必需由出發(fā)地滿足。 在運(yùn)輸問題的根本模型中，供應(yīng)量需求量3.本錢假設(shè)

4、從任何一個出發(fā)地到任何一個目的地的貨物配送本錢和所配送的數(shù)量成線性比例關(guān)系，因此這個本錢就等于配送的單位本錢乘以所配送的數(shù)量。4.運(yùn)輸問題的代數(shù)模型略5.整數(shù)解性質(zhì)只需它的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運(yùn)輸問題必然由一切決策變量都是整數(shù)的最優(yōu)解。因此，在求解時，沒有必要加上一切變量都是整數(shù)的約束條件。6.Excel電子表格模型Excel任務(wù)表P&T公司的運(yùn)輸問題.xlsP&T公司問題是一個典型的運(yùn)輸問題，符合運(yùn)輸問題的每一個條件。但是在現(xiàn)實(shí)生活中這種情況很少出現(xiàn)。一個或幾個特征不符合運(yùn)輸問題條件的運(yùn)輸問題在線性規(guī)劃問題中經(jīng)常出現(xiàn)。如：1.供應(yīng)總量超出了需求總量供過于求;

5、2.供應(yīng)總量小于需求總量供不應(yīng)求；3.一個目的地同時存在著最小需求和最大需求，于是一切在這兩個數(shù)值之間的數(shù)量都是可以接受的；4.在配送中不能運(yùn)用特定的出發(fā)地目的地組合；5.目的是使與配送數(shù)量有關(guān)的總利潤最大而不是使本錢最小。于是將具有上述一個或一些特征的運(yùn)輸問題轉(zhuǎn)換為根本的運(yùn)輸問題然后求解根本的運(yùn)輸問題即可使問題得到處理。 例1：求佳產(chǎn)品Better Product Co.公司決議運(yùn)用三個有消費(fèi)余力的工廠進(jìn)展四種新產(chǎn)品的消費(fèi)制造。每單位產(chǎn)品需求等量的任務(wù)，所以工廠的有效消費(fèi)才干以每天消費(fèi)的任一種產(chǎn)品的數(shù)量來衡量，有關(guān)參數(shù)列表如下：單位成本（美元）生產(chǎn)能力產(chǎn)品：1234工廠12341403727

6、29302827242321757545要求的產(chǎn)量20303040電子表格模型的建立Excel任務(wù)表求佳公司問題.xls例2：耐芙迪Nifty公司在三個工廠中專門消費(fèi)一種產(chǎn)品。在未來四個月中，有四個處于國內(nèi)不同區(qū)域的潛在顧客零售商很有能夠大量訂購。顧客1是公司最好的顧客，所以他的全部訂單都應(yīng)該滿足；顧客2和3也是公司很重要的顧客，所以營銷經(jīng)理以為作為最低限制至少要滿足他們的訂單的13；對于顧客4，他以為并不需求進(jìn)展特殊思索。耐芙迪公司問題中的數(shù)據(jù)單位利潤（美元）產(chǎn)量顧客1234工廠123553729421859463251534835800050007000最小采購量要求采購量70007000

7、300090002000600008000電子表格模型Excel任務(wù)表耐芙迪公司問題.xls例1：米德羅水管站Metro Water District是一個主管著寬廣地域的水資源分配的機(jī)構(gòu)。由于這個地域非?？菰?，所以這個機(jī)構(gòu)需求從外地引水。這些引入的水來自科倫坡、賽克隆以及卡路里河這三條河流。引入這些水后，這個機(jī)構(gòu)把水轉(zhuǎn)賣給這個地域的用戶。它的主要客戶是布都、老斯戴維斯、圣哥以及豪利格拉斯等城市的供水部門。 米德羅水管站的水資源數(shù)據(jù)每立方英尺的成本（美元）可供應(yīng)量布都勞斯戴維斯圣哥豪斯格拉斯科倫坡河賽克隆河卡路里河160140190130130200220190230170150565需求25

8、41.5（百萬立方英尺）電子表格模型及求解Excel任務(wù)表米德羅水管站問題.xls例2：北方飛機(jī)制造公司Northern Airplane Company為全世界的航空公司消費(fèi)各種商務(wù)飛機(jī)。制造過程的最后一步是消費(fèi)噴氣式發(fā)動機(jī)并把它們安裝到曾經(jīng)完成的飛機(jī)框架之中去非常快的一個操作。按照公司的一些訂單合同，不久公司要交付運(yùn)用相當(dāng)多數(shù)量的飛機(jī)。所以有必要制定今后四個月的消費(fèi)方案。北方飛機(jī)制造公司問題的消費(fèi)進(jìn)度安排數(shù)據(jù)月份計(jì)劃安裝量最大產(chǎn)量單位生產(chǎn)成本（百萬美元）單位存儲成本（美元）正常時間加班時間 正常時間加班時間1234101525202030255101510101.081.111.101.1

9、31.101.121.111.15150001500015000電子表格模型及求解Excel任務(wù)表北方飛機(jī)制造公司問題.xls例3：米德爾城學(xué)區(qū)Middletown School District)興辦了第三所中學(xué)，需求為每一所學(xué)校重新劃定這個城市內(nèi)的效力區(qū)域。在初步的方案中，這個城是被分為擁有大致一樣數(shù)量人口的九個區(qū)域。學(xué)區(qū)管理者以為劃分入學(xué)區(qū)域界限的適當(dāng)目的是要使學(xué)生到學(xué)校的平均路程最短。在這個初步的方案之中，他們要確定為了實(shí)現(xiàn)這一目的每一個區(qū)域內(nèi)有多少學(xué)生要安排到每一所學(xué)校中去。米德爾學(xué)區(qū)問題的數(shù)據(jù)距離學(xué)校的距離（英里）高中學(xué)生數(shù)量123區(qū)域1234567892.21.40.51.20.

10、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電子表格模型及求解Excel任務(wù)表米德爾學(xué)區(qū)問題.xls例4：源豐公司Energetic Company)需求為新的建筑物建立起能源系統(tǒng)。建筑物的能源需求主要來自于下面三個方面1電，2熱水，3建筑物內(nèi)取暖。每天這三類用途的能源需求以一樣的單位衡量分別是10個單位、20個單位和30個單位。點(diǎn)的需求只能經(jīng)過購電來滿足。但是對于其他的兩種能源需求來

11、說，可以經(jīng)過這三個能量來源中的一個或者是幾個組合得到滿足。電子表格模型及求解Excel任務(wù)表源豐公司問題.xls特賽格公司Texago Corporation是一家設(shè)在美國外鄉(xiāng)的大型一體化石油公司。這家公司大部分的石油在公司本人的油田中消費(fèi)，所需的其他部分從中東地域進(jìn)口。公司擁有大型配送網(wǎng)絡(luò)，把石油運(yùn)送到公司的煉油廠，然后再把石油產(chǎn)品從煉油廠運(yùn)送到公司的配送中心。 特賽格公司正在繼續(xù)添加其幾種主要產(chǎn)品的市場占有率。因此管理層決議建立一個新的煉油廠來添加公司的產(chǎn)量，同時添加從中東地域進(jìn)口石油的數(shù)量。接下來所要作出的決策就是確定在什么地方建立新的煉油廠。 新煉油廠的參與對整個配送系統(tǒng)都將產(chǎn)生宏大的

12、影響,其中包括要確定從每個出發(fā)地運(yùn)輸?shù)綗捰蛷S的原油數(shù)量,以及從每一個煉油廠運(yùn)送石油到每一個配送中心的數(shù)量.因此,管理者選擇新煉油廠建立地點(diǎn)的三個關(guān)鍵要素是:1.從出發(fā)地運(yùn)送原油到一切煉油廠(包括新煉油廠的本錢;2.從一切煉油廠包括新煉油廠運(yùn)送石油制品到每一個配送中心的本錢;3.新的煉油廠的運(yùn)作本錢,包括勞動力本錢、稅賦、原料不包括原油本錢、能源本錢、保險(xiǎn)本錢，等等。資金本錢并不是一個所要關(guān)注的要素，由于任何地點(diǎn)的資金本錢幾乎都是一樣的。我們?nèi)缃竦膯栴}是要確定新的煉油廠的位置地址，使得總本錢最小。l搜集必要的數(shù)據(jù)lExcel任務(wù)表特賽格公司的數(shù)據(jù)表.docl計(jì)算新煉油廠的每個位置選擇帶來的總的原

13、油運(yùn)輸本錢;l例1假設(shè)新的煉油廠設(shè)在洛杉磯，那么有如下的運(yùn)輸問題lExcel任務(wù)表特賽格公司的選址問題.xlsl計(jì)算新煉油廠的每個位置選擇帶來的總石油制品運(yùn)輸本錢。l例2假設(shè)新的煉油廠設(shè)在洛杉磯，那么有如下的運(yùn)輸問題lExcel任務(wù)表特賽格公司的選址問題.xlsl計(jì)算特賽格公司每一個備選廠址所帶來的年變動本錢。l例3 特賽格煉油廠每一個備選廠址所帶來的年變動本錢列表如下：Excel任務(wù)表特賽格公司的數(shù)據(jù)表.doc指派問題就是給定一組義務(wù)和一組人,所需求確定的就是哪個人完成哪個義務(wù)。指派問題的根本模型，需求滿足下面的假設(shè)：1.被指派者的數(shù)量和義務(wù)的數(shù)量是一樣的；2.每一個被指派者只完成一項(xiàng)義務(wù)；

14、3.每一項(xiàng)義務(wù)只能由一個被指派者來完成；4.每一個被指派者和每一項(xiàng)義務(wù)的組合都會有一個相關(guān)的本錢；5.問題的目的是要確定怎樣進(jìn)展指派才干使得總本錢到達(dá)最小。塞爾默Sellmore)公司的問題塞爾默公司的營銷經(jīng)理將要主持召開一年一度的有營銷區(qū)域經(jīng)理以及銷售人員參與的銷售協(xié)商會議。為了更好地安排這次會議，他雇用了四個暫時工安、伊安、瓊、肖恩，每一個人擔(dān)任完成下面的一項(xiàng)義務(wù)：1.書面陳說的文字處置；2.只作口頭和書面陳說的電腦圖；3.會議資料的預(yù)備，包括書面資料的謄寫和組織；4.處置與會者的提早和當(dāng)場注冊報(bào)名。如今他需求確定要將那一項(xiàng)義務(wù)指派給那一個人。塞爾默公司問題的有關(guān)數(shù)據(jù)塞爾默公司問題的電子表

15、格模型Excel任務(wù)表塞爾默公司問題.xls臨時工每一項(xiàng)任務(wù)所需要的時間（小時）每小時工資（美元）文字處理繪圖材料準(zhǔn)備記錄安伊恩瓊肖恩3547393241455651273236254051434614121315當(dāng)問題本身是一個指派的問題,但上一節(jié)根本的指派問題模型中的一個或多個假設(shè)不成立時,稱它們?yōu)橹概蓡栴}的變形。我們思索下面一些特征：1.有一些被指派者并不能進(jìn)展某一些的人物。2.雖然每一個被指派者完成一項(xiàng)義務(wù)，但是義務(wù)比被指派者多。所以其中某些義務(wù)并沒有得到執(zhí)行。3.雖然每一項(xiàng)義務(wù)只由一個被指派者完成，但是這里被指派者比要完成的義務(wù)多。所以，其中有一些被指派者沒有指派到義務(wù)。4.每一個被

16、指派者可以同時被派給多于一個義務(wù)。5.每一項(xiàng)義務(wù)都可以有多個被指派者共同完成。例1 嬌普肖普J(rèn)ob Sho Company)購買了三種不同類型的新設(shè)備。但是在車間里卻有五個不同的地點(diǎn)可供安裝。其中某些地點(diǎn)比其他的地點(diǎn)更為需求某些設(shè)備，緣由是他們非常接近任務(wù)中心，流入和流出這些設(shè)備的任務(wù)很多。因此該問題的目的是把這些設(shè)備安裝到有效的地點(diǎn)上，使物料處置本錢到達(dá)最小。嬌普肖普公司問題中的原料處置本錢數(shù)據(jù)嬌普肖普問題的電子表格模型Excel任務(wù)表嬌普肖普問題模型.xls位置每小時成本（美元）12345機(jī)器123131541671213101420615167例2 如今我們再來看一下5.3節(jié)所講到的例子。求佳產(chǎn)品公司需求安排三個工廠來消費(fèi)四種新產(chǎn)品。我們得到的最優(yōu)結(jié)果是：第一個廠消費(fèi)第二和第三種產(chǎn)品各30單位，第二個廠只消費(fèi)第四種產(chǎn)品15單位，第三個廠消費(fèi)第一和第四種產(chǎn)品分別為20，25單位，本錢為$3260美圓。從結(jié)果中可以看出，第四種產(chǎn)品分到了兩個廠消費(fèi)，這樣會添加隱性本錢。所以，我們加進(jìn)一些新的要求：每個工廠至少完成一種產(chǎn)品，一種產(chǎn)品不能分到兩個