運(yùn)籌學(xué)運(yùn)輸問題

1、第四章 運(yùn)輸問題transportation problem第四章 運(yùn)輸問題第1節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型第2節(jié) 表上作業(yè)法第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法第4節(jié) 應(yīng)用問題舉例第1節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型一、運(yùn)輸問題運(yùn)輸問題屬于線性規(guī)劃問題，因?yàn)槠浼s束方程組的系數(shù)矩陣a具有特殊的結(jié)構(gòu)，所以專門介紹一種比單純形法更簡(jiǎn)便的求解方法，以節(jié)約計(jì)算時(shí)間和費(fèi)用。第1節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型例1：某食品公司經(jīng)銷的主要產(chǎn)品之一是糖果。它下面設(shè)有三個(gè)加工廠，每天的糖果生產(chǎn)量分別為a17t（噸）；a24t；a39t。該公司把這些糖果分別運(yùn)往四個(gè)地區(qū)的門市部銷售，各地區(qū)每天的銷售量為b13t（噸）；b26t；

2、b35t；b46t。已知從每個(gè)加工廠到各銷售門市部每噸糖果的運(yùn)價(jià)，如下表所示。試問該食品公司應(yīng)如何調(diào)運(yùn)，在滿足各門市部銷售需要的情況下，使總的運(yùn)費(fèi)支出最少。門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3749銷量3 6 5 6 門市部加工廠b1 b2 b3 b4a1a2a33 11 3 101 9 2 87 4 10 5第1節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型二、運(yùn)輸問題的數(shù)學(xué)模型已知有m個(gè)生產(chǎn)地點(diǎn)（簡(jiǎn)稱產(chǎn)地） 可供應(yīng)某種物資，其供應(yīng)量（產(chǎn)量）分別為 ；有n個(gè)銷售地點(diǎn)（簡(jiǎn)稱銷地） ，其需要量（銷量）分別為 ，從 到 運(yùn)輸單位物資的運(yùn)價(jià)（單位運(yùn)價(jià)）為 ，將這些數(shù)據(jù)表示在如下頁的兩個(gè)表中。問應(yīng)如何調(diào)運(yùn)，在

3、滿足各銷地銷量的情況下，使總的運(yùn)費(fèi)支出最少？(1,2,)jbjn(1,2,)ia im(1,2,)ia im(1,2,)jbjnjbijcia第1節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型產(chǎn)銷平衡表 兩個(gè)表合二為一 銷地產(chǎn)地b1 b2 bn產(chǎn)量a1a2ama1a2am銷量b1 b2 bn 銷地產(chǎn)地b1 b2 bna1a2amc11 c12 c1n c21 c22 c2n cm1 cm2 cmn銷地產(chǎn)地b1 b2 bn產(chǎn)量a1a2amc11 c12 c1n c21 c22 c2n cm1 cm2 cmna1a2am銷量b1 b2 bn 單位運(yùn)價(jià)表第1節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型例1：解：設(shè)xij為第i加工廠向第j門市

4、部的糖果的供應(yīng)量，cij表示第i加工廠向第j門市部供應(yīng)糖果的單位運(yùn)費(fèi)34111213143411111213142122232431323334112131122232132333142434min311310574936560 ( 12 312 3 4)ijijijijzxxxxxc xxxxxxxxxxxxxxxxxxxxxxxxxxij，= ， ， ； = ， ， ，第1節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型產(chǎn)銷平衡 運(yùn)輸問題的數(shù)學(xué)模型：設(shè)xij表示從產(chǎn)地ai運(yùn)往銷地bj的產(chǎn)品數(shù)量mniji=1j=1（a =b）1111min12120mnijijijnijijmijjiijzc xxaimxbjnx

5、， = ， ， ， = ， ， ，第1節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型特征（1）決策變量：mn（2）約束方程：mn；都是等式約束（3）目標(biāo)函數(shù)：最小化（4）約束方程組系數(shù)矩陣aa中只有數(shù)字0或1a的每一列只有兩個(gè)非零元素1（5）各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和（6）基變量：mn1（7）對(duì)于產(chǎn)銷平衡的運(yùn)輸問題，必有可行解和最優(yōu)解mniji=1j=1（a =b）第1節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型111213142122232431323334111100000000000011110000000000001111100010001000010001000100001000100010000100010001ap

6、pppppppppppa第2節(jié) 表上作業(yè)法一、表上作業(yè)法的解題思路表上作業(yè)法的實(shí)質(zhì)是單純形法在求解運(yùn)輸問題時(shí)的一種簡(jiǎn)化方法，屬于單純形法，又稱為運(yùn)輸單純形法?；尚薪庾顑?yōu)否結(jié)束換基是否第2節(jié) 表上作業(yè)法二、表上作業(yè)法的特點(diǎn)表上作業(yè)法是一種迭代法用表上作業(yè)法求解運(yùn)輸問題，直接在表上進(jìn)行，不必寫出數(shù)學(xué)模型第2節(jié) 表上作業(yè)法三、表上作業(yè)法的解題步驟（一）找出初始基可行解：在產(chǎn)銷平衡表上找出 (m+n-1)個(gè)數(shù)字格，形成初始產(chǎn)銷平衡表方法（二）求非基變量檢驗(yàn)數(shù)：計(jì)算初始產(chǎn)銷平衡表中空格的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解，如果已達(dá)到，停止計(jì)算；否則轉(zhuǎn)入3方法（三）確定換入變量和換出變量，找出新的基可行解方法：

7、閉回路調(diào)整法（四）重復(fù)（二）（三），直到求出最優(yōu)解最小元素法伏格爾法（vogel法）閉回路法位勢(shì)法（對(duì)偶變量法）第2節(jié) 表上作業(yè)法（一）確定初始基可行解方法一：最小元素法1、基本思路從運(yùn)費(fèi)上考慮，優(yōu)先安排單位運(yùn)價(jià)最小的產(chǎn)地和銷地之間的運(yùn)輸業(yè)務(wù)，最大限度地滿足其產(chǎn)銷量，從而實(shí)現(xiàn)“就近供應(yīng)”。第2節(jié) 表上作業(yè)法2、求解步驟第一，從單位運(yùn)價(jià)表中找出最小運(yùn)價(jià)，（有兩個(gè)或兩個(gè)以上的最小單位運(yùn)價(jià)，則任選其一），比較產(chǎn)量和銷量：產(chǎn)量銷量，則劃去該運(yùn)價(jià)所在列；產(chǎn)量銷量，則劃去該運(yùn)價(jià)所在行。并在初始產(chǎn)銷平衡表上填上相應(yīng)的數(shù)字。第二，從單位運(yùn)價(jià)表中未被劃去的運(yùn)價(jià)中再找最小運(yùn)價(jià)，重復(fù)第一第二，直到單位運(yùn)價(jià)表中所有運(yùn)

8、價(jià)都被劃去，并找出(m+n-1)個(gè)數(shù)字格。第2節(jié) 表上作業(yè)法例2：用最小元素法找出例1的初始基可行解。產(chǎn)銷平衡表和單位運(yùn)價(jià)表合二為一，如下所示：門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 3 11 3 10 1 9 2 8 7 4 10 5749銷量 3 6 5 6第2節(jié) 表上作業(yè)法例2：解： 初始產(chǎn)銷平衡表門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 4 33 1 6 3749銷量3 6 5 6第2節(jié) 表上作業(yè)法3、小結(jié)（1）在初始產(chǎn)銷平衡表上每填入一個(gè)數(shù)字，在單位運(yùn)價(jià)表上就劃去一行或一列（當(dāng)表中只剩一個(gè)元素時(shí)，在初始產(chǎn)銷平衡表上填數(shù)字時(shí)，在單位運(yùn)價(jià)表上同時(shí)劃去一行和一列）（2

9、）在單位運(yùn)價(jià)表上共劃去（mn）條直線，（相當(dāng)于單位運(yùn)價(jià)表上所有cij都被劃去兩次）（3）在初始產(chǎn)銷平衡表上填了（mn1）個(gè)數(shù)字格，每行數(shù)字之和該行產(chǎn)量，每列數(shù)字之和該列銷量第2節(jié) 表上作業(yè)法例3：用最小元素法求出下述運(yùn)輸問題的初始基可行解。門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 3 11 4 5 7 7 3 8 1 2 10 6749銷量 3 6 5 6第2節(jié) 表上作業(yè)法例3：解： 初始基可行解門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 0 1 6 0 4 3 6 0 0749銷量 3 6 5 6第2節(jié) 表上作業(yè)法例4：判斷下表給出的運(yùn)輸方案能否作為用最小元素法 求解出的初

10、始基可行解？銷地產(chǎn)地1 2 3 4產(chǎn)量1230 15 15 10515255銷量5 15 15 10第2節(jié) 表上作業(yè)法（一）確定初始基可行解方法二：伏格爾法1、基本思路按某一最小單位運(yùn)價(jià)優(yōu)先安排物品調(diào)運(yùn)時(shí)，可能導(dǎo)致其他產(chǎn)銷點(diǎn)不得不采用很高的單位運(yùn)價(jià)進(jìn)行運(yùn)輸，從而使整個(gè)運(yùn)輸費(fèi)用增加。對(duì)每一個(gè)產(chǎn)地或銷地，找出最小單位運(yùn)價(jià)和次小單位運(yùn)價(jià)，求二者之差。若差值不大，當(dāng)不能按最小單位運(yùn)價(jià)安排運(yùn)輸時(shí)造成的運(yùn)費(fèi)損失不大；反之，若二者之差很大，不按最小單位運(yùn)價(jià)組織運(yùn)輸就會(huì)造成很大損失，所以應(yīng)盡量按最小單位運(yùn)價(jià)安排運(yùn)輸。第2節(jié) 表上作業(yè)法2、求解步驟第一，在單位運(yùn)價(jià)表中分別計(jì)算各行和各列的最小運(yùn)價(jià)與次小運(yùn)價(jià)的差額

11、，并填在該表的最右列和最下行。第二，從行或列差額中選出最大者，（有兩個(gè)或兩個(gè)以上的最大差額，則選擇差額所在行（或列）中的最小單位運(yùn)價(jià)），選擇它所在行或列中的最小運(yùn)價(jià)，按照最小元素法確定初始基可行解。第三，對(duì)單位運(yùn)價(jià)表中未被劃去的運(yùn)價(jià)再計(jì)算各行和各列的最小運(yùn)價(jià)與次小運(yùn)價(jià)的差額，并仍填入該表的最右列和最下行，重復(fù)第二、三，直至給出初始基可行解為止，即找出（m+n-1）個(gè)數(shù)字格。第2節(jié) 表上作業(yè)法例5：用伏格爾法找出例1的初始基可行解。門市部加工廠b1 b2 b3 b4a1a2a33 11 3 101 9 2 87 4 10 5門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3749銷量3 6 5

12、6 第2節(jié) 表上作業(yè)法例5：解： 初始產(chǎn)銷平衡表門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 5 23 1 6 3749銷量3 6 5 6 第2節(jié) 表上作業(yè)法3、小結(jié)（1）伏格爾法和最小元素法僅在確定產(chǎn)銷關(guān)系的原則上不同，其余步驟都相同（伏格爾法是在最小元素法的基礎(chǔ)上改進(jìn)的一種方法）（2）伏格爾法給出的初始基可行解比用最小元素法給出的初始基可行解更接近最優(yōu)解（伏格爾法給出的解的目標(biāo)函數(shù)值比最小元素法給出的解的目標(biāo)函數(shù)值小）（3）伏格爾法得出的初始基可行解常作為運(yùn)輸問題最優(yōu)解的近似解作業(yè)10作業(yè)10：1、用最小元素法找出下述運(yùn)輸問題的初始基可行解。2、找出下述運(yùn)輸問題的近似最優(yōu)解。（其中m

13、為任意大正數(shù)，表示含義為從a4到b4不存在運(yùn)輸路線）銷地產(chǎn)地1 2 3產(chǎn)量1235 1 82 4 13 6 712144銷量9 10 11 銷地產(chǎn)地 1 2 3 4 5產(chǎn)量123410 2 3 15 9 5 10 15 2 415 5 14 7 1520 15 13 m 825302030銷量20 20 30 10 25 作業(yè)10答案1、2、銷地產(chǎn)地1 2 3產(chǎn)量1232 103 11412144銷量9 10 11 銷地產(chǎn)地 1 2 3 4 5產(chǎn)量1234 0 25 0 20 0 0 10 0 0 20 0 0 0 5 0 2525302030銷量20 20 30 10 25 49z 3224

14、20201010abab560z第2節(jié) 表上作業(yè)法（二）求檢驗(yàn)數(shù)，判別最優(yōu)解基本思路計(jì)算空格（非基變量）的檢驗(yàn)數(shù)，（運(yùn)輸問題的目標(biāo)函數(shù)要求實(shí)現(xiàn)最小化）當(dāng)所有檢驗(yàn)數(shù)0時(shí)，所得的解是最優(yōu)解，否則要進(jìn)行解的改進(jìn)。第2節(jié) 表上作業(yè)法（二）求檢驗(yàn)數(shù)，判別最優(yōu)解方法一：閉回路法1、求解步驟第一，在初始產(chǎn)銷平衡表上，從每一空格出發(fā)找一條閉回路：以某空格為起點(diǎn)，用水平或垂直線向前畫，碰到一數(shù)字格轉(zhuǎn)90（有些情況下也可以不改變方向），然后繼續(xù)前進(jìn)，直到回到起始空格為止。第二，在一閉回路上，令某空格取值為+1，表示增加的運(yùn)量，然后變化相應(yīng)數(shù)字格的值，并計(jì)算該閉回路上運(yùn)費(fèi)的變化值，即為該空格的檢驗(yàn)數(shù)，填入檢驗(yàn)數(shù)表。

15、第2節(jié) 表上作業(yè)法2、檢驗(yàn)數(shù)的含義檢驗(yàn)數(shù)表示變化的運(yùn)費(fèi)。即：若某空格（ai，bj）的檢驗(yàn)數(shù)0，表示將該空格變?yōu)閿?shù)字格使運(yùn)輸費(fèi)用減少，則當(dāng)前這個(gè)解不是最優(yōu)解；反之，若所有空格的檢驗(yàn)數(shù)都0，表示不管怎樣變換，都使運(yùn)輸費(fèi)用增加，則目標(biāo)函數(shù)已無法改進(jìn)，當(dāng)前這個(gè)解就是最優(yōu)解第2節(jié) 表上作業(yè)法例6：用閉回路法求例5所得的初始基可行解的檢驗(yàn)數(shù)。門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 5 23 1 6 3749銷量3 6 5 6 第2節(jié) 表上作業(yè)法例6：解： 檢驗(yàn)數(shù)表門市部加工廠b1 b2 b3 b4a1a2a3 0 2 2 1 9 12第2節(jié) 表上作業(yè)法例7：用閉回路法求例2所得的初始基可行解的

16、檢驗(yàn)數(shù)。門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 4 33 1 6 3749銷量3 6 5 6 第2節(jié) 表上作業(yè)法例7：解： 檢驗(yàn)數(shù)表門市部加工廠b1 b2 b3 b4a1a2a3 1 2 1 -110 12第2節(jié) 表上作業(yè)法3、小結(jié)（1）閉回路的頂點(diǎn)，除出發(fā)點(diǎn)為空格外，其他均為數(shù)字格（2）每個(gè)空格唯一存在一條閉回路（3）對(duì)于產(chǎn)銷點(diǎn)過多的運(yùn)輸問題，空格的數(shù)目很大，計(jì)算檢驗(yàn)數(shù)很繁瑣第2節(jié) 表上作業(yè)法（二）求檢驗(yàn)數(shù)，判別最優(yōu)解方法二：位勢(shì)法1、求解步驟第一，仿照初始產(chǎn)銷平衡表做一個(gè)表，在對(duì)應(yīng)的數(shù)字格處填入單位運(yùn)價(jià)cij。第二，在表的最右列和最下行分別增加一列ui和一行vj，使表中的單位運(yùn)

17、價(jià)等于它所在行和列的ui與vj之和，求出所有的ui和vj，并填寫在表中。第三，計(jì)算各空格的檢驗(yàn)數(shù)，填入檢驗(yàn)數(shù)表。第2節(jié) 表上作業(yè)法例8：用位勢(shì)法求例2所得的初始基可行解的檢驗(yàn)數(shù)。門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 4 33 1 6 3749銷量3 6 5 6 第2節(jié) 表上作業(yè)法例8：解： 檢驗(yàn)數(shù)表門市部加工廠b1 b2 b3 b4a1a2a3 1 2 1 -110 12第2節(jié) 表上作業(yè)法例9：用位勢(shì)法求例5所得的初始基可行解的檢驗(yàn)數(shù)。門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 5 23 1 6 3749銷量3 6 5 6 第2節(jié) 表上作業(yè)法例9：解： 檢驗(yàn)數(shù)表門市部加工

18、廠b1 b2 b3 b4a1a2a3 0 2 2 1 9 12第2節(jié) 表上作業(yè)法2、小結(jié)當(dāng)運(yùn)輸問題的產(chǎn)地和銷地很多時(shí)，空格的數(shù)目很大，采用位勢(shì)法計(jì)算檢驗(yàn)數(shù)簡(jiǎn)便第2節(jié) 表上作業(yè)法（三）確定換入和換出變量，找出新的基可行解，直至求出最優(yōu)解方法：閉回路調(diào)整法1、基本思想在初始產(chǎn)銷平衡表中，選取檢驗(yàn)數(shù)為負(fù)的所有空格中的最小者作為換入格，以對(duì)應(yīng)空格為出發(fā)點(diǎn)畫出閉回路，在經(jīng)過的數(shù)字格中選擇（-1）的最小者，對(duì)應(yīng)的數(shù)字格為換出格，然后對(duì)閉回路上各頂點(diǎn)的數(shù)據(jù)進(jìn)行調(diào)整，得到另一個(gè)更好的基可行解。第2節(jié) 表上作業(yè)法2、求解步驟第一，確定換入格。在初始產(chǎn)銷平衡表上，最小的負(fù)檢驗(yàn)數(shù)所在的空格為換入格，（有兩個(gè)或兩個(gè)以

19、上的最小者，則任選其一），并以此空格為出發(fā)點(diǎn)，作一閉回路。第二，確定換出格：選擇閉回路上標(biāo)記為-1的數(shù)字格中的最小者，記做，則該數(shù)字格為換出格。第三，調(diào)整：將閉回路上標(biāo)記為+1的數(shù)字格加，標(biāo)記為-1的數(shù)字格減，得到新的基可行解。第四，采用閉回路法或位勢(shì)法求空格的檢驗(yàn)數(shù)，若所有檢驗(yàn)數(shù)都0，則獲得最優(yōu)解；否則重復(fù)第一第三，直至求出最優(yōu)解。第2節(jié) 表上作業(yè)法例10：以例8所求的檢驗(yàn)數(shù)為依據(jù)，求例1的最優(yōu)解。 檢驗(yàn)數(shù)表 初始產(chǎn)銷平衡表門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 4 33 1 6 3749銷量3 6 5 6 門市部加工廠b1 b2 b3 b4a1a2a3 1 2 1 -110 1

20、2第2節(jié) 表上作業(yè)法例10：解： 最優(yōu)解 檢驗(yàn)數(shù)表 z*=85門市部加工廠b1 b2 b3 b4產(chǎn)量a1a2a3 5 23 1 6 3749銷量3 6 5 6 門市部加工廠b1 b2 b3 b4a1a2a3 0 2 2 1 9 12第2節(jié) 表上作業(yè)法四、表上作業(yè)法的解1、無窮多（多重）最優(yōu)解某個(gè)空格（非基變量）的檢驗(yàn)數(shù)為0時(shí)，該運(yùn)輸問題有無窮多（多重）最優(yōu)解。在已求得一個(gè)最優(yōu)解的表中，以這樣的空格出發(fā)做閉回路重新進(jìn)行調(diào)整，得到另一個(gè)最優(yōu)解。第2節(jié) 表上作業(yè)法2、退化解某個(gè)數(shù)字格（基變量）為0時(shí)，該運(yùn)輸問題為退化解。退化解出現(xiàn)的情況：確定初始解的各供需關(guān)系時(shí)，若在某格填入某數(shù)字后，出現(xiàn)該處的供應(yīng)

21、量與需求量相等。用閉回路調(diào)整法調(diào)整時(shí)，在閉回路上出現(xiàn)兩個(gè)或兩個(gè)以上的具有（-1）標(biāo)記的相等的最小值。第2節(jié) 表上作業(yè)法例11：已知某初始產(chǎn)銷平衡表，如下表：空格a2b4格的檢驗(yàn)數(shù)0，其余空格的檢驗(yàn)數(shù)均0 ，試確定換入、換出格，求出新的基可行解。銷地產(chǎn)地b1 b2 b3 b4產(chǎn)量a1a2a3 4 13 1 6 3549銷量3 6 5 4 第2節(jié) 表上作業(yè)法例11：解： 下一個(gè)基可行解銷地產(chǎn)地b1 b2 b3 b4產(chǎn)量a1a2a3 5 03 1 6 3549銷量3 6 5 4 第2節(jié) 表上作業(yè)法例11：解： 再下一個(gè)基可行解銷地產(chǎn)地b1 b2 b3 b4產(chǎn)量a1a2a30 53 1 6 3549銷

22、量3 6 5 4 第2節(jié) 表上作業(yè)法五、表上作業(yè)法計(jì)算步驟框圖分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案（最小元素法或伏格爾法）求檢驗(yàn)數(shù)（閉回路法或位勢(shì)法）所有檢驗(yàn)數(shù)0唯一最優(yōu)解算出總的運(yùn)價(jià)找出最小的負(fù)檢驗(yàn)數(shù)用閉回路調(diào)整，得出新的調(diào)運(yùn)方案是否某空格檢驗(yàn)數(shù)0是否無窮多最優(yōu)解第2節(jié) 表上作業(yè)法例12：已知三個(gè)產(chǎn)地a1，a2，a3，四個(gè)銷地b1，b2，b3，b4的產(chǎn)銷量即單位運(yùn)價(jià)如下表所示，求使總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。銷地產(chǎn)地 b1 b2 b3 b4產(chǎn)量a1a2a3 2 2 3 7 4 3 5 9 1 6 7 8 500600300銷量300 200 500 400第2節(jié) 表上作業(yè)法例12

23、：解： 無窮多最優(yōu)解、退化解 z*=6000銷地產(chǎn)地 b1 b2 b3 b4產(chǎn)量a1a2a3 0 500 200 0 400300 500600300銷量300 200 500 400作業(yè)11作業(yè)11：用表上作業(yè)法求解下列運(yùn)輸問題的最優(yōu)解。（要求采用伏格爾法、閉回路法求解）1、 2、銷地產(chǎn)地 甲 乙 丙 丁產(chǎn)量1233 7 6 42 4 3 24 3 8 5 523銷量3 3 2 2 銷地產(chǎn)地甲 乙 丙 丁產(chǎn)量12310 6 7 1216 10 5 9 5 4 10 10 494銷量5 2 4 6 作業(yè)11答案1、2、銷地產(chǎn)地 甲 乙 丙 丁產(chǎn)量1233 0 2 0 2 3 523銷量3 3

24、2 2 銷地產(chǎn)地甲 乙 丙 丁產(chǎn)量1231 2 1 3 64 494銷量5 2 4 6 32z無窮多最優(yōu)解，退化解118z唯一最優(yōu)解第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法一、求解思路總產(chǎn)量不等于總銷量，為使用表上作業(yè)法求解，將產(chǎn)銷不平衡運(yùn)輸問題轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問題。第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法二、求解方法1、總產(chǎn)量總銷量（ ）11mnijijab銷地產(chǎn)地b1 b2 bn產(chǎn)量a1a2amc11 c12 c1nc21 c22 c2n cm1 cm2 cmna1a2am銷量 b1 b2 bn第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法數(shù)學(xué)模型： 1111min12120mnijijijn

25、ijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法銷地產(chǎn)地b1 b2 bn bn+1產(chǎn)量a1a2amc11 c12 c1n 0c21 c22 c2n 0 cm1 cm2 cmn 0a1a2am銷量 b1 b2 bn bn+1 111mnnijijbab第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法解題思路：為借助于產(chǎn)銷平衡的表上作業(yè)法求解，增加一個(gè)假想的銷地bn+1，由于實(shí)際上它不存在，因而由產(chǎn)地ai（i=1，2，m）調(diào)運(yùn)到這個(gè)假想銷地的物品數(shù)量xi,n+1，就是就地存貯在ai的物品數(shù)量。就地存貯的物品未經(jīng)運(yùn)輸，所以其單位運(yùn)價(jià)c

26、i,n+1=0（i=1，2，m）。第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法數(shù)學(xué)模型：11111111min122110mmnijijijijijijijijmijjiijnnzc xc xxaimxbjnxn， = ， ， ， = ， ， ， ，第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法數(shù)學(xué)模型變化： 1111min12120mnijijijnijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，11111111min122110mmnijijijijijijijijmijjiijnnzc xc xxaimxbjnxn， = ， ， ， = ， ， ， ，第3節(jié) 產(chǎn)銷

27、不平衡的運(yùn)輸問題及其求解方法2、總產(chǎn)量總銷量（ ）11mnijijab銷地產(chǎn)地b1 b2 bn產(chǎn)量a1a2amc11 c12 c1n c21 c22 c2n cm1 cm2 cmna1a2am銷量 b1 b2 bn第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法數(shù)學(xué)模型：1111min12120mnijijijnijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法銷地產(chǎn)地b1 b2 bn產(chǎn)量a1a2amam+1c11 c12 c1n c21 c22 c2n cm1 cm2 cmn 0 0 0a1a2amam+1銷量 b1 b2 bn

28、111nmmjijiaba第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法解題思路：為借助于產(chǎn)銷平衡的表上作業(yè)法求解，增加一個(gè)假想的產(chǎn)地am+1，由于實(shí)際上它不存在，因而由它發(fā)往各個(gè)銷地的物品數(shù)量xm+1,j（j=1，2，n），就是各銷地bj所需物品的欠缺額。欠缺的物品未經(jīng)運(yùn)輸，所以其單位運(yùn)價(jià)cm+1,j=0（j=1，2，n）。第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法數(shù)學(xué)模型：11111111min112120nmnijijijijijijnijijijjiijmmzc xc xxaimxbjmnx， = ， ， ， ， = ， ， ，第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法數(shù)學(xué)模型變化： 1111m

29、in12120mnijijijnijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，11111111min112120nmnijijijijijijnijijijjiijmmzc xc xxaimxbjmnx， = ， ， ， ， = ， ， ，第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法例13：用表上作業(yè)法求解下述運(yùn)輸問題的最優(yōu)解。銷地產(chǎn)地b1 b2 b3 b4產(chǎn)量a1a2a3 2 11 3 410 3 5 9 7 8 1 2 757銷量2 3 4 6 第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法例13：解： 不產(chǎn)銷平衡產(chǎn)銷平衡銷地產(chǎn)地b1 b2 b3 b4 b5產(chǎn)量a

30、1a2a3 2 11 3 4 010 3 5 9 0 7 8 1 2 0 757銷量2 3 4 6 4 1915+4第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法 無窮多最優(yōu)解 z*=35銷地產(chǎn)地b1 b2 b3 b4 b5產(chǎn)量a1a2a3 2 3 2 3 2 4 3 757銷量2 3 4 6 4 1915+4第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法小結(jié)采用最小元素法或伏格爾法求初始基可行解時(shí)，由于虛擬產(chǎn)地或銷地不存在，所以盡管二者的單位運(yùn)價(jià)ci,n+1=0或cm+1,j=0，但不能作為最小運(yùn)價(jià)（元素）優(yōu)先使用。應(yīng)從有實(shí)際運(yùn)輸任務(wù)的產(chǎn)地或銷地之間安排運(yùn)量，最后再考慮虛擬產(chǎn)、銷地的0運(yùn)價(jià)。作業(yè)12作業(yè)

31、12：用表上作業(yè)法求解下列運(yùn)輸問題的最優(yōu)調(diào)運(yùn)方案和最小總運(yùn)費(fèi)。（要求采用最小元素法、位勢(shì)法求解）1、 2、 銷地產(chǎn)地 b1 b2 b3 b4產(chǎn)量a1a2a3 3 5 9 4 7 4 8 5 9 7 5 2 300500600銷量150 100 400 450銷地產(chǎn)地b1 b2 b3產(chǎn)量a1a2 6 5 4 3 7 21525銷量20 10 15作業(yè)12答案1、2、銷地產(chǎn)地 b1 b2 b3 b4 b5產(chǎn)量a1a2a3150 150 100 100 300 400 200 300500600銷量150 100 400 450 30014001100+300銷地產(chǎn)地b1 b2 b3產(chǎn)量a1a2a3

32、 10 515 10 515255銷量20 10 1540+5454350z2無窮多最優(yōu)解（a 余300）135z1無窮多最優(yōu)解（b 缺5）第4節(jié) 應(yīng)用問題舉例例14：設(shè)有三個(gè)化肥廠（a，b，c）供應(yīng)四個(gè)地區(qū)1，2，3，4的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)如下表所示。試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)運(yùn)方案。需求地區(qū)化肥廠 1 2 3 4產(chǎn)量（萬噸）abc16 13 22 1714 13 19 1519 20 23 506050最低需求（萬噸）最高需求（萬噸）30 70 0 1050 70 30 不限 第4節(jié) 應(yīng)用問題舉例例14：解： 不產(chǎn)銷平衡產(chǎn)銷平衡需求地區(qū)化肥廠 1122 3 344產(chǎn)量（萬噸）abcd16