運籌學(xué)與最優(yōu)化方法優(yōu)化建模.ppt

1、a,1,最優(yōu)化方法,哈爾濱工業(yè)大學(xué) 尚壽亭,建模原理算法,a,2,教材與參考 1 吳祈宗. 運籌學(xué)與最優(yōu)化方法. 北京：機械工業(yè)出版社， 2003.8 2 薛嘉慶. 最優(yōu)化原理與方法（修訂版）. 北京：冶金工業(yè) 出版社，1992.8 3 解可新，韓立興，林友聯(lián). 最優(yōu)化方法. 天津：天津大學(xué) 出版社，1997.1 4 蕭樹鐵，姜啟源等. 數(shù)學(xué)實驗，北京：高等教育出版社， 1999.7 5 邢文訓(xùn)，謝金星. 現(xiàn)代優(yōu)化計算方法. 北京：清華大學(xué)出 版社，1999.8 6 胡運權(quán)，運籌學(xué)基礎(chǔ)及應(yīng)用（第三版），哈爾濱工業(yè)大學(xué) 出版社，1998,a,3,參考網(wǎng)站,1 全國大學(xué)生數(shù)學(xué)建模競賽網(wǎng)： 2 美國

2、：數(shù)學(xué)及其應(yīng)用聯(lián)合會網(wǎng)站： 3 中國數(shù)學(xué)建模網(wǎng)站： 4 “中國電機工程學(xué)會杯”全國大學(xué)生電工數(shù)學(xué)建模競賽網(wǎng)： /,a,4,最優(yōu)化方法 實際問題與建模,a,5,1.經(jīng)典極值問題,例1.車站選址問題 一直線鐵路經(jīng)過鋼廠A，礦區(qū) B 位于距鐵路最近處 C 為20km，A C 相距150km。計劃在鐵路上設(shè)一站 D，在A D之間筑一條直線公路，若礦石運費鐵路為3元/kmt，公路為5元/kmt。 問題：D 站選在何處最好。 y B（150，20） o x 150 x A D C,a,6,建模與求解 建立模型： 設(shè)：坐標(biāo)系 xoy，鐵路線在 ox- 軸上，點A 位于坐

3、標(biāo)原點 o，點B位于（150，20）,點C位于（150，0）,站D選在 x 處，運費為 f (x)。 模型： （min-minimize） （1） 其中： 求解：應(yīng)用導(dǎo)數(shù)求極值 令 ，即 （2） 由（2）,a,7,移項后兩邊開方，解得： （3） 由（2）知 x = 165 為增根（ ） x = 135 為唯一駐點 答案：站 D 應(yīng)設(shè)在距鋼廠 A 135km處。 問題擴展：考慮筑路、建站、裝卸等費用，如何建模？ 數(shù)學(xué)建模競賽題：道路改造項目中碎石運輸?shù)脑O(shè)計 相關(guān)網(wǎng)站： “中國電機工程學(xué)會杯”全國大學(xué)生電工數(shù)學(xué)建模競賽 / 例2. 罐頭盒問題 設(shè)計圓柱形罐頭盒

4、，使用料最省。 假設(shè)：1.不考慮折邊及鐵皮厚度； 2.底半徑 r，高 h； 3.容積為常數(shù)V。,a,8,建立最優(yōu)化模型： （4） s.t. - subject to (滿足于): 約束條件 令 模型（4）可寫成 與（1）類似的形式 不考慮不等式約束時，模型（4）可用Lagrange乘子法求解,a,9,令 求解方程組 由 r 0,及（6）解得 ，代入（5） 結(jié)論：高與直徑相等時用料最省。 問題擴展：側(cè)面與底面厚度不同或造價不同，該如何設(shè)計？ 作 業(yè) 題：建立易拉罐的優(yōu)化設(shè)計模型。,a,10,經(jīng)典優(yōu)化問題一般模型： a.無約束問題： 其中的 可省去； b.條件極值： 最優(yōu)化問題一般模型：,a,11

5、,2.最優(yōu)化問題實例： 例4. 生產(chǎn)計劃問題 某工廠有 m 種資源 某一時段的數(shù)量 分別為： 可用來生產(chǎn) n 種產(chǎn)品 每生產(chǎn)一單位 消耗 為 利潤為 。如何安排 生產(chǎn)可獲最大利潤？ 設(shè)：計劃生產(chǎn) 單位 建立線性規(guī)劃模型 LP（Linear Programming） Max c1x1+ c2x2+ + cnxn s. t. a11 x1+ a12x2+ + a1nxnb1 am1 x1+ am2x2+ + amnxn bm x1, x2, , xn 0,a,12,令 X = x1, x2, , xn T ; c = c1, c2, , cn T ; b = b1, b2, , bn T ; A

6、= aij mxn LP： 問題擴展 a. 若 c1, c2, , cn 不是固定的，c 是隨機變量， 平均值 ，協(xié)方差矩陣 V 。 希望利潤期望值最大且方差最小，建立多目標(biāo)優(yōu)化模型：,a,13,問題擴展 b. 風(fēng)險投資問題（參考98全國建模賽題） 將前面的產(chǎn)品換成投資項目，考慮投資 Aj 風(fēng)險損失qj 。 建立多目標(biāo)優(yōu)化模型： 化為多目標(biāo)線性規(guī)劃模型：,a,14,例5. 數(shù)據(jù)擬合問題 設(shè)某系統(tǒng)中變量 x, y 滿足： y = f (x) 已獲得系統(tǒng)數(shù)據(jù)： ( xi , yi ) , i = 1, 2 , , m 確定 f (x) 的參數(shù)，例如： 最優(yōu)化模型： （最小二乘） 其中決策變量為f

7、(x) 的參數(shù),a,15,例6. 指派問題（0-1規(guī)劃）,a,16,例7. 旅行商問題-TSP（組合優(yōu)化） 一商人欲到 n 個城市推銷， 城市 i 到城市 j 相距 dij , 求走遍所有城市的最短路。 模型：,a,17,計算復(fù)雜性概念 n個城市的旅行商問題-TSP，固定一個城市，采用枚舉法需 (n-1)! 個枚舉。 枚舉時城市數(shù)與計算時間的關(guān)系 可以看出27個城市時枚舉法已很費時，27個以上可采用啟發(fā)式算法(heuristic algrithm)，參見： 5 （邢文訓(xùn)，謝金星. 現(xiàn)代優(yōu)化計算方法. ） 問題擴展 ：多旅行商問題 98全國建模賽題 ： B. 災(zāi)情巡視路線,a,18,2000B題

8、 鋼管訂購和運輸 要鋪設(shè)一條的輸送天然氣的主管道, 如圖一所示(見下頁)。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有。圖中粗線表示鐵路，單細線表示公路，雙細線表示要鋪設(shè)的管道(假設(shè)沿管道或者原來有公路，或者建有施工公路)，圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯?dāng)?shù)字表示里程(單位km)。 為方便計，1km主管道鋼管稱為1單位鋼管。 一個鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個單位，鋼管出廠銷價1單位鋼管為萬元，如下表：,a,19,鋼管可由鐵路、公路運往鋪設(shè)地點（不只是運到點，而是管道全線）。 （1）請制定一個主管道鋼管的訂購和運輸計劃，使

9、總費用最?。ńo出總費用)。 （2）請就（1）的模型分析：哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運計劃和總費用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。 （3）如果要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。,a,20,a,21,a,22,鋼管訂購和運輸 最優(yōu)化模型,a,23,鋼管訂購和運輸 最優(yōu)化模型,a,24,鋼管訂購和運輸 最優(yōu)化模型,a,25,1998A題 投資的收益和風(fēng)險 市場上有n種資產(chǎn)（如股票、債券、）Si ( i=1,n) 供投資者選擇，某公司

10、有數(shù)額為M的一筆相當(dāng)大的資金可用作一個時期的投資。公司財務(wù)分析人員對這n種資產(chǎn)進行了評估，估算出在這一時期內(nèi)購買Si的平均收益率為ri，并預(yù)測出購買Si的風(fēng)險損失率為qi?？紤]到投資越分散，總的風(fēng)險越小，公司確定，當(dāng)用這筆資金購買若干種資產(chǎn)時，總體風(fēng)險可用所投資的Si中最大的一個風(fēng)險來度量。 購買Si要付交易費，費率為pi，并且當(dāng)購買額不超過給定值ui時，交易費按購買ui計算（不買當(dāng)然無須付費）。另外，假定同期銀行存款利率是r0, 且既無交易費又無風(fēng)險。（ r0 =5%）,a,26,a,27,a,28,a,29,Matlab優(yōu)化工具箱 （Optimization toolbox）,attgoa

11、l： 求解多目標(biāo)優(yōu)化問題. constr： 求解約束非線性優(yōu)化問題. fmin： 求解標(biāo)量非線性優(yōu)化問題. fminu,fmins：求解無約束非線性優(yōu)化問題. lp： 求解線性規(guī)劃問題. minmax： 求解最小最大問題. qp： 求解二次規(guī)劃問題. seminf： 求解半無限問題. conls： 求解線性約束最小二乘最優(yōu)解. curvefit： 非線性數(shù)據(jù)擬合. leastsq： 求解非線性最小二乘最優(yōu)問題. nnls： 求解非負約束最小二乘最優(yōu)解,a,30,a,31,a,32,a,33,線性規(guī)劃MATLAB程序,模型： Min Z = cTx S.t. Ax b v1 x v2 X=lp

12、(c,A,b,v1,v2, x0,ne,dis) v1,v2- x 的下,上界 X0 - 初始值 ne - 前 ne 個約束為等式約束 dis - 給出警告信息，如解無界或無可行解 缺省時 用 占據(jù)其位置，程序?qū)⒆詣咏o出,a,34,無約束非線性規(guī)劃MATLAB程序,模型： Min f（x） X=fminu (fun,x0,opt,grad,p1,p2) x, opt=fminu (fun,x0,opt,grad,p1,p2) fun - 建立 fun.m 函數(shù)文件 X0 - 初始值 Opt -控制參數(shù) grad-建立 grad .m 函數(shù)文件計算梯度 p1,p2-可傳遞到 fun 和 grad 中公用的參數(shù) （最多10個） 缺省時 用 占據(jù)其位置，程序?qū)⒆詣咏o出,a,35,約束非線性規(guī)劃MATLAB程序,模型： Min f（x） S.t. g（x） 0 X=constr (fun,x0,opt,v1,v2,grad,p1,p2) x, opt=