圖論(組合優(yōu)化)實驗

1、工程數(shù)學(xué) 4.圖論(組合優(yōu)化)實驗 Gxxxxxxxxxxxxxxx xxxxxx工程數(shù)學(xué)Gxxxxxxxxx xxxxxxE-mail: xxxxxxxxxxxxxxx Tel: xxxxxxxxxx4 數(shù)學(xué)建?；A(chǔ)：1.2.3.4.4.1. 實驗?zāi)康呐c要求l 學(xué)會用圖論（組合優(yōu)化）的方法或思想建模l 學(xué)會LINGO軟件求解組合優(yōu)化問題l 建立相應(yīng)的數(shù)學(xué)模型，并對計算結(jié)果進(jìn)行分析討論4.2. 基本實驗4.2.1. 設(shè)備更新問題某公司需要對一臺已經(jīng)使用了2年的機(jī)器確定今后4年（n=4）的最優(yōu)更新策略。公司要求，用了6年的機(jī)器必須更新，購買一臺新機(jī)器的價格是100萬元，表4.1給出了該問題的數(shù)據(jù)

2、，請給出設(shè)備的更新策略。解：用圖論知識來理解此題。設(shè)用A,B表示決策年度，用數(shù)字表示機(jī)齡，因此，第1年決策的節(jié)點就是A2，第2年只有兩種可能，就是B3（第1年不更新）或B1(第1年更新)，以此類推。則得出Lingo的程序：sets: nodes/A2, B3, B1, C4, C2, C1, D5, D3, D2, D1,E6, E4, E3, E2, E1, F/; arcs(nodes, nodes)/ A2,B3 A2,B1 B3,C4 B3,C1 B1,C2 B1,C1 C4,D5 C4,D1 C2,D3 C2,D1 C1,D2 C1,D1 D5,E1 D5,E6 D3,E4 D3,E

3、1 D2,E3 D2,E1 D1,E2 D1,E1 E6,F E4,F E3,F E2, F E1,F /: c, x;endsetsdata: c = 17.3 -20.2 15.7 -30.2 18.4 -0.2 13.8 -50.2 17.3 20.2 18.4 -0.2 12.2 -70.2 15.7 -30.2 17.3 20.2 18.4 -0.2 5 30 50 60 80; enddatan = size(nodes);max = sum(arcs: c * x);sum(arcs(i,j)| i #eq# 1 : x(i,j) = 1;for(nodes(i)| i #ne#

4、 1 #and# i #ne# n: sum(arcs(i,j): x(i,j) - sum(arcs(j,i): x(j,i)=0);sum(arcs(j,i)| i #eq# n : x(j,i) = 1;for(arcs: bin(x);則得出程序運行結(jié)果：(取非零的x結(jié)果)分析結(jié)果：A2-B3-C4-D5-E1-F，得知設(shè)備應(yīng)該是使用5年后再更新設(shè)備，為最優(yōu)更新策略。4.2.2. 運輸問題有甲、乙和丙三個城市，每年分別需要煤炭320萬噸、250萬噸和350萬噸，由A, B兩個煤礦負(fù)責(zé)供應(yīng)。已知煤礦年產(chǎn)量A為400萬噸，B為450萬噸，從兩煤礦至各城市煤炭運價如表4.2所示。由于需求大于

5、供應(yīng)，經(jīng)協(xié)商平衡，甲城市在必要時可少供應(yīng)0-30萬噸，乙城市需求量須全部滿足，丙城市需求量不少于270萬噸。試求將甲、乙兩礦煤炭全部分配出去，滿足上述條件又使總運費最低的調(diào)運方案。解：sets: From / A, B/: Capacity; To / C1, C2, C3/: Demand; Routes( From, To): D, x;endsets! The objective;OBJ min = sum(Routes: D * x);! The supply constraints;for (From(i): SUP sum (To(j): x(i,j) = Demand(j);!

6、Here are the parameters;data: Capacity = 400, 450 ; Demand = 320, 250, 380 ; D = 15, 18, 22, 21, 25, 16;Enddata程序運行結(jié)果如下：（1）甲甲乙丙丙銷量A1515192222400B2121251616450CM0MM070運量2903025027080（2）甲甲乙丙丙銷量VjA1515182222400-6B21212516164500CM0MM070-16產(chǎn)量2903025027080Ui2121241616（3）甲甲乙丙丙銷量A1515192222400B2121251616450

7、CM0MM070運量2903025027080（4）甲甲乙丙丙銷量VjA1515182222400-6B21212516164500CM30MM070-16產(chǎn)量2903025027080Ui2116241616結(jié)論：調(diào)整后最優(yōu)方案的最低費用：150*15+250*18+140*21+270*16+40*16+30*0+40*0=14650萬元4.2.3. 生產(chǎn)計劃與庫存管理(1)某公司生產(chǎn)一種除臭劑，它在1至4季度的生產(chǎn)成本、生產(chǎn)量及訂貨量表4.3所示。如果除臭劑在生產(chǎn)當(dāng)季沒有交貨，保管在倉庫里除臭劑每盒每季度還需1元錢的儲存費用。如果某個季度的貨物供應(yīng)量不足，則允許延期交貨，延期交貨的罰金是

8、每盒每季度3元。請公司希望制定一個成本最低(包括儲存費用和罰金)的除臭劑的生產(chǎn)計劃，問各季度應(yīng)生產(chǎn)多少?(2)如果產(chǎn)品不允許延期交貨，則公司考慮工人加班，已知加班生產(chǎn)出產(chǎn)品的成本要比原成本高出20%，且每季度加班最多生產(chǎn)2萬盒。問：在這種情況下，將如何安排生產(chǎn)，使總成本最少?解：(1) 設(shè)第一季度、第二季度、第三季度、第四季度生產(chǎn)量分別為a、b、c、d，a1為第一季度后剩余量，b1為第二季度后剩余量，c1為第三季度后剩余量，d1為第四季度后的剩余量。每季度的生產(chǎn)的除臭劑應(yīng)該小于等于最大產(chǎn)量，大于等于訂貨量，第一個季度以為的季度中實際貨物量應(yīng)該等于上月的剩余量加該月的產(chǎn)量，以此類推，可以得出；L

9、INGO的程序：model:min=5*a+5*b+6*c+6*d+ya1+b1+c1+d1;a=10;a=14;b=20;c=8;d=13;d1=d+c1-8;end程序運行結(jié)果如下：第一個季度應(yīng)生產(chǎn)14萬盒，第二季度應(yīng)該生產(chǎn)15萬盒，第三季度應(yīng)該生產(chǎn)15萬盒，第四季度應(yīng)該生產(chǎn)8萬盒除臭劑。最低費用為288萬元。（2）第1季度加班生產(chǎn)的產(chǎn)品為y1盒，第2季度加班生產(chǎn)的產(chǎn)品為y2盒，第3季度加班生產(chǎn)的產(chǎn)品為y3盒，第4季度加班生產(chǎn)的產(chǎn)品為y3盒，LINGO的程序：Model:min=8*a+9*y1+7*b+8*y2+7*c+8.2*y3+6*d+7.2*y4-78;a+y1+b+y2+c+y

10、3+d+y4=52;a=10;b=24;c=44;d=13;End Lingo程序運行結(jié)果：Lingo運行結(jié)果可得：安排生產(chǎn)：第一季度正常生產(chǎn)13萬盒，不加班生產(chǎn)；第二季度正常生產(chǎn)15萬，加班生產(chǎn)1萬盒；第三季度正常生產(chǎn)15萬，不加班生產(chǎn)；第四季度生產(chǎn)8萬盒，不加班生產(chǎn)?？偝杀咀钌贋?92萬元。4.2.4. 指派問題某公司需要把4項工作派給4名工人，每名工人完成每項工作的費用如表4.4所示，其中甲不能完成工作C，丙不能完成工作D。（1）確定每名工人完成工作的最優(yōu)方案；（2）假設(shè)有另外一名工人（戊）能完成這4項工作，完成每項工作相應(yīng)費用分別為60、45、30和80元。是否用這名新工人（戊）替換原

11、來的某位工人？（3）假設(shè)公司有了第5項工作（E），4名工人（甲、乙、丙、?。┩瓿晒ぷ鱁的費用分別為20、10、20和80元。這項新工作E比原有的四項工作（A，B，C，D）的某一項優(yōu)先嗎？解：根據(jù)題意分析方案。利用lingo的程序(不可能任務(wù)設(shè)成999，求min)sets: Flight/1.4/; Assign(Flight, Flight): c, x;endsetsdata: c = 50 50 999 20 70 40 20 30 90 30 50 999 70 20 60 70 ;enddatamin = sum(Assign: c*x);for(Flight(i): sum(Flig

12、ht(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;);Lingo程序運行得： 最優(yōu)方案：甲完成工作D， 乙完成C，丙完成B，丁完成A。總費用為140元（2） 根據(jù)題意增加一個工人（戊），設(shè)替換丙方案（且丁完成B任務(wù)）。Lingo的程序：sets: Flight/1.5/; Assign(Flight, Flight): c, x;endsetsdata: c = 50 50 999 20 999 70 40 20 30 999 90 30 50 999 999 70 20 60 70 999 60 45 30 80 999;enddatamin = su

13、m(Assign: c*x);for(Flight(i): sum(Flight(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;); Lingo程序運行得： 結(jié)論：1119-999=120, 費用減少120元。甲完成D，乙完成C，丙完成5（去掉），丁完成B，戊完成A。（3）Lingo的程序：sets: Flight/1.5/; Assign(Flight, Flight): c, x;endsetsdata: c = 50 50 999 20 20 70 40 20 30 10 90 30 50 999 20 70 20 60 70 80 999 999

14、999 999 999 ;enddatamin = sum(Assign: c*x);for(Flight(i): sum(Flight(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;);Lingo程序運行得： 結(jié)論：1079-999=80，甲完成D，乙完成C，丙完成E，丁完成B， 即E比A優(yōu)先4.2.5. 旅行商問題張三住在A市，他在A, B, C,D,E和F市都有保險代理業(yè)務(wù).由于業(yè)務(wù)關(guān)系，他每個月都需要訪問這些城市作一次。表4.5給出了每個城市之間的距離，試分析他按照什么的順序訪問這些城市使得總旅行的距離最短?（1）用啟發(fā)式算法求解； （2）用LIN

15、GO軟件求解。解：（1）用啟發(fā)式算法求解由題意得知，以下幾條最為便捷的路徑：A- B- C- D- E- F- A路程s1=588+129+483+1288+440+825=3753公里；A- B- C- D- F- E- A路程s2=588+129+483+1100+440+1096=3836公里；A- B- C- E- F- D- A路程s3=588+129+1638+440+1100+334=4229公里；A- B- C- E- D- F- A路程s4=588+129+1638+1288+1100+825=5568公里；A- B- D- C- E- F- A路程s5=588+448+48

16、3+1638+440+825=4422公里；A- B- D- C- F- E- A路程s6=588+448+483+1346+440+1096=4401公里；A- B- D- E- C- F- A路程s7=588+448+1288+1638+1364+825=6151公里；A- B- D- E- F- C- A路程s8=588+448+1288+440+1364+542=4670公里；A- B- D- F- C- E- A路程s9=588+448+1100+1346+1638+1096=6234公里；A- B- D- F- E- C- A路程s10=588+448+1100+440+1638+

17、542=4756公里；A- C- B- D- E- F- A路程s11=542+129+448+1288+440+825=3672公里；A- C- B- D- F- E- A路程s12=542+129+448+1100+440+1096=3755公里；A- C- B- E- D- F- A路程s13=542+129+1675+1288+1100+825=5559公里；A- C- B- E- F- D- A路程s14=542+129+1675+440+1100+825=4711公里；A- C- B- F- D- E- A路程s15=542+129+1410+1100+1288+1096=5565

18、公里；A- C- B- F- E- D- A路程s16=542+129+1410+440+1288+334=4143公里；A- C- D- B- E- F- A路程s17=542+483+448+1675+440+825=4413公里；A- C- D- B- F- E- A路程s18=542+483+448+1410+440+1096=4419公里；A- C- D- E- B- F- A路程s19=542+483+1288+1675+1410+825=6223公里；（2）用LINGO軟件求解LINGO的程序：sets: city/A,B,C,D,E,F/: u; link(city, city

19、): w, x;endsetsdata: w =0,588,542,334,1096,825 588,0,129,448,1675,1410 542,129,0,483,1638,1346 334,448,483,0,1288,1100 1096,1675,1638,1288,0,440 825,1410,1346,1100,440,0; enddatan=size(city);min = sum(link: w * x);for(city(k): sum(city(i)| i #ne# k: x(i,k)=1; sum(city(j)| j #ne# k: x(k,j)=1;);for(li

20、nk(i,j)| i #gt# 1 #and# j #gt# 1 #and# i #ne# j: u(i)-u(j)+n*x(i,j)=n-1;);for(link: bin(x);程序運行結(jié)果如下：從答案可知：最短距離為ACBDEFA最短距離3672。4.2.6. 最優(yōu)連線問題求5題中6個城市（A, B, C,D,E，F(xiàn)）的最優(yōu)連線，城市之間的距離如表4.5所示。解：sets: city/A B C D E F/: u; link(city, city): w, x;endsetsdata: !to: A B C D E F; w = 0 588 542 334 1096 825 !from

21、 A; 588 0 129 448 1675 1410 !from B; 542 129 0 483 1638 1346 !from C; 334 448 483 0 1288 1100 !from D; 1096 1675 1638 1288 0 440 !from E; 825 1410 1346 1100 440 0;!from F;enddatan=size(city);min = sum(link: w * x);for(city(k): sum(city(i)| i #ne# k: x(i,k)=1; sum(city(j)| j #ne# k: x(k,j)=1; );for(l

22、ink(i,j)|i #gt# 1 #and# j #gt# 1 #and# i #ne# j: u(i)-u(j)+n*x(i,j)=n-1;);for(link: bin(x);程序運行結(jié)果如下：最優(yōu)連線ACBDEFA4.2.7. 最大流問題 三個煉油廠通過管道網(wǎng)絡(luò)為兩個分散的終端運送汽油。這個管道網(wǎng)絡(luò)中有三個泵站，如圖4.1所示。汽油的流向如圖中箭頭所示，圖中標(biāo)出了每一段管道的運送容量，單位是百萬桶/天。求解下面的問題: (1)要滿足這個網(wǎng)絡(luò)的最大流量，每一個煉油廠每天的產(chǎn)量應(yīng)該是多少； (2)要滿足這個網(wǎng)絡(luò)的最大流量，每一個終端每天的需求量應(yīng)該是多少； (3)要滿足這個網(wǎng)絡(luò)的最大流量，

23、每個泵站每天的容量應(yīng)該是多少；(4)如果進(jìn)一步假定在圖4.1所示的網(wǎng)絡(luò)中泵站6每天的最大容量限制為50百萬桶，求出相應(yīng)的網(wǎng)絡(luò)的最大容量。解：由題已知條件令xij為從i到j(luò)的流量LINGO的程序：Model:max=x47+x67+x68+x58;x14=20;x24=10;x26=50;x25=20;x35=15;x47=10;x46=10;x45=20;x56=30;x58=30;x67=50;x68=x45+x46+x47;x35+x25x+x45=x58+x56;x26+x46+x56=x67+x68;end程序運行結(jié)果如下：（1）x14=20，煉油1產(chǎn)量為20百萬桶/天；x24=10，

24、x25=20， x26=50，煉油廠2的產(chǎn)量為80百萬桶/天；X35=15，煉油廠3的產(chǎn)量為1百萬桶/天。（2）X47=10，X67=50，終端7需求量為60百萬桶/天；X58=30，X68=20，終端8需求量為50百萬桶/天。（3）X47=20，X24=10時，泵站4容量為30百萬桶/天；X25=20，X35=15， X45=5，泵站5容量為40百萬桶/天；X26=50， X46=10， X56=10，泵站6容量為70百萬桶/天。（4）LINGO的程序：Model:max=x47+x67+x68+x58;x14=20;x24=10;x26=50;x25=20;x35=15;x47=10;x4

25、6=10;x45=20;x56=30;x58=30;x67=50;x68=x45+x46x+x47;x35+x25x45=x58+x56;x26+x46x+x56=x67+x68;x26+x46+x56=50;end程序運行結(jié)果如下：結(jié)論：X47=20，X24=10，泵站4的容量為30百萬桶/天；X25=20， X35=15， X45=0，泵站5的容量為35百萬桶/天；X26=40，X46=10，X56=0，泵站6的容量為50百萬桶/天。4.3. 加分實驗 所得稅管理部門計劃對某個地區(qū)中的所得稅交納點網(wǎng)絡(luò)進(jìn)行重新設(shè)計。圖4.2是對此地區(qū)內(nèi)的城市和主要道路的示意圖，城市旁邊的黑體數(shù)字表示城市的居民數(shù)目，單位為千人。在連接城市之間的弧上標(biāo)出了它們之間的距離，單位為千米(斜體字)。為