數(shù)學建模競賽中的部分優(yōu)化問題

1、數(shù)學建模競賽中的部分優(yōu)化問題最短路問題定義 是由 點出發(fā)至終點 的最短路程，由最優(yōu)化原理可得這是一個函數(shù)方程，用LINGO可以方便的解決。最短路問題最短路問題LINGO源程序(shorttest.lg4) 計算的部分結(jié)果為： Feasible solution found at iteration: 0 Variable Value N 10.00000 F( 1) 17.00000 F( 2) 11.00000 F( 3) 15.00000 F( 4) 8.000000 F( 5) 13.00000 F( 6) 11.00000 F( 7) 5.000000 F( 8) 7.000000 F

2、( 9) 9.000000 F( 10) 0.000000 P( 1, 2) 1.000000 P( 1, 3) 0.000000 P( 2, 4) 1.000000 P( 2, 5) 0.000000 P( 2, 6) 0.000000 P( 3, 4) 1.000000 P( 3, 5) 0.000000 P( 3, 6) 0.000000 P( 4, 7) 0.000000 P( 4, 8) 1.000000 P( 5, 7) 1.000000 P( 5, 8) 0.000000 P( 5, 9) 0.000000 P( 6, 8) 1.000000 P( 6, 9) 0.000000

3、P( 7, 10) 1.000000 P( 8, 10) 1.000000 P( 9, 10) 1.000000在約10,000米高空的某邊長160公里的正方形區(qū)域內(nèi), 經(jīng)常有若干架飛機作水平飛行。區(qū)域內(nèi)每架飛機的位置和速度均由計算機記錄其數(shù)據(jù)，以便進行飛行管理。當一架欲進入該區(qū)域的飛機到達區(qū)域邊緣, 記錄其數(shù)據(jù)后，要立即計算并判斷是否會與區(qū)域內(nèi)的飛機發(fā)生碰撞。如果會碰撞，則應(yīng)計算如何調(diào)整各架(包括新進入的)飛機飛行方向角，以避免碰撞?，F(xiàn)假定條件如下: 1)不碰撞的標準為任意兩架飛機的距離大于8公里; 2) 飛機飛行方向角調(diào)整的幅度不應(yīng)超過30度; 3) 所有飛機飛行速度均為每小時800公里;

4、 4) 進入該區(qū)域的飛機在到達區(qū)域邊緣時, 與區(qū)域內(nèi)飛機的距離應(yīng)在60公里以上; 5) 最多需考慮6架飛機; 6) 不必考慮飛機離開此區(qū)域后的狀況。請你對這個避免碰撞的飛行管理問題建立數(shù)學模型，列出計算步驟，對以下數(shù)據(jù)進行計算(方向角誤差不超過0.01度)，要求飛機飛行方向角調(diào)整的幅度盡量小。設(shè)該區(qū)域4個頂點的座標為(0,0)，(160,0)，(160,160)，(0,160)。記錄數(shù)據(jù)為:飛行管理問題飛機編號橫座標x縱座標y方向角(度) 1150140243285852363150155220.54145501595130150230新進入0 052 注: 方向角指飛行方向與x軸正向的夾角。

5、試根據(jù)實際應(yīng)用背景對你的模型進行評價與推廣。 飛行管理問題模型及求解模型的建立飛行管理問題飛行管理問題飛行管理問題飛行管理問題模型求解ij=max，這實際上強化了問題的要求，即考慮了有些飛機可能已經(jīng)飛出區(qū)域，但仍不允許兩架飛機的距離小于Km這個簡化的模型可以輸入LINGO軟件演示：CUMCM-1995Aa.lg4 結(jié)果：CUMCM-1995A-a.txt飛行管理問題問題1. 如何下料最節(jié)省 ? 鋼管下料 問題2. 客戶增加需求：原料鋼管:每根19米 4米50根 6米20根 8米15根 客戶需求節(jié)省的標準是什么？由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最

6、節(jié)??？5米10根 按照客戶需要在一根原料鋼管上安排切割的一種組合。 切割模式余料1米 4米1根 6米1根 8米1根 余料3米 4米1根 6米1根 6米1根 合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米 8米1根 8米1根 鋼管下料 為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)??？合理切割模式2. 所用原料鋼管總根數(shù)最少 模式4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問題1 兩種標準1. 原料鋼管剩余總余量最小xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,7) 約束滿足需求

7、 決策變量 目標1（總余量）按模式2切割12根,按模式5切割15根，余料27米 模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015最優(yōu)解：x2=12, x5=15, 其余為0；最優(yōu)值：27整數(shù)約束： xi 為整數(shù)當余料沒有用處時，通常以總根數(shù)最少為目標 目標2（總根數(shù)）鋼管下料問題1 約束條件不變 最優(yōu)解：x2=15, x5=5, x7=5, 其余為0；最優(yōu)值：25。xi 為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米 雖余料增加8米，但減少了2根 與目標1的結(jié)果“共切割27根，余料27米”

8、 相比 鋼管下料問題2對大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復雜。決策變量 xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,3) r1i, r2i, r3i, r4i 第i 種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長的鋼管的數(shù)量滿足需求模式合理：每根余料不超過3米整數(shù)非線性規(guī)劃模型鋼管下料問題2目標函數(shù)（總根數(shù)）約束條件整數(shù)約束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)為整數(shù)增加約束，縮小可行域，便于求解原料鋼管

9、總根數(shù)下界： 特殊生產(chǎn)計劃：對每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：31 模式排列順序可任定 鋼管下料問題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長19米LINGO求解整數(shù)非線性規(guī)劃模型Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.0

10、00000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 模式1：每根原料鋼管切割成2根

11、4米、1根5米和1根6米鋼管，共10根；(書上模式1與模式2相反了)模式2：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數(shù)為28根。演示cut02a.lg4； cut02b.lg4露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘卡車在等待時所耗費的能量也是相當可觀的，原則上在安排時不應(yīng)發(fā)生卡車等待的情況。 露天礦生產(chǎn)的車輛安排(CUMCM-2003B) 礦石卸點需要的鐵含量要求都為2

12、9.5%1%(品位限制），搭配量在一個班次（8小時）內(nèi)滿足品位限制即可。卸點在一個班次內(nèi)不變?？ㄜ囕d重量為154噸，平均時速28km,平均卸車時間為3分鐘。問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次 ?平面示意圖問題數(shù)據(jù) 距離鏟位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.7

13、61.271.832.742.604.213.725.056.10倒裝4.423.863.723.162.252.810.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量095105100105110125105130135125巖石量125110135105115135105115135125鐵含量30%28%29%32%31%33%32%31%33%31%問題分析 與典型的運輸問題明顯有以下不同：這是運輸?shù)V石與巖石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸；產(chǎn)地、銷地均有單位時間的流量限制；運輸車輛只有

14、一種，每次滿載運輸，154噸/車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個產(chǎn)地作為最后結(jié)果中的產(chǎn)地；最后求出各條路線上的派出車輛數(shù)及安排。近似處理：先求出產(chǎn)位、卸點每條線路上的運輸量(MIP模型)然后求出各條路線上的派出車輛數(shù)及安排模型假設(shè)卡車在一個班次中不應(yīng)發(fā)生等待或熄火后再啟動的情況；在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認為只要平均時間能完成任務(wù)，就認為不沖突。我們不排時地進行討論；空載與重載的速度都是28km/h，耗油相差很大；卡車可提前退出系統(tǒng)，等等。如理解為嚴格不等待，難以用數(shù)學規(guī)劃模型來解 個別參數(shù)隊找到了可行解 （略）符號xij ：從i鏟位到j(luò)號卸點的石料運

15、量 （車） 單位： 噸；cij ：從i號鏟位到j(luò)號卸點的距離 公里；Tij :從i號鏟位到號j卸點路線上運行一個周期平均時間 分；Aij ：從號鏟位到號卸點最多能同時運行的卡車數(shù) 輛；Bij ：從號鏟位到號卸點路線上一輛車最多可運行的次數(shù) 次；pi：i號鏟位的礦石鐵含量 p=(30,28,29,32,31,33,32,31,33,31) %qj : j號卸點任務(wù)需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸cki ：i號鏟位的鐵礦石儲量 萬噸cyi ：i號鏟位的巖石儲量 萬噸fi :描述第i號鏟位是否使用的0-1變量，取1為使用；0為關(guān)閉。(近似)優(yōu)化模型（1）道路能力(

16、卡車數(shù))約束（2）電鏟能力約束（3）卸點能力約束（4）鏟位儲量約束（5）產(chǎn)量任務(wù)約束（6）鐵含量約束（7）電鏟數(shù)量約束（8）整數(shù)約束 .xij為非負整數(shù)fi 為0-1整數(shù)計算結(jié)果（LINGO軟件）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦漏135411倒4243巖場7015巖漏8143倒13270鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏0.8671.8620.314倒場1.0771.162巖場1.8920.326巖石漏1.8411.229倒場0.6840.11.489cumcm2003b1.lg4計算結(jié)果（派車）鏟位1鏟位2鏟位3鏟位4鏟位5鏟

17、位6鏟位7鏟位8鏟位9鏟位10礦石漏1 (29)倒場1 (39)1 (37)巖場1 (37)巖石漏1(44)1 (35)倒場1 (47)結(jié)論：鏟位1、2、3、4、8、9、10處各放置一臺電鏟。一共使用了13輛卡車；總運量為85628.62噸公里；巖石產(chǎn)量為32186噸；礦石產(chǎn)量為38192噸。此外：6輛聯(lián)合派車（方案略）最大化產(chǎn)量結(jié)論：（略）目標函數(shù)變化此外：車輛數(shù)量（20輛）限制（其實上面的模型也應(yīng)該有） 鋼管運輸問題（CUMCM-2000B) 要鋪設(shè)一條的輸送天然氣的主管道, 如圖所示(見下頁)。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有表示公路，雙細線表示要鋪設(shè)的管道(假設(shè)沿管道或者原來有公

18、路，或者建有施工公路)，圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯數(shù)字表示里程(單位km)。 為方便計，1km主管道鋼管稱為1單位鋼管。圖中粗線表示鐵路，單細線A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7鐵路運價表里程3003013503514004014

19、50451500運價2023262932 鋼管運輸問題（CUMCM-2000B) 鋼管運輸問題（CUMCM-2000B)一個鋼廠如果承擔制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠在指定期限內(nèi)能生產(chǎn)該鋼管的最大個單位，鋼管出廠銷價1單位鋼管為萬元，如下表：數(shù)量為1234567800800100020002000200030001601551551601551501601單位鋼管的鐵路運價如下表： 鋼管運輸問題（CUMCM-2000B)里程(km)300301350351400401450451500運價(萬元)2023262932里程(km)50160060170070180080190090

20、01000運價(萬元)37445055601000km以上每增加1至100km運價增加5萬元。 鋼管運輸問題（CUMCM-2000B)公路運輸費用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計算）。鋼管可由鐵路、公路運往鋪設(shè)地點（不只是運到點，而是管道全線）。(1)請制定一個主管道鋼管的訂購和運輸計劃，使總費用最?。ńo出總費用)。(2)請就（1）的模型分析：哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運計劃和總費用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。(3)如果要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。 鋼管運輸問題（CUMCM-2000B)常用解法: 二次規(guī)劃先計算最小運費矩陣兩種運輸方式（鐵路公路）混合最短路問題是普通最短路問題的變種，需要自己設(shè)計算法 鋼管運輸問題（CUMCM-2000B) 鋼管運輸問題（CUMCM-2000B)運輸矩陣的計算模型問題分析鐵路子網(wǎng)絡(luò) 鋼管運輸問題（CU