代數(shù)方程與最優(yōu)化問(wèn)題的計(jì)算機(jī)求解

第6章

代數(shù)方程與最優(yōu)化問(wèn)題的計(jì)算機(jī)求解高等應(yīng)用數(shù)學(xué)問(wèn)題的MATLAB求解清華大學(xué)出版社2008CAI課件開(kāi)發(fā)：薛定宇、劉瑩瑩、董雯彬2/1/2023第6章代數(shù)方程與最優(yōu)

化問(wèn)題的計(jì)算機(jī)求解代數(shù)方程的求解無(wú)約束最優(yōu)化問(wèn)題求解有約束最優(yōu)化問(wèn)題的計(jì)算機(jī)求解混合整數(shù)規(guī)劃問(wèn)題的計(jì)算機(jī)求解線性矩陣不等式問(wèn)題求解多目標(biāo)優(yōu)化問(wèn)題求解動(dòng)態(tài)規(guī)劃及其在路徑規(guī)劃中的應(yīng)用2/1/20236.1代數(shù)方程的求解代數(shù)方程的圖解法多項(xiàng)式型方程的準(zhǔn)解析解法一般非線性方程數(shù)值解非線性矩陣方程求解2/1/20236.1.1代數(shù)方程的圖解法一元方程的圖解法二元方程的圖解法2/1/2023

一元方程的圖解法用ezplot()函數(shù)可以繪制出給定的隱函數(shù)

曲線，所以可以用圖解法從給出的曲線和

線的交點(diǎn)上讀出所有的實(shí)數(shù)解。2/1/2023例6.1用圖解法求解方程：MATLAB求解命令證明：2/1/2023

二元方程的圖解法使用ezplot()函數(shù)將所有的方程都畫(huà)出來(lái)，得出曲線后就可以通過(guò)讀取交點(diǎn)坐標(biāo)的方式得出聯(lián)立方程的根2/1/2023例6.2用圖解法求解聯(lián)立方程：畫(huà)第一個(gè)函數(shù)：畫(huà)第二個(gè)函數(shù)：2/1/20236.1.2多項(xiàng)式型方程的準(zhǔn)解析解法特殊的高階方程如多項(xiàng)式型方程，可以被求解出Abel-Ruffini定理證明5階以上的多項(xiàng)式型方程沒(méi)有解析解一般的數(shù)值算法得出的解不精確得出高精度解的方法存在很多方程可以轉(zhuǎn)換成多項(xiàng)式方程2/1/2023例6.3試用圖解方法求解二元方程MATLAB求解命令：2/1/2023求解多項(xiàng)式型方程的函數(shù)調(diào)用格式最簡(jiǎn)調(diào)用方式直接得出根指定變量2/1/2023例6.4使用solve()函數(shù)求解MATLAB求解命令：證明：2/1/2023例6.5試求解MATLAB求解命令：證明：2/1/2023最后一個(gè)式子改寫(xiě)成MATLAB求解命令：2/1/2023例6.6試求解MATLAB求解命令：2/1/2023證明：2/1/2023例6.7試求解帶有參數(shù)的方程MATLAB求解命令：2/1/20236.1.3一般非線性方程數(shù)值解求出已知多元方程的一個(gè)實(shí)數(shù)根的函數(shù)調(diào)用格式最簡(jiǎn)求解語(yǔ)句一般求解語(yǔ)句2/1/2023選擇方法和修改控制精度的函數(shù)調(diào)用格式獲得默認(rèn)的常用變量設(shè)置控制參數(shù)或2/1/2023求解數(shù)值代數(shù)方程組的步驟設(shè)置變量，使等式變成如下所示按如下方式描述等式M-函數(shù)匿名函數(shù)Inline函數(shù)，不推薦使用求解方程組檢驗(yàn)階的正確性2/1/2023例6.8Lambert函數(shù)，是變量，

是方程的解，對(duì)不同的，求解

然后繪制

求解策略和過(guò)程使用for循環(huán)使用匿名函數(shù)描述生成w向量繪制函數(shù)曲線MATLAB求解語(yǔ)句：2/1/2023MATLAB表述直接求解，使用lambertw函數(shù)2/1/2023例6.9數(shù)值方法求解選擇變量把原始常微分方程組(ODEs)變?yōu)樽兂删仃囆问?/1/2023描述方程的方法M-函數(shù)匿名函數(shù)Inline函數(shù)2/1/2023當(dāng)初值選為當(dāng)使用另一個(gè)搜索初始點(diǎn)注意：選擇不同的初值可以得出不同的結(jié)果2/1/2023例6.10數(shù)值方法解使用solve()函數(shù)：使用圖解法求初始值：2/1/2023重新設(shè)置相關(guān)精度的控制變量所期望的精度可能無(wú)法達(dá)到然而，在算精度制下的最好結(jié)果可以得到2/1/20236.1.4非線性矩陣方程求解Riccati

方程（第4章）更多的非線性矩陣方程，例如，廣義Riccati方程類Riccati方程還有很多很多的矩陣方程2/1/2023函數(shù)fsolve()只能求解出，而不是，其中，是向量不是矩陣將矩陣方程轉(zhuǎn)換成向量方程向量轉(zhuǎn)換成矩陣

數(shù)學(xué)表述

MATLAB表述矩陣轉(zhuǎn)換成向量數(shù)學(xué)表述MATLAB表述Riccati方程求解2/1/2023以向量的形式描述Riccati方程的殘差求解Riccati方程的新函數(shù)2/1/2023例6.11求解下列Riccati方程組：

其中2/1/2023are()

函數(shù)可能會(huì)得出一個(gè)解重新使用MATLAB命令：另一個(gè)解：2/1/2023例6.12給定其中求出并檢驗(yàn)全部的根2/1/2023對(duì)于類Riccati方程另一個(gè)M-函數(shù)另一個(gè)矩陣方程求解函數(shù)2/1/2023重新使用MATLAB命令注意：有些解可能很難得到，需要反復(fù)調(diào)用多次上述函數(shù)2/1/2023已通過(guò)檢驗(yàn)的可能解

2/1/20236.2無(wú)約束最優(yōu)化問(wèn)題求解解析解法和圖解法基于MATLAB的數(shù)值解法全局最優(yōu)解與局部最優(yōu)解利用梯度求解最優(yōu)化問(wèn)題帶有變量邊界約束的最優(yōu)化問(wèn)題求解2/1/2023無(wú)約束最小化問(wèn)題的數(shù)學(xué)描述目標(biāo)函數(shù)是一個(gè)標(biāo)量函數(shù)向量決定變量，或優(yōu)化變量物理意義：求取一組

向量，使得最優(yōu)化目標(biāo)函數(shù)

為最小最大化問(wèn)題數(shù)學(xué)描述2/1/20236.2.1解析解法和圖解法無(wú)約束最優(yōu)化問(wèn)題的必要條件：其中，是最優(yōu)點(diǎn)方程的求解可能會(huì)更難，有時(shí)可能需要二階導(dǎo)數(shù)運(yùn)算2/1/2023例6.13研究下式的最優(yōu)性繪制函數(shù)的一階導(dǎo)數(shù)2/1/2023求一階導(dǎo)數(shù)為零的點(diǎn)，并驗(yàn)證二階導(dǎo)數(shù)為正2/1/20236.2.2基于MATLAB的數(shù)值解法得出數(shù)值解的函數(shù)調(diào)用格式最簡(jiǎn)求解語(yǔ)句或一般求解格式或2/1/2023描述目標(biāo)函數(shù)M-函數(shù)匿名函數(shù)Inline函數(shù)（不推薦使用）在匿名函數(shù)或inline函數(shù)中無(wú)法使用中間變量2/1/2023例6.14給定

，求其最小值

使用函數(shù)fminsearch()：使用函數(shù)fminunc()：2/1/2023繪制出搜索過(guò)程中間點(diǎn)的軌線：2/1/2023結(jié)果：2/1/20236.2.3全局最優(yōu)解與局部最優(yōu)解最小值存在的必要條件是使用搜索方法，從初始值出發(fā)，可能找到唯一的一個(gè)這樣的點(diǎn)，它是全局最小值2/1/2023例6.15給定觀察不同的初值得出的最小值構(gòu)造目標(biāo)函數(shù)初值是2/1/2023初值是在

內(nèi)的曲線：在

內(nèi)的曲線2/1/20236.2.4利用梯度求解最優(yōu)化問(wèn)題有時(shí)，僅利用目標(biāo)函數(shù)提供的信息，很難得到最優(yōu)解。這是由于求解最優(yōu)化問(wèn)題收斂速度一般較慢，尤其是變量較多的最優(yōu)化問(wèn)題可以利用梯度信息解決上述問(wèn)題2/1/2023例6.16求Rosenbrock

函數(shù)的無(wú)約束最優(yōu)化問(wèn)題繪制三維等高線圖：2/1/2023無(wú)梯度信息求梯度矩陣：2/1/2023編寫(xiě)目標(biāo)函數(shù)：求解最優(yōu)化問(wèn)題2/1/20236.2.5帶有變量邊界約

束的最優(yōu)化問(wèn)題求解帶有變量邊界約束的最優(yōu)化問(wèn)題的數(shù)學(xué)描述

其中，符號(hào)s.t.表示subjecttoJohnD'Errico,woodchips@fminsearchbnd()函數(shù)在隨書(shū)光盤(pán)中給出2/1/2023帶有變量邊界約束的最優(yōu)化問(wèn)題求解的語(yǔ)句調(diào)用格式最簡(jiǎn)求解語(yǔ)句

一般求解格式2/1/2023例6.17求解Rosenbrock問(wèn)題其中，和

MATLAB求解語(yǔ)句2/1/20236.3有約束最優(yōu)化

問(wèn)題的計(jì)算機(jī)求解約束條件與可行解區(qū)域線性規(guī)劃問(wèn)題的計(jì)算機(jī)求解二次型規(guī)劃的求解一般非線性規(guī)劃問(wèn)題的求解2/1/20236.3.1約束條件與可行解區(qū)域有約束非線性最優(yōu)化問(wèn)題的一般描述為其中，所有的

滿足約束條件該范圍稱為可行解區(qū)域2/1/2023例6.18圖解方法求解：目標(biāo)函數(shù)描述可行解區(qū)域描述2/1/2023可行區(qū)域圖解說(shuō)明2/1/20236.3.2線性規(guī)劃問(wèn)題的計(jì)算機(jī)求解線性規(guī)劃(LP)問(wèn)題的一般數(shù)學(xué)描述為所有都是線性的注意，約束的標(biāo)準(zhǔn)形式2/1/2023求解LP問(wèn)題的函數(shù)調(diào)用格式2/1/2023例6.19試求解下面的線性規(guī)劃問(wèn)題2/1/2023MATLAB求解語(yǔ)句：2/1/2023例6.20求解下列LP問(wèn)題：先將原問(wèn)題轉(zhuǎn)換為最小值問(wèn)題2/1/2023MATLAB求解命令2/1/2023例6.21是求解下列LP問(wèn)題雙下標(biāo)描述2/1/2023將原問(wèn)題轉(zhuǎn)換成單下標(biāo)自變量原問(wèn)題改寫(xiě)成2/1/2023MATLAB求解命令2/1/20236.3.3二次型規(guī)劃的求解一般二次型規(guī)劃問(wèn)題的數(shù)學(xué)表示為首先建立矩陣表述2/1/2023求解二次型規(guī)劃問(wèn)題的函數(shù)調(diào)用格式2/1/2023例6.22試求解下面的四元二次型規(guī)劃問(wèn)題首先求出相關(guān)矩陣形式2/1/2023展開(kāi)目標(biāo)函數(shù)得寫(xiě)成矩陣形式2/1/2023MATLAB求解語(yǔ)句其中，忽略了常數(shù)302/1/20236.3.4一般非線性規(guī)劃問(wèn)題的求解一般非線性規(guī)劃問(wèn)題其中，物理解釋：在給出的約束條件下，找出向量，使目標(biāo)函數(shù)達(dá)到最小值2/1/2023簡(jiǎn)化描述求解出非線性規(guī)劃問(wèn)題2/1/2023例6.23試求解下面非線性規(guī)劃問(wèn)題為目標(biāo)函數(shù)和約束函數(shù)編輯M-函數(shù)，后者返回兩個(gè)變量2/1/2023編輯非線性約束函數(shù)編輯目標(biāo)函數(shù)2/1/2023使用函數(shù)fmincon()求解2/1/2023簡(jiǎn)化非線性約束條件函數(shù)：求出結(jié)果：2/1/2023例6.24利用梯度信息求解如下問(wèn)題，并比較結(jié)果

2/1/2023推導(dǎo)Jacobian矩陣編寫(xiě)目標(biāo)函數(shù)2/1/2023使用函數(shù)fmincon()得出結(jié)果2/1/20236.4混合整數(shù)規(guī)劃

問(wèn)題的計(jì)算機(jī)求解整數(shù)線性規(guī)劃問(wèn)題的求解一般非線性整數(shù)規(guī)劃問(wèn)題與求解0-1規(guī)劃問(wèn)題求解2/1/20236.4.1整數(shù)線性規(guī)劃問(wèn)題的求解整數(shù)線性規(guī)劃的一般數(shù)學(xué)描述其中，

為變量

的子集2/1/2023求解整數(shù)線性規(guī)劃問(wèn)題的函數(shù)調(diào)用格式該免費(fèi)工具箱，可以由MathWorks公司網(wǎng)站下載，也可以由本書(shū)光盤(pán)得出當(dāng)前版本的ipslv_mex()函數(shù)不能用于低于MATLAB7.*的版本2/1/2023求解下列線性整數(shù)規(guī)劃問(wèn)題，其中，各個(gè)變量全為整數(shù)例6.252/1/2023MATLAB求解命令2/1/2023采用窮舉算法，假定

的各個(gè)元素均為202/1/2023得出次最優(yōu)解混合整數(shù)規(guī)劃問(wèn)題，要求

為整數(shù)，其他兩個(gè)變量為任意數(shù)2/1/20236.4.2一般非線性整

數(shù)規(guī)劃問(wèn)題與求解分枝定界算法是一種最常用的處理非線性整數(shù)規(guī)劃或混合規(guī)劃問(wèn)題的算法免費(fèi)工具箱由

Mr.Keort

Kuipers提供

koertkuipers@該工具箱也附在由隨書(shū)光盤(pán)上在MATLABR2008a中，薛定宇老師對(duì)其進(jìn)行了簡(jiǎn)單的修改2/1/2023函數(shù)調(diào)用格式向量表示變量必須是整數(shù)，當(dāng)表示變量可以是實(shí)數(shù)fun變量要是一個(gè)被引用的文件名，而不能是@...的形式如果err返回空，則求解成功2/1/2023補(bǔ)丁語(yǔ)句調(diào)用前調(diào)用后，截?cái)喽嘤嗟臄?shù)字2/1/2023例6.26假定,使用函數(shù)bnb20()求解線性整數(shù)規(guī)劃問(wèn)題(ILP)編輯目標(biāo)函數(shù)（不要編輯非匿名函數(shù)）2/1/2023求解出ILPerrmsg是空，求解成功2/1/2023如果要求

為整數(shù)，其他兩個(gè)變量為任意數(shù)，則2/1/2023窮舉法小結(jié)優(yōu)點(diǎn)保證得出全局最優(yōu)值除了最優(yōu)值，還可以得出次最優(yōu)值對(duì)于小規(guī)模問(wèn)題，求解簡(jiǎn)便缺點(diǎn)帶來(lái)很重的計(jì)算負(fù)擔(dān)和極大的內(nèi)存使用不可能求解大型甚至中型問(wèn)題2/1/2023例6.27求出修改的Rosenbrock問(wèn)題其中，并且是整數(shù)目標(biāo)函數(shù)2/1/2023MATLAB求解語(yǔ)句：2/1/2023選擇區(qū)間給定區(qū)間，使用窮舉法2/1/20236.4.30-1規(guī)劃問(wèn)題求解0-1線性規(guī)劃問(wèn)題MATLAB求解函數(shù)0-1非線性規(guī)劃問(wèn)題，使用函數(shù)bnb20()將下界定義一個(gè)全為0的向量將上界定義一個(gè)全為1的向量直接使用函數(shù)bnb20()2/1/2023例6.28求解0-1線性規(guī)劃問(wèn)題MATLAB求解語(yǔ)句：2/1/2023枚舉方法2/1/2023例6.29運(yùn)用函數(shù)bnb20()求解下列問(wèn)題構(gòu)造目標(biāo)函數(shù)：2/1/2023MATLAB求解語(yǔ)句：2/1/20236.5線性矩陣不等式問(wèn)題求解線性矩陣不等式的一般描述Lyapunov不等式線性矩陣不等式問(wèn)題分類線性矩陣不等式問(wèn)題的MATLAB求解基于YALMIP工具箱的最優(yōu)化求解方法2/1/20236.5.1線性矩陣不等式的一般描述線性矩陣不等式(LMI)的數(shù)學(xué)描述其中，為多項(xiàng)式系數(shù)向量，又稱為決策向量，為實(shí)對(duì)稱矩陣或復(fù)Hermit矩陣2/1/2023如果LMI矩陣是負(fù)定矩陣，那么解是凸集其中，多個(gè)線性矩陣不等式可以合并成單一的線性矩陣不等式2/1/20236.5.2Lyapunov不等式Lyapunov不等式的數(shù)學(xué)描述

其中，

是對(duì)稱矩陣2/1/2023構(gòu)造MATLAB函數(shù)求取2/1/2023接上頁(yè)函數(shù)調(diào)用格式：2/1/2023例6.30給定試求出其線性矩陣不等式表示。對(duì)于矩陣，寫(xiě)出相應(yīng)的線性矩陣不等式MATLAB求解語(yǔ)句：2/1/2023對(duì)于X矩陣線性矩陣不等式形式的數(shù)學(xué)描述2/1/2023對(duì)于的符號(hào)矩陣結(jié)果：2/1/2023給定分塊矩陣其中，

是方陣，那么，下述三種況等價(jià)Schur補(bǔ)性質(zhì)2/1/2023數(shù)學(xué)描述其中，原非線性不等式可以等價(jià)地變換成下述線性矩陣不等式代數(shù)Riccati不等式2/1/20236.5.3線性矩陣不等式問(wèn)題分類可行解問(wèn)題可行解問(wèn)題實(shí)際上就是求下述的解其中要找到最小值如果找到的

，則得出的解是原問(wèn)題的可行解，否則會(huì)提示無(wú)法找到可行解。2/1/2023線性目標(biāo)函數(shù)最優(yōu)化問(wèn)題給定這樣的問(wèn)題可以用普通的線性規(guī)劃方法求解2/1/2023廣義特征值最優(yōu)化問(wèn)題廣義特征值問(wèn)題可以視為線性矩陣不等式問(wèn)題的最一般的問(wèn)題.表達(dá)式由該式演化可以得到更一般的不等式其中，是矩陣的廣義特征值歸納出下面的最優(yōu)化問(wèn)題2/1/20236.5.4線性矩陣不等式

問(wèn)題的MATLAB求解用MATLAB描述線性矩陣不等式創(chuàng)建LMI模型定義需要求解的變量其中，是未知矩陣類型的標(biāo)記2/1/2023描述分塊形式給出線性矩陣不等式

其中通常，該項(xiàng)是APB如果,那么k=-k如果flag==‘s’,該項(xiàng)是如果該項(xiàng)是常數(shù)，那么P=0，并且忽略B完成LMI模型描述2/1/2023求解LMI問(wèn)題可行解問(wèn)題線性目標(biāo)函數(shù)問(wèn)題廣義特征值問(wèn)題2/1/2023例6.31給定對(duì)于Riccati不等式試求出該不等式的一個(gè)正定可行解2/1/2023MATLAB求解語(yǔ)句：2/1/20236.5.5基于YALMIP工

具箱的最優(yōu)化求解方法YALMIP(yetanotherLMIpackage)由瑞典Link?ping

大學(xué)電子工程專業(yè)的JohanL?fberg博士開(kāi)發(fā),

johanl@isy.liu.se現(xiàn)在，它以成為最優(yōu)化問(wèn)題建模和求解的一種簡(jiǎn)便求解方法接近數(shù)學(xué)形式本書(shū)的隨書(shū)光盤(pán)附帶最新的版本2/1/2023決策變量的聲明對(duì)稱矩陣長(zhǎng)方形矩陣整數(shù)變量二項(xiàng)形式其它形式，例如Hankel矩陣，hankel()2/1/2023約束可以通過(guò)[]來(lái)聲明最優(yōu)化問(wèn)題求解求解可行解問(wèn)題求解目標(biāo)函數(shù)的最優(yōu)化問(wèn)題2/1/2023允許設(shè)定選項(xiàng)，如算法選擇提取得出的解矩陣2/1/2023例6.32給定使用YALMIP工具箱求解Riccati不等式2/1/2023MATLAB求解命令比使用魯棒控制工具箱(RCT)更方便2/1/2023例6.33求解線性規(guī)劃問(wèn)題MATLAB求解語(yǔ)句2/1/2023假設(shè)決策變量是整數(shù)2/1/2023例6.34對(duì)于線性系統(tǒng)其中2/1/2023采用LMI方法也可以求解系統(tǒng)的范數(shù)，其數(shù)學(xué)描述為

求解線性系統(tǒng)模型的范數(shù)2/1/2023MATLAB求解命令：2/1/20236.6多目標(biāo)優(yōu)化問(wèn)題求解多目標(biāo)優(yōu)化模型無(wú)約束多目標(biāo)函數(shù)的最小二乘求解多目標(biāo)問(wèn)題轉(zhuǎn)換為單目標(biāo)問(wèn)題求解多目標(biāo)優(yōu)化問(wèn)題的Pareto解集極小極大問(wèn)題求解目標(biāo)規(guī)劃問(wèn)題求解2/1/20236.6.1多目標(biāo)優(yōu)化模型多目標(biāo)最優(yōu)化問(wèn)題的一般表示為其中，2/1/2023例6.35

三種糖果，單價(jià)每公斤4，2.8和2.4元，買(mǎi)糖果不超過(guò)20元，總量不得少于6公斤，

和

不得少于3公斤，設(shè)計(jì)方案設(shè)

購(gòu)買(mǎi)量為

公斤，則2/1/20236.6.2無(wú)約束多目標(biāo)

函數(shù)的最小二乘求解設(shè)目標(biāo)函數(shù)將其轉(zhuǎn)換成單目標(biāo)問(wèn)題MATLAB函數(shù)調(diào)用格式2/1/2023例6.36求解下面無(wú)約束非線性多目標(biāo)規(guī)劃問(wèn)題的最小二乘解2/1/2023MATLAB求解語(yǔ)句使用函數(shù)fmincon()2/1/20236.6.3多目標(biāo)問(wèn)題轉(zhuǎn)

換為單目標(biāo)問(wèn)題求解線性加權(quán)變換及求解線性規(guī)劃問(wèn)題的最佳妥協(xié)解線性規(guī)劃問(wèn)題的最小二乘解2/1/2023

線性加權(quán)變換及求解單目標(biāo)優(yōu)化算法不能直接由于求解多目標(biāo)優(yōu)化問(wèn)題，需要將其變換成單目標(biāo)優(yōu)化問(wèn)題線性加權(quán)變換的數(shù)學(xué)描述其中，且2/1/2023例6.37重新考慮例6.35，求解如下最優(yōu)化問(wèn)題2/1/2023不同加權(quán)系數(shù)下的方案2/1/2023不同加權(quán)系數(shù)下的最優(yōu)方案2/1/2023

線性規(guī)劃

問(wèn)題的最佳妥協(xié)解特殊的線性規(guī)劃數(shù)學(xué)描述目標(biāo)函數(shù)不是一個(gè)向量，而是一個(gè)矩陣每一個(gè)目標(biāo)函數(shù)2/1/2023最佳妥協(xié)解的求解步驟如下單獨(dú)求解每個(gè)單目標(biāo)函數(shù)的最優(yōu)化問(wèn)題，得出最優(yōu)解通過(guò)規(guī)范化構(gòu)造單獨(dú)的目標(biāo)函數(shù)最佳妥協(xié)解變換成單目標(biāo)線性規(guī)劃2/1/2023最佳妥協(xié)解（最大值）的求解程序2/1/2023例6.38重新考慮例6.35，求解如下最優(yōu)化問(wèn)題2/1/2023MATLAB求解語(yǔ)句：2/1/2023例6.39求解如下最優(yōu)化問(wèn)題2/1/2023MATLAB求解語(yǔ)句：2/1/2023

線性規(guī)劃

問(wèn)題的最小二乘解多目標(biāo)線性規(guī)劃問(wèn)題的最小二乘表示則最小二乘解可以由函數(shù)直接得出2/1/2023例6.40給定如下最優(yōu)化問(wèn)題，試求其最小二乘解2/1/2023MATLAB求解語(yǔ)句：2/1/20236.6.4多目標(biāo)優(yōu)化

問(wèn)題的Pareto解集對(duì)于雙目標(biāo)函數(shù)的問(wèn)題，將可行解的離散點(diǎn)在二維平面上顯示出來(lái)從得出的可行解離散點(diǎn)提取出區(qū)域左下角的一條曲線，這個(gè)曲線上的點(diǎn)都是原問(wèn)題的解，稱為Pareto解集2/1/2023YiCao

在Gianluca

Dorini

貢獻(xiàn)的Pareto解集提取程序的基礎(chǔ)上，開(kāi)發(fā)了改進(jìn)的快速提取程序函數(shù)調(diào)用格式其中，

為可行解、離散點(diǎn)構(gòu)成的列向量，向量為標(biāo)志向量，指示可行解離散點(diǎn)是否為Pareto解集中的點(diǎn)2/1/2023例6.41采用上述的離散點(diǎn)分析方法重新研究下述的多目標(biāo)優(yōu)化問(wèn)題2/1/2023對(duì)原始問(wèn)題中花費(fèi)的錢(qián)數(shù)取一系列離散點(diǎn)原始問(wèn)題可以改寫(xiě)成單目標(biāo)的線性規(guī)劃問(wèn)題2/1/2023MATLAB求解語(yǔ)句：2/1/2023例6.42重新考慮例6.35，試提取其Pareto解集2/1/2023MATLAB求解語(yǔ)句：2/1/20236.6.5極小極大問(wèn)題求解極小極大問(wèn)題的數(shù)學(xué)描述極小極大問(wèn)題是在最不利的條件下尋找最有利決策方案的一種方法2/1/2023直接求解極小極大問(wèn)題的函數(shù)調(diào)用格式其中，目標(biāo)函數(shù)為向量形式描述，用匿名函數(shù)、inline()函數(shù)和M-函數(shù)均可以表示新目標(biāo)函數(shù)2/1/2023例6.43試求解下面的極小極大問(wèn)題2/1/2023選擇隨機(jī)數(shù)為初值2/1/2023有了fminimax()函數(shù)，還可以求解相關(guān)的變形問(wèn)題極小極小問(wèn)題極小極大問(wèn)題2/1/20236.6.6目標(biāo)規(guī)劃問(wèn)題求解最優(yōu)化問(wèn)題求解過(guò)程中，發(fā)現(xiàn)找不到可行解時(shí)，要放松約束條件。如，不等式約束條件

改寫(xiě)成將偏差對(duì)

引入目標(biāo)函數(shù)使得嚴(yán)格的不等式約束盡可能小地被突破，相應(yīng)的最優(yōu)化問(wèn)題稱為目標(biāo)規(guī)劃問(wèn)題。2/1/2023數(shù)學(xué)描述形式其中，

為原始的多目標(biāo)向量，

為各個(gè)目標(biāo)函數(shù)的加權(quán)系數(shù)，

為用戶人為引入的目標(biāo)2/1/2023MATLAB函數(shù)調(diào)用格式2/1/2023例6.44試用目標(biāo)規(guī)劃方法求解下式2/1/2023兩個(gè)目標(biāo)函數(shù)可以接受的目標(biāo)分別是20和6，將其權(quán)重設(shè)置80%和20%2/1/20236.7動(dòng)態(tài)規(guī)劃及其

在路徑規(guī)劃中的應(yīng)用圖的矩陣表示方法有向圖的路徑尋優(yōu)無(wú)向圖的路徑最優(yōu)搜索2/1/20236.7.1圖的矩陣表示方法圖是由節(jié)點(diǎn)和邊構(gòu)成的。邊是連接兩個(gè)節(jié)點(diǎn)的直接路徑。如果邊是有向的，則圖稱為有向圖，否則稱為無(wú)向圖在計(jì)算機(jī)中，圖用矩陣表示，即關(guān)聯(lián)矩陣MATLAB語(yǔ)言還支持關(guān)聯(lián)矩陣的稀疏矩陣表示方法2/1/2023構(gòu)造關(guān)聯(lián)矩陣的稀疏矩陣函數(shù)調(diào)用格式其中，為起始節(jié)點(diǎn)向量，為終止節(jié)點(diǎn)向量，為邊權(quán)值向量，這里各個(gè)向量最后的一個(gè)值使得關(guān)聯(lián)矩陣為方陣2/1/2023稀疏矩陣可以由full()函數(shù)變換成常規(guī)矩陣，而常規(guī)矩陣可以由sparse()函數(shù)轉(zhuǎn)換成稀疏矩陣注意：在若第i和j節(jié)點(diǎn)間不存在邊，則可令，當(dāng)然，也有的算法要求2/1/20236.7.2有向圖的路徑尋優(yōu)有向圖最短路徑問(wèn)題的手工求解有向圖搜索及圖示Dijkstra最短路徑算法及實(shí)現(xiàn)2/1/2023

有向圖最短

路徑問(wèn)題的手工求解有向圖與最優(yōu)路徑搜索是很多領(lǐng)域都能遇到的常見(jiàn)問(wèn)題應(yīng)用動(dòng)態(tài)規(guī)劃理論，通常需要由終點(diǎn)反推回起點(diǎn)，搜索最優(yōu)路徑2/1/2023例6.45有向圖路徑如下，數(shù)字為從該路徑所花費(fèi)的時(shí)間，試求出從節(jié)點(diǎn)①到節(jié)點(diǎn)⑨的最優(yōu)路徑。最短路徑為：2/1/2023

有向圖搜索及圖示函數(shù)調(diào)用格式建立有向圖對(duì)象求解最短路徑問(wèn)題函數(shù)view()可以顯示有向圖2/1/2023例6.46試求出從節(jié)點(diǎn)①到節(jié)點(diǎn)⑨的最優(yōu)路徑。2/1/2023建立關(guān)聯(lián)矩陣并顯示圖2/1/2023求出最短路徑2/1/2023

Dijkstra最

短路徑算法及實(shí)現(xiàn)編輯MATLAB程序?qū)崿F(xiàn)Dijkstra算法2/1/2023接上頁(yè)2/1/2023函數(shù)的調(diào)用格式其中，W為關(guān)聯(lián)矩陣