線性規(guī)劃與非線性規(guī)劃方法(2次課)

《線性規(guī)劃與非線性規(guī)劃方法(2次課)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第七講線性規(guī)劃與非線性規(guī)劃內(nèi)容:本講主要介紹線性規(guī)劃問題的求解目的:接觸最優(yōu)化問題,學(xué)習(xí)線性規(guī)劃算法的MATLAB實(shí)現(xiàn)(基于單純型法變種)要求:能夠直接對(duì)小規(guī)模線性規(guī)劃問題進(jìn)行求解了解線性規(guī)劃問題的基本概念、形式和算法掌握線性規(guī)劃問題的圖解法(2維)和lp算法通過范例,掌握線性規(guī)劃問題求解一般過程關(guān)于線性規(guī)劃的引入和概述~線性規(guī)劃隸屬于運(yùn)籌學(xué)中的約束優(yōu)化，簡(jiǎn)單說就是目標(biāo)函數(shù)(希望進(jìn)行最優(yōu)化的指標(biāo))和約束條件(決策變量受到的限制)均為線性函數(shù)的約束優(yōu)化(否則稱為非線性規(guī)劃)線性規(guī)劃問題是企業(yè)運(yùn)作、科技研發(fā)和工程設(shè)計(jì)的常見問題，應(yīng)用十分廣泛。具有代表性的算法有單純型法、橢球法和K

2、armarkar算法。隨著計(jì)算機(jī)硬件和軟件技術(shù)發(fā)展，幾十萬變量和約束的線性規(guī)劃問題已經(jīng)很普通。MATLAB優(yōu)化工具箱OptimizationToolbox采用投影法(單純型法變種)，由函數(shù)linprog實(shí)現(xiàn)求解。解決規(guī)劃問題的基本流程~第1步：?jiǎn)栴}的分析理解及描述（數(shù)學(xué)建模）第2步：解決問題的整體目標(biāo)（目標(biāo)函數(shù)）第3步：影響目標(biāo)的各種限制條件（約束條件）第4步：應(yīng)用相關(guān)函數(shù)獲得求解（算法實(shí)現(xiàn)）哪樣一些問題可以描述成為線性規(guī)劃問題？線性規(guī)劃模型的一般形式當(dāng)均為線性函數(shù)，上述優(yōu)化模型稱為線性規(guī)劃，否則稱為非線性規(guī)劃。關(guān)于線性規(guī)劃的形式，有諸如標(biāo)準(zhǔn)形式、規(guī)范形式等~之分，在這里我們

3、只關(guān)心MATLAB能夠接受的形式：一般來說不同形式之間可以轉(zhuǎn)換(YCXp14)z目標(biāo)函數(shù)/c價(jià)值向量/A約束矩陣/b右端向量一個(gè)滿足約束的x-可行解/可行解集合-可行域線性規(guī)劃的圖解法(2維情形)1通過一個(gè)簡(jiǎn)單的實(shí)例,鞏固對(duì)線性規(guī)劃的若干概念的理解：exp.1圖解法求解線性規(guī)劃問題:將前三個(gè)約束條件的不等號(hào)改為等號(hào),就是如上三條直線,下面考察直線L1,L2,L3及坐標(biāo)軸圍成的可行域:線性規(guī)劃的圖解法(2維情形)2如圖所示:五邊形OQ1Q2Q4Q3構(gòu)成可行域x1x2oL1L2L3Q1Q2Q4(4,1)Q3Z1Z2Z3Z4Z5當(dāng)目標(biāo)函數(shù)z=3x1+x2取不同值時(shí)，表示一組平行直線

4、，如圖中虛線，最優(yōu)解在Q4點(diǎn)，Zmax=13線性規(guī)劃的圖解法(2維情形)3一些直觀結(jié)論和定理：在2維情形下，可行域?yàn)橹本€組成的凸多邊形，目標(biāo)函數(shù)的等值線為直線，最優(yōu)解在凸多邊形的某個(gè)頂點(diǎn)處取得?？尚杏蚩占?，如改例中第3個(gè)約束為-3x1+2x2?14，則無最優(yōu)解；可行域無界，如去掉例中第3個(gè)約束-3x1+2x2?14，則可能無最優(yōu)解；無窮多最優(yōu)解，如改例中第3個(gè)約束為3x1+x2?14，則最優(yōu)解在凸多邊形一條邊上取得；推廣到n維歐氏空間，線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解必是作為可行域的凸多面體的某個(gè)頂點(diǎn)。線性規(guī)劃的LP解法相關(guān)函數(shù)介紹：lpx=lp(c,A,b)x=lp(c,A

5、,b,v1,v2)%即有約束v1?x?v2x=lp(c,A,b,v1,v2,x0)%x0為初始解，缺省為0[x,lag]=lp(…)%lag為拉格朗日乘子，非零分量對(duì)應(yīng)于起作用的約束條件[x,lag,how]=lp(…)%how給出求解信息，無可行解infeasible,無有界解unbounded,成功ok不過在高版本中l(wèi)p已被linprog取代！lp函數(shù)求解示例：針對(duì)前述exp.1可如下計(jì)算：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.0000c=

6、-[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ī)劃的LP解法相關(guān)函數(shù)介紹：linprogx=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)%增加約束Aeq*x=beqx=linprog(f,A,b,Aeq,beq,lb,ub)%設(shè)計(jì)變量下上界[x,fval,exitflag,output,lambda]=linprog(…)%fval返回目標(biāo)函數(shù)值/exitflag返回退出條件/output返回優(yōu)化信息/lambda返回顯示哪些主動(dòng)約束（參數(shù)繁雜會(huì)用即可）l

7、inprog函數(shù)求解示例：exp.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范例-化工公司產(chǎn)品生產(chǎn)計(jì)劃1.問題：略2.建模：3.求解：范例-化工公司產(chǎn)品生產(chǎn)計(jì)劃f=[-400;-1000;-300;200];A=[0,-