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

1、工程數學Gxxxxxxxxx xxxxxxE-mail: xxxxxxxxxxxxxxx Tel: xxxxxxxxxx4 數學建?；A：1.1. 實驗目的與要求l 學會用圖論（組合優(yōu)化）的方法或思想建模l 學會LINGO軟件求解組合優(yōu)化問題l 建立相應的數學模型，并對計算結果進行分析討論1.2. 基本實驗1.2.1. 設備更新問題某公司需要對一臺已經使用了2年的機器確定今后4年（n=4）的最優(yōu)更新策略。公司要求，用了6年的機器必須更新，購買一臺新機器的價格是100萬元，表4.1給出了該問題的數據，請給出設備的更新策略。解：用圖論知識來理解此題。設用A,B表示決策年度，用數字表示機齡，因此，第

2、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,E1 D2,E3 D2,E1 D1,E2 D1,E1 E6,F E4,F E3,F E2, F E1

3、,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# 1 #and# i #ne# n: sum(arcs(i,j): x(i,j) - sum(ar

4、cs(j,i): x(j,i)=0);sum(arcs(j,i)| i #eq# n : x(j,i) = 1;for(arcs: bin(x);則得出程序運行結果：(取非零的x結果)分析結果：A2-B3-C4-D5-E1-F，得知設備應該是使用5年后再更新設備，為最優(yōu)更新策略。1.2.2. 運輸問題有甲、乙和丙三個城市，每年分別需要煤炭320萬噸、250萬噸和350萬噸，由A, B兩個煤礦負責供應。已知煤礦年產量A為400萬噸，B為450萬噸，從兩煤礦至各城市煤炭運價如表4.2所示。由于需求大于供應，經協(xié)商平衡，甲城市在必要時可少供應0-30萬噸，乙城市需求量須全部滿足，丙城市需求量不少于2

5、70萬噸。試求將甲、乙兩礦煤炭全部分配出去，滿足上述條件又使總運費最低的調運方案。解：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);! Here are the parameters;data: Capacity = 400, 450

6、 ; Demand = 320, 250, 380 ; D = 15, 18, 22, 21, 25, 16;Enddata程序運行結果如下：（1）甲甲乙丙丙銷量A1515192222400B2121251616450CM0MM070運量2903025027080（2）甲甲乙丙丙銷量A1515182222400-6B21212516164500CM0MM070-16產量29030250270802121241616（3）甲甲乙丙丙銷量A1515192222400B2121251616450CM0MM070運量2903025027080（4）甲甲乙丙丙銷量A1515182222400-6B212

7、12516164500CM30MM070-16產量29030250270802116241616結論：調整后最優(yōu)方案的最低費用：150*15+250*18+140*21+270*16+40*16+30*0+40*0=14650萬元1.2.3. 生產計劃與庫存管理(1)某公司生產一種除臭劑，它在1至4季度的生產成本、生產量及訂貨量表4.3所示。如果除臭劑在生產當季沒有交貨，保管在倉庫里除臭劑每盒每季度還需1元錢的儲存費用。如果某個季度的貨物供應量不足，則允許延期交貨，延期交貨的罰金是每盒每季度3元。請公司希望制定一個成本最低(包括儲存費用和罰金)的除臭劑的生產計劃，問各季度應生產多少?(2)如果

8、產品不允許延期交貨，則公司考慮工人加班，已知加班生產出產品的成本要比原成本高出20%，且每季度加班最多生產2萬盒。問：在這種情況下，將如何安排生產，使總成本最少?解：(1) 設第一季度、第二季度、第三季度、第四季度生產量分別為a、b、c、d，a1為第一季度后剩余量，b1為第二季度后剩余量，c1為第三季度后剩余量，d1為第四季度后的剩余量。每季度的生產的除臭劑應該小于等于最大產量，大于等于訂貨量，第一個季度以為的季度中實際貨物量應該等于上月的剩余量加該月的產量，以此類推，可以得出；LINGO的程序：model:min=5*a+5*b+6*c+6*d+ya1+b1+c1+d1;a=10;a=14;

9、b=20;c=8;d=13;d1=d+c1-8;end程序運行結果如下：第一個季度應生產14萬盒，第二季度應該生產15萬盒，第三季度應該生產15萬盒，第四季度應該生產8萬盒除臭劑。最低費用為288萬元。（2）第1季度加班生產的產品為y1盒，第2季度加班生產的產品為y2盒，第3季度加班生產的產品為y3盒，第4季度加班生產的產品為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+y3+d+y4=52;a=10;b=24;c=44;d=13;End Lingo程序運行結果：Lingo運行結果可得

10、：安排生產：第一季度正常生產13萬盒，不加班生產；第二季度正常生產15萬，加班生產1萬盒；第三季度正常生產15萬，不加班生產；第四季度生產8萬盒，不加班生產。總成本最少為292萬元。1.2.4. 指派問題某公司需要把4項工作派給4名工人，每名工人完成每項工作的費用如表4.4所示，其中甲不能完成工作C，丙不能完成工作D。（1）確定每名工人完成工作的最優(yōu)方案；（2）假設有另外一名工人（戊）能完成這4項工作，完成每項工作相應費用分別為60、45、30和80元。是否用這名新工人（戊）替換原來的某位工人？（3）假設公司有了第5項工作（E），4名工人（甲、乙、丙、丁）完成工作E的費用分別為20、10、20

11、和80元。這項新工作E比原有的四項工作（A，B，C，D）的某一項優(yōu)先嗎？解：根據題意分析方案。利用lingo的程序(不可能任務設成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(Flight(j): x(i,j) = 1; sum(Flight(j): x(j,i) = 1;);Lingo程序運行得

12、： 最優(yōu)方案：甲完成工作D， 乙完成C，丙完成B，丁完成A。總費用為140元（2） 根據題意增加一個工人（戊），設替換丙方案（且丁完成B任務）。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 = sum(Assign: c*x);for(Flight(i): sum(Flight(j): x(i,j) = 1;

13、sum(Flight(j): x(j,i) = 1;); Lingo程序運行得： 結論：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 999 999 999 ;enddatamin = sum(Assign: c*x);for(Flight(i):

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

15、路程=588+129+483+1288+440+825=3753公里；A- B- C- D- F- E- A路程=588+129+483+1100+440+1096=3836公里；A- B- C- E- F- D- A路程=588+129+1638+440+1100+334=4229公里；A- B- C- E- D- F- A路程=588+129+1638+1288+1100+825=5568公里；A- B- D- C- E- F- A路程=588+448+483+1638+440+825=4422公里；A- B- D- C- F- E- A路程=588+448+483+1346+440+10

16、96=4401公里；A- B- D- E- C- F- A路程=588+448+1288+1638+1364+825=6151公里；A- B- D- E- F- C- A路程=588+448+1288+440+1364+542=4670公里；A- B- D- F- C- E- A路程=588+448+1100+1346+1638+1096=6234公里；A- B- D- F- E- C- A路程=588+448+1100+440+1638+542=4756公里；A- C- B- D- E- F- A路程=542+129+448+1288+440+825=3672公里；A- C- B- D- F

17、- E- A路程=542+129+448+1100+440+1096=3755公里；A- C- B- E- D- F- A路程=542+129+1675+1288+1100+825=5559公里；A- C- B- E- F- D- A路程=542+129+1675+440+1100+825=4711公里；A- C- B- F- D- E- A路程=542+129+1410+1100+1288+1096=5565公里；A- C- B- F- E- D- A路程=542+129+1410+440+1288+334=4143公里；A- C- D- B- E- F- A路程=542+483+448+1

18、675+440+825=4413公里；A- C- D- B- F- E- A路程=542+483+448+1410+440+1096=4419公里；A- C- D- E- B- F- A路程=542+483+1288+1675+1410+825=6223公里；（2）用LINGO軟件求解LINGO的程序：sets: city/A,B,C,D,E,F/: u; link(city, city): w, x;endsetsdata: w =0,588,542,334,1096,825 588,0,129,448,1675,1410 542,129,0,483,1638,1346 334,448,48

19、3,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(link(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);程序運行結果如下：從答案可知

20、：最短距離為ACBDEFA最短距離3672。1.2.6. 最優(yōu)連線問題求5題中6個城市（A, B, C,D,E，F）的最優(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 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; 10

21、96 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(link(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);程序運行結果如下：最優(yōu)連線A

22、CBDEFA1.2.7. 最大流問題 三個煉油廠通過管道網絡為兩個分散的終端運送汽油。這個管道網絡中有三個泵站，如圖4.1所示。汽油的流向如圖中箭頭所示，圖中標出了每一段管道的運送容量，單位是百萬桶/天。求解下面的問題: (1)要滿足這個網絡的最大流量，每一個煉油廠每天的產量應該是多少； (2)要滿足這個網絡的最大流量，每一個終端每天的需求量應該是多少； (3)要滿足這個網絡的最大流量，每個泵站每天的容量應該是多少；(4)如果進一步假定在圖4.1所示的網絡中泵站6每天的最大容量限制為50百萬桶，求出相應的網絡的最大容量。解：由題已知條件令為從i到j的流量LINGO的程序：Model:max=x

23、47+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程序運行結果如下：（1）x14=20，煉油1產量為20百萬桶/天；x24=10，x25=20， x26=50，煉油廠2的產量為80百萬桶/天；X35=15，煉油廠3的產量為1百萬桶/天。（2）X47=10，X67=50，終端7需求量為60百萬桶/天；X58=30，X68=20，終端8需求量為50

24、百萬桶/天。（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;x46=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程序運行結果如下：結論：X47=20，X24=10，泵站4的容量為30百萬桶/天；X25=20， X35=15， X45=0，泵站5的容量為35百萬桶/天；X26=40，X46=10，X56=0，泵站6的容量為50百萬桶/天。1.3. 加分實驗 所得稅管理部門計劃對某個地區(qū)中的所得稅交納點網絡進行重新設計。圖4.2是對此地區(qū)內的城市和主要道路的示意圖，城市旁邊的黑體數字表示城市的居民數目，單位為千人。在連接城市之間的弧上標出了它們之間的距離，單位為千米(斜體字)。為覆蓋各個城市，所得稅管