表上作業(yè)法在貨物運(yùn)輸組織中的應(yīng)用分析

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

2、的必由之路。本文利用表上作業(yè)法求得了貨物運(yùn)輸組織中的最小費(fèi)原理，解決了物流公司在貨物運(yùn)輸中所存在的問題，為物流公司的貨物運(yùn)輸提供了一種行之有效的方法。通過建立物流配送模型，利用表上作業(yè)法解出最小運(yùn)輸成本，解決了降低運(yùn)輸成本問題，提升了物流公司的市場競爭力。 關(guān)鍵詞：貨物運(yùn)輸，表上作業(yè)發(fā)，應(yīng)用實(shí)例分析。目錄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)性檢驗(yàn)162.3.1 位勢法162.

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

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

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

6、4、A5和4個(gè)銷地B1、B2、B3、B4的運(yùn)輸問題，他們的供應(yīng)量和需求量及單位運(yùn)費(fèi)如下表。表2.1供應(yīng)量和需求量及單位運(yùn)費(fèi)B1B2B3B4供應(yīng)量A110205710A213912820A34157930A41471040A531251950需求量60602010150表2.2供應(yīng)量和需求量B1B2B3B4供應(yīng)量A110A220A330A440A550需求量606020101502.2 確定初始基本可行解確定初始基本可行解一般的方法是既簡便，有盡可能接近最優(yōu)解，下面介紹最小元素法和Vogel法。 最小元素法最小元素法的基本思想就是就近供應(yīng)，即從最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小。一直到給出初始

7、基本可行解，以上述材料為例進(jìn)行討論。（1）從表2.1中找出最小運(yùn)價(jià)為0，這表示先將A4的產(chǎn)品供應(yīng)給B4，因?yàn)閍4>b4A4除滿足B4的需求外，還可多余30的產(chǎn)品。在表2.2中的（A4,B4）的交叉處填上10，得表2.3。并將表2.1的B4列劃去，得表2.4。表2.3計(jì)算過程表（1）B1B2B3B4供應(yīng)量A110A220A330A41040A550需求量60602010150表2.4計(jì)算過程表（2）B1B2B3B4供應(yīng)量A110205710A213912820A34157930A41471040A531251950需求量60602010150 （2）在表2.4中在找出最小的運(yùn)價(jià)1，確定A4

8、中剩余30供應(yīng)給B3，滿足B3的需求量還多出10，并得出表2.5。并劃去表2.1中的B3，得表2.6表2.5計(jì)算過程表（3）B1B2B3B4供應(yīng)量A110A220A330A4201040A550需求量60602010150表2.6計(jì)算過程表（4）B1B2B3B4供應(yīng)量A110205710A213912820A34157930A41471040A531251950需求量60602010150（3）在表2.6中找出最小運(yùn)價(jià)為3。a5<b1,所以A5里面的50全部供應(yīng)給B1,還缺少10需求量，在從表中找出最小運(yùn)價(jià)4，而B1只需求10，因此A3中止供應(yīng)10給BI，還剩余20，由此的表2.7。在表

9、2.6中劃去B1列，由于A5里的均已供應(yīng)完，均劃去，得表2.8。表2.7計(jì)算過程表（5）B1B2B3B4供應(yīng)量A110A220A31030A4201040A55050需求量60602010150表2.8計(jì)算過程表（6）B1B2B3B4供應(yīng)量A110205710A213912820A34157930A41471040A531251950需求量60602010150（4）現(xiàn)在只有B2的需求沒有滿足，所以A1,A2,A3,A4的全部供應(yīng)給B2，剛好滿足所有的供需量，由此的到表2.9。表2.9調(diào)運(yùn)方案表B1B2B3B4供應(yīng)量A11010A22020A3102030A410201040A55050需求量

10、60602010150由表2.8可知，此方案的總費(fèi)用為1O×20+20×9+10×4+20×15+10×7+20×1+0+50×3=960. 西北角法從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。 西北角法的基本思想是給產(chǎn)銷平衡表左上角的變量分配運(yùn)輸量，以確定產(chǎn)銷關(guān)系，依此類推，一直到給出初始可行方案為止。求解步驟如下：（1）先決定產(chǎn)銷平衡表左上角變量 的值。令這個(gè)變量取盡可能大的值

11、，即 ，在這個(gè)變量對應(yīng)的數(shù)字格填上變量所取的值。（2）若，則在第L行空格處打“×”，這些空格不再賦值；若，則在第K列空格處打“×”，這些空格不再賦值；若=，則在行的空格處打“×”后，就不能在列的空格處打“×”，反之，若在列的空格處打“×”，就不在行空格處打“×”。（3）對表上沒有打“×”的地方重復(fù)（1）， （2）步，直到所有格子都有標(biāo)記止。 可以證明，用西北角法確定的初始方案是運(yùn)輸問題的一個(gè)初始基可行解，它也恰好包含m+n.1個(gè)數(shù)字格。 伏格爾法（Vogel）最大差額法是一行或一列的整體出發(fā)考慮，會更加合理。一產(chǎn)地的產(chǎn)品假如

12、不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)差額。差額越大，說明不能按最小費(fèi)用調(diào)運(yùn)時(shí)，運(yùn)輸量就會加多從而運(yùn)費(fèi)增加越多。因而對差額最大處，要優(yōu)先考慮，應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。最大差額法的具體步驟如下：（1）在表2.1中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，見表2.10。表2.10計(jì)算過程表（7）B1B2B3B4行差額A11020572A21391281A3415793A4147101A53125192列差額1247（2）從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表2.10中B4列是最大差額所在列。B4列最小元素為0，可確定A4產(chǎn)品先供應(yīng)B

13、4的需要。得表2.11。B4的需求量滿足時(shí)，則在表2.11中劃去B4，得表2.12。表2.11計(jì)算過程表（8）B1B2B3B4供應(yīng)量A110A220A330A41040A550需求量60602010150表2.12計(jì)算過程表（9）B1B2B3B4行差額A11020572A21391281A3415793A4147101A53125192列差額1247（3）在表2.12中，未劃去的行和列中再分別計(jì)算出行差額和列差額，得表2.13。在表2.13中，A4為最大差額所在行，所對應(yīng)的最小元素為B3列，則A4的成品供應(yīng)給B3，A3里還有30個(gè)，B3需求30個(gè)，得表2.14。B3中的需求滿足時(shí)，在表2.12

14、中劃去B3，得表2.15。2.13計(jì)算過程表（10）B1B2B3行差額A1102055A2139123A341573A414716A531252列差額124表2.14計(jì)算過程表（11）B1B2B3B4供應(yīng)量A110A220A330A4201040A550需求量60602010150表2.15計(jì)算過程表（12）B1B2B3B4行差額A11020572A21391281A3415793A4147101A53125192列差額1247（4）在表2.15中，未劃去的元素在進(jìn)行計(jì)算出行差額和列差額，得表2.16.重復(fù)步驟（1），（2），可得表2.17。由于A1中的一全部供應(yīng)完，則應(yīng)劃去，得表2.18。表

15、2.16計(jì)算過程表（13）B1B2行差額A1102010A21394A34151A41477A53129列差額12表2.17計(jì)算過程表（14）B1B2B3B4供應(yīng)量A11010A220A330A4201040A550需求量60602010150表2.18計(jì)算過程表（15）B1B2B3B4行差額A11020572A21391281A3415793A4147101A53125192列差額1247一直重復(fù)步驟（1），（2），可得最終結(jié)果，如表2.19。表2.19調(diào)運(yùn)方案表B1B2B3B4供應(yīng)量A11010A22020A330 30A410201040A5203050需求量60602010150由表2

16、.17可知，此方案的最優(yōu)解為：10×10+20×9+30×4+10×7+20×1+0+20×3+30×12=910。由以上可見：最大差額法和最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟基本相同。最大差額法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。本例題用最大差額法給出的初始解就是最優(yōu)解繼續(xù)判別。2.3 基本可行解的最優(yōu)性檢驗(yàn)最優(yōu)解的檢驗(yàn)的方法是查看空格（非基變量）的檢驗(yàn)數(shù)是否有不符合最優(yōu)性條件的。為此，介紹空格檢驗(yàn)數(shù)的求法。基可行解是否最優(yōu)的判別法有閉回路法、位勢法。 位勢法位勢法是一種檢驗(yàn)數(shù)的簡便方法，設(shè)是

17、運(yùn)輸問題的m+n個(gè)約束條件對應(yīng)的對偶變量，決策變量對應(yīng)的列向量，對于一個(gè)基可行解，由單純形法得知所有基變量（數(shù)字格）的檢驗(yàn)數(shù)等于0，即,所以由m+n.1個(gè)數(shù)字格對應(yīng)的及即可確定所有的值。 稱分別為產(chǎn)銷平衡表各行與各列的位勢。 因?yàn)榉腔兞浚崭瘢z驗(yàn)數(shù)，所以，只要計(jì)算出所有位勢值，就能求出各空格的檢驗(yàn)數(shù)。首先根據(jù)最大差額法得到的初始方案并假設(shè)行位勢為u，列位勢為v得到表2.20。表2.20位勢計(jì)算表（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】

18、10【7】20【1】10【0】40u4（.12）A520【3】30【12】【5】【19】50u5（.7）需求量60602010150viv1（10）v2（19）v3（13）v4（12）然后，計(jì)算位勢。可先建立方程組，并據(jù)此計(jì)算出運(yùn)輸表各行和各列的位勢，填入表2.21中。u1+v1=10 u2+v2=9 u3+v1=4 u4+v2=7 u4+v3=1 u4+v4=0 u5+v1=3 u5+v2=12由于方程數(shù)量為m+n.1個(gè)，而位勢的數(shù)量為m+n個(gè)，所以無法直接求它們的值，但由于我們想得到的只是它們的相對關(guān)系，因此我們可以假設(shè)其中一個(gè)的數(shù)值，一般為了方便計(jì)算我們可以假設(shè)u1=0.解得：u1=0

19、u2=.10 u3=.6 u4=.12 u5=.7 v1 =10 v2=19 v3=13 v4=12。最后計(jì)算檢驗(yàn)數(shù)。有了位勢之后，即可由公式計(jì)算出各空格的檢驗(yàn)數(shù)，如表2.21所示。當(dāng)所有的檢驗(yàn)數(shù)都為非負(fù)時(shí)，方案即為最優(yōu)的調(diào)整方案。否則為非最優(yōu)，則需要調(diào)整。表2.21檢驗(yàn)數(shù)表（1）B1B2B3B4供應(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）需

20、求量60602010150viv1（10）v2（19）v3（13）v4（12）當(dāng)表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表明未得到最優(yōu)解。若有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)數(shù)，一般選擇其中較小的負(fù)檢驗(yàn)數(shù)，以它對應(yīng)的空格為調(diào)入格，即以它對應(yīng)的非基變量為換入變量。由表2.21得（1，3）為調(diào)入格。以此格作為出發(fā)點(diǎn)，作一個(gè)閉合回路，調(diào)整后的運(yùn)輸方案見表2.19。表2.22計(jì)算過程表（16）B1B2B3B4供應(yīng)量A12810A22020A33030A418121040A5282250需求量60602010150再進(jìn)行位勢法判斷：表2.23位勢計(jì)算表（2）B1B2B3B4供應(yīng)量uiA1【10】【20】10【5】【7】10u1

21、（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）求出檢驗(yàn)數(shù)見表2.23。表2.24檢驗(yàn)數(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

22、【12】.1【5】14【19】50u5（1）需求量60602010150viv1（2）v2（11）v3（5）v4（4）當(dāng)表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表明未得到最優(yōu)解。以此格作為出發(fā)點(diǎn)，作一個(gè)閉合回路，調(diào)整后的運(yùn)輸方案見表2.25，并算出位勢數(shù)。表2.25 位勢計(jì)算表（3）B1B2B3B4供應(yīng)量uiA1【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）

23、v2（12）v3（5）v4（5）求出檢驗(yàn)數(shù)，見表2.26表2.26檢驗(yàn)數(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】1【1】0【0】40u4（.5）A50【3】0【12】0【5】14【19】50u5（0）需求量60602010150viv1（3）v2（12）v3（5）v4（5）檢驗(yàn)數(shù)均為非負(fù)數(shù)，所以此為最佳方案。得最小運(yùn)費(fèi)為：820。2.3.2 閉回路法為了確定空格（i,j）的檢驗(yàn)數(shù)，可以先找出以該空格為一個(gè)頂點(diǎn)，其

24、余頂點(diǎn)全是數(shù)字格的閉回路。所謂閉回路，就是從該空格出發(fā)，沿水平方向或垂直方向前進(jìn)，遇到合適的數(shù)字格后轉(zhuǎn)90°，繼續(xù)前進(jìn)，如果能夠回到出發(fā)點(diǎn)，則稱這個(gè)封閉折線為閉回路。該頂點(diǎn)通常記為第一個(gè)頂點(diǎn)，為奇數(shù)位，它的下一個(gè)頂點(diǎn)為偶數(shù)位，下面的頂點(diǎn)依次奇偶相同，奇數(shù)位取正值，偶數(shù)位取負(fù)值，各數(shù)累加的和就等于（i,j）格的檢驗(yàn)數(shù)。 可以證明，在任何可行方案中，以空格（i,j）為一個(gè)頂點(diǎn)，其余頂點(diǎn)全是數(shù)字格的閉回路存在而且唯一。下面以最大差額法的結(jié)果為例，對表2.19所有的非基變量的檢驗(yàn)數(shù)計(jì)算過程如表2.27表2.27閉合回路檢驗(yàn)過程非基變量閉合回路檢驗(yàn)數(shù)X12X12X52X51X11X121X21

25、X21X22X52X51X2113X32X32X52X51X31X322X41X41X42X52X51X4116X13X13X11X51X52X42X43X13.8X14X14X11X51X52X42X44X14.5X23X23X22X42X43X239X24X24X22X42X44X246X33X33X31X51X52X42X43X330X34X34X31X51X52X42X44X343X53X53X43X42X52X53.1X54X54X44X42X52X54 14 按上述做法，可計(jì)算出表2.27中的所有非基變量的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的方括號內(nèi)，如表2.28所示：表2.28非基變量檢

26、驗(yàn)數(shù)B1B2B3B4供應(yīng)量A110205710101.8.5A213912820132096A3415793030203A4147104016102010A5312519502030.114需求量60602010150表格中所有的檢驗(yàn)數(shù)不均為非負(fù)，這表明該方案不是最優(yōu)，仍能調(diào)整，下面會介紹到。3 表上作業(yè)法在實(shí)際中的應(yīng)用3.1 產(chǎn)銷平衡問題產(chǎn)銷平衡是指生產(chǎn)量與銷售量相同，即ai=bi。公路貨運(yùn)企業(yè)時(shí)常會遇到若干貨源地向若干需求地的貨物運(yùn)輸問題，供貨量與需求量不盡相同，怎樣合理組織運(yùn)輸，滿足貨主的運(yùn)輸要求，同時(shí)使完成運(yùn)輸計(jì)劃的運(yùn)輸費(fèi)用最低，這是運(yùn)輸業(yè)制定計(jì)劃時(shí)優(yōu)先考慮的問題。顯然，調(diào)運(yùn)方案可以有

27、很多個(gè)，但最優(yōu)方案只有一個(gè)，表上作業(yè)法可以找到這個(gè)最優(yōu)方案。表上作業(yè)法求解線性規(guī)劃問題也是取迭代選優(yōu)的辦法，即給出一個(gè)初始可行方案，經(jīng)過反復(fù)迭代，每次迭代使目標(biāo)函數(shù)有所降低（以成本為目標(biāo)函數(shù)），最后取得最優(yōu)方案。 平衡問題模型已知有M個(gè)供應(yīng)地點(diǎn)，Ai，i=1，2，3，,m。可供應(yīng)某種物資，其供應(yīng)量分別為ai，i=1，2，3m,有N個(gè)銷地Bj，j=1，2，3，,n，其需求量分別為bj，j=1，2，3，,n。從Ai到Bj運(yùn)輸單位物資的運(yùn)價(jià)為cij這些問題可以匯總到產(chǎn)銷平衡表（3.1）和單位運(yùn)價(jià)表（3.2）中。表3.1產(chǎn)銷平衡表123n產(chǎn)量1a12a23a3mam銷量b1b2b3bn表3.2單位運(yùn)價(jià)表123n1C11C12C13C1n2C21C22C23C2n3C31C32C33C3nmCm1Cm2Cm3Cmn 數(shù)學(xué)模型的建立若用xij表示從Ai到Bj的用量，那么供需平衡的條件下，要求得總費(fèi)用最小的調(diào)運(yùn)方案，可求解一下數(shù)學(xué)模型：目標(biāo)函數(shù)： 約束