運(yùn)籌學(xué)-5(運(yùn)輸問(wèn)題)

1、運(yùn)籌學(xué)基礎(chǔ)教程運(yùn)籌學(xué)基礎(chǔ)教程5 黃桐城黃桐城 主編主編 趙弘志趙弘志 改編改編 主講主講 第五章第五章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題l主要內(nèi)容主要內(nèi)容你們手中教材你們手中教材p-091第第4章章 運(yùn) 輸 問(wèn) 題 及 其 數(shù) 學(xué) 模 型運(yùn) 輸 問(wèn) 題 及 其 數(shù) 學(xué) 模 型 表 上 作 業(yè) 法表 上 作 業(yè) 法 產(chǎn) 銷 不 平 衡 的 運(yùn) 輸 問(wèn) 題產(chǎn) 銷 不 平 衡 的 運(yùn) 輸 問(wèn) 題4.1 4.1 運(yùn)運(yùn) 輸輸 問(wèn)問(wèn) 題及其數(shù)學(xué)模型題及其數(shù)學(xué)模型 在物流活動(dòng)中，經(jīng)常會(huì)有大宗貨物的調(diào)運(yùn)問(wèn)題。在物流活動(dòng)中，經(jīng)常會(huì)有大宗貨物的調(diào)運(yùn)問(wèn)題。如何編制調(diào)運(yùn)方案，把貨物從供應(yīng)地運(yùn)到各消費(fèi)如何編制調(diào)運(yùn)方案，把貨物從供應(yīng)地運(yùn)

2、到各消費(fèi)地，而總運(yùn)費(fèi)最小，就是我們要解決的問(wèn)題。一般地，而總運(yùn)費(fèi)最小，就是我們要解決的問(wèn)題。一般說(shuō)來(lái)，這種物流中的運(yùn)輸問(wèn)題可以用以下數(shù)學(xué)語(yǔ)言說(shuō)來(lái)，這種物流中的運(yùn)輸問(wèn)題可以用以下數(shù)學(xué)語(yǔ)言描述。描述。 已知有已知有 m m 個(gè)供應(yīng)地點(diǎn)個(gè)供應(yīng)地點(diǎn) A Ai i, , i i=1,2,=1,2,m；可供應(yīng)；可供應(yīng)某種物資，其供應(yīng)量分別為某種物資，其供應(yīng)量分別為a ai i, , i i=1,2,=1,2,m； 以有以有n n個(gè)銷地個(gè)銷地 B Bj j, ,j j=1,2,=1,2,n; 其需要量分別為其需要量分別為 b bj j, , j j=1,2,=1,2,n; 從從A Ai i到到B Bj j運(yùn)

3、輸單位物資的運(yùn)價(jià)運(yùn)輸單位物資的運(yùn)價(jià)( (單價(jià)單價(jià)) )為為c cijij，這些數(shù)據(jù)，這些數(shù)據(jù)可以匯總到產(chǎn)銷平衡表和單位運(yùn)價(jià)表中。若用可以匯總到產(chǎn)銷平衡表和單位運(yùn)價(jià)表中。若用x xijij 表示從表示從A Ai i到到B Bj j 的運(yùn)量，那么在供需平衡的條件下，的運(yùn)量，那么在供需平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可求解以下數(shù)學(xué)模要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可求解以下數(shù)學(xué)模型：型： 0,2, 1,2, 1,min1111 ijnjiijmijijminiijijxmiaxnjbxStxcz運(yùn)運(yùn) 輸輸 表表運(yùn)輸價(jià)格表運(yùn)輸價(jià)格表 銷地銷地產(chǎn)地產(chǎn)地B1B2Bn產(chǎn)量產(chǎn)量 A1C11C12C1n

4、a1 A2C21C22C2n a2 AmCm1Cm2Cmn am 銷量銷量b1b2bn4.2. 4.2. 表上作業(yè)法表上作業(yè)法 表上作業(yè)法實(shí)質(zhì)上是單純形法。下面我們結(jié)合例表上作業(yè)法實(shí)質(zhì)上是單純形法。下面我們結(jié)合例題來(lái)解析表上作業(yè)法。題來(lái)解析表上作業(yè)法。 例例4 4 某物流公司有三個(gè)倉(cāng)庫(kù)，每天向四個(gè)超市某物流公司有三個(gè)倉(cāng)庫(kù)，每天向四個(gè)超市供應(yīng)某種貨物。已知三個(gè)倉(cāng)庫(kù)供應(yīng)某種貨物。已知三個(gè)倉(cāng)庫(kù)A A1 1，A A2 2和和A A3 3的此貨物的此貨物儲(chǔ)藏量分別為儲(chǔ)藏量分別為7 7箱、箱、4 4箱和箱和9 9箱。該物流公司把這些貨箱。該物流公司把這些貨物分別送往物分別送往B B1 1、B B2 2、B

5、 B3 3和和B B4 4四個(gè)超市，各超市每日銷四個(gè)超市，各超市每日銷量分別為量分別為3 3箱、箱、6 6箱、箱、5 5箱和箱和6 6箱。試用表上作業(yè)法求箱。試用表上作業(yè)法求解滿足供需要求的最佳調(diào)運(yùn)方案，使總運(yùn)費(fèi)最少。解滿足供需要求的最佳調(diào)運(yùn)方案，使總運(yùn)費(fèi)最少。解：步驟如下：解：步驟如下： 第一步：做出單位運(yùn)價(jià)表與供銷平衡表：第一步：做出單位運(yùn)價(jià)表與供銷平衡表： 第二步：第二步：求初始解。初始解一般可通過(guò)最小元求初始解。初始解一般可通過(guò)最小元素法和伏格爾法兩種方法得到。素法和伏格爾法兩種方法得到。 超市超市倉(cāng)庫(kù)倉(cāng)庫(kù)B1B2B3B4儲(chǔ)量?jī)?chǔ)量A13113107A219284A3741059銷量銷量

6、3656 20 204.2.1 確定初始基本可行解確定初始基本可行解 1 1最小元素法最小元素法 p095 最小元素法的基本思想是就近配送，即從單位運(yùn)價(jià)表中最小元素法的基本思想是就近配送，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開(kāi)始確定供需關(guān)系，然后次小，一直到給出初始最小的運(yùn)價(jià)開(kāi)始確定供需關(guān)系，然后次小，一直到給出初始可行解為止?？尚薪鉃橹?。 超市超市倉(cāng)庫(kù)倉(cāng)庫(kù)B1B2B3B4儲(chǔ)量?jī)?chǔ)量A13113107A21（3）9284-3=1A3741059銷量銷量3-3=0656 20 20繼續(xù)繼續(xù)B1B2B3B4儲(chǔ)量?jī)?chǔ)量A13113107A21（3）92（1）81-1=0A3741059銷量銷量065-1=46B1

7、B2B3B4儲(chǔ)量?jī)?chǔ)量A13113（4）107-4=3A21（3）92 （1）80A3741059銷量銷量064-4=06繼續(xù)繼續(xù)B1B2B3B4儲(chǔ)量?jī)?chǔ)量A13113（4）103A21（3）92 （1）80A374（6）1059-6=3銷量銷量06-6=006B1B2B3B4儲(chǔ)量?jī)?chǔ)量A13113（4）10（3）3A21（3）92 （1）80A374 （6）105（3）3銷量銷量0006-6=0最后，得到運(yùn)輸分配表。最后，得到運(yùn)輸分配表。（分配結(jié)果一定（分配結(jié)果一定= n + m - 1 個(gè)）個(gè)）它的運(yùn)輸總成本：它的運(yùn)輸總成本： 31+ 64 + 43 + 12 + 310 + 35=86元元 超

8、市超市倉(cāng)庫(kù)倉(cāng)庫(kù)B1B2B3B4儲(chǔ)量?jī)?chǔ)量A1437A2314A3639銷量銷量3656 20 20 2 2伏格爾法伏格爾法 p098 最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用, , 有有時(shí)造成在其他處要花幾倍的運(yùn)費(fèi)。伏格爾法考慮時(shí)造成在其他處要花幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)就考慮次小運(yùn)費(fèi)j j這就有一個(gè)差額，差額越大，說(shuō)明這就有一個(gè)差額，差額越大，說(shuō)明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因而對(duì)差不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因而對(duì)差額最大處，就應(yīng)當(dāng)采用最小運(yùn)

9、費(fèi)調(diào)查。基于此，伏額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)查。基于此，伏格爾法的步驟是：格爾法的步驟是： 首先，在表首先，在表4 41 1中分別計(jì)算出各行各列的最小運(yùn)中分別計(jì)算出各行各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該列表的最右列和最費(fèi)和次小運(yùn)費(fèi)的差額，并填入該列表的最右列和最下行下行, ,見(jiàn)下表：見(jiàn)下表： 然后，從行或列差額中選出最大者，選擇它所在行或列然后，從行或列差額中選出最大者，選擇它所在行或列的最小元素，在表的最小元素，在表4-84-8中中B2B2列是最大差額所在列。列是最大差額所在列。B2B2列中最列中最小元素為小元素為4 4，可確定，可確定A3A3的產(chǎn)品先供應(yīng)的產(chǎn)品先供應(yīng)B2B2的需要

10、，得表的需要，得表4-94-9。同。同時(shí)將運(yùn)價(jià)表中的時(shí)將運(yùn)價(jià)表中的B2B2列數(shù)字劃去，如表列數(shù)字劃去，如表 超市超市倉(cāng)庫(kù)倉(cāng)庫(kù)B1B2B3B4行差值行差值A(chǔ)13113100（7）A219281（4）A374（6）1051（9-6）列差值列差值 2（3） 5（6-6）1（5） 3（6） 20 20B1B2B3B4行差值行差值A(chǔ)13113100（7）A219281（4）A374 （6）105（3）2（3-3）列差值列差值2（3）（0）1（5）3（6-3）B1B2B3B4行差值行差值A(chǔ)13113100（7）A21 （3）9281（4-3）A374 （6）105 （3）（0）列差值列差值2（3-3）（0

11、）1（5）2（3）繼續(xù)繼續(xù)B1B2B3B4行差值行差值A(chǔ)13113 （5）107（7-5）A21 （3）9286（1）A374 （6）105 （3）（0）列差值列差值（0）（0）1（5-5）2（3）B1B2B3B4行差值行差值A(chǔ)13113 （5）10（2）（2）A21 （3）928（1）（1）A374 （6）105 （3）（0）列差值列差值（0）（0）（0）（ 3 -3）最后，得到運(yùn)輸方案：最后，得到運(yùn)輸方案： （分配結(jié)果一定（分配結(jié)果一定= n + m - 1 個(gè)）個(gè)）它的運(yùn)輸總成本：它的運(yùn)輸總成本： 31+ 64 + 53 + 210 + 18 + 35=82元元 超市超市倉(cāng)庫(kù)倉(cāng)庫(kù)B1B2

12、B3B4儲(chǔ)量?jī)?chǔ)量A1527A2314A3639銷量銷量3656 20 20 4.2.24.2.2 最優(yōu)性檢驗(yàn)與方案的調(diào)整最優(yōu)性檢驗(yàn)與方案的調(diào)整p101 運(yùn)輸問(wèn)題中的閉合回路是指調(diào)運(yùn)方案中由一個(gè)空格和若運(yùn)輸問(wèn)題中的閉合回路是指調(diào)運(yùn)方案中由一個(gè)空格和若干個(gè)有數(shù)字格的水平和垂直連線包圍成的封閉回路。干個(gè)有數(shù)字格的水平和垂直連線包圍成的封閉回路。 目的是要計(jì)算解中各非基變量目的是要計(jì)算解中各非基變量( (對(duì)應(yīng)空格對(duì)應(yīng)空格) )的的檢驗(yàn)數(shù)檢驗(yàn)數(shù)，方法是令某非基變量取值為方法是令某非基變量取值為1 1，通過(guò)變化原基變量的值，找，通過(guò)變化原基變量的值，找出一個(gè)新的可行解，將其同原來(lái)的基可行解目標(biāo)函數(shù)值的變出

13、一個(gè)新的可行解，將其同原來(lái)的基可行解目標(biāo)函數(shù)值的變化比較?；容^。 閉合回路應(yīng)該這樣選?。簭哪骋豢崭癯霭l(fā)，用水平或垂閉合回路應(yīng)該這樣選?。簭哪骋豢崭癯霭l(fā)，用水平或垂直直線向前劃，每遇到一數(shù)字格，可以但并非一定要轉(zhuǎn)直直線向前劃，每遇到一數(shù)字格，可以但并非一定要轉(zhuǎn) 90度，直到回到起點(diǎn)空格，一定能夠找到唯一的閉合回路。度，直到回到起點(diǎn)空格，一定能夠找到唯一的閉合回路。 如果如果檢驗(yàn)數(shù)檢驗(yàn)數(shù) 大于等于零，表明對(duì)調(diào)運(yùn)方案作出任何改大于等于零，表明對(duì)調(diào)運(yùn)方案作出任何改變不會(huì)減少運(yùn)費(fèi)，現(xiàn)有方案是最優(yōu)的方案。變不會(huì)減少運(yùn)費(fèi)，現(xiàn)有方案是最優(yōu)的方案。 如果如果檢驗(yàn)數(shù)檢驗(yàn)數(shù)為負(fù)，則方案需要進(jìn)一步的改進(jìn)。改進(jìn)的為負(fù)

14、，則方案需要進(jìn)一步的改進(jìn)。改進(jìn)的方法是從為負(fù)的格出發(fā)（當(dāng)有兩個(gè)以上方法是從為負(fù)的格出發(fā)（當(dāng)有兩個(gè)以上檢驗(yàn)數(shù)檢驗(yàn)數(shù)負(fù)的時(shí)，從負(fù)的時(shí)，從絕對(duì)值最大的負(fù)絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)檢驗(yàn)數(shù)格出發(fā)），在這條閉合回路上，作格出發(fā)），在這條閉合回路上，作運(yùn)量的最大可能調(diào)整。剛才使用最小元素法得到下表值：運(yùn)量的最大可能調(diào)整。剛才使用最小元素法得到下表值： a、b、c、d、e、f 就是我們需要求的檢驗(yàn)值。就是我們需要求的檢驗(yàn)值。B1B2B3B4儲(chǔ)儲(chǔ)A1a 3b 114 33 107A23 1c 9 1 2d 84A3e 76 4f 103 59銷銷3656 檢驗(yàn)數(shù)檢驗(yàn)數(shù) a （x11）= 3 3 + 2 1 =1 檢驗(yàn)

15、數(shù)檢驗(yàn)數(shù) b （x12） = 11 10 + 5 4 =2 檢驗(yàn)數(shù)檢驗(yàn)數(shù) c （x22） = 9 2 + 3 10 + 5 4 =1 檢驗(yàn)數(shù)檢驗(yàn)數(shù) d （x24） = 8 10 + 3 2 = -1 檢驗(yàn)數(shù)檢驗(yàn)數(shù) e （x31） = 7 5 + 10 3 + 2 1 =10 檢驗(yàn)數(shù)檢驗(yàn)數(shù) f （x33） = 10 5 + 10 3 =12B1B2B3B4A111-b310A219-c28-dA37-e410-f5 閉回路調(diào)整法閉回路調(diào)整法 p47 當(dāng)所有檢驗(yàn)數(shù)都不小于零時(shí)，方案即為最優(yōu)調(diào)運(yùn)方案。當(dāng)所有檢驗(yàn)數(shù)都不小于零時(shí)，方案即為最優(yōu)調(diào)運(yùn)方案。當(dāng)檢驗(yàn)數(shù)還存在負(fù)值時(shí)，說(shuō)明該方案不是最優(yōu)，需要調(diào)整。

16、當(dāng)檢驗(yàn)數(shù)還存在負(fù)值時(shí)，說(shuō)明該方案不是最優(yōu)，需要調(diào)整。 4 + 1 = 5，3 1 = 2（因?yàn)檫@里價(jià)格（因?yàn)檫@里價(jià)格10，比較高），比較高） 0 + 1 = 1, 1 1= 0 。 得到新方案。得到新方案。B1B2B3B4A14 53 2A231 0 1A363 3 3、閉回路法。、閉回路法。（運(yùn)價(jià)）（運(yùn)價(jià)） 在給出調(diào)運(yùn)方案的計(jì)算表在給出調(diào)運(yùn)方案的計(jì)算表( (最終表最終表) )上，從每一空格出發(fā)上，從每一空格出發(fā)找一條閉回路。即以某空格為起點(diǎn)，用水平或垂直線向前找一條閉回路。即以某空格為起點(diǎn)，用水平或垂直線向前劃，碰到數(shù)字格可轉(zhuǎn)劃，碰到數(shù)字格可轉(zhuǎn)9090度后，繼續(xù)前進(jìn)，直到回到起始空度后，繼續(xù)

17、前進(jìn)，直到回到起始空格。在表格。在表4-114-11中，空格中，空格(A1(A1，B1)B1)的閉回路之一如表中虛線所的閉回路之一如表中虛線所示，檢驗(yàn)數(shù)示，檢驗(yàn)數(shù)=+3 -10 + 8 =+3 -10 + 8 1 = O 1 = O，其中：式中計(jì)算所用，其中：式中計(jì)算所用值為閉回路頂點(diǎn)所在格的運(yùn)價(jià)，起始空格為奇數(shù)位，它的下值為閉回路頂點(diǎn)所在格的運(yùn)價(jià)，起始空格為奇數(shù)位，它的下一個(gè)頂點(diǎn)為偶數(shù)位，下面頂點(diǎn)依次奇偶相間，奇數(shù)位取正一個(gè)頂點(diǎn)為偶數(shù)位，下面頂點(diǎn)依次奇偶相間，奇數(shù)位取正值，偶數(shù)位取負(fù)值，各數(shù)累加的和就為檢驗(yàn)數(shù)。同樣，可以值，偶數(shù)位取負(fù)值，各數(shù)累加的和就為檢驗(yàn)數(shù)。同樣，可以計(jì)算出其他空格的檢驗(yàn)

18、數(shù)。計(jì)算出其他空格的檢驗(yàn)數(shù)。 當(dāng)所有檢驗(yàn)數(shù)都不小于零時(shí)，方案即為最優(yōu)調(diào)運(yùn)方案。當(dāng)所有檢驗(yàn)數(shù)都不小于零時(shí)，方案即為最優(yōu)調(diào)運(yùn)方案。當(dāng)檢驗(yàn)數(shù)還存在負(fù)值時(shí)，說(shuō)明該方案不是最優(yōu)，需要調(diào)整。當(dāng)檢驗(yàn)數(shù)還存在負(fù)值時(shí)，說(shuō)明該方案不是最優(yōu)，需要調(diào)整。 本次課后的課外作業(yè)本次課后的課外作業(yè)習(xí)題：請(qǐng)您用習(xí)題：請(qǐng)您用最小元素法最小元素法以及以及伏格爾法伏格爾法解下面的習(xí)解下面的習(xí)題。然后您想想辦法，如何來(lái)進(jìn)行調(diào)整？題。然后您想想辦法，如何來(lái)進(jìn)行調(diào)整？ 5161224014367491011126704212315111010104.3 4.3 供需不平衡的運(yùn)輸問(wèn)題供需不平衡的運(yùn)輸問(wèn)題 前面的問(wèn)題是供需平衡問(wèn)題，即前面的

19、問(wèn)題是供需平衡問(wèn)題，即但實(shí)際問(wèn)題往往不平衡，或供大于需，或需大于但實(shí)際問(wèn)題往往不平衡，或供大于需，或需大于供。只要把供需不平衡問(wèn)題轉(zhuǎn)化成供需平衡問(wèn)題，供。只要把供需不平衡問(wèn)題轉(zhuǎn)化成供需平衡問(wèn)題，就可以用上述方法解決，具體方法如下。就可以用上述方法解決，具體方法如下。 (1)(1)當(dāng)倉(cāng)庫(kù)供應(yīng)量大于超市需求量時(shí)，只要增加當(dāng)倉(cāng)庫(kù)供應(yīng)量大于超市需求量時(shí)，只要增加一個(gè)假想的超市，一個(gè)假想的超市，j=n+1(j=n+1(實(shí)際上是儲(chǔ)存實(shí)際上是儲(chǔ)存) )，該超市，該超市總總需求量為：需求量為： 單位運(yùn)價(jià)為單位運(yùn)價(jià)為0 0，這樣，就轉(zhuǎn)，這樣，就轉(zhuǎn)化為平衡化為平衡 的運(yùn)輸問(wèn)題。的運(yùn)輸問(wèn)題。 njjmiiba11njjmiiba11 (2) (2)當(dāng)超市需求量大于倉(cāng)庫(kù)供應(yīng)量時(shí)，只要在供當(dāng)超市需求量大于倉(cāng)庫(kù)供應(yīng)量時(shí)，只要在供需平衡表中增加一個(gè)假想的倉(cāng)庫(kù)需平衡表中增加一個(gè)假想的倉(cāng)庫(kù)i=m+1i=m+1，該倉(cāng)庫(kù)供，該倉(cāng)庫(kù)供應(yīng)應(yīng)量為：量為： 而在單位運(yùn)價(jià)表上從該假想倉(cāng)而在單位運(yùn)價(jià)表上從該假想倉(cāng)庫(kù)庫(kù)到各超市的運(yùn)價(jià)為到各超市的運(yùn)價(jià)為0 0，同樣可以轉(zhuǎn)化為一個(gè)供需平衡，同樣可以轉(zhuǎn)化為一個(gè)供需平衡的運(yùn)輸問(wèn)題。的運(yùn)輸問(wèn)題。 為了讓同學(xué)們能夠自覺(jué)理解這個(gè)問(wèn)題，我們?cè)跒榱俗屚瑢W(xué)們能夠自覺(jué)理解這個(gè)問(wèn)題，我們?cè)谙乱豁?yè)畫一個(gè)供需不平衡的案例：下一頁(yè)畫一個(gè)供需不平衡的案例：m