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

1、2021/6/161最優(yōu)化模型最優(yōu)化模型一、最優(yōu)化模型的概述一、最優(yōu)化模型的概述二、最優(yōu)化模型的分類(lèi)二、最優(yōu)化模型的分類(lèi)三、最優(yōu)化模型的建立及求解三、最優(yōu)化模型的建立及求解四、最優(yōu)化模型的評(píng)價(jià)分析四、最優(yōu)化模型的評(píng)價(jià)分析2021/6/162 數(shù)學(xué)家對(duì)最優(yōu)化問(wèn)題的研究已經(jīng)有很多年的數(shù)學(xué)家對(duì)最優(yōu)化問(wèn)題的研究已經(jīng)有很多年的歷史。歷史。 以前解決最優(yōu)化問(wèn)題的數(shù)學(xué)方法只限于古典以前解決最優(yōu)化問(wèn)題的數(shù)學(xué)方法只限于古典求導(dǎo)方法和變分法，拉格朗日（求導(dǎo)方法和變分法，拉格朗日（LagrangeLagrange）乘數(shù)）乘數(shù)法解決等式約束下的條件極值問(wèn)題。法解決等式約束下的條件極值問(wèn)題。 計(jì)算機(jī)技術(shù)的出現(xiàn)，使得數(shù)學(xué)

2、家研究出了許計(jì)算機(jī)技術(shù)的出現(xiàn)，使得數(shù)學(xué)家研究出了許多最優(yōu)化方法和算法用以解決以前難以解決的問(wèn)多最優(yōu)化方法和算法用以解決以前難以解決的問(wèn)題。題。一、最優(yōu)化模型的概述一、最優(yōu)化模型的概述 解決最優(yōu)生產(chǎn)計(jì)劃、最優(yōu)設(shè)計(jì)、最優(yōu)策略解決最優(yōu)生產(chǎn)計(jì)劃、最優(yōu)設(shè)計(jì)、最優(yōu)策略.2021/6/163 運(yùn)用最優(yōu)化方法解決最優(yōu)化問(wèn)題的一般方運(yùn)用最優(yōu)化方法解決最優(yōu)化問(wèn)題的一般方法步驟如下：法步驟如下：前期分析：分析問(wèn)題，找出要解決的目標(biāo)，約束條件，前期分析：分析問(wèn)題，找出要解決的目標(biāo)，約束條件，并確立最優(yōu)化的目標(biāo)。并確立最優(yōu)化的目標(biāo)。定義變量，建立最優(yōu)化問(wèn)題的數(shù)學(xué)模型，列出目標(biāo)函定義變量，建立最優(yōu)化問(wèn)題的數(shù)學(xué)模型，列出目

3、標(biāo)函數(shù)和約束條件。數(shù)和約束條件。針對(duì)建立的模型，選擇合適的求解方法或數(shù)學(xué)軟件。針對(duì)建立的模型，選擇合適的求解方法或數(shù)學(xué)軟件。編寫(xiě)程序，利用計(jì)算機(jī)求解。編寫(xiě)程序，利用計(jì)算機(jī)求解。對(duì)結(jié)果進(jìn)行分析，討論諸如：結(jié)果的合理性、正確性，對(duì)結(jié)果進(jìn)行分析，討論諸如：結(jié)果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與算法的收斂性，模型的適用性和通用性，算法效率與誤差等。誤差等。2021/6/164 最優(yōu)化模型分類(lèi)方法有很多，可按變量、約最優(yōu)化模型分類(lèi)方法有很多，可按變量、約束條件、目標(biāo)函數(shù)個(gè)數(shù)、目標(biāo)函數(shù)和約束條件的束條件、目標(biāo)函數(shù)個(gè)數(shù)、目標(biāo)函數(shù)和約束條件的是否線性是否依賴時(shí)間等分類(lèi)。是否線性是

4、否依賴時(shí)間等分類(lèi)。 根據(jù)目標(biāo)函數(shù)，約束條件的特點(diǎn)將最優(yōu)化模根據(jù)目標(biāo)函數(shù)，約束條件的特點(diǎn)將最優(yōu)化模型包含的主要內(nèi)容大致如下劃分：型包含的主要內(nèi)容大致如下劃分： 線性規(guī)劃線性規(guī)劃 整數(shù)規(guī)劃整數(shù)規(guī)劃 非線性規(guī)劃非線性規(guī)劃 多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃 動(dòng)態(tài)動(dòng)態(tài)規(guī)劃規(guī)劃 對(duì)策論對(duì)策論二、最優(yōu)化模型的分類(lèi)二、最優(yōu)化模型的分類(lèi)2021/6/165最優(yōu)化模型的求解方法分類(lèi)最優(yōu)化模型的求解方法分類(lèi)圖克定理庫(kù)恩極值原理有約束變分法微分法無(wú)約束解析法-. 1. 5. 4網(wǎng)絡(luò)優(yōu)化方法多目標(biāo)優(yōu)化法隨機(jī)搜索法單純形法方向加速法步長(zhǎng)加速法坐標(biāo)輪換法多維搜索法插值法黃金分割法裴波那契法一維搜索法數(shù)值算法. 2復(fù)形法法法化有為無(wú)梯度

5、法梯度投影法可行方向法有約束梯度法變尺度法共軛梯度法擬牛頓法最速下降法無(wú)約束梯度法梯度算法SWIFTSUMT. 32021/6/166最優(yōu)化數(shù)學(xué)模型形式最優(yōu)化數(shù)學(xué)模型形式 min( )xf x. .( )0,1,2,.,( )0,1,2,.,iistg ximh xin 其中，極大值問(wèn)題可以轉(zhuǎn)化為極小值問(wèn)題來(lái)其中，極大值問(wèn)題可以轉(zhuǎn)化為極小值問(wèn)題來(lái)進(jìn)行求解。如求：進(jìn)行求解。如求：max( )xf x 可以轉(zhuǎn)化為：可以轉(zhuǎn)化為：min( )xf x三、最優(yōu)化模型的建立三、最優(yōu)化模型的建立目標(biāo)：求函數(shù)極值或最值，求取得極值時(shí)變量的取值。目標(biāo)：求函數(shù)極值或最值，求取得極值時(shí)變量的取值。2021/6/16

6、7問(wèn)題問(wèn)題：某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)：某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消兩種原材料的消耗，如下表所示耗，如下表所示 12kg40原材料原材料B16kg04原材料原材料A8臺(tái)時(shí)臺(tái)時(shí)21設(shè)備設(shè)備III該工廠每生產(chǎn)一件產(chǎn)品該工廠每生產(chǎn)一件產(chǎn)品I可獲利可獲利2元，每生產(chǎn)一件產(chǎn)品元，每生產(chǎn)一件產(chǎn)品II可獲利可獲利3元。問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？元。問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？ 2021/6/168解解：該工廠生產(chǎn)產(chǎn)品：該工廠生產(chǎn)產(chǎn)品I x1件，生產(chǎn)產(chǎn)品件，生產(chǎn)產(chǎn)品II x2件，件，我們

7、可建立如下數(shù)學(xué)模型：我們可建立如下數(shù)學(xué)模型：2132maxxxz0,12416482212121xxxxxxs.t. 2, 41421xxz2021/6/169 最優(yōu)化問(wèn)題中的所有變量均為整數(shù)時(shí)，這類(lèi)最優(yōu)化問(wèn)題中的所有變量均為整數(shù)時(shí)，這類(lèi)問(wèn)題稱為整數(shù)規(guī)劃問(wèn)題。問(wèn)題稱為整數(shù)規(guī)劃問(wèn)題。 整數(shù)規(guī)劃可分為線性整數(shù)規(guī)劃和非線性整數(shù)整數(shù)規(guī)劃可分為線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃規(guī)劃 ，以及混合整數(shù)規(guī)劃等。，以及混合整數(shù)規(guī)劃等。 如果決策變量的取值要么為如果決策變量的取值要么為0 0，要么為，要么為1 1，則，則這樣的規(guī)劃問(wèn)題稱為這樣的規(guī)劃問(wèn)題稱為0 01 1規(guī)劃。規(guī)劃。2021/6/1610問(wèn)題：?jiǎn)栴}：某班級(jí)

8、準(zhǔn)備從某班級(jí)準(zhǔn)備從5名名游泳隊(duì)員中選擇游泳隊(duì)員中選擇4人人組成接力隊(duì)，組成接力隊(duì)，參加學(xué)校的參加學(xué)校的4*100m混合泳接力比賽。混合泳接力比賽。5名隊(duì)員名隊(duì)員4種泳姿種泳姿的百的百米平均成績(jī)?nèi)绫砻灼骄煽?jī)?nèi)绫?-1，問(wèn)應(yīng)如何選拔隊(duì)員組成接力隊(duì)？，問(wèn)應(yīng)如何選拔隊(duì)員組成接力隊(duì)？隊(duì)員隊(duì)員甲甲已已丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳66.866.8秒秒57.257.27878707067.467.475.675.66666878758.658.666.466.4535367.867.874.274.2717184.684.659.459.469.669.657.257.283.883.8

9、62.462.4表表2-12-12021/6/1611問(wèn)題分析：?jiǎn)栴}分析：記甲、乙、丙、丁、戊分別為記甲、乙、丙、丁、戊分別為i i=1,2,3,4,5; =1,2,3,4,5; 記泳姿記泳姿j j=1,2,3,4.=1,2,3,4.記隊(duì)員記隊(duì)員 i i 的第的第 j j 種泳姿的百米最好種泳姿的百米最好成績(jī)?yōu)槌煽?jī)?yōu)閏_c_ijij(s),(s),則表則表2-12-1可以表示成表可以表示成表2-2.2-2.c_iji=1i=2i=3i=4i=5j=1j=2j=3j=466.866.857.257.27878707067.467.475.675.66666878758.658.666.466.4

10、535367.867.874.274.2717184.684.659.459.469.669.657.257.283.883.862.462.4表表2-22-22021/6/1612 決策變量：決策變量：引入引入0-1變量變量 ，若選擇隊(duì)員，若選擇隊(duì)員i參加泳姿參加泳姿j的的比賽比賽, 記，記， ，否則記，否則記 。 目標(biāo)函數(shù)：目標(biāo)函數(shù)：當(dāng)隊(duì)員當(dāng)隊(duì)員i入選泳姿入選泳姿j時(shí)，時(shí)， 表示該隊(duì)員的成表示該隊(duì)員的成績(jī)，否則績(jī)，否則 。于是接力隊(duì)的成績(jī)可表示為。于是接力隊(duì)的成績(jī)可表示為 約束條件：約束條件：根據(jù)接力隊(duì)要求，根據(jù)接力隊(duì)要求， 滿足約束條件滿足約束條件a. 每人最多只能入選每人最多只能入選4

11、種泳姿之一，即種泳姿之一，即b. 每種泳姿必須有每種泳姿必須有1人而且只能有一人入選，即人而且只能有一人入選，即ijx0ijx1ijx. 151iijx. 141jijxijx.4151jiijijxcf0ijijxcijijxc2021/6/1613 綜上所述，這個(gè)問(wèn)題的優(yōu)化模型可寫(xiě)作：綜上所述，這個(gè)問(wèn)題的優(yōu)化模型可寫(xiě)作：.1 , 0ijx. 4 , 3 , 2 , 1, 151jxiij. 5 , 4 , 3 , 2 , 1, 1. .41ixtsjij4151minjiijijxcf2021/6/1614非線性規(guī)劃問(wèn)題的一般數(shù)學(xué)模型：非線性規(guī)劃問(wèn)題的一般數(shù)學(xué)模型：其中，其中， ， 為目標(biāo)

12、函數(shù)，為目標(biāo)函數(shù)， 為約束函數(shù)，這些函數(shù)中至少有為約束函數(shù)，這些函數(shù)中至少有一個(gè)是非線性函數(shù)。一個(gè)是非線性函數(shù)。min( ). .( )0,1,2,( )0,1,2, .ijf xstg ximh xjlnEx)(xf)(),(xhxgji2021/6/1615應(yīng)用實(shí)例：應(yīng)用實(shí)例： 供應(yīng)與選址供應(yīng)與選址 某公司有某公司有6個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系a，b表示，距離單位：表示，距離單位：km）及水泥日用量）及水泥日用量d(t)由下表給出目前有由下表給出目前有兩個(gè)臨時(shí)料場(chǎng)位于兩個(gè)臨時(shí)料場(chǎng)位于A(5,1)，B(2,7)，日儲(chǔ)量，日儲(chǔ)量

13、各有各有20t假設(shè)從料場(chǎng)到假設(shè)從料場(chǎng)到工地之間均有直線道路相連工地之間均有直線道路相連 （1）試制定每天的供應(yīng)計(jì)劃，即從）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場(chǎng)兩料場(chǎng)分別向各工地運(yùn)分別向各工地運(yùn)送多少水泥，可使總的送多少水泥，可使總的噸千米數(shù)最小噸千米數(shù)最小 （2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩個(gè)新的，日儲(chǔ)量各為個(gè)新的，日儲(chǔ)量各為20t，問(wèn)應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？，問(wèn)應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？2021/6/1616建立模型建立模型 記工地的位置為記工地的位置為(ai，bi)，水泥日用量為，水泥日用量為

14、di，i=1,6;料場(chǎng)位置為料場(chǎng)位置為(xj，yj)，日儲(chǔ)量為，日儲(chǔ)量為ej，j=1,2；料場(chǎng)；料場(chǎng)j向工地向工地i的運(yùn)送量為的運(yùn)送量為Xij當(dāng)用臨時(shí)料場(chǎng)時(shí)決策變量為：當(dāng)用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，當(dāng)不用臨時(shí)料場(chǎng)時(shí)決策變量為：當(dāng)不用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，xj，yj2021/6/1617 事實(shí)上，客觀世界中的大多問(wèn)題都是非線性的，給事實(shí)上，客觀世界中的大多問(wèn)題都是非線性的，給予線性化處理是近似的，是在作了科學(xué)的假設(shè)和簡(jiǎn)化后予線性化處理是近似的，是在作了科學(xué)的假設(shè)和簡(jiǎn)化后得到的得到的. . 另一方面，有一些是不能進(jìn)行線性化處理的，另一方面，有一些是不能進(jìn)行線性化處理的，否則將嚴(yán)重影響模

15、型對(duì)實(shí)際問(wèn)題近似的可依賴型否則將嚴(yán)重影響模型對(duì)實(shí)際問(wèn)題近似的可依賴型. . 由于非線性規(guī)劃問(wèn)題在理論分析和計(jì)算上通常是很由于非線性規(guī)劃問(wèn)題在理論分析和計(jì)算上通常是很困難的，也不能像線性規(guī)劃那樣給出簡(jiǎn)潔的結(jié)果形式和困難的，也不能像線性規(guī)劃那樣給出簡(jiǎn)潔的結(jié)果形式和全面透徹的結(jié)論全面透徹的結(jié)論. . 所以，在數(shù)學(xué)建模時(shí)，要進(jìn)行認(rèn)真的所以，在數(shù)學(xué)建模時(shí)，要進(jìn)行認(rèn)真的分析，對(duì)實(shí)際問(wèn)題進(jìn)行合理的假設(shè)、簡(jiǎn)化，首先考慮用分析，對(duì)實(shí)際問(wèn)題進(jìn)行合理的假設(shè)、簡(jiǎn)化，首先考慮用線性規(guī)劃模型，線性規(guī)劃模型，若線性近似誤差較大時(shí)若線性近似誤差較大時(shí)，則考慮用非線，則考慮用非線性規(guī)劃性規(guī)劃. .2021/6/1618 在約在

16、約1萬(wàn)米的高空的某邊長(zhǎng)為萬(wàn)米的高空的某邊長(zhǎng)為160km的正方的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機(jī)作水平飛行，區(qū)形區(qū)域內(nèi)，經(jīng)常有若干架飛機(jī)作水平飛行，區(qū)域內(nèi)每架飛機(jī)的位置和速度向量均由計(jì)算機(jī)記域內(nèi)每架飛機(jī)的位置和速度向量均由計(jì)算機(jī)記錄其數(shù)據(jù)，以便進(jìn)行飛行管理。當(dāng)一架欲進(jìn)入錄其數(shù)據(jù)，以便進(jìn)行飛行管理。當(dāng)一架欲進(jìn)入該區(qū)域的飛機(jī)到達(dá)區(qū)域邊緣時(shí)，計(jì)算機(jī)記錄其該區(qū)域的飛機(jī)到達(dá)區(qū)域邊緣時(shí)，計(jì)算機(jī)記錄其數(shù)據(jù)后，要立即計(jì)算并判斷是否會(huì)發(fā)生碰撞。數(shù)據(jù)后，要立即計(jì)算并判斷是否會(huì)發(fā)生碰撞。若會(huì)發(fā)生碰撞，則應(yīng)計(jì)算若會(huì)發(fā)生碰撞，則應(yīng)計(jì)算如何調(diào)整如何調(diào)整各架飛機(jī)各架飛機(jī)（包括新進(jìn)入的飛機(jī)）飛行的方向角，以避免（包括新進(jìn)入的飛機(jī)

17、）飛行的方向角，以避免碰撞，且使飛機(jī)的調(diào)整的幅度盡量小，碰撞，且使飛機(jī)的調(diào)整的幅度盡量小，例例1 1995年全國(guó)數(shù)學(xué)建模年全國(guó)數(shù)學(xué)建模A題：飛行管理問(wèn)題題：飛行管理問(wèn)題例題講解例題講解2021/6/1619該題比較有意思的一句話是：該題比較有意思的一句話是： “使調(diào)整弧度最小使調(diào)整弧度最小”開(kāi)放性的一句話，沒(méi)有限制得很死，較靈活，開(kāi)放性的一句話，沒(méi)有限制得很死，較靈活，給參賽者的創(chuàng)新空間比較大一些，使得構(gòu)建模型給參賽者的創(chuàng)新空間比較大一些，使得構(gòu)建模型的目標(biāo)函數(shù)表現(xiàn)形式很多，再加上模型求解方法的目標(biāo)函數(shù)表現(xiàn)形式很多，再加上模型求解方法（算法）的多樣性，從而可以呈現(xiàn)出五花八門(mén)的（算法）的多樣性，

18、從而可以呈現(xiàn)出五花八門(mén)的論文。論文。2021/6/1620 不碰撞的標(biāo)準(zhǔn)為任意兩架飛機(jī)的距離大于不碰撞的標(biāo)準(zhǔn)為任意兩架飛機(jī)的距離大于8km;假設(shè)條件：假設(shè)條件：30 飛機(jī)飛行的方向角調(diào)整幅度不應(yīng)超過(guò)飛機(jī)飛行的方向角調(diào)整幅度不應(yīng)超過(guò) ； （因飛機(jī)飛行的速度變化不大）所有飛機(jī)的飛行（因飛機(jī)飛行的速度變化不大）所有飛機(jī)的飛行 速度速度 v 均為均為800km/h;有時(shí)需要通過(guò)查閱文獻(xiàn)、資料給出合理假設(shè)有時(shí)需要通過(guò)查閱文獻(xiàn)、資料給出合理假設(shè)注：注：2021/6/1621 進(jìn)入該區(qū)域的飛機(jī)在到達(dá)區(qū)域邊緣時(shí)，與區(qū)域內(nèi)進(jìn)入該區(qū)域的飛機(jī)在到達(dá)區(qū)域邊緣時(shí)，與區(qū)域內(nèi) 飛機(jī)的距離應(yīng)在飛機(jī)的距離應(yīng)在60km以上；以上

19、； 最多需考慮六架飛機(jī)；最多需考慮六架飛機(jī)； 不必考慮飛機(jī)離開(kāi)此區(qū)域后的狀況。不必考慮飛機(jī)離開(kāi)此區(qū)域后的狀況。根據(jù)當(dāng)年競(jìng)賽題目給出的數(shù)據(jù)，可以驗(yàn)證根據(jù)當(dāng)年競(jìng)賽題目給出的數(shù)據(jù)，可以驗(yàn)證新進(jìn)入的飛機(jī)與區(qū)域內(nèi)的飛機(jī)的距離超過(guò)新進(jìn)入的飛機(jī)與區(qū)域內(nèi)的飛機(jī)的距離超過(guò)60公里。公里。根據(jù)當(dāng)年競(jìng)賽題目給出的數(shù)據(jù)，可以驗(yàn)證根據(jù)當(dāng)年競(jìng)賽題目給出的數(shù)據(jù)，可以驗(yàn)證區(qū)域內(nèi)的飛機(jī)不超過(guò)架區(qū)域內(nèi)的飛機(jī)不超過(guò)架(包括新進(jìn)入的包括新進(jìn)入的)。2021/6/1622 個(gè)人的想法不同，隊(duì)友之間爭(zhēng)執(zhí)不下的情況下，個(gè)人的想法不同，隊(duì)友之間爭(zhēng)執(zhí)不下的情況下，若時(shí)間允許，都可一一寫(xiě)到論文中去，建立的模若時(shí)間允許，都可一一寫(xiě)到論文中去，建立

20、的模型一、模型二型一、模型二；或者經(jīng)討論后，選擇一個(gè)認(rèn)或者經(jīng)討論后，選擇一個(gè)認(rèn)為更合理的。為更合理的。 現(xiàn)在看來(lái)，無(wú)論是構(gòu)建模型，還是計(jì)算，都不太現(xiàn)在看來(lái)，無(wú)論是構(gòu)建模型，還是計(jì)算，都不太難。難。 本例題未給出數(shù)據(jù)，將重點(diǎn)放在如何構(gòu)建模型上本例題未給出數(shù)據(jù)，將重點(diǎn)放在如何構(gòu)建模型上2021/6/1623解：解：(1)不考慮飛機(jī)的尺寸，用點(diǎn)代表飛機(jī)；不考慮飛機(jī)的尺寸，用點(diǎn)代表飛機(jī)；(2)已在區(qū)域內(nèi)的已在區(qū)域內(nèi)的5架飛機(jī)按給定的方向角作架飛機(jī)按給定的方向角作 直線飛行，則必不會(huì)碰撞，也不會(huì)發(fā)生直線飛行，則必不會(huì)碰撞，也不會(huì)發(fā)生 意外；意外；(應(yīng)該根據(jù)題目中所給出的數(shù)據(jù)簡(jiǎn)應(yīng)該根據(jù)題目中所給出的數(shù)據(jù)簡(jiǎn)

21、 單的單的 驗(yàn)證一下驗(yàn)證一下)(3)飛機(jī)調(diào)整方向角的過(guò)程可在瞬間完成飛機(jī)調(diào)整方向角的過(guò)程可在瞬間完成,(不不 計(jì)調(diào)整方向所花費(fèi)的時(shí)間計(jì)調(diào)整方向所花費(fèi)的時(shí)間)。為解決該問(wèn)題，補(bǔ)充假設(shè)：為解決該問(wèn)題，補(bǔ)充假設(shè)：2021/6/1624變量、參數(shù)的符號(hào)假設(shè)變量、參數(shù)的符號(hào)假設(shè)（為了建模）（為了建模） 00,1 26)iixyii 第第 架架機(jī)機(jī)的的初初始始位位置置, (，, (， ，01 26)iii 第第 架架機(jī)機(jī)的的整整前前的的方方向向角角, , ( (， ，1 26)iii 第第 架架機(jī)機(jī)的的整整后后的的方方向向角角, , ( (， ， 在區(qū)域內(nèi)飛行在區(qū)域內(nèi)飛行iiTi 第第 架架 機(jī)機(jī)按按方方

22、向向角角飛飛時(shí)間（可以根據(jù)數(shù)據(jù)算出來(lái)）時(shí)間（可以根據(jù)數(shù)據(jù)算出來(lái)）2021/6/1625四種情況：四種情況：四個(gè)象限，易用四個(gè)象限，易用4個(gè)表達(dá)式表示個(gè)表達(dá)式表示說(shuō)明：說(shuō)明：用初等數(shù)學(xué)的知識(shí)即可完成，用初等數(shù)學(xué)的知識(shí)即可完成，思考：思考：在哪個(gè)時(shí)間段某兩架飛機(jī)可能相撞？在哪個(gè)時(shí)間段某兩架飛機(jī)可能相撞？?ijTTor otherelseIn fact, 我們只需考慮兩架飛機(jī)我們只需考慮兩架飛機(jī)同時(shí)同時(shí)在區(qū)域內(nèi)在區(qū)域內(nèi)飛行時(shí)的情況，也就是說(shuō)，飛行時(shí)的情況，也就是說(shuō)， min,ijT T才是同在區(qū)域內(nèi)的狀況。才是同在區(qū)域內(nèi)的狀況。記為記為ijT2021/6/1626 00002202,mincosco

23、ssinsinijijijijijt Tijijdxxvtyyvt 根據(jù)題目條件，需計(jì)算第根據(jù)題目條件，需計(jì)算第 架飛機(jī)之間架飛機(jī)之間的的最短距離最短距離, i j2021/6/1627為此，我們可以給出原問(wèn)題的模型如下：為此，我們可以給出原問(wèn)題的模型如下： 00612min,60, ,1,2,6,. .,1,2,6.6iiiijijiidi jijs ti 思考：思考：是否還有其他的表達(dá)形式？是否還有其他的表達(dá)形式？非線性非線性規(guī)劃模規(guī)劃模型型分別從目標(biāo)函數(shù)和約束條件角度思考分別從目標(biāo)函數(shù)和約束條件角度思考2021/6/1628首先思考一下目標(biāo)函數(shù)是否有其它的表達(dá)？首先思考一下目標(biāo)函數(shù)是否有

24、其它的表達(dá)？ 061miniii 同學(xué)們首先想到的可能是同學(xué)們首先想到的可能是Oh, Sorry!有正有負(fù)有正有負(fù)抵消抵消2021/6/1629061miniii 0621miniii 最小一最小一乘乘 法法最小二最小二乘乘 法法 因最小一乘法帶絕對(duì)值，不好計(jì)算，以上兩式，因最小一乘法帶絕對(duì)值，不好計(jì)算，以上兩式，比較而言，后者較好。比較而言，后者較好。為了避免抵消為了避免抵消or2021/6/1630有的隊(duì)員這樣考慮：有的隊(duì)員這樣考慮：016min maxiii 令為令為 ,轉(zhuǎn)化為二次規(guī)劃轉(zhuǎn)化為二次規(guī)劃用到經(jīng)驗(yàn)?zāi)Ｐ椭写_定參數(shù)的近似準(zhǔn)則用到經(jīng)驗(yàn)?zāi)Ｐ椭写_定參數(shù)的近似準(zhǔn)則:就所有飛機(jī)而言，就所有飛

25、機(jī)而言， 讓調(diào)整弧度最大的讓調(diào)整弧度最大的即即盡可能小，盡可能小，Chebshavf 準(zhǔn)則準(zhǔn)則2021/6/1631其次討論一下約束條件是否有其它表達(dá)？其次討論一下約束條件是否有其它表達(dá)？ 若考慮區(qū)域內(nèi)不發(fā)生碰撞（若時(shí)間允許，也若考慮區(qū)域內(nèi)不發(fā)生碰撞（若時(shí)間允許，也可以考慮出了區(qū)域的情況，另外建模）、錯(cuò)層可以考慮出了區(qū)域的情況，另外建模）、錯(cuò)層飛行（飛高或者飛低避免碰撞），進(jìn)行模型的飛行（飛高或者飛低避免碰撞），進(jìn)行模型的進(jìn)一步改進(jìn)，重點(diǎn)應(yīng)放在解決問(wèn)題的方法上。進(jìn)一步改進(jìn)，重點(diǎn)應(yīng)放在解決問(wèn)題的方法上。 如如 02,1,2,6,6,60, ,1,2,6,iiijijidi jij 2021/6/

26、1632 無(wú)論選擇哪一種表達(dá)，怎樣考慮約束條件，無(wú)論選擇哪一種表達(dá)，怎樣考慮約束條件，目標(biāo)函數(shù)都不可能是線性的。目標(biāo)函數(shù)都不可能是線性的。 現(xiàn)在看來(lái)，那年的題目建模只是在條件的現(xiàn)在看來(lái)，那年的題目建模只是在條件的考慮上和建模中目標(biāo)函數(shù)的表達(dá)方面較難一點(diǎn)?？紤]上和建模中目標(biāo)函數(shù)的表達(dá)方面較難一點(diǎn)。 是一個(gè)帶不等式約束的非線性規(guī)劃問(wèn)題。是一個(gè)帶不等式約束的非線性規(guī)劃問(wèn)題。 而且不可能轉(zhuǎn)化成線性的形式。而且不可能轉(zhuǎn)化成線性的形式。2021/6/1633非線性規(guī)劃模型按約束條件可分為以下三類(lèi)：非線性規(guī)劃模型按約束條件可分為以下三類(lèi)： 無(wú)約束非線性規(guī)劃模型：無(wú)約束非線性規(guī)劃模型： 等式約束非線性規(guī)劃模型

27、：等式約束非線性規(guī)劃模型：min ( )nf xxRmin ( ). . ( )0,1,2,jf xst h xjr 不等式約束非線性規(guī)劃模型：不等式約束非線性規(guī)劃模型：min ( ). . ( )0,1,2,if xst g xim2021/6/1634如如數(shù)據(jù)擬合的最小二乘問(wèn)題就是一個(gè)無(wú)約束極值問(wèn)數(shù)據(jù)擬合的最小二乘問(wèn)題就是一個(gè)無(wú)約束極值問(wèn)題。題。 其思想是：觀察點(diǎn)（實(shí)驗(yàn)數(shù)據(jù)點(diǎn)）到曲線的距其思想是：觀察點(diǎn)（實(shí)驗(yàn)數(shù)據(jù)點(diǎn)）到曲線的距離的平方之和最小離的平方之和最小 無(wú)約束非線性規(guī)劃模型：無(wú)約束非線性規(guī)劃模型：2021/6/1635理論上無(wú)約束極值問(wèn)題可化成求解理論上無(wú)約束極值問(wèn)題可化成求解 0g

28、rad fx 即解一個(gè)即解一個(gè) n 元方程組，且往往是非線性方程組。元方程組，且往往是非線性方程組。 而一般說(shuō)來(lái)，非線性方程組的求解并不比求無(wú)而一般說(shuō)來(lái)，非線性方程組的求解并不比求無(wú)約束極值容易。約束極值容易。2021/6/1636求解無(wú)約束極值問(wèn)題的基本方法：求解無(wú)約束極值問(wèn)題的基本方法：迭代法迭代法 從一個(gè)給定的初始可行點(diǎn)從一個(gè)給定的初始可行點(diǎn) 出發(fā)，依次出發(fā)，依次0 x產(chǎn)生一個(gè)可行點(diǎn)列產(chǎn)生一個(gè)可行點(diǎn)列12,kxxx的一個(gè)極小值點(diǎn)的一個(gè)極小值點(diǎn),恰好是恰好是使得某個(gè)使得某個(gè)kx fx基本思路：基本思路：或或 kx收斂于收斂于x , 稱具有這種性質(zhì)的算法稱具有這種性質(zhì)的算法是是收斂的收斂的.

29、2021/6/1637由由kx迭代到迭代到1kx 時(shí)時(shí),1,kkkkxxp 記記即即1,kkkkxxp kp其中向量其中向量為為搜索方向搜索方向, 實(shí)數(shù)實(shí)數(shù)k 稱為稱為步長(zhǎng)步長(zhǎng),確定以后確定以后,kkp kx由由可唯一地確定可唯一地確定1,kx 從從0 x出發(fā)就可確定點(diǎn)列出發(fā)就可確定點(diǎn)列 .kx2021/6/1638迭代的方法很多迭代的方法很多, 各種迭代法的區(qū)別在于選取各種迭代法的區(qū)別在于選取,kkp 的方式不同的方式不同, 而而kp尤為關(guān)鍵尤為關(guān)鍵.一般要求一般要求 kfx遞減遞減, 具有這種性質(zhì)的算法叫做具有這種性質(zhì)的算法叫做下降下降算法算法.2021/6/1639若已得若已得,kx下降

30、得最多下降得最多,并確定了并確定了kx的可行下降方向的可行下降方向,kp上選取步長(zhǎng)上選取步長(zhǎng)則在射線則在射線 0kkxp ,k 使使 ,kkkkfxpfx 且使且使 kfx 00minmin,kkkkkfxpfxp 即求即求求求k 的過(guò)程稱為的過(guò)程稱為一維搜索一維搜索.1. 下降算法下降算法2021/6/1640于是一維搜索歸結(jié)為求解一維無(wú)約束極值問(wèn)題于是一維搜索歸結(jié)為求解一維無(wú)約束極值問(wèn)題: min,xxR 其算法有其算法有Newton法、平分法、黃金分割法法、平分法、黃金分割法（0.618法）、分?jǐn)?shù)法（法）、分?jǐn)?shù)法（Fibonacci法）、拋法）、拋物線法（二次插值法）等，物線法（二次插值

31、法）等， 前兩種算法需計(jì)算前兩種算法需計(jì)算 x 的導(dǎo)數(shù)，的導(dǎo)數(shù)，后三種算法只需計(jì)算后三種算法只需計(jì)算 x 的函數(shù)值。的函數(shù)值。下面僅介紹下面僅介紹Newton法，對(duì)其他方法的了解可法，對(duì)其他方法的了解可參考有關(guān)書(shū)籍。參考有關(guān)書(shū)籍。2021/6/1641按按0,1,2,k 給定初始可行點(diǎn)給定初始可行點(diǎn) 和控制誤差和控制誤差 ，0 x0 迭代格式迭代格式 1kkkkxxxx 迭代，迭代，當(dāng)當(dāng)1kkxx 時(shí)，時(shí)， x 即求得即求得的最優(yōu)解的近似解的最優(yōu)解的近似解1,kxx 停止計(jì)算。停止計(jì)算。Newton 法介紹法介紹2021/6/1642 一個(gè)好的算法必須以較快的速度收斂到一個(gè)好的算法必須以較快的

32、速度收斂到最優(yōu)解。最優(yōu)解。 kx設(shè)算法產(chǎn)生的點(diǎn)列設(shè)算法產(chǎn)生的點(diǎn)列收斂于最優(yōu)解收斂于最優(yōu)解,x 1p 若存在若存在及及1lim,kpkkxxCxx 0,C 使使 kx則稱則稱為為 p 階收斂的。階收斂的。該算法也是該算法也是 p 階收斂的。階收斂的。2021/6/1643 稱為稱為線性收斂；線性收斂；1lim,kpkkxxCxx 1p 當(dāng)當(dāng)且且01C時(shí)，時(shí)， 稱為稱為超線性收斂；超線性收斂；12p當(dāng)當(dāng)時(shí)，時(shí)， 稱為稱為平方收斂；平方收斂；2p 當(dāng)當(dāng)時(shí)，時(shí)，2021/6/1644一個(gè)算法是否收斂，一個(gè)算法是否收斂，0 x往往與往往與的選取有關(guān)的選取有關(guān) 若當(dāng)若當(dāng)0 x充分接近充分接近x 時(shí)，時(shí)，由

33、算法產(chǎn)生的點(diǎn)列由算法產(chǎn)生的點(diǎn)列 kx才收斂于才收斂于,x 則稱該算法為具有局部收斂則稱該算法為具有局部收斂性的算法；性的算法； 若對(duì)若對(duì)0,xD則稱該算法為具有全局收斂性的算法。則稱該算法為具有全局收斂性的算法。由算法產(chǎn)生由算法產(chǎn)生 的點(diǎn)列的點(diǎn)列 kx均收斂均收斂,x 于于2021/6/1645 Newton法是平方收斂的，具有局部收斂法是平方收斂的，具有局部收斂性；拋物線法是超線性收斂的，具有全局收斂性；拋物線法是超線性收斂的，具有全局收斂性；平分法、黃金分割法、分?jǐn)?shù)法是線性收斂性；平分法、黃金分割法、分?jǐn)?shù)法是線性收斂的，具有全局收斂性。的，具有全局收斂性。常見(jiàn)一維搜索算法的收斂性常見(jiàn)一維搜

34、索算法的收斂性2021/6/1646當(dāng)當(dāng) x 具有多個(gè)極小值點(diǎn)時(shí)，具有多個(gè)極小值點(diǎn)時(shí)， 則算法求得則算法求得的往往是的往往是 x 的一個(gè)局部極小值點(diǎn)。的一個(gè)局部極小值點(diǎn)。此時(shí)可此時(shí)可改變改變0 x的取值，重新迭代求解。的取值，重新迭代求解。 若求得多個(gè)極小值點(diǎn)，則從中選擇一個(gè)若求得多個(gè)極小值點(diǎn)，則從中選擇一個(gè)較滿意的結(jié)果。較滿意的結(jié)果。 說(shuō)明：說(shuō)明：2021/6/1647 1847年年Cauchy提出了第一個(gè)無(wú)約束極值問(wèn)提出了第一個(gè)無(wú)約束極值問(wèn)題的算法題的算法梯度法或最速下降法：梯度法或最速下降法：2. 梯度法梯度法. 00)(0kX，令，允許誤差越接近最優(yōu)點(diǎn)越好步驟一：選定初始點(diǎn)).(),(

35、,kkkkXfPXfX選取搜索方向計(jì)算梯度優(yōu)點(diǎn)步驟二：假定已得非最.11返回繼續(xù)搜索令不滿足給定精度要求，如果kkXk).(min)( ,k0kkkk1PXfPXfPXXkkkkk，滿足：步驟三：選定搜索步長(zhǎng).1*1kkXXX搜索完成，近似最優(yōu)點(diǎn)滿足給定精度要求，則如果.)()()(.1111kkkkkkXXXfXfXfX或或斷準(zhǔn)則：檢驗(yàn)是否滿足收斂性判根據(jù)精度要求，要求的近似解是否是最優(yōu)點(diǎn)或是滿足步驟四：判斷2021/6/1648例題：應(yīng)用梯度法求解例題：應(yīng)用梯度法求解. 0:2 . 0)2 , 2(0kX，令，允許誤差步驟一：選定初始點(diǎn).100, 4)(),(kkkXfPXf選取搜索方向步

36、驟二：計(jì)算梯度.02. 0,)1002(25)42()().(min)( ,02200000kkkk1解得優(yōu)步長(zhǎng)第一點(diǎn)搜索計(jì)算：求最，滿足：步驟三：選定搜索步長(zhǎng)PXfPXfPXfPXXkkkk.02. 031.100)()(),0 ,92. 1 (.)()()(.0111111不滿足，繼續(xù)搜索且第一點(diǎn)搜索計(jì)算：或或斷準(zhǔn)則：檢驗(yàn)是否滿足收斂性判根據(jù)精度要求，要求的近似解是否是最優(yōu)點(diǎn)或是滿足步驟四：判斷XfXfXXXXfXfXfXkkkkkk.25)(min2221xxXf解：解：2021/6/1649 該算法具有全局收斂性，是線性收斂的，該算法具有全局收斂性，是線性收斂的，但有時(shí)是很慢的線性收斂

37、，這似乎與但有時(shí)是很慢的線性收斂，這似乎與“最速下最速下降降”矛盾。其實(shí)不然，最速下降方向函數(shù)在某矛盾。其實(shí)不然，最速下降方向函數(shù)在某點(diǎn)處的局部性質(zhì)，對(duì)局部來(lái)說(shuō)是最速下降方向，點(diǎn)處的局部性質(zhì)，對(duì)局部來(lái)說(shuō)是最速下降方向，對(duì)全局來(lái)說(shuō)卻不一定是最速下降方向，故梯度對(duì)全局來(lái)說(shuō)卻不一定是最速下降方向，故梯度法不是有效的實(shí)用算法。法不是有效的實(shí)用算法。 通過(guò)對(duì)它改進(jìn)或利用它與其他收斂快的算通過(guò)對(duì)它改進(jìn)或利用它與其他收斂快的算法相結(jié)合可得法相結(jié)合可得Newton法、法、Fletcher-Reeves共軛梯度法、變尺度法和共軛梯度法、變尺度法和Powell法法等有效算等有效算法。法。2021/6/1650 下

38、面僅介紹前兩者，對(duì)后兩者的了解可參下面僅介紹前兩者，對(duì)后兩者的了解可參閱有關(guān)書(shū)籍。閱有關(guān)書(shū)籍。 121,kkkkxxfxg 當(dāng)當(dāng)1kkxx 時(shí)，時(shí)，則則 。1kxx 其中其中 1112121222122,nnnnnnx xkx xkx xkx xkx xkx xkkx xkx xkx xkfxfxfxfxfxfxfxfxfxfx 稱為稱為 fx在在 處的處的Hesse矩陣。矩陣。kxNewton法法2021/6/1651 該算法是平方收斂的，具有局部收斂性。該算法是平方收斂的，具有局部收斂性。 對(duì)對(duì)Newton法進(jìn)行改進(jìn)，可得具有超線性法進(jìn)行改進(jìn)，可得具有超線性收斂的且具有全局收斂性的收斂的且

39、具有全局收斂性的阻尼阻尼Newton法法或或修正修正Newton法法： 121102min,kkkkkkkkfxfxgfxgfxfx 當(dāng)當(dāng)1kkxx 時(shí)，時(shí)，有有 。1kxx 2021/6/1652 Fletcher-Reeves共軛梯度法共軛梯度法當(dāng)當(dāng)1kkxx 時(shí)，時(shí)，有有 。1kxx 該算法的收斂速度介于梯度法和該算法的收斂速度介于梯度法和Newton法法其中其中00,Pg 之間，既克服了前者的慢收斂性，又避免了之間，既克服了前者的慢收斂性，又避免了111TkkkkkTkkg gPgPgg 10min,kkkkkkfxfxpfxp 后者計(jì)算量大和僅具有局部收斂性的缺陷。后者計(jì)算量大和僅具

40、有局部收斂性的缺陷。2021/6/1653（2 2）只有等式約束的非線性規(guī)劃問(wèn)題通常可用只有等式約束的非線性規(guī)劃問(wèn)題通常可用消元法、拉格朗日乘子法，將其化為無(wú)約束問(wèn)消元法、拉格朗日乘子法，將其化為無(wú)約束問(wèn)題求解題求解. .（3 3）具有不等式約束的非線性規(guī)劃問(wèn)題解起來(lái)具有不等式約束的非線性規(guī)劃問(wèn)題解起來(lái)很復(fù)雜，求解這一類(lèi)問(wèn)題，通常將不等式化很復(fù)雜，求解這一類(lèi)問(wèn)題，通常將不等式化為等式約束，再將約束問(wèn)題化為無(wú)約束問(wèn)題，為等式約束，再將約束問(wèn)題化為無(wú)約束問(wèn)題，用線性逼近的方法將非線性規(guī)劃問(wèn)題化為線用線性逼近的方法將非線性規(guī)劃問(wèn)題化為線性規(guī)劃問(wèn)題性規(guī)劃問(wèn)題. 下面先介紹一個(gè)簡(jiǎn)單的非線性規(guī)劃問(wèn)題下面先

41、介紹一個(gè)簡(jiǎn)單的非線性規(guī)劃問(wèn)題的例子，其中的一些約束條件是等式，這類(lèi)非的例子，其中的一些約束條件是等式，這類(lèi)非線性規(guī)劃問(wèn)題可用拉格朗日方法求解線性規(guī)劃問(wèn)題可用拉格朗日方法求解.2021/6/16542021/6/16552021/6/16562021/6/16572021/6/1658Kuhn-Tucker定理：對(duì)于不等式約束非線性最優(yōu)化 極值問(wèn)題若 ， 均可微，則其極值點(diǎn)存在的必要條件是：注：更詳細(xì)的結(jié)論參閱有關(guān)書(shū)籍注：更詳細(xì)的結(jié)論參閱有關(guān)書(shū)籍.()fX()igX 不等式約束非線性規(guī)劃模型不等式約束非線性規(guī)劃模型2021/6/1659注：1、庫(kù)-圖條件是判別有約束極值點(diǎn)的必要條件，并非充分條件

42、。但是對(duì)于凸函數(shù)、凸集問(wèn)題也是判別其極值點(diǎn)的充分條件。固此時(shí)的局部最優(yōu)解也必為全局的最優(yōu)解。2、庫(kù)-圖乘子與拉格朗日乘子類(lèi)似。但拉格朗日乘子的符號(hào)不是確定的，可正可負(fù)；而庫(kù)-恩乘子的符號(hào)是確定的，其規(guī)律為： a、求 ， 時(shí)，則 b、求 ， 時(shí)，則 c、求 ， 時(shí)，則 d、求 ， 時(shí)，則m in ( )f Xm in ( )f X( ) 0ig X ( ) 0ig X ()0ig X ( ) 0ig X 0i0i0i0ima x ( )f Xma x ( )f X2021/6/1660罰函數(shù)法罰函數(shù)法:約束最優(yōu)化問(wèn)題化為無(wú)約束最優(yōu)化問(wèn)題的一種求解方法約束最優(yōu)化問(wèn)題化為無(wú)約束最優(yōu)化問(wèn)題的一種求解方

43、法2021/6/16612021/6/1662罰函數(shù)法的步驟：（等式約束最優(yōu)化問(wèn)題罰函數(shù)法）罰函數(shù)法的步驟：（等式約束最優(yōu)化問(wèn)題罰函數(shù)法）2021/6/16632021/6/16642021/6/16652021/6/1666罰函數(shù)法步驟：（不等式約束最優(yōu)化問(wèn)題罰函數(shù)法）罰函數(shù)法步驟：（不等式約束最優(yōu)化問(wèn)題罰函數(shù)法）2021/6/16672021/6/16682021/6/1669注：罰函數(shù)法更多的詳細(xì)改進(jìn)工作，需參閱相關(guān)書(shū)籍注：罰函數(shù)法更多的詳細(xì)改進(jìn)工作，需參閱相關(guān)書(shū)籍2021/6/1670 在許多實(shí)際問(wèn)題中，衡量一個(gè)方案的好壞標(biāo)準(zhǔn)往往不止一個(gè)，例如設(shè)計(jì)一個(gè)導(dǎo)彈，既要射程最遠(yuǎn)，又要燃料最省，

44、還要精度最高. 這一類(lèi)問(wèn)題統(tǒng)稱為多目標(biāo)最優(yōu)化問(wèn)題或多目標(biāo)規(guī)劃問(wèn)題. 我們先來(lái)看一個(gè)投資計(jì)劃的例子.2021/6/1671例：例： 投資問(wèn)題投資問(wèn)題 某公司在一段時(shí)間內(nèi)有某公司在一段時(shí)間內(nèi)有a(億元億元)的資金可用于建廠投資。的資金可用于建廠投資。若可供選擇的項(xiàng)目記為若可供選擇的項(xiàng)目記為1,2,m。而且一旦對(duì)第。而且一旦對(duì)第i個(gè)項(xiàng)目投個(gè)項(xiàng)目投資就用去資就用去ai億元；而這段時(shí)間內(nèi)可得收益億元；而這段時(shí)間內(nèi)可得收益ci億元。問(wèn)如何億元。問(wèn)如何確定最佳的投資方案？確定最佳的投資方案？1i0iix對(duì)第 個(gè)項(xiàng)目投資不對(duì)第 個(gè)項(xiàng)目投資 最佳投資方案：投資最少，收益最大！最佳投資方案：投資最少，收益最大！2021/6/1672投資最少：投資最少：1121min( ,.,)mniiif x xxa x2121max( ,.,)mniiifx xxc x約束條件為：約束條件為：1(1)0,1,2,.miiiiia xaxxim收益最大：收益最大：2021/6/16732021/6/16742021/6/16752021/6/16762021/6/16772021/6/16782021/6/16792021/6/16802021/6/16812021/6/16822021/6/16832021/6/16842021/6/16852021