最優化計算方法數學建模系列講座最優化問題的解就是從所有可能的方案中選出最合理的,以達到最優目標的方案--最優方案.搜尋最優方案的方法就是最優化方法.

最優化是工程技術、經濟管理、科學研究、社會生活中經常遇到的問題.如：結構設計資源分配生產計劃運輸方案最優化:在一定條件下,尋求使目標最大（小）的決策CUMCM賽題：約一半以上與最優化問題有關.2012年B題太陽能小屋的設計，2011年B題交巡警服務平臺的設置與調度，2010年A題儲油罐的變位識別與罐容表標定，2009年B題眼科病床的合理安排等非線性規劃：96A最優捕魚策略

96B節水洗衣機97A零件參數設計

98A投資收益與風險01B公交車調度混合整數規劃:99B鉆井布局最短路，二次規劃：00B管道訂購組合優化最短路：97B截斷切割，

04A奧運會臨時超市(MS)網點設計旅行商問題:98B災情巡視優化：02A車燈光源優化設計

02B彩票中的數學最優化理論是運籌學的基本內容運籌學OR：OperationalResearch管理科學MS:ManagementScience決策科學DS:DecisionScience優化Optimization規劃Programming動態規劃整數規劃不確定規劃非線性規劃目標規劃組合優化網絡優化線性規劃無約束優化多目標規劃智能優化優化問題的一般形式優化問題三要素：決策變量；目標函數；約束條件

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

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

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

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

如:小于

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

多局部極小

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

確定后,求步長實際上是一個一維優化問題

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

方向的選擇:最速下降法(梯度法)牛頓法擬牛頓法由BFGS迭代公式或DEP公式迭代得出稱為一維搜索搜索過程最優點(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

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

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

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

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

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

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

模型建立總利潤函數

z(x1,x2)=(p1-q1)x1+(p2-q2)x2若根據大量的統計數據,求出系數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,則問題轉化為無約束優化問題：求甲,乙兩個牌號的產量x1，x2，使總利潤z最大.為簡化模型,先忽略成本,并令a12=0,a21=0,問題轉化為求:z1=(b1-a11x1)x1+(b2-a22x2)x2

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

目標和約束均為線性函數非線性規劃NLP

目標和約束均為非線性函數

二次規劃QP

目標為二次函數,約束為線性函數整數規劃IP

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

整數線性規劃ILP

整數非線性規劃INLP

純整數規PIP

混合整數規劃MIP

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

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

.用表示由運

輸單位物資的運價,如何

確定一種調運方案才能

使總運輸費用最小.

用表示由調運物資的

數量,則運輸問題的數學

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

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

求解方法:割平面法—用于求解純整數規劃分枝定界法—用于求解混合整數規劃.

窮舉法—用于規模不大的整數規劃.背包問題:

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

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

SUTM外點法將求解將非線性規劃問題轉化為無約束問題

構造罰函數

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

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

最大.根據動態規劃方法,利用動態規劃基本方程和狀態轉移方程

逆向遞推可求得最優決策序列和總利潤的最大值其中多目標規劃目標函數由兩個或兩個以上函數構成其中

為(vp)的絕對最優解.

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

先求解p個單目標問題.設其最優值為,稱為一個理想值點,一般很難達到,尋求距最近的f作為近似值.

構造評價函數線性加權和法

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

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

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

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

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

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