運(yùn)籌學(xué) CH2運(yùn)輸規(guī)劃.ppt

1、Chapter2 運(yùn)輸規(guī)劃( Transportation Problem ),運(yùn)輸規(guī)劃問題 運(yùn)輸規(guī)劃的數(shù)學(xué)模型 表上作業(yè)法 運(yùn)輸問題的應(yīng)用 運(yùn)輸規(guī)劃模型的Excel解法,本章主要內(nèi)容：,教學(xué)要求,教學(xué)要求： 了解運(yùn)輸問題的數(shù)學(xué)模型及其特點(diǎn)； 掌握表上作業(yè)法； 了解Microsoft Excel求解運(yùn)輸問題的方法。 重難點(diǎn)： 表上作業(yè)法,運(yùn)輸規(guī)劃問題介紹,人們?cè)趶氖律a(chǎn)活動(dòng)中，不可避免地要進(jìn)行物資調(diào)運(yùn)工作。如某時(shí)期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運(yùn)到需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量和銷售量及各地之間的運(yùn)輸費(fèi)用，如何制定一個(gè)運(yùn)輸方案，使總的運(yùn)輸費(fèi)用最小。這樣的問題稱為運(yùn)輸問題。,

2、運(yùn)輸規(guī)劃問題介紹,物資調(diào)運(yùn)是一個(gè)典型的線性規(guī)劃問題。 1939年前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇提出這一問題； 1941年美國(guó)數(shù)學(xué)家F.L.Hitchcock提出運(yùn)輸問題數(shù)學(xué)模型； 1951年Dantzig將此類問題的解法系統(tǒng)化,完善化,改為用表上作業(yè)法求解.,運(yùn)輸問題的分類,分類：有轉(zhuǎn)運(yùn)與無轉(zhuǎn)運(yùn)運(yùn)輸問題 無轉(zhuǎn)運(yùn)的運(yùn)輸問題: 產(chǎn)銷平衡問題: 總產(chǎn)量 =總銷量 產(chǎn)銷不平衡問題: 總產(chǎn)量 總銷量，則為產(chǎn)大于銷情況 總產(chǎn)量 總銷量，則為銷大于產(chǎn)情況 對(duì)于產(chǎn)銷不平衡運(yùn)輸問題，可轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問題處理，而有轉(zhuǎn)運(yùn)問題可化為無轉(zhuǎn)運(yùn)問題處理。,運(yùn)輸問題網(wǎng)絡(luò)圖,產(chǎn)地,銷地,若 則稱該問題為平衡運(yùn)輸問題，否則稱為非平

3、衡運(yùn)輸問題。,運(yùn)輸問題,產(chǎn)銷平衡問題,產(chǎn)銷平衡問題,幾個(gè)術(shù)語： 生產(chǎn)地（供應(yīng)地，出發(fā)地）：產(chǎn)量（供應(yīng)量） 銷售地（需求地，目的地）：銷量（需求量） 運(yùn)價(jià)（單價(jià)）：?jiǎn)挝划a(chǎn)品運(yùn)輸費(fèi)用 運(yùn)費(fèi)：?jiǎn)蝺r(jià)運(yùn)量,產(chǎn)銷平衡問題的數(shù)學(xué)模型,例2.1 某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)價(jià)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？,產(chǎn)銷平衡問題的數(shù)學(xué)模型,解：產(chǎn)銷平衡問題：總產(chǎn)量 = 總銷量500 設(shè) xij 為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：,產(chǎn)銷平衡問題的數(shù)學(xué)模型,數(shù)學(xué)模型為：,產(chǎn)銷平衡問題的數(shù)學(xué)模型,產(chǎn)

4、銷平衡問題數(shù)學(xué)模型的一般形式： 設(shè)某物品有m個(gè)產(chǎn)地A1, A2 , Am；各產(chǎn)地的產(chǎn)量分別是a1,a2,am；有n個(gè)銷地B1, B2, Bn。各銷地的銷量分別是b1,b2,bn ；假如從產(chǎn)地Ai(i=1,2,m)向銷地Bj( j= 1,2,n)運(yùn)輸單位物品的運(yùn)價(jià)是cij；問怎樣調(diào)運(yùn)這些物品才能使總運(yùn)費(fèi)最??？,產(chǎn)銷平衡問題的數(shù)學(xué)模型,這是一個(gè)線性規(guī)劃問題，可以用單純形法求解。 但是，由于它所含變量多，求解極不方便。即使求解一個(gè)m3，n4的簡(jiǎn)單運(yùn)輸問題，變量數(shù)目也將達(dá)到19個(gè)之多。 因此，必須尋找更簡(jiǎn)便的求解方法。,產(chǎn)量約束,銷量約束,非負(fù)約束,總運(yùn)輸費(fèi)用,極小化,由某一產(chǎn)地運(yùn)往各個(gè)銷地的物品數(shù)量

5、之和等于該產(chǎn)地的產(chǎn)量,由各個(gè)產(chǎn)地運(yùn)往某一銷地的物品數(shù)量之和等一該銷地的銷量,非負(fù)條件,產(chǎn)銷平衡問題數(shù)學(xué)模型的特點(diǎn),1.運(yùn)輸問題有最優(yōu)解 2.運(yùn)輸問題約束條件的系數(shù)矩陣,系數(shù)列向量的結(jié)構(gòu)：,即除第i個(gè)和第( m + j )個(gè)分量為1外，其它分量全等于0。,約束條件系數(shù)矩陣的元素等于0或1； 約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素，對(duì)應(yīng)于每一個(gè)變量在前 m 個(gè)約束方程中出現(xiàn)一次,在后 n 個(gè)約束方程中也出現(xiàn)一次； 所有結(jié)構(gòu)約束條件都是等式約束； 各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。,產(chǎn)銷平衡問題數(shù)學(xué)模型的特點(diǎn),產(chǎn)銷平衡問題的數(shù)學(xué)模型,模型的變化： 1）有時(shí)目標(biāo)函數(shù)求最大。如求利潤(rùn)最大或營(yíng)業(yè)額最大等；

6、 2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入約束條件（等式或不等式約束)； 3）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。P89P90,產(chǎn)銷平衡模型的求解-表上作業(yè)法,表上作業(yè)法是求解運(yùn)輸問題的一種簡(jiǎn)便而有效的方法,其求解過程在運(yùn)輸表上進(jìn)行,它是一種迭代法,其實(shí)質(zhì)是單純形法。步驟為： 1. 先按某種方法找出一個(gè)初始解(初始調(diào)運(yùn)方案）； 2. 對(duì)現(xiàn)行解作最優(yōu)性判別； 3. 若不是最優(yōu)解,就在表上對(duì)它進(jìn)行調(diào)整改進(jìn),得出一個(gè)新解； 4. 再判別,再改進(jìn),直到得到運(yùn)輸問題的最優(yōu)解為止； 在迭代過程中,得出的所有解都要求是運(yùn)輸問題的基可行解。,表上作業(yè)法步驟,運(yùn)輸表,表

7、上作業(yè)法,例2.2 某運(yùn)輸資料如下表所示：,問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？,表上作業(yè)法-初始方案,解：第1步 求初始方案,方法1：最小元素法 基本思想： 就近供應(yīng)，即從運(yùn)價(jià)最小的地方開始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。,表上作業(yè)法-初始方案,用最小元素法確定初始方案的步驟： 1）從表中找出運(yùn)價(jià)最小的單元格。 2）從該單元格所對(duì)應(yīng)的產(chǎn)量和銷量中選擇最小的值，作為該單元格的運(yùn)量。 3）調(diào)整該單元格所對(duì)應(yīng)的產(chǎn)量和銷量，同時(shí)劃去產(chǎn)量或銷量的剩余量為0的行或列。 4）再在剩下的單元格中重復(fù)1），2），3）步，至產(chǎn)量（銷量）的剩余量為0結(jié)束。,注意：表上作業(yè)法要求，調(diào)運(yùn)方案的有數(shù)字格必須為m

8、+n-1個(gè)。一般，用最小元素法給出的方案符合這一要求。,表上作業(yè)法-初始方案,總的運(yùn)輸費(fèi)(31)+(64) +(43) +(12)+(310)+(35)=86元,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,表上作業(yè)法-初始方案,最小元素法的缺點(diǎn)：為了節(jié)省一處費(fèi)用，有時(shí)可能造成其他處要多花費(fèi)幾倍費(fèi)用。 基本思想： 元素差額法對(duì)最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。,方法2：Vogel法（伏格爾法、元素差額法）,表上作業(yè)法-初始方案,Vogel法（伏格爾法、元素差額法）步驟：,1）

9、從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。,3,11,3,10,1,9,2,7,4,10,5,8,表上作業(yè)法-初始方案,2）再?gòu)牟钪底畲蟮男谢蛄兄姓页鲎钚∵\(yùn)價(jià)確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列。 重復(fù)1)和2)，直到找出初始解為至。,3,11,3,10,1,9,2,7,4,10,5,8,6,3,0,表上作業(yè)法-初始方案,0,2,1,3,2,1,6,3,表上作業(yè)法-初始方案,0,1,2,2,1,6,3,3,表上作業(yè)法-初始方案,7,1,2,6,6,3,3,5,表上作業(yè)法-初始方案,6,3,3

10、,5,1,2,表上作業(yè)法-初始方案,5,3,6,3,1,2,該方案的總運(yùn)費(fèi): (13)(46)(35)(210)(18)(35)85元,表上作業(yè)法-初始方案,用元素差額法求得的基本可行解更接近最優(yōu)解。,最小元素法：總的運(yùn)輸費(fèi)=86元 伏格爾法：總的運(yùn)輸費(fèi)=85元,用元素差額法求得的基本可行解更接近最優(yōu)解。,表上作業(yè)法-最優(yōu)解的判別,第2步 最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）,求出一組初始方案（基可行解）后，判斷是否為最優(yōu)解，仍然是用檢驗(yàn)數(shù)來判斷，記xij的檢驗(yàn)數(shù)為ij，求最小值的運(yùn)輸問題的最優(yōu)判別準(zhǔn)則是：,所有檢驗(yàn)數(shù)都非負(fù)，則為最優(yōu)運(yùn)輸方案（最優(yōu)解）； 所有檢驗(yàn)數(shù)都0，則為唯一最優(yōu)運(yùn)輸方案（唯一最優(yōu)

11、解）； 存在檢驗(yàn)數(shù)為0，其他檢驗(yàn)數(shù)0，則為無窮多最優(yōu)運(yùn)輸方案（無窮多最優(yōu)解）。,求檢驗(yàn)數(shù)的方法： 閉回路法,表上作業(yè)法-最優(yōu)解的判別,閉回路的概念,為一個(gè)閉回路 ，集合中的變量稱為回路的頂點(diǎn)，相鄰兩個(gè)變量的連線為閉回路的邊。如下表,表上作業(yè)法-最優(yōu)解的判別,從x11出發(fā)，用水平或垂直線段向前劃，碰到數(shù)字格必須轉(zhuǎn)90度，再繼續(xù)向前，直到回到起點(diǎn)止。 閉回路的變量集合是x11,x12,x42,x43,x23,x25,x35, x31 。,表上作業(yè)法-最優(yōu)解的判別,閉回路法求空格檢驗(yàn)數(shù) 空格閉回路概念： 從一空格出發(fā)，向數(shù)字格作直線，每遇數(shù)字格則轉(zhuǎn)90度，直回到開始的空格。這種以一個(gè)空格為頂點(diǎn)，其余

12、頂點(diǎn)全為數(shù)字格的閉合折線，被稱為該空格的閉合回路。 可以證明： 按前面方法確定的調(diào)運(yùn)方案，每一個(gè)空格都有惟一的閉合回路。,表上作業(yè)法-最優(yōu)解的判別,空格檢驗(yàn)數(shù)概念： 作出空格的閉合回路，令空格增加一個(gè)單位調(diào)運(yùn)量(+1)，沿閉合回路進(jìn)行減一(-1)增一(+1)方法進(jìn)行平衡調(diào)整調(diào)運(yùn)量得到新的調(diào)運(yùn)方案，新方案總運(yùn)費(fèi)與前一方案總運(yùn)費(fèi)相比，總運(yùn)費(fèi)的改變量，就是該空格的檢驗(yàn)數(shù)。 最優(yōu)性檢驗(yàn)：所有空格檢驗(yàn)數(shù)非負(fù)，則為最優(yōu)解。 下面以例子說明空格檢驗(yàn)數(shù)的求法：,表上作業(yè)法-最優(yōu)解的判別,該空格檢驗(yàn)數(shù)：11=(+1) 3+(-1) 1+ (+1) 2+ (-1) 3=1,3,11,3,10,1,9,2,7,4,

13、10,5,8,3,4,1,6,3,3,+1,-1,+1,-1,1,表上作業(yè)法-最優(yōu)解的判別,該空格檢驗(yàn)數(shù)：12=(+1) 11+(-1) 4 + (+1) 5+ (-1) 10=2,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,+1,-1,+1,-1,2,1,表上作業(yè)法-最優(yōu)解的判別,該空格檢驗(yàn)數(shù)：22=(+1) 9+(-1) 4 + (+1) 5+ (-1) 10 + (+1) 3+ (-1) 2=1,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,+1,-1,+1,-1,2,1,+1,-1,1,表上作業(yè)法-最優(yōu)解的判別,該空格檢

14、驗(yàn)數(shù)：22=(+1) 8+(-1) 10 + (+1) 3+ (-1) 2=-1 故不是最優(yōu)解。,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,+1,-1,2,1,+1,-1,1,-1,表上作業(yè)法-解的改進(jìn),第3步 解的改進(jìn) 閉回路調(diào)整法 步驟: 1、找出空格檢驗(yàn)數(shù)最小的空格 ； 2、作此空格的惟一閉合回路； 3、確定值： 閉回路中具有(-1) 的數(shù)字格中運(yùn)量最小的運(yùn)量作為 ； 4、按閉合回路上的正、負(fù)號(hào)，將該單元格的運(yùn)量加減此值，調(diào)整運(yùn)量得新調(diào)運(yùn)方案； 5、再對(duì)此方案用閉回路法進(jìn)行最優(yōu)性檢驗(yàn)。,表上作業(yè)法-解的改進(jìn),1、空格(2,4)檢驗(yàn)數(shù)最??； 2、作此空格

15、的惟一閉合回路； 3、確定值為1；,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,2,1,1,-1,10,12,+1,-1,+1,-1,表上作業(yè)法-解的改進(jìn),4、按閉合回路上的正、負(fù)號(hào)，將該單元格的運(yùn)量加減此=1值，調(diào)整運(yùn)量得新調(diào)運(yùn)方案（新的運(yùn)輸表）；,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,+1,-1,+1,-1,1,2,5,0,總的運(yùn)輸費(fèi)(31)+(64) +(53) +(210)+(18)+(35)=85元,表上作業(yè)法-解的改進(jìn),對(duì)新的運(yùn)輸表進(jìn)行最優(yōu)解的判定，所有檢驗(yàn)數(shù)都非負(fù)，故為最優(yōu)解，且總的運(yùn)輸費(fèi)(31)+(64)

16、 +(53) +(210)+(18)+(35)=85元。,3,11,3,10,1,9,2,7,4,10,5,8,3,5,1,6,3,2,2,0,2,1,9,12,表上作業(yè)法-解的改進(jìn),同時(shí)，發(fā)現(xiàn)單元格（1,1）的檢驗(yàn)數(shù)為0，此問題（模型）有無窮多解。,3,11,3,10,1,9,2,7,4,10,5,8,3,5,1,6,3,2,2,0,2,1,9,12,表上作業(yè)法-退化解的處理,表上作業(yè)法計(jì)算中的問題：,退化解： 表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證有(m+n-1)個(gè)數(shù)字格。一般可在劃去的行和列的任意空格處加一個(gè)0即可。 利

17、用閉回路調(diào)整法對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量，若最小運(yùn)量超過2個(gè)相同，則選擇任意一個(gè)最小運(yùn)量標(biāo)記為“0”。 （換句話說，調(diào)整后有2個(gè)或2個(gè)以上運(yùn)量為0的單元格時(shí)，只取1個(gè)單元格為空格，其他單元格運(yùn)量填0。）,表上作業(yè)法-小結(jié),表上作業(yè)法的計(jì)算步驟：,運(yùn)輸規(guī)劃,產(chǎn)銷不平衡問題利用教材P90方法處理，變?yōu)楫a(chǎn)銷平衡問題。,Excel求解演示 例2.2,例題：某公司承擔(dān)4條航線的運(yùn)輸任務(wù)，已知：（1）各條航線的起點(diǎn)城市和終點(diǎn)城市及每天的航班數(shù)見表1；（2）各城市間的航行時(shí)間見表2；（3）所有航線都使用同一種船只，每次裝船和卸船時(shí)間均為1天。問該公司至少應(yīng)配備多少條船才能滿足所有航線運(yùn)輸?shù)男枰?應(yīng)用舉例 P93 例4,應(yīng)用舉例,表2 各城市間的航行時(shí)間（天）,應(yīng)用舉例,應(yīng)用舉例,解：所需船只可分為兩部分： （1）各航線航行、裝船、卸船所占用的船只，對(duì)各航線逐一分析，所需船只數(shù)列入表3中，累計(jì)共需91條船。,表3 各航線航行、裝船、卸船所占用的船只,（2）各港口之間調(diào)度所需船只數(shù)。這由每天到達(dá)港口的船只數(shù)與它所需發(fā)出的船只數(shù)不相等而產(chǎn)生。各港口城市每天到達(dá)船只數(shù)、需求船只數(shù)及其差額如表4中。,應(yīng)用舉例,將船由多余的港