本推送總結(jié)數(shù)學建模中常用的數(shù)學規(guī)劃模型，并附詳細的MATLAB求解案例。分為四個模塊：

求解數(shù)學模型的一般步驟如下：

• 讀題+理解模型；

• 設計決策變量；

• 列出目標函數(shù)及約束條件；

• 表示（畫）出約束條件代表的可行域;

• 在可行域內(nèi)求目標函數(shù)的最優(yōu)解及最優(yōu)值;

如果你還不太理解，跟著例子往下看...

1 線性規(guī)劃問題（LP）

求線性目標函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題。

舉一個簡單案例：

例：某機床廠生產(chǎn)甲、乙兩種機床，每臺銷售后的利潤分別為4000元與3000元。生產(chǎn)甲機床需用A、B機器加工，加工時間分別為每臺2小時和1小時；生產(chǎn)乙機床需用A、B、C三種機器加工，加工時間為每臺各一小時。若每天可用于加工的機器時數(shù)分別為A機器10小時、B機器8小時和C機器7小時，問該廠應生產(chǎn)甲、乙機床各幾臺，才能使總利潤最大？

根據(jù)上述描述建立數(shù)學模型：

設該廠生產(chǎn)x1臺甲機床和x2乙機床時總利潤最大，則x1,x2應滿足:

上式中：

• x1 , x2 稱之為決策變量; -（1）式被稱為問題的目標函數(shù); -（2）中的幾個不等式是問題的約束條件，記為 s.t.(即 subject to);

上面的目標函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題。

在解決實際問題時，把問題歸結(jié)成一個線性規(guī)劃數(shù)學模型非常重要，但往往也最困難，模型建立得是否恰當，直接影響到求解。選適當?shù)臎Q策變量，是建立有效模型的關(guān)鍵之一。

線性規(guī)劃的目標函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號可以是小于號也可以是大于號。為了避免這種形式多樣性帶來的不便，MATLAB中規(guī)定線性規(guī)劃的標準形式為:

其中c 和 x 為 n 維列向量， A 、 Aeq 為適當維數(shù)的矩陣，b 、beq 為適當維數(shù)的列向量；lb與ub分別為x的下界和上界，維度與x對應。

模型已經(jīng)表示為MATLAB的標準形式，下面就可以采用MATLAB進行求解了，此處采用linprog函數(shù)。

風格1

需要注意的就是將約束條件轉(zhuǎn)換為合適維度的矩陣！

如果你不太想進行矩陣（系數(shù)）轉(zhuǎn)換，也可以采用另一種編程風格：

風格2

相信通過上述的簡單例子，你已經(jīng)對線性問題的建模和求解有了一定的了解，下面我們看更復雜的模型。

2 非線性規(guī)劃

若目標函數(shù)·或·約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題。

非線性規(guī)劃問題有無約束和有約束兩種，它們的求解思路不太一致，具體的方法可以參考“運籌學”或者“最優(yōu)化”的書籍；其中一類比較特殊的問題是二次規(guī)劃問題。

一般說來，解非線性規(guī)劃要比解線性規(guī)劃問題困難得多。而且，也不像線性規(guī)劃有單純形法這一通用方法，非線性規(guī)劃目前還沒有適于各種問題的一般算法，各方法都有特定的適用范圍。

線性規(guī)劃與非線性規(guī)劃的區(qū)別在于：如果線性規(guī)劃的最優(yōu)解存在，則其最優(yōu)解只能在其可行域的邊界上達到（特別是可行域的頂點上達到），而非線性規(guī)劃的最優(yōu)解（如果存在）可能在其可行域的任意一點達到。下方線性問題的圖解法很容易反映解在頂點這一性質(zhì)：

非線性規(guī)劃問題在MATLAB里的標準形式為：

在非線性求解時常用的函數(shù)為fmincon，舉一個示例模型來看看它的用法:

下方為fmincon的調(diào)用格式：

（該模型的代碼在文末下載）

采用fmicon的求解結(jié)果為：

除了采用默認的內(nèi)點法外，也可以根據(jù)需要為fmincon函數(shù)設置不同的尋優(yōu)算法：

接下來是動態(tài)規(guī)劃問題。

3 動態(tài)規(guī)劃

動態(tài)規(guī)劃基本思路

• 將多階段決策過程劃分階段，恰當?shù)剡x擇狀態(tài)變量、決策變量以定義最優(yōu)指標函數(shù)，從而把問題化成一族同類型的子問題，然后逐個求解；

• 求解時從邊界條件開始，逆序過程行進，逐段遞推尋優(yōu)．在每一個子問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果．最后一個子問題的最優(yōu)解，就是整個問題的最優(yōu)解；

• 動態(tài)規(guī)劃方法是既將當前一段與未來各段分開，又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的；

學習動態(tài)規(guī)劃，我們首先要了解多階段決策問題。 比如：

生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。 機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。 航天飛機飛行控制問題：由于航天飛機的運動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機飛行在不同環(huán)境中的情況，不斷地決定航天飛機的飛行方向和速度（狀態(tài)），使之能最省燃料和完成飛行任務（如軟著陸）。

針對多階段決策過程的最優(yōu)化問題，美國數(shù)學家Bellman等人在20世紀50年代初提出了著名的最優(yōu)化原理，把多階段決策問題轉(zhuǎn)化為一系列單階段最優(yōu)化問題，從而逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法：動態(tài)規(guī)劃。對最佳路徑（最佳決策過程）所經(jīng)過的各個階段，其中每個階段始點到全過程終點的路徑，必定是該階段始點到全過程終點的一切可能路徑中的最佳路徑（最優(yōu)決策），這就是Bellman提出的著名的最優(yōu)化原理。即：一個最優(yōu)策略的子策略必然也是最優(yōu)的。

我們還是直接看一個求解案例:

例：設有m=4個目標，目標價值（重要性和危害性）各不相同，用數(shù)值Ak（k=1，2，…,m)表示，計劃用n=5枚導彈突襲，導彈擊毀目標地概率

中a_k是常數(shù)，取決于導彈地特性與目標地性質(zhì)；u_k為向目標發(fā)射地導彈數(shù)，如何做出方案使預期地突擊效果最大？

首先需要建立問題的模型：

根據(jù)模型和動態(tài)規(guī)劃算法建立函數(shù)文件：

完整的代碼在文末

在動態(tài)規(guī)劃問題中，路徑規(guī)劃也非常重要，下方列出了關(guān)于A星算法和概率路線圖（基于dijkstra算法）的求解案例:

A星算法

基于dijkstra的概率路線圖

4 多目標規(guī)劃

上面的問題無論約束條件有多復雜，目標都是只有一個。但是在現(xiàn)實中很多問題都能最終抽象為多目標優(yōu)化問題。這是因為現(xiàn)實問題往往比較復雜，一般在達成目標時會權(quán)衡很多方面。這里簡單介紹主流的幾種方法。

• 包含多個可能有沖突的目標函數(shù)

• 希望找到能夠很好平衡全部優(yōu)化目標的解集

理解多目標優(yōu)化，需要先理解帕累托最優(yōu)（Pareto Optimal）

帕累托最優(yōu)

帕雷托最優(yōu)是指資源分配的一種理想狀態(tài)。給定固有的一群人和可分配的資源，如果從一種分配狀態(tài)到另一種狀態(tài)的變化中，在沒有使任何人境況變壞的前提下，使得至少一個人變得更好，這就是帕雷托改善。

帕雷托最優(yōu)的狀態(tài)就是不可能再有更多的帕雷托改善的狀態(tài)；換句話說，不可能在不使任何其他人受損的情況下再改善某些人的境況。

支配（Dominace）

當x1和x2滿足如下條件時稱x1支配x2： 對于所有目標函數(shù)x1不比x2差； 至少在一個目標函數(shù)上，x1嚴格比x2要好；

(上圖中點1支配點2；點5支配點1；點1和點4互不支配)

不可支配解集

（Non-dominated solution set） 當一個解集中任何一個解都不能被該集合中其他解支配，那么就稱該解集為不可支配解集。

帕累托最優(yōu)解集

（Pareto-optimal set） 所有可行解的不可支配解集被成為帕累托最優(yōu)解集。

帕累托最優(yōu)前沿面

（Pareto-optimal front） 帕累拖最優(yōu)解集的邊界（boundary）被成為帕累托最優(yōu)前沿面。

多目標優(yōu)化問題的經(jīng)典方法有哪些？

線性加權(quán)法

其中權(quán)重代表了每個目標函數(shù)的重要程度。優(yōu)點是簡單；缺點是很難設定一個權(quán)重向量能夠去獲得帕累托最優(yōu)解；在一些非凸情況不能夠保證獲得帕累托最優(yōu)解。

約束轉(zhuǎn)化法

(注：以上關(guān)于多目標優(yōu)化的部分配圖來源于：https://hpzhao.github.io)

多目標遺傳算法

基于遺傳算法的多目標優(yōu)化就是利用遺傳算法的原理來搜索帕累托最優(yōu)前沿面。關(guān)于遺傳算法的介紹在往期推送已有，直接搜索歷史推送即可。

其基本流程如下：

• 隨機產(chǎn)生初始群體;

• 計算各點的目標函數(shù)值和約束函數(shù)值;

• 根據(jù)目標函數(shù)值對群體分級;

• 根據(jù)約束函數(shù)值和分級結(jié)果計算各點的約束罰項、劣解罰項及總罰項;

• 根據(jù)各點的總罰項計算適應度;

• 根據(jù)各點的適應度,進行選擇、交叉和變異操作,生成新群體;

• 將總罰項為0的點放入非劣解集侯選表,對侯選表進行檢查,保留第1級非劣點 , 刪除其它點;

• 檢查是否收斂,如沒有,轉(zhuǎn)到步驟2;

• 刪除侯選表中與其它點距離太近的點;

• 輸出侯選表中的Pareto最優(yōu)解集及對應的目標函數(shù)值;

• 決策人根據(jù)個人偏好從Pareto最優(yōu)解集中挑選出最適合該問題的解；

遺傳算法相比與傳統(tǒng)算法的優(yōu)點是能夠得到一個最優(yōu)解集，而不是單單一個最優(yōu)解，這樣給我們更多的選擇。但計算復雜度可能稍高，而且里面涉及的一些函數(shù)需要精心設計。

多目標優(yōu)化是一個非常復雜的問題，這次肝不動了，之后的推送再介紹（100個“在看”），有一個中文期刊里的案例可以參考《飛機方案多目標優(yōu)化的Pareto遺傳算法》

下載文中提到的所有完整代碼：https://mbd.pub/o/bread/mbd-YZycmplq