最優(yōu)化問題數學模型

關于最優(yōu)化問題數學模型

數學家對最優(yōu)化問題的研究已經有很多年的歷史。以前解決最優(yōu)化問題的數學方法只限于古典求導方法和變分法，拉格朗日（Lagrange）乘數法解決等式約束下的條件極值問題。計算機技術的出現，使得數學家研究出了許多最優(yōu)化方法和算法用以解決以前難以解決的問題。一、最優(yōu)化模型的概述

解決最優(yōu)生產計劃、最優(yōu)設計、最優(yōu)策略….第2頁,共117頁，2024年2月25日，星期天

運用最優(yōu)化方法解決最優(yōu)化問題的一般方法步驟如下：①前期分析：分析問題，找出要解決的目標，約束條件，并確立最優(yōu)化的目標。②定義變量，建立最優(yōu)化問題的數學模型，列出目標函數和約束條件。③針對建立的模型，選擇合適的求解方法或數學軟件。④編寫程序，利用計算機求解。⑤對結果進行分析，討論諸如：結果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。第3頁,共117頁，2024年2月25日，星期天

最優(yōu)化模型分類方法有很多，可按變量、約束條件、目標函數個數、目標函數和約束條件的是否線性是否依賴時間等分類。根據目標函數，約束條件的特點將最優(yōu)化模型包含的主要內容大致如下劃分：線性規(guī)劃整數規(guī)劃

非線性規(guī)劃多目標規(guī)劃動態(tài)規(guī)劃對策論二、最優(yōu)化模型的分類第4頁,共117頁，2024年2月25日，星期天最優(yōu)化模型的求解方法分類第5頁,共117頁，2024年2月25日，星期天最優(yōu)化數學模型形式

其中，極大值問題可以轉化為極小值問題來進行求解。如求：

可以轉化為：三、最優(yōu)化模型的建立目標：求函數極值或最值，求取得極值時變量的取值。第6頁,共117頁，2024年2月25日，星期天1.線性規(guī)劃問題：某工廠在計劃期內要安排生產I、II兩種產品，已知生產單位產品所需的設備臺時及A、B兩種原材料的消耗，如下表所示12kg40原材料B16kg04原材料A8臺時21設備III該工廠每生產一件產品I可獲利2元，每生產一件產品II可獲利3元。問應如何安排計劃使該工廠獲利最多？第7頁,共117頁，2024年2月25日，星期天解：該工廠生產產品Ix1件，生產產品IIx2件，我們可建立如下數學模型：s.t.第8頁,共117頁，2024年2月25日，星期天

最優(yōu)化問題中的所有變量均為整數時，這類問題稱為整數規(guī)劃問題。整數規(guī)劃可分為線性整數規(guī)劃和非線性整數規(guī)劃，以及混合整數規(guī)劃等。如果決策變量的取值要么為0，要么為1，則這樣的規(guī)劃問題稱為0－1規(guī)劃。2.整數規(guī)劃第9頁,共117頁，2024年2月25日，星期天問題：某班級準備從5名游泳隊員中選擇4人組成接力隊，參加學校的4*100m混合泳接力比賽。5名隊員4種泳姿的百米平均成績如表2-1，問應如何選拔隊員組成接力隊？隊員甲已丙丁戊蝶泳仰泳蛙泳自由泳66.8秒57.2787067.475.6668758.666.45367.874.27184.659.469.657.283.862.4表2-1第10頁,共117頁，2024年2月25日，星期天問題分析：記甲、乙、丙、丁、戊分別為i=1,2,3,4,5;記泳姿j=1,2,3,4.記隊員i的第

j種泳姿的百米最好成績?yōu)閏_ij(s),則表2-1可以表示成表2-2.c_iji=1i=2i=3i=4i=5j=1j=2j=3j=466.857.2787067.475.6668758.666.45367.874.27184.659.469.657.283.862.4表2-2第11頁,共117頁，2024年2月25日，星期天

決策變量：引入0-1變量，若選擇隊員i參加泳姿j的比賽,記，，否則記。

目標函數：當隊員i入選泳姿j時，表示該隊員的成績，否則。于是接力隊的成績可表示為

約束條件：根據接力隊要求，滿足約束條件a.每人最多只能入選4種泳姿之一，即b.每種泳姿必須有1人而且只能有一人入選，即第12頁,共117頁，2024年2月25日，星期天

綜上所述，這個問題的優(yōu)化模型可寫作：第13頁,共117頁，2024年2月25日，星期天非線性規(guī)劃問題的一般數學模型：其中，，為目標函數，為約束函數，這些函數中至少有一個是非線性函數。3.非線性規(guī)劃第14頁,共117頁，2024年2月25日，星期天應用實例：供應與選址

某公司有6個建筑工地要開工，每個工地的位置（用平面坐標系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出．目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20t．假設從料場到工地之間均有直線道路相連．（1）試制定每天的供應計劃，即從A，B兩料場分別向各工地運送多少水泥，可使總的噸千米數最?。?）為了進一步減少噸千米數，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20t，問應建在何處，節(jié)省的噸千米數有多大？第15頁,共117頁，2024年2月25日，星期天建立模型

記工地的位置為(ai，bi)，水泥日用量為di，i=1,…,6;料場位置為(xj，yj)，日儲量為ej，j=1,2；料場j向工地i的運送量為Xij．當用臨時料場時決策變量為：Xij，當不用臨時料場時決策變量為：Xij，xj，yj．第16頁,共117頁，2024年2月25日，星期天

事實上，客觀世界中的大多問題都是非線性的，給予線性化處理是近似的，是在作了科學的假設和簡化后得到的.另一方面，有一些是不能進行線性化處理的，否則將嚴重影響模型對實際問題近似的可依賴型.

由于非線性規(guī)劃問題在理論分析和計算上通常是很困難的，也不能像線性規(guī)劃那樣給出簡潔的結果形式和全面透徹的結論.所以，在數學建模時，要進行認真的分析，對實際問題進行合理的假設、簡化，首先考慮用線性規(guī)劃模型，若線性近似誤差較大時，則考慮用非線性規(guī)劃.第17頁,共117頁，2024年2月25日，星期天

在約1萬米的高空的某邊長為160km的正方形區(qū)域內，經常有若干架飛機作水平飛行，區(qū)域內每架飛機的位置和速度向量均由計算機記錄其數據，以便進行飛行管理。當一架欲進入該區(qū)域的飛機到達區(qū)域邊緣時，計算機記錄其數據后，要立即計算并判斷是否會發(fā)生碰撞。若會發(fā)生碰撞，則應計算如何調整各架飛機（包括新進入的飛機）飛行的方向角，以避免碰撞，且使飛機的調整的幅度盡量小，例11995年全國數學建模A題：飛行管理問題例題講解第18頁,共117頁，2024年2月25日，星期天該題比較有意思的一句話是：“使調整弧度最小”開放性的一句話，沒有限制得很死，較靈活，給參賽者的創(chuàng)新空間比較大一些，使得構建模型的目標函數表現形式很多，再加上模型求解方法（算法）的多樣性，從而可以呈現出五花八門的論文。第19頁,共117頁，2024年2月25日，星期天不碰撞的標準為任意兩架飛機的距離大于8km;假設條件：飛機飛行的方向角調整幅度不應超過；（因飛機飛行的速度變化不大）所有飛機的飛行速度v均為800km/h;有時需要通過查閱文獻、資料給出合理假設注：第20頁,共117頁，2024年2月25日，星期天進入該區(qū)域的飛機在到達區(qū)域邊緣時，與區(qū)域內飛機的距離應在60km以上；最多需考慮六架飛機；不必考慮飛機離開此區(qū)域后的狀況。根據當年競賽題目給出的數據，可以驗證新進入的飛機與區(qū)域內的飛機的距離超過60公里。根據當年競賽題目給出的數據，可以驗證區(qū)域內的飛機不超過架(包括新進入的)。第21頁,共117頁，2024年2月25日，星期天個人的想法不同，隊友之間爭執(zhí)不下的情況下，若時間允許，都可一一寫到論文中去，建立的模型一、模型二……；或者經討論后，選擇一個認為更合理的?，F在看來，無論是構建模型，還是計算，都不太難。本例題未給出數據，將重點放在如何構建模型上第22頁,共117頁，2024年2月25日，星期天解：(1)不考慮飛機的尺寸，用點代表飛機；(2)已在區(qū)域內的5架飛機按給定的方向角作直線飛行，則必不會碰撞，也不會發(fā)生意外；(應該根據題目中所給出的數據簡單的驗證一下)(3)飛機調整方向角的過程可在瞬間完成,(不計調整方向所花費的時間)。為解決該問題，補充假設：第23頁,共117頁，2024年2月25日，星期天變量、參數的符號假設（為了建模）在區(qū)域內飛行飛時間（可以根據數據算出來）第24頁,共117頁，2024年2月25日，星期天四種情況：四個象限，易用4個表達式表示說明：用初等數學的知識即可完成，思考：在哪個時間段某兩架飛機可能相撞？Infact,我們只需考慮兩架飛機同時在區(qū)域內飛行時的情況，也就是說，才是同在區(qū)域內的狀況。記為第25頁,共117頁，2024年2月25日，星期天根據題目條件，需計算第架飛機之間的最短距離第26頁,共117頁，2024年2月25日，星期天為此，我們可以給出原問題的模型如下：思考：是否還有其他的表達形式？非線性規(guī)劃模型分別從目標函數和約束條件角度思考第27頁,共117頁，2024年2月25日，星期天首先思考一下目標函數是否有其它的表達？同學們首先想到的可能是Oh,Sorry!有正有負抵消第28頁,共117頁，2024年2月25日，星期天最小一乘法最小二乘法

因最小一乘法帶絕對值，不好計算，以上兩式，比較而言，后者較好。為了避免抵消or第29頁,共117頁，2024年2月25日，星期天有的隊員這樣考慮：令為,轉化為二次規(guī)劃用到經驗模型中確定參數的近似準則:就所有飛機而言，讓調整弧度最大的即盡可能小，Chebshavf準則第30頁,共117頁，2024年2月25日，星期天其次討論一下約束條件是否有其它表達？

若考慮區(qū)域內不發(fā)生碰撞（若時間允許，也可以考慮出了區(qū)域的情況，另外建模）、錯層飛行（飛高或者飛低避免碰撞），進行模型的進一步改進，重點應放在解決問題的方法上。

如第31頁,共117頁，2024年2月25日，星期天

無論選擇哪一種表達，怎樣考慮約束條件，目標函數都不可能是線性的。

現在看來，那年的題目建模只是在條件的考慮上和建模中目標函數的表達方面較難一點。

是一個帶不等式約束的非線性規(guī)劃問題。

而且不可能轉化成線性的形式。第32頁,共117頁，2024年2月25日，星期天非線性規(guī)劃模型按約束條件可分為以下三類：⑴無約束非線性規(guī)劃模型：⑵

等式約束非線性規(guī)劃模型：⑶

不等式約束非線性規(guī)劃模型：第33頁,共117頁，2024年2月25日，星期天如數據擬合的最小二乘問題就是一個無約束極值問題。

其思想是：觀察點（實驗數據點）到曲線的距離的平方之和最?、艧o約束非線性規(guī)劃模型：第34頁,共117頁，2024年2月25日，星期天理論上無約束極值問題可化成求解

即解一個n元方程組，且往往是非線性方程組。

而一般說來，非線性方程組的求解并不比求無約束極值容易。第35頁,共117頁，2024年2月25日，星期天求解無約束極值問題的基本方法：迭代法

從一個給定的初始可行點出發(fā)，依次產生一個可行點列的一個極小值點,恰好是使得某個基本思路：或收斂于,稱具有這種性質的算法是收斂的.第36頁,共117頁，2024年2月25日，星期天由迭代到時,記即其中向量為搜索方向,實數稱為步長,確定以后,由可唯一地確定從出發(fā)就可確定點列第37頁,共117頁，2024年2月25日，星期天迭代的方法很多,各種迭代法的區(qū)別在于選取的方式不同,而尤為關鍵.一般要求遞減,具有這種性質的算法叫做下降算法.第38頁,共117頁，2024年2月25日，星期天若已得下降得最多,并確定了的可行下降方向上選取步長則在射線使且使即求求的過程稱為一維搜索.1.下降算法第39頁,共117頁，2024年2月25日，星期天于是一維搜索歸結為求解一維無約束極值問題:

其算法有Newton法、平分法、黃金分割法（0.618法）、分數法（Fibonacci法）、拋物線法（二次插值法）等，前兩種算法需計算的導數，后三種算法只需計算的函數值。下面僅介紹Newton法，對其他方法的了解可參考有關書籍。第40頁,共117頁，2024年2月25日，星期天按

給定初始可行點和控制誤差，迭代格式迭代，當時，即求得的最優(yōu)解的近似解停止計算。Newton法介紹第41頁,共117頁，2024年2月25日，星期天

♂一個好的算法必須以較快的速度收斂到最優(yōu)解。設算法產生的點列收斂于最優(yōu)解若存在及使則稱為p

階收斂的。該算法也是p

階收斂的。第42頁,共117頁，2024年2月25日，星期天

稱為線性收斂；當且時，

稱為超線性收斂；當時，

稱為平方收斂；當時，第43頁,共117頁，2024年2月25日，星期天一個算法是否收斂，往往與的選取有關①若當充分接近時，由算法產生的點列才收斂于則稱該算法為具有局部收斂性的算法；②若對則稱該算法為具有全局收斂性的算法。由算法產生的點列均收斂于第44頁,共117頁，2024年2月25日，星期天Newton法是平方收斂的，具有局部收斂性；拋物線法是超線性收斂的，具有全局收斂性；平分法、黃金分割法、分數法是線性收斂的，具有全局收斂性。常見一維搜索算法的收斂性第45頁,共117頁，2024年2月25日，星期天當具有多個極小值點時，則算法求得的往往是的一個局部極小值點。此時可改變的取值，重新迭代求解。

若求得多個極小值點，則從中選擇一個較滿意的結果。

♂說明：第46頁,共117頁，2024年2月25日，星期天1847年Cauchy提出了第一個無約束極值問題的算法——梯度法或最速下降法：2.梯度法第47頁,共117頁，2024年2月25日，星期天例題：應用梯度法求解解：第48頁,共117頁，2024年2月25日，星期天

該算法具有全局收斂性，是線性收斂的，但有時是很慢的線性收斂，這似乎與“最速下降”矛盾。其實不然，最速下降方向函數在某點處的局部性質，對局部來說是最速下降方向，對全局來說卻不一定是最速下降方向，故梯度法不是有效的實用算法。

通過對它改進或利用它與其他收斂快的算法相結合可得Newton法、Fletcher-Reeves共軛梯度法、變尺度法和Powell法等有效算法。第49頁,共117頁，2024年2月25日，星期天

下面僅介紹前兩者，對后兩者的了解可參閱有關書籍。當時，則。其中稱為在處的Hesse矩陣。①Newton法第50頁,共117頁，2024年2月25日，星期天

該算法是平方收斂的，具有局部收斂性。

對Newton法進行改進，可得具有超線性收斂的且具有全局收斂性的阻尼Newton法或修正Newton法：當時，有。第51頁,共117頁，2024年2月25日，星期天②Fletcher-Reeves共軛梯度法當時，有。該算法的收斂速度介于梯度法和Newton法其中之間，既克服了前者的慢收斂性，又避免了后者計算量大和僅具有局部收斂性的缺陷。第52頁,共117頁，2024年2月25日，星期天（2）只有等式約束的非線性規(guī)劃問題通?？捎孟?、拉格朗日乘子法，將其化為無約束問題求解.（3）具有不等式約束的非線性規(guī)劃問題解起來很復雜，求解這一類問題，通常將不等式化為等式約束，再將約束問題化為無約束問題，用線性逼近的方法將非線性規(guī)劃問題化為線性規(guī)劃問題.

下面先介紹一個簡單的非線性規(guī)劃問題的例子，其中的一些約束條件是等式，這類非線性規(guī)劃問題可用拉格朗日方法求解.第53頁,共117頁，2024年2月25日，星期天第54頁,共117頁，2024年2月25日，星期天第55頁,共117頁，2024年2月25日，星期天第56頁,共117頁，2024年2月25日，星期天第57頁,共117頁，2024年2月25日，星期天Kuhn-Tucker定理：對于不等式約束非線性最優(yōu)化極值問題若，均可微，則其極值點存在的必要條件是：注：更詳細的結論參閱有關書籍.⑶

不等式約束非線性規(guī)劃模型第58頁,共117頁，2024年2月25日，星期天注：1、庫-圖條件是判別有約束極值點的必要條件，并非充分條件。但是對于凸函數、凸集問題也是判別其極值點的充分條件。固此時的局部最優(yōu)解也必為全局的最優(yōu)解。2、庫-圖乘子與拉格朗日乘子類似。但拉格朗日乘子的符號不是確定的，可正可負；而庫-恩乘子的符號是確定的，其規(guī)律為：

a、求，時，則

b、求，時，則

c、求，時，則

d、求，時，則第59頁,共117頁，2024年2月25日，星期天罰函數法:

約束最優(yōu)化問題化為無約束最優(yōu)化問題的一種求解方法第60頁,共117頁，2024年2月25日，星期天第61頁,共117頁，2024年2月25日，星期天罰函數法的步驟：（等式約束最優(yōu)化問題罰函數法）第62頁,共117頁，2024年2月25日，星期天第63頁,共117頁，2024年2月25日，星期天第64頁,共117頁，2024年2月25日，星期天第65頁,共117頁，2024年2月25日，星期天罰函數法步驟：（不等式約束最優(yōu)化問題罰函數法）第66頁,共117頁，2024年2月25日，星期天第67頁,共117頁，2024年2月25日，星期天第68頁,共117頁，2024年2月25日，星期天注：罰函數法更多的詳細改進工作，需參閱相關書籍第69頁,共117頁，2024年2月25日，星期天

在許多實際問題中，衡量一個方案的好壞標準往往不止一個，例如設計一個導彈，既要射程最遠，又要燃料最省，還要精度最高.這一類問題統稱為多目標最優(yōu)化問題或多目標規(guī)劃問題.我們先來看一個投資計劃的例子.4.多目標規(guī)劃第70頁,共117頁，2024年2月25日，星期天例：投資問題某公司在一段時間內有a(億元)的資金可用于建廠投資。若可供選擇的項目記為1,2,…,m。而且一旦對第i個項目投資就用去ai億元；而這段時間內可得收益ci億元。問如何確定最佳的投資方案？

最佳投資方案：投資最少，收益最大！第71頁,共117頁，2024年2月25日，星期天投資最少：約束條件為：收益最大：第72頁,共117頁，2024年2月25日，星期天第73頁,共117頁，2024年2月25日，星期天第74頁,共117頁，2024年2月25日，星期天第75頁,共117頁，2024年2月25日，星期天第76頁,共117頁，2024年2月25日，星期天第77頁,共117頁，2024年2月25日，星期天第78頁,共117頁，2024年2月25日，星期天第79頁,共117頁，2024年2月25日，星期天第80頁,共117頁，2024年2月25日，星期天第81頁,共117頁，2024年2月25日，星期天第82頁,共117頁，2024年2月25日，星期天5.動態(tài)規(guī)劃

動態(tài)規(guī)劃模型問題一般要歸結為求最優(yōu)控制函數使某個泛函達到極值.求解泛函極值問題的方法主要有變分法和最優(yōu)控制理論方法.第83頁,共117頁，2024年2月25日，星期天第84頁,共117頁，2024年2月25日，星期天第85頁,共117頁，2024年2月25日，星期天第86頁,共117頁，2024年2月25日，星期天第87頁,共117頁，2024年2月25日，星期天一元函數的泰勒公式：第88頁,共117頁，2024年2月25日，星期天二元函數的泰勒公式:第89頁,共117頁，2024年2月25日，星期天其中記號表示表示第90頁,共117頁，2024年2月25日，星期天第91頁,共117頁，2024年2月25日，星期天第92頁,共117頁，2024年2月25日，星期天第93頁,共117頁，2024年2月25日，星期天第94頁,共117頁，2024年2月25日，星期天第95頁,共117頁，2024年2月25日，星期天第96頁,共117頁，2024年2