科大數(shù)學(xué)建模培訓(xùn)最優(yōu)化優(yōu)化

1、最優(yōu)化 哈爾濱工業(yè)大學(xué) 尚壽亭建模原理算法教材1 Mokhtar S. Bazaraa, C. M. Shetty, Nonlinear Programming theory and Algorithms. John Wiley & Sons, Inc.,19792 M.S.巴扎拉，C.M.希蒂，王化存，張春柏譯，非線性規(guī)劃理論與算法. 貴陽(yáng)：貴州人民出版社，19863 Mokhtar S. Bazaraa, C. M. Shetty, Foundations of optimization, lecture Notes in Economics and Mathematical System

2、s, No. 122, Springer-Verlag, New York,1976參考1 應(yīng)玫茜，魏權(quán)齡. 非線性規(guī)劃及其理論. 北京：中國(guó)人民大學(xué)出版社. 1994.92 薛嘉慶. 最優(yōu)化原理與方法（修訂版）. 北京：冶金工業(yè)出版社，1992.83 解可新，韓立興，林友聯(lián). 最優(yōu)化方法. 天津：天津大學(xué)出版社，1997.14 謝金星，薛毅. 優(yōu)化建模與LINDO/LINGO軟件. 北京：清華大學(xué)出版社，2005.75 邢文訓(xùn)，謝金星. 現(xiàn)代優(yōu)化計(jì)算方法. 北京：清華大學(xué)出版社，1999.8參考網(wǎng)站1 全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽網(wǎng)： 2 美國(guó)：數(shù)學(xué)及其應(yīng)用聯(lián)合會(huì)網(wǎng)站： 3 中國(guó)數(shù)學(xué)建模網(wǎng)站： 4

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

4、ze） （1） 其中： 求解：應(yīng)用導(dǎo)數(shù)求極值令 ，即 （2）由（2）移項(xiàng)后兩邊開(kāi)方，解得： （3）由（2）知 x = 165 為增根（ ） x = 135 為唯一駐點(diǎn)答案：站 D 應(yīng)設(shè)在距鋼廠 A 135km處。問(wèn)題擴(kuò)展：考慮筑路、建站、裝卸等費(fèi)用，如何建模？數(shù)學(xué)建模競(jìng)賽題：道路改造項(xiàng)目中碎石運(yùn)輸?shù)脑O(shè)計(jì)相關(guān)網(wǎng)站： “中國(guó)電機(jī)工程學(xué)會(huì)杯”全國(guó)大學(xué)生電工數(shù)學(xué)建模競(jìng)賽 例2. 罐頭盒問(wèn)題設(shè)計(jì)圓柱形罐頭盒，使用料最省。假設(shè)：1.不考慮折邊及鐵皮厚度； 2.底半徑 r，高 h； 3.容積為常數(shù)V。rh建立最優(yōu)化模型： （4）s.t. - subject to (滿足于): 約束條件令模型（4）可寫(xiě)成 與

5、（1）類似的形式不考慮不等式約束時(shí)，模型（4）可用Lagrange乘子法求解令 求解方程組由 r 0,及（6）解得 ，代入（5）結(jié)論：高與直徑相等時(shí)用料最省。問(wèn)題擴(kuò)展：側(cè)面與底面厚度不同或造價(jià)不同，該如何設(shè)計(jì)？作 業(yè) 題：建立易拉罐的優(yōu)化設(shè)計(jì)模型。經(jīng)典優(yōu)化問(wèn)題一般模型： a.無(wú)約束問(wèn)題： 其中的 可省去； b.條件極值：最優(yōu)化問(wèn)題一般模型：2.最優(yōu)化問(wèn)題實(shí)例：例4. 生產(chǎn)計(jì)劃問(wèn)題 某工廠有 m 種資源 某一時(shí)段的數(shù)量分別為： 可用來(lái)生產(chǎn) n 種產(chǎn)品每生產(chǎn)一單位 消耗 為 利潤(rùn)為 。如何安排生產(chǎn)可獲最大利潤(rùn)？設(shè)：計(jì)劃生產(chǎn) 單位 建立線性規(guī)劃模型LP（Linear Programming） Max

6、 c1x1+ c2x2+ + cnxn s. t. a11 x1+ a12x2+ + a1nxnb1 am1 x1+ am2x2+ + amnxn bm x1, x2, , xn 0令 x = x1, x2, , xn T ; c = c1, c2, , cn T ; b = b1, b2, , bm T ; A = aij mxnLP：?jiǎn)栴}擴(kuò)展 a. 若 c1, c2, , cn 不是固定的，c 是隨機(jī)變量， 平均值 ，協(xié)方差矩陣 V 。 希望利潤(rùn)期望值最大且方差最小，建立多目標(biāo)優(yōu)化模型： 問(wèn)題擴(kuò)展 b. 風(fēng)險(xiǎn)投資問(wèn)題（參考98全國(guó)建模賽題） 將前面的產(chǎn)品換成投資項(xiàng)目，考慮投資 Aj 風(fēng)險(xiǎn)損

7、失qj 。建立多目標(biāo)優(yōu)化模型：化為多目標(biāo)線性規(guī)劃模型：例5. 數(shù)據(jù)擬合問(wèn)題設(shè)某系統(tǒng)中變量 x, y 滿足： y = f (x)已獲得系統(tǒng)數(shù)據(jù)： ( xi , yi ) , i = 1, 2 , , m確定 f (x) 的參數(shù)，例如：最優(yōu)化模型： （最小二乘）其中決策變量為f (x) 的參數(shù) 例6. 指派問(wèn)題（0-1規(guī)劃）例7. 旅行商問(wèn)題-TSP（組合優(yōu)化）一商人欲到 n 個(gè)城市推銷，城市 i 到城市 j 相距 dij ,求走遍所有城市的最短路。模型：計(jì)算復(fù)雜性概念n個(gè)城市的旅行商問(wèn)題-TSP，固定一個(gè)城市，采用枚舉法需 (n-1)! 個(gè)枚舉。枚舉時(shí)城市數(shù)與計(jì)算時(shí)間的關(guān)系 可以看出27個(gè)城市時(shí)

8、枚舉法已很費(fèi)時(shí)，27個(gè)以上可采用啟發(fā)式算法(heuristic algrithm)，參見(jiàn)： 5 （邢文訓(xùn)，謝金星. 現(xiàn)代優(yōu)化計(jì)算方法. ）問(wèn)題擴(kuò)展 ：多旅行商問(wèn)題98全國(guó)建模賽題 ： B. 災(zāi)情巡視路線 城 市 數(shù)24 25 26 27 28 29 30 31計(jì)算時(shí)間1s 24s 10min 4.3h 4.9d 136.5d 10.8a 325a2000B題 鋼管訂購(gòu)和運(yùn)輸要鋪設(shè)一條A1 A2 A15的輸送天然氣的主管道, 如圖一所示(見(jiàn)下頁(yè))。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有S1, S2, S7, 。圖中粗線表示鐵路，單細(xì)線表示公路，雙細(xì)線表示要鋪設(shè)的管道(假設(shè)沿管道或者原來(lái)有公路，或

9、者建有施工公路)，圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯?dāng)?shù)字表示里程(單位km)。為方便計(jì)，1km主管道鋼管稱為1單位鋼管。一個(gè)鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個(gè)單位。鋼廠Si在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個(gè)si單位，鋼管出廠銷價(jià)1單位鋼管為pi萬(wàn)元，如下表： 1單位鋼管的鐵路運(yùn)價(jià)如下表：1000km以上每增加1至100km運(yùn)價(jià)增加5萬(wàn)元。公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬(wàn)元（不足整公里部分按整公里計(jì)算）。 i1234567si80080010002000200020003000pi160155155160155150160里程(km) 300 301350 35

10、1400 401450 451500 運(yùn)價(jià)(萬(wàn)元) 2023262932里程(km)501600 601700 701800 801900 9011000 運(yùn)價(jià)(萬(wàn)元) 3744505560鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只是運(yùn)到點(diǎn)，而是管道全線）。（1）請(qǐng)制定一個(gè)主管道鋼管的訂購(gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最小（給出總費(fèi)用)。（2）請(qǐng)就（1）的模型分析：哪個(gè)鋼廠鋼管的銷價(jià)的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響最大，哪個(gè)鋼廠鋼管的產(chǎn)量的上限的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。（3）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹(shù)形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情形給出一種解決辦法，

11、并對(duì)圖二按（1）的要求給出模型和結(jié)果。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7圖一A1325801010312012427010881070627030202030450104301750606194205201680480

12、3002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)圖二鋼管訂購(gòu)和運(yùn)輸最優(yōu)化模型鋼管訂購(gòu)和運(yùn)輸最優(yōu)化模型鋼管訂購(gòu)和運(yùn)輸最優(yōu)化模型1998A題 投資的收益和風(fēng)險(xiǎn)市場(chǎng)上有n種資產(chǎn)（如股票、債券、）Si ( i=1,n) 供投資者選擇，某公司有數(shù)額為M的一筆相當(dāng)大的資金可用作一個(gè)時(shí)期的投資。公司財(cái)務(wù)分析人員對(duì)這n種資產(chǎn)進(jìn)行了評(píng)估，估算出在這一時(shí)

13、期內(nèi)購(gòu)買Si的平均收益率為ri，并預(yù)測(cè)出購(gòu)買Si的風(fēng)險(xiǎn)損失率為qi。考慮到投資越分散，總的風(fēng)險(xiǎn)越小，公司確定，當(dāng)用這筆資金購(gòu)買若干種資產(chǎn)時(shí)，總體風(fēng)險(xiǎn)可用所投資的Si中最大的一個(gè)風(fēng)險(xiǎn)來(lái)度量。購(gòu)買Si要付交易費(fèi)，費(fèi)率為pi，并且當(dāng)購(gòu)買額不超過(guò)給定值ui時(shí)，交易費(fèi)按購(gòu)買ui計(jì)算（不買當(dāng)然無(wú)須付費(fèi)）。另外，假定同期銀行存款利率是r0, 且既無(wú)交易費(fèi)又無(wú)風(fēng)險(xiǎn)。（ r0 =5%）2006東北三省建模聯(lián)賽賽題B題（研究生、本科生）公平的競(jìng)賽評(píng)卷系統(tǒng)數(shù)學(xué)建模競(jìng)賽吸引了眾多的大學(xué)生、研究生甚至中學(xué)生的參與，越來(lái)越多的人關(guān)心競(jìng)賽評(píng)卷的公平性。現(xiàn)今大多數(shù)的評(píng)卷工作是這樣進(jìn)行的：先將答卷編成密號(hào)，評(píng)委由各參賽學(xué)校（2

14、0-50所）派出，按不同的題目分成幾個(gè)題組，每個(gè)題組由M個(gè)評(píng)委組成，評(píng)閱N份答卷，每份答卷經(jīng)L個(gè)評(píng)委評(píng)閱，評(píng)委對(duì)每份答卷給出等級(jí)分（A+，A，A-，B+，B，B-，C+ ，C，C-，D），如果L個(gè)評(píng)委給出的分?jǐn)?shù)基本一致，就給出這份答卷的平均分，否則需討論以達(dá)成一致（其中M = 5-10，N = 60-200，L = 3-5）。現(xiàn)在需要你解決如下問(wèn)題：1有A,B,C,D四個(gè)題目，P（P M）所學(xué)校參賽，給出一種答卷編號(hào)加密和解密的數(shù)學(xué)公式方法（其中題號(hào)為明號(hào)）；要求方法簡(jiǎn)單易算、可隨意變換且保密性能好；對(duì)你的方法給出分析。2每個(gè)題組的M個(gè)評(píng)委來(lái)自不同學(xué)校，給出一種評(píng)閱答卷分配的數(shù)學(xué)公式方法，要求

15、回避本校答卷，并且每個(gè)評(píng)委評(píng)閱的答卷盡可能廣泛，并滿足某些特殊的要求。3給出評(píng)分一致性或公正性的檢驗(yàn)方法，該方法要求對(duì)每個(gè)評(píng)委的公平性給出評(píng)價(jià)（某評(píng)委分?jǐn)?shù)普遍給的偏高或低屬于尺度偏差，不應(yīng)算作不公平，可在下面的問(wèn)題中調(diào)整）。4給出最終的分?jǐn)?shù)調(diào)整計(jì)算公式。該公式要處理那些可能出現(xiàn)的“不公平”，及尺度偏差。對(duì)可能出現(xiàn)的“不公平”構(gòu)造例子，說(shuō)明你的方法。5對(duì)評(píng)卷中的其他問(wèn)題（如采用百分制還是等級(jí)分，一份答卷由幾個(gè)評(píng)委評(píng)閱可以滿足既經(jīng)濟(jì)又公平，等等）提出你的看法和根據(jù)。6假定有35所學(xué)校298個(gè)參賽隊(duì)參賽，數(shù)據(jù)如附表。其中：數(shù)字前兩位代表學(xué)校，甲組選做A，B題；乙組選做C，D題；25名評(píng)委所屬的學(xué)校編

16、號(hào)為：1-17，20，21，22，24，26，28，29，30。每份試卷經(jīng)四位評(píng)委評(píng)閱，編號(hào)為15，22的只容許評(píng)C，D題，編號(hào)為26的只容許評(píng)A，B題，編號(hào)為1，4，6，12，16的評(píng)委要求評(píng)A題，編號(hào)為2，5，7，10的評(píng)委要求評(píng)B題；編號(hào)為24的評(píng)委要求評(píng)C題，編號(hào)為29的評(píng)委要求評(píng)D題。其余按所在學(xué)校的甲、乙組別及個(gè)人的要求安排。要求對(duì)問(wèn)題1，2給出具體的算法及結(jié)果。對(duì)問(wèn)題3，4，5給出模擬數(shù)據(jù)再進(jìn)行分析和運(yùn)算。數(shù)據(jù)全國(guó)高校研究生數(shù)學(xué)建模競(jìng)賽賽題2006D：學(xué)生面試問(wèn)題 高校自主招生是高考改革中的一項(xiàng)新生事物，現(xiàn)在仍處于探索階段。某高校擬在全面衡量考生的高中學(xué)習(xí)成績(jī)及綜合表現(xiàn)后再采用專

17、家面試的方式?jīng)Q定錄取與否。該校在今年自主招生中，經(jīng)過(guò)初選合格進(jìn)入面試的考生有N人，擬聘請(qǐng)老師M人。每位學(xué)生要分別接受4位老師（簡(jiǎn)稱該學(xué)生的“面試組”）的單獨(dú)面試。面試時(shí)，各位老師獨(dú)立地對(duì)考生提問(wèn)并根據(jù)其回答問(wèn)題的情況給出評(píng)分。由于這是一項(xiàng)主觀性很強(qiáng)的評(píng)價(jià)工作，老師的專業(yè)可能不同，他們的提問(wèn)內(nèi)容、提問(wèn)方式以及評(píng)分習(xí)慣也會(huì)有較大差異，因此面試同一位考生的“面試組”的具體組成不同會(huì)對(duì)錄取結(jié)果產(chǎn)生一定影響。為了保證面試工作的公平性，組織者提出如下要求：Y1. 每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡；Y2. 面試不同考生的“面試組”成員不能完全相同；Y3. 兩個(gè)考生的“面試組”中有兩位或三位老師相同的情形盡量

18、的少；Y4. 被任意兩位老師面試的兩個(gè)學(xué)生集合中出現(xiàn)相同學(xué)生的人數(shù)盡量的少。請(qǐng)回答如下問(wèn)題：?jiǎn)栴}一：設(shè)考生數(shù)N已知，在滿足Y2條件下，說(shuō)明聘請(qǐng)老師數(shù)M至少分別應(yīng)為多大，才能做到任兩位學(xué)生的“面試組”都沒(méi)有兩位以及三位面試?yán)蠋熛嗤那樾巍?wèn)題二：請(qǐng)根據(jù)Y1Y4的要求建立學(xué)生與面試?yán)蠋熤g合理的分配模型，并就N379，M24的情形給出具體的分配方案（每位老師面試哪些學(xué)生）及該方案滿足Y1Y4這些要求的情況。問(wèn)題三：假設(shè)面試?yán)蠋熤欣砜婆c文科的老師各占一半，并且要求每位學(xué)生接受兩位文科與兩位理科老師的面試，請(qǐng)?jiān)诖思僭O(shè)下分別回答問(wèn)題一與問(wèn)題二。問(wèn)題四：請(qǐng)討論考生與面試?yán)蠋熤g分配的均勻性和面試公平性的關(guān)

19、系。為了保證面試的公平性，除了組織者提出的要求外，你們認(rèn)為還有哪些重要因素需要考慮，試給出新的分配方案或建議。 Matlab優(yōu)化工具箱（Optimization toolbox） attgoal： 求解多目標(biāo)優(yōu)化問(wèn)題. constr： 求解約束非線性優(yōu)化問(wèn)題. fmin： 求解標(biāo)量非線性優(yōu)化問(wèn)題. fminu,fmins：求解無(wú)約束非線性優(yōu)化問(wèn)題. lp： 求解線性規(guī)劃問(wèn)題. minmax： 求解最小最大問(wèn)題. qp： 求解二次規(guī)劃問(wèn)題. seminf： 求解半無(wú)限問(wèn)題. conls： 求解線性約束最小二乘最優(yōu)解. curvefit： 非線性數(shù)據(jù)擬合. leastsq： 求解非線性最小二乘最優(yōu)問(wèn)題. nnls： 求解非負(fù)約束最小二乘最優(yōu)解 線性規(guī)