最優(yōu)化問題數(shù)學(xué)模型

關(guān)于最優(yōu)化問題數(shù)學(xué)模型

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

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

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

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

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

其中，極大值問題可以轉(zhuǎn)化為極小值問題來進(jìn)行求解。如求：

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

最優(yōu)化問題中的所有變量均為整數(shù)時，這類問題稱為整數(shù)規(guī)劃問題。整數(shù)規(guī)劃可分為線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃，以及混合整數(shù)規(guī)劃等。如果決策變量的取值要么為0，要么為1，則這樣的規(guī)劃問題稱為0－1規(guī)劃。2.整數(shù)規(guī)劃第9頁,共117頁，2024年2月25日，星期天問題：某班級準(zhǔn)備從5名游泳隊員中選擇4人組成接力隊，參加學(xué)校的4*100m混合泳接力比賽。5名隊員4種泳姿的百米平均成績?nèi)绫?-1，問應(yīng)如何選拔隊員組成接力隊？隊員甲已丙丁戊蝶泳仰泳蛙泳自由泳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的比賽,記，，否則記。

目標(biāo)函數(shù)：當(dāng)隊員i入選泳姿j時，表示該隊員的成績，否則。于是接力隊的成績可表示為

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

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

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

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

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

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

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

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

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

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

無論選擇哪一種表達(dá)，怎樣考慮約束條件，目標(biāo)函數(shù)都不可能是線性的。

現(xiàn)在看來，那年的題目建模只是在條件的考慮上和建模中目標(biāo)函數(shù)的表達(dá)方面較難一點。

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

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

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

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

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

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

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

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

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

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

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

階收斂的。該算法也是p

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

稱為線性收斂；當(dāng)且時，

稱為超線性收斂；當(dāng)時，

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

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

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

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

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

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

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

對Newton法進(jìn)行改進(jìn)，可得具有超線性收斂的且具有全局收斂性的阻尼Newton法或修正Newton法：當(dāng)時，有。第51頁,共117頁，2024年2月25日，星期天②Fletcher-Reeves共軛梯度法當(dāng)時，有。該算法的收斂速度介于梯度法和Newton法其中之間，既克服了前者的慢收斂性，又避免了后者計算量大和僅具有局部收斂性的缺陷。第52頁,共117頁，2024年2月25日，星期天（2）只有等式約束的非線性規(guī)劃問題通?？捎孟?、拉格朗日乘子法，將其化為無約束問題求解.（3）具有不等式約束的非線性規(guī)劃問題解起來很復(fù)雜，求解這一類問題，通常將不等式化為等式約束，再將約束問題化為無約束問題，用線性逼近的方法將非線性規(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)化極值問題若，均可微，則其極值點存在的必要條件是：注：更詳細(xì)的結(jié)論參閱有關(guān)書籍.⑶

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

a、求，時，則

b、求，時，則

c、求，時，則

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

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

在許多實際問題中，衡量一個方案的好壞標(biāo)準(zhǔn)往往不止一個，例如設(shè)計一個導(dǎo)彈，既要射程最遠(yuǎn)，又要燃料最省，還要精度最高.這一類問題統(tǒng)稱為多目標(biāo)最優(yōu)化問題或多目標(biāo)規(guī)劃問題.我們先來看一個投資計劃的例子.4.多目標(biāo)規(guī)劃第70頁,共117頁，2024年2月25日，星期天例：投資問題某公司在一段時間內(nèi)有a(億元)的資金可用于建廠投資。若可供選擇的項目記為1,2,…,m。而且一旦對第i個項目投資就用去ai億元；而這段時間內(nèi)可得收益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ī)劃模型問題一般要歸結(jié)為求最優(yōu)控制函數(shù)使某個泛函達(dá)到極值.求解泛函極值問題的方法主要有變分法和最優(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日，星期天一元函數(shù)的泰勒公式：第88頁,共117頁，2024年2月25日，星期天二元函數(shù)的泰勒公式:第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