第六講 線性規(guī)劃與非線性規(guī)劃.ppt

《第六講 線性規(guī)劃與非線性規(guī)劃.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第六講線性規(guī)劃與非線性規(guī)劃線性規(guī)劃與非線性規(guī)劃最優(yōu)化是人們在工程技術(shù)、科學(xué)研究和經(jīng)濟(jì)管理等領(lǐng)域常見的問題。要表述一個最優(yōu)化問題，一般需要確定三個要素：一是決策變量，通常是要求解的未知量；二是目標(biāo)函數(shù)，通常是要優(yōu)化(最小或最大)的那個目標(biāo)的數(shù)學(xué)表達(dá)式，是決策變量的函數(shù)；三是約束條件，對決策變量的限制條件，即允許取值的范圍，稱為可行域。一般地，優(yōu)化模型可表述為只滿足(2)的解稱為可行解，同滿足(1)(2)的解稱最優(yōu)解。優(yōu)化模型的分類數(shù)學(xué)規(guī)劃線性規(guī)劃(LP)二次規(guī)劃(QP)非線性規(guī)劃(NLP)0-1整數(shù)規(guī)劃一般整數(shù)規(guī)劃純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃(

2、MIP)整數(shù)規(guī)劃(IP)連續(xù)規(guī)劃一、線性規(guī)劃1、引例問題一：任務(wù)分配問題：某車間有甲、乙兩臺機(jī)床，可用于加工三種工件.假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費(fèi)用如下表.問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？模型設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為在乙車床上加工工件1、2、3的數(shù)量分別為問題二：某廠每日8小時的產(chǎn)量不低于1800件.為了進(jìn)行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標(biāo)準(zhǔn)為：速

3、度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標(biāo)準(zhǔn)為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗員每錯檢一次，工廠要損失2元.為使總檢驗費(fèi)用最省，該工廠應(yīng)聘一級、二級檢驗員各幾名？模型設(shè)需要一級、二級檢驗員的人數(shù)分別為人，應(yīng)付檢驗員工資為因檢驗員錯檢而造成的損失為2、線性規(guī)劃模型的標(biāo)準(zhǔn)形式或矩陣形式其中是決策變量，是約束矩陣，，3、線性規(guī)劃模型的實用形式(1)(2)注；當(dāng)前MATLAB只支持第一種形式。4、用MATLAB優(yōu)化工具箱解線性規(guī)劃(1)模型1：命令：x=linprog(c,A,b)(2)模型2：命令：x=l

4、inprog(c,A1,b1,A2,b2)注：[1]若沒有不等式存在，則令[2]輸出的x為最優(yōu)解。(3)模型3：命令：[1]x=linprog(c,A1,b1,A2,b2,v1,v2)[2]x=linprog(c,A1,b1,A2,b2,v1,v2,x0)注：[1]若沒有等式約束：，令[2]x0表示初始解。(4)命令：[x,fval,ef,out,lambda]=linprog(c,A1,b1,A2,b2,v1,v2,x0)輸出x為最優(yōu)解，fval為最優(yōu)值，ef為程序停止的標(biāo)志，out為個結(jié)構(gòu)變量，包括程序運(yùn)行的有關(guān)信息，lambda也是結(jié)構(gòu)變量

5、，對應(yīng)于相應(yīng)的約束的Lagrange乘子。例1：見MATLAB程序（xianxingguihua1）例2：見MATLAB程序（xianxingguihua2）例3：問題一的解答改寫為見MATLAB程序（xianxingguihua3）結(jié)果：即在甲機(jī)床上加工600個工件2,在乙機(jī)床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費(fèi)最小為13800.例4：問題二的解答改寫為見MATLAB程序（xianxingguihua4）結(jié)果：即只需聘用9個一級檢驗員。注：本問題應(yīng)還有一個約束條件：x1、x2取整數(shù)，故它屬于一個整數(shù)線性規(guī)劃問題，

6、這里當(dāng)成一個線性規(guī)劃求解，求得最優(yōu)解剛好是整數(shù)x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解.二、非線性規(guī)劃1、二次規(guī)劃標(biāo)準(zhǔn)形式：MATLAB調(diào)用格式：(1)x=quadprog(H,C,A1,b1);(2)x=quadprog(H,C,A1,b1,A2,b2,v1,v2);(3)[x,fval,exitflag,output]=quadprog(H,C,A1,b1,A2,b2,v1,v2,x0,options);例1：改寫成標(biāo)準(zhǔn)形式：

7、編程(見MATLAB程序(erciguihua1))結(jié)果：2、一般非線性規(guī)劃標(biāo)準(zhǔn)形式：其中為n維變元向量，均為非線性函數(shù)組成的向量，其他變量的含義與線性規(guī)劃、二次規(guī)劃中相同．用MATLAB求解上述問題，基本步驟分三步。(1)首先建立M文件fun.m,用來定義目標(biāo)函數(shù)f(x)，形式為functionf=fun(x)f=f(x);(2)若有非線性約束條件：或則建立M文件c.m定義函數(shù)一般形式為function[c1,c2]=c(x)c1=…c2=…(3)建立主程序。求解非線性規(guī)劃的函數(shù)是fmincon,調(diào)用格式為x=fmincon(‘fun’,x0,

8、A1,b1);[x,fv,ef,out,lag,grad,hess]=fmincon(‘fun’,x0,A1,b1,A2,b2,v1,v