優(yōu)化模型實訓

提要12幾類典型優(yōu)化問題及其軟件解法3舉例4最優(yōu)化概論MATLAB優(yōu)化工具箱簡介最優(yōu)化概論當今，“優(yōu)化”無疑是一個熱門詞。做宏觀經濟規(guī)劃要優(yōu)化資源配置，搞企業(yè)經營管理要優(yōu)化生產計劃，作新產品設計要優(yōu)化性能成本比。就是在人們的日常生活中，優(yōu)化的要求也比比皆是，消費時，如何花盡可能少的錢辦盡可能多的事，出行時，如何走最短的路程到達目的地，等等?？偠灾诮洕绱税l(fā)展，競爭如此劇烈，資源日漸緊張的今天，人們做任何事，無不望求事半功倍之術，以求或提效、或增收、或節(jié)約等等之目標。一、最優(yōu)化概念所有類似的這種課題統(tǒng)稱為最優(yōu)化問題，研究解決這些問題的科學一般就總稱之為最優(yōu)化理論和方法另外也可用學術味更濃的名稱：“運籌學”。由于最優(yōu)化問題背景十分廣泛，涉及的知識不盡相同，學科分枝很多，因此這個學科名下到底包含哪些分枝，其說法也不一致。比較公認的是：“規(guī)劃論”（包括線性和非線性規(guī)劃、整數規(guī)劃、動態(tài)規(guī)劃、多目標規(guī)劃和隨機規(guī)劃等），“組合最優(yōu)化”，“對策論”及“最優(yōu)控制”等等。數學建模競賽中的優(yōu)化問題2000B鋼管訂購和運輸問題—二次規(guī)劃2001B公交車優(yōu)化調度2001C基金使用的最優(yōu)策略-----線性規(guī)劃2002B彩票中的數學2003B露天礦生產的車輛安排問題

2004A奧運會臨時超市網點設計問題

2004D公務員招聘工作中錄用方案—多目標規(guī)劃2005BDVD在線租賃2006A出版社的資源配置問題

2007A乘公交，看奧運

2008B高等教育學費探討2009B眼科病床的合理安排

數學建模競賽中的優(yōu)化問題2002B，彩票中的數學—約束非線性規(guī)劃從數學上來看，所謂最優(yōu)化問題可以概括為這樣一種數學模型：給定一個“函數”，F(X)，以及“自變量”X應滿足的一定條件，求X為怎樣的值時，F(X)取得其最大值或最小值。通常，稱F(X)為“目標函數”，X應滿足的條件為“約束條件”。約束條件一般用一個集合D表示為：X∈D。求目標函數F(X)在約束條件X∈D下的最小值或最大值問題，就是一般最優(yōu)問題的數學模型．無約束最優(yōu)化問題目標函數二、最優(yōu)化問題的一般形式約束最優(yōu)化問題約束函數最優(yōu)解；最優(yōu)值三、最優(yōu)化問題分類分類1：無約束最優(yōu)化約束最優(yōu)化

非線性規(guī)劃：目標函數與約束函數中至少有一個是變量x的非線性函數；

線性規(guī)劃：目標函數與約束函數均為線性函數；分類2：線性規(guī)劃非線性規(guī)劃三、最優(yōu)化問題分類(續(xù)）分類3（根據決策變量、目標函數和要求不同）整數規(guī)劃動態(tài)規(guī)劃網絡規(guī)劃隨機規(guī)劃幾何規(guī)劃多目標規(guī)劃三、最優(yōu)化問題分類(續(xù)）函數最優(yōu)化組合最優(yōu)化分類４函數最優(yōu)化：決策變量是一定區(qū)間內的連續(xù)變量．組合最優(yōu)化：決策變量是離散狀態(tài)，同時可行域是由有限個點組成的集合典型組合優(yōu)化問題：旅行商問題；加工調度問題；0-1背包問題；圖著色問題四、求解最優(yōu)化問題的方法（1）傳統(tǒng)優(yōu)化方法-----基于導數的優(yōu)化方法

無約束規(guī)劃：梯度法、共軛梯度法、擬牛頓法

約束規(guī)劃：序列二次規(guī)劃法，罰函數法

線性規(guī)劃：單純形方法等（2）現代優(yōu)化方法-----智能優(yōu)化方法

遺傳算法，模擬退火法，蟻群算法，粒子群算法神經網絡算法，禁忌搜索算法等

為了使系統(tǒng)達到最優(yōu)的目標所提出的各種求解方法稱為最優(yōu)化方法。最優(yōu)化方法通常采用迭代法求最優(yōu)解，過程是：五、構造數值優(yōu)化算法的一般過程或迭代公式六、最優(yōu)化方法的基本結構七、搜索算法結構框圖線性搜索求，使x(k+1)∈S初始x(1)∈S,k=1對x(k)點選擇下降可行方向d(k)是否滿足停機條件？停k=k+1YesNo八、最優(yōu)化方法解決問題的步驟（1）確定變量，寫出目標函數和有關約束條件，建立數學模型。（2）分析模型，搞清它屬于運籌學哪一分枝，選擇合適的最優(yōu)化方法；（3）編程求解；盡量利用現有的數學軟件或最優(yōu)化軟件，比如Matlab，Mathematica，Lindo，Lingo等，來計算。（4）最優(yōu)解的驗證和實施。九、MATLAB優(yōu)化工具箱簡介

1.功能（1）求解無約束條件非線性極小值；（2）求解約束條件下非線性極小值，包括目標逼近問題、極大-極小值問題和半無限極小值問題；（3）求解二次規(guī)劃和線性規(guī)劃問題；（4）非線性最小二乘逼近和曲線擬合；（5）非線性系統(tǒng)的方程求解；（6）約束條件下的線性最小二乘優(yōu)化；（7）求解復雜結構的大規(guī)模優(yōu)化問題。2.常用函數：

一元函數極小值X=fminbnd(‘F’,x1,x2,options)無約束極小值X=fminunc(‘F’,X0,options)X=fminsearch(‘F’,X0,options)線性規(guī)劃

X=linprog(c,A,b,options)0-1整數規(guī)劃X=bintprog(F

,options)二次規(guī)劃X=quadprog(H,c,A,b,options)約束非線性規(guī)劃極小值X=fmincon(‘FG’,X0,options)非線性最小二乘X=lsqnonlin(F,X0,options)目標達到問題X=fgoalattain(‘F’,x,goal,w)極小極大問題X=fminimax(‘FG’,x0)3.Options選項說明輸入參數中可以用options，用于所有函數，其中包括有一下參數。（1）Display：結果顯示方式，off不顯示，iter顯示每次迭代的信息，final為最終結果，notify只有當求解不收斂的時候才顯示結果。（2）MaxFunEvals：允許函數計算的最大次數，取值為正整數。（3）MaxIter：允許迭代的最大次數，正整數。（4）TolFun：函數值（計算結果）精度，正整數。（5）TolX：自變量的精度，正整數。而且可以用函數optimset創(chuàng)建和修改。4.輸出變量說明變量描述調用函數x由優(yōu)化函數求得的值.若exitflag>0,則x為解;否則,x不是最終解,它只是迭代制止時優(yōu)化過程的值所有優(yōu)化函數fval解x處的目標函數值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin,fminbndexitflag描述退出條件:exitflag>0,表目標函數收斂于解x處exitflag=0,表已達到函數評價或迭代的最大次數exitflag<0,表目標函數不收斂output包含優(yōu)化結果信息的輸出結構.Iterations:迭代次數Algorithm:所采用的算法FuncCount:函數評價次數所有優(yōu)化函數eg1

在區(qū)間（0，2π）上求函數sin(x)的最小值：eg2

對邊長為3m的正方形鐵板，在四個角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？學會使用fminbnd函數:功能：找到固定區(qū)間內單變量函數的最小值。線性規(guī)劃問題及其MATLAB解法1.線性規(guī)劃的一般形式或線性規(guī)劃問題及其MATLAB解法2.線性規(guī)劃的matlab解法問題形式1：minz=CTx

S.t.Ax

≤b指令：（x，z）=linprog(f,A,b)問題形式2：minz=CTx

S.t.Ax

≤b

Aeqx

=beq指令：（x，z）=linprog(f,A,b,Aeq,beq)線性規(guī)劃問題及其MATLAB解法問題形式3：minz=CTx

S.t.Ax

≤b

Aeqx

=beqlb≤x≤ub指令：（x，z）=linprog(f,A,b,Aeq,beq,lb,ub)注：

若沒有不等式約束,可用[]替代A和b,

若沒有等式約束,可用[]替代Aeq和beq,

若某個xi下無界或上無界,可設定-inf或inf；x1+x2

5,-6

x1

10,

-1

x24;例:minZ=4x1

+3x2s.t.解：程序如下c=[4,3];a=[1,1];b=[5];vlb=[-6;-1];

%lowerboundofvector

x%vub=[10;4];%upperboundofvectorx%[X,z]=linprog(c,a,b,[],[],vlb,vub)例題：裁料問題在某建筑工程施工中需要制作10000套鋼筋，每套鋼筋由2.9m、2.1m和1.5m三種不同長度的鋼筋各一根組成，它們的直徑和材質不同。目前在市場上采購到的同類鋼筋的長度每根均為7.4m，問應購進多少根7.4m長的鋼筋才能滿足工程的需要？

首先分析共有多少種不同的套裁方法，該問題的可能材料方案如表所示。表

材料方案表下料長度(m)裁料方案編號i123456782.9211100002.1021032101.510130234料頭長度(m)0.10.30.901.10.20.81.4設以xi(i=1,2,…,8)表示按第i種裁料方案下料的原材料數量，則可得該問題的數學模型為：首先輸入下列系數：f=[1;1;1;1;1;1;1;1];Aeq=[200000000210321010130234];beq=[100001000010000];lb=zeros(8,1);然后調用linprog函數：[x,fval,exitflag,output,lambda]=linprog(f,[],[],Aeq,beq,lb);習題1：生產計劃的最優(yōu)化問題某工廠生產A和B兩種產品，它們需要經過三種設備的加工，其工時如表所示。設備一、二和三每天可使用的時間分別不超過12、10和8小時。產品A和B的利潤隨市場的需求有所波動，如果預測未來某個時期內A和B的利潤分別為4和3千元/噸，問在那個時期內，每天應安排產品A、B各多少噸，才能使工廠獲利最大？表生產產品工時表產品設備一設備二設備三A（小時/噸）334B（小時/噸）432設備每天最多可工作時數（小時）12108習題2：廠址選擇問題

考慮A、B、C三地，每地都出產一定數量的原料，也消耗一定數量的產品（見表）。已知制成每噸產品需3噸原料，各地之間的距離為：A-B：150km，A-C：100km，B-C：200km。假定每萬噸原料運輸1km的運價是5000元，每萬噸產品運輸1km的運價是6000元。由于地區(qū)條件的差異，在不同地點設廠的生產費用也不同。問究竟在哪些地方設廠，規(guī)模多大，才能使總費用最??？另外，由于其它條件限制，在B處建廠的規(guī)模（生產的產品數量）不能超過5萬噸。表

A、B、C三地出產原料、消耗產品情況表地點年產原料（萬噸）年銷產品（萬噸）生產費用（萬元/萬噸）A207150B1613120C240100

1.整數線性規(guī)劃一般形式依照決策變量取整要求的不同，整數規(guī)劃可分為純整數規(guī)劃、混合整數規(guī)劃、0－1整數規(guī)劃。整數線性規(guī)劃(ILP)及其lindo解法部分或者全部為整數多目標規(guī)劃及其求解方法多目標規(guī)劃的一般形式則稱為線性多目標規(guī)劃。其中x=(x1,x2,…,xn)為一個n維向量；fi(x)為目標函數，hj(x)

gi(x)為約束函數。求解多目標規(guī)劃的方法1、降維法，即把多目標化為比較容易求解的單目標或雙目標，如主要目標法、線性加權法、極大極小法、理想點法等；2、分層序列法，即把目標按其重要性給出一個序列，每次都在前一目標最優(yōu)解集內求下一個目標最優(yōu)解，直到求出共同的最優(yōu)解。3、層次分析法，是由美國運籌學家沙旦于70年代提出的，這是一種定性與定量相結合的多目標決策與分析方法，對于目標結構復雜且缺乏必要的數據的情況更為實用。主要目標法

其基本思想是：在多目標問題中，根據問題的實際情況，確定一個目標為主要目標，而把其余目標作為次要目標，并且根據經驗，選取一定的界限值。這樣就可以把次要目標作為約束來處理，于是就將原來的多目標問題轉化為一個在新的約束下的單目標最優(yōu)化問題。

線性加權法

其基本思想是：按照多目標fi(x)(i=1,2,…,m)的重要程度，分別乘以一組權系數λj(j=1,2,…,m)然后相加作為目標函數而構成單目標規(guī)劃問題。即其中極大極小法

其基本思想是：對于極小化的多目標規(guī)劃，讓其中最大的目標函數值盡可能地小.為此，對每個x∈R，我們先求諸目標函數值fi(x)的最大值，然后再求這些最大值中的最小值。即構造單目標規(guī)劃：

為權值系數向量。于是多目標規(guī)劃問題化為：

理想點法

對于多目標規(guī)劃：

s.tgj(x)≤0j=1,2,…,n先設計與目標函數相應的一組目標值理想化向量

再設γ為一松弛因子標量。設

在Matlab的優(yōu)化工具箱中，fgoalattain函數用于解決此類問題。其數學模型形式為：

minγ F(x)-weight·γ≤goal c(x)≤0非線性不等式約束

ceq(x)=0非線性等式約束

Ax≤b線性不等式約束

Aeqx=beq

線性等式約束

lb≤x≤ub

其中，x,weight,goal,b,beq,lb和ub為向量，A和Aeq為矩陣，c(x),ceq(x)和F(x)為函數調用格式：x=fgoalattain(F,x0,goal,weight)[x,fval,attainfactor,exitflag,output,lambda]=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options)說明：F為目標函數；x0為初值；goal為F達到的指定目標；weight為參數指定權重；A、b為線性不等式約束的矩陣與向量；Aeq、beq為等式約束的矩陣與向量；lb、ub為變量x的上、下界向量；nonlcon為定義非線性不等式約束函數c(x)和等式約束函數ceq(x)；options中設置優(yōu)化參數。x返回最優(yōu)解；fval返回解x處的目標函數值；attainfactor返回解x處的目標達到因子；exitflag描述計算的退出條件；output返回包含優(yōu)化信息的輸出參數；lambda返回包含拉格朗日乘子的參數。例1：

投資組合模型市場上有n種資產Si(i=1,2,…,n)可以選擇，現用數額為M的相當大的資金作一個時期的投資。財務人員分析估算出這一時期內購買Si的平均收益率為ri

,風險損失率為qi,在多項投資組合中，總體風險可用投資的Si中最大的一個風險來度量。購買Si時要付交易費，費率pi(不買無須付費).當購買額不超過給定值ui時，交易費按購買ui計算.另外，假定同期銀行存款利率是r0,既無交易費又無風險。(r0=5%)SiriqipiuiS1282.51103S2211.52198S3235.54.552S4252.66.540試給該公司設計一種投資組合方案，即用給定達到資金M,有選擇地購買若干種資產或存銀行生息，使凈收益盡可能大，使總體風險盡可能小。已知n=4時的相關數據如下:基本假設1.投資數額M相當大,為了便于計算，假設M=1;2.投資越分散，總的風險越??；3.總體風險Si用投資項目中最大的一個風險來度量；4.n種資產Si之間是相互獨立的；5.在投資的這一時期內,ri,pi,qi,r0為定值，不受意外因素影響；6.凈收益和總體風險只受ri,pi,qi影響，不受其他因素干擾。符號規(guī)定Si——第i種投資項目，如股票，債券ri

,pi,qi

——分別為Si的平均收益率,風險損失率，交易費率ui

——Si的交易定額,r0——同期銀行利率xi——投資項目Si的資金,a——投資風險度Q——總體收益,?Q——總體收益的增量

模型的建立與分析1.總體風險用所投資的Si中最大的一個風險來衡量,即max{qixi|i=1，2,…n}2．購買Si所付交易費是一個分段函數,即

pixixi>ui

交易費=

piui

xi≤ui而題目所給定的定值ui(單位:元)相對總投資M很小,piui更小,可以忽略不計,這樣購買Si的凈收益為(ri-pi)xi凈收益盡可能大建立模型總體風險盡可能小多目標規(guī)劃問題采用主要目標法化為單目標規(guī)劃

方法一.

固定風險水平，優(yōu)化收益

在實際投資中，投資者承受風險的程度不一樣，若給定風險一個界限a，使最大的一個風險qixi/M≤a，可找到相應的投資方案。

模型一線性規(guī)劃模型若投資者希望總盈利至少達到水平k以上，在風險最小的情況下尋找相應的投資組合。

模型二線性規(guī)劃模型方法二：固定盈利水平，極小化風險采用線性加權法化為單目標規(guī)劃

投資者在權衡資產風險和預期收益兩方面時，希望選擇一個令自己滿意的投資組合。因此對風險、收益賦予權重s（0＜s≤1)，s稱為投資偏好系數.

模型三線性規(guī)劃模型模型一的求解

將具體數據代入,模型一如下:

由于a是任意給定的風險度，到底怎樣給定沒有一個準則，不同的投資者有不同的風險度。我們從a=0開始，以步長△a=0.001進行循環(huán)搜索，編制程序如下：a=0;while(1.1-a)>1c=[-0.05-0.27-0.19-0.185-0.185];

Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];

vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')計算結果：風險大，收益也大。曲線上的任一點表示該風險水平的最大可能收益。對于不同風險的承受能力，選擇該風險水平下的最優(yōu)投資組合。在a=0.006附近有一個轉折點，在這一點左邊，風險增加很少時，利潤增長很快。在這一點右邊，風險增加很大時，利潤增長很緩慢，所以對于風險和收益沒有特殊偏好的投資者來說，應該選擇曲線的拐點作為最優(yōu)投資組合，大約是：

a*=0.6%，Q*=20%。

此時所對應投資方案為:

風險度=0.0060；收益=0.2019；

x0=0，x1=0.2400，x2=0.4000，

x