非線性規(guī)劃LINGO

1、 非非 線線 性性 規(guī)規(guī) 劃劃n非現(xiàn)性規(guī)劃的基本概念非現(xiàn)性規(guī)劃的基本概念定義定義 如果目標(biāo)函數(shù)或約束條件中至少有一個是非線性函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題非線性規(guī)劃問題 一般形式一般形式: （1） 其中 ， 是定義在 en 上的實(shí)值函數(shù)，簡記: xfmin .,.,2 , 1 0 m;1,2,., 0. . ljxhixgtsjintnexxxx,21jihgf,1nj1ni1ne :h ,e :g ,e :eeef 非非 線線 性性 規(guī)規(guī) 劃劃 定義定義1 1 把滿足問題（1）中條件的解 稱為可行解可行解（或可行（或可行點(diǎn)點(diǎn)），），所有可行點(diǎn)的集合稱為可行集可行集（或（或可行域可行域

2、）記為d即 問題(1)可簡記為 njiexxhxgxd, 0, 0|)(nex xfdxmin 非非 線線 性性 規(guī)規(guī) 劃劃定義定義2 2 對于問題(1)，設(shè) ，若存在 ,使得對一切 ，且 ，都有 ，則稱x*是f(x)在d上的局部極小值點(diǎn)局部極小值點(diǎn)（局部最優(yōu)解局部最優(yōu)解）特別地當(dāng) 時，若 ，則稱x*是f(x)在d上的嚴(yán)格局部極小值點(diǎn)嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最優(yōu)解嚴(yán)格局部最優(yōu)解）dx *0dx *xx*xx xfxf* xfxf* 非非 線線 性性 規(guī)規(guī) 劃劃定義定義3 3 對于問題(1),設(shè) ,對任意的 ,都有 則稱x*是f(x)在d上的全局極小值點(diǎn)全局極小值點(diǎn)（全局最優(yōu)解全局最優(yōu)解）特別

3、地當(dāng) 時，若 ，則稱x*是f(x)在d上的嚴(yán)格全局極小值點(diǎn)嚴(yán)格全局極小值點(diǎn)（嚴(yán)格全局最優(yōu)解嚴(yán)格全局最優(yōu)解）dx *dx xfxf*xx xfxf* 非非 線線 性性 規(guī)規(guī) 劃劃n如何用lingo軟件求解非線性規(guī)劃問題？ 非非 線線 性性 規(guī)規(guī) 劃劃例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 非非 線線 性性 規(guī)規(guī) 劃劃nlingo 程序nmin=-2*x1-6*x2+x1*x1-2*x1*x2+2*x1*x1;nx1+x2=2;n-x1+2*x2=2; 非非 線線 性性 規(guī)規(guī) 劃劃n計(jì)算結(jié)果n

4、objective value: -9.777778nx1 = 0.6666667 x2 = 1.333333 非非 線線 性性 規(guī)規(guī) 劃劃n練習(xí)題122212121212minxxxxf 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0 非非 線線 性性 規(guī)規(guī) 劃劃n例例2) 12424()(22122211xxxxxexfx x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0 非非 線線 性性 規(guī)規(guī) 劃劃nlingo程序nmin=exp(x1)*(4*x1*x1+2*x2*x2+4*x1*x2+2*x2+1);nx1+x2=0;n1.5+x

5、1*x2-x1-x2=0;n-x1*x2-10=0;nfree(x1);nfree(x2); 非非 線線 性性 規(guī)規(guī) 劃劃n計(jì)算結(jié)果nobjective value: 5.276848nx1 = 1.224745 nx2 = -1.224745 選 址 問 題某公司有6個建筑工地要開工，每個工地的位置（用平面坐標(biāo)系a，b表示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個臨時料場位于a(5,1)，b(2,7)，日儲量各有20噸。假設(shè)從料場到工地之間均有直線道路相連。 （1）試制定每天的供應(yīng)計(jì)劃，即從a，b兩料場分別向各工地運(yùn)送多少噸水泥，使總的噸千米數(shù)最小。 （2）為了進(jìn)一步減少

6、噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20噸，問應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？lingo 使用外部數(shù)據(jù)使用外部數(shù)據(jù)方法一 copy paste 方法方法二 file 輸入數(shù)據(jù)、text輸出數(shù)據(jù)（文本文件）方法三ole函數(shù)與電子表格軟件excel連接方法四 odbc函數(shù)與數(shù)據(jù)庫連接 file和和text：文本文件輸入輸出文本文件輸入輸出使用格式file(“filename”) 文件filename 是文本文件 每行以 結(jié)束 一次file(“filename”) 讀取一行紀(jì)錄file和和text：文本文件輸入輸出文本文件輸入輸出data:a=file(example3_3.l

7、dt);b=file(example3_3.ldt);d=file(example3_3.ldt);e=file(example3_3.ldt);enddatainit:x,y=file(example3_3.ldt);endinit1.25,8.75,0.5,5.75,3,7.251.25,0.75,4.75,5,6.5,7.753,5,4,7,6,1120,205,1,2,7example3_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

8、,4,7,6,11; e=20,20;x,y=5,1,2,7;ole ：與與excel連接連接使用格式ole(“filename” ，range_name_list) filename 為電子表 文件名 , range_name_list 為數(shù)據(jù)的單元范圍。ole 的使用例子excel文件example3_4.xls 的內(nèi)容abdexyresult1.251.25320518.750.75520270.54.7545.755736.567.257.7511注意 要將表格中的數(shù)據(jù)進(jìn)行命名 :選中數(shù)據(jù),選菜單“插入|名稱|定義” 在這里分別命名為 a,b,d,e,x,y,result ole 的使

9、用例子lingo文件example3_4.lg4 的內(nèi)容data:a,b,d,e=ole(d:數(shù)學(xué)建模example3_4.xls);enddatainit:x,y=ole(d:數(shù)學(xué)建模example3_4.xls);endinitole 的使用例子如果在lingo文件example3_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;enddataole 的使用例子則example3_4.xls 變?yōu)閍bdexy

10、result1.251.253205.69594 4.92852438.750.75520 7.2499977.7500.54.75455.7557036.5647.257.751107015011注意其中x,y ,result 的變化鋼管訂購和運(yùn)輸鋼管訂購和運(yùn)輸(2000(2000年年b b題題 ） 要鋪設(shè)一條 的輸送天然氣的主管道, 如圖一所示. 經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有 。圖中粗線表示鐵路，單細(xì)線表示公路，雙細(xì)線表示要鋪設(shè)的管道(假設(shè)沿管道或者原來有公路，或者建有施工公路)，圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯?dāng)?shù)字表示里程(單位km)。1521aaa721,sss

11、a13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200a2a3a4a5a6a11a711a 11a8a11a911a11a10a11a12a13a14a15s1s2s3s4s5s6s7圖一為方便計(jì)，1km主管道鋼管稱為1單位鋼管。一個鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個單位，鋼管出廠銷價1單位鋼管為萬元，如

12、下表：ip1234567800800100020002000200030001601551551601551501601單位鋼管的鐵路運(yùn)價如下表：里程(km)300301350351400401450451500運(yùn)價(萬元)2023262932 里程(km)5016006017007018008019009011000運(yùn)價(萬元)3744505560 1000km以上每增加1至100km運(yùn)價增加5萬元。公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計(jì)算）。鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只是運(yùn)到點(diǎn)，而是管道全線）。問題：問題：（1）請制定一個主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總

13、費(fèi)用最?。ńo出總費(fèi)用)。（2）請就（1）的模型分析：哪個鋼廠鋼管的銷價的變化對購運(yùn)計(jì)劃和總費(fèi)用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運(yùn)計(jì)劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。（3）如果要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。a13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003 0 60195202720690520170690462160320160110

14、290115011001200a19130190260100a2a3a4a5a6a7a8a11a9a10a11a12a13a14a15s1s2s3s4s5s6s7a16a17a18a20(a21)圖二 問問 題題 分分 析析這是一個優(yōu)化問題，要找到一個鋼管訂購運(yùn)輸計(jì)劃，使得總費(fèi)用最小。而總費(fèi)用=鋼廠到各樞紐點(diǎn)的運(yùn)輸費(fèi)用+鋪設(shè)費(fèi)用 問問 題題 分分 析析 運(yùn)輸費(fèi)用的計(jì)算記1單位鋼管從鋼廠i運(yùn)到結(jié)點(diǎn)j的最少總費(fèi)用為： (包含鋼管采購費(fèi)用)若運(yùn)輸點(diǎn)j向鋼廠i訂購 單位鋼管，則鋼管從鋼廠i運(yùn)到運(yùn)輸點(diǎn)j所需的費(fèi)用為 。那么所有鋼管從各鋼廠運(yùn)到各運(yùn)輸點(diǎn)上的總費(fèi)用為： ijaijxijijxa 15171j

15、iijijax 問問 題題 分分 析析 鋪設(shè)費(fèi)用的計(jì)算鋪設(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)用為：jzjy2/1 . 0)1() 1(151jjjjjyyzz2/ ) 1(1 . 02/ ) 1(1 . 0jjjjzzyy 問問 題題 一模一模 型型 0, 0,15, 2, 7 , 1 0 ,5000,151,2,j . .1 . 0)2) 1(2) 1(min15111517115171151yzbyzjixsxzyxtsaxzzyyfjjjijjiijijjijjiijijjjjjj

16、其中si為第i個鋼廠的最大產(chǎn)量， bj為aj,aj+1兩節(jié)點(diǎn)的距離。問問 題題 求求 解解一、求鋼廠si到aj的單位鋼管最小費(fèi)用aij 由于鋼管從鋼廠運(yùn)到運(yùn)輸點(diǎn)要通過鐵路和公路運(yùn)輸，而鐵路運(yùn)輸費(fèi)用是分段函數(shù)，與全程運(yùn)輸總距離有關(guān),因此不能直接使用圖論中的dijkstra算法或floyd算法. 問問 題題 求求 解解一、求鋼廠si到aj的單位鋼管最小費(fèi)用aij 分別在鐵路網(wǎng)和公路網(wǎng)上計(jì)算最短路徑,換算成費(fèi)用在整個網(wǎng)絡(luò)上以相應(yīng)的運(yùn)費(fèi)為權(quán), 再求一次最短路. 問問 題題 求求 解解二、模型求解 . ,5000151jiijsx為了能夠處理約束我們增加0-1變量ui, ui=0表示不使用si, 此時上

17、述約束變?yōu)? 500151jiiijisuxu問問 題題 求求 解解三、lingo 程序 . moel:title 鋼管運(yùn)輸計(jì)劃問題一;sets:supply/s1.s7/:s,u;need/a1.a15/:b,y,z;matrix(supply,need):a,x;endsets問問 題題 求求 解解三、lingo 程序 . data:s=800 800 1000 2000 2000 2000 3000;b=104 301 750 606 194 205 201 680 480 300 220 210 420 500;a=text(“cost.txt”);enddata;問問 題題 求求 解

18、解三、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問問 題題 求求 解解三、lingo 程序 . 運(yùn)行結(jié)果objective value: 1278632. 其 它 合 理