1、非 線 性 規(guī) 劃,非現(xiàn)性規(guī)劃的基本概念 定義 如果目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線性函數(shù)時(shí)的最優(yōu)化問(wèn)題就叫做非線性規(guī)劃問(wèn)題,一般形式: （1） 其中 ， 是定義在 En 上的實(shí)值函數(shù)，簡(jiǎn)記:,非 線 性 規(guī) 劃,定義1 把滿足問(wèn)題（1）中條件的解 稱為可行解（或可行點(diǎn)），所有可行點(diǎn)的集合稱為可行集（或可行域）記為D即 問(wèn)題(1)可簡(jiǎn)記為 ,非 線 性 規(guī) 劃,定義2 對(duì)于問(wèn)題(1)，設(shè) ，若存在 ,使得對(duì)一切 ，且 ，都有 ，則稱X*是f(X)在D上的局部極小值點(diǎn)（局部最優(yōu)解）特別地當(dāng) 時(shí)，若 ，則稱X*是f(X)在D上的嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最優(yōu)解）,非 線 性 規(guī) 劃,定義3 對(duì)

2、于問(wèn)題(1),設(shè) ,對(duì)任意的 ,都有 則稱X*是f(X)在D上的全局極小值點(diǎn)（全局最優(yōu)解）特別地當(dāng) 時(shí)，若 ，則稱X*是f(X)在D上的嚴(yán)格全局極小值點(diǎn)（嚴(yán)格全局最優(yōu)解）,非 線 性 規(guī) 劃,如何用LINGO軟件求解非線性規(guī)劃問(wèn)題？,非 線 性 規(guī) 劃,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20,非 線 性 規(guī) 劃,Lingo 程序 MIN=-2*X1-6*X2+X1*X1-2*X1*X2+2*X1*X1; X1+X2=2; -X1+2*X2=2;,非 線 性 規(guī) 劃,計(jì)算結(jié)果 Objective

3、value: -9.777778 X1 = 0.6666667 X2 = 1.333333,非 線 性 規(guī) 劃,練習(xí)題1,2x1+3x2 6 s.t x1+4x2 5 x1,x2 0,非 線 性 規(guī) 劃,例2,x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0,非 線 性 規(guī) 劃,Lingo程序 min=exp(x1)*(4*x1*x1+2*x2*x2+4*x1*x2+2*x2+1); x1+x2=0; 1.5+x1*x2-x1-x2=0; -x1*x2-10=0; free(x1); free(x2);,非 線 性 規(guī) 劃,計(jì)算結(jié)果 Objective

4、value: 5.276848 X1 = 1.224745 X2 = -1.224745,選 址 問(wèn) 題,某公司有6個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系a，b表示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個(gè)臨時(shí)料場(chǎng)位于A(5,1)，B(2,7)，日儲(chǔ)量各有20噸。假設(shè)從料場(chǎng)到工地之間均有直線道路相連。 （1）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場(chǎng)分別向各工地運(yùn)送多少噸水泥，使總的噸千米數(shù)最小。 （2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩個(gè)新的，日儲(chǔ)量各為20噸，問(wèn)應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？,Lingo 使用外部數(shù)據(jù),方法一 Copy Past

5、e 方法 方法二 FILE 輸入數(shù)據(jù)、TEXT輸出數(shù)據(jù)（文本文件） 方法三OLE函數(shù)與電子表格軟件EXCEL連接 方法四 ODBC函數(shù)與數(shù)據(jù)庫(kù)連接,FILE和TEXT：文本文件輸入輸出,使用格式 File(“filename”) 文件filename 是文本文件 每行以 結(jié)束 一次File(“filename”) 讀取一行紀(jì)錄,FILE和TEXT：文本文件輸入輸出,data: a=file(example3_3.ldt); b=file(example3_3.ldt); d=file(example3_3.ldt); e=file(example3_3.ldt); enddata init:

6、x,y=file(example3_3.ldt); endinit,1.25,8.75,0.5,5.75,3,7.25 1.25,0.75,4.75,5,6.5,7.75 3,5,4,7,6,11 20,20 5,1,2,7,Example3_3.ldt的格式,FILE和TEXT：文本文件輸入輸出,比較,a=1.25,8.75,0.5,5.75,3,7.25; b=1.25,0.75,4.75,5,6.5,7.75; d=3,5,4,7,6,11; e=20,20; x,y=5,1,2,7;,OLE ：與EXCEL連接,使用格式 OLE(“filename” ，range_name_list)

7、 filename 為電子表 文件名 , range_name_list 為數(shù)據(jù)的單元范圍。,OLE 的使用例子 Excel文件example3_4.xls 的內(nèi)容,注意 要將表格中的數(shù)據(jù)進(jìn)行命名 :選中數(shù)據(jù),選菜單 “插入|名稱|定義” 在這里分別命名為 a,b,d,e,x,y,result,OLE 的使用例子 Lingo文件example3_4.lg4 的內(nèi)容,data: a,b,d,e=OLE(d:數(shù)學(xué)建模EXAMPLE3_4.XLS); enddata init: x,y=Ole(d:數(shù)學(xué)建模Example3_4.xls); endinit,OLE 的使用例子 如果在Lingo文件ex

8、ample3_4.lg4 加上以下內(nèi)容 其他不變,data: ole(d:數(shù)學(xué)建模EXAMPLE3_4.XLS,result)=c; ole(d:數(shù)學(xué)建模EXAMPLE3_4.XLS,x)=x; ole(d:數(shù)學(xué)建模EXAMPLE3_4.XLS,y)=y; enddata,OLE 的使用例子,則example3_4.xls 變?yōu)?注意其中x,y ,result 的變化,鋼管訂購(gòu)和運(yùn)輸(2000年B題 ）,要鋪設(shè)一條 的輸送天然氣的主管道, 如圖一所示. 經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有 。圖中粗線表示鐵路，單細(xì)線表示公路，雙細(xì)線表示要鋪設(shè)的管道(假設(shè)沿管道或者原來(lái)有公路，或者建有施工公路

9、)，圓圈表示火車(chē)站，每段鐵路、公路和管道旁的阿拉伯?dāng)?shù)字表示里程(單位km)。,為方便計(jì)，1km主管道鋼管稱為1單位鋼管。 一個(gè)鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個(gè)單位。鋼廠在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個(gè)單位，鋼管出廠銷(xiāo)價(jià)1單位鋼管為萬(wàn)元，如下表：,1單位鋼管的鐵路運(yùn)價(jià)如下表：,1000km以上每增加1至100km運(yùn)價(jià)增加5萬(wàn)元。 公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬(wàn)元（不足整公里部分按整公里計(jì)算）。 鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只是運(yùn)到點(diǎn)，而是管道全線）。,問(wèn)題： （1）請(qǐng)制定一個(gè)主管道鋼管的訂購(gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最?。ńo出總費(fèi)用)。 （2）請(qǐng)就（1）的模型分析：哪

10、個(gè)鋼廠鋼管的銷(xiāo)價(jià)的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響最大，哪個(gè)鋼廠鋼管的產(chǎn)量的上限的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。 （3）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹(shù)形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情形給出一種解決辦法，并對(duì)圖二按（1）的要求給出模型和結(jié)果。,問(wèn) 題 分 析,這是一個(gè)優(yōu)化問(wèn)題，要找到一個(gè)鋼管訂購(gòu)運(yùn)輸計(jì)劃，使得總費(fèi)用最小。 而總費(fèi)用=鋼廠到各樞紐點(diǎn)的運(yùn)輸費(fèi)用+鋪設(shè)費(fèi)用,問(wèn) 題 分 析,運(yùn)輸費(fèi)用的計(jì)算 記1單位鋼管從鋼廠i運(yùn)到結(jié)點(diǎn)j的最少總費(fèi)用為： (包含鋼管采購(gòu)費(fèi)用) 若運(yùn)輸點(diǎn)j向鋼廠i訂購(gòu) 單位鋼管，則鋼管從鋼廠i運(yùn)到運(yùn)輸點(diǎn)j所需的費(fèi)用為 。那么所有

11、鋼管從各鋼廠運(yùn)到各運(yùn)輸點(diǎn)上的總費(fèi)用為：,問(wèn) 題 分 析,鋪設(shè)費(fèi)用的計(jì)算 若運(yùn)輸點(diǎn)j向(j,j-1)路段鋪設(shè) ，運(yùn)輸點(diǎn)j向(j,j+1)路段鋪設(shè)的總費(fèi)用為： ，于是運(yùn)輸點(diǎn)j巷兩邊鋪設(shè)的費(fèi)用為： 從而鋪設(shè)總費(fèi)用為：,問(wèn) 題 一模 型,其中si為第i個(gè)鋼廠的最大產(chǎn)量， Bj為Aj,Aj+1兩節(jié)點(diǎn)的距離。,問(wèn) 題 求 解,一、求鋼廠Si到Aj的單位鋼管最小費(fèi)用Aij,由于鋼管從鋼廠運(yùn)到運(yùn)輸點(diǎn)要通過(guò)鐵路和公路運(yùn)輸， 而鐵路運(yùn)輸費(fèi)用是分段函數(shù)，與全程運(yùn)輸總距離有關(guān), 因此不能直接使用圖論中的Dijkstra算法或Floyd算 法.,問(wèn) 題 求 解,一、求鋼廠Si到Aj的單位鋼管最小費(fèi)用Aij,分別在鐵路網(wǎng)

12、和公路網(wǎng)上計(jì)算最短路徑, 換算成費(fèi)用 在整個(gè)網(wǎng)絡(luò)上以相應(yīng)的運(yùn)費(fèi)為權(quán), 再求一次最短路.,問(wèn) 題 求 解,二、模型求解,.,為了能夠處理約束,我們?cè)黾?-1變量Ui, Ui=0表示不使用Si, 此時(shí)上述約束變?yōu)?,問(wèn) 題 求 解,三、Lingo 程序,.,Moel: Title 鋼管運(yùn)輸計(jì)劃問(wèn)題一; Sets: Supply/S1.S7/:s,U; Need/A1.A15/:B,Y,Z; Matrix(Supply,Need):A,X; EndSets,問(wèn) 題 求 解,三、Lingo 程序,.,Data: S=800 800 1000 2000 2000 2000 3000; B=104 301

13、 750 606 194 205 201 680 480 300 220 210 420 500; A=Text(“cost.txt”); Enddata;,問(wèn) 題 求 解,三、Lingo 程序,.,Min=sum(Matrix(i,j):A(i,j)*X(i,j)+0.05*sum (Need(j):Y(j)2+Y(j)+Z(j)2+Z(j); for(Supply(i):sum(Need(j):X(i,j)=500*U(i); for(Need(j):sum(supply(i):X(i,j)=Y(j)+Z(j); for(Need(j)|j#NE#15:Y(j)+Z(j+1)=B(j); Z(1)=0;Y(15)=0; for(Supply:bin(U); for(Need:gin(Y); End,問(wèn) 題 求 解,三、Lingo 程序,.,運(yùn)行結(jié)果 Objective value: 1278632.,其 它 合 理 模 型,將待鋪設(shè)的管道全線，按照1公里作為一個(gè)單位分割成 5170個(gè)點(diǎn)Pj。以Aij 記一個(gè)單位鋼管從Si到Pj的最小費(fèi)用. Xij為運(yùn)量(0-1變量),則問(wèn)題一的模型為:.,