第六講 運輸、指派與轉(zhuǎn)運問題

1、第六講 運輸、指派與轉(zhuǎn)運問題 物流管理系 薛偉霞 主要內(nèi)容 n運輸問題：網(wǎng)絡(luò)模型與線性規(guī)劃模型 n指派問題：網(wǎng)絡(luò)模型與線性規(guī)劃模型 n轉(zhuǎn)運問題：網(wǎng)絡(luò)圖與線性規(guī)劃模型 n生產(chǎn)與庫存應(yīng)用 運輸問題 n運輸問題運輸問題經(jīng)常出現(xiàn)在計劃貨物配送和從某些供給經(jīng)常出現(xiàn)在計劃貨物配送和從某些供給 地區(qū)到達需求地區(qū)之間的服務(wù)中，特別是每個供地區(qū)到達需求地區(qū)之間的服務(wù)中，特別是每個供 給地區(qū)（起點）的貨物可獲得量是有限的，每個給地區(qū)（起點）的貨物可獲得量是有限的，每個 需求地區(qū)（目的地）的貨物需求量是已知的。需求地區(qū)（目的地）的貨物需求量是已知的。 n運輸問題中運輸問題中最常用的目標最常用的目標是要使貨物從起點到

2、目是要使貨物從起點到目 的地的運輸成本最低。的地的運輸成本最低。 案例 福斯特發(fā)電機公司的運輸問題 n從從3 3個加工廠運輸一種產(chǎn)品到個加工廠運輸一種產(chǎn)品到4 4個分銷中心。福斯特發(fā)電個分銷中心。福斯特發(fā)電 機公司在俄亥俄州的克里夫蘭、印第安納州的貝德福德機公司在俄亥俄州的克里夫蘭、印第安納州的貝德福德 和賓夕法尼亞州的約克有和賓夕法尼亞州的約克有3 3個工廠，下個工廠，下3 3個月德計劃期內(nèi)個月德計劃期內(nèi) 的這個特殊型號的發(fā)電機的生產(chǎn)能力如下：的這個特殊型號的發(fā)電機的生產(chǎn)能力如下： 起 點 工 廠 三個月生產(chǎn)能力（臺） 1 克利夫蘭 5000 2 貝德福德 6000 3 約克 2500 合

3、計 13500 案例 福斯特發(fā)電機公司的運輸問題 n公司通過坐落在波士頓、芝加哥、圣路易斯和萊克星頓公司通過坐落在波士頓、芝加哥、圣路易斯和萊克星頓 的的4 4個分銷中心來分銷這種發(fā)電機；每個分銷中心個分銷中心來分銷這種發(fā)電機；每個分銷中心3 3個月個月 的需求預(yù)測如下：的需求預(yù)測如下： 終 點 分銷中心 三個月需求預(yù)測（臺） 1 波士頓 6000 2 芝加哥 4000 3 圣路易斯 2000 4 萊克星頓 1500 合 計 13500 案例 福斯特發(fā)電機公司的運輸問題 n運輸成本如下所示：運輸成本如下所示： 終點 起點 波士頓 芝加哥圣路易斯 萊克星頓 克利夫蘭3276 貝德福德7523 約

4、克2545 n管理層想知道從每個加工廠運輸?shù)椒咒N中心的產(chǎn)品管理層想知道從每個加工廠運輸?shù)椒咒N中心的產(chǎn)品 運輸量為多少。運輸量為多少。 網(wǎng)絡(luò)圖 n圓圈表示圓圈表示節(jié)點節(jié)點，連接，連接 節(jié)點的線條表示節(jié)點的線條表示弧弧。 n每個起點和目的地都每個起點和目的地都 由節(jié)點表示，每個可由節(jié)點表示，每個可 能的運輸路線都由弧能的運輸路線都由弧 表示。表示。 n供給量供給量寫在起始節(jié)點寫在起始節(jié)點 邊上，邊上，需求量需求量寫在每寫在每 個目的地節(jié)點邊上。個目的地節(jié)點邊上。 n從起始節(jié)點到目的地從起始節(jié)點到目的地 節(jié)點之間運輸?shù)呢浳锕?jié)點之間運輸?shù)呢浳?數(shù)量表示了這個網(wǎng)絡(luò)數(shù)量表示了這個網(wǎng)絡(luò) 的的流量流量。 建立

5、線性規(guī)劃模型的步驟 n1 1、全面地了解問題；、全面地了解問題； n2 2、描述目標；、描述目標； n3 3、描述約束條件；、描述約束條件； n4 4、定義決策變量；、定義決策變量； n5 5、用決策變量寫出目標函數(shù)；、用決策變量寫出目標函數(shù)； n6 6、用決策變量寫出約束條件。、用決策變量寫出約束條件。 描述目標和約束條件 n確定使用哪些路線以及每條線路上的流量是多少確定使用哪些路線以及每條線路上的流量是多少 時，使得總的運輸成本最低。時，使得總的運輸成本最低。 n每個起點的供給能力和每個目的地的特定需求量每個起點的供給能力和每個目的地的特定需求量 是有限的。是有限的。 定義決策變量 n運用

6、雙下標決策變量。運用雙下標決策變量。 nx x11 11表示起點 表示起點1(1(克利夫蘭克利夫蘭) )運送到終點運送到終點( (波士頓波士頓) )的貨物數(shù)量，的貨物數(shù)量， x x12 12表示從起點 表示從起點1(1(克利夫蘭克利夫蘭) )運送到終點運送到終點2(2(芝加哥芝加哥) )的貨物的貨物 數(shù)量等等。數(shù)量等等。 n一般來說一般來說, ,運輸問題的決策變量有運輸問題的決策變量有m m個起點和個起點和n n個終點，如個終點，如 下下: : 用決策變量寫出目標函數(shù) n從克利夫蘭運輸貨物的成本：從克利夫蘭運輸貨物的成本： n 3 3x x11 11 2 2x x12 12 7 7x x13

7、13 + 6 + 6x x14 14 n從貝德福德運輸貨物德成本：從貝德福德運輸貨物德成本： n 7 7x x21 21 5 5x x22 22 2 2x x23 23 + 3 + 3x x24 24 n從約克運輸貨物德成本：從約克運輸貨物德成本： n 2 2x x31 31 5 5x x32 32 4 4x x33 33 + 5 + 5x x34 34 n這些公式的總和為我們提供了福斯特發(fā)電廠運輸總成本這些公式的總和為我們提供了福斯特發(fā)電廠運輸總成本 的目標函數(shù)。的目標函數(shù)。 用決策變量寫出約束條件 n每個起點的供給能力和每個目的地的特定每個起點的供給能力和每個目的地的特定 需求量是有限的。

8、需求量是有限的。 n供給約束條件和需求約束條件供給約束條件和需求約束條件 供給約束條件 n克利夫蘭的供給約束條件則為克利夫蘭的供給約束條件則為: : n x x1111x x1212x x13 + 13 + x x145000145000 n貝德福德的供給約束條件：貝德福德的供給約束條件： x x2121x x2222x x23 + 23 + x x245000245000 n約克的供給約束條件：約克的供給約束條件： n x x3131x x3232x x33 + 33 + x x342500342500 需求約束條件 n 波士頓分銷售中心需要量：波士頓分銷售中心需要量： n x x11 11

9、 + + x x21 21 + + x x31 31= 6000 = 6000 n 芝加哥分銷售中心需要量：芝加哥分銷售中心需要量： n x x12 12 + + x x22 22 + + x x32 32= 4000 = 4000 n 圣圣. .路易斯分銷售中心需要量：路易斯分銷售中心需要量： n x x13 13 + + x x23 23 + + x x33 33= 2000 = 2000 n 萊克星頓分銷售中心需要量：萊克星頓分銷售中心需要量： n x x14 14 + + x x24 24 + + x x34 34= 1500 = 1500 福斯特公司的線性規(guī)劃模型 .4,3,2, 1

10、;3,2, 1,0 1500 2000 4000 6000 2500 6000 5000 5452 3257 6723min 342414 332313 322212 312111 34333231 24232221 14131211 34333231 24232221 14131211 jix xxx xxx xxx xxx xxxx xxxx xxxx xxxx xxxx xxxxZ ij 約束條件： 目標函數(shù)： 管理科學(xué)軟件求解 n線性規(guī)劃線性規(guī)劃 n運輸問題運輸問題 問題的變化 n總供給不等于總需求總供給不等于總需求 n最大化目標函數(shù)最大化目標函數(shù) n線路容量或者線路最小量線路容量或者

11、線路最小量 n不可接受的路線不可接受的路線 總供給不等于總需求 n總供給超過總需求總供給超過總需求線性規(guī)劃模型不需要進行修改。線性規(guī)劃模型不需要進行修改。 多余的供給總量在線性規(guī)劃解決方案中表現(xiàn)為松弛。而多余的供給總量在線性規(guī)劃解決方案中表現(xiàn)為松弛。而 任何起點的松弛都可以被理解為未使用的供給或者未從任何起點的松弛都可以被理解為未使用的供給或者未從 起點運輸?shù)呢浳飻?shù)量。起點運輸?shù)呢浳飻?shù)量。 n總供給小于總需求總供給小于總需求運輸問題的線性規(guī)劃模型沒有可運輸問題的線性規(guī)劃模型沒有可 行解。增加一個虛擬起點，等于不被滿足的需求。從虛行解。增加一個虛擬起點，等于不被滿足的需求。從虛 擬起點出發(fā)的弧上

12、單位的運輸成本為零。最優(yōu)解中目的擬起點出發(fā)的弧上單位的運輸成本為零。最優(yōu)解中目的 地節(jié)點處顯示的運輸量為這個節(jié)點需求不被滿足的貨物地節(jié)點處顯示的運輸量為這個節(jié)點需求不被滿足的貨物 短缺量。短缺量。 最大化目標函數(shù) n問題問題在某些運輸問題中，目標是要找到最大化利潤在某些運輸問題中，目標是要找到最大化利潤 或者收入的解決方案?；蛘呤杖氲慕鉀Q方案。 n解決方法解決方法把單位利潤或者收入作為一個系數(shù)列入目把單位利潤或者收入作為一個系數(shù)列入目 標函數(shù)中，簡單地把最小改成最大，約束條件不變，就標函數(shù)中，簡單地把最小改成最大，約束條件不變，就 可求得線性規(guī)劃的最大值而不是最小值?？汕蟮镁€性規(guī)劃的最大值而不

13、是最小值。 路線容量和/或路線最小量 n運輸問題的線性規(guī)劃模型也能夠包含一條或者更多運輸問題的線性規(guī)劃模型也能夠包含一條或者更多 的路線容量或者最小數(shù)量問題。的路線容量或者最小數(shù)量問題。 n例如：假設(shè)在福斯特公司發(fā)電機問題中，約克例如：假設(shè)在福斯特公司發(fā)電機問題中，約克- -波波 士頓路線（起點士頓路線（起點3 3到終點到終點1 1）因為其常規(guī)的運輸模式）因為其常規(guī)的運輸模式 中有限空間的限制，只有中有限空間的限制，只有10001000單位的運輸能力。用單位的運輸能力。用 x x3131表示從約克運到波士頓的貨物數(shù)量，那么約表示從約克運到波士頓的貨物數(shù)量，那么約 克克波士頓路線容量的約束條件為

14、波士頓路線容量的約束條件為 ： x x31 311000 1000 n同樣同樣, ,路線的最小量也可以得到說明。例如：路線的最小量也可以得到說明。例如： x x22 222000 2000，這一條件保證了我們可以在最優(yōu)解中，這一條件保證了我們可以在最優(yōu)解中 繼續(xù)維持先前承諾的至少繼續(xù)維持先前承諾的至少20002000單位的貝德福德單位的貝德福德芝芝 加哥路線的交貨訂單。加哥路線的交貨訂單。 不可接受的路線 n構(gòu)建從每一個起點到終點的路線并不都是可能的。構(gòu)建從每一個起點到終點的路線并不都是可能的。 n去除網(wǎng)絡(luò)圖中相關(guān)的弧和線性規(guī)劃模型中相關(guān)的去除網(wǎng)絡(luò)圖中相關(guān)的弧和線性規(guī)劃模型中相關(guān)的 變量。變量

15、。 運輸問題的一般線性規(guī)劃模型 ni i起點下標，起點下標，i i=1=1，2 2，m m； nj j終點下標，終點下標，j j=1=1，2 2，n n； nx xij ij從起點 從起點i i到終點到終點j j的運量量；的運量量； nc cij ij從起點 從起點i i到終點到終點j j的單位運輸成本；的單位運輸成本； ns si i起點起點i i的供應(yīng)量或者生產(chǎn)能力；的供應(yīng)量或者生產(chǎn)能力； nd dj j終點終點j j的需求量。的需求量。 運輸問題的一般線性規(guī)劃模型 nm m個起點，個起點，n n個終點的運輸問題的線性規(guī)劃的一般模個終點的運輸問題的線性規(guī)劃的一般模 型如下型如下: : nj

16、mix njdx misx xcZ ij m i jij n j iij m i n j ijij ,1,10 ,1 ,1 min 1 1 11 ； 約束條件： 有容量限制的運輸問題 n如果從起點如果從起點i i到終點到終點j j之間的運輸容量為之間的運輸容量為L Lij ij，增加 ，增加 約束條件：約束條件：x xij ijL Lij ij。 。 n如果起點如果起點i i到終點到終點j j之間必須處理的運輸容量最小之間必須處理的運輸容量最小 為為M Mij ij，增加約束條件： ，增加約束條件：x xij ijM Mij ij。 。 練習(xí) n某種產(chǎn)品在某種產(chǎn)品在3 3個不同的工廠生產(chǎn)后被運

17、輸?shù)絺€不同的工廠生產(chǎn)后被運輸?shù)? 3個不個不 同的倉庫（下表顯示了每件的運輸成本），相關(guān)同的倉庫（下表顯示了每件的運輸成本），相關(guān) 信息如下表。信息如下表。 工廠工廠 倉倉 庫庫 工廠生產(chǎn)工廠生產(chǎn) 能力能力 W1 W2 W3W1 W2 W3 P1P1 P2P2 P3P3 20 16 2420 16 24 10 1010 10 8 8 12 18 1012 18 10 300300 500500 100100 倉庫需求倉庫需求200 400 300200 400 300 練習(xí) na.a.設(shè)計一個網(wǎng)絡(luò)模型來求解這個問題。設(shè)計一個網(wǎng)絡(luò)模型來求解這個問題。 nb.b.設(shè)計一個線性規(guī)劃模型，該模型的目標

18、是最小設(shè)計一個線性規(guī)劃模型，該模型的目標是最小 化總運輸成本；求解最低成本方案?；傔\輸成本；求解最低成本方案。 nc.c.假設(shè)表中的數(shù)據(jù)表示在工廠假設(shè)表中的數(shù)據(jù)表示在工廠i i生產(chǎn)出來的運到生產(chǎn)出來的運到 倉庫倉庫j j的每件產(chǎn)品的利潤，你在的每件產(chǎn)品的利潤，你在(b)(b)部分所建的模部分所建的模 型該如何變動？型該如何變動？ nd.d.如果如果W2W2總需求變?yōu)榭傂枨笞優(yōu)?00500，試改變模型。，試改變模型。 實踐海軍陸戰(zhàn)隊的調(diào)遣 n美國海軍陸戰(zhàn)隊已經(jīng)建立了一個網(wǎng)絡(luò)模型，以備在世美國海軍陸戰(zhàn)隊已經(jīng)建立了一個網(wǎng)絡(luò)模型，以備在世 界危機或者戰(zhàn)爭中用來調(diào)遣軍官。這個問題要解決的界危機或者戰(zhàn)爭

19、中用來調(diào)遣軍官。這個問題要解決的 就是盡可能快地把每個軍官指派到合適的位置（職位就是盡可能快地把每個軍官指派到合適的位置（職位 指派）。指派）。 n起點節(jié)點或者供應(yīng)節(jié)點代表現(xiàn)有的軍官，目標節(jié)點或起點節(jié)點或者供應(yīng)節(jié)點代表現(xiàn)有的軍官，目標節(jié)點或 者需求節(jié)點代表的是職位。實際執(zhí)行時有者需求節(jié)點代表的是職位。實際執(zhí)行時有4000040000個軍官個軍官 和和2500025000個職位。如果所有軍官個職位。如果所有軍官- -職位的連接弧都是可職位的連接弧都是可 行的，那么這個運輸問題就有行的，那么這個運輸問題就有1 1億條弧。為了減小問題億條弧。為了減小問題 的規(guī)模，相似條件的軍官可以匯集成一個供應(yīng)節(jié)點

20、，的規(guī)模，相似條件的軍官可以匯集成一個供應(yīng)節(jié)點， 相似的職位可以匯集成一個需求節(jié)點。用這個方法將相似的職位可以匯集成一個需求節(jié)點。用這個方法將 不可行的弧刪除，海軍陸戰(zhàn)隊在不可行的弧刪除，海軍陸戰(zhàn)隊在1010秒鐘之內(nèi)就通過一秒鐘之內(nèi)就通過一 臺個人電腦解決了包含臺個人電腦解決了包含2700027000個軍官和個軍官和1000010000個工作職個工作職 位的指派問題。位的指派問題。 實踐海軍陸戰(zhàn)隊的調(diào)遣 n結(jié)果是令人滿意的：合適級別和工作資歷的軍官結(jié)果是令人滿意的：合適級別和工作資歷的軍官 都被派遣到了需要的工作崗位上。遇到危機時，都被派遣到了需要的工作崗位上。遇到危機時， 如果能夠獲得并使用

21、這套系統(tǒng)的話，他能夠決定如果能夠獲得并使用這套系統(tǒng)的話，他能夠決定 我們將對此做出適當(dāng)?shù)姆磻?yīng)還是將去面對一場災(zāi)我們將對此做出適當(dāng)?shù)姆磻?yīng)還是將去面對一場災(zāi) 難。先前的系統(tǒng)需要難。先前的系統(tǒng)需要2 24 4天來產(chǎn)生這么一個完整天來產(chǎn)生這么一個完整 的分配計劃且這個計劃的軍官資歷和職位需求之的分配計劃且這個計劃的軍官資歷和職位需求之 間的匹配度比較低。海軍陸戰(zhàn)隊利用現(xiàn)在這個分間的匹配度比較低。海軍陸戰(zhàn)隊利用現(xiàn)在這個分 配模型提高了它在和平時期的運作能力。配模型提高了它在和平時期的運作能力。 指派問題 n典型的指派問題有：將工作分配給機器，對代理典型的指派問題有：將工作分配給機器，對代理 分配任務(wù)，將

22、銷售人員分配給銷售區(qū)域，將合同分配任務(wù)，將銷售人員分配給銷售區(qū)域，將合同 分配給投標人，等等。分配給投標人，等等。 n特征：一個代理只分配給一個任務(wù)，僅僅一個任特征：一個代理只分配給一個任務(wù)，僅僅一個任 務(wù)。務(wù)。 案例福爾市場調(diào)查公司 n公司剛剛從公司剛剛從3 3個新客戶那里獲得市場調(diào)查項目。個新客戶那里獲得市場調(diào)查項目。 公司面臨著給每一個客戶分配一個項目負責(zé)人的公司面臨著給每一個客戶分配一個項目負責(zé)人的 任務(wù)。最近，有任務(wù)。最近，有3 3個項目負責(zé)人手上沒有其他的個項目負責(zé)人手上沒有其他的 任務(wù)，可以被分配。福爾的管理層意識到完成每任務(wù)，可以被分配。福爾的管理層意識到完成每 個市場調(diào)研的時

23、間取決于項目負責(zé)人的經(jīng)驗和能個市場調(diào)研的時間取決于項目負責(zé)人的經(jīng)驗和能 力。這力。這3 3個項目具有相似的優(yōu)先順序，公司希望個項目具有相似的優(yōu)先順序，公司希望 分配的項目負責(zé)人完成這分配的項目負責(zé)人完成這3 3個項目所需的總時間個項目所需的總時間 最短。如果每個客戶只需要一個項目負責(zé)人，那最短。如果每個客戶只需要一個項目負責(zé)人，那 么怎么進行分配呢？么怎么進行分配呢？ 案例富爾市場調(diào)查公司 n為了解決這個指派問題，福爾的管理層必須首先為了解決這個指派問題，福爾的管理層必須首先 考慮所有可能的負責(zé)人考慮所有可能的負責(zé)人- -客戶的分配方法，然后客戶的分配方法，然后 預(yù)測相對應(yīng)的完成項目所需的時間

24、。預(yù)測相對應(yīng)的完成項目所需的時間。 網(wǎng)絡(luò)模型 線性規(guī)劃模型 其他情況 備分配給客戶如果項目負責(zé)人 0 1ji xij 這里這里i i1 1，2 2，3 3；j j1 1，2 2，3 3。 決策變量決策變量 線性規(guī)劃模型目標函數(shù) n使用表使用表7 73 3中的符號和完成時間數(shù)據(jù)，我們得出了完成中的符號和完成時間數(shù)據(jù)，我們得出了完成 時間表達式：時間表達式： n特瑞完成配置所用的總天數(shù)：特瑞完成配置所用的總天數(shù)： 1010 x x11 11+15 +15x x12 12+9 +9x x13 13 n卡爾完成配置所用的總天數(shù)：卡爾完成配置所用的總天數(shù)： 9 9x x21 21+18 +18x x22

25、 22+5 +5x x23 23 n邁克孟德完成配置所用的總天數(shù)：邁克孟德完成配置所用的總天數(shù)： 6 6x x31 31+14 +14x x32 32+3 +3x x33 33 目標函數(shù)：目標函數(shù)： Min Z=10 x11 11+15x1212+9x1313+9x2121+18x2222+5x2323+6x3131+ 14x32 32+3x3333 線性規(guī)劃模型約束條件 n保證每個負責(zé)人能夠被至多分配給一個客戶且每個客戶保證每個負責(zé)人能夠被至多分配給一個客戶且每個客戶 必須有一個分配過來的負責(zé)人。必須有一個分配過來的負責(zé)人。 n x x11 11+ +x x1212+ +x x13131 1

26、 對特瑞的指派對特瑞的指派 n x x21 21+ +x x2222+ +x x23231 1 對卡爾的指派對卡爾的指派 n x x31 31+ +x x3232+ +x x33331 1 對邁克孟德的指派對邁克孟德的指派 n x x11 11+ +x x2121+ +x x3131 1 1 客戶客戶1 1 n x x12 12+ +x x2222+ +x x3232 1 1 客戶客戶2 2 n x x13 13+ +x x2323+ +x x3333 1 1 客戶客戶3 3 福爾公司指派問題的線性規(guī)劃模型福爾公司指派問題的線性規(guī)劃模型 31 ,3110 1 1 1 1 1 1 31465 1

27、8991510Zmin 332313 322212 312111 333231 232221 131211 33323123 2221131211 jix xxx xxx xxx xxx xxx xxx xxxx xxxxx ij ；或 管理科學(xué)軟件求解結(jié)果 Objective Function Value= 26.000 Variable Value Reduced Costs x11 0.000 0.000 x12 1.000 0.000 x13 0.000 3.000 x21 0.000 0.000 x22 0.000 4.000 x23 1.000 0.000 x31 1.000 0.

28、000 x32 0.000 3.000 x33 0.000 1.000 福爾公司問題的最優(yōu)項目負責(zé)人指派 Assignment模塊求解結(jié)果 問題的變化 n總的代理（供給）數(shù)不等于總的任務(wù)（需求）數(shù)?？偟拇恚ü┙o）數(shù)不等于總的任務(wù)（需求）數(shù)。 n目標函數(shù)最大化。目標函數(shù)最大化。 n不可接受的分配。不可接受的分配。 指派問題的一般線性規(guī)劃模型 一般指派問題包括一般指派問題包括m m個代理和個代理和n n項任務(wù)。項任務(wù)。 令令x xij ij=1 =1或者或者0 0來表示代理來表示代理i i是否分配給任務(wù)是否分配給任務(wù)j j，如果，如果c cij ij表 表 示把代理示把代理i i分配給任務(wù)分配給

29、任務(wù)j j所花的成本，一般指派模型如下：所花的成本，一般指派模型如下： njmix njx mix xcZ ij m i ij n j ij m i n j ijij ,1,10 ,11 ,11 min 1 1 11 ； 任務(wù) 代理 約束條件： 多種指派 n假設(shè)：福爾公司問題中的特瑞能被指派給兩個假設(shè)：福爾公司問題中的特瑞能被指派給兩個 客戶，增加約束條件：客戶，增加約束條件： nx x11 11+x +x12 12+x +x13 13 2 2 n一般情況下，如果一般情況下，如果a ai i表示代表表示代表i i能夠被指派的任能夠被指派的任 務(wù)的最高上限，我們可以把代理約束條件寫成務(wù)的最高上限

30、，我們可以把代理約束條件寫成 如下形式：如下形式： miax n j iij ,1 1 實踐Herry International nHerryHerry International International與田納西州等多方客戶簽與田納西州等多方客戶簽 訂了各種建設(shè)項目的合同，包括高等教育設(shè)施、訂了各種建設(shè)項目的合同，包括高等教育設(shè)施、 旅館和停車場。在任何一個時間點上，旅館和停車場。在任何一個時間點上， HerryHerry 都有都有100100多個正在進行的項目。每個項目必須單多個正在進行的項目。每個項目必須單 獨指派一個主管。如果獨指派一個主管。如果7 7個主管可以指派的話，個主管可以

31、指派的話， 有多于有多于7007007 7100100種可能的指派。在外來顧問種可能的指派。在外來顧問 的協(xié)助下，的協(xié)助下， HerryHerry International International設(shè)計出了一個設(shè)計出了一個 給項目指派建筑主管的數(shù)學(xué)模型。給項目指派建筑主管的數(shù)學(xué)模型。 實踐Herry International nHerryHerry 設(shè)計出的指派模型對于每個主管和項目組設(shè)計出的指派模型對于每個主管和項目組 合使用合使用0/10/1決策變量，就如前邊討論過的指派問決策變量，就如前邊討論過的指派問 題一樣。指派主管的目標是為了平衡每個主管之題一樣。指派主管的目標是為了平衡每個

32、主管之 間的工作負擔(dān)，在同一個時間內(nèi)最小化從主管家間的工作負擔(dān)，在同一個時間內(nèi)最小化從主管家 到建筑項目的工作地點之間的交通成本。由此得到建筑項目的工作地點之間的交通成本。由此得 出了關(guān)于每個可能的指派目標函數(shù)系數(shù)：將項目出了關(guān)于每個可能的指派目標函數(shù)系數(shù)：將項目 強度（一個關(guān)于項目預(yù)算大小的函數(shù)）和從主管強度（一個關(guān)于項目預(yù)算大小的函數(shù)）和從主管 人員的家到建筑工地的交通距離組合起來。目標人員的家到建筑工地的交通距離組合起來。目標 函數(shù)要求所有的指派變量的系數(shù)總和最小。函數(shù)要求所有的指派變量的系數(shù)總和最小。 實踐Herry International n由于建筑項目多于主管人數(shù)，所以必須考慮

33、對包含了由于建筑項目多于主管人數(shù)，所以必須考慮對包含了 多種指派的標準指派問題進行修改。有兩組約束條件，多種指派的標準指派問題進行修改。有兩組約束條件， 一組要求每個項目有一個并只能有一個主管；另一組一組要求每個項目有一個并只能有一個主管；另一組 通過限制所有被指派項目的總的可接受強度來限制每通過限制所有被指派項目的總的可接受強度來限制每 個主管接到的指派的任務(wù)量。個主管接到的指派的任務(wù)量。 nHerryHerry International International實行了這個指派模型，產(chǎn)生了實行了這個指派模型，產(chǎn)生了 很好的效果。據(jù)副總裁很好的效果。據(jù)副總裁Emory F. ReddenE

34、mory F. Redden稱：稱：“最優(yōu)最優(yōu) 化模型對于我們指派主管到項目很有幫助，我們對于化模型對于我們指派主管到項目很有幫助，我們對于 納什維爾分部的指派就很滿意，我們希望將這種模型納什維爾分部的指派就很滿意，我們希望將這種模型 應(yīng)用于我們的亞特蘭大及應(yīng)用于我們的亞特蘭大及HerryHerry集團的每一個分部。集團的每一個分部?！?練習(xí) n美國電纜公司利用包括美國電纜公司利用包括5 5個分銷中心、個分銷中心、8 8個客戶區(qū)域的分銷系統(tǒng)個客戶區(qū)域的分銷系統(tǒng) 分銷產(chǎn)品。配給每個客戶區(qū)域一個專門的資源供應(yīng)商，且其所分銷產(chǎn)品。配給每個客戶區(qū)域一個專門的資源供應(yīng)商，且其所 有電纜產(chǎn)品都來自同一分銷

35、中心。為了能平衡分銷中心的客戶有電纜產(chǎn)品都來自同一分銷中心。為了能平衡分銷中心的客戶 需求和雇員的工作量，公司負責(zé)物流的副總裁特別指明一個分需求和雇員的工作量，公司負責(zé)物流的副總裁特別指明一個分 銷中心最多負責(zé)銷中心最多負責(zé)3 3個客戶區(qū)。下面的表格就是這個客戶區(qū)。下面的表格就是這5 5個分銷中心以個分銷中心以 及每個客戶區(qū)的供給成本（單位：及每個客戶區(qū)的供給成本（單位：10001000美元）：美元）： n1 1、設(shè)計一個表述該問題的網(wǎng)絡(luò)圖。、設(shè)計一個表述該問題的網(wǎng)絡(luò)圖。 n2 2、構(gòu)建一個該問題的線性規(guī)劃模型，并求解得出使總成本最、構(gòu)建一個該問題的線性規(guī)劃模型，并求解得出使總成本最 小的最優(yōu)

36、解。小的最優(yōu)解。 n3 3、如果有，哪一分銷中心沒有分派任務(wù)？、如果有，哪一分銷中心沒有分派任務(wù)？ n4 4、假設(shè)每個分銷中心最多只能負責(zé)兩個客戶區(qū)，那么這個限、假設(shè)每個分銷中心最多只能負責(zé)兩個客戶區(qū)，那么這個限 制條件將如何改變指派和客戶區(qū)的供給成本？制條件將如何改變指派和客戶區(qū)的供給成本？ 練習(xí) 分銷中心分銷中心 客戶區(qū)客戶區(qū) 洛杉磯洛杉磯芝加哥芝加哥哥倫比亞哥倫比亞亞特蘭大亞特蘭大紐約紐約堪薩斯堪薩斯丹佛丹佛達拉斯達拉斯 普萊諾普萊諾7047225398212713 納什維爾納什維爾7538195890344026 弗拉各斯塔夫弗拉各斯塔夫15783782111402932 斯普林菲爾德

37、斯普林菲爾德602383982363245 博爾德博爾德4540297586251137 轉(zhuǎn)運問題 n運輸問題的擴展，其中中間節(jié)點代表轉(zhuǎn)運節(jié)點，運輸問題的擴展，其中中間節(jié)點代表轉(zhuǎn)運節(jié)點， 加入這個節(jié)點的目的是指代地點位置，例如倉庫。加入這個節(jié)點的目的是指代地點位置，例如倉庫。 案例瑞恩電子公司的轉(zhuǎn)運問題 n瑞恩電子是一家電子公司，其生產(chǎn)線分別位于丹佛和亞瑞恩電子是一家電子公司，其生產(chǎn)線分別位于丹佛和亞 特蘭大，在每條生產(chǎn)線上生產(chǎn)出來的商品都可以被運送特蘭大，在每條生產(chǎn)線上生產(chǎn)出來的商品都可以被運送 到公司在堪薩斯城或者是路易斯維爾地區(qū)的倉庫中，公到公司在堪薩斯城或者是路易斯維爾地區(qū)的倉庫中，公

38、 司把這些地區(qū)的倉庫中的商品發(fā)給底特律、邁阿密、達司把這些地區(qū)的倉庫中的商品發(fā)給底特律、邁阿密、達 拉斯和新奧爾良的零售商。拉斯和新奧爾良的零售商。 600 400 200300350150 6 1 2 4 3 8 7 6 5 工廠開工廠開 始節(jié)點始節(jié)點 倉庫轉(zhuǎn)倉庫轉(zhuǎn) 載節(jié)點載節(jié)點 零售商零售商 丹佛丹佛 600 亞特蘭亞特蘭 大大400 底特律底特律 200 邁阿密邁阿密 150 達拉斯達拉斯 350 新奧爾新奧爾 良良300 堪薩斯城堪薩斯城 路易斯維爾路易斯維爾 2 3 3 1 2 6 3 5 6 4 4 網(wǎng)絡(luò)圖 線性規(guī)劃模型 n決策變量：令決策變量：令xij代表從節(jié)點代表從節(jié)點i到節(jié)點

39、到節(jié)點j運輸?shù)募?shù)。運輸?shù)募?shù)。 n目標函數(shù)：運輸線路的總運輸成本最小目標函數(shù)：運輸線路的總運輸成本最小 n起點節(jié)點約束：輸出的總量減去輸入的總量必須小于起點節(jié)點約束：輸出的總量減去輸入的總量必須小于 或等于該節(jié)點的商品供給量或等于該節(jié)點的商品供給量 n終點節(jié)點約束：輸入的總量減去輸出的總量必須等于終點節(jié)點約束：輸入的總量減去輸出的總量必須等于 該節(jié)點的需求。該節(jié)點的需求。 n轉(zhuǎn)運節(jié)點約束：輸出的總量必須等于輸入的總量。轉(zhuǎn)運節(jié)點約束：輸出的總量必須等于輸入的總量。 瑞恩電子問題的線性規(guī)劃模型 。和對于所有的，所有節(jié)點約束： 終點節(jié)點約束： 轉(zhuǎn)運節(jié)點約束： 起點節(jié)點約束： jix xx xx x

40、x xx xxxxxx xxxxxx xx xx xxxxxx xxxxxx ij 0 300 350 150 200 0 0 400 600 564463 621332Zmin 4838 4737 4636 4535 484746452314 383736352313 2423 1413 484746453837 363524231413 管理科學(xué)軟件求解結(jié)果 Objective Function Value = 5200.000 Variable Value Reduced Costs x13 550.000 0.000 x14 50.000 0.000 x23 0.000 3.000 x

41、24 400.000 0.000 x35 200.000 0.000 x36 0.000 1.000 x37 350.000 0.000 x38 0.000 0.000 x45 0.000 3.000 x46 150.000 0.000 x47 0.000 4.000 x48 300.000 0.000 瑞恩電子轉(zhuǎn)運問題的最優(yōu)解 更一般的轉(zhuǎn)運問題 n假設(shè)可以直接從亞特蘭大運輸商品到新奧爾良，假設(shè)可以直接從亞特蘭大運輸商品到新奧爾良， 單位運輸費用為單位運輸費用為4 4美元，且從達拉斯運到新奧爾美元，且從達拉斯運到新奧爾 良的單位運費為良的單位運費為1 1美元。美元。 1 2 4 3 8 7 6

42、 5 工廠開工廠開 始節(jié)點始節(jié)點 倉庫轉(zhuǎn)倉庫轉(zhuǎn) 載節(jié)點載節(jié)點 丹佛丹佛 600 亞特蘭亞特蘭 大大400 底特律底特律 200 邁阿密邁阿密 150 達拉斯達拉斯 350 新奧爾新奧爾 良良300 堪薩斯城堪薩斯城 路易斯維爾路易斯維爾 2 3 3 1 2 6 3 6 5 6 4 4 4 1 線性規(guī)劃模型 。和對于所有的，所有節(jié)點約束： 終點節(jié)點約束： 轉(zhuǎn)運節(jié)點約束： 起點節(jié)點約束： jix xxxx xxx xx xx xxxxxx xxxxxx xxx xx xxxxxxx xxxxxxx ij 0 300 350 150 200 0 0 400 600 1456446 3621332Zm

43、in 78284838 784737 4636 4535 484746452314 383736352313 282423 1413 78284847464538 37363524231413 軟件求解結(jié)果 問題的變化 n總供給不等于總需求總供給不等于總需求 n最大化目標函數(shù)最大化目標函數(shù) n路線容量或者路線最小量（有容量限制的轉(zhuǎn)運問題）路線容量或者路線最小量（有容量限制的轉(zhuǎn)運問題） n不可接受的路線不可接受的路線 轉(zhuǎn)運問題的一般線性規(guī)劃模型 jix dxx xx isxx xcZ ij jijij ijij iijij ijij 和對所有的 終點節(jié)點 轉(zhuǎn)載節(jié)點 起點節(jié)點 約束條件： 運入弧線運出弧線 運出弧線運入弧線 運出弧線運入弧線 所有弧線 0 0 min 這里，這里，x xij ij表示從節(jié)點 表示從節(jié)點i i到節(jié)點到節(jié)點j j的運量；的運量；c cij ij表示從節(jié)點 表示從節(jié)點i i到節(jié)點到節(jié)點j j 的單位運價；的單位運價；s si i表示起點節(jié)點表示起點節(jié)點i i的供給量；的供給量；d dj j表示終點節(jié)點表示終點節(jié)點j j的需的需 求量。求量。 實踐 寶潔公司在產(chǎn)品供應(yīng)上的啟發(fā)式探索 n幾年前，寶潔公司開始了一個重大戰(zhàn)略計劃，稱為北美幾年前，寶潔公司開始了一個重大戰(zhàn)略計劃，稱為北美 產(chǎn)