表上作業(yè)法.doc

表上作業(yè)法 什么是表上作業(yè)法表上作業(yè)法是指用列表的方法求解線性規(guī)劃問(wèn)題中運(yùn)輸模型的計(jì)算方法。是線性規(guī)劃一種求解方法。當(dāng)某些線性規(guī)劃問(wèn)題采用圖上作業(yè)法難以進(jìn)行直觀求解時(shí)，就可以將各元素列成相關(guān)表，作為初始方案，然后采用檢驗(yàn)數(shù)來(lái)驗(yàn)證這個(gè)方案，否則就要采用閉合回路法、位勢(shì)法等方法進(jìn)行調(diào)整，直至得到滿(mǎn)意的結(jié)果。這種列表求解方法就是表上作業(yè)法。 編輯表上作業(yè)法的步驟11、找出初始基本可行解（初始調(diào)運(yùn)方案，一般m+n-1個(gè)數(shù)字格），用西北角法、最小元素法； （1）西北角法： 從西北角（左上角）格開(kāi)始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷(xiāo)量）已滿(mǎn)足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。 （2）最小元素法： 從運(yùn)價(jià)最小的格開(kāi)始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價(jià)從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷(xiāo)量）已滿(mǎn)足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。 注:應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列，只有最后一個(gè)元例外（同時(shí)劃去一行和一列）。當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行（列），在保留的列（行）中沒(méi)被劃去的格內(nèi)標(biāo)一個(gè)0。 2、求出各非基變量的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如果是停止計(jì)算，否則轉(zhuǎn)入下一步，用位勢(shì)法計(jì)算； 運(yùn)輸問(wèn)題的約束條件共有m+n個(gè)，其中：m是產(chǎn)地產(chǎn)量的限制；n是銷(xiāo)地銷(xiāo)量的限制。其對(duì)偶問(wèn)題也應(yīng)有m+n個(gè)變量，據(jù)此： ij = cij (ui + vj) ,其中前m個(gè)計(jì)為,前n個(gè)計(jì)為 由單純形法可知，基變量的ij = 0 cij (ui + vj) = 0因此ui,vj可以求出。 3、改進(jìn)當(dāng)前的基本可行解（確定換入、換出變量），用閉合回路法調(diào)整； （因?yàn)槟繕?biāo)函數(shù)要求最小化） 表格中有調(diào)運(yùn)量的地方為基變量，空格處為非基變量?；兞康臋z驗(yàn)數(shù)ij = 0，非基變量的檢驗(yàn)數(shù)。ij 0表示運(yùn)費(fèi)增加。 4、重復(fù)，直到找到最優(yōu)解為止。 編輯表上作業(yè)法計(jì)算中的問(wèn)題1、無(wú)窮多最優(yōu)解 產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解。如果非基變量的ij = 0，則該問(wèn)題有無(wú)窮多最優(yōu)解。 2、退化 表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)，在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證有(m+n-1)個(gè)數(shù)字格。一般可在劃去的行和列的任意空格處加一個(gè)0即可。 編輯表上作業(yè)法案例分析 編輯案例一:表上作業(yè)法在物流配送中的應(yīng)用2 配送是物流系統(tǒng)的一項(xiàng)十分重要的功能。隨著物流行業(yè)的發(fā)展，物流公司迅速增加，各個(gè)物流公司之間的競(jìng)爭(zhēng)日趨激烈。如何加強(qiáng)管理以減少成本問(wèn)題成為各物流公司非常關(guān)注的話題。一般來(lái)說(shuō)，配送中心數(shù)量減少，配送中心距離客戶(hù)的距離就會(huì)越長(zhǎng)，配送成本就越高;配送中心數(shù)量增多，配送中心距離客戶(hù)的距離就會(huì)縮短，配送成本就越少，但是配送中心的管理成本隨之增加。本文討論利用現(xiàn)有的配送中心向客戶(hù)的配送問(wèn)題，尋求最小的配送成本。 一、配送模型的建立與求解 1.配送模型的建立。物流公司常常在某個(gè)地區(qū)有多個(gè)配送中心來(lái)供應(yīng)貨物，每個(gè)物流中心都有一定的供應(yīng)量。物流中心配送貨物的客戶(hù)也往往不止一個(gè)，多個(gè)客戶(hù)更為常見(jiàn)。ai(i=1，2，3，m)表示不同的配送中心貨物供應(yīng)量，m表示配送中心的數(shù)量。bj(j=1，2，3,n)表示不同客戶(hù)需求的貨物量，n表示量客戶(hù)的數(shù)量。從配送中心到客戶(hù)的單位配送價(jià)格用c_ij表示。這些數(shù)據(jù)可用表1來(lái)表示。 若用xij表示從ai到bj的實(shí)際供應(yīng)量，那么在供需平衡的條件下，要求得總運(yùn)費(fèi)最小的配送方案，可求解以下數(shù)學(xué)模型: 2.表上作業(yè)法對(duì)模型的求解。利用一般的求解方法很難求得上述數(shù)學(xué)模型的解，但是根據(jù)運(yùn)籌學(xué)的相關(guān)內(nèi)容來(lái)求解就相當(dāng)容易了。求解的步驟分三步:首先用最小元素法求出初始可行解，再采用閉合回路法判斷是否最優(yōu)，最后采用閉合回路調(diào)整法調(diào)整變量直至最優(yōu)解。 以最小單位配送價(jià)格運(yùn)價(jià)開(kāi)始配送，從單位配送價(jià)格最小到最大順序逐一使供需量平衡，配送中供需達(dá)到規(guī)定量的可以從表上劃掉。根據(jù)表上求得的結(jié)果可以得到最小的配送成本。最小元素法的缺點(diǎn)是:為了節(jié)省某一配送中心的費(fèi)用，可能造成其他配送中心幾倍的配送成本，所以必須對(duì)上述的結(jié)果進(jìn)行檢驗(yàn)。 檢驗(yàn)的方法采用閉合回路法，即從表上任一個(gè)空格出發(fā)，沿水平或垂直方向前進(jìn)，每遇到一個(gè)適當(dāng)數(shù)字(有利于回到原空格)轉(zhuǎn)90,繼續(xù)前進(jìn)直到回到原空格。當(dāng)所有檢驗(yàn)數(shù)，則就是最優(yōu)解，否則還需要繼續(xù)改進(jìn)。 當(dāng)有的空格檢驗(yàn)數(shù)小于0時(shí)，說(shuō)明此空格應(yīng)當(dāng)使用。改進(jìn)的方法采用閉合回路調(diào)整法，從檢驗(yàn)數(shù)是負(fù)數(shù)的空格開(kāi)始，沿閉回路前進(jìn)取數(shù)字的最小值，使用閉回路轉(zhuǎn)角的數(shù)加減這個(gè)數(shù)。然后再次使用閉合回路法檢驗(yàn)所有空格的檢驗(yàn)數(shù)，所有檢驗(yàn)數(shù)大于0則就是最優(yōu)解，否則再繼續(xù)改進(jìn)，直至最優(yōu)。 二、物流公司配送實(shí)例 某物流公司給四個(gè)客戶(hù)甲、乙、丙和丁配送貨物，配送量分別為3噸、6噸、5噸和6噸。物流公司在該地區(qū)有三個(gè)配送中心，每個(gè)配送中心的貨物供應(yīng)量分別為7噸、4噸和9噸。由于各個(gè)配送中心距離客戶(hù)的距離不一樣，所以配送貨物的單位價(jià)格也不同。需求量和供應(yīng)量及價(jià)格數(shù)據(jù)如表2所示。其中價(jià)格單位為萬(wàn)元/噸。 1.最小元素法求出初始可行解。物流公司在配送貨物時(shí)，除了考慮準(zhǔn)時(shí)、安全送達(dá)貨物以外，盡可能減少配送成本。首先以最小單位價(jià)格開(kāi)始配送，從單位價(jià)格最小到最大順序逐一使供需平衡，配送中供需達(dá)到規(guī)定量的劃掉。從上表中找到最低配送單位價(jià)格為2.1萬(wàn)元/噸，由于甲客戶(hù)需求量為3噸，物流中心2的供應(yīng)量為4噸，取min3 4=3填入表中，甲客戶(hù)一欄需求量達(dá)到規(guī)定量，把甲客戶(hù)一欄劃去，如表3所示。 再?gòu)谋碇形磩澣サ膬r(jià)格中找到最小價(jià)格開(kāi)始配送，這時(shí)最小的單位價(jià)格為2.2萬(wàn)元/噸。由于丙客戶(hù)需求量為5噸，而物流中心2的供應(yīng)量?jī)H為4噸且已經(jīng)配給甲客戶(hù)3噸，故配給丙客戶(hù)只能1噸，取min5 1=1填入表中，物流中心2一行供應(yīng)量達(dá)到規(guī)定量，把物流中心2一行劃去，如表4所示。 同理:按照上面的做法一直劃下去，最后的結(jié)果如下表5所示。 最后可得到最小配送成本為: Zmin=42.3+33.0+32.1+12.262.432.5 (萬(wàn)元)。 2.閉合回路法判斷最優(yōu)解。上表中未填入數(shù)字的稱(chēng)之為空格，需要計(jì)算所有空格的檢驗(yàn)數(shù)，若檢驗(yàn)數(shù)全部大于等于0，則上述填入的數(shù)字為最優(yōu)解，否則不是最優(yōu)解，需要進(jìn)一步計(jì)算。 圖中的空格(11)閉合回路，可采取空格(11)空格(13)空格(23)空格(21)空格(11)組成回路。如下表6所示。 檢驗(yàn)數(shù)： 同理,空格(12)、空格(22)、空格(24)、空格(31)和空格(33)的檢驗(yàn)數(shù)分別為:K12 = 0.2,K22 = 0.1,K24 = 0.1,K31 = 1和K33 = 1.2。 空格檢驗(yàn)數(shù)K24 = 0.1為負(fù)數(shù)，所以上述不是最優(yōu)解。 3.閉合回路調(diào)整法對(duì)上述變量進(jìn)行調(diào)整。由于K24 = 0.1，故空格(24)必須要使用，先對(duì)(24)轉(zhuǎn)角進(jìn)行調(diào)整。取轉(zhuǎn)角最小值min1，3，4=1填入空格(24)中，其空格(24)轉(zhuǎn)角值相應(yīng)做出如下調(diào)整，如表7所示。 調(diào)整后的空格檢驗(yàn)數(shù)如下： K11 = 0,K12 = 0.2,K22 = 0.2,K23 = 0.1,K31 = 0.9,K33 = 1.2 所有空格檢驗(yàn)數(shù)均為正數(shù)，說(shuō)明上表中的解為最優(yōu)解。即，物流中心1給丙客戶(hù)配送5噸貨物，給丁客戶(hù)配送2噸貨物；物流公司2給甲客戶(hù)配送3噸貨物，給丁客戶(hù)配送1噸貨物。物流中心3給乙客戶(hù)配送6噸貨物，給丁客戶(hù)配送3噸貨物。此時(shí)物流公司的配送總成本最小。 Zmin=52.323.0+32.112.862.432.5(萬(wàn)元)。 從計(jì)算結(jié)果可以看出，最優(yōu)解比初始可行解總成本又降低了0.1萬(wàn)元。 通過(guò)建立物流配送模型，利用表上作業(yè)法解出最小配送成本，解決了降低配送中心的配送成本問(wèn)題，提升了物流公司的市場(chǎng)競(jìng)爭(zhēng)力圖上作業(yè)法什么是圖上作業(yè)法圖上作業(yè)法在運(yùn)輸圖上求解線性規(guī)劃運(yùn)輸模型的方法。它是在一張運(yùn)輸交通上通過(guò)一定步驟的規(guī)劃和計(jì)算來(lái)完成物資調(diào)運(yùn)計(jì)劃的編制工作，以便使物資運(yùn)行的總噸公里數(shù)最小可使物資運(yùn)費(fèi)降低，并縮短了運(yùn)輸時(shí)間，所以，在一定條件下稱(chēng)這樣的方案為最優(yōu)方案。 編輯圖上作業(yè)法的步驟1制定一個(gè)物資調(diào)運(yùn)方案時(shí)： 1、首先要編制物資平衡表（如下圖所示）。 圖1：物資平衡表 在編制物資平衡表時(shí)需要做3件事。 (1)出需要調(diào)出物資的地點(diǎn)（即發(fā)點(diǎn)）及發(fā)量。 (2)出需要調(diào)進(jìn)物資的地點(diǎn)（即收點(diǎn)）及收量。 (3)求：總發(fā)量=總收量。 2、第二步，根據(jù)物資平衡表和收點(diǎn)，發(fā)點(diǎn)間的相互位置繪制交通圖。所謂交通圖就是表明收點(diǎn)和發(fā)點(diǎn)間的相互位置以及聯(lián)結(jié)這些點(diǎn)之間的交通線路的簡(jiǎn)要地圖。在交通圖上，用圓圈“”表示發(fā)點(diǎn)，將該發(fā)點(diǎn)的發(fā)量填入圓圈“”內(nèi)。用方框“”表示收點(diǎn)，將該收點(diǎn)的收量填入方框“”內(nèi)。兩點(diǎn)間的距離，記在交通線路的旁邊。 3、第三步，交通圖繪制好后，即可在其上面進(jìn)行物資調(diào)運(yùn)，找出初始調(diào)運(yùn)方案(初始基可行解)，作物資調(diào)運(yùn)流向圖。 我們用箭頭“”表示物資調(diào)運(yùn)的方向即稱(chēng)流向，并規(guī)定：流向“”必須畫(huà)在沿著線路前進(jìn)的右側(cè)。把運(yùn)送物資的數(shù)量記在流向“”的旁邊并加括號(hào)（ ），以區(qū)別于兩點(diǎn)之間的距離數(shù)。 另一方面，為了保持圖面的整潔，流向量最好不要通過(guò)收，發(fā)點(diǎn)以及交叉路口，如圖1中，(a)，(b)是正確的。 編輯圖上作業(yè)法的注意事項(xiàng)1在物資運(yùn)輸中，把某種物資從各發(fā)點(diǎn)調(diào)到各收點(diǎn)的調(diào)運(yùn)方案是很多的，但我們的目的是找出噸公里數(shù)是最小的調(diào)運(yùn)方案。這就要注意在調(diào)運(yùn)中不要發(fā)生對(duì)流運(yùn)輸和迂回運(yùn)輸，因此，我們?cè)谥贫飨驁D時(shí)，就要避免它的出現(xiàn)。 （1）對(duì)流：所謂對(duì)流就是在一段線路上有同一種物資往返運(yùn)輸（同一段線路上，兩各方向都有流向），如下圖。 圖2 圖3 將某種物資10噸從A1運(yùn)往B2，同時(shí)又有同樣的物資10噸同時(shí)從A2運(yùn)往B1，于是在A1A2之間就出現(xiàn)了對(duì)流現(xiàn)象.如果把流向圖改成圖3，即將A1的10噸運(yùn)往B1，而將A2的10噸運(yùn)往B2，就避免了A1A2的對(duì)流，從而可以節(jié)約運(yùn)輸量(噸公里)。 （2）迂回：當(dāng)交通圖成圈時(shí)，如果流向圖中內(nèi)圈流向的總長(zhǎng)（簡(jiǎn)稱(chēng)內(nèi)圈長(zhǎng)）或外圈流向的總長(zhǎng)（簡(jiǎn)稱(chēng)外圈長(zhǎng)）超過(guò)整個(gè)圈長(zhǎng)的一半就稱(chēng)為迂回運(yùn)輸。例如某物資流向圖如下圖4所示。 圖4 圖5 顯然，它是一個(gè)迂回運(yùn)輸流向圖，它的內(nèi)圈長(zhǎng)6大于整個(gè)圈長(zhǎng)的一半5。如果把它改成圖5，就避免了迂回現(xiàn)象，可節(jié)約運(yùn)輸量（噸公里）理論上可以證明，一個(gè)物資調(diào)運(yùn)方案中，如果沒(méi)有對(duì)流和迂回運(yùn)輸，則該方案就是最優(yōu)調(diào)運(yùn)方案。即運(yùn)輸量最小的方案。 從以上討論可以看到，圖上作