北工大數(shù)學(xué)建模作業(yè)4--已通過考核(共35頁)

1、 數(shù)學(xué)模型圖論(t ln)（組合優(yōu)化）實驗 基本(jbn)實驗1.設(shè)備更新(gngxn)問題某公司需要對一臺已經(jīng)使用了2年的機器確定今后4年(n=4)的最優(yōu)更新策略.公司要求，用了6年的機器必須更新，購買一臺新機器的價格是100萬元，表4.1給出了該問題的數(shù)據(jù)，請給出設(shè)備的更新策略。解：根據(jù)題意可以設(shè)a, b, c, d為判斷年度，用數(shù)字表示機器已經(jīng)使用的時間，則有第1年：機器使用的情況可以表示為a2；第2年：若第1年機器不更新則情況表示成b3，若第一年機器更新則第二年應(yīng)表示成b1；使用Lingo軟件進行計算(j sun)并取最優(yōu)解，編程如下：model:sets: Nodes/a2, b3,

2、 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,f /: c, x;endsetsdata: c = 17.3 -20.2 15.7 -30.2 18.4 -0.2 13.8 -

3、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(arcs(j,i): x(j,i)=0);sum (arcs (j,i)| i #eq# n : x(j,i) = 1;f

4、or (arcs: bin(x);End得到結(jié)果(ji gu)如下：Global optimal solution found. Objective value: 139.0000 Objective bound: 139.0000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost N 16.00000 0.000000 C (a2, b3) 17.30000 0.000000 C (a2, b1) -20.20000 0.00000

5、0 C (b3, c4) 15.70000 0.000000 C (b3, c1) -30.20000 0.000000 C (b1, c2) 18.40000 0.000000 C (b1, c1) -0.2000000 0.000000 C (c4, d5) 13.80000 0.000000 C (c4, d1) -50.20000 0.000000 C (c2, d3) 17.30000 0.000000 C (c2, d1) -20.20000 0.000000 C (c1, d2) 18.40000 0.000000 C (c1, d1) -0.2000000 0.000000 C

6、 (d5, e1) 12.20000 0.000000 C (d5, e6) -70.20000 0.000000 C (d3, e4) 15.70000 0.000000 C (d3, e1) -30.20000 0.000000 C (d2, e3) 17.30000 0.000000 C (d2, e1) -20.20000 0.000000 C (d1, e2) 18.40000 0.000000 C (d1, e1) -0.2000000 0.000000 C (e6, f) 5.000000 0.000000 C (e4, f) 30.00000 0.000000 C (e3, f

7、) 50.00000 0.000000 C (e2, f) 60.00000 0.000000 C (e1, f) 80.00000 0.000000 X (a2, b3) 1.000000 -17.30000 X (a2, b1) 0.000000 20.20000 X (b3, c4) 1.000000 -15.70000 X (b3, c1) 0.000000 30.20000 X (b1, c2) 0.000000 -18.40000 X (B1, c1) 0.000000 0.2000000 X (c4, d5) 1.000000 -13.80000 X (c4, d1) 0.000

8、000 50.20000 X (c2, d3) 0.000000 -17.30000 X (c2, d1) 0.000000 20.20000 X (c1, d2) 0.000000 -18.40000 X (c1, d1) 0.000000 0.2000000 X (d5, e1) 1.000000 -12.20000 X (d5, e6) 0.000000 70.20000 X (d3, e4) 0.000000 -15.70000 X (d3, e1) 0.000000 30.20000 X (d2, e3) 0.000000 -17.30000 X (d2, e1) 0.000000

9、20.20000 X (d1, e2) 0.000000 -18.40000 X (d1, e1) 0.000000 0.2000000 X (e6, f) 0.000000 -5.000000 X (e4, f) 0.000000 -30.00000 X (e3, f) 0.000000 -50.00000 X (e2, f) 0.000000 -60.00000 X (e1, f) 1.000000 -80.00000Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 139.0000 1.000000 3 0.000000 0.00

10、0000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.000000 18 0.00

11、0000 0.000000分析結(jié)果容易(rngy)得出最佳的路徑為a2-b3-c4-d5-e1-f，因此得出結(jié)論，設(shè)備(shbi)的最優(yōu)更新策略應(yīng)該是使用5年。2. 運輸(ynsh)問題有甲、乙和丙三個城市，每年分別需要煤炭320萬噸、250萬噸和350萬噸，由A, B兩個煤礦負責(zé)供應(yīng).已知煤礦年產(chǎn)量A為400萬噸，B為450萬噸，從兩煤礦至各城市煤炭運價如表4.2所示.由于需求大于供應(yīng)，經(jīng)協(xié)商平衡，甲城市在必要時可少供應(yīng)0-30萬噸，乙城市需求量須全部滿足，丙城市需求量不少于270萬噸。試求將甲、乙兩礦煤炭全部分配出去，滿足上述條件又使總運費最低的調(diào)運方案。解：根據(jù)題意認為該問題是一個運輸線

12、性規(guī)劃的典型(dinxng)問題。設(shè)甲、乙、丙三個城市的煤炭獲取量（Customer）1, 2, 3；A、B兩個煤礦的煤炭貯存（Warehouse）表達為A, B；煤礦與各城市之間的煤炭運價為P，用x表示決策點。使用Lingo軟件進行計算并取最優(yōu)解，編程如下：Model:!2 Warehouse, 3 Customer Transportation Problem;sets: Warehouse / A, B/: Supply; Customer / 1, 2, 3/: Gain; Routes (Warehouse, Customer): c, x;Endsets! The objectiv

13、e;OBJ min = sum (Routes: c * x);! The supply constraints;for (Warehouse (i): SUPsum (Customer (j): x (i,j) 290;sum (warehouse (i): x (i, 1) 270;sum (warehouse (i): x (i, 3) 350;! Here are the parameters;data: Supply = 400, 450; Gain = 320, 250, 380; c = 15, 18, 22,21, 25, 16;Enddataend 得到如下(rxi)結(jié)果：G

14、lobal optimal solution found. Objective value: 14650.00 Infeasibilities: 0.000000 Total solver iterations: 4Variable Value Reduced CostSUPPLY (A) 400.0000 0.000000SUPPLY (B) 450.0000 0.000000GAIN (1) 250.0000 0.000000GAIN (2) 290.0000 0.000000GAIN (3) 310.0000 0.000000C (A, 1) 15.00000 0.000000C (A,

15、 2) 18.00000 0.000000C (A, 3) 22.00000 0.000000C (B, 1) 21.00000 0.000000C (B, 2) 25.00000 0.000000C (B, 3) 16.00000 0.000000X (A, 1) 150.0000 0.000000X (A, 2) 250.0000 0.000000X (A, 3) 0.000000 12.00000X (B, 1) 140.0000 0.000000X (B, 2) 0.000000 1.000000X (B, 3) 310.0000 0.000000因此得到結(jié)論：由A礦向甲乙丙三座城市(

16、chngsh)的送礦量（萬噸）為150、250、0；由B礦向甲乙丙三座城市的送礦量（萬噸）為140、0、310，此時總運輸費最小，為14650萬元。3、生產(chǎn)計劃與庫存(kcn)管理(1)某公司生產(chǎn)一種除臭劑，它在1至4季度的生產(chǎn)成本、生產(chǎn)量及訂貨量表4.3所示.如果除臭劑在生產(chǎn)當(dāng)季沒有交貨，保管在倉庫里除臭劑每盒每季度還需1元錢的儲存費用。如果某個季度的貨物供應(yīng)量不足，則允許延期交貨，延期交貨的罰金是每盒每季度3元。請公司希望制定一個成本最低(包括儲存費用和罰金)的除臭劑的生產(chǎn)計劃，問各季度應(yīng)生產(chǎn)多少?(2)如果產(chǎn)品不允許(ynx)延期交貨，則公司考慮工人加班，已知加班生產(chǎn)出產(chǎn)品的成本要比原成

17、本高出20%，且每季度加班最多生產(chǎn)2萬盒.問:在這種情況下，將如何安排生產(chǎn)，使總成本最少?解：根據(jù)(gnj)題意，將此問題轉(zhuǎn)化為運輸(ynsh)問題，將每季度的生產(chǎn)量看作是供方，將每季度的訂貨量看作是需求方，將不屬于本季度供貨的量視為其他季度運輸過來的，那么具體思路作圖如下：紅色字樣為第一季度運輸每件費用，5+166+36+325+1255+35+135+125+15季度2訂貨量季度3訂貨量季度4訂貨量季度1生產(chǎn)量季度2生產(chǎn)量季度3生產(chǎn)量季度4生產(chǎn)量季度1訂貨量6+336+326+3166+1紅色字樣(zyng)為季度1生產(chǎn)向4個季度的運送量；綠色(l s)字樣為季度2生產(chǎn)向4個季度的運送量；

18、藍色字樣為季度2生產(chǎn)(shngchn)向4個季度的運送量；黑色字樣為季度2生產(chǎn)向4個季度的運送量。列出配送供需表格：季度1需求季度2需求季度3需求季度4需求季度1配送單價（萬元/萬盒）5666季度2配送單價（萬元/萬盒）8567季度3配送單價（萬元/萬盒）12967季度4配送單價（萬元/萬盒）151296設(shè)Cij為從季度(jd)生產(chǎn)Ai到季度(jd)需求Bj的配送(pi sn)單價，Xij為從季度生產(chǎn)Ai到季度需求Bj的運輸量，因此總的費用為：i=1mj=1ncij xij第i個季度的運出量應(yīng)該小于或等于該季度的生產(chǎn)量：j=1mxijai第j個季度的運入量應(yīng)該等于該季度的需求量：i=1mxij

19、bj根據(jù)此模型寫出Lingo程序并求出最優(yōu)解：Model:!4 Warehouse, 4 Customer Transportation Problem;sets: Warehouse /1.4/: a; Customer /1.4/: b; Routes (Warehouse, Customer): c, x;Endsets! Here are the parameters;data: a= 13, 15, 15, 13; b= 10, 14, 20, 8; c = 5, 6, 7, 8, 8, 5, 6, 7, 12, 9, 6, 7, 15, 12, 9, 6;Enddata! The

20、objective;OBJ min = sum (Routes: c * x);! The supply constraints;for (Warehouse (i): SUP sum (Customer (j): X (i,j)= a(i);! The demand constraints;for (Customer (j): DEM sum (Warehouse (i): X (i,j)= b(j);end 得到如下(rxi)結(jié)果：Global optimal solution found. Objective value: 294.0000 Infeasibilities: 0.0000

21、00 Total solver iterations: 7Variable Value Reduced CostA (1) 13.00000 0.000000A (2) 15.00000 0.000000A (3) 15.00000 0.000000A (4) 13.00000 0.000000B (1) 10.00000 0.000000B (2) 14.00000 0.000000B (3) 20.00000 0.000000B (4) 8.000000 0.000000C (1, 1) 5.000000 0.000000C (1, 2) 6.000000 0.000000C (1, 3)

22、 7.000000 0.000000C (1, 4) 8.000000 0.000000C (2, 1) 8.000000 0.000000C (2, 2) 5.000000 0.000000C (2, 3) 6.000000 0.000000C (2, 4) 7.000000 0.000000C (3, 1) 12.00000 0.000000C (3, 2) 9.000000 0.000000C (3, 3) 6.000000 0.000000C (3, 4) 7.000000 0.000000C (4, 1) 15.00000 0.000000C (4, 2) 12.00000 0.00

23、0000C (4, 3) 9.000000 0.000000C (4, 4) 6.000000 0.000000X (1, 1) 10.00000 0.000000X (1, 2) 3.000000 0.000000X (1, 3) 0.000000 0.000000X (1, 4) 0.000000 4.000000X (2, 1) 0.000000 4.000000X (2, 2) 11.00000 0.000000X (2, 3) 4.000000 0.000000X (2, 4) 0.000000 4.000000X (3, 1) 0.000000 8.000000X (3, 2) 0

24、.000000 4.000000X (3, 3) 15.00000 0.000000X (3, 4) 0.000000 4.000000X (4, 1) 0.000000 8.000000X (4, 2) 0.000000 4.000000X (4, 3) 1.000000 0.000000X (4, 4) 8.000000 0.000000Row Slack or Surplus Dual PriceOBJ 294.0000 -1.000000SUP (1) 0.000000 2.000000SUP (2) 0.000000 3.000000SUP (3) 0.000000 3.000000

25、SUP (4) 4.000000 0.000000DEM (1) 0.000000 -7.000000DEM (2) 0.000000 -8.000000DEM (3) 0.000000 -9.000000DEM (4) 0.000000 -6.000000分析結(jié)果易知，最佳(zu ji)的方案為：第一季度生產(chǎn)14萬盒，給出10萬盒滿足第一季度要求，庫存3萬盒，不拖欠；第二季度生產(chǎn)(shngchn)15萬盒，給出11萬盒，連同第一季度庫存3萬盒加起來為14萬盒滿足第二季度要求，庫存4萬盒，不拖欠(tuqin)；第三季度生產(chǎn)15萬盒，全部給出，連同第二季度庫存4萬盒加起來19萬盒，拖欠1萬盒；第

26、四季度生產(chǎn)9萬盒，還清第三季度拖欠1萬盒，剩下8萬盒滿足第四季度需求。此方案下總成本最小，為294萬元。分析題目，可以將工人加班的費用視為除本季生產(chǎn)外為接下來其他季度供應(yīng)貨物的費用。參考如下配送供需表格：季度1需求季度2需求季度3需求季度4需求季度1配送單價（萬元/萬盒）5666季度2配送單價（萬元/萬盒）-566季度3配送單價（萬元/萬盒）-67.2季度4配送單價（萬元/萬盒）-6對于Lingo程序的改變，只需將每季度生產(chǎn)量擴充(kuchng)為+2萬盒即可，對于表格中午單價的位置，使用極大數(shù)105來表示無窮大，根據(jù)此模型(mxng)寫出Lingo程序并求出最優(yōu)解：Model:!4 Ware

27、house, 4 Customer Transportation Problem;sets: Warehouse /1.4/: a; Customer /1.4/: b; Routes (Warehouse, Customer): c, x;Endsets! Here are the parameters;data: a= 15, 17, 17, 15; b= 10, 14, 20, 8; c = 5, 6, 6, 6, 100000, 5, 6, 6, 1000000, 1000000, 6, 7.2, 1000000, 1000000, 1000000, 6;Enddata! The ob

28、jective;OBJ min = sum (Routes: c * x);! The supply constraints;for (Warehouse (i): SUP sum (Customer (j): X (i,j)= a(i);! The demand constraints;for (Customer (j): DEM sum (Warehouse (i): x (i,j)= b(j);end 得到如下(rxi)結(jié)果： Global optimal solution found. Objective value: 288.0000 Infeasibilities: 0.00000

29、0 Total solver iterations: 8Variable Value Reduced CostA (1) 15.00000 0.000000A (2) 17.00000 0.000000A (3) 17.00000 0.000000A (4) 15.00000 0.000000B (1) 10.00000 0.000000B (2) 14.00000 0.000000B (3) 20.00000 0.000000B (4) 8.000000 0.000000C (1, 1) 5.000000 0.000000C (1, 2) 6.000000 0.000000C (1, 3)

30、6.000000 0.000000C (1, 4) 6.000000 0.000000C (2, 1) 100000.0 0.000000C (2, 2) 5.000000 0.000000C (2, 3) 6.000000 0.000000C (2, 4) 6.000000 0.000000C (3, 1) 1000000 0.000000C (3, 2) 1000000 0.000000C (3, 3) 6.000000 0.000000C (3, 4) 7.200000 0.000000C (4, 1) 1000000 0.000000C (4, 2) 1000000 0.000000C

31、 (4, 3) 1000000 0.000000C (4, 4) 6.000000 0.000000X (1, 1) 10.00000 0.000000X (1, 2) 0.000000 1.000000X (1, 3) 0.000000 0.000000X (1, 4) 5.000000 0.000000X (2, 1) 0.000000 99995.00X (2, 2) 14.00000 0.000000X (2, 3) 3.000000 0.000000X (2, 4) 0.000000 0.000000X (3, 1) 0.000000 999995.0X (3, 2) 0.00000

32、0 999995.0X (3, 3) 17.00000 0.000000X (3, 4) 0.000000 1.200000X (4, 1) 0.000000 999995.0X (4, 2) 0.000000 999995.0X (4, 3) 0.000000 999994.0X (4, 4) 3.000000 0.000000Row Slack or Surplus Dual PriceOBJ 288.0000 -1.000000SUP (1) 0.000000 0.000000SUP (2) 0.000000 0.000000SUP (3) 0.000000 0.000000SUP (4

33、) 12.00000 0.000000DEM( 1) 0.000000 -5.000000DEM( 2) 0.000000 -5.000000DEM( 3) 0.000000 -6.000000DEM( 4) 0.000000 -6.000000分析結(jié)果，得到(d do)最優(yōu)生產(chǎn)方案：第一季度生產(chǎn)(shngchn)15萬盒（2萬盒為加班(ji bn)產(chǎn)出），10萬盒給出，滿足第一季度需求，剩下5萬盒庫存至第四季度；第二季度生產(chǎn)17萬盒（2萬盒為加班產(chǎn)出），14萬盒給出，滿足第二季度需求，剩下3萬盒庫存至第三季度；第三季度生產(chǎn)17萬盒（2萬盒為加班產(chǎn)出），連同第二季度庫存共計20萬盒給出，滿足第

34、三季度需求；第四季度生產(chǎn)3萬，盒連同第一季度庫存5萬盒共計8萬盒給出，滿足第四季度要求。此時可以將成本控制到最少288萬元。4. 指派問題某公司需要把4項工作派給4名工人，每名工人完成每項工作的費用如表4.4所示，其中工人甲不能完成工作C，工人丙不能完成工作D。確定每名工人完成(wn chng)工作的最優(yōu)方案；假設(shè)(jish)有另外一名工人（戊）能完成這4項工作，完成每項工作相應(yīng)費用分別為60、45、30和80元。是否用這名新工人（戊）替換原來的某位工人？假設(shè)公司有了第5項工作(E)，4名工人（甲、乙、丙、?。┩瓿晒ぷ鱁的費用分別(fnbi)為20、10、20和80元。這項新工作E比原有的四項

35、工作(A, B, C, D)的某一項優(yōu)先嗎？解：（1）根據(jù)題意，此題屬于最優(yōu)指派問題，引入如下變量：設(shè)變量為Xij,表示第i個人做第j項工作時，Xij=1，否則Xij=0。因此，相應(yīng)的線性規(guī)劃問題為：min=i=1nj=1ncijxij限制條件為：j=1nxij=1i=1, 2, , n, （每個人做一項工作(gngzu)）i=1nxij=1j=1,2, n （每項工作(gngzu)有一個人去做）xij=0或1 i, j=1, 2, , n對于不能工作的情況(qngkung)取一個極大數(shù)代替之即可。根據(jù)此模型寫出Lingo程序并求出最優(yōu)解：model: !4個工人，4個工作的分配問題;sets

36、: Workers/w1.w4/; Jobs/j1.j4/; links (workers, jobs): cost, volume;endsets !目標函數(shù); min=sum (links: cost*volume); !每個工人只能有一份工作; for (workers (I) : sum (jobs (J): volume (I, J) =1; ); !每份工作只能有一個工人; for (jobs (J) : sum (workers(I): volume(I,J)=1; );data: cost= 50 50 100000 20 70 40 20 30 90 30 50 100000

37、 70 20 60 70;enddataend得到如下結(jié)果：Objective value: 140.0000Infeasibilities: 0.000000Total solver iterations: 8Variable Value Reduced CostCOST (W1, J1) 50.00000 0.000000COST (W1, J2) 50.00000 0.000000COST (W1, J3) 100000.0 0.000000COST (W1, J4) 20.00000 0.000000COST (W2, J1) 70.00000 0.000000COST (W2, J2

38、) 40.00000 0.000000COST (W2, J3) 20.00000 0.000000COST (W2, J4) 30.00000 0.000000COST (W3, J1) 90.00000 0.000000COST (W3, J2) 30.00000 0.000000COST (W3, J3) 50.00000 0.000000COST (W3, J4) 100000.0 0.000000COST (W4, J1) 70.00000 0.000000COST (W4, J2) 20.00000 0.000000COST (W4, J3) 60.00000 0.000000CO

39、ST (W4, J4) 70.00000 0.000000VOLUME (W1, J1) 0.000000 0.000000VOLUME (W1, J2) 0.000000 50.00000VOLUME (W1, J3) 0.000000 99990.00VOLUME (W1, J4) 1.000000 0.000000VOLUME (W2, J1) 0.000000 10.00000VOLUME (W2, J2) 0.000000 30.00000VOLUME (W2, J3) 1.000000 0.000000VOLUME (W2, J4) 0.000000 0.000000VOLUME

40、(W3, J1) 0.000000 10.00000VOLUME (W3, J2) 1.000000 0.000000VOLUME (W3, J3) 0.000000 10.00000VOLUME (W3, J4) 0.000000 99950.00VOLUME (W4, J1) 1.000000 0.000000VOLUME (W4, J2) 0.000000 0.000000VOLUME (W4, J3) 0.000000 30.00000VOLUME (W4, J4) 0.000000 30.00000由此得到最佳的工作(gngzu)方案：應(yīng)該由甲來完成工作D，乙來完成工作C，丙來完成工

41、作B，丁來完成工作A。此時總工作成本最小，為140元。（2）根據(jù)題意加入一人戊后該工作變?yōu)?人4項工作問題(wnt)，安照該思路，使用Lingo寫出程序并求出最優(yōu)解：model: !5個工人(gng rn)，4個工作的分配問題;sets: Workers/w1.w5/; Jobs/j1.j4/; links (workers, jobs): cost, volume;endsets !目標(mbio)函數(shù); min=sum (links: cost*volume); !每個工人(gng rn)只能有一份工作; for (workers (I): sum (jobs (J): volume (I

42、, J) =1; ); !每份工作只能(zh nn)有一個工人; for (jobs (J): sum (workers (I): volume (I, J)=1; );data: cost= 50 50 100000 20 70 40 20 30 90 30 50 100000 70 20 60 7060 45 30 80;enddataend得到如下結(jié)果：Global optimal solution found. Objective value: 120.0000 Infeasibilities: 0.000000 Total solver iterations: 6Variable V

43、alue Reduced CostCOST (W1, J1) 50.00000 0.000000COST (W1, J2) 50.00000 0.000000COST (W1, J3) 100000.0 0.000000COST (W1, J4) 20.00000 0.000000COST (W2, J1) 70.00000 0.000000COST (W2, J2) 40.00000 0.000000COST (W2, J3) 20.00000 0.000000COST (W2, J4) 30.00000 0.000000COST (W3, J1) 90.00000 0.000000COST

44、 (W3, J2) 30.00000 0.000000COST (W3, J3) 50.00000 0.000000COST (W3, J4) 100000.0 0.000000COST (W4, J1) 70.00000 0.000000COST (W4, J2) 20.00000 0.000000COST (W4, J3) 60.00000 0.000000COST (W4, J4) 70.00000 0.000000COST (W5, J1) 60.00000 0.000000COST (W5, J2) 45.00000 0.000000COST (W5, J3) 30.00000 0.

45、000000COST (W5, J4) 80.00000 0.000000VOLUME (W1, J1) 0.000000 0.000000VOLUME (W1, J2) 0.000000 40.00000VOLUME (W1, J3) 0.000000 99990.00VOLUME (W1, J4) 1.000000 0.000000VOLUME (W2, J1) 0.000000 10.00000VOLUME (W2, J2) 0.000000 20.00000VOLUME (W2, J3) 1.000000 0.000000VOLUME (W2, J4) 0.000000 0.00000

46、0VOLUME (W3, J1) 0.000000 30.00000VOLUME (W3, J2) 0.000000 10.00000VOLUME (W3, J3) 0.000000 30.00000VOLUME (W3, J4) 0.000000 99970.00VOLUME (W4, J1) 0.000000 10.00000VOLUME (W4, J2) 1.000000 0.000000VOLUME (W4, J3) 0.000000 40.00000VOLUME (W4, J4) 0.000000 40.00000VOLUME (W5, J1) 1.000000 0.000000VO

47、LUME (W5, J2) 0.000000 25.00000VOLUME (W5, J3) 0.000000 10.00000VOLUME (W5, J4) 0.000000 50.00000由此可以得出結(jié)論，此時最佳的工作方案(fng n)為，由甲做工作D，乙來做工作C，丁來做工作B，戊來做工作A。因此，戊要替換掉丙。此時(c sh)成本最小，為120元。（3）根據(jù)題意加入工作(gngzu)E后原題目變?yōu)?人5項工作問題，安照該思路，使用Lingo寫出程序并求出最優(yōu)解：model: !4個工人，5個工作的分配問題;sets: Workers/w1.w4/; Jobs/j1.j5/; Lin

48、ks (workers, jobs): cost, volume;endsets !目標函數(shù); min=sum (links: cost*volume); !每個工人只能有一份工作; for (workers (I) : sum (jobs (J): volume (I, J)=1; ); !每份工作只能(zh nn)有一個工人; for (jobs (J) : sum (workers(I): volume(I,J)=1; );data: cost= 50 50 100000 20 20 70 40 20 30 10 90 30 50 100000 20 70 20 60 70 80;end

49、dataend得到(d do)如下結(jié)果：Global optimal solution found. Objective value: 80.00000 Infeasibilities: 0.000000 Total solver iterations: 5Variable Value Reduced CostCOST (W1, J1) 50.00000 0.000000COST (W1, J2) 50.00000 0.000000COST (W1, J3) 100000.0 0.000000COST (W1, J4) 20.00000 0.000000COST (W1, J5) 20.000

50、00 0.000000COST (W2, J1) 70.00000 0.000000COST (W2, J2) 40.00000 0.000000COST (W2, J3) 20.00000 0.000000COST (W2, J4) 30.00000 0.000000COST (W2, J5) 10.00000 0.000000COST (W3, J1) 90.00000 0.000000COST (W3, J2) 30.00000 0.000000COST (W3, J3) 50.00000 0.000000COST (W3, J4) 100000.0 0.000000COST (W3,

51、J5) 20.00000 0.000000COST (W4, J1) 70.00000 0.000000COST (W4, J2) 20.00000 0.000000COST (W4, J3) 60.00000 0.000000COST (W4, J4) 70.00000 0.000000COST (W4, J5) 80.00000 0.000000VOLUME (W1, J1) 0.000000 30.00000VOLUME (W1, J2) 0.000000 30.00000VOLUME (W1, J3) 0.000000 99980.00VOLUME (W1, J4) 1.000000

52、0.000000VOLUME (W1, J5) 0.000000 10.00000VOLUME (W2, J1) 0.000000 50.00000VOLUME (W2, J2) 0.000000 20.00000VOLUME (W2, J3) 1.000000 0.000000VOLUME (W2, J4) 0.000000 10.00000VOLUME (W2, J5) 0.000000 0.000000VOLUME (W3, J1) 0.000000 60.00000VOLUME (W3, J2) 0.000000 0.000000VOLUME (W3, J3) 0.000000 20.

53、00000VOLUME (W3, J4) 0.000000 99970.00VOLUME (W3, J5) 1.000000 0.000000VOLUME (W4, J1) 0.000000 50.00000VOLUME (W4, J2) 1.000000 0.000000VOLUME (W4, J3) 0.000000 40.00000VOLUME (W4, J4) 0.000000 50.00000VOLUME (W4, J5) 0.000000 70.00000分析結(jié)果易知，此時的工作方案為甲完成(wn chng)工作D，乙完成工作C，丙完成工作E，丁完成工作B，因此，新工作E的優(yōu)先程度

54、要比原工作A要高。5.油畫(yuhu)制作問題(wnt)有一家油畫公司有一些大型客戶，它們一直有穩(wěn)定的需求，此公司每周需要為這些客戶制造5批油畫，每批油畫都完全相同。每批油畫都在同一個制造過程中完成，所有批油畫都要使用同一支調(diào)和畫筆，在繪制兩批油畫之間必須清洗此畫筆。第1到5批油畫的繪制時間分別為40，35，45，32和50分鐘。清洗時間取決于所使用的顏色和顏料類型。例如，如果在使用水性顏料使用油性顏料，或者在使用深色后使用淺色，則需要較長的清洗時間。表4.5給出了清洗時間，其中數(shù)字表示在第i批油畫之后繪制第 j批油畫所需的清洗時間。由于此公司還有其他業(yè)務(wù)，因此希望盡量縮短完成這項每周固定的任

55、務(wù)所需的時間（繪制時間和清洗時間）。那么應(yīng)采取什么順序繪制這些批次的油畫？所指定的順序?qū)⒚恐苤貜?fù)(chngf)執(zhí)行，因此總清洗時間中也應(yīng)計入一周的最后一批油畫與下周的第一批油畫之間所需的清洗時間。解：該問題本質(zhì)上是旅行商問題，解法(ji f)如下：假設(shè)該問題由油畫(yuhu)1, 2, ,n組成，Wij表示油畫i到油畫j之間的清洗時間，決策變量定義為：Xij=1表示選擇從油畫i到油畫j；Xij=0表示不選擇。因此，相應(yīng)的線性規(guī)劃問題為：min=i=1nj=1nWijXiji=1nxij=1,j=1,2,nj=1nxij=1,i=1,2,nui-uj+nxijn-1ij,i,j=2,3,nuj0

56、,j=1,2,nxij=0或1，i,j=1,2,nLINGO程序sets: Picture/A B C D E/: u; link (picture, picture): w, x;endsetsdata: W= 0 11 7 13 11 5 0 13 15 15 13 15 0 23 11 9 13 5 0 3 3 7 7 7 0 ;enddatan=size (picture);min = sum(link: w * x);for (picture (k) :sum (picture (i)| i #ne# k: X(i,k)=1; sum (picture (j)| j #ne# k:

57、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)= 1;for (city (j) |j #gt# 1:sum (city (i)| i #ne# j: X (i, j) = 1;);n=size (city);for (link (i,j)|i #ne# j: u (i)-u(j)+ n*x(i,j)= n-1);for (link: bin(x);運行(ynxng)結(jié)果 Global optimal solution found. Objective value: 1

58、542.000 Objective bound: 1542.000 Infeasibilities: 0.000000 Extended solver steps: 3 Total solver iterations: 150 Model Class: MILP Total variables: 110 Nonlinear variables: 0 Integer variables: 100 Total constraints: 101 Nonlinear constraints: 0 Total nonzeros: 450 Nonlinear nonzeros: 0 Variable Va

59、lue Reduced Cost N 10.00000 0.000000 U (C2) 1.000000 0.000000 U (C3) 3.000000 0.000000 U (C4) 2.000000 0.000000 U (C5) 2.000000 0.000000 U (C6) 3.000000 0.000000 U (C7) 5.000000 0.000000 U (C8) 4.000000 0.000000 U (C9) 6.000000 0.000000 U (C10) 6.000000 0.000000 W (C1, C2) 122.0000 0.000000 W (C1, C

60、3) 259.0000 0.000000 W (C1, C4) 999.0000 0.000000 W (C1, C5) 999.0000 0.000000 W (C1, C6) 999.0000 0.000000 W (C1, C7) 999.0000 0.000000 W (C1, C8) 999.0000 0.000000 W (C1, C9) 999.0000 0.000000 W (C1, C10) 999.0000 0.000000 W (C2, C1) 122.0000 0.000000 W (C2, C3) 999.0000 0.000000 W (C2, C4) 345.00