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

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

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

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

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

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

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

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

8、多無窮多最優(yōu)解，如改例中第最優(yōu)解，如改例中第3個(gè)約束為個(gè)約束為3x1+x2 14，則最優(yōu)解在凸多邊形一條邊上取得；則最優(yōu)解在凸多邊形一條邊上取得； 推廣到推廣到n維歐氏空間維歐氏空間，線性規(guī)劃問題若有最，線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解必是作為可行域的凸多面體的某優(yōu)解，則最優(yōu)解必是作為可行域的凸多面體的某個(gè)頂點(diǎn)。個(gè)頂點(diǎn)。8第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃應(yīng)用非線性規(guī)劃應(yīng)用線性規(guī)劃的LP解法相關(guān)函數(shù)介紹：相關(guān)函數(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為拉格朗日乘子，非為拉格朗日乘子，非 零分量對(duì)應(yīng)于起作用的約束條件零分量對(duì)應(yīng)于起作用的約束條件x,lag,how=lp() % how給出求解信息，無給出求解信息，無可行解可行解infeasible,無有界解無有界解unbounded,成功成功ok不過在高版本中不過在高版本中l(wèi)p已被已被linprog取代！取代！9第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃應(yīng)用非線性規(guī)劃應(yīng)用lp函數(shù)求解示例：針對(duì)前述針對(duì)前述exp.1可如下計(jì)算：可如下計(jì)算：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ī)劃應(yīng)用非線性規(guī)劃應(yīng)用線性規(guī)劃的LP解法相關(guān)函數(shù)介紹：相關(guān)函數(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) % 設(shè)計(jì)變量下上界設(shè)計(jì)變量下上界x,fval,exitflag,output,lambda=linprog() % fval返回返回目標(biāo)函數(shù)值目標(biāo)函數(shù)值/exitflag返回退出條件返回退出條件/output返回優(yōu)化信息返回優(yōu)化信息/lambda返回顯示哪些主動(dòng)約束（返回顯示哪些主動(dòng)約束（參數(shù)繁雜會(huì)用即可參數(shù)繁雜會(huì)用即可）11第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃應(yīng)用非線性規(guī)劃應(yīng)用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ī)劃應(yīng)用非線性規(guī)劃應(yīng)用范例-化工公司產(chǎn)品生產(chǎn)計(jì)劃1.問題：略問題：略2.建模：建模：123423412123124()4001000300200. .202316342405,0fxxxxxs txxxxxxxxxxx 3.求解：求解：13第七講第七講 線性規(guī)劃與線性規(guī)劃與非線性規(guī)劃應(yīng)用非線性規(guī)劃應(yīng)用范例-化工公司產(chǎn)品生產(chǎn)計(jì)劃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;