【正文】 數(shù)據(jù)建模作業(yè)4圖論(組合優(yōu)化)實驗最短路問題的應(yīng)用一設(shè)備更新問題，連續(xù)使用4年，也可以在任何一年末將設(shè)備賣掉，，及賣掉舊設(shè)備的回收費(fèi)。問如何確定設(shè)備的更新策略，使4年內(nèi)的總費(fèi)用最少?(單位:萬元)第一年第二年第三年第四年年初購置價(單位:萬元)設(shè)備役齡0～11～22～33～4年維護(hù)費(fèi)年末處理回收費(fèi)解答：用圖論知識來解此題。分別用5個點[1，2，3，4，5]表示第i年開始，各點之間連線表示費(fèi)用，用Cij表示第i年開始，到j(luò)1年結(jié)束的費(fèi)用。根據(jù)題意，可畫出下圖114433結(jié)束32222111110 1 2 3 4 5 6圖11LINGO中程序：sets: nodes/1..5/。 arcs(nodes,nodes)|amp。1 lt amp。2:c,x。end setsdata: c = ,,2,。enddatan = @size(nodes)。min = @sum(arcs:c*x)。@for(nodes(i)| i ne 1 and i ne n :@sum(arcs(i,j):x(i,j)) = @sum(arcs(j,i):x(j,i)))。@sum(arcs(i,j)| i eq 1 : x(i,j)) = 1。程序運(yùn)行結(jié)果如下：Global optimal solution found. Objective value: Total solver iterations: 0 Variable Value Reduced Cost N C( 1, 2) C( 1, 3) C( 1, 4) C( 1, 5) C( 2, 3) C( 2, 4) C( 2, 5) C( 3, 4) C( 3, 5) C( 4, 5) X( 1, 2) X( 1, 3) X( 1, 4) X( 1, 5) X( 2, 3) X( 2, 4) X( 2, 5) X( 3, 4) X( 3, 5) X( 4, 5) Row Slack or Surplus Dual Price 1 2 3 4 5 6 結(jié)論：從程序運(yùn)行結(jié)果可見，設(shè)備應(yīng)該在第一年年末賣出，在第二年初買入，在第四年末賣出，總費(fèi)用最小。運(yùn)輸問題有甲、乙和丙三個城市，每年分別需要煤炭320萬噸、250萬噸和350萬噸，由A, ，B為450萬噸。由于需求大于供應(yīng)，經(jīng)協(xié)商平衡，甲城市在必要時可少供應(yīng)030萬噸，乙城市需求量須全部滿足，丙城市需求量不少于270萬噸。試求將甲、乙兩礦煤炭全部分配出去，滿足上述條件又使總運(yùn)費(fèi)最低的調(diào)運(yùn)方案。(單位:萬元/萬噸)甲乙丙A151822B212516解答：解：（1）甲甲’乙丙丙’銷量A1515192222400B2121251616450CM0MM070運(yùn)量2903025027080（2）甲甲’乙丙丙’銷量VjA15151822224006B21212516164500CM0MM07016產(chǎn)量2903025027080Ui2121241616（3）甲甲’乙丙丙’銷量A1515192222400B2121251616450CM0MM070運(yùn)量2903025027080（4）甲甲’乙丙丙’銷量VjA15151822224006B21212516164500CM30MM07016產(chǎn)量2903025027080Ui2116241616結(jié)論：調(diào)整后最優(yōu)方案的最低費(fèi)用為：150*15+250*18+140*21+270*16+40*16+30*0+40*0=14650萬元生產(chǎn)計劃與庫存管理(1)某公司生產(chǎn)一種除臭劑，它在1至4季度的生產(chǎn)成本、，則允許延期交貨，(包括儲存費(fèi)用和罰金)的除臭劑的生產(chǎn)計劃，問各季度應(yīng)生產(chǎn)多少?、生產(chǎn)量及訂貨量季度生產(chǎn)成本(盒/元)季度生產(chǎn)成本（盒/元）訂貨量（萬盒）生產(chǎn)量（萬盒）Ⅰ51013Ⅱ51415Ⅲ62015Ⅳ6813 (2)如果產(chǎn)品不允許延期交貨，則公司考慮工人加班，已知加班生產(chǎn)出產(chǎn)品的成本要比原成本高出20%，且每季度加班最多生產(chǎn)2萬盒。問：在這種情況下，將如何安排生產(chǎn)，使總成本最少?解答：（1）設(shè)第一、二、三、四季度生產(chǎn)量分別為x1，x2，x3，x4，得出四個季度支出費(fèi)用為：季度費(fèi)用第一季度費(fèi)用z15*x1+x110第二季度費(fèi)用z25*x2+x1+x224第三季度費(fèi)用z36*x3+x1+x2+x343第四季度費(fèi)用z46*x4+x1+x2+x3+x452總的支出費(fèi)用為：Z=z1+z2+z3+z4=9*x1+8*x2+8*x3+7*x4130；LINGO中程序：min = 7*x1 + 6*x2 + 6*x3 + 6*x431。x1+x2+x3+x4=52。x1= 13。x1=10。x2= 15。x1+x2= 24。x3= 15。x1+x2+x3= 43。x4= 13。程序運(yùn)行結(jié)果如下： Global optimal solution found. Objective value: Total solver iterations: 0 Variable Value Reduced Cost X1 X2 X3 X4 Row Slack or Surplus Dual Price 1 2 3 4 5 6 7 8 9 lingo運(yùn)行結(jié)果可得：X1=13；X2=15；X3=15；X4=9；應(yīng)該這樣安排生產(chǎn)：第一季度生產(chǎn)13萬盒，第二季度生產(chǎn)15萬，第三季度生產(chǎn)15萬，第四季度生產(chǎn)9萬盒。總成本最低294萬元。（2）設(shè)第一季度加班生產(chǎn)的產(chǎn)品為x11盒，第二季度加班生產(chǎn)的產(chǎn)品為x21盒，第三季度加班生產(chǎn)的產(chǎn)品為x31盒，第四季度加班生產(chǎn)的產(chǎn)品為x41盒。LINGO中程序：min = 8*x1 +9*x11+ 7*x2 + 8*x21+7*x3 +*x31+ 6*x4+*x4178。x1+x11+x2+x21+x3+x31+x4+x41=52。x1= 13。x1+x11=10。x2= 15。x1+x2+x11+x21= 24。x3= 15。x1+x2+x3+x11+x21+x31= 44。x4= 13。程序運(yùn)行結(jié)果如下： Global optimal solution found. Objective value: Total solver iterations: 2 Variable Value Reduced Cost X1 X11 X2 X21 X3 X31