【正文】 1221 2 1 2 2( ) ( 4 2 4 2 1 ) e xf x x x x x x? ? ? ? ? ?*非線性規(guī)劃的基本解法 非線性規(guī)劃的基本概念 非線性規(guī)劃 返回 定義 如果目標函數(shù)或約束條件中至少有一個是非線性函數(shù) ,則最優(yōu)化問題就叫做 非線性規(guī)劃問題 ． 非現(xiàn)性規(guī)劃的基本概念 一般形式 : （ 1） 其中 ， 是定義在 Rn 上的實值函數(shù)，簡記 : ? ?Xfm in ji hgf , 其它情況 : 求目標函數(shù)的最大值，或約束條件小于等于零兩種情況，都可通過取其相反數(shù)化為上述一般形式． 1 n j 1 n i 1 n R : h ,R : g ,R : R R R f ? ? ? ? ? n T n R x x x X ? ? , , , 2 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? . ,..., 2 , 1 0 m。 M文件 : x0 = [1, 1]。dfp39。 (默認值 ),使用大型算法 LargeScale=‘off39。,0,)。2*exp(x).*sin (x)39。,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 = 0 . 027 9 xm ax = 0 .7 854 ym ax = 0 . 644 8 MATLAB(wliti1) 例 1 求 f = 2 e si nx x? 在 0 x 8 中的最小值與最大值 . 主程序為 : f=39。,value2,...) 創(chuàng)建一個名稱為選項的優(yōu)化選項參數(shù) ,其中指定的參數(shù)具有指定值 ,所有未指定的參數(shù)取默認值 . (3) options= optimset(oldops, 39。) 創(chuàng)建一個含有所有參數(shù)名 ,并與優(yōu)化函數(shù) optimfun相關的默認值的選項結構 . （ 2） options=optimset(39。,1e8) 該語句創(chuàng)建一個稱為選擇的優(yōu)化選項結構 ,其中顯示參數(shù)設為 39。, 39。時 ,顯示最終結果 .默認值為 39。iter39。 否則 , 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。 練習 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)化問題的解法 可微，則利用 求其駐點，然后利用充分條件判別這些駐點是否 是極值點。 ENDDATA F(SIZE(CITIES))=0。 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 (最短路線為 B1→ C1 → D) d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 (最短路線為 B2→ C1 → D) 第三階段（ A → B ）： A 到 B 有二條路線。 例一、從 A 地到 D 地要鋪設一條煤氣管道 ,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。 確定狀態(tài)轉移方程 根據(jù) k 階段狀態(tài)變量和決策變量，寫出 k+1階段狀態(tài)變量，狀態(tài)轉移方程應當具有遞推關系。 對于靜態(tài)問題要人為地賦予 “ 時間 ” 概念 ， 以便劃分階段 。 不僅跟當前狀態(tài) sk有關 ， 還跟該子過程策略pk,n(sk)有關 ， 表示為 : ,( ( ) )k n k n kV p s 適于用動態(tài)規(guī)劃求解的問題的過程指標函數(shù)（ 即目標函數(shù) ） ， 必須具有關于階段指標的可分離形式 ． 對于部子過程的指標函數(shù)可以表示為： , , 1 , 1 , 1( ( ) ) ( , , ( ( ) ) )k n k n k k k k k n k n kV p s s u V p s? ? ? ?? (2) ,11 , 1 , 1( ( ) ( , )( , ) ( , )( , ) ( ( )nk n k n k i i iiknk k k i i iikk k k k n k n kV p s v s uv s u v s uv s u V p s???? ? ????????多階段決策問題中，常見的目標函數(shù)形式之 一是取各階段效應之和的形式，即 : (七 ) 最優(yōu)解 用 fk(sk)表示第 k子過程指標函數(shù)在狀態(tài) sk下的最優(yōu)值 ,即 相應的子策略稱為 sk狀態(tài)下的最優(yōu)子策略 ， 記 為 pk,n*(sk) ；而構成該子策賂的各段決策稱為該 過程上的最優(yōu)決策 ， 記為 ； 有 , , , ,()( ) { ( ( ) ) } ( * ( ) ) ,1 , 2, ,k n k n kk k k n k n k k n k n kp P sf s o p t V p s V p skn????)(,),(),( 11 nnkkkk sususu ??? ?? ?,1{ , , , } , 1 , 2 , ,k n k k np u u u k n? ? ? ???? 最優(yōu)化原理 （ 貝爾曼最優(yōu)化原理 ） 作為一個全過程的最優(yōu)策略具有這樣的性質：對于最優(yōu)策略過程中的任意狀態(tài)而言 ， 無論其過去的狀態(tài)和決策如何 ， 余下的諸決策必構成一個最優(yōu)子策略 。 例如：圖 1的指標就是運費 。 在實際問題中 ， 由于在各個階段可供選擇的決策有許多個 ， 因此 ， 它們的不同組合就構成了許多可供選擇的決策序列 (策略 )， 由它們組成的集合 ，稱之 允許策略集合 ， 記作 P1,n ， 從允許策略集中 ，找出具有最優(yōu)效果的策略稱為 最優(yōu)策略 。 決策變量 uk(sk)的允許決策集用 Uk(sk)表示 , uk(sk)∈ Uk(sk)允許決策集合實際是決策的約束條件 。 通?？赡軤顟B(tài)集用相應階段狀態(tài) sk的大寫字母 Sk表示 ，sk∈ Sk， 可能狀態(tài)集可以是一離散取值的集合 ，也可以為一連續(xù)的取值區(qū)間 ． 在圖 1所示的最短路問題中 ， 第一階段狀態(tài)為 v1， 狀態(tài)變量 s1的狀態(tài)集合 S1={v1}；第二階段則有三個狀態(tài)：v2 ,v3 ,v4 , 狀 態(tài) 變 量 s2 的 狀 態(tài) 集 合S2={v2 ,v3 ,v4} ； 第 三 階 段 也 有 三 個 狀態(tài) :v5 ,v6 ,v7 ， 狀態(tài)變量 s3 的狀態(tài)集合S3={v5 ,v6 ,v7} ；第四階段則有二個狀態(tài)： v8 ,v9 , 狀態(tài)變量 s4的狀態(tài)集合 S4={v8 ,v9} ； （ 三 ） 決策 所謂 決策 ， 就是確定系統(tǒng)過程發(fā)展的方案 。 但為了清楚起見 ， 通常定義階段的狀態(tài)即指其初始狀態(tài) 。 用以描述事物 (或系統(tǒng) )在某特定的時間與空間域中所處位置及運動特征的量 ， 稱為狀態(tài) 。 四、動態(tài)規(guī)劃的基本概念與基本方程 使用動態(tài)規(guī)劃方法解決多階段決策問題 ， 首先要將實際問題寫成動態(tài)規(guī)劃模型 ， 同時也為了今后敘述和討論方便 ，這里需要對動態(tài)規(guī)劃的下述一些基本術語進一步加以說明和定義 ： (一 ) 階段 為了便于求解和表示決策及過程的發(fā)展順序 ， 而把所給問題恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題 ， 稱之為多段決策問題的階段 。 綜上所述可見 ， 全枚舉法雖可找出最優(yōu)方案 ，但不是個好算法 ， 局部最優(yōu)法則完