運籌學-表上作業(yè)法

1、運輸問題求解運輸問題求解 表上作業(yè)法表上作業(yè)法運輸問題求解之表上作業(yè)法運輸問題求解之表上作業(yè)法1.運輸問題模型及其求解思路運輸問題模型及其求解思路2.確定初始基本可行解確定初始基本可行解3.最優(yōu)性檢驗最優(yōu)性檢驗4.方案調(diào)整方案調(diào)整1.運輸問題模型及其求解思路運輸問題模型及其求解思路v運輸問題： 研究把某種商品從若干個產(chǎn)地運至若干個銷售地而使總運費最小的一類問題。v目標：1總運費最小 1.運輸問題模型及其求解思路運輸問題模型及其求解思路 銷地產(chǎn)地B1B2Bn產(chǎn)量A1A2 :Amc11c21:cm1c12c22:cm2:c1nc2n:cmna1a2:am銷量b1b2bnv 已知有m個產(chǎn)地Ai（i=

2、1,2， ， m ）可供應某種物資，其供應量（產(chǎn)量）分別為ai ，有n個銷地Bj （j=1,2， ， n）其銷量（需求量）分別為bj ，從A到B的單位物資運價為cij 。若設若設 代表從第代表從第Ai個產(chǎn)地到第個產(chǎn)地到第Bj個銷售地的調(diào)運量，在個銷售地的調(diào)運量，在產(chǎn)銷產(chǎn)銷平衡平衡的條件下（的條件下（ ），要確定總運輸費用最小的調(diào)運），要確定總運輸費用最小的調(diào)運方案，可表示為如下的數(shù)學模型方案，可表示為如下的數(shù)學模型ijxnjjmiiba11ijmnjijxcz11mini011ijjmiijinjijxbxaxs.t.(i=1，2，m； j=1，2，n)矩陣形式：CXzmin0XAXbs.t.

3、 1.運輸問題模型及其求解思路運輸問題模型及其求解思路1 1 1 1 1 11 1 11 1 11 1 11 1 1 A=m 行n 行 1.運輸問題模型及其求解思路運輸問題模型及其求解思路系數(shù)矩陣2 1.運輸問題模型及其求解思路運輸問題模型及其求解思路對于產(chǎn)銷平衡的運輸問題，對于產(chǎn)銷平衡的運輸問題，若產(chǎn)地為若產(chǎn)地為m個，銷地為個，銷地為n個，個，則則 變量個數(shù)為變量個數(shù)為mn個，個，約束條件個數(shù)為約束條件個數(shù)為m+n，其中包含：總產(chǎn)量總銷售其中包含：總產(chǎn)量總銷售故線性無關(guān)的約束條件個數(shù)為故線性無關(guān)的約束條件個數(shù)為m+n-1，基本解中的基變量個數(shù)為基本解中的基變量個數(shù)為m+n-1。v運輸問題求解

4、思路運輸問題求解思路表上作業(yè)法表上作業(yè)法v由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計算，則無法利用這些有利條性規(guī)劃單純形法求解計算，則無法利用這些有利條件。件。v人們在分析運輸規(guī)劃系數(shù)矩陣特征的基礎上建立了人們在分析運輸規(guī)劃系數(shù)矩陣特征的基礎上建立了針對運輸問題的針對運輸問題的表上作業(yè)法表上作業(yè)法。 1.運輸問題模型及其求解思路運輸問題模型及其求解思路v 表上作業(yè)法是單純形法在求解產(chǎn)銷平衡的運輸問題時的一表上作業(yè)法是單純形法在求解產(chǎn)銷平衡的運輸問題時的一種簡化方法，其實質(zhì)仍是單純形法，所不同的只是完成各種簡化方法，其實質(zhì)仍是單純

5、形法，所不同的只是完成各步采用的具體形式。步采用的具體形式。v 具體操作步驟如下：具體操作步驟如下：v （1）確定一個初始基本可行解：即在）確定一個初始基本可行解：即在mn階產(chǎn)銷平衡階產(chǎn)銷平衡表上給出表上給出m+n-1個數(shù)字格（個數(shù)字格（基變量基變量）；）；v （2）求各非基變量（空格）的檢驗數(shù)，即在表上）求各非基變量（空格）的檢驗數(shù)，即在表上計算空格的計算空格的檢驗數(shù)檢驗數(shù)。判別式否達到最優(yōu)解。如果是最優(yōu)解，。判別式否達到最優(yōu)解。如果是最優(yōu)解，則停止計算，否則進入下一步。則停止計算，否則進入下一步。v （3）確定換入變量和換出變量，找出新的基可行解。）確定換入變量和換出變量，找出新的基可行解

6、。v （4）重復）重復(2)、(3)直至得到最優(yōu)解為止直至得到最優(yōu)解為止。 1.運輸問題模型及其求解思路運輸問題模型及其求解思路2.確定初始基本可行解確定初始基本可行解1）最小元素法）最小元素法 基本思想：基本思想：就近供應就近供應，按運價最小的優(yōu)先調(diào)運原則確，按運價最小的優(yōu)先調(diào)運原則確定初始方案，即從單位運價表中選擇運價定初始方案，即從單位運價表中選擇運價最小的開始確定調(diào)運關(guān)系，然后次小。若最小的開始確定調(diào)運關(guān)系，然后次小。若某行（列）的產(chǎn)量（銷量）已滿足，則把某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，該行（列）的其他格劃去。如此進行下去，一直到給出初始基可行

7、解為止一直到給出初始基可行解為止 。 v 例如，某公司經(jīng)營某種產(chǎn)品，該公司下設例如，某公司經(jīng)營某種產(chǎn)品，該公司下設A、B、C三個三個生產(chǎn)廠，有甲、乙、丙、丁四個銷售點。公司每天把三個生產(chǎn)廠，有甲、乙、丙、丁四個銷售點。公司每天把三個工廠生產(chǎn)的產(chǎn)品分別運往四個銷售點，各工廠到各銷售點工廠生產(chǎn)的產(chǎn)品分別運往四個銷售點，各工廠到各銷售點的路程不同，單位產(chǎn)品的運費不同。各工廠每日的產(chǎn)量、的路程不同，單位產(chǎn)品的運費不同。各工廠每日的產(chǎn)量、各銷售點每日的銷量，以及從各工廠到各銷售點單位產(chǎn)品各銷售點每日的銷量，以及從各工廠到各銷售點單位產(chǎn)品的運價如下表。問該公司如何調(diào)運產(chǎn)品，在滿足各銷售點的運價如下表。問該

8、公司如何調(diào)運產(chǎn)品，在滿足各銷售點需要的前提下，使需要的前提下，使總運費最小總運費最小。甲甲乙乙丙丙丁丁產(chǎn)量產(chǎn)量A3113107B19284C741059銷量銷量36562.確定初始基本可行解確定初始基本可行解34333231242322211413121151047829103113minxxxxxxxxxxxxz06563947342414332313322212312111343332312423222114131211ijxxxxxxxxxxxxxxxxxxxxxxxxxs.t2.確定初始基本可行解確定初始基本可行解ijxv 若設 代表從第i個產(chǎn)地到第j個銷售地的運輸量（i=1,2,3；

9、j=1,2,3,4)B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量36563431632.確定初始基本可行解確定初始基本可行解Z=43+310+31+12+64+35=86為保證基變量的個數(shù)有為保證基變量的個數(shù)有m+n-1個，個，v1、每次填完數(shù)，只能劃去一行或一列，只、每次填完數(shù)，只能劃去一行或一列，只有最后一個格子例外。有最后一個格子例外。v2、用最小元素法時，可能會出現(xiàn)基變量個、用最小元素法時，可能會出現(xiàn)基變量個數(shù)還差兩個以上但只剩下一行或一列的情數(shù)還差兩個以上但只剩下一行或一列的情況，此時不能將剩下行或列按空格劃掉，況，此時不能將剩下行或列按空格劃掉，

10、應在剩下的空格中標上應在剩下的空格中標上0。（退化的基本可。（退化的基本可行解）行解）2.確定初始基本可行解確定初始基本可行解注意：注意：B1B2B3B4產(chǎn)量產(chǎn)量A13113108A219283A3741059銷量銷量36563530632.確定初始基本可行解確定初始基本可行解v）伏格爾法）伏格爾法v 伏格爾法的基本思想：如果某一地的產(chǎn)品不能按最小運費伏格爾法的基本思想：如果某一地的產(chǎn)品不能按最小運費就近供應，就考慮次小運費，兩者間就有一個差額。差額就近供應，就考慮次小運費，兩者間就有一個差額。差額越大，說明越大，說明費用增量費用增量越大。因而對差額最大處，優(yōu)先采用越大。因而對差額最大處，優(yōu)先

11、采用最小運費調(diào)運。最小運費調(diào)運。v 步驟：步驟：v 分別計算表中各行和各列中分別計算表中各行和各列中最小運費和次小運費的差最小運費和次小運費的差 額額，并填入表中的最右列和最下行。，并填入表中的最右列和最下行。v 從行和列的差額中選出最大者，選擇其所在行或列中的從行和列的差額中選出最大者，選擇其所在行或列中的最小元素，按類似于最小元素法優(yōu)先供應，劃去相應的行最小元素，按類似于最小元素法優(yōu)先供應，劃去相應的行或列。或列。v 對表中未劃去的元素，重復對表中未劃去的元素，重復 ，直到所有的行和列，直到所有的行和列都劃完為止。都劃完為止。2.確定初始基本可行解確定初始基本可行解B1B2B3B4兩最小元

12、素之差兩最小元素之差A1311310A21928A374105兩最小元素之差兩最小元素之差2.確定初始基本可行解確定初始基本可行解0112513B1B2B3B4兩最小元素之差兩最小元素之差A13113100A219281A3741052兩最小元素之兩最小元素之差差2132.確定初始基本可行解確定初始基本可行解B1B2B3B4兩最小元素之差兩最小元素之差A13113100A219281A374105兩最小元素之兩最小元素之差差2122.確定初始基本可行解確定初始基本可行解B1B2B3B4兩最小元素之差兩最小元素之差A13113107A219286A374105兩最小元素之兩最小元素之差差122.

13、確定初始基本可行解確定初始基本可行解B1B2B3B4兩最小元素之差兩最小元素之差A1311310A21928A374105兩最小元素之兩最小元素之差差22.確定初始基本可行解確定初始基本可行解B1B2B3B4兩最小元素之差兩最小元素之差A1311310A21928A374105兩最小元素之兩最小元素之差差2.確定初始基本可行解確定初始基本可行解B1B2B3B4產(chǎn)量產(chǎn)量A1527A2314A3639銷量銷量36562.確定初始基本可行解確定初始基本可行解Z=53+210+31+18+64+35=853.最優(yōu)性檢驗最優(yōu)性檢驗v檢驗數(shù)的意義：非基變量增加一個單位，檢驗數(shù)的意義：非基變量增加一個單位，

14、使目標函數(shù)值增加的數(shù)量。使目標函數(shù)值增加的數(shù)量。v運輸問題中目標函數(shù)值要求最小化，因此，運輸問題中目標函數(shù)值要求最小化，因此，當所有的檢驗數(shù)都當所有的檢驗數(shù)都大于或等于零大于或等于零時該調(diào)運時該調(diào)運方案就是最優(yōu)方案；否則不是。方案就是最優(yōu)方案；否則不是。v下面介紹兩種計算檢驗數(shù)的方法：下面介紹兩種計算檢驗數(shù)的方法：v1 1、閉回路法、閉回路法v閉回路：在已給出基本解的運輸表上，從一個非基閉回路：在已給出基本解的運輸表上，從一個非基變量出發(fā)，沿水平或豎直方向前進，只有碰到基變變量出發(fā)，沿水平或豎直方向前進，只有碰到基變量，才能向右或向左轉(zhuǎn)量，才能向右或向左轉(zhuǎn)9090o o ( (當然也可以不改變

15、方向）當然也可以不改變方向）繼續(xù)前進。繼續(xù)前進。v這樣繼續(xù)下去，總能回到出發(fā)的那個非基變量，由這樣繼續(xù)下去，總能回到出發(fā)的那個非基變量，由此路線形成的封閉曲線，叫閉回路。此路線形成的封閉曲線，叫閉回路。3.最優(yōu)性檢驗最優(yōu)性檢驗3.最優(yōu)性檢驗最優(yōu)性檢驗B1B2B3B4產(chǎn)量產(chǎn)量A13113 410 37A21 392 184A374 6105 39銷量銷量3656v若讓若讓x111，則總運費變化：，則總運費變化：31+231 。 11 =1v若讓若讓x311，則總運費變化：，則總運費變化：75+103+2-110 。 31 =103.最優(yōu)性檢驗最優(yōu)性檢驗63 24 = -13B49 33 = 12

16、6 31 = 10A3563銷量銷量41 22= 13A274 12 = 2A1產(chǎn)量產(chǎn)量B3B2B1 11 = 1v最優(yōu)標準：所有檢驗數(shù)最優(yōu)標準：所有檢驗數(shù) ij 0v2、位勢法、位勢法v 閉回路法的缺點：當變量個數(shù)較多時，尋找閉回路以及計算閉回路法的缺點：當變量個數(shù)較多時，尋找閉回路以及計算兩方面都容易出錯。兩方面都容易出錯。位勢法檢驗步驟：位勢法檢驗步驟：v 1）設產(chǎn)地設產(chǎn)地Ai對應的位勢量為對應的位勢量為ui ，銷地，銷地Bj對應的位勢量為對應的位勢量為vj；v 2）由）由 ij=Cij-（Ui+Vj）,利用對基變量而言有利用對基變量而言有 ij=0，計算位計算位勢勢Ui ， Vj ，即

17、即Cij-（Ui+Vj） = 0，令，令U1=0；v 3）再由）再由 ij=Cij-（Ui+Vj）計算非基變量的檢驗數(shù)計算非基變量的檢驗數(shù) ij3.最優(yōu)性檢驗最優(yōu)性檢驗B1B2B3B4uiA13 11 3 410 3A21 39 2 18A37 4 6105 3vju1 u2u3v1v2v3v40103-1-5293.最優(yōu)性檢驗最優(yōu)性檢驗B1B2B3B4uiA13 11 3 410 30A21 39 2 18-1A37 4 6105 3-5vj29310 ij=Cij-（Ui+Vj） 11=C11-（U1+V1）=3-(0+2)=1 12=C12-（U1+V2）=11-(0+9)=2(1)(2

18、)3.最優(yōu)性檢驗最優(yōu)性檢驗B1B2B3B4產(chǎn)量產(chǎn)量A1437A2314A3639銷量銷量36563.最優(yōu)性檢驗最優(yōu)性檢驗 33=12 11=1 22=1 31=10 24= -1 12=2當存在非基變量的檢驗數(shù)當存在非基變量的檢驗數(shù) ij 0，說明現(xiàn)行方案為最，說明現(xiàn)行方案為最優(yōu)方案，否則目標成本還可以進一步減小。優(yōu)方案，否則目標成本還可以進一步減小。3.最優(yōu)性檢驗最優(yōu)性檢驗v1、閉回路法計算式：、閉回路法計算式：v ij = (閉回路上的奇數(shù)頂點運價之和閉回路上的奇數(shù)頂點運價之和) - (閉回路上閉回路上的偶數(shù)頂點運價之和的偶數(shù)頂點運價之和)v2、位勢法計算式：、位勢法計算式：v ij =

19、cij - ui vj 當存在非基變量的檢驗數(shù)當存在非基變量的檢驗數(shù) ij 0，說明現(xiàn)行方案為，說明現(xiàn)行方案為最優(yōu)方案，否則目標成本還可以進一步減小。最優(yōu)方案，否則目標成本還可以進一步減小。4.方案調(diào)整方案調(diào)整閉回路調(diào)整法步驟：閉回路調(diào)整法步驟：1、入基變量的確定：選負檢驗數(shù)中最小者、入基變量的確定：選負檢驗數(shù)中最小者 rk，那，那么么 xrk 作為進基變量；（使總運費盡快減少）作為進基變量；（使總運費盡快減少）2、出基變量的確定：在進基變量、出基變量的確定：在進基變量xrk 的閉回路上，的閉回路上，選取偶數(shù)頂點上調(diào)運量最小的值，將其對應的運量選取偶數(shù)頂點上調(diào)運量最小的值，將其對應的運量作為出

20、基變量。（剛好有一個基變量出基，其它基作為出基變量。（剛好有一個基變量出基，其它基變量都為正）變量都為正）4.方案調(diào)整方案調(diào)整 即求即求 =Minxij 閉回路上的偶數(shù)頂點的閉回路上的偶數(shù)頂點的xij= xpq。那么那么確定確定xpq為出基變量，為出基變量， 為調(diào)整量；為調(diào)整量； 3、換基調(diào)整：對閉回路的奇數(shù)頂點運量調(diào)整為：、換基調(diào)整：對閉回路的奇數(shù)頂點運量調(diào)整為：xij+ ，對各偶數(shù)頂點運量調(diào)整為：，對各偶數(shù)頂點運量調(diào)整為：xij- ，特別，特別 xpq- =0，xpq變?yōu)榉腔兞?。變?yōu)榉腔兞俊?重復以上步驟，直到所有檢驗數(shù)均非負，即得到最優(yōu)重復以上步驟，直到所有檢驗數(shù)均非負，即得到最優(yōu)解

21、。解。4.方案調(diào)整方案調(diào)整B1B2B3B4產(chǎn)量產(chǎn)量A13 （1）11 （2）3 410 37A21 39 （1）2 18 （-1）4A37 （10）4 610 （12）5 39銷量銷量3656最小檢驗數(shù)最小檢驗數(shù)原則，確定原則，確定進基變量進基變量最小偶點原則，最小偶點原則，確定出基變量和確定出基變量和調(diào)整量調(diào)整量+1-1+1-1 13 , 1minmin14,23 xx四、方案調(diào)整B1B2B3B4產(chǎn)量產(chǎn)量aiA13 11 3 5 10 2 7A21 39 2 8 14A37 4 610 5 39銷量銷量bj3656v得到新的基變量：得到新的基變量：x13 = 5, x14 = 2, x21

22、= 3, x24 = 1, x32 = 6, x34 = 3。重新計算檢驗數(shù)。重新計算檢驗數(shù)。（1）（2）（2）（1）（9）（12）四、方案調(diào)整v經(jīng)過一次基變換，所有經(jīng)過一次基變換，所有 ij 0，已得到最優(yōu)解：，已得到最優(yōu)解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3，其它為，其它為0。v最優(yōu)值：最優(yōu)值：vf* =35+102+13+81+46+53 = 85表上作業(yè)法計算中的相關(guān)問題表上作業(yè)法計算中的相關(guān)問題v1.無窮多最優(yōu)解v 當最優(yōu)方案中存在某空格（非基變量）檢驗數(shù)為當最優(yōu)方案中存在某空格（非基變量）檢驗數(shù)為0,時，則時，則該運輸問題一定有多重最優(yōu)解。該運輸問題一定有多重最優(yōu)解。v2.退化解v 當運輸問題的最優(yōu)表中有數(shù)格（基變量）的運量為當運輸問題的最優(yōu)表中有數(shù)格（基變量）的運量為0，則，則出現(xiàn)退化。出現(xiàn)退化。v 1）確定基本可行解中，出現(xiàn)同時需要劃去一行和一列的）確定基本可行解中，出現(xiàn)同時需要劃去一行和一列的情況，則需要