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

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

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

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

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

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

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

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

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 約束條件： 目標(biāo)函數(shù)： 管理科學(xué)軟件求解 n線性規(guī)劃線性規(guī)劃 n運(yùn)輸問題運(yùn)輸問題 問題的變化 n總供給不等于總需求總供給不等于總需求 n最大化目標(biāo)函數(shù)最大化目標(biāo)函數(shù) n線路容量或者線路最小量線路容量或者

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

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

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

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

15、。 運(yùn)輸問題的一般線性規(guī)劃模型 ni i起點(diǎn)下標(biāo)，起點(diǎn)下標(biāo)，i i=1=1，2 2，m m； nj j終點(diǎn)下標(biāo)，終點(diǎn)下標(biāo)，j j=1=1，2 2，n n； nx xij ij從起點(diǎn) 從起點(diǎn)i i到終點(diǎn)到終點(diǎn)j j的運(yùn)量量；的運(yùn)量量； nc cij ij從起點(diǎn) 從起點(diǎn)i i到終點(diǎn)到終點(diǎn)j j的單位運(yùn)輸成本；的單位運(yùn)輸成本； ns si i起點(diǎn)起點(diǎn)i i的供應(yīng)量或者生產(chǎn)能力；的供應(yīng)量或者生產(chǎn)能力； nd dj j終點(diǎn)終點(diǎn)j j的需求量。的需求量。 運(yùn)輸問題的一般線性規(guī)劃模型 nm m個(gè)起點(diǎn)，個(gè)起點(diǎn)，n n個(gè)終點(diǎn)的運(yùn)輸問題的線性規(guī)劃的一般模個(gè)終點(diǎn)的運(yùn)輸問題的線性規(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 ； 約束條件： 有容量限制的運(yùn)輸問題 n如果從起點(diǎn)如果從起點(diǎn)i i到終點(diǎn)到終點(diǎn)j j之間的運(yùn)輸容量為之間的運(yùn)輸容量為L(zhǎng) Lij ij，增加 ，增加 約束條件：約束條件：x xij ijL Lij ij。 。 n如果起點(diǎn)如果起點(diǎn)i i到終點(diǎn)到終點(diǎn)j j之間必須處理的運(yùn)輸容量最小之間必須處理的運(yùn)輸容量最小 為為M Mij ij，增加約束條件： ，增加約束條件：x xij ijM Mij ij。 。 練習(xí) n某種產(chǎn)品在某種產(chǎn)品在3 3個(gè)不同的工廠生產(chǎn)后被運(yùn)

17、輸?shù)絺€(gè)不同的工廠生產(chǎn)后被運(yùn)輸?shù)? 3個(gè)不個(gè)不 同的倉庫（下表顯示了每件的運(yùn)輸成本），相關(guān)同的倉庫（下表顯示了每件的運(yù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è)計(jì)一個(gè)網(wǎng)絡(luò)模型來求解這個(gè)問題。設(shè)計(jì)一個(gè)網(wǎng)絡(luò)模型來求解這個(gè)問題。 nb.b.設(shè)計(jì)一個(gè)線性規(guī)劃模型，該模型的目標(biāo)

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

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

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

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

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

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

24、。預(yù)測(cè)相對(duì)應(yīng)的完成項(xiàng)目所需的時(shí)間。 網(wǎng)絡(luò)模型 線性規(guī)劃模型 其他情況 備分配給客戶如果項(xiàng)目負(fù)責(zé)人 0 1ji xij 這里這里i i1 1，2 2，3 3；j j1 1，2 2，3 3。 決策變量決策變量 線性規(guī)劃模型目標(biāo)函數(shù) n使用表使用表7 73 3中的符號(hào)和完成時(shí)間數(shù)據(jù)，我們得出了完成中的符號(hào)和完成時(shí)間數(shù)據(jù)，我們得出了完成 時(shí)間表達(dá)式：時(shí)間表達(dá)式： 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 目標(biāo)函數(shù)：目標(biāo)函數(shù)： Min Z=10 x11 11+15x1212+9x1313+9x2121+18x2222+5x2323+6x3131+ 14x32 32+3x3333 線性規(guī)劃模型約束條件 n保證每個(gè)負(fù)責(zé)人能夠被至多分配給一個(gè)客戶且每個(gè)客戶保證每個(gè)負(fù)責(zé)人能夠被至多分配給一個(gè)客戶且每個(gè)客戶 必須有一個(gè)分配過來的負(fù)責(zé)人。必須有一個(gè)分配過來的負(fù)責(zé)人。 n x x11 11+ +x x1212+ +x x13131 1

26、 對(duì)特瑞的指派對(duì)特瑞的指派 n x x21 21+ +x x2222+ +x x23231 1 對(duì)卡爾的指派對(duì)卡爾的指派 n x x31 31+ +x x3232+ +x x33331 1 對(duì)邁克孟德的指派對(duì)邁克孟德的指派 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)項(xiàng)目負(fù)責(zé)人指派 Assignment模塊求解結(jié)果 問題的變化 n總的代理（供給）數(shù)不等于總的任務(wù)（需求）數(shù)?？偟拇恚ü┙o）數(shù)不等于總的任務(wù)（需求）數(shù)。 n目標(biāo)函數(shù)最大化。目標(biāo)函數(shù)最大化。 n不可接受的分配。不可接受的分配。 指派問題的一般線性規(guī)劃模型 一般指派問題包括一般指派問題包括m m個(gè)代理和個(gè)代理和n n項(xiàng)任務(wù)。項(xiàng)任務(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è)：福爾公司問題中的特瑞能被指派給兩個(gè)假設(shè)：福爾公司問題中的特瑞能被指派給兩個(gè) 客戶，增加約束條件：客戶，增加約束條件： 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 實(shí)踐Herry International nHerryHerry International International與田納西州等多方客戶簽與田納西州等多方客戶簽 訂了各種建設(shè)項(xiàng)目的合同，包括高等教育設(shè)施、訂了各種建設(shè)項(xiàng)目的合同，包括高等教育設(shè)施、 旅館和停車場(chǎng)。在任何一個(gè)時(shí)間點(diǎn)上，旅館和停車場(chǎng)。在任何一個(gè)時(shí)間點(diǎn)上， HerryHerry 都有都有100100多個(gè)正在進(jìn)行的項(xiàng)目。每個(gè)項(xiàng)目必須單多個(gè)正在進(jìn)行的項(xiàng)目。每個(gè)項(xiàng)目必須單 獨(dú)指派一個(gè)主管。如果獨(dú)指派一個(gè)主管。如果7 7個(gè)主管可以指派的話，個(gè)主管可以

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

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

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

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

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

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

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

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

39、到節(jié)點(diǎn)j運(yùn)輸?shù)募?shù)。運(yùn)輸?shù)募?shù)。 n目標(biāo)函數(shù)：運(yùn)輸線路的總運(yùn)輸成本最小目標(biāo)函數(shù)：運(yùn)輸線路的總運(yùn)輸成本最小 n起點(diǎn)節(jié)點(diǎn)約束：輸出的總量減去輸入的總量必須小于起點(diǎn)節(jié)點(diǎn)約束：輸出的總量減去輸入的總量必須小于 或等于該節(jié)點(diǎn)的商品供給量或等于該節(jié)點(diǎn)的商品供給量 n終點(diǎn)節(jié)點(diǎn)約束：輸入的總量減去輸出的總量必須等于終點(diǎn)節(jié)點(diǎn)約束：輸入的總量減去輸出的總量必須等于 該節(jié)點(diǎn)的需求。該節(jié)點(diǎn)的需求。 n轉(zhuǎn)運(yùn)節(jié)點(diǎn)約束：輸出的總量必須等于輸入的總量。轉(zhuǎn)運(yùn)節(jié)點(diǎn)約束：輸出的總量必須等于輸入的總量。 瑞恩電子問題的線性規(guī)劃模型 。和對(duì)于所有的，所有節(jié)點(diǎn)約束： 終點(diǎn)節(jié)點(diǎn)約束： 轉(zhuǎn)運(yùn)節(jié)點(diǎn)約束： 起點(diǎn)節(jié)點(diǎn)約束： 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ùn)問題的最優(yōu)解 更一般的轉(zhuǎn)運(yùn)問題 n假設(shè)可以直接從亞特蘭大運(yùn)輸商品到新奧爾良，假設(shè)可以直接從亞特蘭大運(yùn)輸商品到新奧爾良， 單位運(yùn)輸費(fèi)用為單位運(yùn)輸費(fèi)用為4 4美元，且從達(dá)拉斯運(yùn)到新奧爾美元，且從達(dá)拉斯運(yùn)到新奧爾 良的單位運(yùn)費(fèi)為良的單位運(yùn)費(fèi)為1 1美元。美元。 1 2 4 3 8 7 6

42、 5 工廠開工廠開 始節(jié)點(diǎn)始節(jié)點(diǎn) 倉庫轉(zhuǎn)倉庫轉(zhuǎn) 載節(jié)點(diǎn)載節(jié)點(diǎn) 丹佛丹佛 600 亞特蘭亞特蘭 大大400 底特律底特律 200 邁阿密邁阿密 150 達(dá)拉斯達(dá)拉斯 350 新奧爾新奧爾 良良300 堪薩斯城堪薩斯城 路易斯維爾路易斯維爾 2 3 3 1 2 6 3 6 5 6 4 4 4 1 線性規(guī)劃模型 。和對(duì)于所有的，所有節(jié)點(diǎn)約束： 終點(diǎn)節(jié)點(diǎn)約束： 轉(zhuǎn)運(yùn)節(jié)點(diǎn)約束： 起點(diǎn)節(jié)點(diǎn)約束： 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最大化目標(biāo)函數(shù)最大化目標(biāo)函數(shù) n路線容量或者路線最小量（有容量限制的轉(zhuǎn)運(yùn)問題）路線容量或者路線最小量（有容量限制的轉(zhuǎn)運(yùn)問題） n不可接受的路線不可接受的路線 轉(zhuǎn)運(yùn)問題的一般線性規(guī)劃模型 jix dxx xx isxx xcZ ij jijij ijij iijij ijij 和對(duì)所有的 終點(diǎn)節(jié)點(diǎn) 轉(zhuǎn)載節(jié)點(diǎn) 起點(diǎn)節(jié)點(diǎn) 約束條件： 運(yùn)入弧線運(yùn)出弧線 運(yùn)出弧線運(yùn)入弧線 運(yùn)出弧線運(yùn)入弧線 所有弧線 0 0 min 這里，這里，x xij ij表示從節(jié)點(diǎn) 表示從節(jié)點(diǎn)i i到節(jié)點(diǎn)到節(jié)點(diǎn)j j的運(yùn)量；的運(yùn)量；c cij ij表示從節(jié)點(diǎn) 表示從節(jié)點(diǎn)i i到節(jié)點(diǎn)到節(jié)點(diǎn)j j 的單位運(yùn)價(jià)；的單位運(yùn)價(jià)；s si i表示起點(diǎn)節(jié)點(diǎn)表示起點(diǎn)節(jié)點(diǎn)i i的供給量；的供給量；d dj j表示終點(diǎn)節(jié)點(diǎn)表示終點(diǎn)節(jié)點(diǎn)j j的需的需 求量。求量。 實(shí)踐 寶潔公司在產(chǎn)品供應(yīng)上的啟發(fā)式探索 n幾年前，寶潔公司開始了一個(gè)重大戰(zhàn)略計(jì)劃，稱為北美幾年前，寶潔公司開始了一個(gè)重大戰(zhàn)略計(jì)劃，稱為北美 產(chǎn)