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

數(shù)學建模競賽中的部分問題描述0（題數(shù)學建模競賽中的部分問題描述0（題(i1,2,,6)0優(yōu)化問題

2.1一個飛行管理問題

2.1.1

1995年全國大學生數(shù)學建模競賽中的A題（“一個飛行管理問題”）。在約10000米高空的某邊長為160km的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機做水平飛行，區(qū)域內(nèi)每架飛機的位置和速度向量均由計算機記錄其數(shù)據(jù)，以便進行飛行管理，當一架欲進入該區(qū)域的飛機到達區(qū)域邊緣時，記錄其數(shù)據(jù)后，要立即計算并判斷是否會與區(qū)域內(nèi)的飛機發(fā)生碰撞?，F(xiàn)假定條件如下：（1）不碰撞的標準為任意兩架飛機的距離大于8km；（2）飛機飛行方向角調(diào)整幅度不應(yīng)超過30°；（3）所有飛機飛行速度均為800km／h；（4）進入該區(qū)域的飛機在到達該區(qū)域邊緣時，與區(qū)域內(nèi)飛機的距離應(yīng)在60km以上；（5）最多需考慮6架飛機；（6）不必考慮飛機離開此區(qū)域后的情況。請你對這個避免碰撞的飛行管理問題家里數(shù)學模型，列出計算步驟，對以下數(shù)據(jù)進行計算（方向角誤差不超過0.01°），要求飛機飛行方向角調(diào)整的幅度盡量小。該區(qū)域四個定點的坐標為（0，0）、（160，0）、（160，160）、（0，160）。記錄數(shù)據(jù)見表2－1。表2－1飛機位置和方向角記錄數(shù)據(jù)飛機橫坐縱坐方向角飛機橫坐縱坐方向角／編號標標（°）編號標x標y（°）11501402434145501592858523651301502303155155220．5新進0052入說明：方向角指飛行方向與x軸正向的夾角。試根據(jù)實際應(yīng)用背景對你的模型進行評價和推廣。

2．1．2模型一及求解

模型建立這個問題顯然是一個優(yōu)化問題。設(shè)第i架飛機在調(diào)整時的方向角為i目中已給出），調(diào)整后的方向角為，題目中就是要iii求飛機飛行方向角調(diào)整的幅度盡量小，因此有化的目的函數(shù)可以是：

||2..v（＝800km／h），以當前時刻為

(x0,y0)，則Ttir(t)，這時在區(qū)域內(nèi)飛機不相撞的約束條件就變成了（5）||2..v（＝800km／h），以當前時刻為

(x0,y0)，則Ttir(t)，這時在區(qū)域內(nèi)飛機不相撞的約束條件就變成了（5）（6）

ijij2ijij22（1）（2）（3）（7）（8）（9）ii1為了建立這個問題的優(yōu)化模型，只需要明確約束條件就可以了。一個簡單的約束是飛機飛行方向角調(diào)整的幅度不應(yīng)超過30°，即

||30題目中要求進入該區(qū)域的飛機在到達該區(qū)域邊緣時，與區(qū)域內(nèi)的飛機的距離應(yīng)在60km以上。這個條件是個初始條件，很容易驗證目前所給的數(shù)據(jù)是滿足的，因此本模型中可以不予考慮。剩下的關(guān)鍵是要慢足題目中描述的任意兩架位于該區(qū)域內(nèi)的飛機的距離應(yīng)該大于8km。但這個問題的難點在于飛機是動態(tài)的，這個約束不好直接描述，為此我們首先需要描述每架飛機的飛行軌跡。

記飛機飛行速率為0時刻。設(shè)第i架飛機在調(diào)整時的位置坐標為（已知條件），t時刻的位置坐標為ii

(xt,yt)ii

xtx0vtcos,yty0vtsin.iiiiii如果要嚴格表示兩架位于該區(qū)域內(nèi)的飛機的距離應(yīng)大于8km，則需要考慮每架飛機在區(qū)域內(nèi)的飛行時間的長度。記為第架飛機飛出區(qū)域i的時間，即

Targmin{t0:x0vtcos0或160，（4）iii或y0vtsin0或160｝ii

記時刻第架飛機與第架飛機的距離為，并記ij

f(t)[r(t)]264ijij

f(t)[r(t)]2640(0tT)ijijij其中

Tmin{T,T}.ijij此外，經(jīng)過計算可以得到

f(t)(x0vtcosx0vtcos)2ijiijj(y0vtsiny0vtsin)264z2bzciijjijijij

z2vtsin,ij

b2[(x0x0)sin(y0y0)cos],ijijij

（10）f(t)zijijijij。注意到）則此時約束條件（5）一定成立，所以0ijij（11）0ijijijijijijij（12）f(t)6（14）（10）f(t)zijijijij。注意到）則此時約束條件（5）一定成立，所以0ijij（11）0ijijijijijijij（12）f(t)6（14）（15）（16）b/2,tb/4vsintf(t)且t，只要在右端點的函數(shù)值非負即可，即t*Tf(t)f(t)b/4c0||2;即（記為）時，函數(shù)取最小值2*，只需要的最小值（13）ij*T*ijijij

所以是一個關(guān)于的二次函數(shù)，表示的是一條開口向上的拋物線。ij

當ij

b/4cf(0)c0（初始時刻不相撞），如果b/20（即ijijijijij

b0ij如果bij

f(T)0;ijij如果b且0ij即可，即

b24c0.ijij

實際上，約束（11）表示的是在右端點的函數(shù)值非負，這個約ij束在（12）的條件下也是自然成立的，所以可以是對約束（11）不再附加且的條件。于是我們的模型就是

minii1

s.t.||230,i

f(T)0;ijij

b24c0.(b0,0t*T)ijijijijij

模型求解

上面這是一個非線性規(guī)劃模型，雖然是嚴格滿足題目要求的模型，但得到的模型邏輯關(guān)系比較復(fù)雜，約束（16）是在一定條件下才成立的約束，而且其中的計算式（4）也含有相當復(fù)雜的關(guān)系式，使用LINGO軟件不太容易將模型很方便的輸入，因為邏輯處理不是LINGO的優(yōu)勢所在。即使想辦法把這個模型輸入到LINGO，也不一定能求出好的解（筆者嘗試過，但是LINGO運行時有時會出現(xiàn)系統(tǒng)內(nèi)部錯誤，可能是系統(tǒng)有問題，無法繼續(xù)求解）。而且，在實時飛行調(diào)度中顯然需要快速求解，所以下面

1602/8000.21602/8000.220.283(h)T2，任何一架飛機在所考慮的區(qū)域內(nèi)這個模型麻煩之處就在于，要求嚴格表示兩架飛機的飛行距離應(yīng)大于8km，所以需要考慮每架飛機在區(qū)域內(nèi)的飛行時間的長度，比較繁瑣。

注意到區(qū)域?qū)蔷€的長度只有

停留的時間不會超過Tmax160。因此這里我們簡化一下問題；不再單獨考慮每架飛機在區(qū)域內(nèi)停留的時間，而是以最大時間T（這是已經(jīng)是一個常數(shù)）代替之，此時所有T，這實際maxijmax上強化了問題的要求，即考慮了有些飛機可能已經(jīng)飛出區(qū)域，但仍不允許兩架飛機的距離小于8km。

程序：

MODEL:TITLE飛行管理問題的非線性規(guī)劃模型;SETS:Plane/1..6/:x0,y0,cita0,cita1,d_cita;!cita0表示初始角度，cita1為調(diào)整后的角度,d_cita為調(diào)整的角度;link(plane,plane)|&1#LT#&2:b,c;ENDSETSDATA:x0y0cita0=1501402438585236150155220.5145501591301502300052;max_cita=30;T_max=0.283;V=800;ENDDATAINIT:d_cita=000000;ENDINIT@for(plane:cita1-cita0=d_cita);@for(link(i,j):b(i,j)=-2*(x0(i)-x0(j))*@sin((cita1(i)+cita1(j))*3.14159265/360)+2*(y0(i)-y0(j))*@cos((cita1(i)+cita1(j))*3.14159265/360);c(i,j)=(x0(i)-x0(j))^2+(y0(i)-y0(j))^2-64;);!避免碰撞的條件;

i66|

i66||||2@for(link(i,j):[Right](2*V*T_max*@sin((cita1(i)-cita1(j))*3.14159265/360))^2+b(i,j)*(2*V*T_max*@sin((cita1(i)-cita1(j))*3.14159265/360))+c(i,j)>0);!最小點非負;@for(link(i,j):[Minimum]@if(b(i,j)#lt#0#and#

-b(i,j)/4/V/@sin((cita1(i)-cita1(j))*3.14159265/360)#gt#0#and#

-b(i,j)/4/V/@sin((cita1(i)-cita1(j))*3.14159265/360)#lt#T_max,b(i,j)^2-4*c(i,j),-1)<0);!@for(link(i,j):@if(b(i,j)#lt#0,b(i,j)^2-4*c(i,j),-1)<0);@for(link:@free(b));!調(diào)整角度上下限，單位為角度;@for(plane:@bnd(-max_cita,d_cita,max_cita));[obj]MIN=@SUM(plane:(d_cita)^2);![obj]MIN=@SUM(plane:@abs(d_cita));END

運行這個程序，結(jié)果得到的是一個局部極小點，調(diào)整角度較大。能找到更好的解嗎？如果不用全局求解程序，通常很難得到稍大規(guī)模的非線性規(guī)劃問題的全局最優(yōu)解。所以我們啟動LINGO全局求解程序求解這個模型（過程省略），可以得到全局最優(yōu)解?？梢钥闯?，在0。01度的誤差要求下，需要調(diào)整第3、4、6三架飛機的角度，分別調(diào)整2.06度，－0.5度,1.57度，調(diào)整量的平方和為6.95。其實，使用全局變量求解程序，通常也不一定要等到全局最優(yōu)解，而是觀察求解狀態(tài)窗口，看到一個較好的當前解（或當前最好解在較長時間內(nèi)不發(fā)生變化）時，就可以中止程序，用當前最好的局部最優(yōu)解作為最后結(jié)果。例如對于本例，LINGO求出最優(yōu)解大約需要一分，而實際上5秒內(nèi)LINGO得到了與全局最優(yōu)解類似的解。此外，上面的模型還可以進一步簡化，例如可以假設(shè)要求飛機永遠不相撞，即認為為無窮大，這時顯然約束條件（15）是多余的，而且約束（16）中只需要的條件就可以了。也就是說上面程序中的對應(yīng)部分（約束和可以改寫為更簡單的形式：！右端點非負，不再需要；！最小點非負，需化為以下形式：實際計算結(jié)果顯示，此時得到的結(jié)果與前面計算的結(jié)果幾乎沒有差別。

備注：優(yōu)化的目標函數(shù)除了外，也可以假定為或iii1i1

max||等，用LINGO求解的過程的是完全類似的，計算結(jié)果略有差異，1i6

AAA2S,S,S2Ssp1800160≤30020501～600371572800155301～35023601～7004431000155351～40026701～8005042000160401～45029801～900AAA2S,S,S2Ssp1800160≤30020501～600371572800155301～35023601～7004431000155351～40026701～8005042000160401～45029801～9005552000155451～50032901～1000606200015073000160機的數(shù)量盡量少，這種想法在實際中也不能說沒有道理，但與題目的要求不符，而且解題難度并沒有減小，意義似乎不大。在實際調(diào)度中，由于計算上面的調(diào)度方案，需要時間將調(diào)度信息告知飛機駕駛員并做出調(diào)整方向角的操作也需要時間，因此如果考慮一定的反應(yīng)滯后時間應(yīng)該是比較合理的。也就是說，如果反應(yīng)時間是10秒，則計算中應(yīng)采用飛機沿當前方向角飛行10秒以后的位置作為計算的基礎(chǔ)。2.2鋼管訂購和運輸

2.2.1問題描述

要鋪設(shè)一條的輸送天然氣的主管道,如圖一所1示(見下頁)。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有。圖1中粗線表示鐵路，單細線表示公路，雙細線表示要鋪設(shè)的管道(假設(shè)沿管道或者原來有公路，或者建有施工公路)，圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯數(shù)字表示里程(單位km)。為方便計，1km主管道鋼管稱為1單位鋼管。一個鋼廠如果承擔制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠i在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個單位，鋼管出廠銷價1單i位鋼管為萬元，如下表：i

i

si

pi

1單位鋼管的鐵路運價如下表：

里程(km)運價(萬元)

里程(km)運價(萬元)

1000km以上每增加1至100km運價增加5萬元。公路運輸費用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計算）。

A,A,230S46903070170520462S14803151080750A2,A15S7160S611088S57042A910194A6606A4301，而32070A156210A1310A10201205A5A316020500420220300A8A7A,A,230S46903070170520462S14803151080750A2,A15S7160S611088S57042A910194A6606A4301，而32070A156210A1310A10201205A5A316020500420220300A8A7圖一20A14210A12A116801是管道全線）。（1）請制定一個主管道鋼管的訂購和運輸計劃，使總費用最小（給出總費用)。（2）請就（1）的模型分析：哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運計劃和總費用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。（3）如果要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。

290

S3S2

6901200720

202

110020121953061150

600450

23104

A1

17S1480A113168051080

750

301A3A2A,A,,A2S,S,7（記為j=1，2，??，15）的每單位鋼管的最小運費Cij（不21601001308846242A910194A6

415S1532070190S517S1480A113168051080

750

301A3A2A,A,,A2S,S,7（記為j=1，2，??，15）的每單位鋼管的最小運費Cij（不21601001308846242A910194A6

415S1532070190S57010300201205

606（記為i=1，2，??，7）到每個結(jié)點160A20260(AA191010A8A7

A5703021)11062A13210220圖二20S6A15500420A1220A14S4S3S2

6901200720A1620211002012195306

1150

600450

23

104

A1

2.2.2運費矩陣的計算模型

問題分析

我們只考慮本題第一問的求解。首先，所有鋼管必須要運到天然氣

主管道鋪設(shè)線路上的結(jié)點，然后才能向左或向右鋪設(shè)。因此，1必須求出從每個鋼管廠12

A,A,,A1妨稱為運費矩陣）及其對應(yīng)的運輸方式和路線。因為題目中沒有給出裝卸成本，我們簡單地假設(shè)總是采用最經(jīng)濟的運輸方式，雖然這個假設(shè)在實際中可能不太接近事實。也就是說，在運輸過程中需要多次裝卸也是允許的（如鐵路轉(zhuǎn)公路，再轉(zhuǎn)鐵路，等等）。自然的想法是運輸路線應(yīng)該是走最短路徑，但由于有兩種運輸和計價方式（鐵路和公路），公路運輸費用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計算），運費是路程的線性函數(shù)；然而，鐵路運輸要通過運輸里程查表得到，是一個階梯函數(shù)，這兩種運輸計價方式混合在一起，使得我們不能直接在整個鐵路、公路混合的運輸網(wǎng)絡(luò)上計算最短路徑作為運輸路線，但可以分別在鐵路、公路網(wǎng)上計算最短路徑，然后換

dc10,

(k1)(k)ijij(kdc10,

(k1)(k)ijij(k)時的最短距離；自然u就是i，j之間的最短1d1iiu(1)

minu,uikkj可以看成任意兩個接點i，j之間(n1)22，然后按照這個最w,ij,ijij(k)(k)uj,k1,2,?,i,n.求一次最短路問題，就可以把它們統(tǒng)一成一個標準的運費矩陣。

鐵路子網(wǎng)絡(luò)

假設(shè)鐵路運輸路線應(yīng)該是走最短路徑，而且采用連續(xù)路徑計價方式

一定優(yōu)于分段計價方式（其實題中數(shù)據(jù)并不符合這一假定，例如題中650km的運價計為44萬元，而分成300km和350km兩段計價只需要43萬元，這種情況應(yīng)該是不太符合實際的，可能是命題時選擇數(shù)據(jù)的疏忽，我們不過多地考慮這種情況）。這時我們可以把鐵路運輸子網(wǎng)獨立出來，

在這個網(wǎng)絡(luò)上計算任意兩個節(jié)點i，j之間的最短路ij短路長度查鐵路運價表得到最小運費。ij在無向網(wǎng)絡(luò)上求任意兩點之間最短路的算法很多，尤其對本題這種弧上的權(quán)（距離）全為正數(shù)的情況，存在相對比較簡單的算法。例如，求任意兩點之間最段路徑的Floyd-Warshall算法是

u(1)

u

這實際上是一種標號算法，其中n是網(wǎng)絡(luò)中的節(jié)點數(shù)（節(jié)點編號為1，

2，??，n）；w是給定的網(wǎng)絡(luò)上相鄰接點i，j之間的直接距離（i，jij

不相鄰時取w充分大就可以了）；uijij距離的中間迭代值（或稱為臨時編號），既成節(jié)點i到j(luò)但不允許經(jīng)過其

他節(jié)點k，k+1，??，nij距離（或稱為永久標號），即d。ij公路子網(wǎng)絡(luò)

類似地，可以假設(shè)公路運輸路線應(yīng)該是走最短路徑，把公路運輸子網(wǎng)獨立出來，在這個網(wǎng)絡(luò)上計算任意兩個節(jié)點i，j之間的最短路長度，

然后按照這個最短路長度乘以0.1得到最小費用c（因為公路運輸費ijij用為1單位鋼管每公里0.1萬元）。

c1c1,S,7A,A,,A

cpsc1c1,S,7A,A,,A

cpsfxy(pc)x

y導致的運輸費：這部分費用是以0.1為首項、0.1為公差的等差15jjjjj122S1y(1z)z（記為i=1，2，??，7）到每個y

在次基礎(chǔ)上，就可以將以上兩個子網(wǎng)絡(luò)（需要分別看成兩個完全子

圖）組合成一個網(wǎng)絡(luò)每條弧上相應(yīng)的運費或c為權(quán)（如果某條弧（i，ijijj上既有鐵路運費，又有公路運費c，只需要取其中較小的一個即可）。ijij此時，再計算從每個鋼管廠S12節(jié)點（記為j=1，2，??，15）的最短路，得到的就是每個1215單位鋼管的最小運費。ij算法仍然可以采用Floyd-Warshall算法。

2.2.3運輸量的計算模型及求解

記第i個鋼廠的采購費用為，最大供應(yīng)量為，最小供應(yīng)量為500，ii從第i個鋼廠到鋪設(shè)節(jié)點j的運輸費用為c；用b表示管道第j段需要ijj鋪設(shè)的鋼管量。這些已經(jīng)是已知的（或已經(jīng)求得的）。

決策變量：用表示鋼廠i是否使用；是從鋼廠i運到節(jié)點j的iij鋼管量；是從節(jié)點j向左鋪設(shè)的鋼管量；z是從節(jié)點j向右鋪設(shè)的鋼jj管量。目標函數(shù)：目標函數(shù)應(yīng)該包括兩部分費用。（1）從第i個鋼廠采購鋼管并將鋼管運到鋪設(shè)節(jié)點j的運費費用，對所有i，j求和，即

iijiji,j（2）從鋪設(shè)節(jié)點j向左鋪設(shè)的鋼管量和從節(jié)點j向右鋪設(shè)的鋼管量j

zj級數(shù)，所以對所有j求和，可得這部分費用為

0.12

約束條件是比較明顯的，所以下面直接給出本題第一問求運輸量的

2

7AAyyxyz問題描述0.115

xyz,j1,2,?15,(2)152

7AAyyxyz問題描述0.115

xyz,j1,2,?15,(2)15;yiijijjjjji,jj1s.t.

500fxsf,i1,2,?7,(1)iijiij1模型如下：ijjji=1yzb,j1,2,?14,(3)j+1jjyz0,(4)115f0,1,i1,2,?7.(5)i約束（1）表示每個鋼廠的生產(chǎn)總量限制（不低于500t，也不超過總能力限制），約束（2）表示運輸?shù)矫總€輔助節(jié)點的鋼管數(shù)量剛好等于從這個節(jié)點向左和向右鋪設(shè)的鋼管的鋼管數(shù)量；約束（3）表示每一段管道上鋪設(shè)的鋼管數(shù)量正好等于前一個節(jié)點向右、后一個節(jié)點向左鋪設(shè)的

鋼管數(shù)量之和；約束（4）是對端點和的自然限制；約束（5）表示115是否使用某個鋼廠的0-1限制。這是一個二次規(guī)劃模型。有些讀者可能已經(jīng)注意到，由于題目中說

明運輸不足整數(shù)公里需要按照整數(shù)公里計算，所以上面費用中的第二項

只有當，z為整數(shù)時才是精確成立，否則只能看成是一種近似。不過，jj由于題目中所給的距離都是整數(shù)，所以雖然上面的模型中最優(yōu)解未必一

定是整數(shù)，但這個問題必然存在，z為整數(shù)的解（自然，此時也是jjij整數(shù)），因此我們只需要在模型中再加上（或）為整數(shù)的限制就完全jj沒有問題了。這樣的性質(zhì)通常為“占優(yōu)”性質(zhì)，在優(yōu)化建模中利用這種性質(zhì)有時是非常方便的。

2.3露天礦生產(chǎn)的車輛安排

2.3.1

2003高教社杯全國大學生數(shù)學建模競賽題目B題露天礦生產(chǎn)的車輛安排鋼鐵工業(yè)是國家工業(yè)的基礎(chǔ)之一，鐵礦是鋼鐵工業(yè)的主要原料基地。許多現(xiàn)代化鐵礦是露天開采的，它的生產(chǎn)主要是由電動鏟車（以下簡稱電鏟）裝車、電動輪自卸卡車（以下簡稱卡車）運輸來完成。提高這些大型設(shè)備的利用率是增加露天礦經(jīng)濟效益的首要任務(wù)。

露天礦里有若干個爆破生成的石料堆，每堆稱為一個鏟位，每個鏟位已預(yù)先根據(jù)鐵含量將石料分成礦石和巖石。一般來說，平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多能安置一臺電鏟，電鏟的平均裝車時間為5分鐘。卸貨地點（以下簡稱卸點）有卸礦石的礦石漏、2個鐵路倒裝場（以下簡稱倒裝場）和卸巖石的巖石漏、巖場等，每個卸點都有各自的產(chǎn)量要求。從保護國家資源的角度及礦山的經(jīng)濟效益考慮，應(yīng)該盡量把礦石按礦石卸點需要的鐵含量（假設(shè)要求都為29.5%1%，稱為品位限制）搭配起來送到卸點，搭配的量在一個班次（8小時）內(nèi)滿足品位限制即可。從長遠看，卸點可以移動，但一個班次內(nèi)不變?？ㄜ嚨钠骄盾嚂r間為3分鐘。所用卡車載重量為154噸，平均時速28?？ㄜ嚨暮挠土亢艽螅總€班次每臺車消耗近1噸柴油發(fā)動機點火時需要消耗相當多的電瓶能量，故一個班次中只在開始工作時點火一次?？ㄜ囋诘却龝r所耗費的能量也是相當可觀的，原則上在安排時不應(yīng)發(fā)生卡車等待的情況。電鏟和卸點都不能同時為兩輛及兩輛以上卡車服務(wù)?？ㄜ嚸看味际菨M載運輸。每個鏟位到每個卸點的道路都是專用的寬60的雙向車道，不會出現(xiàn)堵車現(xiàn)象，每段道路的里程都是已知的。一個班次的生產(chǎn)計劃應(yīng)該包含以下內(nèi)容：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次（因為隨機因素影響，裝卸時間與運輸時間都不精確，所以排時計劃無效，只求出各條路線上的卡車數(shù)及安排即可）。一個合格的計劃要在卡車不等待條件下滿足產(chǎn)量和質(zhì)量（品位）要求，而一個好的計劃還應(yīng)該考慮下面兩條原則之一：1.總運量（噸公里）最小，同時出動最少的卡車，從而運輸成本最??；2.利用現(xiàn)有車輛運輸，獲得最大的產(chǎn)量（巖石產(chǎn)量優(yōu)先；在產(chǎn)量相同的情況下，取總運量最小的解）。請你就兩條原則分別建立數(shù)學模型，并給出一個班次生產(chǎn)計劃的快速算法。針對下面的實例，給出具體的生產(chǎn)計劃、相應(yīng)的總運量及巖石和礦石產(chǎn)量。某露天礦有鏟位10個，卸點5個，現(xiàn)有鏟車7臺，卡車20輛。各卸點一個班次的產(chǎn)量要求：礦石漏1.2萬噸、倒裝場Ⅰ1.3萬噸、倒裝場Ⅱ1.3萬噸、巖石漏1.9萬噸、巖場1.3萬噸。鏟位和卸點位置的二維示意圖如下，各鏟位和各卸點之間的距離（公里）如下表：鏟位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ù)量(萬噸)和礦石的平均鐵含量如下表：

0．951．051．001．051．101．251．051．301．351．251．251．101．351．051．150．951．051．001．051．101．251．051．301．351．251．251．101．351．051．151．351．051．151．351．2530%28%29%32%31%33%32%31%33%31%C7礦石量巖石量鐵含量

2.3.2運輸計劃模型及求解

問題分析

于2.2節(jié)的問題類似，本題也可以看成是經(jīng)典運輸問題的一種變形和擴展，它與典型的運輸問題明顯有以下不同：（1）這是運輸?shù)V石與巖石兩種物資的問題；（2）屬于產(chǎn)量大于銷量的不平衡運輸問題；（3）為了完成品位約束，礦石要搭配運輸；（4）產(chǎn)地、銷地均有單位時間的流量限制；（5）運輸車輛只有一種，每次都是滿載運輸，154t/車次；（6）鏟位數(shù)多于鏟車數(shù)意味著最優(yōu)的選擇不多于7個產(chǎn)地作為最后結(jié)果的產(chǎn)地（7）最后求出各條路線上的派出車輛數(shù)及安排每個運輸問題對應(yīng)著一個線形規(guī)劃問題，以上不同點對它的影響不同，（1）（2）（3）（4）條可通過變量的設(shè)計、調(diào)整約束條件實現(xiàn)；（5）條是整數(shù)要求將使其變?yōu)檎麛?shù)線形規(guī)劃；（6）條不容易用線形模型實現(xiàn)，一種簡單的辦法是從=120個整數(shù)規(guī)劃中取最優(yōu)的即得到最佳物流；10為完成（7）條，由最佳物流算出各條路線上的最少派車數(shù)（整數(shù)）再給出具體安排即完成全部計算。然而這是個實際問題，為了及時指揮生產(chǎn)，題中要求算法是快速算法，而整數(shù)規(guī)劃的本質(zhì)是NPC問題，僅就20min內(nèi)計算含50個變量的整數(shù)規(guī)劃來說就不一定辦得到。從另一個角度看，這是一個二層規(guī)劃問題，第二層規(guī)劃是組合優(yōu)化，如果求最優(yōu)解計算量較大，現(xiàn)成的各種算法都無能為力。于是問題變?yōu)檎乙粋€尋求近優(yōu)解的近似解法，例如可用啟發(fā)式方法求解。

調(diào)用120次整數(shù)規(guī)劃可用三種方法避免：1先不考慮電鏟數(shù)量約束運行整數(shù)規(guī)劃，再對解中運量最少的幾個鏟位進行篩選；2在整數(shù)線形規(guī)劃的鏟車約束中調(diào)用sign函數(shù)來實現(xiàn)；3增加10個1-0個變量了來標志各個鏟位是否有產(chǎn)量。從每個運輸問題都有目標函數(shù)的角度看，這又是一個多目標規(guī)劃問題，第一問的主要目標有：1重載路程最??；2總路程最??；3出動卡車數(shù)最少。仔細分析可得：1和2在第一層，3在第二層；1與2基本等價，于是只用1于第一層，對其結(jié)果在第二層中派最少的卡車，實現(xiàn)全局目標生產(chǎn)成本最小。第二問的主要目標有：4巖石產(chǎn)量最大；5礦石產(chǎn)量最大；6運量最小。三者之間的關(guān)系根據(jù)應(yīng)該理解為字典序。合理的假設(shè)主要有：（1）卡車在一個班次中不應(yīng)發(fā)生等待或熄火再啟動的情況（2）在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認為只要平均時間能完成任務(wù)，就認為不沖突。不進行具體排時方面的討論（3）空載與重載的速度都是28km/h，耗油相差卻很大（4）卡車可提前退出系統(tǒng)，等等

模型建立

我們將只考慮本題第一問（求運輸量）的模型。首先定義如下數(shù)學符號：Xij為i號鏟位到j(luò)號卸點路線上運行一個周期平均所需要時間（min）；Aij為從i號鏟位到j(luò)號卸點最多能同時運行的卡車數(shù)（輛）；Bij為從i號鏟位到j(luò)號卸點路線上一輛車最多可以運行的次數(shù)（次）；Pi為i號鏟位的礦石鐵含量（%）；P=（3028293231332323331）；qj為i號卸點任務(wù)需要（t）；q=（1.2，1.3，1.3，1.9，1.3）*10000。CKi為i號鏟位的鐵礦石儲量（萬t）；CYi為i號鏟位的巖石儲量（萬t）；fi為描述第i號鏟位是否使用的0-1開關(guān)變量，取1為使用，取0為關(guān)閉。目標函數(shù)與約束條件的分析；（1）目標函數(shù)取為重載運輸時的運量（.t.km）最?。ㄒ騒ij代表整數(shù)車次數(shù)，乘154后等于運量；再乘以運輸距離等于噸公里）。（2）道路能力約束；由于一個電鏟（卸點）不能同時為兩輛卡車服務(wù)，所以一條路線上最多能同時運行的卡車數(shù)是有限的，卡車在i號鏟位到j(luò)號卸點路線上運行一個周期平均所需的時間為T=（i到j(luò)距離*2/平均速度）+3+5（min）由于裝車時間5min大于卸車時間3min，所以可分析出這條路線上在卡車不等待條件下最多能同時運行的卡車數(shù)為：Aij=[Tij/5]。同樣可分析每輛卡車一個班次中在這條路線上最多可以運行的次數(shù)為Bij=[8*60-（Aij-1）*5]/Tij，其中（Aij-1）*5是開始裝車時最后一輛車的延時時間。則一個班次中這條固定路線上最多可能運行的總車次大約為：Lij=Aij*Bij。（3）電鏟能力約束：還是因為一臺電鏟不能同時為兩輛卡車服務(wù)，所以一臺電鏟早一個班次中的最大可能產(chǎn)量為：8*60/5

1545

10

10

1545

10

10

10

10

10

xij

ij

T105xf*8*60/5,i1,2,…，10，

x8*20,j1,2,

xq/154,j1,2,，

x*(p30.5)0,j1,2,

x*(p28.5)0,

f7,

20,

ij5（4）卸點能力約束：卸點的最大吞吐量為每小時60/3=20車次。于是一個卸點在一個班次中的最大可能產(chǎn)量為：8*20車（5）鏟位儲量約束：鏟位的礦石和巖石產(chǎn)量都不能超過相應(yīng)儲藏量（6）產(chǎn)量任務(wù)約束：各卸點的產(chǎn)量大于等于該卸點的任務(wù)要求（7）鐵含量約束：各礦石卸點的平均品位要求都在指定的范圍內(nèi)（8）電鏟數(shù)量約束：電鏟數(shù)量約束無法用普通不等式表達，但算法運行時間增加了，也可以用其他方法解決該問題（9）卡車數(shù)量約束：卡車總數(shù)不超過20輛（10）整數(shù)約束：當把問題作為整數(shù)規(guī)劃模型時，車流量Xij為非負整數(shù)這樣，我們可以得到的各種模型之一為：

minxc,ijiji1j1s.t.xAB,i1,2,…，10，j1,2,?，5，ijijijijij1iji1xxxck*10000/154,i1,2,…，10，i1i2i5ixxcy*10000/154,i3i4iijji1ijii1ijii1ii1

i,f0,1;x為整數(shù)，i1,2,?，10，j1,2,?，5.iij其中，Ti到j(luò)距離*2/平均速度3（5min），ij

A,B8*60(A1)*5/T近似）ij=ijijij

空洞探測PQPQt

i

PQtQjPiij0.05920.41310.44530.4529空洞探測PQPQt

i

PQtQjPiij0.05920.41310.44530.45290.31770.3397jijCBQ20.08950.44130.05980.40400.22630.23640.3566Q30.19960.43180.41530.07380.19170.30640.1954Q40.20320.47700.41560.17890.08390.22170.0760Q50.41810.52420.35630.07400.17680.09390.0688Q60.49230.38050.19190.21220.18100.10310.1042Q70.5646

2.4.1問題描述

山體、隧洞、壩體等的某些內(nèi)部結(jié)構(gòu)可用彈性波測量來確定。一個簡化問題可描述為，一塊均勻介質(zhì)構(gòu)成的矩形平板內(nèi)有一些充滿空氣的空洞，在平板的兩個鄰邊分別等距地設(shè)置若干波源，在它們的對邊對等地安放同樣多的接收器，記錄彈性波由每個波源到達對邊上每個接收器的時間，根據(jù)彈性波在介質(zhì)中和在空氣中不同的傳播速度，來確定板內(nèi)空洞的位置。現(xiàn)考察如下的具體問題：一塊240（米）×240（米）的平板（如圖），在AB邊等距地設(shè)置7個波源(i=1,?,7)，CD邊對等地安放7個接收器(j=1,?,7)，記錄由發(fā)出的彈性波到達i的時間(秒);在AD邊等距地設(shè)置j7個波源R(ii=1,?,7)，BC邊對等地安放j7ij個接收器S(j=1,?,7)，記錄由R發(fā)出的彈性波到達iS的時間τ(秒)。已知彈性波在介質(zhì)和空氣中的傳j播速度分別為2880（米j/秒）和ij320（米/秒），且彈性波沿板邊緣的傳播速度與在介質(zhì)中的傳播速度相同。1）確定該平板內(nèi)空洞的位置。2）只根據(jù)由發(fā)出的彈性波到達的時間(i,j=1,?,7)，能確定空洞的位置嗎；討論在同樣能夠確定空洞位置的前提下，減少波源和i

D

Ri

Sj

A接受器的方法。

tQ1P0.0611P10.0989P20.3052P30.3221P40.3490P50.3807P670.4311

ij0.07530.34560.36550.31650.27490.443440m40m的正方形平板被均勻地分成個小正方形單元，每個，k,l6xxS0.064510.07000.32050.32890.24090.3891ij0.07530.34560.36550.31650.27490.443440m40m的正方形平板被均勻地分成個小正方形單元，每個，k,l6xxS0.064510.07000.32050.32890.24090.38910.4919例S0.060220.28520.09740.42470.32140.58950.3904如S0.081330.43410.40930.10070.32560.30160.0786單S0.351640.34910.42400.32490.09040.20580.0709元S0.386750.48000.45400.21340.18740.08410.0914（S0.431460.49800.31120.10170.21300.07060.0583k,lS0.57217）表示由點（40RR1R2R3R4R5R67

2．4.2優(yōu)化模型及求解

問題分析

這道題目有多種解法。測量問題一般是隨機性問題，我們把這個問題看成是確定性問題來解。雖然平板上空洞的大小和形狀可以是任意的，我們這里把它簡化成的正方形（可以成為單元），即240m240m6636小正方形或者全是空洞，此外，在以下假設(shè)下考慮這個問題的解法：（1）觀測數(shù)據(jù)有測量誤差，觀測數(shù)據(jù)除測量誤差外是可靠的。（2）波在傳播過程中沿直線單向傳播，且不考慮波的反射，折射以及干涉等現(xiàn)象。（3）空氣和介質(zhì)都是均勻的。（4）“彈性波”在傳播過程中沒有能量損失，其波速僅與介質(zhì)有關(guān)，且在同一均勻介質(zhì)中波速不變。（5）假設(shè)平板可劃分為網(wǎng)絡(luò)，空洞定位于每個網(wǎng)格單元內(nèi)，空洞大小大致相同。（6）題中已經(jīng)假設(shè)彈性波沿板邊緣的傳播速度與在介質(zhì)中的傳播速度相同，此外，網(wǎng)格化以后，如果某條波線位于平板中兩個單元的邊緣（交線）上，我們假設(shè)這條波線的傳播是沿著每個單元各走一半的路程（或者換句話說，如果這兩個單元中一個是空洞，另一個是介質(zhì)，則波線沿這條交線的傳播速度是在空洞和介質(zhì)中傳播速度的平均值）。做這樣的網(wǎng)格化（離散化）以后，設(shè)一邊上的波源為m個（本題m=7個），另一邊上的波源為n個（本題n=7）,則得到(m-1)(n-1)個單元。

建立平面直角坐標系，設(shè)A點為原點，AB為x軸，AD為y軸，則C點坐標為（240，240），假設(shè)平板上每個單元是從左到右。從下到上編號的（k-1）,40(l-1)）,(40k,40(l-1),(40(k-1),40l),(40k,40l)圍成的小正方形單元，其中k,l的取值范圍是1。每個單元對應(yīng)一個決策

變量，表示該單元是否為空洞（1表示是，0表示否）。我們的任務(wù)是kl確定這36個0-1變量的取值。為此，首先需要計算每條波線與每個單kl元的交線的長度，這雖然可以使用任何軟件編程進行計算，但我們下面還是說明如何用LINGO進行計算。

Rk,l7QPQjQPRk,l7QPQjQPQ）Q240(ki)/(ji),其中l(wèi)16(ki)/(ji)l16(ki)/(ji)l40,如果kij1或k1ij7;20,y=6(x-40(i-1)).1如果kij或k1ij,且2k5l6

可以先考慮波源P與接受器Q決定的波線與每個單元（k,l）的交線，ij記其長度為b（對與S可以類似的考慮，或直接根據(jù)對稱性得到結(jié)果，ijklij我們將在后面再討論）。假設(shè)P與Q都是從左到右編號的，其中i,j的取ij值范圍是1，如P位于原點（0，0），Q位于（40，240），等等。12如果i=j，則波線P與y軸平行，此時只要不是平板上最左邊和最ij右邊的波線，波線都會位于兩個單元的邊緣（交線）上，根據(jù)上面ij的假設(shè)6，容易得出：

bijkl（43）

下面來考慮i的情況。

因為波源P的坐標是（40(i-1),0）,的坐標是（40（j-1）,240）,ij所以容易得到的直線方程為ij（j-i(44)這條直線P與每個單元（k,l）的邊緣最多只能有兩個交點，但交ij點有可能位于單元的不同的邊緣位置（每個單元有上，下，左，右四個邊緣位置）。雖然對于像本題這樣規(guī)模不太大的問題，可以通過枚舉法確定所有交點，但我們下面還是介紹能夠用于更大規(guī)模問題的一般解題方法。對于單元（k,l）的左邊緣，其對應(yīng)的直線方程為

x=40(k-1).(45)將（45）代入（44），可以得到波線與單元邊緣對應(yīng)交點的y坐標為

y1ijkl（46）式（46）條件l是為了保證這個交點是有效的，

即這個交點確實位于這個單元（k,l）所在的范圍內(nèi)。

(120i20(ij)(l1))(120i20(ij)(l1))/3k1)(120i20(ij)(l1))/340k06(ik)(ij)(l1)6，其中(120i20(ij)l)/340(k1)(120i20(ij)l1)/340k6(ik)(ij)l640l,其中06(ik)(ij)l6Q

PQj06(ik)(ij)(l1)6。

x40k(47)將（47）代入（44），可以得到對應(yīng)交點的y坐標為

y2240(k1i)/(ji),其中l(wèi)16(k1i)/(ji)lijkl（48）對應(yīng)單元（k,l）的下邊緣，其對應(yīng)的直線方程為

y40(l1)（49）將（49）代入（44），可以得到對應(yīng)交點的x的坐標為

x3ijkl（50）但（50）只有在40(時才是有效的，

這個條件化簡后就是，于是可以得到對應(yīng)交點

的y坐標為

y340(l1)ijkl（51）同理，對于單元（k,l）的上邊緣，其對應(yīng)的子癇方程為

y40l（52）將（52）代入（42），可以得到對應(yīng)交點的x的坐標為

x4ijkl（53）但是（53）只有在時才是有效

的，這個條件化簡后就是0，于是可以得到對應(yīng)的交

點的y坐標為

y4ijkl（54）至此，式（46），（48），（51），（54）給出了直線P與單元（k,l）ij的邊緣所有可能的交點的y坐標及其存在交點的條件，但事實上，這些條件