表上作業(yè)法.doc

什么是表上作業(yè)法表上作業(yè)法是指用列表的方法求解線性規(guī)劃問題中運(yùn)輸模型的計(jì)算方法。是線性規(guī)劃一種求解方法。當(dāng)某些線性規(guī)劃問題采用圖上作業(yè)法難以進(jìn)行直觀求解時(shí)，就可以將各元素列成相關(guān)表，作為初始方案，然后采用檢驗(yàn)數(shù)來驗(yàn)證這個(gè)方案，否則就要采用閉合回路法、位勢法等方法進(jìn)行調(diào)整，直至得到滿意的結(jié)果。這種列表求解方法就是表上作業(yè)法。 表上作業(yè)法的步驟1、找出初始基本可行解（初始調(diào)運(yùn)方案，一般m+n-1個(gè)數(shù)字格），用西北角法、最小元素法； （1）西北角法： 從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。 （2）最小元素法： 從運(yùn)價(jià)最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價(jià)從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。 注:應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列，只有最后一個(gè)元例外（同時(shí)劃去一行和一列）。當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行（列），在保留的列（行）中沒被劃去的格內(nèi)標(biāo)一個(gè)0。 2、求出各非基變量的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如果是停止計(jì)算，否則轉(zhuǎn)入下一步，用位勢法計(jì)算； 運(yùn)輸問題的約束條件共有m+n個(gè)，其中：m是產(chǎn)地產(chǎn)量的限制；n是銷地銷量的限制。其對偶問題也應(yīng)有m+n個(gè)變數(shù)，據(jù)此： ij = cij (ui + vj) ,其中前m個(gè)計(jì)為,前n個(gè)計(jì)為 由單純形法可知，基變數(shù)的ij = 0 cij (ui + vj) = 0因此ui,vj可以求出。 3、改進(jìn)當(dāng)前的基本可行解（確定換入、換出變量），用閉合回路法調(diào)整； （因?yàn)槟繕?biāo)函數(shù)要求最小化） 表格中有調(diào)運(yùn)量的地方為基變量，空格處為非基變數(shù)?；兞康臋z驗(yàn)數(shù)ij = 0，非基變數(shù)的檢驗(yàn)數(shù)。ij 0表示運(yùn)費(fèi)增加。 4、重復(fù)，直到找到最優(yōu)解為止。 表上作業(yè)法計(jì)算中的問題1、無窮多最優(yōu)解 產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的ij = 0，則該問題有無窮多最優(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è)物流公司之間的競爭日趨激烈。如何加強(qiáng)管理以減少成本問題成為各物流公司非常關(guān)注的話題。一般來說，配送中心數(shù)量減少，配送中心距離客戶的距離就會(huì)越長，配送成本就越高;配送中心數(shù)量增多，配送中心距離客戶的距離就會(huì)縮短，配送成本就越少，但是配送中心的管理成本隨之增加。本文討論利用現(xiàn)有的配送中心向客戶的配送問題，尋求最小的配送成本。 一、配送模型的建立與求解 1.配送模型的建立。物流公司常常在某個(gè)地區(qū)有多個(gè)配送中心來供應(yīng)貨物，每個(gè)物流中心都有一定的供應(yīng)量。物流中心配送貨物的客戶也往往不止一個(gè)，多個(gè)客戶更為常見。ai(i=1，2，3，m)表示不同的配送中心貨物供應(yīng)量，m表示配送中心的數(shù)量。bj(j=1，2，3,n)表示不同客戶需求的貨物量，n表示量客戶的數(shù)量。從配送中心到客戶的單位配送價(jià)格用c_ij表示。這些數(shù)據(jù)可用表1來表示。 若用xij表示從ai到bj的實(shí)際供應(yīng)量，那么在供需平衡的條件下，要求得總運(yùn)費(fèi)最小的配送方案，可求解以下數(shù)學(xué)模型: 2.表上作業(yè)法對模型的求解。利用一般的求解方法很難求得上述數(shù)學(xué)模型的解，但是根據(jù)運(yùn)籌學(xué)的相關(guān)內(nèi)容來求解就相當(dāng)容易了。求解的步驟分三步:首先用最小元素法求出初始可行解，再采用閉合回路法判斷是否最優(yōu)，最后采用閉合回路調(diào)整法調(diào)整變數(shù)直至最優(yōu)解。 以最小單位配送價(jià)格運(yùn)價(jià)開始配送，從單位配送價(jià)格最小到最大順序逐一使供需量平衡，配送中供需達(dá)到規(guī)定量的可以從表上劃掉。根據(jù)表上求得的結(jié)果可以得到最小的配送成本。最小元素法的缺點(diǎn)是:為了節(jié)省某一配送中心的費(fèi)用，可能造成其他配送中心幾倍的配送成本，所以必須對上述的結(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í)，說明此空格應(yīng)當(dāng)使用。改進(jìn)的方法采用閉合回路調(diào)整法，從檢驗(yàn)數(shù)是負(fù)數(shù)的空格開始，沿閉回路前進(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è)客戶甲、乙、丙和丁配送貨物，配送量分別為3噸、6噸、5噸和6噸。物流公司在該地區(qū)有三個(gè)配送中心，每個(gè)配送中心的貨物供應(yīng)量分別為7噸、4噸和9噸。由于各個(gè)配送中心距離客戶的距離不一樣，所以配送貨物的單位價(jià)格也不同。需求量和供應(yīng)量及價(jià)格數(shù)據(jù)如表2所示。其中價(jià)格單位為萬元/噸。 1.最小元素法求出初始可行解。物流公司在配送貨物時(shí)，除了考慮準(zhǔn)時(shí)、安全送達(dá)貨物以外，盡可能減少配送成本。首先以最小單位價(jià)格開始配送，從單位價(jià)格最小到最大順序逐一使供需平衡，配送中供需達(dá)到規(guī)定量的劃掉。從上表中找到最低配送單位價(jià)格為2.1萬元/噸，由于甲客戶需求量為3噸，物流中心2的供應(yīng)量為4噸，取min3 4=3填入表中，甲客戶一欄需求量達(dá)到規(guī)定量，把甲客戶一欄劃去，如表3所示。 再從表中未劃去的價(jià)格中找到最小價(jià)格開始配送，這時(shí)最小的單位價(jià)格為2.2萬元/噸。由于丙客戶需求量為5噸，而物流中心2的供應(yīng)量僅為4噸且已經(jīng)配給甲客戶3噸，故配給丙客戶只能1噸，取min5 1=1填入表中，物流中心2一行供應(yīng)量達(dá)到規(guī)定量，把物流中心2一行劃去，如表4所示。 同理:按照上面的做法一直劃下去，最后的結(jié)果如下表5所示。 最后可得到最小配送成本為: Zmin=42.3+33.0+32.1+12.262.432.5 (萬元)。 2.閉合回路法判斷最優(yōu)解。上表中未填入數(shù)字的稱之為空格，需要計(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)整法對上述變數(shù)進(jìn)行調(diào)整。由于K24 = 0.1，故空格(24)必須要使用，先對(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ù)，說明上表中的解為最優(yōu)解。即，物流中心1給丙客戶配送5噸貨物，給丁客戶配送2噸貨物；物流公司2給甲客戶配送3噸貨物，給丁客戶配送1噸貨物。物流中心3給乙客戶