Matlab的優(yōu)化工具箱.doc

9.1 概 述 利用Matlab的優(yōu)化工具箱，可以求解線性規(guī)劃、非線性規(guī)劃和多目標規(guī)劃問題。具體而言，包括線性、非線性最小化，最大最小化，二次規(guī)劃，半無限問題，線性、非線性方程（組）的求解，線性、非線性的最小二乘問題。另外，該工具箱還提供了線性、非線性最小化，方程求解，曲線擬合，二次規(guī)劃等問題中大型課題的求解方法，為優(yōu)化方法在工程中的實際應用提供了更方便快捷的途徑。9.1.1 優(yōu)化工具箱中的函數(shù) 優(yōu)化工具箱中的函數(shù)包括下面幾類： 1最小化函數(shù)表9-1 最小化函數(shù)表函 數(shù)描 述fgoalattain多目標達到問題fminbnd有邊界的標量非線性最小化fmincon有約束的非線性最小化fminimax最大最小化fminsearch, fminunc無約束非線性最小化fseminf半無限問題linprog線性課題quadprog二次課題2方程求解函數(shù)表9-2 方程求解函數(shù)表函 數(shù)描 述線性方程求解fsolve非線性方程求解fzero標量非線性方程求解3最小二乘（曲線擬合）函數(shù)表9-3 最小二乘函數(shù)表函 數(shù)描 述線性最小二乘lsqlin有約束線性最小二乘lsqcurvefit非線性曲線擬合lsqnonlin非線性最小二乘lsqnonneg非負線性最小二乘4實用函數(shù)表9-4 實用函數(shù)表函 數(shù)描 述optimset設置參數(shù)optimget 5大型方法的演示函數(shù)表9-5 大型方法的演示函數(shù)表函 數(shù)描 述circustent馬戲團帳篷問題二次課題molecule用無約束非線性最小化進行分子組成求解optdeblur用有邊界線性最小二乘法進行圖形處理6中型方法的演示函數(shù)表9-6 中型方法的演示函數(shù)表函 數(shù)描 述bandemo香蕉函數(shù)的最小化dfildemo過濾器設計的有限精度goaldemo目標達到舉例optdemo演示過程菜單tutdemo教程演示9.1.3 參數(shù)設置 利用optimset函數(shù)，可以創(chuàng)建和編輯參數(shù)結(jié)構(gòu)；利用optimget函數(shù)，可以獲得options優(yōu)化參數(shù)。 optimget函數(shù)功能：獲得options優(yōu)化參數(shù)。語法：val = optimget(options,param)val = optimget(options,param,default)描述：val = optimget(options,param) 返回優(yōu)化參數(shù)options中指定的參數(shù)的值。只需要用參數(shù)開頭的字母來定義參數(shù)就行了。val = optimget(options,param,default) 若options結(jié)構(gòu)參數(shù)中沒有定義指定參數(shù)，則返回缺省值。注意，這種形式的函數(shù)主要用于其它優(yōu)化函數(shù)。舉例：1 下面的命令行將顯示優(yōu)化參數(shù)options返回到my_options結(jié)構(gòu)中： val = optimget(my_options,Display)2 下面的命令行返回顯示優(yōu)化參數(shù)options到my_options結(jié)構(gòu)中（就象前面的例子一樣），但如果顯示參數(shù)沒有定義，則返回值final: optnew = optimget(my_options,Display,final);參見：optimset optimset函數(shù)功能：創(chuàng)建或編輯優(yōu)化選項參數(shù)結(jié)構(gòu)。語法：options = optimset(param1,value1,param2,value2,.)optimsetoptions = optimsetoptions = optimset(optimfun)options = optimset(oldopts,param1,value1,.)options = optimset(oldopts,newopts)描述：options = optimset(param1,value1,param2,value2,.) 創(chuàng)建一個稱為options的優(yōu)化選項參數(shù)，其中指定的參數(shù)具有指定值。所有未指定的參數(shù)都設置為空矩陣（將參數(shù)設置為表示當options傳遞給優(yōu)化函數(shù)時給參數(shù)賦缺省值）。賦值時只要輸入?yún)?shù)前面的字母就行了。optimset函數(shù)沒有輸入輸出變量時，將顯示一張完整的帶有有效值的參數(shù)列表。options = optimset (with no input arguments) 創(chuàng)建一個選項結(jié)構(gòu)options，其中所有的元素被設置為。options = optimset(optimfun) 創(chuàng)建一個含有所有參數(shù)名和與優(yōu)化函數(shù)optimfun相關(guān)的缺省值的選項結(jié)構(gòu)options。options = optimset(oldopts,param1,value1,.) 創(chuàng)建一個oldopts的拷貝，用指定的數(shù)值修改參數(shù)。options = optimset(oldopts,newopts) 將已經(jīng)存在的選項結(jié)構(gòu)oldopts與新的選項結(jié)構(gòu)newopts進行合并。newopts參數(shù)中的所有元素將覆蓋oldopts參數(shù)中的所有對應元素。舉例： 1下面的語句創(chuàng)建一個稱為options的優(yōu)化選項結(jié)構(gòu)，其中顯示參數(shù)設為iter，TolFun參數(shù)設置為1e-8: options = optimset(Display,iter,TolFun,1e-8) 2下面的語句創(chuàng)建一個稱為options的優(yōu)化結(jié)構(gòu)的拷貝，改變TolX參數(shù)的值，將新值保存到optnew參數(shù)中: optnew = optimset(options,TolX,1e-4); 3下面的語句返回options優(yōu)化結(jié)構(gòu)，其中包含所有的參數(shù)名和與fminbnd函數(shù)相關(guān)的缺省值： options = optimset(fminbnd) 4若只希望看到fminbnd函數(shù)的缺省值，只需要簡單地鍵入下面的語句就行了： optimset fminbnd 或者輸入下面的命令，其效果與上面的相同： optimset(fminbnd)參見：optimget9.1.4 模型輸入時需要注意的問題使用優(yōu)化工具箱時，由于優(yōu)化函數(shù)要求目標函數(shù)和約束條件滿足一定的格式，所以需要用戶在進行模型輸入時注意以下幾個問題：1.目標函數(shù)最小化優(yōu)化函數(shù)fminbnd、fminsearch、fminunc、fmincon、fgoalattain、fminmax和lsqnonlin都要求目標函數(shù)最小化，如果優(yōu)化問題要求目標函數(shù)最大化，可以通過使該目標函數(shù)的負值最小化即-f(x)最小化來實現(xiàn)。近似地，對于quadprog函數(shù)提供-H和-f，對于linprog函數(shù)提供-f。2.約束非正優(yōu)化工具箱要求非線性不等式約束的形式為Ci(x)0，通過對不等式取負可以達到使大于零的約束形式變?yōu)樾∮诹愕牟坏仁郊s束形式的目的，如Ci(x)0形式的約束等價于- Ci(x)0；Ci(x)b形式的約束等價于- Ci(x)+b0。3.避免使用全局變量 9.1.5 （函數(shù)句柄）函數(shù) MATLAB6.0中可以用函數(shù)進行函數(shù)調(diào)用。函數(shù)返回指定MATLAB函數(shù)的句柄，其調(diào)用格式為： handle = function利用函數(shù)進行函數(shù)調(diào)用有下面幾點好處： 用句柄將一個函數(shù)傳遞給另一個函數(shù)； 減少定義函數(shù)的文件個數(shù)； 改進重復操作； 保證函數(shù)計算的可靠性。下面的例子為humps函數(shù)創(chuàng)建一個函數(shù)句柄，并將它指定為fhandle變量。 fhandle = humps;同樣傳遞句柄給另一個函數(shù)，也將傳遞所有變量。本例將剛剛創(chuàng)建的函數(shù)句柄傳遞給fminbnd函數(shù)，然后在區(qū)間0.3,1上進行最小化。x = fminbnd (humps, 0.3, 1)x = 0.63709.2 最小化問題9.2.1 單變量最小化9.2.1.1 基本數(shù)學原理本節(jié)討論只有一個變量時的最小化問題，即一維搜索問題。該問題在某些情況下可以直接用于求解實際問題，但大多數(shù)情況下它是作為多變量最優(yōu)化方法的基礎(chǔ)在應用，因為進行多變量最優(yōu)化要用到一維搜索法。該問題的數(shù)學模型為： 其中，x,x1,和x2為標量，f(x)為函數(shù)，返回標量。該問題的搜索過程可用下式表達：其中xk為本次迭代的值，d為搜索方向，為搜索方向上的步長參數(shù)。所以一維搜索就是要利用本次迭代的信息來構(gòu)造下次迭代的條件。求解單變量最優(yōu)化問題的方法有很多種，根據(jù)目標函數(shù)是否需要求導，可以分為兩類，即直接法和間接法。直接法不需要對目標函數(shù)進行求導，而間接法則需要用到目標函數(shù)的導數(shù)。1直接法常用的一維直接法主要有消去法和近似法兩種。（1）消去法 該法利用單峰函數(shù)具有的消去性質(zhì)進行反復迭代，逐漸消去不包含極小點的區(qū)間，縮小搜索區(qū)間，直到搜索區(qū)間縮小到給定的允許精度為止。一種典型的消去法為黃金分割法(Golden Section Search)。黃金分割法的基本思想是在單峰區(qū)間內(nèi)適當插入兩點，將區(qū)間分為三段，然后通過比較這兩點函數(shù)值的大小來確定是刪去最左段還是最右段，或同時刪去左右兩段保留中間段。重復該過程使區(qū)間無限縮小。插入點的位置放在區(qū)間的黃金分割點及其對稱點上，所以該法稱為黃金分割法。該法的優(yōu)點是算法簡單，效率較高，穩(wěn)定性好。（2）多項式近似法 該法用于目標函數(shù)比較復雜的情況。此時尋找一個與它近似的函數(shù)代替目標函數(shù)，并用近似函數(shù)的極小點作為原函數(shù)極小點的近似。常用的近似函數(shù)為二次和三次多項式。二次內(nèi)插涉及到形如下式的二次函數(shù)數(shù)據(jù)擬合問題： 其中步長極值為：然后只要利用三個梯度或函數(shù)方程組就可以確定系數(shù)a和b，從而可以確定*。得到該值以后，進行搜索區(qū)間的收縮。在縮短的新區(qū)間中，重新安排三點求出下一次的近似極小點*，如此迭代下去，直到滿足終止準則為止。其迭代公式為：其中 二次插值法的計算速度比黃金分割法的快，但是對于一些強烈扭曲或可能多峰的函數(shù)，該法的收斂速度會變得很慢，甚至失敗。2間接法 間接法需要計算目標函數(shù)的導數(shù)，優(yōu)點是計算速度很快。常見的間接法包括牛頓切線法、對分法、割線法和三次插值多項式近似法等。優(yōu)化工具箱中用得較多的是三次插值法。三次插值的基本思想與二次插值的一致，它是用四個已知點構(gòu)造一個三次多項式P3(x)，用它逼近函數(shù)f(x)，以P3(x)的極小點作為f(x)的近似極小點。一般講，三次插值法比二次插值法的收斂速度要快些，但每次迭代需要計算兩個導數(shù)值。三次插值法的迭代公式為其中 如果函數(shù)的導數(shù)容易求得，一般來說首先考慮使用三次插值法，因為它具有較高的效率。對于只需要計算函數(shù)值的方法中，二次插值法是一個很好的方法，它的收斂速度較快，尤其在極小點所在區(qū)間較小時尤其如此。黃金分割法則是一種十分穩(wěn)定的方法，并且計算簡單。由于以上原因，Matlab優(yōu)化工具箱中使用得較多的方法是二次插值法、三次插值法、二次、三次混合插值法和黃金分割法。9.2.1.2 相關(guān)函數(shù)介紹fminbnd功能：找到固定區(qū)間內(nèi)單變量函數(shù)的最小值。語法：x = fminbnd(fun,x1,x2)x = fminbnd(fun,x1,x2,options)x = fminbnd(fun,x1,x2,options,P1,P2,.)x,fval = fminbnd(.)x,fval,exitflag = fminbnd(.)x,fval,exitflag,output = fminbnd(.)描述：fminbnd求取固定區(qū)間內(nèi)單變量函數(shù)的最小值。x = fminbnd(fun,x1,x2)返回區(qū)間x1，x2上fun參數(shù)描述的標量函數(shù)的最小值x。x = fminbnd(fun,x1,x2,options)用options參數(shù)指定的優(yōu)化參數(shù)進行最小化。x = fminbnd(fun,x1,x2,options,P1,P2,.)提供另外的參數(shù)P1,P2等,傳輸給目標函數(shù)fun。如果沒有設置options選項，則令options=。x,fval = fminbnd(.)返回解x處目標函數(shù)的值。x,fval,exitflag = fminbnd(.)返回exitflag值描述fminbnd函數(shù)的退出條件。x,fval,exitflag,output = fminbnd(.)返回包含優(yōu)化信息的結(jié)構(gòu)輸出。變量：函數(shù)的輸入變量在表9-7中進行描述，輸出變量在表9-8中描述。與fminbnd函數(shù)相關(guān)的細節(jié)內(nèi)容包含在fun,options,exitflag和output等參數(shù)中，如表9-10所示。表9-10 參數(shù)描述表參 數(shù)描 述fun需要最小化的目標函數(shù)。fun函數(shù)需要輸入標量參數(shù)x，返回x處的目標函數(shù)標量值f?？梢詫un函數(shù)指定為命令行，如 x = fminbnd(inline(sin(x*x),x0)同樣，fun參數(shù)可以是一個包含函數(shù)名的字符串。對應的函數(shù)可以是M文件、內(nèi)部函數(shù)或MEX文件。若fun=myfun，則M文件函數(shù)myfun.m必須右下面的形式。 function f = myfun(x) f = . %計算x處的函數(shù)值。options優(yōu)化參數(shù)選項。你可以用optimset函數(shù)設置或改變這些參數(shù)的值。options參數(shù)有以下幾個選項：l Display 顯示的水平。選擇off，不顯示輸出；選擇iter，顯示每一步迭代過程l 的輸出；選擇final，顯示最終結(jié)果。 MaxFunEvals 函數(shù)評價的最大允許次數(shù)。l MaxIter 最大允許迭代次數(shù)。l TolX x處的終止容限。 exitflag描述退出條件:l 0 表示目標函數(shù)收斂于解x處。l 0 表示已經(jīng)達到函數(shù)評價或迭代的最大次數(shù)。l 0 表示目標函數(shù)不收斂。output該參數(shù)包含下列優(yōu)化信息：l output.iterations 迭代次數(shù)。l output.algorithm 所采用的算法。l output.funcCount 函數(shù)評價次數(shù)。算法：fminbnd是一個M文件。其算法基于黃金分割法和二次插值法。文獻1中給出了實現(xiàn)同樣算法的Fortran程序。局限性： 1目標函數(shù)必須是連續(xù)的。2fminbnd函數(shù)可能只給出局部最優(yōu)解。3當問題的解位于區(qū)間邊界上時，fminbnd函數(shù)的收斂速度常常很慢。此時，fmincon函數(shù)的計算速度更快，計算精度更高。4fminbnd函數(shù)只用于實數(shù)變量。參見：fminsearch, fmincon, fminunc, optimset, inline文獻：1 Forsythe, G.E., M.A. Malcolm, and C.B. Moler, Computer Methods for Mathematical Computations, Prentice Hall, 1976.9.2.1.3 應用實例例一 在區(qū)間（0，2）上求函數(shù)sin(x)的最小值：x = fminbnd(sin,0,2*pi)x = 4.7124所以區(qū)間（0，2）上函數(shù)sin(x)的最小值點位于x=4.7124處。最小值處的函數(shù)值為：y = sin(x)y = -1.0000 磁盤中該問題的M文件名為opt21_1.m。 例三 對邊長為3m的正方形鐵板，在四個角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？ 假設剪去的正方形的邊長為x，則水槽的容積為 現(xiàn)在要求在區(qū)間（0，1.5）上確定一個x，使 最大化。因為優(yōu)化工具箱中要求目標函數(shù)最小化，所以需要對目標函數(shù)進行轉(zhuǎn)換，即要求 最小化。首先編寫M文件opt21_3o.m:function f = myfun(x)f = -(3-2*x).2 * x;然后調(diào)用fminbnd函數(shù)(磁盤中M文件名為opt21_3.m)：x = fminbnd(opt21_3o,0,1.5)得到問題的解：x = 0.5000即剪掉的正方形的邊長為0.5m時水槽的容積最大。水槽的最大容積計算：y = optim2(x)y = -2.0000 所以水槽的最大容積為2.0000m3。9.2.2 線性規(guī)劃9.2.2.1 基本數(shù)學原理線性規(guī)劃是處理線性目標函數(shù)和線性約束的一種較為成熟的方法，目前已經(jīng)廣泛應用于軍事、經(jīng)濟、工業(yè)、農(nóng)業(yè)、教育、商業(yè)和社會科學等許多方面。線性規(guī)劃問題的標準形式是：或?qū)懗删仃囆问綖椋浩渲校?為n維列向量。線性規(guī)劃的標準形式要求目標函數(shù)最小化，約束條件取等式，變量非負。不符合這幾個條件的線性模型要首先轉(zhuǎn)化成標準形。線性規(guī)劃的求解方法主要是單純形法（Simple Method），該法由Dantzig于1947年提出，以后經(jīng)過多次改進。單純形法是一種迭代算法，它從所有基本可行解的一個較小部分中通過迭代過程選出最優(yōu)解。其迭代過程的一般描述為：1 將線性規(guī)劃化為典范形式，從而可以得到一個初始基本可行解x(0)(初始頂點)，將它作為迭代過程的出發(fā)點，其目標值為z(x(0)。2 尋找一個基本可行解x(1)，使z(x(1)z(x(0)。方法是通過消去法將產(chǎn)生x(0)的典范形式化為產(chǎn)生x(1)的典范形式。3 繼續(xù)尋找較好的基本可行解x(2)，x(3)，使目標函數(shù)值不斷改進，即z(x(1)z(x(2) z(x(3) 。當某個基本可行解再也不能被其它基本可行解改進時，它就是所求的最優(yōu)解。 Matlab優(yōu)化工具箱中采用的是投影法，它是單純形法的一種變種。9.2.2.2 相關(guān)函數(shù)介紹linprog函數(shù)功能：求解線性規(guī)劃問題。 數(shù)學模型： 其中f, x, b, beq, lb和ub為向量，A 和Aeq為矩陣。語法：x = linprog(f,A,b,Aeq,beq)x = linprog(f,A,b,Aeq,beq,lb,ub)x = linprog(f,A,b,Aeq,beq,lb,ub,x0)x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)x,fval = linprog(.)x,fval,exitflag = linprog(.)x,fval,exitflag,output = linprog(.)x,fval,exitflag,output,lambda = linprog(.)描述：x = linprog(f,A,b)求解問題 min f*x，約束條件為A*x = b。x = linprog(f,A,b,Aeq,beq)求解上面的問題，但增加等式約束，即Aeq*x = beq。若沒有不等式存在，則令A=、b=。x = linprog(f,A,b,Aeq,beq,lb,ub)定義設計變量x的下界lb和上界ub，使得x始終在該范圍內(nèi)。若沒有等式約束，令Aeq=、beq=。x = linprog(f,A,b,Aeq,beq,lb,ub,x0)設置初值為x0。該選項只適用于中型問題，缺省時大型算法將忽略初值。x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)用options指定的優(yōu)化參數(shù)進行最小化。x,fval = linprog(.) 返回解x處的目標函數(shù)值fval。x,lambda,exitflag = linprog(.)返回exitflag值，描述函數(shù)計算的退出條件。x,lambda,exitflag,output = linprog(.) 返回包含優(yōu)化信息的輸出變量output。x,fval,exitflag,output,lambda = linprog(.) 將解x處的拉格朗日乘子返回到lambda參數(shù)中。變量：lambda參數(shù) lambda參數(shù)是解x處的拉格朗日乘子。它有以下一些屬性：l lambda.lower lambda的下界。l lambda.upper lambda的上界。l lambda.ineqlin lambda的線性不等式。l lambda.eqlin lambda的線性等式。其它參數(shù)意義同前。算法：大型優(yōu)化算法 大型優(yōu)化算法采用的是LIPSOL法，該法在進行迭代計算之前首先要進行一系列的預處理。中型優(yōu)化算法 linprog函數(shù)使用的是投影法，就象quadprog函數(shù)的算法一樣。linprog函數(shù)使用的是一種活動集方法，是線性規(guī)劃中單純形法的變種。它通過求解另一個線性規(guī)劃問題來找到初始可行解。診斷：大型優(yōu)化問題 算法的第一步涉及到一些約束條件的預處理問題。有些問題可能導致linprog函數(shù)退出，并顯示不可行的信息。在本例中，exitflag參數(shù)將被設為負值以表示優(yōu)化失敗。若Aeq參數(shù)中某行的所有元素都為零，但Beq參數(shù)中對應的元素不為零，則顯示以下退出信息： Exiting due to infeasibility: an all zero row in the constraint matrix does not have a zero in corresponding right hand size entry.若x的某一個元素沒在界內(nèi)，則給出以下退出信息： Exiting due to infeasibility: objective f*x is unbounded below.若Aeq參數(shù)的某一行中只有一個非零值，則x中的相關(guān)值稱為奇異變量。這里，x中該成分的值可以用Aeq和Beq算得。若算得的值與另一個約束條件相矛盾，則給出以下退出信息： Exiting due to infeasibility: Singleton variables in equality constraints are not feasible.若奇異變量可以求解但其解超出上界或下界，則給出以下退出信息： Exiting due to infeasibility: singleton variables in the equality constraints are not within bounds.9.2.2.3 應用實例 例二 生產(chǎn)決策問題某廠生產(chǎn)甲乙兩種產(chǎn)品，已知制成一噸產(chǎn)品甲需用資源A 3噸，資源B 4m3；制成一噸產(chǎn)品乙需用資源A 2噸，資源B 6m3，資源C 7個單位。若一噸產(chǎn)品甲和乙的經(jīng)濟價值分別為7萬元和5萬元，三種資源的限制量分別為90噸、200m3和210個單位，試決定應生產(chǎn)這兩種產(chǎn)品各多少噸才能使創(chuàng)造的總經(jīng)濟價值最高？ 令生產(chǎn)產(chǎn)品甲的數(shù)量為x1，生產(chǎn)產(chǎn)品乙的數(shù)量為x2。由題意可以建立下面的模型：該模型中要求目標函數(shù)最大化，需要按照Matlab的要求進行轉(zhuǎn)換，即目標函數(shù)為首先輸入下列系數(shù)：f = -7;-5;A = 3 2 4 6 0 7;b = 90; 200; 210;lb = zeros(2,1);然后調(diào)用linprog函數(shù)：x,fval,exitflag,output,lambda = linprog(f,A,b,lb)x = 14.0000 24.0000fval = -218.0000exitflag = 1output = iterations: 5 cgiterations: 0 algorithm: lipsollambda = ineqlin: 3x1 double eqlin: 0x1 double upper: 2x1 double lower: 2x1 double 由上可知，生產(chǎn)甲種產(chǎn)品14噸、乙種產(chǎn)品24噸可使創(chuàng)建的總經(jīng)濟價值最高。最高經(jīng)濟價值為218萬元。exitflag=1表示過程正常收斂于解x處。磁盤中本問題的M文件為opt22_2.m。例三 投資問題某單位有一批資金用于四個工程項目的投資，用于各工程項目時所得到得凈收益（投入資金的百分比）如下表所示：表9-11 工程項目收益表工 程 項 目ABCD收益（%）1510812由于某種原因，決定用于項目A的投資不大于其它各項投資之和；而用于項目B和C的投資要大于項目D的投資。試確定使該單位收益最大的投資分配方案。用x1、x2、x3和x4分別代表用于項目A、B、C和D的投資百分數(shù)，由于各項目的投資百分數(shù)之和必須等于100%，所以 x1+x2+x3+x4=1據(jù)題意，可以建立下面的數(shù)學模型：將它轉(zhuǎn)換為標準形式：然后進行求解：首先輸入下列系數(shù)：f = -0.15;-0.1;-0.08;-0.12;A = 1 -1 -1 -1 0 -1 -1 1;b = 0; 0;Aeq=1 1 1 1;beq=1;lb = zeros(4,1);然后調(diào)用linprog函數(shù)：x,fval,exitflag,output,lambda = linprog(f,A,b,Aeq,beq,lb)；x = 0.5000 0.2500 0.0000 0.2500fval = -0.1300exitflag = 1可見，四個項目的投資百分數(shù)分別為0.50、0.25、0.00和0.25時可使該單位獲得最大的收益。最大收益為13%。過程正常收斂。磁盤中本問題的M文件為opt22_3.m。例四 工件加工任務分配問題某車間有兩臺機床甲和乙，可用于加工三種工件。假定這兩臺機床的可用臺時數(shù)分別為700和800，三種工件的數(shù)量分別為300、500和400，且已知用三種不同機床加工單位數(shù)量的不同工件所需的臺時數(shù)和加工費用（如表 所示），問怎樣分配機床的加工任務，才能既滿足加工工件的要求，又使總加工費用最低？表9-12 機床加工情況表機床類型單位工作所需加工臺時數(shù)單位工件的加工費用可用臺時數(shù)工件1工件2工件3工件1工件2工件3甲0.41.11.013910700乙0.51.21.311128800設在甲機床上加工工件1、2和3的數(shù)量分別為x1、x2和x3，在乙機床上加工工件1、2和3的數(shù)量分別為x4、x5和x6。根據(jù)三種工種的數(shù)量限制，有x1+x4=300 (對工件1)x2+x5=500 (對工件2)x3+x6=400 (對工件3) 再根據(jù)機床甲和乙的可用總臺時限制，可以得到其它約束條件。以總加工費用最少為目標函數(shù)，組合約束條件，可以得到下面的數(shù)學模型：首先輸入下列系數(shù)：f = 13;9;10;11;12;8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 700; 800;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=300 500 400;lb = zeros(6,1);然后調(diào)用linprog函數(shù)：x,fval,exitflag,output,lambda = linprog(f,A,b,Aeq,beq,lb);x = 0.0000 500.0000 0.0000 300.0000 0.0000 400.0000fval = 1.1000e+004exitflag = 1可見，在甲機床上加工500個工件2，在乙機床上加工300個工件1、加工400個工件3可在滿足條件的情況下使總加工費最小。最小費用為11000元。收斂正常。磁盤中本問題的M文件為opt22_4.m。例五 裁料問題 在某建筑工程施工中需要制作10000套鋼筋，每套鋼筋由2.9m、2.1m和1.5m三種不同長度的鋼筋各一根組成，它們的直徑和材質(zhì)不同。目前在市場上采購到的同類鋼筋的長度每根均為7.4m，問應購進多少根7.4m長的鋼筋才能滿足工程的需要？ 首先分析共有多少種不同的套裁方法，該問題的可能材料方案如表9-13所示。表9-13 材料方案表下料長度(m)裁 料 方 案 編 號 i123456782.9211100002.1021032101.510130234料頭長度(m)0.10.30.901.10.20.81.4 設以xi(i=1,2,8)表示按第i種裁料方案下料的原材料數(shù)量，則可得該問題的數(shù)學模型為：首先輸入下列系數(shù)：f = 1;1;1;1;1;1;1;1;Aeq=2 0 0 0 0 0 0 0 0 2 1 0 3 2 1 0 1 0 1 3 0 2 3 4;beq=10000 10000 10000;lb = zeros(8,1);然后調(diào)用linprog函數(shù)：x,fval,exitflag,output,lambda = linprog(f,Aeq,beq,lb);x = 1.0e+003 * 5.0000 0.0000 0.0000 0.0000 1.6667 2.5000 0.0000 0.0000fval = 9.1667e+003 所以最節(jié)省的情況需要9167根7.4m長的鋼筋，其中第一種方案使用5000根，第五種方案使用1667根，第六種方案使用2500根。磁盤中本問題的M文件為opt22_5.m。例六 工作人員計劃安排問題某晝夜服務的公共交通系統(tǒng)每天各時間段（每4小時為一個時間段）所需的值班人數(shù)如表 所示，這些值班人員在某一時段開始上班后要連續(xù)工作8個小時（包括輪流用膳時間），問該公交系統(tǒng)至少需要多少名工作人員才能滿足值班的需要？表9-14 各時段所需值班人數(shù)表班 次時 間 段所 需 人 數(shù)16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030 設xi為第i個時段開始上班的人員數(shù)，據(jù)題意建立下面的數(shù)學模型：需要對前面六個約束條件進行形式變換，是不等式為非正不等式。只需要在不等式兩側(cè)取負即可。首先輸入下列系數(shù)：f = 1;1;1;1;1;1;A=-1 0 0 0 0 -1 -1 -1 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 -1;b=-60;-70;-60;-50;-20;-30;lb = zeros(6,1);然后調(diào)用linprog函數(shù)：x,fval,exitflag,output,lambda = linprog(f,A,b,lb);x = 41.9176 28.0824 35.0494 14.9506 9.8606 20.1394fval = 150.0000exitflag = 1可見，只要六個時段分別安排42人、28人、35人、15人、10人和20人就可以滿足值班的需要。共計150人。計算收斂。磁盤中本問題的M文件為opt22_6.m。例七 廠址選擇問題 考慮A、B、C三地，每地都出產(chǎn)一定數(shù)量的原料，也消耗一定數(shù)量的產(chǎn)品（見表9-15）。已知制成每噸產(chǎn)品需3噸原料，各地之間的距離為：A-B：150km，A-C：100km，B-C：200km。假定每萬噸原料運輸1km的運價是5000元，每萬噸產(chǎn)品運輸1km的運價是6000元。由于地區(qū)條件的差異，在不同地點設廠的生產(chǎn)費用也不同。問究竟在哪些地方設廠，規(guī)模多大，才能使總費用最??？另外，由于其它條件限制，在B處建廠的規(guī)模（生產(chǎn)的產(chǎn)品數(shù)量）不能超過5萬噸。表9-15 A、B、C三地出產(chǎn)原料、消耗產(chǎn)品情況表地點年產(chǎn)原料（萬噸）年銷產(chǎn)品（萬噸）生產(chǎn)費用（萬元/萬噸）A207150B1613120C240100 令xij為由i地運到j地的原料數(shù)量（萬噸），yij為由i地運往j地的產(chǎn)品數(shù)量（萬噸），i,j=1,2,3（分別對應A、B、C三地）。根據(jù)題意，可以建立問題的數(shù)學模型（其中目標函數(shù)包括原材料運輸費、產(chǎn)品運輸費和生產(chǎn)費）：首先輸入下列系數(shù)：f = 75;75;50;50;100;100;150;240;210;120;160;220;A=1 -1 1 -1 0 0 3 3 0 0 0 0 -1 1 0 0 1 -1 0 0 3 3 0 0 0 0 -1 1 -1 1 0 0 0 0 3 3 0 0 0 0 0 0 0 0 1 1 0 0;b=20;16;24;5;Aeq=0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1;beq=7;13;lb = zeros(12,1);然后調(diào)用linprog函數(shù)：x,fval,exitflag,output,lambda = linprog(f,A,b,Aeq,beq,lb);x = 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 7.0000 0.0000 0.0000 5.0000 0.0000 8.0000fval = 3.4850e+003exitflag = 1要使總費用最小，需要B地向A地運送1萬噸，A、B、C三地的建廠規(guī)模分別為7萬噸、5萬噸和8萬噸。最小總費用為3485元。磁盤中本問題的M文件為opt22_7.m。例八 確定職工編制問題 某廠每日八小時的產(chǎn)量不低于1800件。為了進行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標準為：速度 25件/小時，正確率 98%，計時工資 4元/小時；二級檢驗員的標準為：速度 15件/小時，正確率 95%，計時工資 3元/小時。檢驗員每錯檢一次，工廠要損失2元。現(xiàn)有可供廠方聘請的檢驗員人數(shù)為一級8人和二級10人。為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各多少名？ 設需要一級和二級檢驗員的人數(shù)分別為x1名和x2名，由題意可以建立下面的模型：利用Matlab進行求解之前需要將第三個約束條件進行轉(zhuǎn)換，兩邊取負以后得到首先輸入下列系數(shù)：f = 40;36;A=1 0 0 1 -5 -3;b=8;10;-45;lb = zeros(2,1);然后調(diào)用linprog函數(shù)：x,fval,exitflag,output,lambda = linprog(f,A,b,lb);x = 8.0000 1.6667fval = 380.0000exitflag = 1 可見，招聘一級檢驗員8名、二級檢驗員2名可使總檢驗費最省，約為380.00元。計算收斂。磁盤中本問題的M文件為opt22_8.m。 例九 生產(chǎn)計劃的最優(yōu)化問題 某工廠生產(chǎn)A和B兩種產(chǎn)品，它們需要經(jīng)過三種設備的加工，其工時如表9-16所示。設備一、二和三每天可使用的時間分別不超過12、10和8小時。產(chǎn)品A和B的利潤隨市場的需求有所波動，如果預測未來某個時期內(nèi)A和B的利潤分別為4和3千元/噸，問在那個時期內(nèi)，每天應安排產(chǎn)品A、B各多少噸，才能使工廠獲利最大？表9-16 生產(chǎn)產(chǎn)品工時表產(chǎn) 品設備一設備二設備三A（小時/噸）334B（小時/噸）432設備每天最多可工作時數(shù)（小時）12108 設每天應安排生產(chǎn)產(chǎn)品A和B分別為x1噸和x2噸，由題意建立下面的數(shù)學模型：首先轉(zhuǎn)換目標函數(shù)為標準形式：輸入下列系數(shù)：f = -4;-3;A=3 4 3 3 4 2;b=12;10;8;lb = zeros(2,1);然后調(diào)用linprog函數(shù)：x,fval,exitflag,output,lambda = linprog(f,A,b,lb);x = 0.8000 2.4000fval = -10.4000所以，每天生產(chǎn)A產(chǎn)品0.80噸、B產(chǎn)品2.40噸可使工廠獲得最大利潤。磁盤中本問題的M文件為opt22_9.m。9.2.3 無約束非線性規(guī)劃問題9.2.3.1 基本數(shù)學原理無約束最優(yōu)化問題在實際應用中也比較常見，如工程中常見的參數(shù)反演問題。另外，許多有約束最優(yōu)化問題可以轉(zhuǎn)化為無約束最優(yōu)化問題進行求解。求解無約束最優(yōu)化問題的方法主要有兩類，即直接搜索法（Search method）和梯度法（Gradient method）。直接搜索法適用于目標函數(shù)高度非線性，沒有導數(shù)或?qū)?shù)很難計算的情況，由于實際工程中很多問題都是非線性的，直接搜索法不失為一種有效的解決辦法。常用的直接搜索法為單純形法，此外還有Hooke-Jeeves搜索法、Pavell共軛方向法等，其缺點是收斂速度慢。在函數(shù)的導數(shù)可求的情況下，梯度法是一種更優(yōu)的方法，該法利用函數(shù)的梯度（一階導數(shù)）和Hessian矩陣（二階導數(shù)）構(gòu)造算法，可以獲得更快的收斂速度。函數(shù)f(x)的負梯度方向-f(x)即反映了函數(shù)的最大下降方向。當搜索方向取為負梯度方向時稱為最速下降法。當需要最小化的函數(shù)有一狹長的谷形值域時，該法的效率很低，如Rosenbrock函數(shù) f(x)=100(x1-x22)2+(1-x1)2它的最小值解為x=1,1，最小值為f(x)=0。下圖是該函數(shù)的等值線圖，圖中還顯示了從初值-1.9，2出發(fā)向最小值前進的路徑。迭代1000次以后終止，此時距最小值仍有相當長的距離。圖中的黑色區(qū)域是該法在谷的兩側(cè)不斷進行“之”字形搜索形成的。圖9-1 香蕉函數(shù)的等值線圖及最速下降法的搜索路徑這種類型的函數(shù)又稱為香蕉函數(shù)。常見的梯度法有最速下降法、Newton法、Marquart法、共軛梯度法和擬牛頓法（Quasi-Newton method）等。在所有這些方法中，用得最多的是擬牛頓法，這些方法在每次迭代過程中建立曲率信息，構(gòu)成下式得二次模型問題：其中，Hessian矩陣H為一正定對稱矩陣，c為常數(shù)向量，b為常數(shù)。對x求偏導數(shù)可以獲得問題的最優(yōu)解解x*可寫作：擬牛頓法包括兩個階段，即 確定搜索方向 一維搜索階段1Hessian矩陣的更新牛頓法由于需要多次計算Hessian矩陣，計算量很大，而擬牛頓法則通過構(gòu)建一個Hessian矩陣的近似矩陣來避開這個問題。在優(yōu)化工具箱中，通過將options參數(shù)HessUpdate設置為BFGS或DFP來決定搜索方向。當Hessian矩陣H始終保持正定時，搜索方向就總是保持為下