第七講線性規(guī)劃與非線性規(guī)劃方法(次課)

1、1第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法第七講 線性規(guī)劃與非線性規(guī)劃內(nèi)容內(nèi)容: 本講主要介紹線性規(guī)劃問題的求解本講主要介紹線性規(guī)劃問題的求解目的目的: 接觸最優(yōu)化問題接觸最優(yōu)化問題,學習線性規(guī)劃算法的學習線性規(guī)劃算法的 MATLAB實現(xiàn)實現(xiàn)(基于單純型法變種基于單純型法變種)要求要求: 能夠直接對小規(guī)模線性規(guī)劃問題進行求解能夠直接對小規(guī)模線性規(guī)劃問題進行求解了解線性規(guī)劃問題的基本概念、形式和算法了解線性規(guī)劃問題的基本概念、形式和算法掌握線性規(guī)劃問題的圖解法掌握線性規(guī)劃問題的圖解法(2維維)和和lp算法算法通過范例通過范例,掌握線性規(guī)劃問題求解一般過程掌握線性規(guī)劃問題求解

2、一般過程2第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法關于線性規(guī)劃的引入和概述 線性規(guī)劃線性規(guī)劃隸屬于運籌學中的隸屬于運籌學中的約束優(yōu)化約束優(yōu)化，簡單說，簡單說就是就是目標函數(shù)目標函數(shù)(希望進行最優(yōu)化的指標希望進行最優(yōu)化的指標)和和約束條件約束條件(決策變量受到的限制決策變量受到的限制)均為線性函數(shù)的約束優(yōu)化均為線性函數(shù)的約束優(yōu)化(否則稱為否則稱為非線性規(guī)劃非線性規(guī)劃) 線性規(guī)劃問題是企業(yè)運作、科技研發(fā)和工程設計線性規(guī)劃問題是企業(yè)運作、科技研發(fā)和工程設計的常見問題，應用十分廣泛。具有代表性的算法的常見問題，應用十分廣泛。具有代表性的算法有有單純型法、橢球法和單純型法、橢球法和

3、Karmarkar算法算法。隨著計。隨著計算機硬件和軟件技術發(fā)展，幾十萬變量和約束的算機硬件和軟件技術發(fā)展，幾十萬變量和約束的線性規(guī)劃問題已經(jīng)很普通。線性規(guī)劃問題已經(jīng)很普通。 MATLAB優(yōu)化工具箱優(yōu)化工具箱 Optimization Toolbox 采用采用投影法投影法(單純型法變種單純型法變種)，由函數(shù)，由函數(shù)linprog實現(xiàn)求解。實現(xiàn)求解。3第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法解決規(guī)劃問題的基本流程第1步：問題的分析理解及描述（數(shù)學建模）第2步：解決問題的整體目標（目標函數(shù)）第3步：影響目標的各種限制條件（約束條件）第4步：應用相關函數(shù)獲得求解（算法實現(xiàn)）4第

4、七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法哪樣一些問題可以描述成為線性規(guī)劃問題？哪樣一些問題可以描述成為線性規(guī)劃問題？線性規(guī)劃模型的一般形式12min( ),( ,.,). .( )0,1,2,.,Tnxizf x xx xxst g xim當當 均為線性函數(shù)，上述優(yōu)化模型稱為均為線性函數(shù)，上述優(yōu)化模型稱為線線性規(guī)劃性規(guī)劃，否則稱為，否則稱為非線性規(guī)劃非線性規(guī)劃。關于線性規(guī)劃的形式，有諸如標準形式、規(guī)范關于線性規(guī)劃的形式，有諸如標準形式、規(guī)范形式等形式等之分之分，在這里我們只關心在這里我們只關心MATLAB能能夠接受的形式：夠接受的形式：,ifgmin. .Tzc xs t

5、Axb一般來說不同形式之間可以轉換一般來說不同形式之間可以轉換(YCXp14)z目標函數(shù)目標函數(shù)/c價值向量價值向量/A約束矩陣約束矩陣/b右端向量右端向量一個滿足約束的一個滿足約束的x-可行解可行解/可行解集合可行解集合-可行域可行域5第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法線性規(guī)劃的圖解法(2維情形)1通過一個簡單的實例通過一個簡單的實例,鞏固對線性規(guī)劃的若干鞏固對線性規(guī)劃的若干概念的理解：概念的理解：exp.1 圖解法求解線性規(guī)劃問題圖解法求解線性規(guī)劃問題: 1212112122121231212m ax3. .2 .:222 .:22321 4 .: 321 4,

6、0zxxs txxLxxxxLxxxxLxxxx將前三個約束條件的不等號改為等號將前三個約束條件的不等號改為等號,就是如上就是如上三條直線三條直線,下面考察直線下面考察直線L1, L2, L3及坐標軸圍成及坐標軸圍成的可行域的可行域:6第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法線性規(guī)劃的圖解法(2維情形)2如圖所示如圖所示:五邊形五邊形OQ1Q2Q4Q3構成可行域構成可行域x1x2oL1L2L3Q1Q2Q4(4,1)Q3Z1 Z2 Z3 Z4 Z5 當目標函數(shù)當目標函數(shù)z=3x1+x2取不同值時，表示一組平行取不同值時，表示一組平行直線，如圖中虛線，最優(yōu)解在直線，如圖中虛線

7、，最優(yōu)解在Q4點，點，Zmax=137第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法線性規(guī)劃的圖解法(2維情形)3一些直觀結論和定理：一些直觀結論和定理： 在在2維情形維情形下，可行域為直線組成的凸多邊下，可行域為直線組成的凸多邊形形，目標函數(shù)的等值線為直線，最優(yōu)解在凸多邊目標函數(shù)的等值線為直線，最優(yōu)解在凸多邊形的形的 某個頂點處取得。某個頂點處取得?？尚杏蚩尚杏蚩占占?，如改例中第，如改例中第3個約束為個約束為-3x1+2x2 14，則無最優(yōu)解；則無最優(yōu)解；可行域可行域無界無界，如去掉例中第如去掉例中第3個約束個約束-3x1+2x2 14，則可能無最優(yōu)解；則可能無最優(yōu)解；無窮

8、多無窮多最優(yōu)解，如改例中第最優(yōu)解，如改例中第3個約束為個約束為3x1+x2 14，則最優(yōu)解在凸多邊形一條邊上取得；則最優(yōu)解在凸多邊形一條邊上取得； 推廣到推廣到n維歐氏空間維歐氏空間，線性規(guī)劃問題若有最，線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解必是作為可行域的凸多面體的某優(yōu)解，則最優(yōu)解必是作為可行域的凸多面體的某個頂點。個頂點。8第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法線性規(guī)劃的LP解法相關函數(shù)介紹：相關函數(shù)介紹：lpmin. .zcxs t Axbx=lp(c,A,b)x=lp(c,A,b,v1,v2) % 即有約束即有約束v1 x v2x=lp(c,A,b,v1,v2,x0)

9、 % x0為初始解，缺省為為初始解，缺省為0 x,lag=lp() % lag為拉格朗日乘子，非為拉格朗日乘子，非 零分量對應于起作用的約束條件零分量對應于起作用的約束條件x,lag,how=lp() % how給出求解信息，無給出求解信息，無可行解可行解infeasible,無有界解無有界解unbounded,成功成功ok不過在高版本中不過在高版本中l(wèi)p已被已被linprog取代！取代！9第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法lp函數(shù)求解示例：針對前述針對前述exp.1可如下計算：可如下計算：c=-3,1;a=-1,1;1,-2;3,2;b=2,2,14;v1=0,0

10、;x=lp(c,a,b,v1)z=-c*xx = 4.0000 1.0000z = 13.0000c=-3;1;a=-1,1;1,-2;3,2;b=2;2;14;v1=0,0;x=lp(c,a,b,v1)z=-c*x10第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法線性規(guī)劃的LP解法相關函數(shù)介紹：相關函數(shù)介紹：linprogmin. .(, , ,Txfxs t A xbAeq xbeqlbuubfx b beq lbubAAeq沒有賦空)其中和為向量和為矩陣x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq) % 增加約束增加約束Aeq*x=beq

11、x=linprog(f,A,b,Aeq,beq,lb,ub) % 設計變量下上界設計變量下上界x,fval,exitflag,output,lambda=linprog() % fval返回返回目標函數(shù)值目標函數(shù)值/exitflag返回退出條件返回退出條件/output返回優(yōu)化信息返回優(yōu)化信息/lambda返回顯示哪些主動約束（返回顯示哪些主動約束（參數(shù)繁雜會用即可參數(shù)繁雜會用即可）11第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法linprog函數(shù)求解示例：exp.2求解下列線性規(guī)劃問題：求解下列線性規(guī)劃問題：12312312312123()546.2 03244 2323

12、0,0fxxxxstxxxxxxxxxxxf=-5;-4;-6;A=1,-1,1;3,2,4;3,2,0;b=20;42;30;lb=zeros(3,1);x,fval,exitflag,output,lambda=linprog(f,A,b,lb);x,fval,lambda.ineqlin, lambda.lower12第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法范例-化工公司產(chǎn)品生產(chǎn)計劃1.問題：略問題：略2.建模：建模：123423412123124()4001000300200. .202316342405,0fxxxxxs txxxxxxxxxxx 3.求解：求解

13、：13第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法范例-化工公司產(chǎn)品生產(chǎn)計劃f=-400;-1000;-300;200;A=0,-2,1,1;2,3,0,0;3,4,0,0;b=0;16;24;Aeq=0,-2,1,1;beq=0;lb=zeros(4,1);ub=inf*ones(4,1);ub(3)=5;x0=zeros(4,1);x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=lp(f,A,b,lb,ub,x0,1)14第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法Thats

14、all3Q!15第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法第七講 線性規(guī)劃與非線性規(guī)劃內(nèi)容：內(nèi)容：本講主要介紹非線性規(guī)劃問題的求解本講主要介紹非線性規(guī)劃問題的求解目的：目的：學習非學習非 線性規(guī)劃算法的線性規(guī)劃算法的 MATLAB實現(xiàn)實現(xiàn) 要求：要求：能夠運用軟件直接對小規(guī)模非線性規(guī)劃能夠運用軟件直接對小規(guī)模非線性規(guī)劃 問題進行求解問題進行求解了解非線性規(guī)劃問題區(qū)別于線性規(guī)劃問題的基了解非線性規(guī)劃問題區(qū)別于線性規(guī)劃問題的基本概念、形式和算法本概念、形式和算法掌握約束和無約束優(yōu)化函數(shù)掌握約束和無約束優(yōu)化函數(shù)constr和和fminu通過范例通過范例,掌握非線性規(guī)劃問題求解一般

15、過程掌握非線性規(guī)劃問題求解一般過程16第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法關于非線性規(guī)劃的引入和概述 非非線性規(guī)劃線性規(guī)劃同時涵蓋運籌學中的同時涵蓋運籌學中的約束約束優(yōu)化和優(yōu)化和無無約束約束優(yōu)化兩種類型優(yōu)化兩種類型，簡單說就是簡單說就是目標函數(shù)目標函數(shù)或或約束約束條件條件( (可以不帶可以不帶constraintconstraint) )均為非線性函數(shù)的優(yōu)均為非線性函數(shù)的優(yōu)化模型，稱為化模型，稱為非線性規(guī)劃非線性規(guī)劃。 非線性規(guī)劃問題同樣是企業(yè)運作、科技研發(fā)和非線性規(guī)劃問題同樣是企業(yè)運作、科技研發(fā)和工程設計的常見問題，甚至在某種意義上應用面工程設計的常見問題，甚至在某

16、種意義上應用面比線性規(guī)劃更廣。因為非線性本身就意味著混沌比線性規(guī)劃更廣。因為非線性本身就意味著混沌和無序，這與現(xiàn)實世界一致。和無序，這與現(xiàn)實世界一致。 MATLABMATLAB優(yōu)化工具箱優(yōu)化工具箱( (OptimOptim) )針對約束和非約束針對約束和非約束分別由函數(shù)分別由函數(shù)constrconstr和和fminufminu進行求解。進行求解。constrconstr升級為升級為fminconfmincon，fminufminu升級為升級為fminuncfminunc17第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法在后繼版本中不再提供支持？熟悉新函數(shù)在后繼版本中不再提供支持

17、？熟悉新函數(shù)版本更新帶來的函數(shù)升級18第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法非線性規(guī)劃模型的一般形式1下面分別給出約束和非約束優(yōu)化的一般形式，下面分別給出約束和非約束優(yōu)化的一般形式，以及各自簡單的例子以及各自簡單的例子: 2212221212m in23. .10, 02zxxs txxxxmin( ),. .( )0,( )0,nxijzf x xRst g xiIgxjJ19第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法非線性規(guī)劃模型的一般形式22212m in23zxxmin( ),nxzf x xR無約束優(yōu)化只有一個目標函數(shù)，這個目標函數(shù)無約束優(yōu)

18、化只有一個目標函數(shù)，這個目標函數(shù)必須是非線性的，實際問題真正無約束并不多必須是非線性的，實際問題真正無約束并不多: 20第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法非線性規(guī)劃方法概要 由于本身的復雜性，非線性規(guī)劃遠不如線性由于本身的復雜性，非線性規(guī)劃遠不如線性規(guī)劃問題那樣具備很規(guī)劃問題那樣具備很高效率高效率的求解方法。的求解方法。 相對而言無約束優(yōu)化更容易求解一些，一個相對而言無約束優(yōu)化更容易求解一些，一個基本的思路就是，基本的思路就是，化約束優(yōu)化為一系列無約束化約束優(yōu)化為一系列無約束優(yōu)優(yōu)化問題，例如：序列無約束極小化技術、可變?nèi)莼瘑栴}，例如：序列無約束極小化技術、可變?nèi)莶罘?/p>

19、，等等差法，等等 對于具體算法細節(jié)，我們雖然不會本課程中對于具體算法細節(jié)，我們雖然不會本課程中深入探究，但能夠從深入探究，但能夠從算法本身的著手改進算法本身的著手改進將會是將會是很有價值的工作，比如本章作者開發(fā)的逼近精確很有價值的工作，比如本章作者開發(fā)的逼近精確罰函數(shù)法，感興趣可以仔細研讀罰函數(shù)法，感興趣可以仔細研讀21第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法MATLAB非線性規(guī)劃函數(shù)約束優(yōu)化函數(shù)介紹：約束優(yōu)化函數(shù)介紹：constrmin( ). . 1( )02( )0f xs t gxgxvlbxvub調(diào)用語法：調(diào)用語法：constr (fmincon)X,OPTIO

20、NS = constr(FUN,x0,OPTIONS,VLB,VUB)具體含義請參見聯(lián)機具體含義請參見聯(lián)機help22第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法MATLAB非線性規(guī)劃函數(shù)無約束優(yōu)化函數(shù)介紹：無約束優(yōu)化函數(shù)介紹：fminu (fminunc)min( )f x調(diào)用語法：調(diào)用語法： fminuX,OPTIONS = fminu(FUN,x0,)具體含義請參見具體含義請參見tbp154求解非線性規(guī)劃問題，需要首先編制一個求解非線性規(guī)劃問題，需要首先編制一個m文文件，描述需要求解的問題，也即求解需以件，描述需要求解的問題，也即求解需以“被被調(diào)調(diào)”的形式進行的形式進行23第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃方法非線性規(guī)劃方法非線性規(guī)劃問題的范例-圈地1 某旅游發(fā)展有限公司計劃開發(fā)度假村，公司某旅游發(fā)展有限公司計劃開發(fā)度假村，公司要求先用一批舊磚建一圈矩形圍墻，以便存放建要求先用一批舊磚建一圈矩形圍墻，以便存放建筑材料舊磚的數(shù)量是固定的，圍墻的高度不能筑材料舊磚的數(shù)量是固定的，圍墻的高度不能低于兩米，圍墻圍住的面積越大越好要你來設低于兩米，圍墻圍住的面積越大越好要你來設計。