數(shù)學(xué)建模運輸問題

1、 運輸問題模型運輸問題模型 Transportation一問題的提出一問題的提出 門市部門市部加工廠加工廠B1B2B3B4A1311310A21928A374105公司把這些糖果分別運往四個地區(qū)的門市部銷售，公司把這些糖果分別運往四個地區(qū)的門市部銷售，各地區(qū)每天的銷售量分別為：各地區(qū)每天的銷售量分別為： B1 13 3噸，噸，B26 6噸，噸，B35 5噸，噸，B46 6噸。噸。A17 噸，噸，A24噸，噸，A39噸。噸。某食品公司主要經(jīng)營糖果。某食品公司主要經(jīng)營糖果。它下面設(shè)有三個加工廠，它下面設(shè)有三個加工廠，每天的糖果生產(chǎn)量分別為：每天的糖果生產(chǎn)量分別為：已知從每個加工廠到各銷售門市部每噸

2、糖果的運價如上表所示，已知從每個加工廠到各銷售門市部每噸糖果的運價如上表所示，該食品公司應(yīng)如何調(diào)運，在滿足各門市部銷售需要的情況下，該食品公司應(yīng)如何調(diào)運，在滿足各門市部銷售需要的情況下，使總的運費支出為最少。使總的運費支出為最少。二問題的概述二問題的概述在線性規(guī)劃中研究這樣一類問題：在線性規(guī)劃中研究這樣一類問題：有某種物資需要調(diào)運，這種物資的計量單位可以是重量，有某種物資需要調(diào)運，這種物資的計量單位可以是重量， 包裝單位或其他。包裝單位或其他。已知已知: :有有m 個地點可以供應(yīng)該種物資（統(tǒng)稱產(chǎn)地，用個地點可以供應(yīng)該種物資（統(tǒng)稱產(chǎn)地，用 i =1,m 表示）；表示）；有有 n 個地點需要該種物

3、資（統(tǒng)稱銷地，用個地點需要該種物資（統(tǒng)稱銷地，用 j =1,n 表示）。表示）。n 個銷地的需要量（統(tǒng)稱銷量）為個銷地的需要量（統(tǒng)稱銷量）為b1 , b2, , bn（統(tǒng)寫為（統(tǒng)寫為 b j ）。）。從第從第 i 個產(chǎn)地到第個產(chǎn)地到第 j 個銷地的單位物資運價為個銷地的單位物資運價為c i j 。又知又知m 個產(chǎn)地的可供量（統(tǒng)稱產(chǎn)量）為個產(chǎn)地的可供量（統(tǒng)稱產(chǎn)量）為a1 , a2, , am（統(tǒng)寫為（統(tǒng)寫為a i ）；）；上面這些數(shù)據(jù)通常用產(chǎn)銷平衡表和單位運價表來表示。上面這些數(shù)據(jù)通常用產(chǎn)銷平衡表和單位運價表來表示。 銷地銷地產(chǎn)地產(chǎn)地12n產(chǎn)量產(chǎn)量12.ma1a2.am銷量銷量b1b2bn 銷地

4、銷地產(chǎn)地產(chǎn)地1 2 n12.mc11 c12 c1nc21 c22 c2n. . . . . . . .cm1 cm2 cmn產(chǎn)銷平衡表產(chǎn)銷平衡表單位運價表單位運價表有時候把兩個表寫在一起有時候把兩個表寫在一起: : 銷地銷地產(chǎn)地產(chǎn)地1 2 n12.mc11 c12 c1nc21 c22 c2n. . . . . . . .cm1 cm2 cmn 銷地銷地產(chǎn)地產(chǎn)地12n產(chǎn)產(chǎn)量量12.ma1a2.am銷量銷量b1b2bn 銷地銷地產(chǎn)地產(chǎn)地1 2 n產(chǎn)產(chǎn)量量12.mc11 c12 c1nc21 c22 c2n. . . . . . . .cm1 cm2 cmna1a2.am銷量銷量b1 b2 bn

5、三運輸問題模型三運輸問題模型設(shè)設(shè) xij 代表從第代表從第 i 個產(chǎn)地調(diào)運給個產(chǎn)地調(diào)運給第第 j 個銷地的物資數(shù)量。個銷地的物資數(shù)量。在產(chǎn)銷平衡的條件下在產(chǎn)銷平衡的條件下，要求解，要求解運輸問題使總的運費支出最小，運輸問題使總的運費支出最小，則有如下的運輸問題數(shù)學(xué)模型：則有如下的運輸問題數(shù)學(xué)模型：0ijx),1(1njbxjmiij),1(1miaxinjij minjijijxcz11min 銷地銷地產(chǎn)地產(chǎn)地1 2 n產(chǎn)產(chǎn)量量12.mx11 x12 x1nx21 x22 x2n. . . . . . . .xm1 xm2 xmna1a2.am銷量銷量b1 b2 bn 銷地銷地產(chǎn)地產(chǎn)地1 2

6、n產(chǎn)產(chǎn)量量12.mc11 c12 c1nc21 c22 c2n. . . . . . . .cm1 cm2 cmna1a2.am銷量銷量b1 b2 bn 0),1(),1(min1111ijjmiijinjijminjijijxnjbxmiaxxcz如果用單純形法求解，如果用單純形法求解，先要在每個約束條件左端加上一個人工變量，先要在每個約束條件左端加上一個人工變量，因此即使象食品公司調(diào)運糖果這樣簡單的數(shù)學(xué)問題，因此即使象食品公司調(diào)運糖果這樣簡單的數(shù)學(xué)問題，變量數(shù)就有變量數(shù)就有 34+3+4=19=19個之多，計算起來非常繁雜。個之多，計算起來非常繁雜。運輸問題的數(shù)學(xué)模型結(jié)構(gòu)比較特殊，運輸問題

7、的數(shù)學(xué)模型結(jié)構(gòu)比較特殊，它的約束條件變量的系數(shù)矩陣具有如下的形式：它的約束條件變量的系數(shù)矩陣具有如下的形式：運輸問題的數(shù)學(xué)模型包含運輸問題的數(shù)學(xué)模型包含 mn個變量，個變量， ( (m+n) )個約束條件。個約束條件。說明：說明： 0),1(),1(min1111ijjmiijinjijminjijijxnjbxmiaxxcz產(chǎn)銷不平衡的運輸問題產(chǎn)銷不平衡的運輸問題minjjiba111 1產(chǎn)大于銷產(chǎn)大于銷1 1）數(shù)學(xué)模型）數(shù)學(xué)模型 銷地銷地產(chǎn)地產(chǎn)地1 2 n產(chǎn)產(chǎn)量量12.mx11 x12 x1nx21 x22 x2n. . . . . . . .xm1 xm2 xmna1a2.am銷量銷量b

8、1 b2 bnminjijijxcz11min0),1(),1(11ijmijijnjiijxnjbxmiaxs.t.產(chǎn)大于銷時，增加一個假想的銷地產(chǎn)大于銷時，增加一個假想的銷地 j = = n+1+1（庫存），（庫存），2 2）求解方法）求解方法: : 轉(zhuǎn)化為產(chǎn)銷平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題該銷地的總需求量為該銷地的總需求量為minjjiba11而在單位運價表中從各產(chǎn)地到假想銷地的單位運價為而在單位運價表中從各產(chǎn)地到假想銷地的單位運價為就轉(zhuǎn)化為一個產(chǎn)銷平衡的運輸問題。就轉(zhuǎn)化為一個產(chǎn)銷平衡的運輸問題。 具體做法如下：具體做法如下： 銷地銷地產(chǎn)地產(chǎn)地 1 2 n產(chǎn)量產(chǎn)量12.m c11 c12 c

9、1n c21 c22 c2n . . . . . . . . . cm1 cm2 cmna1a2.am銷量銷量 b1 b2 bnn+100.0庫存庫存01,nic minjjiba112.2.銷大于產(chǎn)銷大于產(chǎn) 銷地銷地產(chǎn)地產(chǎn)地1 2 n產(chǎn)產(chǎn)量量12.mx11 x12 x1nx21 x22 x2n. . . . . . . .xm1 xm2 xmna1a2.am銷量銷量b1 b2 bn 0),1(),1(.min 1111ijjmiijinjijminjijijxnjbxmiaxtsxcz1 1）數(shù)學(xué)模型）數(shù)學(xué)模型miinjjab11銷大于產(chǎn)時，在產(chǎn)銷平衡表中增加一個假想的產(chǎn)地銷大于產(chǎn)時，在產(chǎn)銷

10、平衡表中增加一個假想的產(chǎn)地 i = m+1，該地產(chǎn)量為該地產(chǎn)量為在單位運價表中，在單位運價表中，從假想產(chǎn)地到各銷地的單位運價為從假想產(chǎn)地到各銷地的單位運價為 就轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題。就轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題。具體做法如下：具體做法如下： 銷地銷地產(chǎn)地產(chǎn)地 1 2 n產(chǎn)量產(chǎn)量12.m c11 c12 c1n c21 c22 c2n . . . . . . . . . cm1 cm2 cmna1a2.am銷量銷量 b1 b2 bnm+1 0 0 0 短缺短缺 0,1 jmc2 2）求解方法）求解方法: : 轉(zhuǎn)化為產(chǎn)銷平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題應(yīng)用實例應(yīng)用實例設(shè)有設(shè)有A1 1、A2 2、A3

11、3三個產(chǎn)地生產(chǎn)某種物資，產(chǎn)量分別為三個產(chǎn)地生產(chǎn)某種物資，產(chǎn)量分別為7 7、5 5、7 7噸，噸，B1 1、B2 2、B3 3、B4 4四個銷地需要該物資，銷量分別為四個銷地需要該物資，銷量分別為2 2、3 3、4 4、6 6噸。噸。又知各產(chǎn)銷地之間的單位運價見下表，又知各產(chǎn)銷地之間的單位運價見下表，試決定總運費最少的調(diào)運方案。試決定總運費最少的調(diào)運方案。 銷地銷地產(chǎn)地產(chǎn)地 B1 1 B2 2 B3 3 B4 4 A1 1A2 2A3 3 2 2 11 11 3 3 4 4 10 10 3 3 5 5 9 9 7 7 8 8 1 1 2 2解：解： 產(chǎn)地總產(chǎn)量為產(chǎn)地總產(chǎn)量為1919噸，噸， 銷地

12、總銷量為銷地總銷量為1515噸，噸， 這是一個產(chǎn)大于銷的運輸問題。這是一個產(chǎn)大于銷的運輸問題。 首先轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題，首先轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題， 其產(chǎn)銷平衡表和單位運價表分別見下兩表。其產(chǎn)銷平衡表和單位運價表分別見下兩表。 銷地銷地產(chǎn)地產(chǎn)地 B1 1 B2 2 B3 3 B4 4 庫存庫存產(chǎn)產(chǎn)量量A1 1A2 2A3 37 75 57 7銷量銷量 2 3 4 6 2 3 4 6 4 4A17噸，噸，A25噸，噸，A37 7噸。噸。B12噸，噸，B23噸，噸，B34噸，噸，B46 6噸。噸。 銷地銷地產(chǎn)地產(chǎn)地 B1 1 B2 2 B3 3 B4 4 A1 1A2 2A3 3 2 2

13、11 11 3 3 4 4 10 10 3 3 5 5 9 9 7 7 8 8 1 1 2 2 銷地銷地產(chǎn)地產(chǎn)地 B1 1 B2 2 B3 3 B4 4 庫存庫存A1 1A2 2A3 3 2 2 11 11 3 3 4 4 0 0 10 10 3 3 5 5 9 9 0 0 7 7 8 8 1 1 2 2 0 0用表上作業(yè)法計算，用表上作業(yè)法計算，求得最優(yōu)調(diào)運方案為：求得最優(yōu)調(diào)運方案為： 銷地銷地產(chǎn)地產(chǎn)地 B1 1 B2 2 B3 3 B4 4 庫存庫存產(chǎn)量產(chǎn)量A1 1A2 2A3 3 2 2 3 3 2 2 3 3 2 2 4 3 4 3 7 5 7銷量銷量 2 3 4 6 2 3 4 6

14、4 4 銷地銷地產(chǎn)地產(chǎn)地 B1 1 B2 2 B3 3 B4 4 A1 1A2 2A3 3 2 2 11 11 3 3 4 4 10 10 3 3 5 5 9 9 7 7 8 8 1 1 2 2 銷地銷地產(chǎn)地產(chǎn)地 B1 1 B2 2 B3 3 B4 4 產(chǎn)量產(chǎn)量A1 1A2 2A3 3 x11 11 x12 12 x13 13 x1414 x21 21 x22 22 x23 23 x2424 x31 31 x32 32 x33 33 x34347 75 57 7銷量銷量 2 3 4 62 3 4 6 06432757.min 3424143323133222123121113433323124

15、232221141312113141ijijijijxxxxxxxxxxxxxxxxxxxxxxxxxtsxczLINGOLINGO求解求解Global optimal solution found at iteration: 8Objective value: 35.00000設(shè)有三個電視機廠供應(yīng)四個地區(qū)某種型號的電視機。設(shè)有三個電視機廠供應(yīng)四個地區(qū)某種型號的電視機。各廠家的年產(chǎn)量、各廠家的年產(chǎn)量、各地區(qū)的年銷售量以及各地區(qū)的年銷售量以及各地區(qū)的單位運價各地區(qū)的單位運價如右表，如右表，試求出總的運費最省的試求出總的運費最省的電視機調(diào)撥方案。電視機調(diào)撥方案。 銷地銷地廠家廠家 B1 B2 B3

16、 B4 產(chǎn)量產(chǎn)量(萬臺萬臺)A1A2A3 6 3 12 6 4 3 9 9 10 13 10101210最低需求（萬臺）最低需求（萬臺）最高需求（萬臺）最高需求（萬臺） 6 14 0 5 10 14 6 不限不限 銷地銷地廠家廠家 B1 B1 B2 B3 B4 B4 產(chǎn)量產(chǎn)量（萬臺）（萬臺）A1A2A3 6 6 3 12 6 6 4 4 3 9 9 9 10 13 10 10 101210銷量銷量 6 4 14 6 5 712A410MMM000M M 銷地銷地廠家廠家 B1 B1 B2 B3 B4 B4 產(chǎn)量產(chǎn)量（萬臺）（萬臺）A1A2A3A4 10 6 2 4 2 5 3 6 410121

17、010銷量銷量 6 4 14 6 5 3+4總運價總運價:172元元LingoLingo求解求解 銷地銷地廠家廠家 B1 B1 B2 B3 B4 B4 產(chǎn)量產(chǎn)量（萬臺）（萬臺）A1A2A3A4 10 4 4 4 2 5 3 6 410121010銷量銷量 4 6 14 6 5 3+4Global optimal solution found at iteration: 8Objective value: 172.00001014131211 xxxx12232221 xxx1034333231 xxxx106312111 xxx14322212 xxx6332313 xxx53414 xx 銷

18、地銷地廠家廠家 B1 B2 B3 B4 產(chǎn)量產(chǎn)量(萬臺萬臺)A1A2A3 6 3 12 6 4 3 9 9 10 13 10101210最低需求（萬臺）最低需求（萬臺）最高需求（萬臺）最高需求（萬臺） 6 14 0 5 10 14 6 不限不限銷地銷地廠家廠家1 2 3 4123x11 x12 x13 x14x21 x22 x23 x24x31 x32 x33 x3434333231242322211413121110131091000 93461236minxxxxxxxxxxxxz 05614106101210.10131091000 93461236min3414332313322212

19、3121113433323123222114131211343332312423222114131211ijxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxxxzLingoLingo求解求解Global optimal solution found at iteration: 16Objective value: 172.0000 銷地銷地廠家廠家 B1 B2 B3 B4 產(chǎn)量產(chǎn)量(萬臺萬臺)A1A2A3 6 3 12 6 4 3 9 9 10 13 10101210最低需求（萬臺）最低需求（萬臺）最高需求（萬臺）最高需求（萬臺） 6 14 0 5 10 14 6 不限不

20、限 銷地銷地廠家廠家 B1 B2 B3 B4 產(chǎn)量產(chǎn)量(萬臺萬臺)A1A2A3 10 8 4 2 8101210最低需求（萬臺）最低需求（萬臺）最高需求（萬臺）最高需求（萬臺） 6 14 0 5 10 14 6 不限不限中轉(zhuǎn)調(diào)運問題中轉(zhuǎn)調(diào)運問題1.已知甲、乙兩處分別有已知甲、乙兩處分別有100噸和噸和85噸同種物資外運，噸同種物資外運， A、B、C三處各需要物資三處各需要物資55，60，70噸。噸。 物資可以直接運到目的地，也可以經(jīng)某些中轉(zhuǎn)點轉(zhuǎn)運。物資可以直接運到目的地，也可以經(jīng)某些中轉(zhuǎn)點轉(zhuǎn)運。 已知各處之間的單位運價如下表，試確定一個最優(yōu)的調(diào)運方案。已知各處之間的單位運價如下表，試確定一個最

21、優(yōu)的調(diào)運方案。甲甲乙乙甲甲乙乙010120ABC甲甲乙乙101514121218ABCABC0108140121140甲甲乙乙甲甲乙乙010120ABC甲甲乙乙101514121218ABCABC0108140121140ABC甲甲乙乙10151412121810085556070銷地銷地產(chǎn)地產(chǎn)地甲甲乙乙ABC產(chǎn)量產(chǎn)量甲甲乙乙ABC0101014121201512181015010814121401212181140銷量銷量甲甲乙乙ABC產(chǎn)量產(chǎn)量甲甲乙乙ABC8510055130851004525115185185130125115銷量銷量851001851851851851851301251

22、1585 100 185185 185用用LingoLingo求解求解甲甲A :55噸，噸，甲甲C C :45 :45噸噸; ; 乙乙B6060噸噸2525噸噸CGlobal optimal solution found at iteration: 10Objective value: 2210.000進一步討論：不考慮中轉(zhuǎn)調(diào)運。進一步討論：不考慮中轉(zhuǎn)調(diào)運。ABC甲甲乙乙10151412121810085556070用用LingoLingo求解求解Global optimal solution found at iteration: 3 Objective value: 2235.000ABC

23、甲甲乙乙3025607010085556070 門市部門市部加工廠加工廠B1B2B3B4A1311310A21928A374105公司把這些糖果分別運往四個地區(qū)公司把這些糖果分別運往四個地區(qū)的門市部銷售，各地區(qū)每天的銷售量分別為：的門市部銷售，各地區(qū)每天的銷售量分別為： B1 13 3噸，噸，B26 6噸，噸，B35 5噸，噸，B46 6噸。噸。A17 噸，噸，A24噸，噸，A39噸。噸。2.某食品公司主要經(jīng)營糖果。某食品公司主要經(jīng)營糖果。 它下面設(shè)有三個加工廠，它下面設(shè)有三個加工廠， 每天的糖果生產(chǎn)量分別為：每天的糖果生產(chǎn)量分別為：假設(shè)有四個中轉(zhuǎn)站假設(shè)有四個中轉(zhuǎn)站, ,每個加工廠生產(chǎn)的糖果在

24、運往銷地的過程中每個加工廠生產(chǎn)的糖果在運往銷地的過程中可以在產(chǎn)地、中轉(zhuǎn)站和銷地之間轉(zhuǎn)運?？梢栽诋a(chǎn)地、中轉(zhuǎn)站和銷地之間轉(zhuǎn)運。已知各產(chǎn)地、銷地和中轉(zhuǎn)站之間的單位運價如表所示，已知各產(chǎn)地、銷地和中轉(zhuǎn)站之間的單位運價如表所示，試確定總運費最少的調(diào)運方案。試確定總運費最少的調(diào)運方案。產(chǎn)產(chǎn) 地地中中 轉(zhuǎn)轉(zhuǎn) 地地銷銷 地地A1A2A3T1T2T3T4B1B2B3B4產(chǎn)產(chǎn)地地A1A2A301310-3-023115-4-2323317119432101085中中轉(zhuǎn)轉(zhuǎn)站站T1T2T3T4214335-21-2301321011310221202411858-42226746銷銷地地B1B2B3B43113101

25、928741052846452718241-260142102142032130B1 13 3噸，噸，B26 6噸，噸，B35 5噸，噸，B46 6噸噸總銷量：總銷量：2020噸噸A17 噸，噸，A24噸，噸，A39噸噸總產(chǎn)量：總產(chǎn)量：2020噸噸銷地銷地產(chǎn)地產(chǎn)地A1A2A3T1T2T3T4B1B2B3B4產(chǎn)產(chǎn)量量A1A2A301310-3-023115-4-2323317119432101085T1T2T3T4214335-21-2301321011310221202411858-42226746B1B2B3B43113101928741052846452718241-26014210214

26、2032130銷量銷量202020202020201714151413 16 1120 20 20 2020 20 20 20用用LingoLingo求解求解 Global optimal solution found at iteration: 41 Objective value: 68.00000 Variable Value Reduced CostVOLUME( WH1, C1) 13.00000 0.000000VOLUME( WH1, C2) 7.000000 0.000000VOLUME( WH2, C2) 9.000000 0.000000VOLUME( WH2, C8) 1

27、1.00000 0.000000VOLUME( WH3, C3) 11.00000 0.000000VOLUME( WH3, C6) 9.000000 0.000000VOLUME( WH4, C4) 20.00000 0.000000VOLUME( WH5, C5) 20.00000 0.000000VOLUME( WH6, C6) 11.00000 0.000000VOLUME( WH6, C8) 4.000000 0.000000VOLUME( WH6, C10) 5.000000 0.000000VOLUME( WH7, C7) 20.00000 0.000000VOLUME( WH8

28、, C8) 5.000000 0.000000VOLUME( WH8, C9) 6.000000 0.000000VOLUME( WH8, C11) 6.000000 0.000000VOLUME( WH9, C9) 14.00000 0.000000VOLUME( WH10, C10) 15.00000 0.000000VOLUME( WH11, C11) 14.00000 0.000000銷地銷地產(chǎn)地產(chǎn)地A1A2A3T1T2T3T4B1B2B3B4產(chǎn)產(chǎn)量量A1A2A3131379-3-1123115-4-93233117119432101085T1T2T3T4214335-21-23201

29、321201131112212202441858-42526746B1B2B3B43113101928741052846452718241-268142614214215361314銷量銷量202020202020201714151413 16 1120 20 20 2020 20 20 20 Global optimal solution found at iteration: 41 Objective value: 68.00000 直接調(diào)運：直接調(diào)運：8585元元614B4614B2155B320T420T2119T311A379A2B1T1A1B1B2B3B4T1T2T3T4A1A2A

30、384201113銷地銷地產(chǎn)地產(chǎn)地B1 13 3噸，噸，B26 6噸，噸，B35 5噸，噸，B46 6噸噸A17 噸，噸，A24噸，噸，A39噸噸667A1（7） A2（4+7） B1（11+4）11B2（6）B4（6）A3（9） T3（9）945B3（5）（設(shè)備生產(chǎn)計劃）（設(shè)備生產(chǎn)計劃） 某公司按照合同規(guī)定需要在當(dāng)年每個季度末分別提供某公司按照合同規(guī)定需要在當(dāng)年每個季度末分別提供1010、1515、2525、2020臺同一規(guī)格的某種機器設(shè)備。臺同一規(guī)格的某種機器設(shè)備。已知該公司各季度的生產(chǎn)能力以及生產(chǎn)每臺設(shè)備的成本下表。已知該公司各季度的生產(chǎn)能力以及生產(chǎn)每臺設(shè)備的成本下表。如果生產(chǎn)的設(shè)備當(dāng)季度不交貨，如果生產(chǎn)的設(shè)備當(dāng)季度不交貨，則每臺積壓一個季度所需的存儲、維護等費用為則每臺積壓一個季度所需的存儲、維護等費用為0.150.15萬元。萬元。試確定在完成合同任務(wù)的條件下，試確定在完成合同任務(wù)的條件下，使公司全年生產(chǎn)費用最小的設(shè)備生產(chǎn)計劃。使公司全年生產(chǎn)費用最小的設(shè)備生產(chǎn)計劃。季度季度生產(chǎn)能力（萬臺）生產(chǎn)能力（萬臺）單位成本（萬元）單位成本（萬元）1 12 23 34 4252535353030101010.810.811.111.111.011.011.311.3每臺