數(shù)學(xué)建模無約束優(yōu)化

1、 優(yōu)化問題的數(shù)學(xué)模型優(yōu)化問題的數(shù)學(xué)模型 xf i 決策變量，目標(biāo)函數(shù)，g(x) 約束條件 可行解（只滿足可行解（只滿足(2)）與最優(yōu)解（滿足）與最優(yōu)解（滿足(1),(2)） 無約束優(yōu)化（只有無約束優(yōu)化（只有(1)）與約束優(yōu)化（）與約束優(yōu)化（(1),(2)） )2(, 2 , 1, 0)(. . )1 ()(min mixgts xfz i x 實(shí)際問題一般總有約束，何時可用無約束優(yōu)化處理？實(shí)際問題一般總有約束，何時可用無約束優(yōu)化處理？ 第五章第五章 無約束優(yōu)化模型無約束優(yōu)化模型 現(xiàn)實(shí)世界中普遍存在著優(yōu)化問題現(xiàn)實(shí)世界中普遍存在著優(yōu)化問題 靜態(tài)優(yōu)化問題指最優(yōu)解是數(shù)靜態(tài)優(yōu)化問題指最優(yōu)解是數(shù)(不是函數(shù)

2、不是函數(shù)) 建立靜態(tài)優(yōu)化模型的關(guān)鍵之一是根建立靜態(tài)優(yōu)化模型的關(guān)鍵之一是根 據(jù)建模目的確定恰當(dāng)?shù)哪繕?biāo)函數(shù)據(jù)建模目的確定恰當(dāng)?shù)哪繕?biāo)函數(shù) 求解靜態(tài)優(yōu)化模型一般用微分法求解靜態(tài)優(yōu)化模型一般用微分法 靜靜 態(tài)態(tài) 優(yōu)優(yōu) 化化 模模 型型 5.1 存貯模型存貯模型 問問 題題 已知某產(chǎn)品日需求量已知某產(chǎn)品日需求量100件，生產(chǎn)準(zhǔn)備費(fèi)件，生產(chǎn)準(zhǔn)備費(fèi)5000元，貯存費(fèi)元，貯存費(fèi) 每日每件每日每件1元。試安排該產(chǎn)品的生產(chǎn)計(jì)劃，即多少天生產(chǎn)元。試安排該產(chǎn)品的生產(chǎn)計(jì)劃，即多少天生產(chǎn) 一次（生產(chǎn)周期），每次產(chǎn)量多少，使總費(fèi)用最小。一次（生產(chǎn)周期），每次產(chǎn)量多少，使總費(fèi)用最小。 要要 求求 不只是回答問題，而且要建立生產(chǎn)

3、周期、產(chǎn)量與不只是回答問題，而且要建立生產(chǎn)周期、產(chǎn)量與 需求量、準(zhǔn)備費(fèi)、貯存費(fèi)之間的關(guān)系。需求量、準(zhǔn)備費(fèi)、貯存費(fèi)之間的關(guān)系。 配件廠為裝配線生產(chǎn)若干種產(chǎn)品，輪換產(chǎn)品時因更換設(shè)配件廠為裝配線生產(chǎn)若干種產(chǎn)品，輪換產(chǎn)品時因更換設(shè) 備要付生產(chǎn)準(zhǔn)備費(fèi)，產(chǎn)量大于需求時要付貯存費(fèi)。該廠備要付生產(chǎn)準(zhǔn)備費(fèi)，產(chǎn)量大于需求時要付貯存費(fèi)。該廠 生產(chǎn)能力非常大，即所需數(shù)量可在很短時間內(nèi)產(chǎn)出。生產(chǎn)能力非常大，即所需數(shù)量可在很短時間內(nèi)產(chǎn)出。 問題分析與思考問題分析與思考 每天生產(chǎn)一次每天生產(chǎn)一次，每次，每次100件，無貯存費(fèi)，準(zhǔn)備費(fèi)件，無貯存費(fèi)，準(zhǔn)備費(fèi)5000元。元。 日需求日需求100件，準(zhǔn)備費(fèi)件，準(zhǔn)備費(fèi)5000元，貯存

4、費(fèi)每日每件元，貯存費(fèi)每日每件1元。元。 10天生產(chǎn)一次天生產(chǎn)一次，每次，每次1000件，貯存費(fèi)件，貯存費(fèi)900+800+100 =4500 元，準(zhǔn)備費(fèi)元，準(zhǔn)備費(fèi)5000元，總計(jì)元，總計(jì)9500元。元。 50天生產(chǎn)一次天生產(chǎn)一次，每次，每次5000件，貯存費(fèi)件，貯存費(fèi)4900+4800+100 =122500元，準(zhǔn)備費(fèi)元，準(zhǔn)備費(fèi)5000元，總計(jì)元，總計(jì)127500元。元。 平均每天費(fèi)用平均每天費(fèi)用950元元 平均每天費(fèi)用平均每天費(fèi)用2550元元 1010天生產(chǎn)一次平均每天費(fèi)用最小嗎天生產(chǎn)一次平均每天費(fèi)用最小嗎? ? 每天費(fèi)用每天費(fèi)用5000元元 這是一個優(yōu)化問題，關(guān)鍵在建立目標(biāo)函數(shù)。這是一個優(yōu)化

5、問題，關(guān)鍵在建立目標(biāo)函數(shù)。 顯然不能用一個周期的總費(fèi)用作為目標(biāo)函數(shù)顯然不能用一個周期的總費(fèi)用作為目標(biāo)函數(shù) 目標(biāo)函數(shù)目標(biāo)函數(shù)每天總費(fèi)用的平均值每天總費(fèi)用的平均值 周期短，產(chǎn)量小周期短，產(chǎn)量小 周期長，產(chǎn)量大周期長，產(chǎn)量大 問題分析與思考問題分析與思考 貯存費(fèi)少，準(zhǔn)備費(fèi)多貯存費(fèi)少，準(zhǔn)備費(fèi)多 準(zhǔn)備費(fèi)少，貯存費(fèi)多準(zhǔn)備費(fèi)少，貯存費(fèi)多 存在最佳的周期和產(chǎn)量，使總費(fèi)用（二者之和）最小存在最佳的周期和產(chǎn)量，使總費(fèi)用（二者之和）最小 模模 型型 假假 設(shè)設(shè) 1. 產(chǎn)品每天的需求量為常數(shù)產(chǎn)品每天的需求量為常數(shù) r； 2. 每次生產(chǎn)準(zhǔn)備費(fèi)為每次生產(chǎn)準(zhǔn)備費(fèi)為 c1, 每天每件產(chǎn)品貯存費(fèi)為每天每件產(chǎn)品貯存費(fèi)為 c2；

6、3. T天生產(chǎn)一次（周期）天生產(chǎn)一次（周期）, 每次生產(chǎn)每次生產(chǎn)Q件，當(dāng)貯存量件，當(dāng)貯存量 為零時，為零時，Q件產(chǎn)品立即到來（生產(chǎn)時間不計(jì)）；件產(chǎn)品立即到來（生產(chǎn)時間不計(jì)）； 建建 模模 目目 的的 設(shè)設(shè) r, c1, c2 已知，求已知，求T, Q 使每天總費(fèi)用的平均值最小。使每天總費(fèi)用的平均值最小。 4. 為方便起見，時間和產(chǎn)量都作為連續(xù)量處理。為方便起見，時間和產(chǎn)量都作為連續(xù)量處理。 模模 型型 建建 立立 0t q 貯存量表示為時間的函數(shù)貯存量表示為時間的函數(shù) q(t) T Q r t=0生產(chǎn)生產(chǎn)Q件，件，q(0)=Q, q(t)以以 需求速率需求速率r遞減，遞減，q(T)=0. 一周

7、期一周期 總費(fèi)用總費(fèi)用 T Q ccC 2 21 每天總費(fèi)用平均每天總費(fèi)用平均 值（目標(biāo)函數(shù)）值（目標(biāo)函數(shù)） 2 )( 21 rTc T c T C TC 離散問題連續(xù)化離散問題連續(xù)化 Acdttqc T 2 0 2 )( 一周期貯存費(fèi)為一周期貯存費(fèi)為 A=QT/2 2 2 21 rT cc rTQ 模型求解模型求解 Min 2 )( 21 rTc T c TC求求 T 使使 0 dT dC 2 1 2 c rc rTQ 2 1 2 rc c T 模型分析模型分析 QTc, 1 QTc, 2 QTr, 模型應(yīng)用模型應(yīng)用c1=5000, c2=1，r=100 T=10(天天), Q=1000(件

8、件), C=1000(元元) 回答問題回答問題 經(jīng)濟(jì)批量訂貨公式經(jīng)濟(jì)批量訂貨公式（EOQ公式公式） 2 1 2 rc c T 2 1 2 c rc rTQ 每天需求量每天需求量 r，每次訂貨費(fèi)，每次訂貨費(fèi) c1,每天每件貯存費(fèi)每天每件貯存費(fèi) c2 ， 用于訂貨、供應(yīng)、存貯情形用于訂貨、供應(yīng)、存貯情形 不允許缺貨的存貯模型不允許缺貨的存貯模型 問：為什么不考慮生產(chǎn)費(fèi)用？在什么條件下才不考慮？問：為什么不考慮生產(chǎn)費(fèi)用？在什么條件下才不考慮？ T天訂貨一次天訂貨一次(周期周期), 每次訂貨每次訂貨Q件，當(dāng)貯存量降到件，當(dāng)貯存量降到 零時，零時，Q件立即到貨。件立即到貨。 允許缺貨的存貯模型允許缺貨的

9、存貯模型 A B 0 q Q r T1t 當(dāng)貯存量降到零時仍有需求當(dāng)貯存量降到零時仍有需求r, 出現(xiàn)缺貨，造成損失出現(xiàn)缺貨，造成損失 原模型假設(shè)：貯存量降到零時原模型假設(shè)：貯存量降到零時Q件件 立即生產(chǎn)出來立即生產(chǎn)出來(或立即到貨或立即到貨) 現(xiàn)假設(shè)：允許缺貨現(xiàn)假設(shè)：允許缺貨, 每天每件缺貨損失費(fèi)每天每件缺貨損失費(fèi) c3 , 缺貨需補(bǔ)足缺貨需補(bǔ)足 T 1 rTQ Acdttqc T 2 0 2 1 )( 一周期一周期 貯存費(fèi)貯存費(fèi) Bcdttqc T T 33 1 )( 一周期一周期 缺貨費(fèi)缺貨費(fèi) 周期周期T, t=T1貯存量降到零貯存量降到零 2 )( 2 2 1 3 1 21 TTr c

10、QT ccC 一周期總費(fèi)用一周期總費(fèi)用 rT QrTc rT Qc T c T C QTC 2 )( 2 ),( 2 3 2 21 0,0 Q C T C 每天總費(fèi)用每天總費(fèi)用 平均值平均值 （目標(biāo)函數(shù)）（目標(biāo)函數(shù)） 2 13121 )( 2 1 2 1 TTrcQTccC 一周期總費(fèi)用一周期總費(fèi)用 Min),(QTC求求 T ,Q 使使 3 32 2 1 2 c cc rc c T 32 3 2 1 2 cc c c rc Q 為與為與不允許缺貨的存貯模型不允許缺貨的存貯模型 相比，相比，T記作記作T , Q記作記作Q 2 1 2 rc c T 2 1 2 c rc rTQ 不允不允 許缺許

11、缺 貨模貨模 型型 Q QTT, 3 32 c cc 記記 1QQTT, 1 3 cQQTT , 3 32 2 1 2 c cc rc c T 32 3 2 1 2 cc c c rc Q 允許允許 缺貨缺貨 模型模型 不不 允允 許許 缺缺 貨貨 3 c 3 32 2 1 2 c cc rc c T 32 3 2 1 2 cc c c rc Q 允許允許 缺貨缺貨 模型模型 0 q Q r T1tT 注意：缺貨需補(bǔ)足注意：缺貨需補(bǔ)足 Q 每周期初的存貯量每周期初的存貯量 R 每周期的生產(chǎn)量每周期的生產(chǎn)量 R （或訂貨量）（或訂貨量） 3 32 2 1 2 c cc c rc TrR Q不允許

12、缺貨時的產(chǎn)量不允許缺貨時的產(chǎn)量(或訂貨量或訂貨量) QQR 5.2 森林救火森林救火 森林失火后，要確定派出消防隊(duì)員的數(shù)量。森林失火后，要確定派出消防隊(duì)員的數(shù)量。 隊(duì)員多，森林損失小，救援費(fèi)用大；隊(duì)員多，森林損失小，救援費(fèi)用大； 隊(duì)員少，森林損失大，救援費(fèi)用小。隊(duì)員少，森林損失大，救援費(fèi)用小。 綜合考慮損失費(fèi)和救援費(fèi)，確定隊(duì)員數(shù)量。綜合考慮損失費(fèi)和救援費(fèi)，確定隊(duì)員數(shù)量。 問題問題 分析分析 問題問題 記隊(duì)員人數(shù)記隊(duì)員人數(shù)x, 失火時刻失火時刻t=0, 開始救火時刻開始救火時刻t1, 滅火時刻滅火時刻t2, 時刻時刻t森林燒毀面積森林燒毀面積B(t). 損失費(fèi)損失費(fèi)f1(x)是是x的減函數(shù)的減函

13、數(shù), 由燒毀面積由燒毀面積B(t2)決定決定. 救援費(fèi)救援費(fèi)f2(x)是是x的增函數(shù)的增函數(shù), 由隊(duì)員人數(shù)和救火時間決定由隊(duì)員人數(shù)和救火時間決定. 存在恰當(dāng)?shù)拇嬖谇‘?dāng)?shù)膞，使，使f1(x), f2(x)之和最小之和最小 關(guān)鍵是對關(guān)鍵是對B(t)作出合理的簡化假設(shè)作出合理的簡化假設(shè). 問題問題 分析分析 失火時刻失火時刻t=0, 開始救火時刻開始救火時刻t1, 滅火時刻滅火時刻t2, 畫出時刻畫出時刻 t 森林燒毀面積森林燒毀面積B(t)的大致圖形的大致圖形 t1t20t B B(t2) 分析分析B(t)比較困難比較困難, 轉(zhuǎn)而討論森林燒毀轉(zhuǎn)而討論森林燒毀 速度速度dB/dt. 模型假設(shè)模型假設(shè)

14、 3）f1(x)與與B(t2)成正比，系數(shù)成正比，系數(shù)c1 (燒毀單位面積損失費(fèi)）燒毀單位面積損失費(fèi)） 1）0 t t1, dB/dt 與與 t成正比，系數(shù)成正比，系數(shù) (火勢蔓延速度）火勢蔓延速度） 2）t1 t t2, 降為降為 - x ( 為隊(duì)員的平均滅火為隊(duì)員的平均滅火速度）速度） 4）每個）每個隊(duì)員的單位時間滅火費(fèi)用隊(duì)員的單位時間滅火費(fèi)用c2, 一次性費(fèi)用一次性費(fèi)用c3 假設(shè)假設(shè)1） 的解釋的解釋 r B 火勢以失火點(diǎn)為中心，火勢以失火點(diǎn)為中心， 均勻向四周呈圓形蔓延，均勻向四周呈圓形蔓延， 半徑半徑 r與與 t 成正比成正比 面積面積 B與與 t2成正比，成正比， dB/dt與與

15、t成正比成正比. x b tt 12 2 2 0 ( ) t dB B tdt dt 模型建立模型建立 dt dB b 0 t1t t2 x 假設(shè)假設(shè)1） , 1 tb xcttxcxftBcxf 31222211 )()(),()( 目標(biāo)函數(shù)目標(biāo)函數(shù)總費(fèi)用總費(fèi)用)()()( 21 xfxfxC 假設(shè)假設(shè)3）4） x t tt 1 12 假設(shè)假設(shè)2） )(222 2 1 22 12 x ttbt 0 dx dC xc x xtc x tctc xC 3 12 2 1 2 1 2 11 )(22 )( 模型建立模型建立目標(biāo)函數(shù)目標(biāo)函數(shù)總費(fèi)用總費(fèi)用 模型求解模型求解求求 x使使 C(x)最小最小

16、2 3 12 2 11 2 2 c tctc x 結(jié)果解釋結(jié)果解釋 / 是火勢不繼續(xù)蔓延的最少隊(duì)員數(shù)是火勢不繼續(xù)蔓延的最少隊(duì)員數(shù) dt dB b 0t1t2t x 其中其中 c1,c2,c3, t1, , 為已知參數(shù)為已知參數(shù) 模型模型 應(yīng)用應(yīng)用 c1,c2,c3已知已知, t1可估計(jì)可估計(jì), c2 x c1, t1, x c3 , x 結(jié)果結(jié)果 解釋解釋 2 3 12 2 11 2 2 c tctc x c1燒毀單位面積損失費(fèi)燒毀單位面積損失費(fèi), c2每個每個隊(duì)員單位時間滅火費(fèi)隊(duì)員單位時間滅火費(fèi), c3每個每個隊(duì)員一次性費(fèi)用隊(duì)員一次性費(fèi)用, t1開始救火時刻開始救火時刻, 火火勢蔓延速度勢蔓

17、延速度, 每個每個隊(duì)員平均滅火隊(duì)員平均滅火速度速度. 為什么為什么? ? , 可可設(shè)置一系列數(shù)值設(shè)置一系列數(shù)值 由模型決定隊(duì)員數(shù)量由模型決定隊(duì)員數(shù)量x 無約束優(yōu)化問題的基本算法無約束優(yōu)化問題的基本算法 1 1最速下降法（共軛梯度法）最速下降法（共軛梯度法） 2 2牛頓法牛頓法 3 3擬牛頓法擬牛頓法 MatlabMatlab優(yōu)化工具箱簡介優(yōu)化工具箱簡介 1.MATLAB1.MATLAB求解優(yōu)化問題的主要函數(shù)求解優(yōu)化問題的主要函數(shù) 2. 2. 優(yōu)化函數(shù)的輸入變量優(yōu)化函數(shù)的輸入變量 使用優(yōu)化函數(shù)或優(yōu)化工具箱中其它優(yōu)化函數(shù)時, 輸入變量見下表: 3. 3. 優(yōu)化函數(shù)的輸出變量下表優(yōu)化函數(shù)的輸出變量下

18、表: : 變量描 述調(diào)用函數(shù) x 由優(yōu)化函數(shù)求得的值.若exitflag0,則x 為解;否則,x不是最終解,它只是迭代制止 時優(yōu)化過程的值 所有優(yōu)化函數(shù) fval解x處的目標(biāo)函數(shù)值 linprog,quadprog,fgoalattain, fmincon,fminimax,lsqcurvefit, lsqnonlin, fminbnd exitflag 描述退出條件: exitflag0,表目標(biāo)函數(shù)收斂于解x處 exitflag=0,表已達(dá)到函數(shù)評價或迭代 的最大次數(shù) exitflag0,表目標(biāo)函數(shù)不收斂 output 包含優(yōu)化結(jié)果信息的輸出結(jié)構(gòu). Iterations:迭代次數(shù) Algor

19、ithm:所采用的算法 FuncCount:函數(shù)評價次數(shù) 所有優(yōu)化函數(shù) 4 4控制參數(shù)控制參數(shù)optionsoptions的設(shè)置的設(shè)置 (3) MaxIterMaxIter: 允許進(jìn)行迭代的最大次數(shù),取值為正整數(shù). OptionsOptions中常用的幾個參數(shù)的名稱、含義、取值如下中常用的幾個參數(shù)的名稱、含義、取值如下: : (1)DisplayDisplay: 顯示水平.取值為off時,不顯示輸 出; 取值為iter時,顯示每次迭代的信息;取值 為final時,顯示最終結(jié)果.默認(rèn)值為final. (2)MaxFunEvalsMaxFunEvals: 允許進(jìn)行函數(shù)評價的最大次數(shù),取 值為正整數(shù)

20、. 例：例：opts=optimset(Display,iter,TolFun,1e-opts=optimset(Display,iter,TolFun,1e- 8)8) 該語句創(chuàng)建一個稱為該語句創(chuàng)建一個稱為optsopts的優(yōu)化選項(xiàng)結(jié)構(gòu)的優(yōu)化選項(xiàng)結(jié)構(gòu), ,其中顯示參數(shù)設(shè)其中顯示參數(shù)設(shè) 為為iter, TolFuniter, TolFun參數(shù)設(shè)為參數(shù)設(shè)為1e-8.1e-8. 控制參數(shù)控制參數(shù)optionsoptions可以通過函數(shù)可以通過函數(shù)optimsetoptimset創(chuàng)建或修改。命創(chuàng)建或修改。命 令的格式如下：令的格式如下： (1) options=optimset(optimfun)(

21、1) options=optimset(optimfun) 創(chuàng)建一個含有所有參數(shù)名創(chuàng)建一個含有所有參數(shù)名, ,并與優(yōu)化函數(shù)并與優(yōu)化函數(shù)optimfunoptimfun相關(guān)相關(guān) 的默認(rèn)值的選項(xiàng)結(jié)構(gòu)的默認(rèn)值的選項(xiàng)結(jié)構(gòu)options.options. （2 2） options=optimset(param1,value1,param2,value2,.)options=optimset(param1,value1,param2,value2,.) 創(chuàng)建一個名稱為創(chuàng)建一個名稱為optionsoptions的優(yōu)化選項(xiàng)參數(shù)的優(yōu)化選項(xiàng)參數(shù), ,其中指定的參數(shù)具有其中指定的參數(shù)具有 指定值指定值, ,所有未

22、指定的參數(shù)取默認(rèn)值所有未指定的參數(shù)取默認(rèn)值. . (3)options=optimset(oldops,param1,value1,param2,(3)options=optimset(oldops,param1,value1,param2, value2,.) value2,.) 創(chuàng)建名稱為創(chuàng)建名稱為oldopsoldops的參數(shù)的拷貝的參數(shù)的拷貝, ,用指定的參數(shù)值修改用指定的參數(shù)值修改oldopsoldops 中相應(yīng)的參數(shù)中相應(yīng)的參數(shù). . 用用MatlabMatlab解無約束優(yōu)化問題解無約束優(yōu)化問題 1. 一一元元函函數(shù)數(shù)無無約約束束優(yōu)優(yōu)化化問問題題: : min f（x） 21 xx

23、x 其中（其中（3 3）、（）、（4 4）、（）、（5 5）的等式右邊可選用（）的等式右邊可選用（1 1）或）或 （2 2）的等式右邊。）的等式右邊。 函數(shù)函數(shù)fminbndfminbnd的算法基于黃金分割法和二次插值法，它的算法基于黃金分割法和二次插值法，它 要求要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出，并可能只給出局部最優(yōu)解局部最優(yōu)解。 常用格式如下：常用格式如下： （1）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2) ) （2）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2 ，op

24、tions)options) （3）xx，fval= fminbndfval= fminbnd（.） （4）xx，fvalfval，exitflag= fminbndexitflag= fminbnd（.） （5）xx，fvalfval，exitflagexitflag，output= fminbndoutput= fminbnd（.） 運(yùn)行結(jié)果： xmin = 3.9270 ymin = -0.0279 xmax = 0.7854 ymax = 0.6448 To Matlab(wliti1) 例例1 1 求 f = 2xe x sin 在 0 x 0，且a11 a12； 同理， p2 = b2 - a21 x1- a22 x2 ，b2，a21，a22 0，且a22 a21 . 2 2成本與產(chǎn)量成負(fù)指數(shù)關(guān)系成本與產(chǎn)量成負(fù)指數(shù)關(guān)系 甲的成本隨其產(chǎn)量的增長而降低,且有一個漸進(jìn)值,可以假設(shè)為 負(fù)指數(shù)關(guān)系,即: 0, 111111 11 crcerq x 同理， 0, 222222 22 crcerq x 模型建立模型建立 若根據(jù)大量的統(tǒng)計(jì)數(shù)據(jù),求出系數(shù)b1=100,a11=1,a12=0.1,b2=280, a21=0.2,a22=2,r