最優(yōu)化計算方法

最優(yōu)化計算方法數(shù)學(xué)建模系列講座最優(yōu)化問題的解就是從所有可能的方案中選出最合理的,以達到最優(yōu)目標(biāo)的方案--最優(yōu)方案.搜尋最優(yōu)方案的方法就是最優(yōu)化方法.

最優(yōu)化是工程技術(shù)、經(jīng)濟管理、科學(xué)研究、社會生活中經(jīng)常遇到的問題.如：結(jié)構(gòu)設(shè)計資源分配生產(chǎn)計劃運輸方案最優(yōu)化:在一定條件下,尋求使目標(biāo)最大（?。┑臎Q策CUMCM賽題：約一半以上與最優(yōu)化問題有關(guān).2012年B題太陽能小屋的設(shè)計，2011年B題交巡警服務(wù)平臺的設(shè)置與調(diào)度，2010年A題儲油罐的變位識別與罐容表標(biāo)定，2009年B題眼科病床的合理安排等非線性規(guī)劃：96A最優(yōu)捕魚策略

96B節(jié)水洗衣機97A零件參數(shù)設(shè)計

98A投資收益與風(fēng)險01B公交車調(diào)度混合整數(shù)規(guī)劃:99B鉆井布局最短路，二次規(guī)劃：00B管道訂購組合優(yōu)化最短路：97B截斷切割，

04A奧運會臨時超市(MS)網(wǎng)點設(shè)計旅行商問題:98B災(zāi)情巡視優(yōu)化：02A車燈光源優(yōu)化設(shè)計

02B彩票中的數(shù)學(xué)最優(yōu)化理論是運籌學(xué)的基本內(nèi)容運籌學(xué)OR：OperationalResearch管理科學(xué)MS:ManagementScience決策科學(xué)DS:DecisionScience優(yōu)化Optimization規(guī)劃Programming動態(tài)規(guī)劃整數(shù)規(guī)劃不確定規(guī)劃非線性規(guī)劃目標(biāo)規(guī)劃組合優(yōu)化網(wǎng)絡(luò)優(yōu)化線性規(guī)劃無約束優(yōu)化多目標(biāo)規(guī)劃智能優(yōu)化優(yōu)化問題的一般形式優(yōu)化問題三要素：決策變量；目標(biāo)函數(shù)；約束條件

可行解（滿足約束）與可行域（可行解的集合）最優(yōu)解（取到最小或最大值的可行解）約束條件目標(biāo)函數(shù)決策變量最優(yōu)化模型與方法的步驟1.分析問題.發(fā)現(xiàn)、提出并形成問題,進行抽象、簡化、歸納和綜合.明確問題的目標(biāo)、各種約束、問題的可控變量以及有關(guān)參數(shù),搜集有關(guān)資料2.建立模型.經(jīng)過合理的假設(shè),確定變量、參數(shù)和目標(biāo)與約束之間的關(guān)系,使用有效的模型來表示3.求解.使用和創(chuàng)立各種數(shù)學(xué)方法和數(shù)學(xué)技術(shù),對模型求解(如最優(yōu)解、次優(yōu)解、近似解).借助于計算機軟件進行求解復(fù)雜的模型,并進行各種數(shù)據(jù)分析4.解的檢驗和控制.檢查求解步驟和程序無誤后,檢驗解是否反映現(xiàn)實問題并進行靈敏度分析

建模時需要注意的幾個基本問題1.盡量使用實數(shù)優(yōu)化,減少整數(shù)約束和整數(shù)變量2.盡量使用光滑優(yōu)化,減少非光滑約束的個數(shù)

如:盡量少使用絕對值函數(shù)、符號函數(shù)、多個變量求最大(最小)值、四舍五入、取整函數(shù)等3.盡量使用線性模型,減少非線性約束和非線性變量的個數(shù)

如:x/y<5應(yīng)改為x<5y4.合理設(shè)定變量上下界,盡可能給定變量初始值5.模型中使用的參數(shù)數(shù)量級要適當(dāng)

如:小于

無約束優(yōu)化最優(yōu)解都是局部最優(yōu)解,全局最優(yōu)解只能從局部最優(yōu)解的比較中得到.

多局部極小

唯一極小(全局極小)在迭代的每一步,確定一個搜索方向和一個步長,使沿此方向和此步長走一步到達下一點時,函數(shù)f(X)的值下降.步長的選擇:搜索方向

確定后,求步長實際上是一個一維優(yōu)化問題

成功-失敗法黃金分割法(0.618法)Fibonacci法拋物線插值法三次插值法求解方法:搜索算法(數(shù)值迭代)

方向的選擇:最速下降法(梯度法)牛頓法擬牛頓法由BFGS迭代公式或DEP公式迭代得出稱為一維搜索搜索過程最優(yōu)點(11)初始點(-11)-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.900.0030.990.991E-40.9990.9981E-50.99970.99981E-8

最速下降法是一種最基本的算法，它在最優(yōu)化方法中占有重要地位.最速下降法的優(yōu)點是工作量小，存儲變量較少,初始點要求不高；缺點是收斂慢，最速下降法適用于尋優(yōu)過程的前期迭代或作為間插步驟，當(dāng)接近極值點時，宜選用別種收斂快的算法.

1．最速下降法（共軛梯度法）算法步驟：無約束優(yōu)化問題的基本算法2．牛頓法算法步驟：

如果f是對稱正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過一次迭代就可達到最優(yōu)點,如不是二次函數(shù)，則牛頓法不能一步達到極值點，但由于這種函數(shù)在極值點附近和二次函數(shù)很近似,因此牛頓法的收斂速度還是很快的.

牛頓法的收斂速度雖然較快，但要求Hessian矩陣要可逆,要計算二階導(dǎo)數(shù)和逆矩陣，就加大了計算機計算量和存儲量.3．?dāng)M牛頓法選址問題:某市燃氣公司計劃要建一個煤氣供應(yīng)站,該站向城市中有固定位置的m個用戶供貨.對于選定的坐標(biāo)系,已知第i個用戶的位置為如果只考慮直線距離,如何確定煤氣站的位置,才能使總的運輸距離最短?設(shè)煤氣站的位置為

,則問題的數(shù)學(xué)模型為容積問題:對邊長為3米的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？產(chǎn)銷量的最佳安排

某廠生產(chǎn)一種產(chǎn)品有甲、乙兩個牌號，討論在產(chǎn)銷平衡的情況下如何確定各自的產(chǎn)量，使總利潤最大.所謂產(chǎn)銷平衡指工廠的產(chǎn)量等于市場上的銷量.總利潤為：z(x1,x2)=(p1-q1)x1+(p2-q2)x2基本假設(shè)1．價格與銷量成線性關(guān)系2．成本與產(chǎn)量成負指數(shù)關(guān)系

模型建立總利潤函數(shù)

z(x1,x2)=(p1-q1)x1+(p2-q2)x2若根據(jù)大量的統(tǒng)計數(shù)據(jù),求出系數(shù)b1=100,a11=1,a12=0.1,b2=280,a21=0.2,a22=2,r1=30,λ1=0.015,c1=20,r2=100,λ2=0.02,c2=30,則問題轉(zhuǎn)化為無約束優(yōu)化問題：求甲,乙兩個牌號的產(chǎn)量x1，x2，使總利潤z最大.為簡化模型,先忽略成本,并令a12=0,a21=0,問題轉(zhuǎn)化為求:z1=(b1-a11x1)x1+(b2-a22x2)x2

的極值.顯然其解為x1=b1/2a11=50,x2=b2/2a22=70,可以把它作為原問題的初始值.約束優(yōu)化連續(xù)優(yōu)化離散規(guī)劃線性規(guī)劃LP

目標(biāo)和約束均為線性函數(shù)非線性規(guī)劃NLP

目標(biāo)和約束均為非線性函數(shù)

二次規(guī)劃QP

目標(biāo)為二次函數(shù),約束為線性函數(shù)整數(shù)規(guī)劃IP

決策變量(全部或部分)為整數(shù)

整數(shù)線性規(guī)劃ILP

整數(shù)非線性規(guī)劃INLP

純整數(shù)規(guī)PIP

混合整數(shù)規(guī)劃MIP

一般整數(shù)規(guī)劃0--1整數(shù)規(guī)劃線性規(guī)劃目標(biāo)函數(shù)和約束條件都是線性函數(shù)線性規(guī)劃的其他形式可通過形式變換和添加松弛變量而化為標(biāo)準(zhǔn)型.常用求解方法:單純形法線性規(guī)劃模型的標(biāo)準(zhǔn)型:其中運輸問題:

設(shè)有m個生產(chǎn)地點可供應(yīng)物資,其供應(yīng)量(產(chǎn)量)分別為.有n個銷售地點,其需求量分別為,假設(shè)供需平衡,即

.用表示由運

輸單位物資的運價,如何

確定一種調(diào)運方案才能

使總運輸費用最小.

用表示由調(diào)運物資的

數(shù)量,則運輸問題的數(shù)學(xué)

模型為:任務(wù)分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件。假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型：人員問題:某廠每日8小時的產(chǎn)量不低于1800件。為了進行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標(biāo)準(zhǔn)為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標(biāo)準(zhǔn)為：速度15小時/件，正確率95%，計時工資3元/小時。檢驗員每錯檢一次，工廠要損失2元。為使總檢驗費用最省，該工廠應(yīng)聘一級、二級檢驗員各幾名？

設(shè)需要一級和二級檢驗員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗員的工資為：因檢驗員錯檢而造成的損失為：故目標(biāo)函數(shù)為：約束條件為：線性規(guī)劃模型：整數(shù)規(guī)劃決策變量只能取整數(shù)的數(shù)學(xué)規(guī)劃問題模型的一般形式為

求解方法:割平面法—用于求解純整數(shù)規(guī)劃分枝定界法—用于求解混合整數(shù)規(guī)劃.

窮舉法—用于規(guī)模不大的整數(shù)規(guī)劃.背包問題:

有一只背包(泛指倉庫、船艙、衛(wèi)星倉等)，最大裝載重量為w單位?，F(xiàn)有k種物品，每種的數(shù)量無限。第i種物品每件重量為,價值.每種物品各取多少裝入背包，使其中的物品總價值最高。設(shè)取第i種物品件,則非線性規(guī)劃目標(biāo)函數(shù)與約束條件中至少有一個是非線性函數(shù)SUTM外點法SUTM內(nèi)點法（障礙罰函數(shù)法）罰函數(shù)法近似規(guī)劃法常用方法基本思想：將非線性規(guī)劃問題中的目標(biāo)函數(shù)和約束條件

近似為線性函數(shù)，并對變量的取值范圍加以限制，從而得到一個近似線性規(guī)劃問題，再用單純形法求解之，把其符合原始條件的最優(yōu)解作為原問題的近似解．每得到一個近似解后，都從這點出發(fā)，重復(fù)以上步驟．這樣，通過求解一系列線性規(guī)劃問題，產(chǎn)生一個由線性規(guī)劃最優(yōu)解組成的序列，經(jīng)驗表明，這樣的序列往往收斂于非線性規(guī)劃問題的解。近似規(guī)劃法

SUTM外點法將求解將非線性規(guī)劃問題轉(zhuǎn)化為無約束問題

構(gòu)造罰函數(shù)

罰函數(shù)法基本思想是通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題.稱為序列無約束最小化方法,簡稱SUMT.其中T(x,M)稱為罰函數(shù)，M稱為罰因子，帶M的項稱為罰項這里的罰函數(shù)只對不滿足約束條件的點實行懲罰：當(dāng)時,滿足各,故罰項=0,不受懲罰.當(dāng)時,必有的約束條件,故罰項>0,要受懲罰．SUTM內(nèi)點法(障礙函數(shù)法)設(shè)集合是可行域中所有嚴格內(nèi)點的集合.構(gòu)造障礙函數(shù)考慮問題將問題轉(zhuǎn)化為無約束問題其中則是問題的解.

其中稱或為障礙項,為障礙因子資金使用問題:設(shè)有400萬元資金,要求4年內(nèi)使用完,若在一年內(nèi)使用資金x萬元,則可得效益萬元(效益不能再使用),當(dāng)年不用的資金可存入銀行,年利率為10%.試制定出資金的使用計劃,以使4年效益之和為最大.設(shè)變量表示第i年所使用的資金數(shù),則有其中H為n階對稱半正定矩陣.二次規(guī)劃問題標(biāo)準(zhǔn)形為動態(tài)規(guī)劃解決多階段決策過程最優(yōu)化的數(shù)學(xué)方法特點:具有明確的階段性,各階段次序遞推且相互依賴和影響.各個階段所作的決策形成確定整個系統(tǒng)的決策序列,稱這樣的決策序列為系統(tǒng)的一個策略.多階段決策過程就是在所有允許的策略集合中確定一個達到最優(yōu)指標(biāo)的最優(yōu)策略.多階段決策過程是一種多維優(yōu)化問題的方法.動態(tài)規(guī)劃是基于最優(yōu)性原理,將一個復(fù)雜的多元問題分解成為若干個相互依賴,相互聯(lián)系的易于求解優(yōu)化的少階段低維問題.構(gòu)造動態(tài)規(guī)劃模型的步驟1）將實際問題恰當(dāng)?shù)貏澐譃槿舾呻A段;2）正確選擇狀態(tài)變量;3）確定決策變量及每段的允許決策集合4）正確選擇狀態(tài)轉(zhuǎn)移方程；5）正確列出指標(biāo)函數(shù)并要求滿足遞推性。根據(jù)Bellman的最優(yōu)化原理，利用逆推（初始狀態(tài)給定）和順推方法(終止?fàn)顟B(tài)給定)，可求出最優(yōu)決策和最優(yōu)值。把資源分配過程分為N個階段.第k階段是向第k個生產(chǎn)項目分配資源.用x(k+1)表示分配完1,2,…,k個生產(chǎn)項目后剩余的資源數(shù)量(稱為狀態(tài)變量,x(1)=M).用v(x(k+1),k+1)表示把剩余的資源x(k+1)分配給第k+1,k+2,…,N個生產(chǎn)項目能獲得的最大利潤(稱為最優(yōu)值函數(shù)).投資問題設(shè)有某種資源(或資金)M個單位(M為正整數(shù)),欲分配用于N個生產(chǎn)項目.已知第k個生產(chǎn)項目獲得u(k)個單位(u(k)為非負整數(shù),稱為決策變量)這種資源后可創(chuàng)利潤L((u(k)),k).L(u(k)),K)是u(k)的不減函數(shù).如何分配這些資源可使所獲利潤

最大.根據(jù)動態(tài)規(guī)劃方法,利用動態(tài)規(guī)劃基本方程和狀態(tài)轉(zhuǎn)移方程

逆向遞推可求得最優(yōu)決策序列和總利潤的最大值其中多目標(biāo)規(guī)劃目標(biāo)函數(shù)由兩個或兩個以上函數(shù)構(gòu)成其中

為(vp)的絕對最優(yōu)解.

為(vp)的(弱)有效解或pareto最優(yōu)解.求解求解多目標(biāo)函數(shù)的評價函數(shù)方法求多目標(biāo)規(guī)劃有效解的最基本方法.基本思想:借助于幾何和應(yīng)用中的直觀背景,構(gòu)造所謂的評價函數(shù),從而將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題.然后利用單目標(biāo)優(yōu)化問題的求解方法求出最優(yōu)解,并把這種最優(yōu)解當(dāng)作多目標(biāo)規(guī)劃問題的最優(yōu)解.所謂的評價函數(shù)是利用(vp)的目標(biāo)函數(shù)f(x),構(gòu)造一個復(fù)合函數(shù),然后在(vp)的約束集上極小化.φ的構(gòu)造必須保證在一定條件下,的最優(yōu)解是(vp)的(弱)有效解.理想點法線性加權(quán)和法極大極小法理想點法

先求解p個單目標(biāo)問題.設(shè)其最優(yōu)值為,稱為一個理想值點,一般很難達到,尋求距最近的f作為近似值.

構(gòu)造評價函數(shù)線性加權(quán)和法

構(gòu)造評價函數(shù)極大極小法在決策時,采取保守策略是穩(wěn)妥的.即在最壞的情況下,尋求最好的結(jié)果.構(gòu)造評價函數(shù)材料問題用直徑為1的圓木制作截面為矩形的梁,為使重量最輕而強度最大,問截面的長與寬應(yīng)取何尺寸?設(shè)矩形截面的長與寬分別為,這時梁的面積為

,它決定重量.而梁的強度取決于截面矩故得到模型為組合最優(yōu)化可行解集合為有限點集求解方法:枚舉法有限個點,逐一判別.以時間為代價

啟發(fā)式算法不一定能保證所得解的可行性和最優(yōu)性.現(xiàn)代優(yōu)化算法包括禁忌搜索,模擬退火,遺傳算法,人工神經(jīng)網(wǎng)絡(luò).D表示由有限點組成的集合背包問題:設(shè)有一個容積為b的背包,n個體積分別為,價值分別為的物品,如何以最大的價值裝包?設(shè)則建模為旅行商問題:一個商人欲到n個城市推銷商品,每兩個城市i和j之間的距離為,如何選擇一條道路使得商人每個城市走一遍后回到起點且所走路徑最短.決策變量和分別表示行走的路線不包含和包含從城市i到城市j路徑,則數(shù)學(xué)模型為投資的收益和風(fēng)險任何人都希望最大化自己的效用而非最小，在保持生活水平不變的條件下最小化自己的支出而非最大，這是經(jīng)濟學(xué)的先驗命題，從重商主義、重農(nóng)主義、古典經(jīng)濟學(xué)、新古典經(jīng)濟學(xué)到當(dāng)代主流經(jīng)濟學(xué)(新古典主義和新凱恩斯主義)，無不接受、繼承和發(fā)展這一命題，效用最大化,支出最小化問題得到了越來越深入的研究。偏好的無滿足性決定了消費者根本不可能在整個消費集合中選擇出最為滿意的消費方案，因此，無限制的效用最大化是無法實現(xiàn)的。也就是說，消費者的欲望是無止境的，永遠沒有一個滿足的時候，當(dāng)消費者面臨一種消費方案時，常常會作出這樣的考慮：只要效用水平不降低，支出越少就越好。正常人都會有想占便宜的正常心理，誰不想以較少的效用換得較多的效用呢？任何人都處在一定的客觀環(huán)境中，客觀環(huán)境必然對人們的選擇行為帶來一定的限制。人們受到的種種限制影響了人們的選擇和享受，但這些限制卻使得效用最大化問題有了解決途徑——服從約束條件的效用最大化。理性消費者正是在服從種種條件限制的情況下，選擇自己最滿意的方案。在保證不降低生活水平的前提下謀求消費支出達到最少。二、問題的分析與假設(shè)這是一個多目標(biāo)優(yōu)化問題，目標(biāo)有二，凈收益最大和整體風(fēng)險最小.一般來說，這兩個目標(biāo)是矛盾的，收益大，風(fēng)險必然大，所以不可能給出這兩個目標(biāo)同時達到最優(yōu)的所謂最優(yōu)決策，我們追求的只能是，在一定的風(fēng)險下收益最大的決策，或在一定收益下風(fēng)險最小的決策，或收益和風(fēng)險按一定比例組合最優(yōu)的決策。這就是說應(yīng)該給出的不是一個解，而是一組Pareto解，比如在一系列風(fēng)險值下收益最大的決策，冒險者會從中選擇高風(fēng)險下收益最大的決策，保守者會從低風(fēng)險下的決策中選擇。三、模型的建立與分析1.總體風(fēng)險用所投資的Si中最大的一個風(fēng)險來衡量,即max{qixi|i=1，2,…n}對投資時交易費凈收益風(fēng)險所需資金

用表示投資方案,則投資方案的

總收益整體風(fēng)險所需資金將多目標(biāo)規(guī)劃問題化為單目標(biāo)規(guī)劃問題雙目標(biāo)優(yōu)化模型a.在實際投資中，投資者承受風(fēng)險的程度不一樣，若給定風(fēng)險一個界限a，使最大的一個風(fēng)險，可找到相應(yīng)的投資方案。這樣把多目標(biāo)規(guī)劃變成一個目標(biāo)的線性規(guī)劃。模型M1:確定風(fēng)險水平,優(yōu)化收益.記.求解

模型M2:確定盈利水平,極小化風(fēng)險.記.求解模型M3:確定投資者對風(fēng)險-收益的相對偏好參數(shù),求解b．若投資者希望總盈利至少達到水平k以上，在風(fēng)險最小的情況下尋找相應(yīng)的投資組合。c．投資者在權(quán)衡資產(chǎn)風(fēng)險和預(yù)期收益兩方面時，希望選擇一個令自