最優(yōu)化模型計算四

最優(yōu)化模型計算四第一頁，共三十二頁，2022年，8月28日建模時需要注意的幾個基本問題

1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù)如：盡量少使用絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)（如x/y<5改為x<5y）4、合理設(shè)定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級要適當(dāng)(如小于103)第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題第二頁，共三十二頁，2022年，8月28日CUMCM-2000B鋼管訂購和運(yùn)輸問題要鋪設(shè)一條的天然氣管道(見上圖)。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7圖中粗線表示鐵路，單細(xì)線表示公路，雙細(xì)線表示要鋪設(shè)的管道(假設(shè)沿管道或者原來有公路，或者建有施工公路)，圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯?dāng)?shù)字表示里程(單位km)。第三頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題為方便計，1km主管道鋼管稱為1單位鋼管。一個鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠Si在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為si個單位，鋼管出廠銷價1單位鋼管為pi萬元，如下表i1234567si80080010002000200020003000pi1601551551601551501601單位鋼管的鐵路運(yùn)價如下表：里程(km)≤300301～350351～400401～450451～500501～600601～700701～800801～900901～1000運(yùn)價(萬元)20232629323744505560第四頁，共三十二頁，2022年，8月28日1000km以上每增加1至100km運(yùn)價增加5萬元。公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計算）。鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只是運(yùn)到點(diǎn)，而是管道全線）。第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題（1）請制定一個鋼管的訂購和運(yùn)輸計劃，使總費(fèi)用最小。（2）請就（1）的模型分析：哪個鋼廠鋼管的銷價的變化對購運(yùn)計劃和總費(fèi)用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運(yùn)計劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。（3）如果要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。第五頁，共三十二頁，2022年，8月28日A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)圖二第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題第六頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題變量與符號說明aij

站點(diǎn)Ai至Aj的距離（即為鋪設(shè)管道的鋼管數(shù)量）si

鋼廠Si的最大生產(chǎn)量xij

從鋼廠Si運(yùn)往站點(diǎn)Aj的鋼管數(shù)量cij

從鋼廠Si運(yùn)1單位鋼管到Aj的最小費(fèi)用（含銷價）yj

從Aj往左鋪設(shè)的鋼管數(shù)量zj

從Aj往右鋪設(shè)的鋼管數(shù)量fi 0-1變量，表示鋼廠Si是否生產(chǎn)f

總費(fèi)用第七頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題問題分析從鋼廠Si向站點(diǎn)Aj運(yùn)輸鋼管時，應(yīng)該走費(fèi)用最低的路線。首先利用網(wǎng)絡(luò)最短路算法，計算鋼廠Si到站點(diǎn)Aj的最小費(fèi)用cij，它是銷售價和運(yùn)輸費(fèi)用之和。具體數(shù)值見下表cijA2A3A4A5A6A7A8A9A10A11A12A13A14A15S1320.3300.2258.6198180.5163.1181.2224.2252256266281.2288302S2360.3345.2326.6266250.5241226.2269.2297301311326.2333347S3375.3355.2336.6276260.5251241.2203.2237241251266.2273287S4410.3395.2376.6316300.5291276.2244.2222211221236.2243257S5400.3380.2361.6301285.5276266.2234.2212188206226.2228242S6405.3385.2366.6306290.5281271.2234.2212201195176.2161178S7425.3405.2386.6326310.5301291.2259.2236226216198.2186162注：各鋼廠運(yùn)往站點(diǎn)A4的最短路徑均需經(jīng)過A5第八頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題在鋪設(shè)管道時，將沿著鋪設(shè)路線離散卸貨，即運(yùn)到站點(diǎn)Aj后，還要在鋪設(shè)路線上運(yùn)輸（不足整公里部分按整公里計算），每鋪設(shè)1公里，就要卸下1單位鋼管。于是從點(diǎn)Aj向左或右鋪設(shè)m單位鋼管，需要的運(yùn)費(fèi)為構(gòu)造模型目標(biāo)函數(shù)是總費(fèi)用最小

鋼廠運(yùn)到站點(diǎn)的總費(fèi)用站點(diǎn)到鋪設(shè)工地的運(yùn)輸費(fèi)用第九頁，共三十二頁，2022年，8月28日約束條件（1）鋼廠Si的鋼管產(chǎn)量限制第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題（2）鋼廠Si如果有訂貨，至少500單位（3）Aj和Aj+1之間相向鋪設(shè)數(shù)量之和為其距離（4）運(yùn)到Aj的鋼管數(shù)等于Aj向左右鋪設(shè)數(shù)量（5）決策變量的非負(fù)約束第十頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題問題1的數(shù)學(xué)模型站點(diǎn)A1的鋼管全部自A2運(yùn)來，所以xi1=0第十一頁，共三十二頁，2022年，8月28日model:

sets:

!si表示最大生產(chǎn)能力，f為0-1變量、表示是否生產(chǎn)，rs表示實際產(chǎn)量;steel/S1..S7/:si,f,rs;

!hm為站點(diǎn)編號，yj和zj分別表示向左、右鋪設(shè)的鋼管數(shù)，aj表示Aj到Aj+1距離;stat/A2,A3,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15/:hm,yj,zj,aj;

!c是最小費(fèi)用矩陣，x是決策變量;links(steel,stat):c,x;

endsets

data:si=80080010002000200020003000;hm=2356789101112131415;aj=301,1356,194,205,201,680,480,300,220,210,420,500,0;c=第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題各鋼廠運(yùn)到A4的最短路徑都經(jīng)過A5，所以不考慮A4站點(diǎn)問題1的LINGO模型第十二頁，共三十二頁，2022年，8月28日320.3300.2198180.5163.1181.2224.2252256266281.2288302360.3345.2266250.5241226.2269.2297301311326.2333347375.3355.2276260.5251241.2203.2237241251266.2273287410.3395.2316300.5291276.2244.2222211221236.2243257400.3380.2301285.5276266.2234.2212188206226.2228242405.3385.2306290.5281271.2234.2212201195176.2161178425.3405.2326310.5301291.2259.2236226216198.2186162

;

enddata!目標(biāo)函數(shù)為總費(fèi)用;min=@sum(links:c*x)+0.05*@sum(stat:yj+yj*yj+zj+zj*zj);!鋼廠實際產(chǎn)量;@for(steel(i):rs(i)=@sum(stat(j):x(i,j)));!生產(chǎn)能力與產(chǎn)量限制;@for(steel(i):rs(i)<=si(i)*f(i); rs(i)>=500*f(i)); !到達(dá)各站點(diǎn)的鋼管數(shù);@for(stat(j):@sum(steel(i):x(i,j))=yj(j)+zj(j)); !每段管道自左右方向運(yùn)來的鋼管數(shù);@for(stat(j)|hm(j)#lt#15:zj(j)+yj(j+1)=aj(j));@for(steel(i):@bin(f(i))); !各鋼廠是否生產(chǎn)標(biāo)記;@for(stat(j):@gin(yj(j));@gin(zj(j))); !運(yùn)輸量取整數(shù);yj(1)=104; zj(13)=0;end第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題第十三頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題Localoptimalsolutionfoundatiteration:1281Objectivevalue:1278632.VariableValueReducedCostRS(S1)800.00000.000000RS(S2)800.00000.000000RS(S3)1000.0000.000000RS(S4)0.0000000.000000RS(S5)1366.0000.000000RS(S6)1205.0000.000000RS(S7)0.0000000.000000YJ(A2)104.00000.000000YJ(A3)226.00000.000000YJ(A5)1074.0000.000000YJ(A6)184.00000.000000YJ(A7)189.00000.000000YJ(A8)125.00000.000000YJ(A9)505.00000.000000YJ(A10)321.00000.000000YJ(A11)270.00000.000000YJ(A12)75.000000.000000YJ(A13)199.00000.000000YJ(A14)286.00000.000000YJ(A15)165.00000.3797138E-05ZJ(A2)75.000000.2653848E-05ZJ(A3)282.00000.1955465E-04ZJ(A5)10.000000.9997957E-01ZJ(A6)16.000000.9998874E-01ZJ(A7)76.00000-0.2661004E-05ZJ(A8)175.00000.7097367E-05ZJ(A9)159.00000.2409726E-05ZJ(A10)30.00000-0.3583863E-05ZJ(A11)145.0000-0.1601378E-05ZJ(A12)11.00000-0.2274057E-04ZJ(A13)134.00000.9606250E-06ZJ(A14)335.00000.000000ZJ(A15)0.0000000.000000X(S1,A5)335.00000.000000X(S1,A6)200.00000.000000X(S1,A7)265.00000.000000X(S2,A2)179.00000.000000X(S2,A5)321.00000.000000X(S2,A8)300.00000.000000X(S3,A5)336.00000.000000X(S3,A9)664.00000.000000X(S5,A3)508.00000.000000X(S5,A5)92.000000.000000X(S5,A10)351.00000.000000X(S5,A11)415.00000.000000X(S6,A12)86.000000.000000X(S6,A13)333.00000.000000X(S6,A14)621.00000.000000X(S6,A15)165.00000.000000第十四頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題A2A3A5A6A7A8A9A10A11A12A13A14A15合計S1335200265800S2179321300800S33366641000S5508923514151366S6863336211651205合計1795081084200265300664351415863336211655171左運(yùn)104226107418418912550532127075199286165右運(yùn)7528210167617515930145111343350模型1的具體運(yùn)輸方案如下模型1的總費(fèi)用為：1278632萬元第十五頁，共三十二頁，2022年，8月28日1.銷售價格的靈敏度分析第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題靈敏度分析S5和S6兩個工廠的鋼管用料比較大，其銷售價格的變化對總費(fèi)用的影響必然較大。現(xiàn)將各鋼廠單位鋼管的銷售價格分別增加和減少1萬元、4萬元，再次求解模型1，得到總費(fèi)用變化如下表鋼廠Pi增1萬元總費(fèi)用上升Pi增4萬元總費(fèi)用上升Pi減1萬元總費(fèi)用減少Pi減4萬元總費(fèi)用減少S180032008003200S280032008003200S31000400010004000S51007394013695504S61202382915646344S7000971第十六頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題2.產(chǎn)量上限的靈敏度分析S4和S7兩個工廠的鋼管生產(chǎn)量為零，S5和S6的鋼管產(chǎn)量小于其產(chǎn)量上限，所以這4個鋼廠的產(chǎn)量上限在一定范圍內(nèi)變化時，對總費(fèi)用不發(fā)生影響。而S1、S2和S3的鋼管生產(chǎn)是滿負(fù)荷的，它們產(chǎn)量上限的變化將對總費(fèi)用產(chǎn)生明顯的影響。現(xiàn)將它們鋼管生產(chǎn)能力分別增加和減少20單位、100單位，再次求解模型1，得到總費(fèi)用變化如下表鋼廠si增20單位總費(fèi)用減少si增100單位總費(fèi)用減少si減20單位總費(fèi)用上升si減100單位總費(fèi)用上升S1206010300206010300S270035007003500S350025005002500第十七頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題CUMCM-2003B露天礦生產(chǎn)的車輛安排問題

露天鐵礦的的生產(chǎn)主要是由電鏟裝車、卡車運(yùn)輸來完成。露天礦里有若干個爆破生成的石料堆（稱為鏟位），每個鏟位已預(yù)先根據(jù)鐵含量將石料分成礦石和巖石。平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟的平均裝車時間為5分鐘。卸貨地點(diǎn)（卸點(diǎn)）有礦石漏、倒裝場、巖石漏、巖場等，卸點(diǎn)有各自的產(chǎn)量要求。礦石卸點(diǎn)需要鐵含量品位限制29.5±1%，搭配起來送到卸點(diǎn)，搭配的量在一個班次（8小時）內(nèi)滿足品位限制即可。從長遠(yuǎn)看，卸點(diǎn)可以移動，但一個班次內(nèi)不變?？ㄜ嚨钠骄盾嚂r間為3分鐘。

第十八頁，共三十二頁，2022年，8月28日卡車載重154噸，平均時速28km/h。每個班次每臺卡車消耗近1噸柴油。發(fā)動機(jī)點(diǎn)火需要消耗相當(dāng)多的電瓶能量，故一個班次只在開始工作時點(diǎn)火一次?？ㄜ嚨却龝r耗費(fèi)的能量相當(dāng)可觀，，安排時不應(yīng)讓卡車等待。電鏟和卸點(diǎn)都不能同時為兩輛及兩輛以上卡車服務(wù)?？ㄜ嚸看味际菨M載運(yùn)輸。第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題鏟位到卸點(diǎn)的每條道路都是寬60m的雙向車道，不會出現(xiàn)堵車現(xiàn)象，每段道路的長度都是已知的。一個班次的生產(chǎn)計劃包含：出動幾臺電鏟，在哪些鏟位上；出動幾輛卡車，在哪些路線上運(yùn)輸多少次。合格的計劃要在卡車不等待條件下滿足產(chǎn)量和質(zhì)量（品位）要求，而一個好的計劃還應(yīng)該考慮下面兩條原則之一：1.總運(yùn)量（噸公里）最小，出動最少卡車，即運(yùn)輸成本最??；模型一2.利用現(xiàn)有車輛運(yùn)輸，獲得最大的產(chǎn)量（巖石產(chǎn)量優(yōu)先；在產(chǎn)量相同的情況下，取總運(yùn)量最小的解）。模型二第十九頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題根據(jù)上面的兩條原則分別建立數(shù)學(xué)模型，并給出一個班次生產(chǎn)計劃的快速算法。對于下面實例，給出具體的生產(chǎn)計劃、計算相應(yīng)的總運(yùn)量及巖石和礦石產(chǎn)量。

某露天礦有鏟位10個，卸點(diǎn)5個，現(xiàn)有鏟車7臺，卡車20輛。各卸點(diǎn)一個班次的產(chǎn)量要求：礦石漏1.2萬噸、倒裝場Ⅰ1.3萬噸、倒裝場Ⅱ1.3萬噸、巖石漏1.9萬噸、巖場1.3萬噸。鏟位和卸點(diǎn)位置的二維示意圖如上所示：第二十頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題各鏟位和各卸點(diǎn)之間的距離（公里）如下表：鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝場Ⅰ1.900.991.901.131.272.251.482.043.093.51巖場5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝場Ⅱ4.423.863.723.162.252.810.781.621.270.50各鏟位礦石、巖石數(shù)量(萬噸)和礦石的平均鐵含量如下表

：鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量0.951.051.001.051.101.251.051.301.351.25巖石量1.251.101.351.051.151.351.051.151.351.25鐵含量30%28%29%32%31%33%32%31%33%31%第二十一頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題基本假設(shè)(1)

忽略各種隨機(jī)因素引起的電鏟和卡車臨時停頓，即認(rèn)為它們在一個班次（8小時）中連續(xù)工作。(2)

卡車在路上不發(fā)生堵車，空載與滿載的速度都是28km/h。(3)卸點(diǎn)的品位限制（29.5±1%），只考慮一個班次的總量滿足品位限制即可。巖石不能摻入鐵礦石。(4)

卡車每車都裝滿154噸。如果8小時內(nèi)完成，卡車可提前退出。(5)每個班次的所有卡車在剛上班時，都是空車。(6)電鏟定鏟位后，一個班次（8小時）內(nèi)不再移動鏟位。第二十二頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題符號說明Pi

代表鏟位，i=1,2,…,10Qj

代表卸點(diǎn)，j=1,2,…,5xij

從Pi到Qj的石料數(shù)，運(yùn)到巖石漏和巖場的是巖石車·次cij

從Pi到Qj的距離公里Tij

從Pi到Qj路線上運(yùn)行一個周期的平均時間分Aij

從Pi到Qj路線上最多能同時運(yùn)行的卡車數(shù)輛Bij

從Pi到Qj，一輛車一個班次的最多運(yùn)行次數(shù)次Ri

第i號鏟位的鐵礦石含量%di

第j號卸點(diǎn)的任務(wù)需求車·次ki,si

分別表示第i號鏟位的鐵礦石、巖石儲量車·次Yi

標(biāo)志第i號鏟位是否安排電鏟的0-1變量第二十三頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題模型一分析1模型目標(biāo)在現(xiàn)有設(shè)備和滿足生產(chǎn)要求的前提下，先滿足總運(yùn)量（噸·公里）最小，再考慮調(diào)度方案，使卡車數(shù)量最少。2約束條件分析(1)卡車運(yùn)行一個周期的平均時間（單位：分）(2)一條路線上在卡車不等待條件下，最多能運(yùn)行的卡車數(shù)第二十四頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題(4)電鏟與卸點(diǎn)能力限制每臺電鏟一個班次（8小時）最多裝96車；每個卸點(diǎn)8小時最多卸160車。(3)每輛卡車在路線上8小時最多運(yùn)行次數(shù)每條路線的運(yùn)量限制第二十五頁，共三十二頁，2022年，8月28日(6)卸點(diǎn)的品位約束第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題(5)產(chǎn)量任務(wù)約束五個卸點(diǎn)的產(chǎn)量任務(wù)折合成車·次數(shù)為d=（78，85，85，124，85）每個鏟位鐵礦石儲量折合成車·次數(shù)為

k=（61,68,64,68,71,81,68,84,87,81）每個鏟位巖石儲量折合成車·次數(shù)為

s=（81,71,87,68,74,87,68,74,87,81）第二十六頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題(7)電鏟與卡車數(shù)量約束三個礦石卸點(diǎn)的品位規(guī)定為(28.5,30.5)（%）(8)變量的整數(shù)約束模型一可以表示為如下的整數(shù)線性規(guī)劃模型第二十七頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題第二十八頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題model:titleCUMCM-2003B-01;sets:chan/1..10/:R,cnum,cy,ck,Y;xie/1..5/:xsubject,xnum;link(xie,chan):c,lsubject,x,che,b;endsetsdata:R=30282932313332313331;xsubject=1.21.31.31.91.3;c=5.265.194.214.002.952.742.461.900.641.271.900.991.901.131.272.251.482.043.093.515.895.615.614.563.513.652.462.461.060.570.641.761.271.832.742.604.213.725.056.104.423.863.723.162.252.810.781.621.270.50;cy=1.251.101.351.051.151.351.051.151.351.25;ck=0.951.051.001.051.101.251.051.301.351.25;enddata第二十九頁，共三十二頁，2022年，8月28日第四講應(yīng)用LINGO軟件求解數(shù)學(xué)建模問題min=@sum(link:154*c*x);!目標(biāo)函數(shù);!卡車每一條路線上最多可以運(yùn)行的次數(shù);@for(link(i,j):b(i,j)=@floor((8*60-(@floor((c(i,j)/28*60*2+3+5)/5)-1)*5)/(c(i,j)/28*60*2+3+5)));!每