線性與非線性規(guī)劃算法及實(shí)現(xiàn)

第九章線性規(guī)劃內(nèi)容：本講主要介紹線性規(guī)劃問題的求解目的：接觸最優(yōu)化問題,學(xué)習(xí)線性規(guī)劃算法的MATLAB實(shí)現(xiàn)(基于單純型法變種)要求：能夠運(yùn)用軟件直接對小規(guī)模線性規(guī)劃問題進(jìn)行求解了解線性規(guī)劃問題的基本概念、形式和算法掌握線性規(guī)劃問題的圖解法(2維)和lp算法通過范例,掌握線性規(guī)劃問題求解一般過程第9.1節(jié)引入與導(dǎo)言01線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第1頁!關(guān)于線性規(guī)劃的引入和概述~

線性規(guī)劃隸屬于運(yùn)籌學(xué)中的約束優(yōu)化，簡單說就是目標(biāo)函數(shù)(希望進(jìn)行最優(yōu)化的指標(biāo))和約束條件(決策變量受到的限制)均為線性函數(shù)的約束優(yōu)化（否則稱為非線性規(guī)劃）。線性規(guī)劃問題是企業(yè)運(yùn)作、科技研發(fā)和工程設(shè)計的常見問題，應(yīng)用十分廣泛。具有代表性的算法有單純型法、橢球法和Karmarkar算法。隨著計算機(jī)硬件和軟件技術(shù)發(fā)展，幾十萬變量和約束的線性規(guī)劃問題已經(jīng)很普通。

MATLAB優(yōu)化工具箱(OptimizationToolbox)采用投影法(單純型法變種)，由函數(shù)linprog實(shí)現(xiàn)求解。第9.1節(jié)引入與導(dǎo)言02線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第2頁!解決規(guī)劃問題的基本流程~第9.1節(jié)引入與導(dǎo)言03第1步：問題的分析理解及描述（數(shù)學(xué)建模）第2步：解決問題的整體目標(biāo)（目標(biāo)函數(shù)）第3步：影響目標(biāo)的各種限制條件（約束條件）第4步：應(yīng)用相關(guān)函數(shù)獲得求解（算法實(shí)現(xiàn)）線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第3頁!線性規(guī)劃的圖解法(2維情形)1通過一個簡單的實(shí)例,鞏固對線性規(guī)劃的若干概念的理解：exp.1圖解法求解線性規(guī)劃問題:第9.34節(jié)線性規(guī)劃圖解法05將前三個約束條件的不等號改為等號,就是如上三條直線,下面考察直線L1,L2,L3及坐標(biāo)軸圍成的可行域:線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第4頁!線性規(guī)劃的圖解法(2維情形)3一些直觀結(jié)論和定理：在2維情形下，可行域為直線組成的凸多邊形，目標(biāo)函數(shù)的等值線為直線，最優(yōu)解在凸多邊形的某個頂點(diǎn)處取得?？尚杏蚩占?，如改例中第3個約束為-3x1+2x214，則無最優(yōu)解；可行域無界，如去掉例中第3個約束-3x1+2x214，則可能無最優(yōu)解；無窮多最優(yōu)解，如改例中第3個約束為3x1+x214，則最優(yōu)解在凸多邊形一條邊上取得；

推廣到n維歐氏空間，線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解必是作為可行域的凸多面體的某個頂點(diǎn)。第9.34節(jié)線性規(guī)劃圖解法07線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第5頁!lp函數(shù)求解示例：第9.2節(jié)線性規(guī)劃LP解法針對前述exp.1可如下計算：c=-[3,1];a=[-1,1;1,-2;3,2];b=[2,2,14];v1=[0,0];x=lp(c,a,b,v1)z=-c*xx=4.00001.0000z=13.000009c=-[3;1];a=[-1,1;1,-2;3,2];b=[2;2;14];v1=[0,0];x=lp(c,a,b,v1)z=-c'*x線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第6頁!linprog函數(shù)求解示例：第9.2節(jié)線性規(guī)劃LP解法11exp.2求解下列線性規(guī)劃問題：f=[-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.lower線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第7頁!范例-化工公司產(chǎn)品生產(chǎn)計劃第9.7節(jié)化工公司生產(chǎn)計劃13f=[-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)線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第8頁!第十章非線性規(guī)劃內(nèi)容：本講主要介紹非線性規(guī)劃問題的求解目的：學(xué)習(xí)非線性規(guī)劃算法的MATLAB實(shí)現(xiàn)要求：能夠運(yùn)用軟件直接對小規(guī)模非線性規(guī)劃問題進(jìn)行求解了解非線性規(guī)劃問題區(qū)別于線性規(guī)劃問題的基本概念、形式和算法掌握約束和無約束優(yōu)化函數(shù)constr和fminu通過范例,掌握非線性規(guī)劃問題求解一般過程第10.1節(jié)引入與導(dǎo)言01線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第9頁!在后繼版本中不再提供支持？熟悉新函數(shù)版本更新帶來的函數(shù)升級…第10.1節(jié)oldname和newname03線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第10頁!非線性規(guī)劃模型的一般形式2第10.31節(jié)無約束優(yōu)化模型05無約束優(yōu)化只有一個目標(biāo)函數(shù)，這個目標(biāo)函數(shù)必須是非線性的，實(shí)際問題真正無約束并不多:線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第11頁!MATLAB非線性規(guī)劃函數(shù)約束優(yōu)化函數(shù)介紹：constr第10.6節(jié)非線性規(guī)劃函數(shù)07調(diào)用語法：constr(fmincon)[X,OPTIONS]=constr('FUN',x0,OPTIONS,VLB,VUB)具體含義請參見聯(lián)機(jī)help線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第12頁!非線性規(guī)劃問題的范例-圈地1

某旅游發(fā)展有限公司計劃開發(fā)度假村，公司要求先用一批舊磚建一圈矩形圍墻，以便存放建筑材料．舊磚的數(shù)量是固定的，圍墻的高度不能低于兩米，圍墻圍住的面積越大越好．要你來設(shè)計。第10.6節(jié)非線性規(guī)劃函數(shù)09線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第13頁!非線性規(guī)劃問題的范例-圈地3具體非線性規(guī)劃模型：第10.7節(jié)范例圈地問題11tbp172.mfunction[F,G]=tbp172(x)F=-x(1)*x(2);G(1)=(x(1)+x(2))*x(3)-120;線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第14頁!非線性規(guī)劃問題的范例-無約束3第10.7節(jié)范例-無約束優(yōu)化13補(bǔ)充范例:求解：fun.mfunctiony=fun(x)a=2;b=2;y=x(1)^2/a+x(2)^2/b;x0=[1,1];x=fminu('fun',x0)精確解為0，0線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第15頁!哪樣一些問題可以描述成為線性規(guī)劃問題？線性規(guī)劃模型的一般形式第9.31節(jié)線性規(guī)劃一般形式04當(dāng)均為線性函數(shù)，上述優(yōu)化模型稱為線性規(guī)劃，否則稱為非線性規(guī)劃。關(guān)于線性規(guī)劃的形式，有諸如標(biāo)準(zhǔn)形式、規(guī)范形式等~之分，在這里我們只關(guān)心MATLAB能夠接受的形式：一般來說不同形式之間可以轉(zhuǎn)換(YCXp14)z目標(biāo)函數(shù)/c價值向量/A約束矩陣/b右端向量一個滿足約束的x-可行解/可行解集合-可行域線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第16頁!線性規(guī)劃的圖解法(2維情形)2第9.34節(jié)線性規(guī)劃圖解法如圖所示:五邊形OQ1Q2Q4Q3構(gòu)成可行域06x1x2oL1L2L3Q1Q2Q4(4,1)Q3Z1Z2Z3Z4Z5當(dāng)目標(biāo)函數(shù)z=3x1+x2取不同值時，表示一組平行直線，如圖中虛線，最優(yōu)解在Q4點(diǎn)，Zmax=13線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第17頁!線性規(guī)劃的LP解法相關(guān)函數(shù)介紹：lp第9.2節(jié)線性規(guī)劃LP解法08x=lp(c,A,b)x=lp(c,A,b,v1,v2)%即有約束v1xv2x=lp(c,A,b,v1,v2,x0)%x0為初始解，缺省為0[x,lag]=lp(…)%lag為拉格朗日乘子，非零分量對應(yīng)于起作用的約束條件[x,lag,how]=lp(…)%how給出求解信息，無可行解infeasible,無有界解unbounded,成功ok不過在高版本中l(wèi)p已被linprog取代！線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第18頁!線性規(guī)劃的LP解法相關(guān)函數(shù)介紹：linprog第9.2節(jié)線性規(guī)劃LP解法10x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)%增加約束Aeq*x=beqx=linprog(f,A,b,Aeq,beq,lb,ub)%設(shè)計變量下上界[x,fval,exitflag,output,lambda]=linprog(…)%fval返回目標(biāo)函數(shù)值/exitflag返回退出條件/output返回優(yōu)化信息/lambda返回顯示哪些主動約束（參數(shù)繁雜會用即可）線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第19頁!范例-化工公司產(chǎn)品生產(chǎn)計劃第9.7節(jié)化工公司生產(chǎn)計劃121.問題：略2.建模：3.求解：線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第20頁!That’sall~3Q!

下次課內(nèi)容非線性規(guī)劃算法實(shí)現(xiàn)14線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第21頁!關(guān)于非線性規(guī)劃的引入和概述~

非線性規(guī)劃同時涵蓋運(yùn)籌學(xué)中的約束優(yōu)化和無約束優(yōu)化兩種類型，簡單說就是目標(biāo)函數(shù)或約束條件(可以不帶constraint)均為非線性函數(shù)的優(yōu)化模型，稱為非線性規(guī)劃。非線性規(guī)劃問題同樣是企業(yè)運(yùn)作、科技研發(fā)和工程設(shè)計的常見問題，甚至在某種意義上應(yīng)用面比線性規(guī)劃更廣。因為非線性本身就意味著混沌和無序，這與現(xiàn)實(shí)世界一致。

MATLAB優(yōu)化工具箱(Optim)針對約束和非約束分別由函數(shù)constr和fminu進(jìn)行求解。constr升級為fmincon，fminu升級為fminunc第10.1節(jié)引入與導(dǎo)言02線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第22頁!非線性規(guī)劃模型的一般形式1下面分別給出約束和非約束優(yōu)化的一般形式，以及各自簡單的例子:第10.31節(jié)約束優(yōu)化模型04線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第23頁!非線性規(guī)劃方法概要

由于本身的復(fù)雜性，非線性規(guī)劃遠(yuǎn)不如線性規(guī)劃問題那樣具備很高效率的求解方法。相對而言無約束優(yōu)化更容易求解一些，一個基本的思路就是，化約束優(yōu)化為一系列無約束優(yōu)化問題，例如：序列無約束極小化技術(shù)、可變?nèi)莶罘?，等等~~對于具體算法細(xì)節(jié)，我們雖然不會本課程中深入探究，但能夠從算法本身的著手改進(jìn)將會是很有價值的工作，比如本章作者開發(fā)的逼近精確罰函數(shù)法，感興趣可以仔細(xì)研讀第9.34節(jié)非線性規(guī)劃方法概要06線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第24頁!MATLAB非線性規(guī)劃函數(shù)無約束優(yōu)化函數(shù)介紹：fminu(fminunc)第10.6節(jié)非線性規(guī)劃函數(shù)08調(diào)用語法：fminu[X,OPTIONS]=fminu('FUN',x0,…)具體含義請參見tbp154求解非線性規(guī)劃問題，需要首先編制一個m文件，描述需要求解的問題，也即求解需以“被調(diào)”的形式進(jìn)行線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第25頁!非線性規(guī)劃問題的范例-圈地2第10.6節(jié)非線性規(guī)劃函數(shù)10線性與非線性規(guī)劃算法及實(shí)現(xiàn)共28頁，您現(xiàn)在瀏覽的是第26頁!非線性規(guī)劃問題的范例-圈地4第10.7節(jié)范例圈地問題12lo