運(yùn)籌學(xué) 第3章運(yùn)輸問(wèn)題

1、Chapter3 運(yùn)輸問(wèn)題( Transportation Problem ),運(yùn)輸問(wèn)題的數(shù)學(xué)模型 表上作業(yè)法 運(yùn)輸問(wèn)題的應(yīng)用,本章主要內(nèi)容：,2,從m個(gè)發(fā)點(diǎn) 向n個(gè)收點(diǎn) 發(fā)送某種貨物. 發(fā)點(diǎn)的發(fā) 量為 ， 收點(diǎn)的收量為 。由 運(yùn) 往 單位貨物的運(yùn)費(fèi)為 ，問(wèn)如何調(diào)配， 才能使運(yùn)費(fèi)最??？,問(wèn)題的提出,3,表1 產(chǎn)銷平衡表,上述數(shù)據(jù)可以匯總于表格中,如下:,表2 單位運(yùn)價(jià)表,4,運(yùn)輸問(wèn)題的數(shù)學(xué)模型,設(shè)xij代表為從第i個(gè)產(chǎn)地調(diào)運(yùn)給第j個(gè)銷地的物資 的數(shù)量.在產(chǎn)銷平衡的條件下，即 使總的運(yùn)費(fèi)支出最小，可以表為以下數(shù)學(xué)形式：,5,運(yùn)輸問(wèn)題的約束方程組系數(shù)矩陣及特征,矩陣A是一個(gè)m+n行mn列的矩陣，它

2、的秩為m+n-1。 運(yùn)輸問(wèn)題應(yīng)該有m+n-1個(gè)基變量。 3. xij的系數(shù)列向量為：,6,表上作業(yè)法,7,表上作業(yè)法的基本思路：,確定初始調(diào)運(yùn)方案 最優(yōu)性檢驗(yàn) 改進(jìn)方案,8,1 確定初始基可行解,運(yùn)輸問(wèn)題確定初始基可行解，就是求出運(yùn)輸問(wèn)題的初始調(diào)運(yùn)方案.,確定初始基可行解的方法有 最小元素法 伏格爾法,9,【例2-1】 某公司經(jīng)銷甲產(chǎn)品,下設(shè)3個(gè)加工廠A1、A2、A3，產(chǎn)品分別運(yùn)往銷售點(diǎn)B1、B2、B3、B4，各工廠的日產(chǎn)量和各銷售點(diǎn)的日需求量及各工廠到各銷售點(diǎn)的運(yùn)價(jià)如下表所示：（運(yùn)輸問(wèn)題供需平衡表和運(yùn)價(jià)表如下），求總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。,表3-3,10,思路：為了減少運(yùn)費(fèi)，應(yīng)優(yōu)先考慮單位運(yùn)價(jià)

3、最小(或運(yùn)距最短)的供銷業(yè)務(wù)，最大限度地滿足其供銷量。在可供物品已用完的產(chǎn)地或需求已全部滿足的銷地，以后將不再考慮。然后，在余下的供、銷點(diǎn)的供銷關(guān)系中，繼續(xù)按上述方法安排調(diào)運(yùn)，直至安排完所有供銷任務(wù)，得到一個(gè)完整的調(diào)運(yùn)方案(完整的解)為止。這樣就得到了運(yùn)輸問(wèn)題的一個(gè)初始基可行解(初始調(diào)運(yùn)方案)。 由于該方法基于優(yōu)先滿足單位運(yùn)價(jià)(或運(yùn)距)最小的供銷業(yè)務(wù)，故稱為最小元素法。,1、最小元素法,11,1. 最小元素法,3,1,4,6,3,3,（思想：就近供應(yīng)）,不能同時(shí)劃去行和列,保證填有運(yùn)量的格子為m+n-1,表3-4,12,最小元素法，有時(shí)按某一最小單位運(yùn)價(jià)優(yōu)先安排物品調(diào)運(yùn)時(shí)，卻可能在其他供銷點(diǎn)多

4、花幾倍的運(yùn)費(fèi)，從而使整個(gè)運(yùn)輸費(fèi)用增加。,2. 沃格爾法,沃格爾法考慮到： 一個(gè)產(chǎn)地的產(chǎn)品假如不能按照最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有個(gè)差額。 如果差額不大，當(dāng)不能按最小單位運(yùn)價(jià)安排運(yùn)輸時(shí)造成的運(yùn)費(fèi)損失不大；反之，如果差額很大，不按最小運(yùn)價(jià)組織運(yùn)輸就會(huì)造成很大損失，故應(yīng)盡量按最小單位運(yùn)價(jià)安排運(yùn)輸。沃格爾法就是基于這種考慮提出來(lái)的。,13,沃格爾法計(jì)算步驟： 1) 分別算出各行、各列的最小運(yùn)費(fèi)與次小運(yùn)費(fèi)的差額。 2) 從行、列中選出差額最大者，選擇它所在行、列中的最小元素，進(jìn)行運(yùn)量調(diào)整。 3) 對(duì)剩余行、列再分別計(jì)算各行、列的差額。返回1)、2)。,14,2.伏格爾法, 2 5 1 3,

5、0 1 1,表3-6, ,6, 2 1 3, 0 1 2,3, 2 1 2, 0 1, , ,3, 1 2, 7 6, ,5,2,1,表3-5,Z=85,15,1 若有兩個(gè)以上相同的最大差值，可任取其一。 2 剩下一行或者一列有空格，填數(shù)字，不能劃掉。 3 計(jì)算行差，列差時(shí)，已經(jīng)劃去的列或者行不再考慮。,16,例 用伏格爾法求初始調(diào)運(yùn)方案,17,初始調(diào)運(yùn)方案,18,2.2 最優(yōu)解的判別,判別辦法是計(jì)算空格(非基變量)的檢驗(yàn)數(shù),因?yàn)檫\(yùn) 輸問(wèn)題的目標(biāo)函數(shù)是實(shí)現(xiàn)最小化,所以當(dāng)所有空格處 的檢驗(yàn)數(shù)大于等于零時(shí),為最優(yōu)解.,下面分別介紹兩種計(jì)算檢驗(yàn)數(shù)的方法: 閉回路法 (2) 位勢(shì)法,19,閉回路：從空

6、格出發(fā)畫水平(或垂直)直線，遇到填有運(yùn)量的方格（數(shù)字格）可轉(zhuǎn)90，然后繼續(xù)前進(jìn)，直到到達(dá)出發(fā)的空格所形成的閉合回路。,調(diào)運(yùn)方案的任意空格一定存在唯一閉回路。,表3-7,20,5,10,4,7,A3,8,2,9,1,A2,10,3,11,3,A1,B4,B3,B2,B1,銷地產(chǎn)地,6,3,3,4,3,1,計(jì)算最小元素法得到的初始基可行解的檢驗(yàn)數(shù),(+1),(-1),(+1),(-1),(+1)3+(-1)3+(+1)2+(-1)1=1,調(diào)整后總運(yùn)費(fèi)增加：,空格處檢驗(yàn)數(shù)為1,表3-8,21,5,10,4,7,A3,8,2,9,1,A2,10,3,11,3,A1,B4,B3,B2,B1,銷地產(chǎn)地,6

7、,3,3,4,3,1,(+1),(-1),(+1),(-1),7-5+10-3+2-1=10,調(diào)整后總運(yùn)費(fèi)增加：,空格處檢驗(yàn)數(shù)為10,(-1),(+1),表3-9,22,檢驗(yàn)數(shù)表,1,10,12,1,-1,2,因?yàn)榇嬖谛∮诹愕臋z驗(yàn)數(shù),所以最小元素法給出的方案不是最優(yōu)方案.,表3-10,23,2. 位勢(shì)法,位勢(shì)：運(yùn)輸問(wèn)題的對(duì)偶變量稱為位勢(shì)。 因?yàn)閙個(gè)供應(yīng)點(diǎn)n個(gè)需求點(diǎn)的運(yùn)輸問(wèn)題有m+n個(gè)約束，因此運(yùn)輸問(wèn)題就有m+n個(gè)位勢(shì)。,行位勢(shì):關(guān)于供應(yīng)點(diǎn)Ai的約束對(duì)應(yīng)的對(duì)偶變量，記為 ui, i=1,2,m。 列位勢(shì):關(guān)于需求點(diǎn)Bj的約束對(duì)應(yīng)的對(duì)偶變量，記為vj, j = 1,2,n。,24,定理：運(yùn)輸問(wèn)題變

8、量xij的檢驗(yàn)數(shù),證明：,25,位勢(shì)法求檢驗(yàn)數(shù)的步驟:,1.在表中下面和右面增加一行和一列,列中添入ui,行中添入vj ,令u1=0, 按照 , 根據(jù)表中已有的數(shù)字確定所有的ui及vj ;,2.計(jì)算所有空格處的檢驗(yàn)數(shù).,26,2,-1,3,0,10,-5,9,檢驗(yàn)數(shù)表,1,2,1,-1,10,12,24=-10，當(dāng)前方案 不是最優(yōu)方案。,最優(yōu)方案判別準(zhǔn)則,表3-12,27,2.3 閉回路調(diào)整法改進(jìn)方案,從(p,q)空格開始畫閉回路，其它轉(zhuǎn)角點(diǎn)都是填有運(yùn)量的方格，并從(p,q)空格開始給閉回路上的點(diǎn)按+1，-1，+1，-1編號(hào)，-1格的最小運(yùn)量為調(diào)整量。,表3-13,28,找到最小調(diào)整量以后,按

9、照閉回路上的正、負(fù)號(hào)，分別加上和減去此值，得到新的運(yùn)輸方案。,再用閉回路法或者位勢(shì)法求檢驗(yàn)數(shù)，得到下表:,表3-14,29,這時(shí)所有的檢驗(yàn)數(shù)都非負(fù)，表中的解就是最優(yōu)解.,表3-15,30,例 求該運(yùn)輸問(wèn)題的最優(yōu)解,31,表上作業(yè)法的計(jì)算步驟：,32,表上作業(yè)法計(jì)算中的問(wèn)題：,（1）若運(yùn)輸問(wèn)題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取ij0中最小者對(duì)應(yīng)的變量為換入變量。 （2）無(wú)窮多最優(yōu)解 產(chǎn)銷平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解。如果非基變量的ij0，則該問(wèn)題有無(wú)窮多最優(yōu)解。,33, 退化解： 表格中一般要有(m+n-1)個(gè)數(shù)字格

10、。但有時(shí)在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證有(m+n-1)個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個(gè)0即可。 利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的最小運(yùn)量（超過(guò)2個(gè)最小值）作為調(diào)整量，選擇任意一個(gè)最小運(yùn)量對(duì)應(yīng)的基變量作為換出變量，而經(jīng)調(diào)整后，得到退化解。這時(shí)另一個(gè)數(shù)字格必須填入一個(gè)“0”以示它為基變量。,34,12,4,11,4,8,3,10,2,9,5,11,6,(0),(2),(9),(2),(1),(12),8,12,4,2,8,14,如下例中11檢驗(yàn)數(shù)是 0，經(jīng)過(guò)調(diào)整，可得到另一個(gè)最優(yōu)解。,其中綠色是非基變量檢驗(yàn)數(shù)，紅色為分配量。,

11、35,11,4,4,3,1,3,7,7,8,2,10,6,3,4,1,6,0,6,在x12、x22、x33、x34中任選一個(gè)變量作為基變量，例如選x34,例：用最小元素法求初始可行解,36,第三節(jié) 產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法,表上作業(yè)法是以產(chǎn)銷平衡為前提的：,實(shí)際中，往往遇到產(chǎn)銷不平衡的運(yùn)輸問(wèn)題,1.產(chǎn)大于銷（供過(guò)于求）,2.銷大于產(chǎn)（供不應(yīng)求）,37,產(chǎn)銷不平衡運(yùn)輸問(wèn)題向產(chǎn)銷平衡運(yùn)輸問(wèn)題的轉(zhuǎn)化,產(chǎn)大于銷的運(yùn)輸問(wèn)題：,數(shù)學(xué)模型,38,設(shè)xi n+1 是產(chǎn)地Ai 的儲(chǔ)存量，化成標(biāo)準(zhǔn)形,其中,引入虛擬的銷地(儲(chǔ)存地)（需求量為 ），并令各個(gè)產(chǎn)地到虛擬銷地的單位運(yùn)費(fèi)為0。,39,產(chǎn)小于銷的運(yùn)輸

12、問(wèn)題：,引入一個(gè)虛擬的產(chǎn)地（產(chǎn)量等于 ）， 并令該虛擬產(chǎn)地到各銷地的單位運(yùn)費(fèi)為0。,40,總供應(yīng)量為19千噸，而總需求量為15千噸,例2： A1、A2、A3三個(gè)蔬菜生產(chǎn)地生產(chǎn)的蔬菜主要供應(yīng)B1、B2、B3、B4四個(gè)城市。已知三個(gè)產(chǎn)地今年的蔬菜產(chǎn)量預(yù)計(jì)分別為7千噸、5千噸和7千噸；四個(gè)城市今年的蔬菜需求量分別為2千噸、3千噸、4千噸和6千噸；從每個(gè)蔬菜產(chǎn)地平均運(yùn)輸1千噸蔬菜到各個(gè)城市的單位費(fèi)用(萬(wàn)元)見下表，你能否替他們編制一個(gè)總運(yùn)費(fèi)最省的蔬菜調(diào)運(yùn)方案？,41,0,0,-2,2,0,4,3,0,8,2,5,7,2,3,8,7,最優(yōu)解中x15=2, x25=2，表示兩個(gè)產(chǎn)地沒有運(yùn)出去的蔬菜量。,42,假如例2中各產(chǎn)地的蔬菜總產(chǎn)量不是19千噸，而是12千噸，就成了一個(gè)供不應(yīng)求的運(yùn)輸問(wèn)題。,引入一個(gè)虛擬產(chǎn)地,43,例3 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同，已知各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各個(gè)化肥廠到各地區(qū)單位化肥的運(yùn)價(jià)如下表所示，試決定使總運(yùn)費(fèi)最省的化肥調(diào)撥方案。,44,這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題，總產(chǎn)量160萬(wàn)噸，四個(gè)地區(qū)的最低需求量為110萬(wàn)噸，最高需求為無(wú)限。根據(jù)現(xiàn)有產(chǎn)量，第四個(gè)地區(qū)每年最多能分配到60萬(wàn)噸，這樣最高需求為210萬(wàn)噸，大于總產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個(gè)假想的