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

2、捕魚策略 96B 節(jié)水洗衣機(jī) 97A 零件參數(shù)設(shè)計(jì) 98A 投資收益與風(fēng)險(xiǎn)01B 公交車調(diào)度混合整數(shù)規(guī)劃: 99B 鉆井布局最短路，二次規(guī)劃： 00B 管道訂購(gòu)組合優(yōu)化最短路： 97B 截?cái)嗲懈睿?04A 奧運(yùn)會(huì)臨時(shí)超市(MS)網(wǎng)點(diǎn)設(shè)計(jì)旅行商問題: 98B 災(zāi)情巡視優(yōu)化： 02A 車燈光源優(yōu)化設(shè)計(jì) 02B 彩票中的數(shù)學(xué)最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座最優(yōu)化理論是運(yùn)籌學(xué)的基本內(nèi)容運(yùn)籌學(xué)OR： Operational Research管理科學(xué)MS: Management Science決策科學(xué)DS: Decision Science優(yōu)化Optimization 規(guī)劃Programming動(dòng)態(tài)規(guī)劃整數(shù)

3、規(guī)劃不確定規(guī)劃非線性規(guī)劃目標(biāo)規(guī)劃組合優(yōu)化網(wǎng)絡(luò)優(yōu)化線性規(guī)劃無約束優(yōu)化多目標(biāo)規(guī)劃智能優(yōu)化最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座優(yōu)化問題的一般形式優(yōu)化問題三要素：決策變量；目標(biāo)函數(shù)；約束條件 可行解（滿足約束）與可行域（可行解的集合） 最優(yōu)解（取到最小或最大值的可行解）約束條件目標(biāo)函數(shù)決策變量最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座最優(yōu)化模型與方法的步驟1.分析問題.發(fā)現(xiàn)、提出并形成問題,進(jìn)行抽象、簡(jiǎ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ù),對(duì)模型

4、求解(如最優(yōu)解、次優(yōu)解、近似解).借助于計(jì)算機(jī)軟件進(jìn)行求解復(fù)雜的模型,并進(jìn)行各種數(shù)據(jù)分析4.解的檢驗(yàn)和控制.檢查求解步驟和程序無誤后,檢驗(yàn)解是否反映現(xiàn)實(shí)問題并進(jìn)行靈敏度分析 最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座建模時(shí)需要注意的幾個(gè)基本問題1.盡量使用實(shí)數(shù)優(yōu)化,減少整數(shù)約束和整數(shù)變量2.盡量使用光滑優(yōu)化,減少非光滑約束的個(gè)數(shù) 如:盡量少使用絕對(duì)值函數(shù)、符號(hào)函數(shù)、多個(gè)變量求最大(最 小)值、四舍五入、取整函數(shù)等3.盡量使用線性模型,減少非線性約束和非線性 變量的個(gè)數(shù) 如: x/y5應(yīng)改為x0,要受懲罰最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座SUTM內(nèi)點(diǎn)法(障礙函數(shù)法)設(shè)集合 是可行域中所有嚴(yán)格內(nèi)點(diǎn)的集合.構(gòu)造障礙

5、函數(shù) 考慮問題將問題轉(zhuǎn)化為無約束問題其中 則 是問題的解. 其中稱 或 為障礙項(xiàng), 為障礙因子最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座資金使用問題:設(shè)有400萬元資金, 要求4年內(nèi)使用完, 若在一年內(nèi)使用資金x萬元, 則可得效益 萬元(效益不能再使用),當(dāng)年不用的資金可存入銀行, 年利率為10%. 試制定出資金的使用計(jì)劃, 以使4年效益之和為最大.設(shè)變量 表示第i年所使用的資金數(shù),則有最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座其中H為n階對(duì)稱半正定矩陣.二次規(guī)劃問題標(biāo)準(zhǔn)形為最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座動(dòng)態(tài)規(guī)劃解決多階段決策過程最優(yōu)化的數(shù)學(xué)方法特點(diǎn): 具有明確的階段性,各階段次序遞推且相互依賴和影響.各個(gè)階段所作的

6、決策形成確定整個(gè)系統(tǒng)的決策序列,稱這樣的決策序列為系統(tǒng)的一個(gè)策略.多階段決策過程就是在所有允許的策略集合中確定一個(gè)達(dá)到最優(yōu)指標(biāo)的最優(yōu)策略.多階段決策過程是一種多維優(yōu)化問題的方法.動(dòng)態(tài)規(guī)劃是基于最優(yōu)性原理,將一個(gè)復(fù)雜的多元問題分解成為若干個(gè)相互依賴,相互聯(lián)系的易于求解優(yōu)化的少階段低維問題.最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座構(gòu)造動(dòng)態(tài)規(guī)劃模型的步驟1）將實(shí)際問題恰當(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)

7、決策和最優(yōu)值。最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座把資源分配過程分為N個(gè)階段. 第k階段是向第k個(gè)生產(chǎn)項(xiàng)目分配資源. 用x(k+1)表示分配完1,2,k個(gè)生產(chǎn)項(xiàng)目后剩余的資源數(shù)量(稱為狀態(tài)變量,x(1)=M). 用v(x(k+1),k+1)表示把剩余的資源x(k+1)分配給第k+1,k+2,N個(gè)生產(chǎn)項(xiàng)目能獲得的最大利潤(rùn)(稱為最優(yōu)值函數(shù)). 投資問題 設(shè)有某種資源(或資金)M個(gè)單位(M為正整數(shù)), 欲分配用于N個(gè)生產(chǎn)項(xiàng)目. 已知第k個(gè)生產(chǎn)項(xiàng)目獲得u(k)個(gè)單位(u(k)為非負(fù)整數(shù), 稱為決策變量)這種資源后可創(chuàng)利潤(rùn)L(u(k),k). L(u(k),K)是u(k)的不減函數(shù).如何分配這些資源可使所獲利

8、潤(rùn) 最大.最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座根據(jù)動(dòng)態(tài)規(guī)劃方法, 利用動(dòng)態(tài)規(guī)劃基本方程和狀態(tài)轉(zhuǎn)移方程 逆向遞推可求得最優(yōu)決策序列和總利潤(rùn)的最大值其中最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座多目標(biāo)規(guī)劃目標(biāo)函數(shù)由兩個(gè)或兩個(gè)以上函數(shù)構(gòu)成其中 為(vp)的絕對(duì)最優(yōu)解. 為(vp)的(弱)有效解或pareto最優(yōu)解.最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座求解求解多目標(biāo)函數(shù)的評(píng)價(jià)函數(shù)方法求多目標(biāo)規(guī)劃有效解的最基本方法.基本思想:借助于幾何和應(yīng)用中的直觀背景, 構(gòu)造所謂的評(píng)價(jià)函數(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)解.所謂的評(píng)價(jià)函數(shù)是利

9、用(vp)的目標(biāo)函數(shù)f(x), 構(gòu)造一個(gè)復(fù)合函數(shù) ,然后在(vp)的約束集上極小化 .的構(gòu)造必須保證在一定條件下, 的最優(yōu)解是(vp)的(弱)有效解.理想點(diǎn)法線性加權(quán)和法極大極小法最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座理想點(diǎn)法 先求解p個(gè)單目標(biāo)問題 .設(shè)其最優(yōu)值為 ,稱 為一個(gè)理想值點(diǎn), 一般很難達(dá)到, 尋求距 最近的f 作為近似值. 構(gòu)造評(píng)價(jià)函數(shù)線性加權(quán)和法 構(gòu)造評(píng)價(jià)函數(shù)極大極小法在決策時(shí), 采取保守策略是穩(wěn)妥的.即在最壞的情況下, 尋求最好的結(jié)果.構(gòu)造評(píng)價(jià)函數(shù)最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座材料問題用直徑為1的圓木制作截面為矩形的梁, 為使重量最輕而強(qiáng)度最大, 問截面的長(zhǎng)與寬應(yīng)取何尺寸?設(shè)矩形截面的

10、長(zhǎng)與寬分別為 ,這時(shí)梁的面積為 ,它決定重量.而梁的強(qiáng)度取決于截面矩故得到模型為最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座組合最優(yōu)化可行解集合為有限點(diǎn)集求解方法:枚舉法 有限個(gè)點(diǎn),逐一判別.以時(shí)間為代價(jià) 啟發(fā)式算法 不一定能保證所得解的可行性和最優(yōu)性.現(xiàn)代優(yōu)化算法 包括禁忌搜索,模擬退火,遺傳算法,人 工神經(jīng)網(wǎng)絡(luò). D表示由有限點(diǎn)組成的集合最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座背包問題:設(shè)有一個(gè)容積為b的背包,n個(gè)體積分別為 ,價(jià)值分別為 的物品,如何以最大的價(jià)值裝包?設(shè)則建模為最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座旅行商問題:一個(gè)商人欲到n個(gè)城市推銷商品, 每?jī)蓚€(gè)城市i和j之間的距離為 ,如何選擇一條道路使得商人每個(gè)城

11、市走一遍后回到起點(diǎn)且所走路徑最短. 決策變量和 分別表示行走的路線不包含和包含從城市i到城市j路徑, 則數(shù)學(xué)模型為最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座投資的收益和風(fēng)險(xiǎn)任何人都希望最大化自己的效用而非最小，在保持生活水平不變的條件下最小化自己的支出而非最大，這是經(jīng)濟(jì)學(xué)的先驗(yàn)命題，從重商主義、重農(nóng)主義、古典經(jīng)濟(jì)學(xué)、新古典經(jīng)濟(jì)學(xué)到當(dāng)代主流經(jīng)濟(jì)學(xué)(新古典主義和新凱恩斯主義)，無不接受、繼承和發(fā)展這一命題，效用最大化,支出最小化問題得到了越來越深入的研究。偏好的無滿足性決定了消費(fèi)者根本不可能在整個(gè)消費(fèi)集合中選擇出最為滿意的消費(fèi)方案，因此，無限制的效用最大化是無法實(shí)現(xiàn)的。也就是說，消費(fèi)者的欲望是無止境的，永遠(yuǎn)沒

12、有一個(gè)滿足的時(shí)候，當(dāng)消費(fèi)者面臨一種消費(fèi)方案時(shí)，常常會(huì)作出這樣的考慮：只要效用水平不降低，支出越少就越好。正常人都會(huì)有想占便宜的正常心理，誰不想以較少的效用換得較多的效用呢？任何人都處在一定的客觀環(huán)境中，客觀環(huán)境必然對(duì)人們的選擇行為帶來一定的限制。人們受到的種種限制影響了人們的選擇和享受，但這些限制卻使得效用最大化問題有了解決途徑服從約束條件的效用最大化。理性消費(fèi)者正是在服從種種條件限制的情況下，選擇自己最滿意的方案。在保證不降低生活水平的前提下謀求消費(fèi)支出達(dá)到最少。最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座二、問題的分析與假設(shè)這是一個(gè)多目標(biāo)優(yōu)化問題，目標(biāo)有二，凈收益最大和整體

13、風(fēng)險(xiǎn)最小. 一般來說，這兩個(gè)目標(biāo)是矛盾的，收益大，風(fēng)險(xiǎn)必然大，所以不可能給出這兩個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu)的所謂最優(yōu)決策，我們追求的只能是，在一定的風(fēng)險(xiǎn)下收益最大的決策，或在一定收益下風(fēng)險(xiǎn)最小的決策，或收益和風(fēng)險(xiǎn)按一定比例組合最優(yōu)的決策。這就是說應(yīng)該給出的不是一個(gè)解，而是一組Pareto解，比如在一系列風(fēng)險(xiǎn)值下收益最大的決策，冒險(xiǎn)者會(huì)從中選擇高風(fēng)險(xiǎn)下收益最大的決策，保守者會(huì)從低風(fēng)險(xiǎn)下的決策中選擇。最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座三、模型的建立與分析1.總體風(fēng)險(xiǎn)用所投資的Si中最大的一個(gè)風(fēng)險(xiǎn)來衡量,即max qixi | i=1，2,n最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座對(duì) 投資

14、時(shí)交易費(fèi)凈收益風(fēng)險(xiǎn)所需資金 用 表示投資方案,則投資方案的 總收益整體風(fēng)險(xiǎn)所需資金最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座將多目標(biāo)規(guī)劃問題化為單目標(biāo)規(guī)劃問題雙目標(biāo)優(yōu)化模型a. 在實(shí)際投資中，投資者承受風(fēng)險(xiǎn)的程度不一樣，若給定風(fēng)險(xiǎn)一個(gè)界限a，使最大的一個(gè)風(fēng)險(xiǎn) ，可找到相應(yīng)的投資方案。這樣把多目標(biāo)規(guī)劃變成一個(gè)目標(biāo)的線性規(guī)劃。模型M1:確定風(fēng)險(xiǎn)水平 ,優(yōu)化收益.記 .求解最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座 模型M2:確定盈利水平 ,極小化風(fēng)險(xiǎn).記 .求解模型M3:確定投資者對(duì)風(fēng)險(xiǎn)-收益的相對(duì)偏好參數(shù) ,求解b若投資者希望總盈利至少達(dá)到水平k以上，在風(fēng)險(xiǎn)最小的情況下尋找相應(yīng)的投資組合。c投資者在權(quán)衡資產(chǎn)風(fēng)險(xiǎn)和預(yù)期收益兩方面時(shí)，希望選擇一個(gè)令自己滿意的投資組合。因此對(duì)風(fēng)險(xiǎn)、收益賦予權(quán)重s（0s1)，s稱為投資偏好系數(shù).最優(yōu)化計(jì)算方法數(shù)學(xué)建模系列講座4. 模型簡(jiǎn)化：交易費(fèi)的簡(jiǎn)化:由于交易費(fèi) 中固定費(fèi)用 的存在, 使得模型中的目標(biāo)函數(shù)或約束條件是非光滑的, 求解非常困難. 考慮到總資金M相當(dāng)大, 而交易費(fèi)中的 又相當(dāng)小, 故可使對(duì)每個(gè) 的投資 都超過 ,于是交易費(fèi)可簡(jiǎn)化為線性函數(shù) 從而資金約束簡(jiǎn)化