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

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

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

3、 , am，稱它們?yōu)楫a(chǎn)量；另有n個銷地B1, B2, , Bn，稱稱它們?yōu)槭拯c收點，其對應銷銷量量為b1, b2, , bn，稱它們?yōu)殇N量。又知，從產(chǎn)地（發(fā)點）Ai運至銷地（收點）Bj，該種物資每單位的運價為ci j（ci j0）。 試問：應如何安排調運方案，在滿足一定要求的前提下，使總運費最低？ 根據(jù)上述參量的意義列出產(chǎn)銷運價，如下表 表表2.3 產(chǎn)銷運價表產(chǎn)銷運價表 銷地銷地 產(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)銷平衡問題。（2） ai bj（總產(chǎn)量總銷量），即產(chǎn)銷不平衡問題。它又可分為兩種情況：產(chǎn)大于銷，即 ai bj ；銷大于產(chǎn)，即 ai bj。 下面先討論產(chǎn)銷平衡問題，再討論產(chǎn)銷不平衡問題。 令xij表示某物資從發(fā)點Ai到收點Bj的調撥量（運輸量），可以列出產(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)銷運價表2.3和產(chǎn)銷平衡表2.4兩個表合在一起，得到的一個新表，被稱為運輸表運輸表（或稱為產(chǎn)銷矩陣表），如表2.5所示。 表表2.5 運輸表（產(chǎ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 轉化為求費用最小的數(shù)學模型。求上述總運費最小問題就等于求下面數(shù)學模型的解，即求：xij（i1, 2, , m；j1, 2, , n）),2,

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

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

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

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

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

11、，再從差值最大的行或列中找出最小運價確定供需關系和供應數(shù)量。當產(chǎn)地或銷地中有一方數(shù)量上供應完畢或得到滿足時，劃去運價表中對應的行或列；然后從剩下的元素中找出每行每列的最小元素之差，依次重復上述步驟直到找出初始方案。Vogel用用Vogel法求解初始調運方案總運費法求解初始調運方案總運費75萬元。萬元。哪個是最優(yōu)的？或者都不是，如何進行最優(yōu)檢驗呢？哪個是最優(yōu)的？或者都不是，如何進行最優(yōu)檢驗呢？Vogel通過計算各空格處的檢驗數(shù)來對初始方案進行檢驗。通過計算各空格處的檢驗數(shù)來對初始方案進行檢驗。一、閉回路法一、閉回路法 通過構造閉回路計算各空格處的檢驗數(shù)，根據(jù)檢通過構造閉回路計算各空格處的檢驗數(shù)，

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

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

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

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

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