第三章最優(yōu)化計(jì)算問(wèn)題概論 最優(yōu)化問(wèn)題 最優(yōu)化問(wèn)題的提出實(shí)例生產(chǎn)計(jì)劃中 在各種資源有限的前提下 如何安排生產(chǎn) 使生產(chǎn)成本達(dá)到最低 工程施工中 要鋪設(shè)一條從A地到B地輸油管道 中間要經(jīng)過(guò)n個(gè)中間站 而對(duì)于每個(gè)中間站又有mi個(gè)可選方案 如果各個(gè)方案在不同兩點(diǎn)間的所需經(jīng)費(fèi)已知 如何選擇一條最佳路線 使得總費(fèi)用最低 金融投資中 如何選擇和設(shè)計(jì)證券組合或者投資項(xiàng)目組合 以便在可以接受的風(fēng)險(xiǎn)限度內(nèi)獲得盡可能大的投資回報(bào) 機(jī)械設(shè)計(jì)中 如何在滿足工作條件 裁荷和工藝要求 并在強(qiáng)度 剛度 壽命 尺寸范圍及其他一些技術(shù)要求的限制條件下 尋找一組參數(shù) 以獲得設(shè)計(jì)指標(biāo)達(dá)到最優(yōu)的設(shè)計(jì)方案 針對(duì)化學(xué)過(guò)程如何設(shè)計(jì)控制方案 才能既優(yōu)化其性能 又能保證其魯棒性 在電力分配中 由N個(gè)火力發(fā)電廠組成一個(gè)供電網(wǎng) 要求輸出總負(fù)荷為S 該如何分配每個(gè)發(fā)電廠的發(fā)電量 在滿足各電廠發(fā)電量約束的條件下使得總的生產(chǎn)消耗為最小 數(shù)學(xué)描述上述各類問(wèn)題資源的最優(yōu)利用問(wèn)題 所有類似的這種課題統(tǒng)稱為最優(yōu)化問(wèn)題 研究解決這些問(wèn)題的科學(xué)一般就總稱之為最優(yōu)化理論和方法 用數(shù)學(xué)語(yǔ)言描述的話 最優(yōu)化方法就是在給定的約束條件下 如何在某種范圍內(nèi)選取一些決策變量的取值 使得一個(gè)或者多個(gè)既定目標(biāo)達(dá)到最優(yōu)狀態(tài) 極大 極小或者某種妥協(xié)狀態(tài) 的一門學(xué)科 最優(yōu)化理論和方法的產(chǎn)生和發(fā)展 一些古老的方法黃金分割法阿基米德證明 如果給定平面幾何圖形的周長(zhǎng) 則在各種圖形中 圓所包圍的面積為最大 古典最優(yōu)化方法 精確的分析方法理論基礎(chǔ)的建立 牛頓和萊布尼茨在他們所創(chuàng)建的微積分理論有約束的最優(yōu)化問(wèn)題變分法最優(yōu)化理論和方法由于軍事上的需要產(chǎn)生了運(yùn)籌學(xué)線性規(guī)劃 非線性規(guī)劃 動(dòng)態(tài)規(guī)劃現(xiàn)代優(yōu)化方法遺傳算法神經(jīng)網(wǎng)絡(luò)模擬退火 最優(yōu)化問(wèn)題的典型實(shí)例 資源利用問(wèn)題某工廠生產(chǎn)A B兩種產(chǎn)品 制造1噸A產(chǎn)品需要耗煤8噸 耗電3千瓦 耗時(shí)2個(gè)工作日 制造1噸B產(chǎn)品需要耗煤4噸 用電4千瓦 耗時(shí)9個(gè)工作日 已知制造1噸產(chǎn)品A和B分別可以獲利6000元和8000元 現(xiàn)在該廠原料有煤300噸 電100千瓦 如果需要在200工作日內(nèi)生產(chǎn)這兩種產(chǎn)品并達(dá)到利潤(rùn)最大 應(yīng)當(dāng)如何安排A和B的生產(chǎn)數(shù)量 最優(yōu)化問(wèn)題的典型實(shí)例 資源利用問(wèn)題問(wèn)題分析設(shè)x1和x2分別代表產(chǎn)品A B計(jì)劃數(shù) 單位 噸 f表示利潤(rùn) 單位 千元 則問(wèn)題就是確定A B的生產(chǎn)數(shù)量x1和x2 既可以充分利用資源 又可以使利潤(rùn)最大化生產(chǎn)A可獲利8x1 千元 生產(chǎn)B可獲利8x2 千元 故目標(biāo)函數(shù)為優(yōu)化設(shè)計(jì)的目標(biāo)就是使得函數(shù)f最大化煤的消耗總量應(yīng)該小于300噸電力資源的消耗不得高于其供應(yīng)量100千瓦勞動(dòng)力時(shí)間的消耗不得高于300工作日每種產(chǎn)品數(shù)量滿足非負(fù)限制數(shù)學(xué)模型模型表達(dá) 最優(yōu)化問(wèn)題的典型實(shí)例 分派問(wèn)題假設(shè)某個(gè)項(xiàng)目有4項(xiàng)連續(xù)的任務(wù)構(gòu)成 即完成了任務(wù)1才能開(kāi)始任務(wù)2 完成了任務(wù)2之后才能開(kāi)始任務(wù)3 以此類推 并且規(guī)定由項(xiàng)目組中的甲乙丙丁四名成員每人完成且僅完成其中的一項(xiàng)任務(wù) 四個(gè)項(xiàng)目組成員分別完成四項(xiàng)任務(wù)的時(shí)間如表所示 應(yīng)該如何分配這些任務(wù) 即讓哪個(gè)成員去完成哪個(gè)任務(wù) 可以使得花費(fèi)的總時(shí)間最短 最優(yōu)化問(wèn)題的典型實(shí)例 分派問(wèn)題問(wèn)題分析設(shè)計(jì)變量其中xij為0 1變量 i代表項(xiàng)目組成員的序號(hào) j代表任務(wù)的序號(hào) 則 x11 x12 x13 x14分別代表指派甲完成任務(wù)1 任務(wù)2 任務(wù)3 任務(wù)4x21 x22 x23 x24分別代表指派乙完成任務(wù)1 任務(wù)2 任務(wù)3 任務(wù)4x31 x32 x33 x34分別代表指派丙完成任務(wù)1 任務(wù)2 任務(wù)3 任務(wù)4x41 x42 x43 x44分別代表指派丁完成任務(wù)1 任務(wù)2 任務(wù)3 任務(wù)4該問(wèn)題的目標(biāo)就是選擇一種合適的一對(duì)一的組合 使得最后所花費(fèi)的時(shí)間總和最小 根據(jù)上述假設(shè) 我們可以得到目標(biāo)函數(shù) 即所花費(fèi)的總時(shí)間為 最優(yōu)化問(wèn)題的典型實(shí)例 分派問(wèn)題問(wèn)題分析每個(gè)人只能完成一項(xiàng)任務(wù)每項(xiàng)工作有且僅有一人去完成數(shù)學(xué)模型 最優(yōu)化問(wèn)題的典型實(shí)例 投資決策問(wèn)題某企業(yè)有n個(gè)項(xiàng)目可供選擇投資 并且至少要對(duì)其中一個(gè)項(xiàng)目投資 已知該企業(yè)擁有總資金A元 投資于第i i 1 2 n 個(gè)項(xiàng)目需花資金ai元 并預(yù)計(jì)可收益bi元 試選擇最佳投資方案 最優(yōu)化問(wèn)題的典型實(shí)例 投資決策問(wèn)題問(wèn)題分析我們可以設(shè)定該問(wèn)題的目標(biāo)是要在選擇相應(yīng)投資項(xiàng)目之后使得投資收益率最大 對(duì)于某項(xiàng)目我們是投資還是不投資 于是我們令設(shè)計(jì)變量為xi i 1 2 n 其中當(dāng)我們決定投資第i個(gè)項(xiàng)目時(shí) xi 1 當(dāng)我們決定不投資第i個(gè)項(xiàng)目時(shí) xi 0目標(biāo)為投資收益率最大 故目標(biāo)函數(shù)應(yīng)為總收益和總投資的比值至少要對(duì)一個(gè)項(xiàng)目投資 并且總的投資金額不能超過(guò)總資金A由于xi i 1 2 n 只取值0或1數(shù)學(xué)模型 最優(yōu)化問(wèn)題的數(shù)學(xué)描述 最優(yōu)化問(wèn)題的數(shù)學(xué)模型由各例子可以看出 最優(yōu)化問(wèn)題涉及的領(lǐng)域非常廣泛 形式也千變?nèi)f化 各自有不同的機(jī)理和解決方法 但是它們卻可以用統(tǒng)一的數(shù)學(xué)形式表達(dá) 簡(jiǎn)單的說(shuō) 均可以轉(zhuǎn)化為最小 或最大 化一個(gè)n維變量x的實(shí)函數(shù)f x 其中對(duì)變量含有多種約束 一般情況下 最優(yōu)化問(wèn)題的數(shù)學(xué)模型可以表達(dá)如下 最優(yōu)化問(wèn)題的三要素設(shè)計(jì)變量目標(biāo)函數(shù)約束條件 最優(yōu)化問(wèn)題的數(shù)學(xué)描述 最優(yōu)化問(wèn)題分類根據(jù)設(shè)計(jì)變量的特征分類按照設(shè)計(jì)變量的維數(shù)進(jìn)行分類 一維優(yōu)化問(wèn)題 n維優(yōu)化問(wèn)題根據(jù)設(shè)計(jì)變量的取值進(jìn)行分類 離散最優(yōu)化和連續(xù)最優(yōu)化根據(jù)目標(biāo)函數(shù)的類型分類只有一個(gè)目標(biāo)的優(yōu)化問(wèn)題稱為單目標(biāo)優(yōu)化問(wèn)題存在兩個(gè)或者兩個(gè)以上目標(biāo)函數(shù)的優(yōu)化問(wèn)題 稱為多目標(biāo)優(yōu)化問(wèn)題根據(jù)約束條件的類型分類有無(wú)約束 無(wú)約束優(yōu)化問(wèn)題和約束優(yōu)化問(wèn)題約束類型 線性規(guī)劃 二次規(guī)劃 整數(shù)規(guī)劃 0 1規(guī)劃 非線性規(guī)劃等根據(jù)最優(yōu)化問(wèn)題的解分類如果最優(yōu)化問(wèn)題的解不隨時(shí)間變化 則稱其為靜態(tài)最優(yōu)化問(wèn)題或參數(shù)最優(yōu)化問(wèn)題如果最優(yōu)化問(wèn)題的解隨時(shí)間而變 則稱其為動(dòng)態(tài)最優(yōu)化問(wèn)題 最優(yōu)化問(wèn)題的解決方案 解決方案的步驟提出需要進(jìn)行最優(yōu)化的問(wèn)題 確定研究問(wèn)題的范圍 并為問(wèn)題的解決準(zhǔn)備一些先決條件 例如與問(wèn)題相關(guān)的數(shù)據(jù)和資料建立能夠反映上述實(shí)際情況的最優(yōu)化問(wèn)題的數(shù)學(xué)模型 確定設(shè)計(jì)變量 目標(biāo)函數(shù)和有關(guān)約束條件對(duì)建立的數(shù)學(xué)模型進(jìn)行分析和修正 選擇合適的優(yōu)化算法運(yùn)用合適的軟件編寫(xiě)優(yōu)化算法程序 對(duì)最優(yōu)化模型進(jìn)行求解如果是理論問(wèn)題 對(duì)優(yōu)化結(jié)果進(jìn)行分析和比較 總結(jié)規(guī)律 如果是實(shí)際問(wèn)題 將所獲得的最優(yōu)解應(yīng)用到實(shí)際問(wèn)題中進(jìn)行驗(yàn)證和實(shí)施 再進(jìn)行理論分析解決方案的關(guān)鍵問(wèn)題數(shù)學(xué)模型的建立優(yōu)化算法的編制 最優(yōu)化問(wèn)題的解決方案 優(yōu)化問(wèn)題的求解方法解析法對(duì)于最優(yōu)化數(shù)學(xué)模型中的目標(biāo)函數(shù)和約束條件 如果其具有明確的數(shù)學(xué)解析表達(dá)式 則一般可以按照函數(shù)求極值的必要條件 用導(dǎo)數(shù)方法或者變分法等數(shù)學(xué)分析的手段求出其解析解 然后按照問(wèn)題的實(shí)際物理意義確定問(wèn)題的最優(yōu)解 數(shù)值解法如果目標(biāo)函數(shù)或者約束條件較為復(fù)雜 或者并沒(méi)有明確的數(shù)學(xué)解析表達(dá)式 抑或是以現(xiàn)有的解析方法和手段無(wú)法求取解析解的優(yōu)化問(wèn)題 我們可以用數(shù)值解法來(lái)解決 在現(xiàn)在計(jì)算機(jī)高速發(fā)展的時(shí)代 數(shù)值算法則顯示出了其優(yōu)越性 其基本的思想就是用搜索的方法經(jīng)過(guò)一系列的迭代 使得產(chǎn)生的這些序列能夠逐步逼近問(wèn)題的最優(yōu)解 數(shù)值解法常常需要經(jīng)驗(yàn)或者試驗(yàn) 同時(shí)結(jié)果也需要通過(guò)實(shí)際問(wèn)題的驗(yàn)證才是有效的 混合解法混合解法即是結(jié)合了上述兩種方法 例如以梯度法為代表的一類解法 這類解法往往是解析法和數(shù)值算法相結(jié)合的一種方法其他優(yōu)化