運輸問題的軟件求解

1、一、運輸問題與數(shù)學(xué)模型一、運輸問題與數(shù)學(xué)模型 二、運輸問題的二、運輸問題的LINGO求解法求解法 三、應(yīng)用案例分析三、應(yīng)用案例分析 引例： 某公司有三個分廠生產(chǎn)某種物資，分別運往四個地區(qū)的銷售公司去銷售，有關(guān)分廠的產(chǎn)量（噸）、各銷售公司的銷量（噸）及單位物資的運價（千元/噸）如下表所示，求總的運費最小的調(diào)運方案？ 銷地產(chǎn)地B1B2B3B4產(chǎn) 量A13113107A219284A3741059銷 量3656 銷地銷地產(chǎn)地產(chǎn)地 B1 B2 Bn產(chǎn)量產(chǎn)量 A1c11c21 c1n a1 A2c21c22 c2n a2 Amcm1cm2 cmn am銷量銷量 b1 b2 bn 運輸表運輸表1 1、產(chǎn)銷

2、平衡問題、產(chǎn)銷平衡問題即即11mnijijab 設(shè)設(shè) xij 表示產(chǎn)地表示產(chǎn)地 Ai 運往銷地運往銷地 Bj (i=1,2,m; j=1,2,n) 的運量的運量.11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn 銷地銷地產(chǎn)地產(chǎn)地 B1 B2 Bn產(chǎn)量產(chǎn)量 A1 x11c11 x12c12 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am銷量銷量 b1 b2 bn一、運輸問題與數(shù)學(xué)模型一、運輸問題與數(shù)學(xué)模型 2 2、產(chǎn)銷不平衡問題

3、、產(chǎn)銷不平衡問題（1） 11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn（2） 11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn二、運輸問題的二、運輸問題的LINGOLINGO求解方法求解方法針對產(chǎn)銷平衡的運輸問題模型，給出一般的針對產(chǎn)銷平衡的運輸問題模型，給出一般的LINGO模型如下模型如下 model:sets:row/1.m/: a; !m表示數(shù)組維數(shù),即為生產(chǎn)地的個數(shù) ar

4、range/1.n/:b; !n表示數(shù)組維數(shù),即為銷售地的個數(shù)link (row, arrange): c,x; !系數(shù)矩陣形狀endsetsData:a=a1,a2,am ; ! 各生產(chǎn)地的實際產(chǎn)量;b=b1,b2,bn ; ! 各銷售地的實際銷量;c=c(1,1),c(1,2),c(1,n),c(m,1),c(m,2),c(m,n); !單位運價系數(shù)矩陣；EnddataOBJmin=sum(link(i,j):c(i,j)*x(i,j); !目標(biāo)函數(shù)求最小for(row(i):sum(arrange(j):x(i,j)=a(i);); !約束條件for(arrange(j):sum(row

5、(i):x(i,j)=b(j);); !約束條件for(link(i,j):x(i,j)=0;); !非負約束END1. .nijijs txa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn11minmnijijijzc x例例1 1：某公司有三個分廠生產(chǎn)某種物資，分別運往四個地區(qū)的銷某公司有三個分廠生產(chǎn)某種物資，分別運往四個地區(qū)的銷售公司去銷售，有關(guān)分廠的產(chǎn)量、各銷售公司的銷量（噸）及運售公司去銷售，有關(guān)分廠的產(chǎn)量、各銷售公司的銷量（噸）及運價（千元價（千元/ /噸）如下表所示，求總的運費最小的調(diào)運方案？噸）如下表所示，求總的運費最小的調(diào)運方案？ B B1 1B

6、 B2 2B B3 3B B4 4產(chǎn)產(chǎn) 量量A A1 13 311113 310107 7A A2 21 19 92 28 84 4A A3 37 74 410105 59 9銷銷 量量3 36 65 56 6 解：解：設(shè)設(shè) xij 表示產(chǎn)地表示產(chǎn)地 Ai 運往銷地運往銷地 Bj (i=1,2,3;j=1,2,4) 的運量的運量.則則3411minijijijzc x41. .ijijstxa，1,2,3i 31ijjixb，1,2,4j 01,2,3;1,2,4ijxij其中，其中，123(,)(7,4,9)a a a其中，其中，1234( ,)(3,6,5,6)b b b b分析：分析：由

7、于三個產(chǎn)地總產(chǎn)量為由于三個產(chǎn)地總產(chǎn)量為7+4+9=20； 四個銷地的總銷四個銷地的總銷量為量為3+6+5+6=20，所以這是，所以這是一個產(chǎn)銷平衡問題。一個產(chǎn)銷平衡問題。求解該問題的LINGO程序如下model:sets:row/1.3/: a; arrange/1.4/:b; link (row, arrange): c,x; endsetsData:a=7,4,9 ;b=3,6,5,6;c=3,11,3,10,1,9,2,8,7,4,10,5; EnddataOBJmin=sum(link(i,j):c(i,j)*x(i,j); for(row(i):sum(arrange(j):x(i,

8、j)=a(i);); for(arrange(j):sum(row(i):x(i,j)=b(j);); for(link(i,j):x(i,j)=0;); ENDB B1 1B B2 2B B3 3B B4 4產(chǎn)產(chǎn) 量量A A1 13 311113 310107 7A A2 21 19 92 28 84 4A A3 37 74 410105 59 9銷銷 量量3 36 65 56 6三、應(yīng)用案例分析三、應(yīng)用案例分析 某制冰廠每年某制冰廠每年1 4 季度必須供季度必須供應(yīng)冰塊應(yīng)冰塊 15、20、25、10（千噸）（千噸）. .已知該廠各季度冰已知該廠各季度冰 塊的生產(chǎn)能力及冰塊的單位成本如表塊的

9、生產(chǎn)能力及冰塊的單位成本如表. . 如果生產(chǎn)出來如果生產(chǎn)出來的冰塊不在當(dāng)季度使用，每千噸冰塊存儲一個季度的冰塊不在當(dāng)季度使用，每千噸冰塊存儲一個季度費用為費用為4（千元）（千元）. .又設(shè)該制冰廠每年第又設(shè)該制冰廠每年第3季度末對貯季度末對貯冰庫進行清庫維修冰庫進行清庫維修. .問應(yīng)如何安排冰塊的生產(chǎn)，可使問應(yīng)如何安排冰塊的生產(chǎn)，可使該廠全年生產(chǎn)、該廠全年生產(chǎn)、存儲費用最少？存儲費用最少？試建立該問題試建立該問題的運輸模型。的運輸模型。季季 度度 生產(chǎn)能力（千噸）生產(chǎn)能力（千噸） 單位成本（千元）單位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 5例例 1 (生產(chǎn)調(diào)度問題生

10、產(chǎn)調(diào)度問題)季季 度度 生產(chǎn)能力（千噸）生產(chǎn)能力（千噸） 單位成本（千元）單位成本（千元） 1 25 52 18 7 3 16 8 4 15 5解：解：設(shè)設(shè)xij表示第表示第i季度生產(chǎn)季度生產(chǎn)第第j季度銷季度銷售的冰塊量售的冰塊量（千噸）（千噸） 1 4 季度冰塊需求季度冰塊需求量分別為：量分別為： 15、20、25、10（千噸）（千噸） 第第3季度末對貯季度末對貯冰庫進行清庫維修，且冰庫進行清庫維修，且每千噸冰塊存儲一個季每千噸冰塊存儲一個季度費用為度費用為 4（千元）（千元） Bj Ai B1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25

11、105913MMMMMM5118179137求解該問題的LINGO程序如下model:sets:row/1.4/: a; arrange/1.4/:b; link (row, arrange): c,x; endsetsData:a=25,18,16,15;b=15,20,25,10 ;c=5,9,13,10000, 10000,7,11,10000,10000,10000,8,10000,9,13,17,5; EnddataOBJmin=sum(link(i,j):c(i,j)*x(i,j); for(row(i):sum(arrange(j):x(i,j)=0;); END Bj Ai B

12、1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25 105913MMMMMM5118179137程序運行結(jié)果為：10, 1,16, 9, 9,11,1444413323221211xxxxxxx其余的)4 , 1; 4 , 1(0jixij且.518minz 所以，生產(chǎn)安排為：第一季度生產(chǎn)25噸冰，其中14噸當(dāng)季使用，11噸在第二季度使用；第二季度生產(chǎn)18噸冰，其中9噸當(dāng)季使用，9噸在第三季度使用；第三季度生產(chǎn)16噸冰，全部當(dāng)季使用；第四季度生產(chǎn)11噸冰，其中10噸當(dāng)季使用，1噸在下一年的第一季度使用。生產(chǎn)和存儲總費用為518千元。例例2 ( (

13、空車調(diào)度問題空車調(diào)度問題) ) 某航運公司承擔(dān)六個港口城市某航運公司承擔(dān)六個港口城市 A、B、C、D、E、F 的四條固定航線的物資運輸任的四條固定航線的物資運輸任務(wù)務(wù). . 已知各條航線的起點、終點城市及每天航班數(shù)見已知各條航線的起點、終點城市及每天航班數(shù)見表表1，假定各條航線使用相同型號的船只，又各城市間，假定各條航線使用相同型號的船只，又各城市間的航程天數(shù)見表的航程天數(shù)見表2. 又知每條船只每次裝卸貨的時間各又知每條船只每次裝卸貨的時間各需一天，則該航運公司至少應(yīng)配備多少條船，才能滿足需一天，則該航運公司至少應(yīng)配備多少條船，才能滿足所有航線的運貨需求？所有航線的運貨需求？航航線線起點起點城

14、市城市終點終點城市城市每天航班每天航班數(shù)數(shù)1ED32BC23AF14DB1表表1 1 到到從從ABCDEFA0121477B1031388C23015557851703F7852030表表2 2解解： 該公司所需配備船只分兩部分該公司所需配備船只分兩部分. .1 1載貨航程需要的周轉(zhuǎn)船只數(shù)載貨航程需要的周轉(zhuǎn)船只數(shù)航航線線起點起點城市城市終點終點城市城市每天航班每天航班數(shù)數(shù)1ED32BC23AF14DB1表表1 1 到到從從ABCDEFA0121477B1031388C23015557851703F7852030表表2 2 如航線如航線1，在港

15、口，在港口E 裝貨裝貨1 天，天，E 至至 D 航程航程17天，天，在在D 卸貨卸貨1天，總計天，總計19天天. . 每天每天3 航班，故該航線周轉(zhuǎn)航班，故該航線周轉(zhuǎn)船只需船只需5757條條. .航線航線裝貨天數(shù)裝貨天數(shù)航程天數(shù)航程天數(shù)卸貨天數(shù)卸貨天數(shù)小計小計航班數(shù)航班數(shù)需周轉(zhuǎn)船只數(shù)需周轉(zhuǎn)船只數(shù)11171193572131521031719194113115115累計共需周轉(zhuǎn)船只數(shù)累計共需周轉(zhuǎn)船只數(shù)91條條.2 2、各港口間調(diào)度所需船只數(shù)、各港口間調(diào)度所需船只數(shù)港口城市港口城市每天到達每天到達每天需求每天需求余缺數(shù)余缺數(shù)A01-1B12-1C202D312E03-3F101 港口每天到達與需要

16、的船只不同，如表港口每天到達與需要的船只不同，如表. .為使配備船只數(shù)最少，應(yīng)做到周轉(zhuǎn)的空船數(shù)為最少為使配備船只數(shù)最少，應(yīng)做到周轉(zhuǎn)的空船數(shù)為最少. . 建立運輸模型，建立運輸模型，C、D、F 為空船的產(chǎn)地為空船的產(chǎn)地，A、B、E 為銷地，單位運價為相應(yīng)各港口之間的船只航程天數(shù)為銷地，單位運價為相應(yīng)各港口之間的船只航程天數(shù). 港港 口口 A B E每天多余船只每天多余船只 C2 35 2 D141317 2 F783 1每天缺少船只每天缺少船只 1 1 3 用用 LINGOLINGO軟件軟件求出空船的最優(yōu)調(diào)求出空船的最優(yōu)調(diào)度方案度方案. . 最少需周轉(zhuǎn)的最少需周轉(zhuǎn)的空船數(shù)為空船數(shù)為 ？條條. .

17、40model:sets:row/1.3/: a; arrange/1.3/:b; link (row, arrange): c,x; endsetsData:a=2,2,1; b=1,1,3; c=2,3,5,14,13,17,7,8,3; EnddataOBJmin=sum(link(i,j):c(i,j)*x(i,j);for(row(i):sum(arrange(j):x(i,j)=a(i);); for(arrange(j):sum(row(i):x(i,j)=b(j);); for(link(i,j):x(i,j)=0;); END附：例附：例2的的LINGO程序程序運行得結(jié)果：運

18、行得結(jié)果：40; 1, 1, 1, 1,xxxxx（1 1）載貨航程需要的周轉(zhuǎn)船只數(shù)）載貨航程需要的周轉(zhuǎn)船只數(shù)9191條條航航線線起點起點城市城市終點終點城市城市每天航班每天航班數(shù)數(shù)1ED32BC23AF14DB1表表1 1 到到從從ABCDEFA0121477B1031388C23015557851703F7852030表表2 2航線航線裝貨天數(shù)裝貨天數(shù)航程天數(shù)航程天數(shù)卸貨天數(shù)卸貨天數(shù)小計小計航班數(shù)航班數(shù)需周轉(zhuǎn)船只數(shù)需周轉(zhuǎn)船只數(shù)11171193572131521031719194113115115（2 2）空船調(diào)運需要的周轉(zhuǎn)船只數(shù)）空船調(diào)運

19、需要的周轉(zhuǎn)船只數(shù)4040條條航航線線起點起點城市城市終點城終點城市市每天航每天航班數(shù)班數(shù)1E（19）D32B（5） C23A（9） F14D（15） B1表表1 1 到到從從ABCDEFA0121477B1031388C23015557851703F7852030表表2 2 港港 口口 A B E每天多余船只每天多余船只 C 12 3 15 2 D14 113 117 2 F78 13 1每天缺少船只每天缺少船只 1 1 3練習(xí)：練習(xí)：( (設(shè)備的生產(chǎn)計劃問題設(shè)備的生產(chǎn)計劃問題) ) 設(shè)某制造企業(yè)根據(jù)合同要求設(shè)某制造企業(yè)根據(jù)合同要求, ,從當(dāng)年起連續(xù)三年在年末各從當(dāng)年起連續(xù)三年在年末各提供三套型號規(guī)格