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

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

3、 1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路1 1 1 1 1 11 1 11 1 11 1 11 1 1 A=m 行n 行 1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路系數(shù)矩陣2 1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路對于產(chǎn)銷平衡的運(yùn)輸問題，對于產(chǎn)銷平衡的運(yù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運(yùn)輸問題求解

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

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

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

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

8、公司如何調(diào)運(yùn)產(chǎn)品，在滿足各銷售點(diǎn)需要的前提下，使需要的前提下，使總運(yùn)費(fèi)最小總運(yùn)費(fèi)最小。甲甲乙乙丙丙丁丁產(chǎn)量產(chǎn)量A3113107B19284C741059銷量銷量36562.確定初始基本可行解確定初始基本可行解34333231242322211413121151047829103113minxxxxxxxxxxxxz06563947342414332313322212312111343332312423222114131211ijxxxxxxxxxxxxxxxxxxxxxxxxxs.t2.確定初始基本可行解確定初始基本可行解ijxv 若設(shè) 代表從第i個產(chǎn)地到第j個銷售地的運(yùn)輸量（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、應(yīng)在剩下的空格中標(biāo)上應(yīng)在剩下的空格中標(biāo)上0。（退化的基本可。（退化的基本可行解）行解）2.確定初始基本可行解確定初始基本可行解注意：注意：B1B2B3B4產(chǎn)量產(chǎn)量A13113108A219283A3741059銷量銷量36563530632.確定初始基本可行解確定初始基本可行解v）伏格爾法）伏格爾法v 伏格爾法的基本思想：如果某一地的產(chǎn)品不能按最小運(yùn)費(fèi)伏格爾法的基本思想：如果某一地的產(chǎn)品不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，兩者間就有一個差額。差額就近供應(yīng)，就考慮次小運(yùn)費(fèi)，兩者間就有一個差額。差額越大，說明越大，說明費(fèi)用增量費(fèi)用增量越大。因而對差額最大處，優(yōu)先采用越大。因而對差額最大處，優(yōu)先

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

12、素之差兩最小元素之差A(yù)1311310A21928A374105兩最小元素之差兩最小元素之差2.確定初始基本可行解確定初始基本可行解0112513B1B2B3B4兩最小元素之差兩最小元素之差A(yù)13113100A219281A3741052兩最小元素之兩最小元素之差差2132.確定初始基本可行解確定初始基本可行解B1B2B3B4兩最小元素之差兩最小元素之差A(yù)13113100A219281A374105兩最小元素之兩最小元素之差差2122.確定初始基本可行解確定初始基本可行解B1B2B3B4兩最小元素之差兩最小元素之差A(yù)13113107A219286A374105兩最小元素之兩最小元素之差差122.

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

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

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

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

17、即即Cij-（Ui+Vj） = 0，令，令U1=0；v 3）再由）再由 ij=Cij-（Ui+Vj）計(jì)算非基變量的檢驗(yàn)數(shù)計(jì)算非基變量的檢驗(yàn)數(shù) ij3.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)B1B2B3B4uiA13 11 3 410 3A21 39 2 18A37 4 6105 3vju1 u2u3v1v2v3v40103-1-5293.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)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)(

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

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

20、出基變量。（剛好有一個基變量出基，其它基作為出基變量。（剛好有一個基變量出基，其它基變量都為正）變量都為正）4.方案調(diào)整方案調(diào)整 即求即求 =Minxij 閉回路上的偶數(shù)頂點(diǎn)的閉回路上的偶數(shù)頂點(diǎn)的xij= xpq。那么那么確定確定xpq為出基變量，為出基變量， 為調(diào)整量；為調(diào)整量； 3、換基調(diào)整：對閉回路的奇數(shù)頂點(diǎn)運(yùn)量調(diào)整為：、換基調(diào)整：對閉回路的奇數(shù)頂點(diǎn)運(yùn)量調(diào)整為：xij+ ，對各偶數(shù)頂點(diǎn)運(yùn)量調(diào)整為：，對各偶數(shù)頂點(diǎn)運(yùn)量調(diào)整為：xij- ，特別，特別 xpq- =0，xpq變?yōu)榉腔兞?。變?yōu)榉腔兞俊?重復(fù)以上步驟，直到所有檢驗(yàn)數(shù)均非負(fù)，即得到最優(yōu)重復(fù)以上步驟，直到所有檢驗(yàn)數(shù)均非負(fù)，即得到最優(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最小檢驗(yàn)數(shù)最小檢驗(yàn)數(shù)原則，確定原則，確定進(jìn)基變量進(jìn)基變量最小偶點(diǎn)原則，最小偶點(diǎn)原則，確定出基變量和確定出基變量和調(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。重新計(jì)算檢驗(yàn)數(shù)。重新計(jì)算檢驗(yàn)數(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è)法計(jì)算中的相關(guān)問題表上作業(yè)法計(jì)算中的相關(guān)問題v1.無窮多最優(yōu)解v 當(dāng)最優(yōu)方案中存在某空格（非基變量）檢驗(yàn)數(shù)為當(dāng)最優(yōu)方案中存在某空格（非基變量）檢驗(yàn)數(shù)為0,時，則時，則該運(yùn)輸問題一定有多重最優(yōu)解。該運(yùn)輸問題一定有多重最優(yōu)解。v2.退化解v 當(dāng)運(yùn)輸問題的最優(yōu)表中有數(shù)格（基變量）的運(yùn)量為當(dāng)運(yùn)輸問題的最優(yōu)表中有數(shù)格（基變量）的運(yùn)量為0，則，則出現(xiàn)退化。出現(xiàn)退化。v 1）確定基本可行解中，出現(xiàn)同時需要劃去一行和一列的）確定基本可行解中，出現(xiàn)同時需要劃去一行和一列的情況，則需要