表上作業(yè)法在貨物運輸組織中的應(yīng)用分析課程設(shè)計1

1、運 輸 工 程 課 程 設(shè) 計題 目 表上作業(yè)法在貨物運輸組織中的應(yīng)用分析 摘要運輸是人們借助于運輸工具，在一定交通路線上實施運輸對象空間位移的有目地的活動?，F(xiàn)代化的運輸不僅需要具備現(xiàn)代化的運輸通路、港站和運載工具等設(shè)施設(shè)備，同時還必須用科學(xué)的方法和手段合理組織運輸生產(chǎn)，充分發(fā)揮各種運輸方式的運能和優(yōu)勢，提高運輸效率，降低運輸成本，以便更好的滿足社會生產(chǎn)和人民生活的需要。企業(yè)的生產(chǎn)過程需要消耗一定的資源，而資源總是稀缺的，因此合理利用現(xiàn)有資源，并將其將行合理分配，是充分發(fā)揮企業(yè)資源效能、提高企業(yè)綜合經(jīng)濟(jì)效益的必由之路。本文利用表上作業(yè)法求得了貨物運輸組織中的最小費原理，解決了物流公司在貨物運輸

2、中所存在的問題，為物流公司的貨物運輸提供了一種行之有效的方法。通過建立物流配送模型，利用表上作業(yè)法解出最小運輸成本，解決了降低運輸成本問題，提升了物流公司的市場競爭力。 關(guān)鍵詞：貨物運輸，表上作業(yè)發(fā)，應(yīng)用實例分析。目錄1 緒論61.1 課題的提出61.1.1 課題背景61.1.2 課題意義62 表上作業(yè)發(fā)62.1 表上作業(yè)發(fā)的具體介紹62.2 確定初始基本可行解82.1.1 最小元素法82.2.2 西北角法112.2.3 伏格爾法（vogel）112.3 基本可行解的最優(yōu)性檢驗162.3.1 位勢法162.3.2 閉回路法203 表上作業(yè)法在實際中的應(yīng)用223.1 產(chǎn)銷平衡問題223.1.1

3、平衡問題模型233.2.3 數(shù)學(xué)模型的建立233.2 產(chǎn)銷不平衡問題244 總結(jié)24參考文獻(xiàn)261 緒論1.1 課題的提出1.1.1 課題背景運輸問題是當(dāng)今社會經(jīng)濟(jì)生活中經(jīng)常出現(xiàn)的問題，在經(jīng)濟(jì)建設(shè)中，經(jīng)常出現(xiàn)物資的調(diào)運問題，如何制定調(diào)運方案，將物資運往指定地點，而且實現(xiàn)運輸費用最小，即為運輸問題。運輸問題是特殊的線性規(guī)劃問題，它是現(xiàn)行網(wǎng)絡(luò)最優(yōu)化的一個例子。與一般線性規(guī)劃問題不同的是它的約束方程組的系數(shù)矩陣具有特殊結(jié)構(gòu)，這就需要采用不同甚至更為簡約的方法來解決這種實際工作中遇到的問題。運輸問題代表了物資合理調(diào)運、車輛合理調(diào)度等問題。其他類型問題經(jīng)過一系列改變后也可歸結(jié)為運輸問題。1.1.2 課題

4、意義物品運輸問題在當(dāng)今經(jīng)濟(jì)建設(shè)中是十分常見的問題，運輸問題及運輸成本的優(yōu)化是運輸企業(yè)制定調(diào)運方案時必須要考慮的內(nèi)容，如何選擇一個合理的運輸方案使的運輸費用最低是十分關(guān)鍵的。表上作業(yè)法可以較好的解決這類問題。本文主要目地便是系統(tǒng)全面的對表上作業(yè)法進(jìn)行研究。2 表上作業(yè)發(fā)2.1 表上作業(yè)發(fā)的具體介紹表上作業(yè)發(fā)的單純形法在求解運輸問題的一種簡化方法，其實質(zhì)是單純形法，但具體計算和術(shù)語有所不同。從運價最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運價從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個基本可行解。 這個方法的基本思想是就近

5、供應(yīng)，即從運價表中最小運價開始確定調(diào)運量，然后次小，一直到給出初始調(diào)運方案為止.可歸納為：（1）找出基本可行解。即在（m*n）產(chǎn)銷平衡表上用西北角法或最小元素法，vogel法給出m+n.1個數(shù)字，稱為數(shù)字格。它就是初始基變量的取值。（2）求各非基變量的檢驗數(shù)，即在表上記載空格的檢驗數(shù)，判斷是否達(dá)到最優(yōu)解。如以是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。（3）確定換入變量和換出變量，找出新的基本可行解，在表上用閉環(huán)回路法調(diào)整。（4）重復(fù)（2）（3）知道得到最優(yōu)解為止。以下通過實際原始材料研究表上作業(yè)發(fā)：設(shè)有5個產(chǎn)地a1、a2、a3、a4、a5和4個銷地b1、b2、b3、b4的運輸問題，他們的供應(yīng)量和需

6、求量及單位運費如下表。表2.1供應(yīng)量和需求量及單位運費b1b2b3b4供應(yīng)量a110205710a213912820a34157930a41471040a531251950需求量60602010150表2.2供應(yīng)量和需求量b1b2b3b4供應(yīng)量a110a220a330a440a550需求量606020101502.2 確定初始基本可行解確定初始基本可行解一般的方法是既簡便，有盡可能接近最優(yōu)解，下面介紹最小元素法和vogel法。2.1.1 最小元素法最小元素法的基本思想就是就近供應(yīng)，即從最小的運價開始確定供銷關(guān)系，然后次小。一直到給出初始基本可行解，以上述材料為例進(jìn)行討論。（1）從表2.1中找出

7、最小運價為0，這表示先將a4的產(chǎn)品供應(yīng)給b4，因為a4b4a4除滿足b4的需求外，還可多余30的產(chǎn)品。在表2.2中的（a4,b4）的交叉處填上10，得表2.3。并將表2.1的b4列劃去，得表2.4。表2.3計算過程表（1）b1b2b3b4供應(yīng)量a110a220a330a41040a550需求量60602010150表2.4計算過程表（2）b1b2b3b4供應(yīng)量a110205710a213912820a34157930a41471040a531251950需求量60602010150 （2）在表2.4中在找出最小的運價1，確定a4中剩余30供應(yīng)給b3，滿足b3的需求量還多出10，并得出表2.5。

8、并劃去表2.1中的b3，得表2.6表2.5計算過程表（3）b1b2b3b4供應(yīng)量a110a220a330a4201040a550需求量60602010150表2.6計算過程表（4）b1b2b3b4供應(yīng)量a110205710a213912820a34157930a41471040a531251950需求量60602010150（3）在表2.6中找出最小運價為3。a5b1,所以a5里面的50全部供應(yīng)給b1,還缺少10需求量，在從表中找出最小運價4，而b1只需求10，因此a3中止供應(yīng)10給bi，還剩余20，由此的表2.7。在表2.6中劃去b1列，由于a5里的均已供應(yīng)完，均劃去，得表2.8。表2.7計

9、算過程表（5）b1b2b3b4供應(yīng)量a110a220a31030a4201040a55050需求量60602010150表2.8計算過程表（6）b1b2b3b4供應(yīng)量a110205710a213912820a34157930a41471040a531251950需求量60602010150（4）現(xiàn)在只有b2的需求沒有滿足，所以a1,a2,a3,a4的全部供應(yīng)給b2，剛好滿足所有的供需量，由此的到表2.9。表2.9調(diào)運方案表b1b2b3b4供應(yīng)量a11010a22020a3102030a410201040a55050需求量60602010150由表2.8可知，此方案的總費用為1o20+209+1

10、04+2015+107+201+0+503=960.2.2.2 西北角法從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個基本可行解。 西北角法的基本思想是給產(chǎn)銷平衡表左上角的變量分配運輸量，以確定產(chǎn)銷關(guān)系，依此類推，一直到給出初始可行方案為止。求解步驟如下：（1）先決定產(chǎn)銷平衡表左上角變量 的值。令這個變量取盡可能大的值，即 ，在這個變量對應(yīng)的數(shù)字格填上變量所取的值。（2）若，則在第l行空格處打“”，這些空格不再賦值；若，則在第k列空格處打“”，這些空格不再賦值；若

11、=，則在行的空格處打“”后，就不能在列的空格處打“”，反之，若在列的空格處打“”，就不在行空格處打“”。（3）對表上沒有打“”的地方重復(fù)（1）， （2）步，直到所有格子都有標(biāo)記止。 可以證明，用西北角法確定的初始方案是運輸問題的一個初始基可行解，它也恰好包含m+n.1個數(shù)字格。2.2.3 伏格爾法（vogel）最大差額法是一行或一列的整體出發(fā)考慮，會更加合理。一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小費用調(diào)運時，運輸量就會加多從而運費增加越多。因而對差額最大處，要優(yōu)先考慮，應(yīng)當(dāng)采用最小運費調(diào)運。最大差額法的具體步驟如下：（1）在表2.1中分

12、別計算出各行和各列的最小運費和次小運費的差額，并填入該表的最右列和最下行，見表2.10。表2.10計算過程表（7）b1b2b3b4行差額a11020572a21391281a3415793a4147101a53125192列差額1247（2）從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表2.10中b4列是最大差額所在列。b4列最小元素為0，可確定a4產(chǎn)品先供應(yīng)b4的需要。得表2.11。b4的需求量滿足時，則在表2.11中劃去b4，得表2.12。表2.11計算過程表（8）b1b2b3b4供應(yīng)量a110a220a330a41040a550需求量60602010150表2.12計算過程

13、表（9）b1b2b3b4行差額a11020572a21391281a3415793a4147101a53125192列差額1247（3）在表2.12中，未劃去的行和列中再分別計算出行差額和列差額，得表2.13。在表2.13中，a4為最大差額所在行，所對應(yīng)的最小元素為b3列，則a4的成品供應(yīng)給b3，a3里還有30個，b3需求30個，得表2.14。b3中的需求滿足時，在表2.12中劃去b3，得表2.15。2.13計算過程表（10）b1b2b3行差額a1102055a2139123a341573a414716a531252列差額124表2.14計算過程表（11）b1b2b3b4供應(yīng)量a110a220

14、a330a4201040a550需求量60602010150表2.15計算過程表（12）b1b2b3b4行差額a11020572a21391281a3415793a4147101a53125192列差額1247（4）在表2.15中，未劃去的元素在進(jìn)行計算出行差額和列差額，得表2.16.重復(fù)步驟（1），（2），可得表2.17。由于a1中的一全部供應(yīng)完，則應(yīng)劃去，得表2.18。表2.16計算過程表（13）b1b2行差額a1102010a21394a34151a41477a53129列差額12表2.17計算過程表（14）b1b2b3b4供應(yīng)量a11010a220a330a4201040a550需求量

15、60602010150表2.18計算過程表（15）b1b2b3b4行差額a11020572a21391281a3415793a4147101a53125192列差額1247一直重復(fù)步驟（1），（2），可得最終結(jié)果，如表2.19。表2.19調(diào)運方案表b1b2b3b4供應(yīng)量a11010a22020a330 30a410201040a5203050需求量60602010150由表2.17可知，此方案的最優(yōu)解為：1010+209+304+107+201+0+203+3012=910。由以上可見：最大差額法和最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟基本相同。最大差額法給出的初始解比用最小元素法

16、給出的初始解更接近最優(yōu)解。本例題用最大差額法給出的初始解就是最優(yōu)解繼續(xù)判別。2.3 基本可行解的最優(yōu)性檢驗最優(yōu)解的檢驗的方法是查看空格（非基變量）的檢驗數(shù)是否有不符合最優(yōu)性條件的。為此，介紹空格檢驗數(shù)的求法?；尚薪馐欠褡顑?yōu)的判別法有閉回路法、位勢法。2.3.1 位勢法位勢法是一種檢驗數(shù)的簡便方法，設(shè)是運輸問題的m+n個約束條件對應(yīng)的對偶變量，決策變量對應(yīng)的列向量，對于一個基可行解，由單純形法得知所有基變量（數(shù)字格）的檢驗數(shù)等于0，即,所以由m+n.1個數(shù)字格對應(yīng)的及即可確定所有的值。 稱分別為產(chǎn)銷平衡表各行與各列的位勢。 因為非基變量（空格）檢驗數(shù)，所以，只要計算出所有位勢值，就能求出各空格

17、的檢驗數(shù)。首先根據(jù)最大差額法得到的初始方案并假設(shè)行位勢為u，列位勢為v得到表2.20。表2.20位勢計算表（1）b1b2b3b4供應(yīng)量uia110【10】【20】【5】【7】10u1（0）a2【13】20【9】【12】【8】20u2（.10）a330【4】【15】【7】【9】30u3（.6）a4【14】10【7】20【1】10【0】40u4（.12）a520【3】30【12】【5】【19】50u5（.7）需求量60602010150viv1（10）v2（19）v3（13）v4（12）然后，計算位勢?？上冉⒎匠探M，并據(jù)此計算出運輸表各行和各列的位勢，填入表2.21中。u1+v1=10 u2+v

18、2=9 u3+v1=4 u4+v2=7 u4+v3=1 u4+v4=0 u5+v1=3 u5+v2=12由于方程數(shù)量為m+n.1個，而位勢的數(shù)量為m+n個，所以無法直接求它們的值，但由于我們想得到的只是它們的相對關(guān)系，因此我們可以假設(shè)其中一個的數(shù)值，一般為了方便計算我們可以假設(shè)u1=0.解得：u1=0 u2=.10 u3=.6 u4=.12 u5=.7 v1 =10 v2=19 v3=13 v4=12。最后計算檢驗數(shù)。有了位勢之后，即可由公式計算出各空格的檢驗數(shù)，如表2.21所示。當(dāng)所有的檢驗數(shù)都為非負(fù)時，方案即為最優(yōu)的調(diào)整方案。否則為非最優(yōu)，則需要調(diào)整。表2.21檢驗數(shù)表（1）b1b2b3b

19、4供應(yīng)量uia10【10】1【20】.8【5】.5【7】10u1（0）a213【13】0【9】9【12】6【8】20u2（.10）a30【4】2【15】0【7】3【9】30u3（.6）a416【14】0【7】0【1】0【0】40u4（.12）a50【3】0【12】.1【5】14【19】50u5（.7）需求量60602010150viv1（10）v2（19）v3（13）v4（12）當(dāng)表中空格處出現(xiàn)負(fù)檢驗數(shù)時，表明未得到最優(yōu)解。若有兩個或兩個以上的負(fù)檢驗數(shù)，一般選擇其中較小的負(fù)檢驗數(shù)，以它對應(yīng)的空格為調(diào)入格，即以它對應(yīng)的非基變量為換入變量。由表2.21得（1，3）為調(diào)入格。以此格作為出發(fā)點，作一個

20、閉合回路，調(diào)整后的運輸方案見表2.19。表2.22計算過程表（16）b1b2b3b4供應(yīng)量a12810a22020a33030a418121040a5282250需求量60602010150再進(jìn)行位勢法判斷：表2.23位勢計算表（2）b1b2b3b4供應(yīng)量uia1【10】【20】10【5】【7】10u1（0）a2【13】20【9】【12】【8】20u2（.2）a330【4】【15】【7】【9】30u3（2）a4【14】20【7】10【1】10【0】40u4（.4）a530【3】20【12】【5】【19】50u5（1）需求量60602010150viv1（2）v2（11）v3（5）v4（4）求出

21、檢驗數(shù)見表2.23。表2.24檢驗數(shù)表（1）b1b2b3b4供應(yīng)量uia18【10】9【20】0【5】3【7】10u1（0）a213【13】0【9】9【12】6【8】20u2（.2）a30【4】2【15】0【7】3【9】30u3（2）a416【14】0【7】0【1】0【0】40u4（.4）a50【3】0【12】.1【5】14【19】50u5（1）需求量60602010150viv1（2）v2（11）v3（5）v4（4）當(dāng)表中空格處出現(xiàn)負(fù)檢驗數(shù)時，表明未得到最優(yōu)解。以此格作為出發(fā)點，作一個閉合回路，調(diào)整后的運輸方案見表2.25，并算出位勢數(shù)。表2.25 位勢計算表（3）b1b2b3b4供應(yīng)量ui

22、a1【10】【20】10【5】【7】10u1（0）a2【13】20【9】【12】【8】20u2（.3）a330【4】【15】【7】【9】30u3（1）a4【14】30【7】【1】10【0】40u4（.5）a530【3】10【12】10【5】【19】50u5（0）需求量60602010150viv1（3）v2（12）v3（5）v4（5）求出檢驗數(shù)，見表2.26表2.26檢驗數(shù)表（3）b1b2b3b4供應(yīng)量uia17【10】8【20】0【5】2【7】10u1（0）a213【13】0【9】10【12】6【8】20u2（.3）a30【4】2【15】1【7】3【9】30u3（1）a416【14】0【7】

23、1【1】0【0】40u4（.5）a50【3】0【12】0【5】14【19】50u5（0）需求量60602010150viv1（3）v2（12）v3（5）v4（5）檢驗數(shù)均為非負(fù)數(shù)，所以此為最佳方案。得最小運費為：820。2.3.2 閉回路法為了確定空格（i,j）的檢驗數(shù)，可以先找出以該空格為一個頂點，其余頂點全是數(shù)字格的閉回路。所謂閉回路，就是從該空格出發(fā)，沿水平方向或垂直方向前進(jìn)，遇到合適的數(shù)字格后轉(zhuǎn)90，繼續(xù)前進(jìn)，如果能夠回到出發(fā)點，則稱這個封閉折線為閉回路。該頂點通常記為第一個頂點，為奇數(shù)位，它的下一個頂點為偶數(shù)位，下面的頂點依次奇偶相同，奇數(shù)位取正值，偶數(shù)位取負(fù)值，各數(shù)累加的和就等于（

24、i,j）格的檢驗數(shù)。 可以證明，在任何可行方案中，以空格（i,j）為一個頂點，其余頂點全是數(shù)字格的閉回路存在而且唯一。下面以最大差額法的結(jié)果為例，對表2.19所有的非基變量的檢驗數(shù)計算過程如表2.27表2.27閉合回路檢驗過程非基變量閉合回路檢驗數(shù)x12x12x52x51x11x121x21x21x22x52x51x2113x32x32x52x51x31x322x41x41x42x52x51x4116x13x13x11x51x52x42x43x13.8x14x14x11x51x52x42x44x14.5x23x23x22x42x43x239x24x24x22x42x44x246x33x33x3

25、1x51x52x42x43x330x34x34x31x51x52x42x44x343x53x53x43x42x52x53.1x54x54x44x42x52x54 14 按上述做法，可計算出表2.27中的所有非基變量的檢驗數(shù)，把它們填入相應(yīng)位置的方括號內(nèi)，如表2.28所示：表2.28非基變量檢驗數(shù)b1b2b3b4供應(yīng)量a110205710101.8.5a213912820132096a3415793030203a4147104016102010a5312519502030.114需求量60602010150表格中所有的檢驗數(shù)不均為非負(fù)，這表明該方案不是最優(yōu)，仍能調(diào)整，下面會介紹到。3 表上作業(yè)法

26、在實際中的應(yīng)用3.1 產(chǎn)銷平衡問題產(chǎn)銷平衡是指生產(chǎn)量與銷售量相同，即ai=bi。公路貨運企業(yè)時常會遇到若干貨源地向若干需求地的貨物運輸問題，供貨量與需求量不盡相同，怎樣合理組織運輸，滿足貨主的運輸要求，同時使完成運輸計劃的運輸費用最低，這是運輸業(yè)制定計劃時優(yōu)先考慮的問題。顯然，調(diào)運方案可以有很多個，但最優(yōu)方案只有一個，表上作業(yè)法可以找到這個最優(yōu)方案。表上作業(yè)法求解線性規(guī)劃問題也是取迭代選優(yōu)的辦法，即給出一個初始可行方案，經(jīng)過反復(fù)迭代，每次迭代使目標(biāo)函數(shù)有所降低（以成本為目標(biāo)函數(shù)），最后取得最優(yōu)方案。3.1.1 平衡問題模型已知有m個供應(yīng)地點，ai，i=1，2，3，,m?？晒?yīng)某種物資，其供應(yīng)量分別為ai，i=1，2，3m,有n個銷地bj，j=1，2，3，,n，其需求量分別為bj，j=1，2，3，,n。從ai到bj運輸單位物資的運價為cij這些問題可以匯總到產(chǎn)銷平衡表（3.1）和單位運價表（3.2）中。表3.1產(chǎn)銷平衡表123n產(chǎn)量1a12a23a3mam銷量b1b2b3bn表3.2單位運價表123n1c11c12c13c1n2c21c22c23c2n3c31c32c33c3nmcm1cm2cm3cmn3.2.3 數(shù)學(xué)模型的建立若用xij表示從ai到bj的用量，那么供需平衡的條件下，要求得總費用最小的調(diào)運方案，可求解一下數(shù)學(xué)模型：目標(biāo)函數(shù)： 約束條件這就是