數(shù)學(xué)建模 非線性規(guī)劃模型用MATLAB++LINGOVIP

非線性規(guī)劃 講義大綱 : 1.非線性規(guī)劃的定義和相關(guān)概念 . 2.常用的求解非線性規(guī)劃的方法 . 3.MATLAB求解 非線性規(guī)劃及例題 . 4.lingo求解 非線性規(guī)劃及例題 . 5.練習(xí) . 非現(xiàn)性規(guī)劃的基本概念 定義 如果目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線性函數(shù)時(shí)的最優(yōu)化問題就叫做非線性規(guī)劃問題 一般形式 : （ 1） 其中 ， 是定義在 En 上的實(shí)值函數(shù)，簡記 : Xfm in .,.,2,1 0m;1 , 2 , . . . , 0. ljXhiXgtsji nTn ExxxX , 21 ji hgf ,1nj1ni1n E :h ,E :g ,E : EEEf 其它情況 : 求目標(biāo)函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)化為上述一般形式 定義 1 把滿足問題（ 1）中條件的解 稱為 可行解 （或可行點(diǎn) ），所有可行點(diǎn)的集合稱為 可行集 （或 可行域 ）記為 D即 問題 (1)可簡記為 nji EXXhXgXD ,0,0|)( nEX XfDX min定義 2 對于問題 (1)，設(shè) ，若存在 ,使得對一切 ，且 ，都有 ，則稱 X*是 f(X)在 D上的局部極小值點(diǎn) （ 局部最優(yōu)解 ） 特別地當(dāng) 時(shí)， 若 則稱 X*是f(X)在 D上的 嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最優(yōu)解） DX * 0DX *XX*XX XfXf * XfXf *定義 3 對于問題 (1),設(shè) ,對任意的 ,都有 則稱 X*是 f(X)在 D上的 全局極小值點(diǎn) （ 全局最優(yōu)解 ） 特別地當(dāng) 時(shí)，若 ，則稱 X*是 f(X)在 D上的 嚴(yán)格全局極小值點(diǎn)（ 嚴(yán)格全局最優(yōu)解 ） DX * DX XfXf *XX XfXf *返回 非線性規(guī)劃的基本解法 SUTM外點(diǎn)法 SUTM內(nèi)點(diǎn)法（障礙罰函數(shù)法） 1、罰函數(shù)法 2、 近似規(guī)劃法 返回 罰函數(shù)法 罰函數(shù)法 基本思想是通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進(jìn)而用無約束最優(yōu)化方法去求解這類方法稱為 序列無約束最小化方法 (Sequential Unconstrained Minization Technique) 簡稱為 SUMT法 其一為 SUMT外點(diǎn)法 ，其二為 SUMT內(nèi)點(diǎn)法 )2( ,0m i n,1212 ljjmii XhMXgMXfMXT可設(shè)： )3( ,m i n 1 MXTnEX ）轉(zhuǎn)化為無約束問題：將問題（其中 T(X,M)稱為 罰函數(shù) ， M稱為 罰因子 ， 帶 M的項(xiàng)稱為 罰項(xiàng) ， 這里的罰函數(shù)只對不滿足約束條件的點(diǎn)實(shí)行懲罰：當(dāng) 時(shí)，滿足各 ，故罰項(xiàng) =0，不受懲罰當(dāng) 時(shí)，必有 的約束條件，故罰項(xiàng) 0，要受懲罰 XD 0,0 XhXg ii DX 00 XhXg ii 或SUTM外點(diǎn)法 )1( ., . . . ,2,1 0m;1 , 2 , . . . , 0. m i n ljXhiXgtsXfji對一般的非線性規(guī)劃： 罰函數(shù)法的 缺點(diǎn) 是：每個(gè)近似最優(yōu)解 Xk往往不是容許解，而只能近似滿足約束，在實(shí)際問題中這種結(jié)果可能不能使用；在解一系列無約束問題中，計(jì)算量太大，特別是隨著 Mk的增大，可能導(dǎo)致錯(cuò)誤 1、 任意給定初始點(diǎn) X0，取 M11，給定允許誤差 ，令 k=1； 2、 求無約束極值問題 的最優(yōu)解，設(shè)為 Xk=X(Mk)，即 ； 3、 若存在 ，使 ，則取 MkM( )令 k=k+1返回（ 2），否則，停止迭代得最優(yōu)解 . 計(jì)算時(shí)也可將收斂性判別準(zhǔn)則 改為 . 0 MXTnEX ,min ),(,m i n kkEXMXTMXTn mii 1 ki Xg 10, 1 MM k 0,0m i n12 mii XgMkXX * ki XgSUTM外點(diǎn)法 (罰函數(shù)法 )的 迭代步驟 例題 .min x2 s.t. x=1 顯然本問題的最優(yōu)解為 x*=1 用 SMT外點(diǎn)法 : T(x,M)=x2+Mmin(0,x-1)2 = 求 minT(x,M).本題可由 T(x,M)=2x+2M(x-1)=0,解得 : x=M/(1+M),M趨于無窮 . 可知 x從小于 1趨于 1,罰函數(shù)從外部趨于最優(yōu)解 . 2221x x Xx M x x X 當(dāng)當(dāng) )1(, . . . ,2,10.m i n i mXgtsXfi考慮問題： 所有嚴(yán)格內(nèi)點(diǎn)的集合。是可行域中，設(shè)集合 00 ,2,1,0| DmiXgXD i 11111, , l n ( , ) ( )1l n mmiii immiii iI X r I X r f X r g X I X r f X rgXr g X r rgX 構(gòu) 造 障 礙 函 數(shù)： 或其 中 稱 或 為 障 礙 項(xiàng) ， 為 障 礙 因 子 ）（得值問題：）就轉(zhuǎn)化為求一系列極這樣問題（kkkDXrXrXI ,m i n10SUTM內(nèi)點(diǎn)法（ 障礙函數(shù)法 ） 內(nèi)點(diǎn)法的迭代步驟 (1) 給定允許誤差 0 ，取 10,01 r ； ( 2 ) 求 出 約 束 集 合 D 的 一 個(gè) 內(nèi) 點(diǎn) 00 DX ，令 1k ；( 3 ) 以 01 DX k 為 初 始 點(diǎn) ， 求 解 kDXrXI ,m i n0， 其 中0DX 的 最 優(yōu) 解 ， 設(shè) 為 0DrXX kk ；( 4 ) 檢 驗(yàn) 是 否 滿 足 mikiXgr1ln 或 miikXgr11，滿足 ， 停 止 迭 代 ，kXX *；否則取kkrr 1，令 1 kk ，返回 (3 ）例題 .min x2 s.t. x=1 顯然本問題的最優(yōu)解為 x*=1 用 SMT內(nèi)點(diǎn)法 : 罰函數(shù) I(x,rk)=x2 rkln(x-1),求其最值 . 可見 ,x從大于 1趨于 1. , 2 0111, 0 , 12kkkkrI x r xxrx r x 解 得 令 得 近似規(guī)劃法的基本思想 ： 將問題 (3)中的目標(biāo)函數(shù) 和約束條件 近似為線性函數(shù)，并對變量的取值范圍加以限制，從而得到一個(gè)近似線性規(guī)劃問題，再用單純形法求解之，把其符合原始條件的最優(yōu)解作為 (3)的解的近似 Xf ),1( 0 m ) ;1 ,. .,( 0 ljXhiXg ji 近似規(guī)劃法 每得到一個(gè)近似解后，都從這點(diǎn)出發(fā)，重復(fù)以上步驟 這樣，通過求解一系列線性規(guī)劃問題，產(chǎn)生一個(gè)由線性規(guī)劃最優(yōu)解組成的序列，經(jīng)驗(yàn)表明，這樣的序列往往收斂于非線性規(guī)劃問題的解。 近似規(guī)劃法的 算法步驟如下 ( 2 ) 在點(diǎn)kX 處 ， 將 Xf ， XhXgji, 按 泰 勒 級 數(shù) 展 開 并取 一 階 近 似 ， 得 到 近 似 線 性 規(guī) 劃 問 題 ： kTkkXXXfXfXf m i n miXXXgXgXgkTkikii,1 0 lXXXhXhXhkTkjkjj,1j 0 ；( 1 ) 給定初始可行點(diǎn) 112111 , nxxxX ，步長限制 njj ,11 ，步長縮小系數(shù) 1,0 ，允許誤差 ，令 k = 1 ； 5) 判 斷 精 度 ：若 njkj ,1 ，則 點(diǎn)1kX為 近 似 最 優(yōu) 解 ；否則，令 njkjkj ,1 1 ， k = k + 1 ， 返 回 步 驟 ( 2 ) ( 3 ) 在 上 述 近 似 線 性 規(guī) 劃 問 題 的 基 礎(chǔ) 上 增 加 一 組 限 制 步 長 的 線性 約 束 條 件 因 為 線 性 近 似 通 常 只 在 展 開 點(diǎn) 附 近 近 似 程 度 較高 ，故 需 要 對 變 量 的 取 值 范 圍 加 以 限 制 ，所 增 加 的 約 束 條 件 是 ： njxxkjkjj,1 求 解 該 線 性 規(guī) 劃 問 題 ， 得 到 最 優(yōu) 解1kX ；( 4 ) 檢驗(yàn) 1kX 點(diǎn) 對 原 約 束 是 否 可 行 。 若 1kX 對 原 約 束 可 行 ，則轉(zhuǎn)步驟 ( 5 ) ；否 則 ，縮 小 步 長 限 制 ，令 njkjkj ,1 ，返回步驟 ( 3 ) ， 重 解 當(dāng) 前 的 線 性 規(guī) 劃 問 題 ；返回 例題 1、用近似規(guī)劃法求解下列問題。 12221 1 2222 1 2121m i n 2 1. . 2 5 0700 5 , 0 1 03 , 2 . 5 , 2 , 1 , 0 . 5TTf x x xs t g x x xg x x xxx 1初 始 點(diǎn) ： x解：第一次迭代：在點(diǎn) x1處將 g1(x), g2(x)線性化。 1 1 11 1 11212369 . 7 52 . 554 0 . 2 5 6 5 0 2TTg x g x g x x xxxxx 1 1 12 2 21212364 . 7 52 . 559 . 2 5 6 5 0 3TTg x g x g x x xxxxx 步長限制： 111122, 2 3 2 1 51 2 . 5 1 1 . 5 3 . 5 4x x x xxx 即2 114 , 36 2 0Tx 解（ 1）（ 2）（ 3）（ 4），得 ， 檢驗(yàn)，可得 x2不滿足原始約束。 第二次迭代，減少 2111221 , 0 . 51 3 1 2 450 . 5 2 . 5 0 . 5 2 3Txxxx 解（ 1,2,3,5)，得 x2=(4,3)T,f(x2)= -11.所以 x2為最小值點(diǎn) . 用 MATLAB軟件求解 ,其 輸入格式 如下 : 1. x=quadprog(H,C,A,b); 2. x=quadprog(H,C,A,b,Aeq,beq); 3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6. x,fval=quaprog(.); 7. x,fval,exitflag=quaprog(.); 8. x,fval,exitflag,output=quaprog(.); 1、二次規(guī)劃 標(biāo)準(zhǔn)型為： M i n Z = 21XTH X + cTX s . t . A X =0時(shí)，返回不超過 x的最大整數(shù)；當(dāng) x=100; x1*r21+x2*r22+x3*r23=100; x1*r31+x2*r32+x3*r33=100; x1*r41+x2*r42+x3*r43=70; x1+x2+x3=105; x1+x2+x3=5.9; 2.9*r12+2.1*r22+1.5*r32+1.8*r42=5.9; 2.9*r13+2.1*r23+1.5*r33+1.8*r43=5.9; 2.9*r11+2.1*r21+1.5*r31+1.8*r41=x2;x2=x3; gin(x1);gin(x2);gin(x3); gin(r11);gin(r21);gin(r31);gin(r41); gin(r12);gin(r22);gin(r32);gin(r42); gin(r13);gin(r23);gin(r33);gin(r43); end 運(yùn)行結(jié)果如下： Feasible solution found at iteration: 26565 Model Title: 鋼管下料； Variable Value X1 72.00000 R11 1.000000 X2 29.00000 R12 0.000000 X3 14.00000 R13 2.000000 R21 1.000000 R22 1.000000 R23 0.000000 R31 0.000000 R32 3.000000 R33 1.000000 R41 1.000000 R42 0.000000 R43 0.000000 Lingo源程序二 model: Title 鋼管下料 - 最小化鋼管根數(shù)的 LINGO模型 ; SETS: NEEDS/1.4/:LENGTH,NUM; ! 定義基本集合 NEEDS及其屬性 LENGTH,NUM; CUTS/1.3/:X; ! 定義基本集合 CUTS及其屬性 X; PATTERNS(NEEDS,CUTS):R; ! 定義派生集合 PATTERNS（這是一個(gè)稠密集合）及其屬性 R; ENDSETS DATA: LENGTH=2.9 2.1 1.5 1.8; NUM=100 100 100 70; CAPACITY=7.4; ENDDATA min=SUM(CUTS(I): X(I) ); !目標(biāo)函數(shù) ; Lingo源程序二 FOR(NEEDS(I): SUM(CUTS(J): X(J)*R(I,J) ) NUM(I) ); !滿足需求約束 ; FOR(CUTS(J): SUM(NEEDS(I): LENGTH(I)*R(I,J) ) CAPACITY -MIN(NEEDS(I):LENGTH(I) ); !合理切割模式約束 ; SUM(CUTS(I): X(I) ) 105; SUM(CUTS(I): X(I) ) X(I+1) ); !人為增加約束 ; FOR(CUTS(J): GIN(X(J) ) ; FOR(PATTERNS(I,J): GIN(R(I,J) ); end 運(yùn)行結(jié)果如下： Local optimal solution found at iteration: 64408 Objective value: 113.0000 Model Title: 鋼管下料 - 最小化鋼管根數(shù)的 LINGO模型 Variable Value Reduced Cost CAPACITY 7.400000 0.000000 LENGTH( 1) 2.900000 0.000000 LENGTH( 2) 2.100000 0.000000 LENGTH( 3) 1.500000 0.000000 LENGTH( 4) 1.800000 0.000000 NUM( 1) 100.0000 0.000000 NUM( 2) 100.0000 0.000000 NUM( 3) 100.0000 0.000000 NUM( 4) 70.00000 0.000000 X( 1) 50.00000 1.000000 X( 2) 37.00000 1.000000 X( 3) 26.00000 1.000000 運(yùn)行結(jié)果如下： R( 1, 1) 1.000000 0.000000 R( 1, 2) 0.000000 0.000000 R