優(yōu)化建模與lindo lingo軟件的課件第12章

優(yōu)化建模與LINDO/LINGO軟件第12章數(shù)學(xué)建模競賽中的部分優(yōu)化問題［原書相關(guān)信息］謝金星,薛毅編，清華大學(xué)出版社,2005年7月出版.

簡要提綱1.CUMCM-1995A:一個飛行管理問題2.CUMCM-2000B:鋼管訂購與運輸3.CUMCM-2003B：露天礦生產(chǎn)的車輛安排4.CUMCM-2000D:空洞探測1995年全國大學(xué)生數(shù)學(xué)建模競賽A題

一個飛行管理問題

一個飛行管理問題在約10000m高空的某邊長160km的正方形區(qū)域內(nèi),經(jīng)常有若干架飛機作水平飛行,區(qū)域內(nèi)每架飛機的位置和速度向量均由計算機記錄其數(shù)據(jù),以便進行飛行管理.當(dāng)一架欲進入該區(qū)域的飛機到達邊界區(qū)域邊緣時,記錄其數(shù)據(jù)后,要立即計算并判斷是否會與其區(qū)域內(nèi)的飛機發(fā)生碰撞.如果會碰撞,則應(yīng)計算如何調(diào)整各架(包括新進入的)飛機飛行的方向角,以避免碰撞.現(xiàn)假設(shè)條件如下:1)不碰撞的標(biāo)準(zhǔn)為任意兩架飛機的距離大于8km;2)飛機飛行方向角調(diào)整的幅度不應(yīng)超過30度;3)所有飛機飛行速度均為每小時為800km;4)進入該區(qū)域的飛機在到達區(qū)域邊緣時,與區(qū)域內(nèi)飛機的距離應(yīng)在60km以上;5)最多考慮6架飛機;6)不必考慮飛機離開此區(qū)域后的狀況;請你對這個避免碰撞的飛行管理問題建立數(shù)學(xué)模型.列出計算步驟,對以下數(shù)據(jù)進行計算(方向角誤差不超過0.01度),要求飛機飛行方向角調(diào)整的幅度盡量小.設(shè)該區(qū)域4個頂點坐標(biāo)為(0,0),(160,0),(160,160),(0,160).記錄數(shù)據(jù)為:

飛機編號橫坐標(biāo)x縱坐標(biāo)y方向角(度)11502363150155220.54145501595130150230

新進入0052注:方向角指飛行方向與x軸正向的夾角兩架飛機不碰撞的條件（0≤t≤Tij）

Ti為第i架飛機飛出區(qū)域的時刻不碰撞條件

初始位置

時刻t飛機的位置兩架飛機的距離（平方）不必考慮在區(qū)域外的碰撞

兩架飛機都在區(qū)域中的時間具體來看，第i架飛機在區(qū)域內(nèi)的時間飛機飛出區(qū)域的時刻整理：

fij(t)的最小值(-bij2/4+cij)

；此時其中：

不碰撞條件的等價表述

最后，優(yōu)化模型為

fij(t)大于等于０肯定成立fij(t)大于等于０等價于fij(t)大于等于０等價于LINGO求解程序exam1201a.lg4一個簡化的數(shù)學(xué)模型任何一架飛機在區(qū)域中停留最長時間

放松到任兩架飛機在這段時間不碰撞甚至放松到任兩架飛機永遠不碰撞其他目標(biāo)調(diào)整后的方向角

總的調(diào)整量最小

最大調(diào)整量最小

初始位置與方向角基于相對運動觀點的模型基于相對運動觀點的模型于是

數(shù)學(xué)規(guī)劃模型

LINGO求解程序exam1201b.lg4注意：應(yīng)先計算出初始時刻的βij2000年全國大學(xué)生數(shù)學(xué)建模競賽B題

鋼管訂購與運輸

問題描述由鋼管廠訂購鋼管，經(jīng)鐵路、公路運輸，鋪設(shè)一條鋼管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1~S7

鋼管廠火車站450里程（km)（沿管道建有公路）鋼廠的產(chǎn)量和銷價（1單位鋼管=1km管道鋼管）鋼廠產(chǎn)量的下限：500單位鋼管1單位鋼管的鐵路運價1000km以上每增加1至100km運價增加5萬元1單位鋼管的公路運價：0.1萬元/km（不足整公里部分按整公里計）（1）制定鋼管的訂購和運輸計劃，使總費用最小.（2）分析對購運計劃和總費用影響：哪個鋼廠鋼管銷價的變化影響最大；哪個鋼廠鋼管產(chǎn)量上限的變化影響最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）討論管道為樹形圖的情形問題1的基本模型和解法總費用最小的優(yōu)化問題總費用：訂購，運輸（由各廠Si經(jīng)鐵路、公路至各點Aj,

i=1,…7;j=1,…15

），鋪設(shè)管道AjAj+1

（j=1,…14)由Si至Aj的最小購運費用路線及最小費用cij

由Si至Aj的最優(yōu)運量xij由Aj向AjAj-1段鋪設(shè)的長度yj及向AjAj+1段鋪設(shè)的長度zj最優(yōu)購運計劃約束條件鋼廠產(chǎn)量約束：上限和下限（如果生產(chǎn)的話）運量約束：xij對i求和等于zj加yj；

zj與

yj+1之和等于AjAj+1段的長度ljyj

zjAj-1

Aj

Aj+1基本模型由Aj向AjAj-1段鋪設(shè)的運量為1+…+yj=yj(

yj+1)/2由Aj向AjAj+1段鋪設(shè)的運量為1+…+zj=zj(

zj+1)/2二次規(guī)劃?求解步驟1）求由Si至Aj的最小購運費用路線及最小費用cij

難點：公路運費是里程的線性函數(shù)，而鐵路運費是里程的分段階躍函數(shù)，故總運費不具可加性。因而計算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要對鐵路網(wǎng)和公路網(wǎng)進行預(yù)處理，才能使用常用算法，得到最小購運費用路線。--至少求3次最短路如S7至A10的最小費用路線先鐵路1130km，再公路70km,運費為77（萬元）先公路（經(jīng)A15）40km,再鐵路1100km，再公路70km,運費為76（萬元）任意兩點之間最短路的Floyd-Warshall算法1）求由Si至Aj的最小購運費用路線及最小費用cij

A13次最短路的LINGO程序：Exam1202a.lg4Exam1202b.lg4Exam1202c.lg4uij(k)

是任意兩個節(jié)點i，j之間距離的臨時標(biāo)號，即從節(jié)點i到j(luò)但不允許經(jīng)過其他節(jié)點k，k+1，…,n時的最短距離實際上只有S4和S7需要分解成子問題求解每個子問題是標(biāo)準(zhǔn)的二次規(guī)劃，決策變量為xij,yj,zj,不超過135個。fi表示鋼廠i是否使用；xij是從鋼廠i運到節(jié)點j的鋼管量yj是從節(jié)點j向左鋪設(shè)的鋼管量；zj是向右鋪設(shè)的鋼管量

c)比較好的方法：引入0-1變量LINDO/LINGO得到的結(jié)果比matlab得到的好exam1202d.lg4yj

zjAj問題2:

分析對購運計劃和總費用影響(哪個鋼廠銷價變化影響最大；哪個鋼廠產(chǎn)量上限變化影響最大)規(guī)劃問題的靈敏度分析問題3：管道為樹形圖701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100(jk)是連接Aj,Ak的邊，E是樹形圖的邊集，ljk是(jk)的長度，yjk是由Aj沿(jk)鋪設(shè)的鋼管數(shù)量2003年全國大學(xué)生數(shù)學(xué)建模競賽B題

露天礦生產(chǎn)的車輛安排露天礦里鏟位已分成礦石和巖石:平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘卡車在等待時所耗費的能量也是相當(dāng)可觀的，原則上在安排時不應(yīng)發(fā)生卡車等待的情況。露天礦生產(chǎn)的車輛安排

礦石卸點需要的鐵含量要求都為29.5%1%(品位限制），搭配量在一個班次（8小時）內(nèi)滿足品位限制即可。卸點在一個班次內(nèi)不變。卡車載重量為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.761.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礦石量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%問題分析與典型的運輸問題明顯有以下不同：這是運輸?shù)V石與巖石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸；產(chǎn)地、銷地均有單位時間的流量限制；運輸車輛只有一種，每次滿載運輸，154噸/車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個產(chǎn)地作為最后結(jié)果中的產(chǎn)地；最后求出各條路線上的派出車輛數(shù)及安排。近似處理：先求出產(chǎn)位、卸點每條線路上的運輸量(MIP模型)然后求出各條路線上的派出車輛數(shù)及安排模型假設(shè)卡車在一個班次中不應(yīng)發(fā)生等待或熄火后再啟動的情況；在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認(rèn)為只要平均時間能完成任務(wù)，就認(rèn)為不沖突。我們不排時地進行討論；空載與重載的速度都是28km/h，耗油相差很大；卡車可提前退出系統(tǒng)，等等。如理解為嚴(yán)格不等待，難以用數(shù)學(xué)規(guī)劃模型來解個別參數(shù)隊找到了可行解（略）符號xij

：從i鏟位到j(luò)號卸點的石料運量（車）單位：噸；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）道路能力(卡車數(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.489exam1203.lg4注:LINGO8.0本來是可以得到最優(yōu)解的，但有些

LINGO8.0可能出現(xiàn)系統(tǒng)錯誤,可能是系統(tǒng)BUG計算結(jié)果（派車）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位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é)論：（略）目標(biāo)函數(shù)變化此外：車輛數(shù)量（20輛）限制（其實上面的模型也應(yīng)該有）2000年全國大學(xué)生數(shù)學(xué)建模競賽D題

空洞探測山體隧道壩體等的某些內(nèi)部結(jié)構(gòu)可用彈性波測量來確定。簡化問題可敘述為，一塊均勻介質(zhì)構(gòu)成的矩形平板內(nèi)有一些充滿空氣的空洞。在平板的兩個鄰邊分別等距地設(shè)置若干波源，在他們的對邊對等地安放同樣多的接收器，記錄彈性波由每個波源到達對邊上每個接收器的時間。根據(jù)彈性波在介質(zhì)和在空氣中不同的傳播速度來確定板內(nèi)空洞的位置具體問題：一塊240(米)×240(米)的平板ABCD，在AB邊等距地設(shè)置7個波源Pi(i=1,…,7),在CD邊等距地設(shè)置7個接收器Qj(j=1,…,7),記錄由Pi發(fā)出的彈性波到達Qj的時間tij(秒);

在AD邊等距地設(shè)置7個波源Ri(i=1,…,7),在BC邊等距地設(shè)置7個接收器Sj(j=1,…,7),記錄由Ri發(fā)出的彈性波到達Sj的時間τij(秒)。已知彈性波在介質(zhì)和空氣中的傳播速度分別為2880(米/秒)和320(米/秒),

且彈性波沿板邊緣的傳播速度與在介質(zhì)中的傳播速度相同P2Q4R3S6TP=(tij)tijQ1Q2Q3Q4Q5Q6Q7P1

.0611.0895.1996.2032.4181.4923.5646P2.0989.0592.4413.4318.4770.5242.3805P3.3052.4131.0598.4153.4156.3563.1919P4.3221.4453.4040.0738.1789.0740.2122P5.3490.4529.2263.1917.0839.1768.1810P6.3807.3177.2364.3064.2217.0939.1031P7.4311.3397.3566.1954.0760.0688.1042TR=(τij)τijS1S2S3S4S5S6S7R1

.0645.0602.0813.3516.3867.4314.5721R2.0753.0700.2852.4341.3491.4800.4980R3.3456.3205.0974.4093.4240.4540.3112R4.3655.3289.4247.1007.3249.2134.1017R5.3165.2509.3214.3256.0904.1874.2130R6.2749.3891.5895.3016.2058.0841.0706R7.4434.4919.3904.0786.0709.0914.0583要求：(1)確定該平面內(nèi)空洞的位置。(2)只根據(jù)Pi發(fā)出的彈性波到達Qj的時間tij

能確定空洞的位置嗎？討論在同樣能夠確定空洞位置的前提下，減少波源和接收器的方法。分析:彈性波沿平板邊緣的理論傳播時間

t=240/2880=0.0833(秒)

彈性波沿平板邊緣的實際傳播時間

t11=.0611,t77=.1042,

τ11=.0645,τ77=.0583

題目中已假設(shè)“彈性波沿板邊緣的傳播速度與在介質(zhì)中的傳播速度相同”觀測數(shù)據(jù)的最大絕對誤差為d=0.025秒.可以認(rèn)為，0.025*360=9(米）以下的空洞是探測不出的．假設(shè)1.觀測數(shù)據(jù)有測量誤差。觀測數(shù)據(jù)除測量誤差外是可靠的。2.

波在傳播過程中沿直線單向傳播，且不考慮波的反射、折射以及干涉等現(xiàn)象。3.空氣密度和介質(zhì)密度都均勻．4.“彈性波”在傳播過程中沒有能量損失。其波速僅與介質(zhì)有關(guān)，且在同一均勻介質(zhì)中波速不變。彈性波沿板邊緣的傳播速度與在介質(zhì)中的傳播速度相同。5.假設(shè)平板可劃分化為網(wǎng)格，空洞定位于每個網(wǎng)格單元內(nèi),空洞大小大致相同.波線與網(wǎng)格交線長度的計算

(k,l)記波源Pi與接收器Qj

決定的波線與每個單元（k，l）的交線長度為bijkl

i=j

時123456654321波線與網(wǎng)格交線長度的計算

PiQj

決定的直線方程：

(j-i）y=6(x-40(i-1))

i=j

以外的情況單元(k,l)左邊緣直線方程

x=40(k-1)波線與單元(k,l)左邊緣對應(yīng)交點的y坐標(biāo)為

y1ijkl=240(k-i)/(j-i)，其中l(wèi)-1≤6(k-i)/(j-i)≤l

(k,l)波線與網(wǎng)格交線長度的計算

PiQj

決定的直線方程：

(j-i）y=6(x-40(i-1))

i=j

以外的情況單元(k,l)右邊緣直線方程

x=40k波線與單元(k,l)右邊緣對應(yīng)交點的y坐標(biāo)為

y2ijkl=240(k+1-i)/(j-i)，其中l(wèi)-1≤6(k+1-i)/(j-i)≤l

(k,l)波線與網(wǎng)格交線長度的計算

PiQj

決定的直線方程：

(j-i）y=6(x-40(i-1))

i=j

以外的情況單元(k,l)下邊緣直線方程

y=40(l-1)波線與單元(k,l)下邊緣對應(yīng)交點的y坐標(biāo)為