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

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

2、2, 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 -50.2 17.3 -20.2 18.4 -0.2

3、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;for (arcs: bin(x);End得到結(jié)果如下

4、：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.000000 C (b3, c4) 15.70000 0.000000 C

5、(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 (d5, e1) 12.20000 0.000000 C (d5

6、, 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) 50.00000 0.000000 C (e2, f) 60.

7、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.000000 50.20000 X (c2, d3) 0.000000

8、-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 20.20000 X (d1, e2) 0.000000 -18.

9、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.000000 4 0.000000 0.000000 5 0.0000

10、00 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.000000 0.000000分析結(jié)果容易得出最佳的路徑為a2-b3-

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

12、煤炭貯存（Warehouse）表達(dá)為A, B；煤礦與各城市之間的煤炭運(yùn)價(jià)為P，用x表示決策點(diǎn)。使用Lingo軟件進(jìn)行計(jì)算并取最優(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 objective;OBJ min = sum (Routes: c * x);! The supply constraints;fo

13、r (Warehouse (i): SUPsum (Customer (j): x (i,j) <= Supply(i);! The demand constraints;sum (warehouse (i): x (i, 1) >290;sum (warehouse (i): x (i, 1) <320;sum (warehouse (i): x (i, 2) =250;sum (warehouse (i): x (i, 3) >270;sum (warehouse (i): x (i, 3) >350;! Here are the parameters;dat

14、a: Supply = 400, 450; Gain = 320, 250, 380; c = 15, 18, 22,21, 25, 16;Enddataend 得到如下結(jié)果：Global 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.

15、000000GAIN (2) 290.0000 0.000000GAIN (3) 310.0000 0.000000C (A, 1) 15.00000 0.000000C (A, 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)

16、 140.0000 0.000000X (B, 2) 0.000000 1.000000X (B, 3) 310.0000 0.000000因此得到結(jié)論：由A礦向甲乙丙三座城市的送礦量（萬噸）為150、250、0；由B礦向甲乙丙三座城市的送礦量（萬噸）為140、0、310，此時(shí)總運(yùn)輸費(fèi)最小，為14650萬元。3、生產(chǎn)計(jì)劃與庫存管理(1)某公司生產(chǎn)一種除臭劑，它在1至4季度的生產(chǎn)成本、生產(chǎn)量及訂貨量表4.3所示.如果除臭劑在生產(chǎn)當(dāng)季沒有交貨，保管在倉庫里除臭劑每盒每季度還需1元錢的儲(chǔ)存費(fèi)用。如果某個(gè)季度的貨物供應(yīng)量不足，則允許延期交貨，延期交貨的罰金是每盒每季度3元。請公司希望制定一個(gè)成本最低(

17、包括儲(chǔ)存費(fèi)用和罰金)的除臭劑的生產(chǎn)計(jì)劃，問各季度應(yīng)生產(chǎn)多少?(2)如果產(chǎn)品不允許延期交貨，則公司考慮工人加班，已知加班生產(chǎn)出產(chǎn)品的成本要比原成本高出20%，且每季度加班最多生產(chǎn)2萬盒.問:在這種情況下，將如何安排生產(chǎn)，使總成本最少?解：（1） 根據(jù)題意，將此問題轉(zhuǎn)化為運(yùn)輸問題，將每季度的生產(chǎn)量看作是供方，將每季度的訂貨量看作是需求方，將不屬于本季度供貨的量視為其他季度運(yùn)輸過來的，那么具體思路作圖如下：紅色字樣為第一季度運(yùn)輸每件費(fèi)用，5+166+36+3×25+1×255+35+1×35+1×25+15季度2訂貨量季度3訂貨量季度4訂貨量季度1生產(chǎn)量季度2

18、生產(chǎn)量季度3生產(chǎn)量季度4生產(chǎn)量季度1訂貨量6+3×36+3×26+3×166+1紅色字樣為季度1生產(chǎn)向4個(gè)季度的運(yùn)送量；綠色字樣為季度2生產(chǎn)向4個(gè)季度的運(yùn)送量；藍(lán)色字樣為季度2生產(chǎn)向4個(gè)季度的運(yùn)送量；黑色字樣為季度2生產(chǎn)向4個(gè)季度的運(yùn)送量。列出配送供需表格：季度1需求季度2需求季度3需求季度4需求季度1配送單價(jià)（萬元/萬盒）5666季度2配送單價(jià)（萬元/萬盒）8567季度3配送單價(jià)（萬元/萬盒）12967季度4配送單價(jià)（萬元/萬盒）151296設(shè)Cij為從季度生產(chǎn)Ai到季度需求Bj的配送單價(jià)，Xij為從季度生產(chǎn)Ai到季度需求Bj的運(yùn)輸量，因此總的費(fèi)用為：i=1mj

19、=1ncij xij第i個(gè)季度的運(yùn)出量應(yīng)該小于或等于該季度的生產(chǎn)量：j=1mxijai第j個(gè)季度的運(yùn)入量應(yīng)該等于該季度的需求量：i=1mxijbj根據(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,

20、 8; c = 5, 6, 7, 8, 8, 5, 6, 7, 12, 9, 6, 7, 15, 12, 9, 6;Enddata! The 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 得到如下結(jié)果：Global opt

21、imal solution found. Objective value: 294.0000 Infeasibilities: 0.000000 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.00000

22、0 0.000000C (1, 1) 5.000000 0.000000C (1, 2) 6.000000 0.000000C (1, 3) 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

23、, 4) 7.000000 0.000000C (4, 1) 15.00000 0.000000C (4, 2) 12.00000 0.000000C (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

24、0.000000X (2, 4) 0.000000 4.000000X (3, 1) 0.000000 8.000000X (3, 2) 0.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 (

25、1) 0.000000 2.000000SUP (2) 0.000000 3.000000SUP (3) 0.000000 3.000000SUP (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é)果易知，最佳的方案為：第一季度生產(chǎn)14萬盒，給出10萬盒滿足第一季度要求，庫存3萬盒，不拖欠；第二季度生產(chǎn)15萬盒，給出11萬盒，連同第一季度庫存3萬盒加起來為14萬盒滿足第二季度要求，庫存4萬盒

26、，不拖欠；第三季度生產(chǎn)15萬盒，全部給出，連同第二季度庫存4萬盒加起來19萬盒，拖欠1萬盒；第四季度生產(chǎn)9萬盒，還清第三季度拖欠1萬盒，剩下8萬盒滿足第四季度需求。此方案下總成本最小，為294萬元。（2） 分析題目，可以將工人加班的費(fèi)用視為除本季生產(chǎn)外為接下來其他季度供應(yīng)貨物的費(fèi)用。參考如下配送供需表格：季度1需求季度2需求季度3需求季度4需求季度1配送單價(jià)（萬元/萬盒）5666季度2配送單價(jià)（萬元/萬盒）-566季度3配送單價(jià)（萬元/萬盒）-67.2季度4配送單價(jià)（萬元/萬盒）-6對于Lingo程序的改變，只需將每季度生產(chǎn)量擴(kuò)充為+2萬盒即可，對于表格中午單價(jià)的位置，使用極大數(shù)105來表示無

27、窮大，根據(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= 15, 17, 17, 15; b= 10, 14, 20, 8; c = 5, 6, 6, 6, 100000, 5, 6, 6, 1000000, 1000000, 6, 7.2, 1000000

28、, 1000000, 1000000, 6;Enddata! The 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 得到如下結(jié)果： Global optimal solution found. Objective valu

29、e: 288.0000 Infeasibilities: 0.000000 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.00000

30、0C (1, 2) 6.000000 0.000000C (1, 3) 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) 100000

31、0 0.000000C (4, 2) 1000000 0.000000C (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,

32、1) 0.000000 999995.0X (3, 2) 0.000000 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.0

33、00000SUP (3) 0.000000 0.000000SUP (4) 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é)果，得到最優(yōu)生產(chǎn)方案：第一季度生產(chǎn)15萬盒（2萬盒為加班產(chǎn)出），10萬盒給出，滿足第一季度需求，剩下5萬盒庫存至第四季度；第二季度生產(chǎn)17萬盒（2萬盒為加班產(chǎn)出），14萬盒給出，滿足第二季度需求，剩下3萬盒庫存至第三季度；第三季度生產(chǎn)17萬盒（2萬盒為加班產(chǎn)出），連同第二季度

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

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

36、Jobs/j1.j4/; links (workers, jobs): cost, volume;endsets !目標(biāo)函數(shù); min=sum (links: cost*volume); !每個(gè)工人只能有一份工作; for (workers (I) : sum (jobs (J): volume (I, J) =1; ); !每份工作只能有一個(gè)工人; 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 70;endda

37、taend得到如下結(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) 40.00000 0.00000

38、0COST (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.000000COST (W4, J4) 70.000

39、00 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 (W3, J1) 0.000000 10.00000VOLUME (W3