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