運籌學(xué)第三章運輸問題

1、運輸問題運輸問題Transportation Problem主要內(nèi)容主要內(nèi)容運輸問題及其數(shù)學(xué)模型運輸問題及其數(shù)學(xué)模型運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法運輸問題運輸問題 把貨物從一系列起始地（把貨物從一系列起始地（sources）（如工廠、倉庫）運輸?shù)揭幌盗薪K點地（如工廠、倉庫）運輸?shù)揭幌盗薪K點地（destinations）（如倉庫、顧客）（如倉庫、顧客）如何分析這類問題？如何分析這類問題？例例1 某公司從兩個產(chǎn)地某公司從兩個產(chǎn)地A A1 1、A A2 2將物品運往三個銷地將物品運往三個銷地B B1 1、B B2 2、B B3 3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各，各產(chǎn)地的產(chǎn)量、各銷地的銷量

2、和各產(chǎn)地運往各銷地每件物品的單位運費如下表所產(chǎn)地運往各銷地每件物品的單位運費如下表所示，應(yīng)如何調(diào)運可使總運輸費用最小？示，應(yīng)如何調(diào)運可使總運輸費用最??？如何設(shè)置變量？111213212223111213212223112112221323min646655200300150. .1502000,1,2,1,2,3ijzxxxxxxxxxxxxxxstxxxxxij一般運輸模型 銷地銷地 產(chǎn)地產(chǎn)地B1B2Bn產(chǎn)量產(chǎn)量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam銷量銷量b1b2bnQ一般運輸問題的數(shù)學(xué)模型一般運輸問題的數(shù)學(xué)模型 m nMin z = cij xij

3、 i = 1 j = 1 n s.t. xij = ai i = 1,2,m j = 1 m xij = bj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n)運輸問題數(shù)學(xué)模型的特點運輸問題數(shù)學(xué)模型的特點運輸問題是否一定有運輸問題是否一定有最優(yōu)解最優(yōu)解？運輸問題模型的運輸問題模型的系數(shù)矩陣系數(shù)矩陣的特征的特征運輸問題運輸問題解的形式解的形式 1 1、平衡運輸問題必有可行解，也必有最優(yōu)解；、平衡運輸問題必有可行解，也必有最優(yōu)解； 2 2、運輸問題的基可行解中應(yīng)包括、運輸問題的基可行解中應(yīng)包括 m+n1 個基變量。個基變量。運輸問題的其它形式運輸問題的其它

4、形式 總供應(yīng)量總供應(yīng)量總需求量的情形總需求量的情形 目標(biāo)函數(shù)最大化的情形，如目標(biāo)是追求利潤目標(biāo)函數(shù)最大化的情形，如目標(biāo)是追求利潤或收入時，只需將或收入時，只需將目標(biāo)函數(shù)目標(biāo)函數(shù)改為改為maxmax即可即可 某些路線的運輸能力有一定限制的情形某些路線的運輸能力有一定限制的情形 某些運輸路線中斷情形，如由于自然災(zāi)害或某些運輸路線中斷情形，如由于自然災(zāi)害或勞動糾紛導(dǎo)致的勞動糾紛導(dǎo)致的 刪除變量刪除變量，單位運價改為，單位運價改為運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法建模建模給出初始的給出初始的基可行解基可行解判斷是否為最優(yōu)判斷是否為最優(yōu)解的改進解的改進 運輸表運輸表 最小元素法、西北角法、最小元素

5、法、西北角法、沃格爾法沃格爾法 閉回路法、位勢法閉回路法、位勢法 解的改進解的改進運輸表運輸表 銷地銷地 產(chǎn)地產(chǎn)地B1B2Bn產(chǎn)量產(chǎn)量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam銷量銷量b1b2bnQ初始調(diào)運方案初始調(diào)運方案（初始的基可行解）（初始的基可行解）最小元素法最小元素法西北角法西北角法沃格爾法沃格爾法最小元素法最小元素法 銷地銷地 產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量3656最小元素法最小元素法 銷地銷地 產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量365

6、6314363總的運輸費用（總的運輸費用（3 31 1）（）（6 64 4） （4 43 3）（）（1 12 2）（）（3 31010）（）（3 35 5）8686元元最小元素法最小元素法優(yōu)先滿足所有優(yōu)先滿足所有單位運價最小單位運價最小的位置的的位置的最大最大運量運量要求要求消掉產(chǎn)地或銷地（消掉一行或一列）消掉產(chǎn)地或銷地（消掉一行或一列）再優(yōu)先滿足再優(yōu)先滿足剩余的單位運價最小剩余的單位運價最小的位置的的位置的最大運量要求最大運量要求西北角法西北角法 銷地銷地 產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量3656總的運費總的運費(3(33)3)(4(4

7、11)11)(2(29)9)(2(22)2)(3(310)10)(6(65)5)135135元元342236沃格爾法沃格爾法 銷地銷地 產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量3656633512總的運費總的運費(3(35)5)(10(102)2)(1(13)3)(8(81)1)(4(46)6)(5(53)3)8585元元沃格爾法沃格爾法罰數(shù)如何計算罰數(shù)如何計算行罰數(shù)、列罰數(shù)是否等價行罰數(shù)、列罰數(shù)是否等價消掉行或列后罰數(shù)是否應(yīng)該重新計算消掉行或列后罰數(shù)是否應(yīng)該重新計算相等的罰數(shù)如何選取相等的罰數(shù)如何選取初始調(diào)運方案的比較初始調(diào)運方案的比較最小元素

8、法最小元素法西北角法西北角法沃格爾法沃格爾法一般情況下總運費較小一般情況下總運費較小便于計算機求解便于計算機求解最直觀的求解表現(xiàn)最直觀的求解表現(xiàn)最優(yōu)調(diào)運方案？最優(yōu)調(diào)運方案？檢驗檢驗最優(yōu)解的判別最優(yōu)解的判別閉回路法閉回路法位勢法位勢法檢驗數(shù)，基變量檢驗數(shù)，非基變量檢驗數(shù)檢驗數(shù)，基變量檢驗數(shù)，非基變量檢驗數(shù)所有非基變量檢驗數(shù)？所有非基變量檢驗數(shù)？最優(yōu)最優(yōu)閉回路法閉回路法閉回路是在已給出調(diào)運方案閉回路是在已給出調(diào)運方案的運輸表上的運輸表上從一個空格出發(fā)，從一個空格出發(fā)，沿水平或垂直方向前進，遇沿水平或垂直方向前進，遇到有數(shù)字的格直行或轉(zhuǎn)到有數(shù)字的格直行或轉(zhuǎn)9090度度，這樣繼續(xù)下去，直至回到出這樣繼

9、續(xù)下去，直至回到出發(fā)的那個空格，由此形成的發(fā)的那個空格，由此形成的封閉折線叫做閉回路。封閉折線叫做閉回路。每一個空格存在唯一的閉回每一個空格存在唯一的閉回路。路。311310431928317410563閉回路閉回路XX433X1XX6X3XX433X1XX6X3XX433X1XX6X3XX433X1XX6X3XX433X1XX6X33113 10192874 105121-110閉回路法閉回路法XX433X1XX6X3+1-1+1-1XX523X01X6X3X初始調(diào)運方案初始調(diào)運方案改進調(diào)運方案改進調(diào)運方案閉回路法閉回路法對于代表非基變量的空格（其調(diào)運量為零），對于代表非基變量的空格（其調(diào)運

10、量為零），把它的調(diào)運量調(diào)整為把它的調(diào)運量調(diào)整為1，由于產(chǎn)銷平衡的要求，由于產(chǎn)銷平衡的要求,我們必須對這個空格的閉回路的頂點的調(diào)運量我們必須對這個空格的閉回路的頂點的調(diào)運量加上或減少加上或減少1。最后計算出由這些變化給整個運輸方案的總運最后計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基變量的空輸費帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則零，則已求得最優(yōu)解，否則繼續(xù)迭代繼續(xù)迭代找出最優(yōu)找出最優(yōu)解。解。位勢法位勢法 對運輸表上的每一行賦予一個數(shù)值對運輸表上的每一行賦予一個數(shù)值ui

11、，對每一列賦，對每一列賦予一個數(shù)值予一個數(shù)值vj，它們的數(shù)值是由，它們的數(shù)值是由基變量基變量xij的檢驗數(shù)的檢驗數(shù) 所決定的所決定的 非基變量非基變量xij的檢驗數(shù)就可以用公式的檢驗數(shù)就可以用公式 求出求出0ijijijcuv（）ijijijcuv（）位勢法位勢法 銷地銷地產(chǎn)地產(chǎn)地 B1 B2 B3 B4 ui A1311310 X X 4 3 A21928 3 X 1X A374105 X 6 X 3 vj 3 10-59-12121-110120運量調(diào)整運量調(diào)整存在檢驗數(shù)存在檢驗數(shù)ij0，因此可以進行運量調(diào)整（即解的改，因此可以進行運量調(diào)整（即解的改進），使得總運費有所降低進），使得總運費

12、有所降低Min （ij0 ）xij畫出其閉回路，在閉回路頂點上進行畫出其閉回路，在閉回路頂點上進行運量調(diào)整運量調(diào)整選取所有偶數(shù)頂點的選取所有偶數(shù)頂點的min （xij ），令所有奇數(shù)頂點增加），令所有奇數(shù)頂點增加該運量，偶數(shù)頂點減少該運量，在為零的偶數(shù)頂點中選該運量，偶數(shù)頂點減少該運量，在為零的偶數(shù)頂點中選一對其所在格打叉，保證基變量的個數(shù)始終為一對其所在格打叉，保證基變量的個數(shù)始終為m+n-1個個310 4 328 1X12341250 x產(chǎn)銷不平衡的運輸問題產(chǎn)銷不平衡的運輸問題模型模型表上作業(yè)的實現(xiàn)表上作業(yè)的實現(xiàn)B1B2B3B4銷量銷量A12113470A21035950A3781270產(chǎn)產(chǎn)量量20304060B540000150190例：存在退化例：存在退化B1B2B3B4發(fā)量發(fā)量A1265315A2132112A3327413收量收量1013125運輸問題應(yīng)用運輸問題應(yīng)用有三個產(chǎn)地有三個產(chǎn)地A1-3A1-3，生產(chǎn)同一種物品，使用者為，生產(chǎn)同一種物品，使用者為B1-3B1-3，單位運價見下表。由于銷售需要和客觀條件的限制，單位運價見下表。由于銷售需要和客觀條件的限制，產(chǎn)地產(chǎn)地A1A1至少要發(fā)出至少要發(fā)出6 6個單位，最多能生產(chǎn)個單位，最多能生產(chǎn)1111個單位；產(chǎn)個單位；產(chǎn)地地A2A2必須發(fā)出必須發(fā)出7 7單位的產(chǎn)品；單位的產(chǎn)品；A3A3至少要發(fā)出至少要發(fā)出4 4個