模塊二 運(yùn)輸問(wèn)題之 表上作業(yè)法

1、模塊二 運(yùn) 輸 問(wèn) 題之 表上作業(yè)法內(nèi)容提要內(nèi)容提要 運(yùn)輸問(wèn)題模型的特點(diǎn)運(yùn)輸問(wèn)題模型的特點(diǎn) 產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法 產(chǎn)銷不平衡運(yùn)輸問(wèn)題的轉(zhuǎn)化產(chǎn)銷不平衡運(yùn)輸問(wèn)題的轉(zhuǎn)化 表上作業(yè)法在物流管理中的典型應(yīng)用表上作業(yè)法在物流管理中的典型應(yīng)用CHAPTER 運(yùn)輸管理是物流管理中重要的環(huán)節(jié)之一，物流企業(yè)的物流成本中，運(yùn)輸與配送管理的成本比重約占80%左右。 因此，合理的優(yōu)化配送路徑不僅可以簡(jiǎn)化配送程序、減少配送頻率，而且更重要的是更重要的是可以降低配送費(fèi)用，從而帶來(lái)更大的效益，因此調(diào)運(yùn)物資配送方案的優(yōu)化選擇調(diào)運(yùn)物資配送方案的優(yōu)化選擇引起了各界人士注意。 運(yùn)運(yùn) 輸輸 問(wèn)問(wèn) 題

2、題物流配送方式物流配送方式 在物流管理過(guò)程中，組織物流配送與運(yùn)輸工作應(yīng)該以及時(shí)及時(shí)、準(zhǔn)確準(zhǔn)確、經(jīng)濟(jì)經(jīng)濟(jì)、安全安全為原則。配送與運(yùn)輸方式有：鐵路、公路、水路、航空、鐵路、公路、水路、航空、管道等管道等。表 銷地銷地產(chǎn)地產(chǎn)地 B1 B2 B3 B4 產(chǎn)產(chǎn) 量量 A1 3113107A2 19284A3 741059 銷銷 量量 3656 20 20 求解此類問(wèn)題可用“表上作業(yè)法”在求解之前了解一下運(yùn)輸問(wèn)題中的一些概念在求解之前了解一下運(yùn)輸問(wèn)題中的一些概念 對(duì)某種物資，其計(jì)量單位可以是重量、包括單位或其他。設(shè)有m個(gè)產(chǎn)地個(gè)產(chǎn)地A1, A2, , Am，稱稱它們?yōu)榘l(fā)發(fā)點(diǎn)點(diǎn)，其對(duì)應(yīng)產(chǎn)量產(chǎn)量為a1, a2,

3、 , am，稱它們?yōu)楫a(chǎn)量；另有n個(gè)銷地B1, B2, , Bn，稱稱它們?yōu)槭拯c(diǎn)收點(diǎn)，其對(duì)應(yīng)銷銷量量為b1, b2, , bn，稱它們?yōu)殇N量。又知，從產(chǎn)地（發(fā)點(diǎn)）Ai運(yùn)至銷地（收點(diǎn)）Bj，該種物資每單位的運(yùn)價(jià)為ci j（ci j0）。 試問(wèn)：應(yīng)如何安排調(diào)運(yùn)方案，在滿足一定要求的前提下，使總運(yùn)費(fèi)最低？ 根據(jù)上述參量的意義列出產(chǎn)銷運(yùn)價(jià)，如下表 表表2.3 產(chǎn)銷運(yùn)價(jià)表產(chǎn)銷運(yùn)價(jià)表 銷地銷地 產(chǎn)地產(chǎn)地 B1 B2 Bn 產(chǎn)量產(chǎn)量 A1 c11 c12 c1n a1 A2 c21 c22 c2n a2 Am cm1 cm2 cmn am 銷量銷量 b1 b2 bn ai bj 表的右下角 ai表示各產(chǎn)地產(chǎn)量

4、的總和，即總產(chǎn)量或總發(fā)量； bj表示各銷地銷量的總和，即總銷量或總收量。這里有兩種可能：（1） ai bj（總產(chǎn)量總銷量），即產(chǎn)銷平衡問(wèn)題。（2） ai bj（總產(chǎn)量總銷量），即產(chǎn)銷不平衡問(wèn)題。它又可分為兩種情況：產(chǎn)大于銷，即 ai bj ；銷大于產(chǎn)，即 ai bj。 下面先討論產(chǎn)銷平衡問(wèn)題，再討論產(chǎn)銷不平衡問(wèn)題。 令xij表示某物資從發(fā)點(diǎn)Ai到收點(diǎn)Bj的調(diào)撥量（運(yùn)輸量），可以列出產(chǎn)銷平衡表如表2.4所示。 表表2.4 產(chǎn)銷平衡表產(chǎn)銷平衡表 銷 地產(chǎn) 地 B1 B2 Bn 產(chǎn) 量 A1 x11 x12 x1n a1 A2 x21 x22 x2n a2 Am xm1 xm2 xmn am 銷量

5、b1 b2 bn ai bj 將產(chǎn)銷運(yùn)價(jià)表2.3和產(chǎn)銷平衡表2.4兩個(gè)表合在一起，得到的一個(gè)新表，被稱為運(yùn)輸表運(yùn)輸表（或稱為產(chǎn)銷矩陣表），如表2.5所示。 表表2.5 運(yùn)輸表（產(chǎn)銷矩陣表）運(yùn)輸表（產(chǎn)銷矩陣表） 銷地產(chǎn)地 B1 B2 Bn 產(chǎn)量 A1 x11 c11 x12 c12 x1n c1n a1 A2 x21 c21 x22 c22 x2n c2n a2 Am xm1 cm1 xm2 cm2 xmn cmn am 銷量 b1 b2 bn ai bj 轉(zhuǎn)化為求費(fèi)用最小的數(shù)學(xué)模型。求上述總運(yùn)費(fèi)最小問(wèn)題就等于求下面數(shù)學(xué)模型的解，即求：xij（i1, 2, , m；j1, 2, , n）),2,

6、 1;,2, 1(0),2, 1(),2, 1(11njmixnjbxmiaxijmijijnjiij（2-1） 11m inmnijijijzcx 約束條件個(gè)數(shù)減去線性相關(guān)的條件個(gè)數(shù) 我國(guó)數(shù)學(xué)家研究出在表上進(jìn)行分析、我國(guó)數(shù)學(xué)家研究出在表上進(jìn)行分析、計(jì)算、判斷的解決計(jì)算、判斷的解決“一批物資從幾個(gè)生產(chǎn)地供應(yīng)給若干個(gè)消費(fèi)地，各地產(chǎn)量和銷量都是已知的，各地運(yùn)費(fèi)也已知，如何調(diào)運(yùn)才能使總運(yùn)費(fèi)（貨總噸公里數(shù)）最小”的的問(wèn)題的方法問(wèn)題的方法（即表上作業(yè)法）。（即表上作業(yè)法）。 11mnijijab先來(lái)學(xué)習(xí)產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法 產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法的基本計(jì)算步驟：產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法

7、的基本計(jì)算步驟：1. 1. 編制產(chǎn)銷運(yùn)價(jià)表（或運(yùn)費(fèi)表和產(chǎn)銷平衡表）；編制產(chǎn)銷運(yùn)價(jià)表（或運(yùn)費(fèi)表和產(chǎn)銷平衡表）；2. 2. 根據(jù)產(chǎn)銷平衡表和運(yùn)價(jià)表編制出可行的初始調(diào)運(yùn)根據(jù)產(chǎn)銷平衡表和運(yùn)價(jià)表編制出可行的初始調(diào)運(yùn)方案；方案；（最小元素法、（最小元素法、VogelVogel法）法）3. 3. 判斷初始方案是否最好，若不是最好的，則在初始方判斷初始方案是否最好，若不是最好的，則在初始方案的基礎(chǔ)上進(jìn)行調(diào)整。案的基礎(chǔ)上進(jìn)行調(diào)整。 通常每調(diào)整一次所得到的新方案（基本可行解基本可行解）就比原方案好一些，經(jīng)過(guò)若干次調(diào)整，最后必能得到最好的調(diào)運(yùn)方案（最優(yōu)解最優(yōu)解）。解（解（1）根據(jù)題意編制產(chǎn)銷運(yùn)價(jià)表根據(jù)題意編制產(chǎn)銷運(yùn)

8、價(jià)表 表表2.6 產(chǎn)銷運(yùn)價(jià)表產(chǎn)銷運(yùn)價(jià)表 單位：?jiǎn)挝唬簢崳瑖崳?萬(wàn)元萬(wàn)元 /噸噸 銷地銷地產(chǎn)地產(chǎn)地 B1 B2 B3 B4 產(chǎn)產(chǎn) 量量 A1 3113107A2 19284A3 741059 銷銷 量量 3656 20 20 （2）編制初始方案：）編制初始方案：初始方案確定的方法一：最小元素法。最小元素法。 最小元素法的基本思想基本思想就是就近供應(yīng)就近供應(yīng)，即從單位運(yùn)價(jià)表中最小最小的運(yùn)價(jià)處開始確定供銷關(guān)系；當(dāng)需求已得到滿足或產(chǎn)量已分配完畢，將此列或此行劃去；然后從剩下的運(yùn)價(jià)中找最小元素確定供銷關(guān)系，依此類推，直到所有的元素都劃去，得出全部方案為止。 解（解（2）將將用最小元素法得到的初始調(diào)運(yùn)方案

9、顯示于下圖用最小元素法得到的初始調(diào)運(yùn)方案顯示于下圖 表表2.7 調(diào)運(yùn)方案表調(diào)運(yùn)方案表2.8 初始調(diào)運(yùn)方案表但此方案是否為最優(yōu)呢？需但此方案是否為最優(yōu)呢？需要對(duì)方案進(jìn)行檢驗(yàn)！要對(duì)方案進(jìn)行檢驗(yàn)！說(shuō)明：說(shuō)明： 一般調(diào)運(yùn)方案表每填一個(gè)數(shù)，劃去單位運(yùn)價(jià)表中的一行或一列。但往往出現(xiàn)下述情況，選定的最小元素所在行的產(chǎn)量等于所在列銷量，這時(shí)在產(chǎn)銷平衡表上填一個(gè)數(shù)，運(yùn)價(jià)表上就要同事劃去一行和一列。為了使調(diào)運(yùn)方案中的有數(shù)字格仍為m+n-1個(gè)，需要在同時(shí)劃去的該行或該列的任一空格處補(bǔ)填一個(gè)“0”。最小元素法編制初始方案：最小元素法編制初始方案：1、編制產(chǎn)銷運(yùn)價(jià)表；、編制產(chǎn)銷運(yùn)價(jià)表；2、從產(chǎn)銷運(yùn)價(jià)表中最小元素處開始找

10、初始方案；、從產(chǎn)銷運(yùn)價(jià)表中最小元素處開始找初始方案；3、檢驗(yàn)方案是否最優(yōu)（未學(xué)習(xí)）、檢驗(yàn)方案是否最優(yōu)（未學(xué)習(xí)）最小元素法的最小元素法的基本思想基本思想。 就近供應(yīng)就近供應(yīng)，即從單位運(yùn)價(jià)表中最小最小的運(yùn)價(jià)處開始確定供銷關(guān)系；當(dāng)需求已得到滿足或產(chǎn)量已分配完畢，將此列或此行劃去；然后從剩下的運(yùn)價(jià)中找最小元素確定供銷關(guān)系，依此類推，直到所有的元素都劃去，得出全部方案為止。 Vogel（2）編制初始方案：）編制初始方案：初始方案確定的方法二： Vogel法（沃格爾法（沃格爾法）法） 。 Vogel法的步驟是：從運(yùn)價(jià)表上分別找出每行從運(yùn)價(jià)表上分別找出每行與每列的與每列的最小的兩個(gè)元素之差最小的兩個(gè)元素之差

11、，再?gòu)牟钪底畲蟮男谢蛄兄姓页鲎钚∵\(yùn)價(jià)確定供需關(guān)系和供應(yīng)數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量上供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列；然后從剩下的元素中找出每行每列的最小元素之差，依次重復(fù)上述步驟直到找出初始方案。Vogel用用Vogel法求解初始調(diào)運(yùn)方案總運(yùn)費(fèi)法求解初始調(diào)運(yùn)方案總運(yùn)費(fèi)75萬(wàn)元。萬(wàn)元。哪個(gè)是最優(yōu)的？或者都不是，如何進(jìn)行最優(yōu)檢驗(yàn)?zāi)?？哪個(gè)是最優(yōu)的？或者都不是，如何進(jìn)行最優(yōu)檢驗(yàn)?zāi)?？Vogel通過(guò)計(jì)算各空格處的檢驗(yàn)數(shù)來(lái)對(duì)初始方案進(jìn)行檢驗(yàn)。通過(guò)計(jì)算各空格處的檢驗(yàn)數(shù)來(lái)對(duì)初始方案進(jìn)行檢驗(yàn)。一、閉回路法一、閉回路法 通過(guò)構(gòu)造閉回路計(jì)算各空格處的檢驗(yàn)數(shù)，根據(jù)檢通過(guò)構(gòu)造閉回路計(jì)算各空格處的檢驗(yàn)數(shù)，

12、根據(jù)檢驗(yàn)驗(yàn)數(shù)是否全部非負(fù)來(lái)判斷方案是否最優(yōu)。數(shù)是否全部非負(fù)來(lái)判斷方案是否最優(yōu)。二、位勢(shì)法二、位勢(shì)法 通過(guò)構(gòu)造閉回路計(jì)算各空格處的檢驗(yàn)數(shù)，根據(jù)檢通過(guò)構(gòu)造閉回路計(jì)算各空格處的檢驗(yàn)數(shù)，根據(jù)檢驗(yàn)數(shù)是否全部非負(fù)來(lái)判斷方案是否最優(yōu)。驗(yàn)數(shù)是否全部非負(fù)來(lái)判斷方案是否最優(yōu)。此方法計(jì)算檢驗(yàn)數(shù)較麻煩！方案的調(diào)整：方案的調(diào)整： 思路：思路：盡量增加檢驗(yàn)數(shù)為負(fù)值格的運(yùn)量（當(dāng)有兩個(gè)以上盡量增加檢驗(yàn)數(shù)為負(fù)值格的運(yùn)量（當(dāng)有兩個(gè)以上負(fù)的檢驗(yàn)數(shù)時(shí)，從絕對(duì)值大的負(fù)檢驗(yàn)數(shù)出發(fā)）。負(fù)的檢驗(yàn)數(shù)時(shí)，從絕對(duì)值大的負(fù)檢驗(yàn)數(shù)出發(fā)）。步驟：步驟：一、找出檢驗(yàn)數(shù)為負(fù)數(shù)格所在的閉回路中一、找出檢驗(yàn)數(shù)為負(fù)數(shù)格所在的閉回路中二、盡量增加檢驗(yàn)數(shù)為負(fù)值格的運(yùn)

13、量，減小其閉回路中二、盡量增加檢驗(yàn)數(shù)為負(fù)值格的運(yùn)量，減小其閉回路中相鄰格的運(yùn)量。得到新的調(diào)運(yùn)方案。相鄰格的運(yùn)量。得到新的調(diào)運(yùn)方案。注意：其中運(yùn)量的增加、減小量是閉回路中最小的運(yùn)量注意：其中運(yùn)量的增加、減小量是閉回路中最小的運(yùn)量調(diào)整后的方案是否最優(yōu)，需進(jìn)一步計(jì)算檢驗(yàn)數(shù)對(duì)方案進(jìn)行檢驗(yàn)。！ 若檢驗(yàn)數(shù)全非負(fù)，則方案為最有；若檢驗(yàn)數(shù)有負(fù)值，則需要對(duì)方案進(jìn)行調(diào)整。最小元素法編制初始方案的步驟如下。最小元素法編制初始方案的步驟如下。（1）編制產(chǎn)銷運(yùn)價(jià)表）編制產(chǎn)銷運(yùn)價(jià)表（2）從運(yùn)價(jià)表中的最小元素出發(fā)確定供需關(guān)系）從運(yùn)價(jià)表中的最小元素出發(fā)確定供需關(guān)系和供需量，依次進(jìn)行下去找出初始方案。和供需量，依次進(jìn)行下去找出

14、初始方案。 （3）求檢驗(yàn)數(shù)。）求檢驗(yàn)數(shù)。（4）若檢驗(yàn)數(shù)不全大于）若檢驗(yàn)數(shù)不全大于0，則調(diào)整方案。，則調(diào)整方案。vogel法編制初始方案的步驟如下。法編制初始方案的步驟如下。（1）編制產(chǎn)銷運(yùn)價(jià)表）編制產(chǎn)銷運(yùn)價(jià)表（2）計(jì)算運(yùn)價(jià)表中每行、每列最小的兩個(gè)元素）計(jì)算運(yùn)價(jià)表中每行、每列最小的兩個(gè)元素的差值，從最大的差值對(duì)應(yīng)的行、列中找最小的差值，從最大的差值對(duì)應(yīng)的行、列中找最小的元素處確定供需關(guān)系。依次進(jìn)行下去找出初的元素處確定供需關(guān)系。依次進(jìn)行下去找出初始方案。始方案。 （3）求檢驗(yàn)數(shù)。）求檢驗(yàn)數(shù)。（4）若檢驗(yàn)數(shù)不全大于）若檢驗(yàn)數(shù)不全大于0，則調(diào)整方案。，則調(diào)整方案。此例表中A1，A2，A3的總發(fā)量為1

15、9t，B1，B2，B3，B4的總收量為15t，總發(fā)量比總收量多出4t，不論怎樣，總庫(kù)存量都是4t，這是不變的。這樣，我們就表中收點(diǎn)處增加一列庫(kù)存，增加一列庫(kù)存，同時(shí)運(yùn)費(fèi)表中也增加一列都是零的運(yùn)費(fèi)增加一列都是零的運(yùn)費(fèi)，如表2-31所示。1、對(duì)于求最大值問(wèn)題，用什么方法求初始方案？、對(duì)于求最大值問(wèn)題，用什么方法求初始方案？用于求最小化問(wèn)題的用于求最小化問(wèn)題的最小元素法與最小元素法與vogelvogel法法是否是否可以用來(lái)求最大化問(wèn)題？可以用來(lái)求最大化問(wèn)題？2、對(duì)初始方案檢驗(yàn)的方法與判別方案最優(yōu)的準(zhǔn)則是什、對(duì)初始方案檢驗(yàn)的方法與判別方案最優(yōu)的準(zhǔn)則是什么？么？思考：思考：1 1、求最大值問(wèn)題，用最?。?/p>

16、最大）元素法？、求最大值問(wèn)題，用最?。ㄗ畲螅┰胤?？ 最大元素法最大元素法思考：思考：2、如何利用vogel法求初始方案？求解思路是什么？計(jì)算每行、每列計(jì)算每行、每列最大最大的兩個(gè)元素之差；的兩個(gè)元素之差；從差值最大的行或列中從差值最大的行或列中最大元素處最大元素處確定供需關(guān)系和確定供需關(guān)系和供應(yīng)量；如有多個(gè)最大差值，從最大元素處確定。供應(yīng)量；如有多個(gè)最大差值，從最大元素處確定。3、求最大值問(wèn)題，如何利用檢驗(yàn)數(shù)判斷方案是否最優(yōu)？ 非負(fù)非負(fù)or非正？非正？要求：要求：依據(jù)上述分析對(duì)依據(jù)上述分析對(duì)作物布局問(wèn)題作物布局問(wèn)題的最優(yōu)播種的最優(yōu)播種方案，是產(chǎn)量最大。方案，是產(chǎn)量最大。本章小結(jié)：本章小結(jié)：1、運(yùn)輸問(wèn)題模型的特點(diǎn)運(yùn)輸問(wèn)題模型的特點(diǎn)2、產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法 求初始方案的方法（最小元素法求初始方案的方法（最小元素法 VOGELVOGEL法）法） 最優(yōu)化檢驗(yàn)的方法（閉回路法最優(yōu)化檢驗(yàn)的方法（閉回路法 位勢(shì)法）位勢(shì)法）3、產(chǎn)銷不平衡運(yùn)輸問(wèn)題的表上作業(yè)法產(chǎn)銷不平衡運(yùn)輸問(wèn)題的表上作業(yè)法 轉(zhuǎn)換為產(chǎn)銷平衡問(wèn)題轉(zhuǎn)換為產(chǎn)銷平衡問(wèn)題4、表上作業(yè)法應(yīng)用實(shí)例表上作業(yè)法應(yīng)用實(shí)例本章練習(xí)題：本章練習(xí)題：某部門有某部門有3個(gè)生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由個(gè)生產(chǎn)同類產(chǎn)品