一、線性規(guī)劃引例：某車間生產(chǎn)A和B兩種產(chǎn)品。為了生產(chǎn)A和B，所需的原料分別為每臺2與3個單位，所需工時分別為每臺4和2個單位?，F(xiàn)在可以應(yīng)用的原料為100個單位，工時為120個單位。每生產(chǎn)一臺A和B分別可得利潤6元和4元。應(yīng)當(dāng)安排生產(chǎn)A、B各多少臺，才能獲得最大的利潤？

解：設(shè)A、B產(chǎn)品的臺數(shù)各生產(chǎn)x1,x2臺。目標(biāo)函數(shù)－利潤函數(shù)

限制條件：§2－1線性規(guī)劃與二次規(guī)劃問題當(dāng)前第1頁\共有150頁\編于星期三\7點原問題表述為：標(biāo)準(zhǔn)化后：線性規(guī)劃問題－目標(biāo)函數(shù)與約束函數(shù)均是線性的當(dāng)前第2頁\共有150頁\編于星期三\7點線性規(guī)劃問題相關(guān)定理1、線性規(guī)劃問題的可行域D是凸集。2、若線性規(guī)劃問題存在最優(yōu)解，則目標(biāo)函數(shù)的最優(yōu)值可在某個極點（頂點）達(dá)到。x1x2Dz減小的方向最優(yōu)解最優(yōu)解：x1=x2=20當(dāng)前第3頁\共有150頁\編于星期三\7點二、線性規(guī)劃問題的單純形求解算法介紹1947年提出，后有許多改造，形成許多變種。應(yīng)用較廣，具權(quán)威性?，F(xiàn)舉例說明該算法的基本思想當(dāng)前第4頁\共有150頁\編于星期三\7點x1x2z下降的方向12345極點1－2－3－4？極點1－5－4？極點1－4？思想：從一個基本可行解（極點）出發(fā)，求另一個使目標(biāo)函數(shù)值下降的基本可行解…..當(dāng)前第5頁\共有150頁\編于星期三\7點引入松弛變量x3、x4、x5，原式化成標(biāo)準(zhǔn)形式當(dāng)前第6頁\共有150頁\編于星期三\7點其中在中若令其中的兩個未知量為零，則剩余的三個可由其解出。當(dāng)前第7頁\共有150頁\編于星期三\7點1）如另x1=x2=0，則有x1x212345上面的解是可行解，x1=x2=0對應(yīng)于點1——基本可行解——基變量當(dāng)前第8頁\共有150頁\編于星期三\7點2）通過某些判定條件。令x5=x2=0新的解是可行解，x1=3，x2=0對應(yīng)于點5——另一基本可行解x1x212345——基變量——非基變量當(dāng)前第9頁\共有150頁\編于星期三\7點3）通過某些判定條件。令x5=x4=0x1x212345新的解是可行解，x1=4.2，x2=5.2對應(yīng)于點5——最優(yōu)基本解——基變量關(guān)鍵點：每次取三個基變量，根據(jù)一些判定條件選擇。前后兩次迭代的基變量相差一個。極點1－5－4——非基變量當(dāng)前第10頁\共有150頁\編于星期三\7點一般形式的線性規(guī)劃問題其中三、利用MATLAB求解線性規(guī)劃問題當(dāng)前第11頁\共有150頁\編于星期三\7點當(dāng)前第12頁\共有150頁\編于星期三\7點當(dāng)前第13頁\共有150頁\編于星期三\7點linprog(C,A,b,Aeq,beq，Lb,Ub)當(dāng)前第14頁\共有150頁\編于星期三\7點>>C=[1;-3;1];>>Aeq=[2-11];>>beq=8;>>A=[-2-10;120];>>b=[-2;10];>>Lb=[0;0;0];>>x=linprog(C,A,b,Aeq,beq,Lb,[])Optimizationterminatedsuccessfully.x=0.80824.595910.9794當(dāng)前第15頁\共有150頁\編于星期三\7點當(dāng)前第16頁\共有150頁\編于星期三\7點當(dāng)前第17頁\共有150頁\編于星期三\7點>>C=[-4;-1];>>A=[-12231-1]>>b=[4;12;3];>>Lb=[0;0];>>x=linprog(C,A,b,[],[],Lb,[])

Optimizationterminatedsuccessfully.x=4.20001.2000當(dāng)前第18頁\共有150頁\編于星期三\7點當(dāng)前第19頁\共有150頁\編于星期三\7點引例：某車間生產(chǎn)A和B兩種產(chǎn)品。為了生產(chǎn)A和B，所需的原料分別為每臺2與3個單位，所需工時分別為每臺4和2個單位?，F(xiàn)在可以應(yīng)用的原料為100個單位，工時為120個單位。每生產(chǎn)一臺A和B分別可得利潤6元和4元。應(yīng)當(dāng)安排生產(chǎn)A、B各多少臺，才能獲得最大的利潤？標(biāo)準(zhǔn)化后MATLAB求解當(dāng)前第20頁\共有150頁\編于星期三\7點當(dāng)前第21頁\共有150頁\編于星期三\7點四、二次規(guī)劃問題其中當(dāng)前第22頁\共有150頁\編于星期三\7點當(dāng)前第23頁\共有150頁\編于星期三\7點quadprog(H,f,A,b,Aeq,beq，Lb,Ub)當(dāng)前第24頁\共有150頁\編于星期三\7點>>f=[-2;-6];>>H=[1-1;-12];>>A=[11;-12;21];>>b=[2;2;2];>>Lb=[0;0];>>x=quadprog(H,f,A,b,[],[],Lb)Optimizationterminatedsuccessfully.x=0.40001.2000當(dāng)前第25頁\共有150頁\編于星期三\7點當(dāng)前第26頁\共有150頁\編于星期三\7點習(xí)題：用Matlab求解下列優(yōu)化問題當(dāng)前第27頁\共有150頁\編于星期三\7點§2－2約束最優(yōu)化方法概述在工程實際中，所有設(shè)計問題幾乎都是約束非線性規(guī)劃問題。當(dāng)前第28頁\共有150頁\編于星期三\7點目前對于約束非線性最優(yōu)化問題的解法較多，可以分為兩大類。直接法：用原來的目標(biāo)函數(shù)限定在可行域內(nèi)進(jìn)行搜索，且在搜索的過程中一步步的降低目標(biāo)函數(shù)值，直到求出在可行域內(nèi)的一個最優(yōu)解。主要方法有：有約束變量輪換法、隨機(jī)試驗法、隨機(jī)方向搜索法、復(fù)合形法、可行方向法等。間接法：將約束最優(yōu)化問題通過變換，轉(zhuǎn)成為無約束最優(yōu)化問題，然后再用無約束最優(yōu)化方法來求得最優(yōu)解。主要方法有：消元法、拉格朗日乘子法、罰函數(shù)法等。

當(dāng)前第29頁\共有150頁\編于星期三\7點目前約束最優(yōu)化問題的算法收斂速度的判斷比無約束最優(yōu)化問題困難，約束最優(yōu)化問題的研究和進(jìn)展情況遠(yuǎn)不如無約束最優(yōu)化問題。在本章將主要介紹隨機(jī)方向搜索法、復(fù)合形法、罰函數(shù)法。當(dāng)前第30頁\共有150頁\編于星期三\7點§2－2約束隨機(jī)方向搜索法一、基本原理約束隨機(jī)方向搜索法是解決小型約束最優(yōu)化問題的一種較為有效的直接求解方法。約束隨機(jī)方向搜索法是一種數(shù)值迭代解法，其基本思想可用二維最優(yōu)化問題來進(jìn)行說明。當(dāng)前第31頁\共有150頁\編于星期三\7點等值線等值線等值線當(dāng)前第32頁\共有150頁\編于星期三\7點當(dāng)前第33頁\共有150頁\編于星期三\7點等值線等值線等值線當(dāng)前第34頁\共有150頁\編于星期三\7點當(dāng)前第35頁\共有150頁\編于星期三\7點二、初始點的選擇當(dāng)前第36頁\共有150頁\編于星期三\7點當(dāng)前第37頁\共有150頁\編于星期三\7點當(dāng)前第38頁\共有150頁\編于星期三\7點當(dāng)前第39頁\共有150頁\編于星期三\7點三、隨機(jī)搜索方向的產(chǎn)生當(dāng)前第40頁\共有150頁\編于星期三\7點當(dāng)前第41頁\共有150頁\編于星期三\7點當(dāng)前第42頁\共有150頁\編于星期三\7點四、隨機(jī)方向搜索的計算過程和算法框圖當(dāng)前第43頁\共有150頁\編于星期三\7點當(dāng)前第44頁\共有150頁\編于星期三\7點當(dāng)前第45頁\共有150頁\編于星期三\7點當(dāng)前第46頁\共有150頁\編于星期三\7點隨機(jī)方向搜索法計算框圖當(dāng)前第47頁\共有150頁\編于星期三\7點隨機(jī)方向搜索法計算框圖（續(xù)）一維搜索過程當(dāng)前第48頁\共有150頁\編于星期三\7點例、用隨機(jī)方向法求解下列優(yōu)化問題取迭代13次，求得當(dāng)前第49頁\共有150頁\編于星期三\7點kx1x2f(x)0-2.02.06.01-0.1681.1171.196┈┈┈┈4-0.0331.0241.025┈┈┈┈10-0.077-2.998-2.998┈┈┈┈13-0.00247-3.0-3.0迭代過程顯示當(dāng)前第50頁\共有150頁\編于星期三\7點一維搜索說明——簡單過程搜索方向x1x201234不可行點當(dāng)前第51頁\共有150頁\編于星期三\7點§2－3復(fù)合形法一、復(fù)合形法的基本原理當(dāng)前第52頁\共有150頁\編于星期三\7點x1x2K=3K=4n=2K=6K=4n=3x1x2x3當(dāng)前第53頁\共有150頁\編于星期三\7點復(fù)合形法的基本原理當(dāng)前第54頁\共有150頁\編于星期三\7點當(dāng)前第55頁\共有150頁\編于星期三\7點當(dāng)前第56頁\共有150頁\編于星期三\7點當(dāng)前第57頁\共有150頁\編于星期三\7點當(dāng)前第58頁\共有150頁\編于星期三\7點當(dāng)前第59頁\共有150頁\編于星期三\7點二、初始復(fù)合形的產(chǎn)生2012年12月6日當(dāng)前第60頁\共有150頁\編于星期三\7點當(dāng)前第61頁\共有150頁\編于星期三\7點當(dāng)前第62頁\共有150頁\編于星期三\7點當(dāng)前第63頁\共有150頁\編于星期三\7點當(dāng)前第64頁\共有150頁\編于星期三\7點當(dāng)前第65頁\共有150頁\編于星期三\7點當(dāng)前第66頁\共有150頁\編于星期三\7點三、復(fù)合形法的迭代過程和算法框圖當(dāng)前第67頁\共有150頁\編于星期三\7點當(dāng)前第68頁\共有150頁\編于星期三\7點當(dāng)前第69頁\共有150頁\編于星期三\7點當(dāng)前第70頁\共有150頁\編于星期三\7點當(dāng)前第71頁\共有150頁\編于星期三\7點當(dāng)前第72頁\共有150頁\編于星期三\7點當(dāng)前第73頁\共有150頁\編于星期三\7點復(fù)合形法計算框圖當(dāng)前第74頁\共有150頁\編于星期三\7點復(fù)合形法計算框圖（續(xù)）當(dāng)前第75頁\共有150頁\編于星期三\7點復(fù)合形法計算框圖（續(xù)）當(dāng)前第76頁\共有150頁\編于星期三\7點四、復(fù)合形法算例當(dāng)前第77頁\共有150頁\編于星期三\7點當(dāng)前第78頁\共有150頁\編于星期三\7點當(dāng)前第79頁\共有150頁\編于星期三\7點當(dāng)前第80頁\共有150頁\編于星期三\7點當(dāng)前第81頁\共有150頁\編于星期三\7點次數(shù)復(fù)合形頂點及目標(biāo)函數(shù)值迭代終止判別值初始12270.015955280.009021各次迭代結(jié)果：當(dāng)前第82頁\共有150頁\編于星期三\7點§2－4罰函數(shù)法一、罰函數(shù)法的基本原理當(dāng)前第83頁\共有150頁\編于星期三\7點當(dāng)前第84頁\共有150頁\編于星期三\7點一系列無約束優(yōu)化問題的解逼近原問題的最優(yōu)解當(dāng)前第85頁\共有150頁\編于星期三\7點對罰函數(shù)的進(jìn)一步說明當(dāng)前第86頁\共有150頁\編于星期三\7點當(dāng)前第87頁\共有150頁\編于星期三\7點總結(jié)求解過程當(dāng)前第88頁\共有150頁\編于星期三\7點二、外點罰函數(shù)法(一)基本原理當(dāng)前第89頁\共有150頁\編于星期三\7點當(dāng)前第90頁\共有150頁\編于星期三\7點化成標(biāo)準(zhǔn)形式當(dāng)前第91頁\共有150頁\編于星期三\7點當(dāng)前第92頁\共有150頁\編于星期三\7點當(dāng)前第93頁\共有150頁\編于星期三\7點外點法：罰函數(shù)的無約束最優(yōu)解在可行域外部。當(dāng)前第94頁\共有150頁\編于星期三\7點當(dāng)前第95頁\共有150頁\編于星期三\7點當(dāng)前第96頁\共有150頁\編于星期三\7點當(dāng)前第97頁\共有150頁\編于星期三\7點外點罰函數(shù)法計算框圖當(dāng)前第98頁\共有150頁\編于星期三\7點當(dāng)前第99頁\共有150頁\編于星期三\7點理論最優(yōu)解X*數(shù)值最優(yōu)解X*外點法當(dāng)前第100頁\共有150頁\編于星期三\7點三、內(nèi)點罰函數(shù)法(一)基本原理當(dāng)前第101頁\共有150頁\編于星期三\7點當(dāng)前第102頁\共有150頁\編于星期三\7點當(dāng)前第103頁\共有150頁\編于星期三\7點當(dāng)前第104頁\共有150頁\編于星期三\7點當(dāng)前第105頁\共有150頁\編于星期三\7點當(dāng)前第106頁\共有150頁\編于星期三\7點內(nèi)點罰函數(shù)法計算框圖當(dāng)前第107頁\共有150頁\編于星期三\7點當(dāng)前第108頁\共有150頁\編于星期三\7點當(dāng)前第109頁\共有150頁\編于星期三\7點四、混合罰函數(shù)法內(nèi)點形式的混合罰函數(shù)法當(dāng)前第110頁\共有150頁\編于星期三\7點可直接令注：初始迭代點應(yīng)在嚴(yán)格滿足不等式約束的區(qū)域內(nèi)。當(dāng)前第111頁\共有150頁\編于星期三\7點當(dāng)前第112頁\共有150頁\編于星期三\7點當(dāng)前第113頁\共有150頁\編于星期三\7點當(dāng)前第114頁\共有150頁\編于星期三\7點*§2－5MATLAB求解非線性規(guī)劃問題與應(yīng)用實例考慮如下約束優(yōu)化問題A—線性不等式約束的系數(shù)矩陣b—線性不等式約束的右端向量Aeq—線性等式約束的系數(shù)矩陣beq—線性等式約束的右端向量C(X)與Ceq(X)是非線性約束函數(shù)返回的向量。Lb與Ub是變量的上下限。當(dāng)前第115頁\共有150頁\編于星期三\7點x=fmincon(fun,x0,A,b,Aeq,beq,Lb,Ub,nonlcon)求解上述約束優(yōu)化問題的MATLAB函數(shù)非線性約束函數(shù)，需要定義外部函數(shù)，計算并返回C(X)與Ceq(X)向量當(dāng)前第116頁\共有150頁\編于星期三\7點例其中當(dāng)前第117頁\共有150頁\編于星期三\7點x=fmincon(fun,x0,A,b,Aeq,beq,Lb,Ub,nonlcon)在Matlab命令窗口中輸入》A=[-1-2-2;123]；》b=[0;72]；》x0=[10;10;10]；》[x,fval]=fmincon(‘-x(1)*x(2)*x(3)’,x0,A,b)結(jié)果：x*=[24,12,8]Tfval=-2.3040e+003當(dāng)前第118頁\共有150頁\編于星期三\7點例定義兩個外部函數(shù)，分別計算目標(biāo)函數(shù)值與約束函數(shù)值。約束函數(shù)化成標(biāo)準(zhǔn)形式目標(biāo)函數(shù)與約束函數(shù)均為非線性當(dāng)前第119頁\共有150頁\編于星期三\7點function[C,Ceq]=fcon(x)g1=1.5+x(1)*x(2)-x(1)-x(2);g2=-x(1)*x(2)-10;C=[g1;g2];Ceq=[];functiony=fobj(x)y=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);x=fmincon(fun,x0,A,b,Aeq,beq,Lb,Ub,nonlcon)當(dāng)前第120頁\共有150頁\編于星期三\7點當(dāng)前第121頁\共有150頁\編于星期三\7點當(dāng)前第122頁\共有150頁\編于星期三\7點[x,fevl]=fmincon(‘fobj’,x0,[],[],[],[],[],[],‘fcon’)得解：x*=[-9.5474,1.0474]T,f(x*)=0.0236x=fmincon(fun,x0,A,b,Aeq,beq,Lb,Ub,nonlcon)當(dāng)前第123頁\共有150頁\編于星期三\7點當(dāng)前第124頁\共有150頁\編于星期三\7點例與前題的區(qū)別：多了一個等式約束。當(dāng)前第125頁\共有150頁\編于星期三\7點function[C,Ceq]=fcon(x)g1=1.5+x(1)*x(2)-x(1)-x(2);g2=-x(1)*x(2)-10;C=[g1;g2];Ceq==-x(1)^2+x(2);functiony=fobj(x)y=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);[x,fevl]=fmincon(‘fobj’,x0,[],[],[],[],[],[],‘fcon’)得解：x*=[-1.1121,1.2367]T,f(x*)=1.9660當(dāng)前第126頁\共有150頁\編于星期三\7點>>[C,Ceq]=fcon(x)C=0-8.6246Ceq=0最優(yōu)解滿足等式約束，且在第一個不等式約束的邊界上。當(dāng)前第127頁\共有150頁\編于星期三\7點當(dāng)前第128頁\共有150頁\編于星期三\7點當(dāng)前第129頁\共有150頁\編于星期三\7點例與前題的區(qū)別：多了設(shè)計變量下限的約束。計算目標(biāo)函數(shù)與非線性約束函數(shù)值的外部函數(shù)不變。[x,fevl]=fmincon(‘fobj’,x0,[],[],[],[],Lb,[],‘fcon’)>>Lb=[-2;2];當(dāng)前第130頁\共有150頁\編于星期三\7點得解：最優(yōu)解x*=[-1.4142,2.000]T

最優(yōu)值f(x*)=2.3549[x,feval]=fmincon(‘fobj’,x0,[],[],[],[],Lb,[],‘fcon’)當(dāng)前第131頁\共有150頁\編于星期三\7點當(dāng)前第132頁\共有150頁\編于星期三\7點當(dāng)前第133頁\共有150頁\編于星期三\7點輪式車輛前輪轉(zhuǎn)向梯形四桿機(jī)構(gòu)的優(yōu)化設(shè)計后輪（驅(qū)動）前輪（轉(zhuǎn)向）直線行駛梯形轉(zhuǎn)向機(jī)構(gòu)一般輪式車輛多為后輪驅(qū)動，前輪導(dǎo)向。工程實例當(dāng)前第134頁\共有150頁\編于星期三\7點轉(zhuǎn)向中心Oαβ當(dāng)車輛繞轉(zhuǎn)向中心O作等角速轉(zhuǎn)向時，要求全部車輪作無側(cè)向滑動的純滾動。當(dāng)前第135頁\共有150頁\編于星期三\7點轉(zhuǎn)向臂θ0轉(zhuǎn)向臂連桿固連在一起，繞鉸點轉(zhuǎn)動θ0梯形機(jī)構(gòu)形狀改變，實現(xiàn)轉(zhuǎn)向當(dāng)前第136頁\共有150頁\編于星期三\7點轉(zhuǎn)向中心Oαβ

M

Lα與β分別為外導(dǎo)向輪、內(nèi)導(dǎo)向輪輪軸線之偏轉(zhuǎn)角。若取α為自變量，則β可由上式解出當(dāng)前第137頁\共有150頁\編于星期三\7點αβ

M問題描述：設(shè)計一梯形轉(zhuǎn)向機(jī)構(gòu)，當(dāng)α在一定范圍內(nèi)變動（0－30°）時，β能按式（1）變化轉(zhuǎn)向臂θ0轉(zhuǎn)向臂連桿當(dāng)前第138頁\共有150頁\編于星期三\7點θ0l1l2l3M取l1和θ0為設(shè)計參數(shù)，則l2不再獨立給定α，βp為多少？根據(jù)連桿長度l2不變來解出。αβpθ0當(dāng)前第139頁\共有150頁\編于星期三\7點αβpθ0外轉(zhuǎn)向臂與水平軸的夾角內(nèi)外轉(zhuǎn)向臂與水平軸的夾角θ1θ3根據(jù)連桿長度l2不變來解出當(dāng)前第140頁\共有150頁\編于星期三\7點αβpθ0θ1θ3當(dāng)前第141頁\共有150頁\編于星期三\7點希望的結(jié)果αβpθ0θ1θ3l1βα30°βEβ0α30°βEβp?β當(dāng)前第142頁\共有150頁\編于星期三\7點若將α的變化范圍分布很多等分點，如30個等分點α30°βEβ0?β要求在這些等分點上，βp與βE的差值小，于是，可構(gòu)造下面的函數(shù)θ0l1l2l3M當(dāng)前第143頁\共有150頁\編于星期三\7點受到