【文章內容簡介】 D( 5, 7) D( 6, 7) Row Slack or Surplus 1 2 3 4 5 6 7 運行結果 練習 1： A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 最優(yōu)路線為： A → B1 → C2 → D1 → E2 → F2 → G 路長 ＝ 18 求從 A到 G的最短路徑 3 有資金 4萬元，投資 A、 B、 C三個項目，每個項目的投資效益與投入該項目的資金有關。三個項目 A、 B、 C的投資效益（萬噸）和投入資金（萬元）關系見下表 ： 求對三個項目的最優(yōu)投資分配，使總投資效益最大。 練習 2 1. 階段 k：每投資一個項目作為一個階段； 2. 狀態(tài)變量 xk：投資第 k個項目前的資金數(shù)； 3. 決策變量 dk：第 k個項目的投資； 4. 決策允許集合： 0≤ dk≤ xk 5. 狀態(tài)轉移方程： xk+1=xkdk 6. 階段指標： vk(xk ,dk)見表中所示； 7. 遞推方程：fk(xk)=max{vk(xk ,dk)+fk+1(xk+1)} 8. 終端條件： f4(x4)=0 k=4， f4(x4)=0 k=3， 0≤d3≤x3， x4=x3d3 k=2， 0≤d2≤x2， x3=x2d2 k=1， 0≤d1≤x1， x2=x1d1 無約束最優(yōu)化問題 標準形式： ? ?Rm i n nX fX? 其中 1: R Rnf ? ? ?Rm a xnX fX? ? ? ?Rm i n [ ]nX fX? ?例 ： 選址問題 某市燃氣公司計劃要建一個煤氣供應站，該站要向城市中有固定位置的 m 個用戶供貨 .對于選定的坐標系而言，已知第 i 個用戶的位置為 如果只考慮直線距離，如何確定這個煤氣站的位置，才能使總的運輸距離最短 ？ 解：設煤氣站的位置為 則第 i 個用戶到 該站的直線距離為 故 m 個用戶到該站的總距離為 故選址問題可以歸結為求變量 使得 無約束優(yōu)化問題的解法 可微，則利用 求其駐點，然后利用充分條件判別這些駐點是否 是極值點。 . 2. 搜索算法（迭代算法） 基本思想 ： 首先給定目標函數(shù) 的極小點的一個初始估計點 然后按照一定的規(guī)則產生一個點列 ，希望這種點列的極限是的一個極小點 . 需要給定初始點 常見的算法 ： １．梯度法（最速下降法） 2. 牛頓法 用 MATLAB優(yōu)化工具箱求解無約束最優(yōu)化 計算機實現(xiàn) 前面我們介紹了 Matlab 工具箱中函數(shù)用 linprog解線性規(guī)劃的 方法， Matlab優(yōu)化工具箱還提供了一般無約束優(yōu)化與約束優(yōu)化 的求解問題，下面介紹 Matlab優(yōu)化工具箱的主要函數(shù)。 MATLAB優(yōu)化工具箱簡介 類 型 模 型 基本函數(shù)名 一元函數(shù)極小 m in F （ x ） . x1 x x 2 x=fmin bnd ( ‘ F ’ ,x1,x2) 無約束極小 m in F ( X ) X=fminu nc ( ‘ F ’ ,X0) X=fmins earch ( ‘ F ’ ,X0) 線性規(guī)劃 m in Xc T . AX ≤ b X=l inprog (c,A,b) 二次規(guī)劃 m in 21xTHx + cTx . Ax ≤ b X=q uad p rog (H,c, A,b) 約束極小 （非線性規(guī)劃） m in F ( X ) . G ( X ) ≤ 0 X= fmincon ( ‘ FG ’ ,X0) 達到目標問題 m in r . F ( x ) wr ≤ goal X= fgoalattain ( ‘ F ’ ,x, goal,w) 極小極大問題 m in m ax { F i ( x )} x { Fi( x )} . G ( x ) ≤ 0 X= f min i max( ‘ FG ’ ,x0) 使用優(yōu)化函數(shù)或優(yōu)化工具箱中其他優(yōu)化函數(shù)時 , 輸入變量見下表 : 變量 描 述 調用函數(shù) f 線性規(guī)劃的目標函數(shù) f X 或二次規(guī)劃的目標函數(shù) XT H X + f X 中線性項的系數(shù)向量 linprog,quadprog fun 非線性優(yōu)化的目標函數(shù) .f u n 必須為行命令對象或 M 文件、嵌入函數(shù)、或 MEX 文件的名稱 fminbnd,fminsearch,fminunc, fmincon ,lsqcurvefit,lsqnonli ,fgoalattain ,fminimax H 二次規(guī)劃的目標函數(shù) XT H X + f X 中二次項的系數(shù)矩陣 quadprog A,b A 矩陣和 b 向量分別為線性不等式約束：bAX ?中的系數(shù)矩陣和右端向量 linprog,quadprog ,fgoalattain , fmincon , fminimax Aeq,b eq Aeq 矩陣和 beq 向量分別為 線性等式約束： be qXA e q ??中的系數(shù)矩陣和右端向量 linprog,quadprog ,fgoalattain , fmincon , fminimax vlb,vub X 的下限和上限向量： vlb ≤ X ≤ vub linprog,quadp rog ,fgoalattain , fmincon ,fminimax,lsqcurvefit, lsqnonlin X0 迭代初始點坐標 除fminbnd 外所有優(yōu)化函數(shù) x1,x2 函數(shù)最小化的區(qū)間 fminbnd options 優(yōu)化選項參數(shù)結構，定義用于優(yōu)化函數(shù)的參數(shù) 所有優(yōu)化函數(shù) : 變量 描 述 調用函數(shù) x 由優(yōu)化函數(shù)求得的值 . 若 e xi t fl ag 0, 則 x為解 。 否則 , x 不是最終解 , 它只是迭代停 止時優(yōu)化過程的值 所有優(yōu)化函數(shù) fval 解 x 處的目標函數(shù)值 linpro g,qu adpr og ,f goal a ttain , fminco n ,fm inim ax,l sqcu r vefit, lsqnon lin , fmi nbnd exitfl ag 描述退出條件 : ? ex i tf la g 0, 表 示 目標函數(shù)收斂于解 x處 ? ex i tf la g =0, 表 示 已達到函數(shù)評價或迭代的最大次數(shù) ? ex i tf la g 0 , 表 示 目標函 數(shù)不收斂 output 包含優(yōu)化結果信息的輸出結構 . ? It e ra ti on s : 迭代次數(shù) ? Al g or it hm : 所采用的算法 ? Fu n cC ou nt : 函數(shù)評價次數(shù) 所有優(yōu)化函數(shù) : 變量 描 述 調用函數(shù) x 由優(yōu)化函數(shù)求得的值 . 若 e xi t fl ag 0, 則 x為解 。 否則 , x 不是最終解 , 它只是迭代停 止時優(yōu)化過程的值 所有優(yōu)化函數(shù) fval 解 x 處的目標函數(shù)值 linpro g,qu adpr og ,f goal a ttain , fminco n ,fm inim ax,l sqcu r vefit, lsqnon lin , fmi nbnd exitfl ag 描述退出條件 : ? ex i tf la g 0, 表 示 目標函數(shù)收斂于解 x處 ? ex i tf la g =0, 表 示 已達到函數(shù)評價或迭代的最大次數(shù) ? ex i tf la g 0 , 表 示 目標函 數(shù)不收斂 output 包含優(yōu)化結果信息的輸出結構 . ? It e ra ti on s : 迭代次數(shù) ? Al g or it hm : 所采用的算法 ? Fu n cC ou nt : 函數(shù)評價次數(shù) 所有優(yōu)化函數(shù) 4．控制參數(shù)選項的設置 (3) MaxIter: 允許進行迭代的最大次數(shù) ,取值為正整數(shù) . 選項中常用的幾個參數(shù)的名稱、含義、取值如下 : (1) 陳列 : 顯示水平 .取值為 39。off39。時 ,不顯示輸出 。 取值為 39。iter39。時 ,顯示每次迭代的信息 。取值為39。final39。時 ,顯示最終結果 .默認值為 39。final39。. (2) MaxFunEvals: 允許進行函數(shù)評價的最大次數(shù) ,取值為正整數(shù) . 例： opts=optimset(39。Display39。, 39。iter39。, 39。TolFun39。,1e8) 該語句創(chuàng)建一個稱為選擇的優(yōu)化選項結構 ,其中顯示參數(shù)設為 39。iter39。, TolFun參數(shù)設為 1e8. 控制參數(shù)選項可以通過函數(shù) optimset創(chuàng)建或修改 .命令的格式如下： (1) options=optimset(39。optimfun39。) 創(chuàng)建一個含有所有參數(shù)名 ,并與優(yōu)化函數(shù) optimfun相關的默認值的選項結構 . （ 2） options=optimset(39。param139。,value1,39。param239。,value2,...) 創(chuàng)建一個名稱為選項的優(yōu)化選項參數(shù) ,其中指定的參數(shù)具有指定值 ,所有未指定的參數(shù)取默認值 . (3) options= optimset(oldops, 39。param139。,value1,39。param239。,value2,...) 創(chuàng)建名稱為 oldops的參數(shù)的拷貝 ,用指定的參數(shù)值修改 oldops中相應的參數(shù) . 返回 用 MATLAB解無約束優(yōu)化問題 1. 一元函數(shù)無約束優(yōu)化問題 : mi n ()fx 21 xxx ?? 其中等式（ 3）、（ 4）、（ 5）的右邊可選用（ 1）或（ 2）的等式右邊 . 函數(shù) fminbnd的算法基于黃金分割法和二次插值法，它要求目標函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解 . 常用格式如下： （ 1） x= fminbnd (fun,x1,x2) （ 2） x= fminbnd (fun,x1,x2 ， options) （ 3） [x， fval]= fminbnd（ …） （ 4） [x， fval， exitflag]= fminbnd（ …） （ 5） [x， fval， exitflag， output]= fminbnd（ …） 運行結果： xm in = 3 .9 2 70 y mi n