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

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

2、物運輸提供了一種有效的方法。通過物流配送模型的建立，利用表上作業(yè)法求解最小運輸成本，解決了降低運輸成本的問題，增強了物流公司的市場競爭力。關(guān)鍵詞:貨物運輸、桌上作業(yè)、應(yīng)用案例分析。目錄TOC o 1-3 h z u HYPERLINK l _RefHeading_Toc343201300 1 緒論6 HYPERLINK l _RefHeading_Toc343201301 1.1 課題的提出6 HYPERLINK l _RefHeading_Toc343201302 1.1.1 課題背景6 HYPERLINK l _RefHeading_Toc343201303 1.1.2 課題意義6 HYP

3、ERLINK l _RefHeading_Toc343201304 2 表上作業(yè)發(fā)6 HYPERLINK l _RefHeading_Toc343201305 2.1 表上作業(yè)發(fā)的具體介紹6 HYPERLINK l _RefHeading_Toc343201306 2.2 確定初始基本可行解8 HYPERLINK l _RefHeading_Toc343201307 2.1.1 最小元素法8 HYPERLINK l _RefHeading_Toc343201308 2.2.2 西北角法11 HYPERLINK l _RefHeading_Toc343201309 2.2.3 伏格爾法（Voge

4、l）11 HYPERLINK l _RefHeading_Toc343201310 2.3 基本可行解的最優(yōu)性檢驗16 HYPERLINK l _RefHeading_Toc343201311 2.3.1 位勢法16 HYPERLINK l _RefHeading_Toc343201312 2.3.2 閉回路法20 HYPERLINK l _RefHeading_Toc343201313 3 表上作業(yè)法在實際中的應(yīng)用22 HYPERLINK l _RefHeading_Toc343201314 3.1 產(chǎn)銷平衡問題22 HYPERLINK l _RefHeading_Toc343201315

5、3.1.1 平衡問題模型23 HYPERLINK l _RefHeading_Toc343201316 3.2.3 數(shù)學(xué)模型的建立23 HYPERLINK l _RefHeading_Toc343201317 3.2 產(chǎn)銷不平衡問題24 HYPERLINK l _RefHeading_Toc343201318 4 總結(jié)24 HYPERLINK l _RefHeading_Toc343201319 參考文獻(xiàn)261導(dǎo)言1.1課題的提出1.1.1課題的背景交通是當(dāng)今社會經(jīng)濟(jì)生活中的一個普遍問題。在經(jīng)濟(jì)建設(shè)中，物資的運輸經(jīng)常發(fā)生。如何制定運輸計劃，將物資運送到指定地點，實現(xiàn)運輸成本最小，就是運輸問題。

6、運輸問題是一個特殊的線性規(guī)劃問題，是當(dāng)前網(wǎng)絡(luò)優(yōu)化的一個例子。不同于一般的線性規(guī)劃問題，其約束方程的系數(shù)矩陣具有特殊的結(jié)構(gòu)，這就要求用不同的甚至更簡單的方法來解決這種實際工作中遇到的問題。運輸問題代表了物資和車輛的合理分配。其他類型的問題，經(jīng)過一系列的變化，也可以歸結(jié)為運輸問題。1.1.2主題的意義交通問題是當(dāng)今經(jīng)濟(jì)建設(shè)中非常普遍的問題。運輸問題和運輸成本的優(yōu)化是運輸企業(yè)在制定運輸計劃時必須考慮的問題。如何選擇合理的運輸方案，使運輸成本最小化，非常關(guān)鍵。作業(yè)法可以很好地解決這類問題。本文的主要目的是系統(tǒng)全面地研究表格操作方法。2桌子上的作業(yè)2.1具體介紹作業(yè)表手術(shù)臺上的單純形法是求解運輸問題的一

7、種簡化方法。其本質(zhì)是單純形法，但具體計算和術(shù)語不同。從運費最低的箱子開始，在箱子的右下角標(biāo)出允許的最大數(shù)量。然后按照運費從小到大的順序填寫數(shù)字。如果某一行(列)的產(chǎn)量(銷售量)已經(jīng)達(dá)到，則劃掉該行(列)的其他方框。這樣做，直到獲得一個基本可行的解決方案。這種方法的基本思想是就近供應(yīng)，即從運價表中的最小運價確定運輸數(shù)量，再到下一個最小值，直到給出初始運輸方案?？梢钥偨Y(jié)如下:(1)找出基本可行的方案。即在產(chǎn)銷平衡表(m*n)上，用西北角法或最小元素法和Vogel法給出m+n.1個數(shù)，稱為數(shù)格。它是初始基本變量的值。(2)求每個非基本變量的檢驗數(shù)，即在表上記錄空格的檢驗數(shù)，判斷是否達(dá)到最優(yōu)解。如果是

8、，停止計算，否則進(jìn)行下一步。(3)確定轉(zhuǎn)入變量和轉(zhuǎn)出變量，找出新的基本可行解，在表上用閉環(huán)法調(diào)整。(4)重復(fù)(2)和(3)，直到獲得最優(yōu)解。以下工作通過實際原材料研究形式進(jìn)行分配:有五個產(chǎn)地A1、A2、A3、A4、A5和四個銷售地B1、B2、B3、B4。它們的供應(yīng)、需求和單位運費如下。表2.1供需和單位運費B1B2B3B4供應(yīng)量A110205710A213912820A34157930A41471040A531251950需求量60602010150表2.2供應(yīng)和需求B1B2B3B4供應(yīng)量A110A220A330A440A550需求量606020101502.2確定初始基本可行方案。確定初始基

9、本可行解的一般方法簡單，且盡可能接近最優(yōu)解。下面介紹最小元素法和Vogel法。最小元素法最小要素法的基本思想是就近供應(yīng)，即從最低運費率開始確定供銷關(guān)系，然后次小。直到給出初步的基本可行方案，再以上述材料為例進(jìn)行討論。(1)從表2.1中查得最小運費率為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計算過程表(二)B1B2B3

10、B4供應(yīng)量A110205710A213912820A34157930A41471040A531251950需求量60602010150(2)在表2.4中，找到最小運費率1后，確定A4中剩余30臺供應(yīng)B3，滿足B3的需求多10臺，得到表2.5。將表2.1中的B3劃掉，得到表2.6。表2.5計算過程表(三)B1B2B3B4供應(yīng)量A110A220A330A4201040A550需求量60602010150表2.6計算過程表(4)B1B2B3B4供應(yīng)量A110205710A213912820A34157930A41471040A531251950需求量60602010150(3)從表2.6中查得最小運

11、費率為3。A5b1，所以A5中的50個全部供應(yīng)給b1，還缺10個需求?，F(xiàn)在從表中找到4的最小運費，B1只需要10，于是A3停止向BI供應(yīng)10，還剩下20，于是表2.7。在表2.6中，B1列被劃掉，由于A5中的所有項目都已供應(yīng)，所以它們都被劃掉，于是得到表2.8。表2.7計算過程表(5)B1B2B3B4供應(yīng)量A110A220A31030A4201040A55050需求量60602010150表2.8計算過程表(6)B1B2B3B4供應(yīng)量A110205710A213912820A34157930A41471040A531251950需求量60602010150(4)目前只有B2的需求沒有得到滿足，

12、所以A1、A2、A3、A4全部供應(yīng)給B2，正好滿足全部供需，從而達(dá)到表2.9。表2.9運輸方案表B1B2B3B4供應(yīng)量A11010A22020A3102030A410201040A55050需求量60602010150從表2.8可以看出，該方案的總成本為1020+209+104+2015+107+201+0+503 = 960。2.2.2西北角法從西北角(左上角)開始，在網(wǎng)格的右下角標(biāo)出允許的最大數(shù)量。然后逐行(列)標(biāo)記下一個網(wǎng)格的編號。如果某一行(列)的產(chǎn)量(銷售量)已經(jīng)達(dá)到，則劃掉該行(列)的其他方框。這樣做，直到獲得一個基本可行的解決方案。西北角法的基本思想是將運輸量分配到產(chǎn)銷平衡表左上

13、角的變量中，從而確定產(chǎn)銷關(guān)系，以此類推，直到給出初始可行方案。求解步驟如下:(1)首先確定產(chǎn)銷平衡表左上角變量的值。使該變量取盡可能大的值，即在該變量對應(yīng)的數(shù)值框中填入該變量取的值。(2)如果是，在L行空格處打“”，這些空格將不再分配；如果是，在K欄的空格處打“”，這些空格將不再分配；如果=，在行空格中標(biāo)記“X”后，不能在列空格中標(biāo)記“X”。相反，如果你在列空間標(biāo)記了“X ”,你就不會在行空間標(biāo)記“X”。(3)對表格上沒有“x”的地方重復(fù)步驟(1)和(2)，直到所有單元格都被標(biāo)記。可以證明，用西北角法確定的初始方案是運輸問題的初始基可行解，它只包含m+n.1個數(shù)字格。沃格爾法最大差值法對于一行

14、或一列整體考慮，會更合理。如果一個產(chǎn)地的產(chǎn)品不能按照最低運費就近供貨，就會考慮第二個最低運費，會有差價。差價越大，運輸量增加越多，運費增加越多。所以應(yīng)該優(yōu)先選擇差價最大的地方，用最少的運費進(jìn)行運輸。最大差值法的具體步驟如下:(1)在表2.1中，計算每一行和每一列的最低運費與下一個最低運費之差，填入表格的最右列和最低行，如表2.10所示。表2.10計算過程表(7)B1B2B3B4行差額A11020572A21391281A3415793A4147101A53125192列差額1247(2)選擇行或列之間的最大差異，并選擇其所在行或列中的最小元素。在表2.10中，B4列是差異最大的列。B4列的最小

15、元素為0，可以確定A4產(chǎn)品需要先供應(yīng)B4。得到表2.11。當(dāng)滿足B4的要求時，在表2.11中劃掉B4，得到表2.12。表2.11計算過程表(8)B1B2B3B4供應(yīng)量A110A220A330A41040A550需求量60602010150表2.12計算過程表(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。當(dāng)B

16、3的需求得到滿足時，在表2.12中劃掉B3，得到表2.15。2.13計算過程表(10)B1B2B3行差額A1102055A2139123A341573A414716A531252列差額124表2.14計算過程表(11)B1B2B3B4供應(yīng)量A110A220A330A4201040A550需求量60602010150表2.15計算過程表(12)B1B2B3B4行差額A11020572A21391281A3415793A4147101A53125192列差額1247(4)表2.15中未劃掉的元素正在計算得到表2.16。重復(fù)步驟(1)和(2)得到表2.17。由于提供了所有的A1，應(yīng)將其劃掉，得到表2

17、.18。表2.16計算過程表(13)B1B2行差額A1102010A21394A34151A41477A53129列差額12表2.17計算過程表(14)B1B2B3B4供應(yīng)量A11010A220A330A4201040A550需求量60602010150表2.18計算過程表(15)B1B2B3B4行差額A11020572A21391281A3415793A4147101A53125192列差額1247重復(fù)步驟(1)和(2)獲得最終結(jié)果，如表2.19所示。表2.19運輸方案表B1B2B3B4供應(yīng)量A11010A22020A330 30A410201040A5203050需求量6060201015

18、0從表2.17可以看出，該方案的最優(yōu)解為:1010+209+304+107+201+0+203+3012 = 910。從上面可以看出，最大差值法和最小元素法除了在確定供求關(guān)系的原則上有所不同之外，基本相同。最大差分法給出的初始解比最小元法給出的更接近最優(yōu)解。在這個例子中，最大差分法給出的初始解就是最優(yōu)解。2.3基本可行解的最優(yōu)性檢驗最優(yōu)解的檢驗方法是檢驗空間(非基變量)的檢驗數(shù)是否不滿足最優(yōu)性條件。為此，本文介紹了尋找空白試驗次數(shù)的方法。判斷可行解是否最優(yōu)有閉環(huán)法和位勢法。潛在方法位勢法是檢驗數(shù)字的一種簡單方法。假設(shè)對偶變量對應(yīng)m+n個約束，列向量對應(yīng)運輸問題的決策變量。對于一個基本可行解，用

19、單純形法已知所有基本變量(數(shù)字格)的檢驗數(shù)都等于0，即所有值都可以由m+n.1個數(shù)字格對應(yīng)的和來確定。叫做產(chǎn)銷平衡表中每一行每一列的潛力。因為非基本變量(空間)測試數(shù)，只要計算出所有的勢值，就可以得到每個空間的測試數(shù)。首先根據(jù)最大差分法得到的初始方案，假設(shè)行電位為U，列電位為V，得到表2.20。表2.20潛力計算表(1)B1B2B3B4供應(yīng)量uiA11010205710A21320912820A3304157930A41410720110040A5203301251950需求量60602010150vi然后，計算勢?？梢韵冉⒎匠探M，然后計算出輸運表各行各列的電位，填入表2.21。u1+v1=

20、10u2+v2=9u3+v1=4u4+v2=7u4+v3=1u4+v4=0u5+v1=3u5+v2=12因為方程的個數(shù)是m+n.1，勢的個數(shù)是m+n，所以不能直接求它們的值，但是因為我們要的只是它們的相對關(guān)系，所以可以假設(shè)其中一個的值。一般為了計算方便，我們可以假設(shè)u1=0。解決方法是:u1 = 0u2 = .10u3 = .6u4 = .12u5 = .7。最后，計算測試次數(shù)。有了電位，就可以通過公式計算出每個空間的測試次數(shù)，如表2.21所示。當(dāng)所有測試數(shù)均為非負(fù)時，該方案為最優(yōu)調(diào)整方案。否則就是非最優(yōu)，需要調(diào)整。表2.21檢驗表(1)B1B2B3B4供應(yīng)量uiA1010120.85.571

21、0A21313099126820A304215073930UA4161407010040UA503012.15141950需求量60602010150vi當(dāng)表中空白處出現(xiàn)負(fù)的測試數(shù)時，表示沒有得到最優(yōu)解。如果有兩個或兩個以上的負(fù)測試數(shù)，一般選擇較小的負(fù)測試數(shù)，將其對應(yīng)的空間作為轉(zhuǎn)入格，即將其對應(yīng)的非基變量作為轉(zhuǎn)入變量。表2.21中的(1，3)是轉(zhuǎn)入單元格。以這個網(wǎng)格為起點，做一個閉環(huán)。調(diào)整后的運輸方案見表2.19。表2.22計算過程表(16)B1B2B3B4供應(yīng)量A12810A22020A33030A418121040A5282250需求量60602010150再做一個潛在的方法判斷:表2.2

22、3潛力計算表(二)B1B2B3B4供應(yīng)量uiA11020105710A21320912820A3304157930u3（2）A41420710110040u4（.4）A5303201251950u5（1）quantity demanded60602010150viv1（2）v2（11）v3（5）v4（4）測試編號見表2.23。表2.24檢驗表(1)B1B2B3B4Supply用戶界面一流的810920053710u1(0)主動脈第二聲1313099126820u2(.2)A3號04215073930u3(2)A4號161407010040u4(.4)A5號03012.15141950u5(1)

23、需求數(shù)量60602010150視覺識別系統(tǒng)v1(2)v2(11)v3(5)第4版當(dāng)表中空白處出現(xiàn)負(fù)的測試數(shù)時，表示沒有得到最優(yōu)解。以這個網(wǎng)格為起點，做一個閉環(huán)。調(diào)整后的運輸方案見表2.25，并計算潛在數(shù)量。表2.25潛力計算表(三)B1B2B3B4供應(yīng)用戶界面一流的1020105710u1(0)主動脈第二聲1320912820u2(.3)A3號304157930u3(1)A44(.5)A5號30310121051950u5(0)需求數(shù)量60602010150視覺識別系統(tǒng)v1(3)v2(12)v3(5)第四版(第五版)檢查次數(shù)見表2.26。表2.26檢驗表(三)B1B2

24、B3B4供應(yīng)用戶界面一流的710820052710u1(0)主動脈第二聲13130910126820u2(.3)A3號04215173930u3(1)A4號161407110040u4(.5)A5號0301205141950u5(0)需求數(shù)量60602010150視覺識別系統(tǒng)v1(3)v2(12)v3(5)第四版(第五版)測試數(shù)字都是非負(fù)的，所以這是最好的方案。最低運費:820。閉環(huán)方法為了確定空間(I，j)的測試數(shù)，可以先找出以這個空間為頂點的閉環(huán)，其余頂點都是數(shù)字格。所謂閉環(huán)，就是從空白處開始，沿水平或垂直方向移動，遇到合適的數(shù)字格后轉(zhuǎn)90，繼續(xù)前進(jìn)。如果能回到起點，這條閉合的折線就叫閉環(huán)

25、。這個頂點通常記為第一個頂點，它是奇數(shù)，它的下一個頂點是偶數(shù)，后面的頂點依次是偶數(shù)和奇數(shù)。奇數(shù)取正值，偶數(shù)取負(fù)值。這些數(shù)的累加和等于(I，j)格的測試數(shù)?？梢宰C明在任何可行的方案中，以空間(I，j)為頂點，其他所有頂點都是數(shù)字格的閉環(huán)存在且唯一。以最大差值法的結(jié)果為例，表2.19中所有非基本變量的檢驗數(shù)的計算過程如表2.27所示。表2.27閉環(huán)檢驗流程非基本變量通路檢驗數(shù)X12X12X52X51X11X12一個X21X21X22X52X51X2113X32X32X52X51X31X322X41X41X42X52X51X4116X13X13X11X51X52X42X43X13.8X14X14X1

26、1X51X52X42X44X14.5X23X23X22X42X43X23九X24X24X22X42X44X24六X33X33X31X51X52X42X43X330X34X34X31X51X52X42X44X34三X53X53X43X42X52X53.1X54X54X44X42X52X5414根據(jù)上述做法，可以計算出表2.27中所有非基本變量的測試數(shù)，并將其填入相應(yīng)位置的方括號內(nèi)，如表2.28所示:表2.28非基本變量測試數(shù)B1B2B3B4供應(yīng)一流的1020五七10101.8.5主動脈第二聲13九12八20132096A3號四15七九3030203A4號14七一個04016102010A5號三1

27、2五19502030.114需求數(shù)量60602010150表中所有測試數(shù)均為非負(fù)，說明該方案不是最優(yōu)的，仍可調(diào)整，下面將介紹。3表格操作法在實踐中的應(yīng)用3.1生產(chǎn)和銷售之間的平衡產(chǎn)銷平衡是指生產(chǎn)量與銷售量相同，即ai=bi。公路貨運企業(yè)經(jīng)常會遇到貨物從幾個貨源地運輸?shù)綆讉€需求地的問題。供應(yīng)的貨物數(shù)量與需求不一樣。如何合理地組織運輸，滿足業(yè)主的運輸要求，同時使完成運輸計劃的運輸成本最低，是運輸行業(yè)在制定計劃時優(yōu)先考慮的問題。顯而易見，調(diào)度方案有很多，但最優(yōu)方案只有一個，可以用表運算法找到。表基法也是求解線性規(guī)劃問題的一種迭代優(yōu)化方法，即給出一個初始可行方案。經(jīng)過反復(fù)迭代，在每次迭代中減少目標(biāo)函數(shù)(以費用為目標(biāo)函數(shù))，最終得到最優(yōu)方案。平衡問題模型已知m個供應(yīng)地點，ai，i=1，2，3，m，可以供應(yīng)某一種物料，分別有Ai，i=1，2，3m，N個銷售地點bj，j=1，2，3，N的供應(yīng)量，和Bj，j=1，2，3，N的需求量。從Ai到Bj運輸單位物料的運費為cij。這些問題可以歸納在產(chǎn)銷平衡表(3.1)和單位運價表(3.2)中。表3.1產(chǎn)銷平衡表一個2三n產(chǎn)量一個第一等的2主動脈第二聲三a3m是銷售量b1b2b3十億表3.2單位運費率一個2三n一個C11C12C13C1n2C21C22C23C2n三C31C32C33C3nmCm1