模型演算法與矩陣

『壹』 MPC——理論知識（1）

    模型閉穗預測控制重構了追蹤軌跡作為優化問題的任務。優化問題的解決方案是最佳的軌跡。模型預測控制涉及模擬不同的執行器輸入，預測最終的軌跡並以最小的成本選擇該軌跡。當前狀態和參考軌跡是已知的。在每個時間步驟中，制動器輸入被優化以便最小化預測軌跡的成本。一旦找到最低成本的軌跡，執行第一組致動器命令，其餘部分被丟棄，並且在計算新的最佳軌跡時在每個時間步重復。

（1）預測模型：預測模型是模型預測控制的基礎。主要功能是根據對象的歷史信息和未來輸入，預測系統未來的輸出。對於模型預測的形式沒有嚴格的限定，狀態方程、傳遞函數這類傳統的模型都可以作為預測模型。對於線性穩定系統，階躍響應、脈沖響應這類非參數模型，也可以直接作為預測模型使用。

（2）滾動優化：預測模型控制通過某一性能指標的最優來確定控製作用，但優化不是一次離線進行，而是反復在線進行的。這就是滾動優化的含義，也是模型預測控制區別於傳統最優控制的根本點。

（3）反饋校正：在新的采樣時刻，首先檢測對象的實際輸出，並利用這一實時信息對基於模型的預測結果進行修正，然後進行新的優化。

控制過程中始終存在一條期望軌跡。以時刻k作為當前時刻（坐標系縱軸所在的位置），控制器結合當前的測量值和預測模型，預測系統未來一段時域內 （也被稱為預測時域）系統的輸出，如曲線2所示。通過求解滿足目標函數的以及各種約束的優化問題，得到控制時域 內一系列的控制序列，如圖中矩形波4所示（從坐標系縱軸開始），並將該控制序列的第一個元素作為受控對象的實際控制量。當下一個時刻k+1時，重復上述過程，如此滾動地完成一個個帶約束的優化問題，以實現對被控對象的持續控制。

  根據所採用模型的不同，模型預測控制主要包括動態矩陣控制（DMC）、模型演算法控制（MAC）、廣義預測控制（GPC）等。同時，在現代控制理論中廣泛使用的狀態空間模型，同樣可以應用於模型預測控制中。

（1）預測方程

首先考慮以下的離散線性化模型：

設定

可以得到一個新的狀態空間表達式：

                   

其中

所以

可得：

為了進一步簡化計算，做出如下假設：

如果系統預測時域為 ，控制時域為 ，那麼預測時域內的狀態量和系統輸出量可以用以下算式計算:

為了使整個關系更加明確，將系統未來時刻的輸出以矩陣的形式表達：

式中：

通過上式可以清楚看到，在預測時域內的狀態量和輸出量都可以通過系統當前的狀態量 和控制時域內的控制增量 計算得到。這也就是模型預測控制演算法中「預測」功能的實現。

（2）優化求解

    實際上，系統的控制增量是未知的搏仿，只有通過設定合適的優化目標，並對其進行求解，才能得到控制時域內的控制序列。

可以把控制增量作為目標函數的狀態量，優化目標函數如下形式：

其中，第一項反映了系統對參考軌線的跟隨能力，第二項反映了對控制量平穩變化的要求。Q和R為權重矩陣，整個表達式的功能是使系統能夠盡快且平穩地跟蹤上期基態纖望的軌跡。同時，在實際控制系統中，往往需要滿足系統狀態量以及控制量的一些約束，一般如下：

控制量約束：

控制量約束：

輸出約束：

上面三個公式，形成了一個完整的優化目標表達式。通過求解這個帶約束條件的優化目標，就能得到未來一段時間的控制序列。然而，由於系統的模型是實時改變的，並不能保證每個時刻該優化目標都能得到可行解。因此，有必要對優化目標進行相應的處理。比普遍並且證明有效的方式是在優化目標中加入鬆弛因子，如下所示：

式中， 為權重系數， 為鬆弛因子。

將系統輸出的狀態空間表達式代入優化目標式，並且將預測時域內的輸出量偏差表示為：

經過相應的矩陣計算， 可以將優化目標調整為：

式中：

在式中， 為常量，因此模型預測控制在每一步的帶約束優化求解問題都等價於求解如下的二次規劃問題：

（3）反饋機制

    在每個控制周期內完成對上式的求解後，得到了控制時域內的一系列控制輸入增量：

    根據模型預測控制的基本原理，將該控制序列中的第一個元素作為實際的控制輸入增量作用於系統，即：

    系統執行這一控制量直到下一時刻。在新的時刻，系統根據狀態信息重新預測下一段時域的輸出，通過優化過程得到一個新的控制增量序列。如此循環，直到系統完成控制過程。

『貳』 數學建模演算法有哪些

1. 蒙特卡羅演算法。 該演算法又稱隨機性模擬演算法，是通過計算機模擬來解決問題的演算法，同時可以通過模擬來檢驗自己模型的正確性，幾乎是比賽時必用的方法。
2. 數據擬合、參數估計、插值等數據處理演算法。 比賽中通常會遇到大量的數據需要處理，而處理數據的關鍵就在於這些演算法，通常使用MATLAB 作為工具。
3. 線性規劃、整數規劃、多元規劃、二次規劃等規劃類演算法。 建模競賽大多數問題屬於最優化問題，很多時候這些問題可以用數學規劃演算法來描述，通常使用Lindo、Lingo 軟體求解。
4. 圖論演算法。 這類演算法可以分為很多種，包括最短路、網路流、二分圖等演算法，涉及到圖論的問題可以用這些方法解決，需要認真准備。
5. 動態規劃、回溯搜索、分治演算法、分支定界等計算機演算法。 這些演算法是演算法設計中比較常用的方法，競賽中很多場合會用到。
6. 最優化理論的三大非經典演算法：模擬退火演算法、神經網路演算法、遺傳演算法。 這些問題是用來解決一些較困難的最優化問題的，對於有些問題非常有幫助，但是演算法的實現比較困難，需慎重使用。
7. 網格演算法和窮舉法。 兩者都是暴力搜索最優點的演算法，在很多競賽題中有應用，當重點討論模型本身而輕視演算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具。
8. 一些連續數據離散化方法。 很多問題都是實際來的，數據可以是連續的，而計算機只能處理離散的數據，因此將其離散化後進行差分代替微分、求和代替積分等思想是非常重要的。
9. 數值分析演算法。 如果在比賽中採用高級語言進行編程的話，那些數值分析中常用的演算法比如方程組求解、矩陣運算、函數積分等演算法就需要額外編寫庫函數進行調用。
10. 圖象處理演算法。 賽題中有一類問題與圖形有關，即使問題與圖形無關，論文中也會需要圖片來說明問題，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用MATLAB 進行處理。
以下將結合歷年的競賽題，對這十類演算法進行詳細地說明。
以下將結合歷年的競賽題，對這十類演算法進行詳細地說明。
2 十類演算法的詳細說明
2.1 蒙特卡羅演算法
大多數建模賽題中都離不開計算機模擬，隨機性模擬是非常常見的演算法之一。
舉個例子就是97 年的A 題，每個零件都有自己的標定值，也都有自己的容差等級，而求解最優的組合方案將要面對著的是一個極其復雜的公式和108 種容差選取方案，根本不可能去求解析解，那如何去找到最優的方案呢？隨機性模擬搜索最優方案就是其中的一種方法，在每個零件可行的區間中按照正態分布隨機的選取一個標定值和選取一個容差值作為一種方案，然後通過蒙特卡羅演算法模擬出大量的方案，從中選取一個最佳的。另一個例子就是去年的彩票第二問，要求設計一種更好的方案，首先方案的優劣取決於很多復雜的因素，同樣不可能刻畫出一個模型進行求解，只能靠隨機模擬模擬。
2.2 數據擬合、參數估計、插值等演算法
數據擬合在很多賽題中有應用，與圖形處理有關的問題很多與擬合有關系，一個例子就是98 年美國賽A 題，生物組織切片的三維插值處理，94 年A 題逢山開路，山體海拔高度的插值計算，還有吵的沸沸揚揚可能會考的「非典」問題也要用到數據擬合演算法，觀察數據的走向進行處理。此類問題在MATLAB中有很多現成的函數可以調用，熟悉MATLAB，這些方法都能游刃有餘的用好。
2.3 規劃類問題演算法
競賽中很多問題都和數學規劃有關，可以說不少的模型都可以歸結為一組不等式作為約束條件、幾個函數表達式作為目標函數的問題，遇到這類問題，求解就是關鍵了，比如98年B 題，用很多不等式完全可以把問題刻畫清楚，因此列舉出規劃後用Lindo、Lingo 等軟體來進行解決比較方便，所以還需要熟悉這兩個軟體。
2.4 圖論問題
98 年B 題、00 年B 題、95 年鎖具裝箱等問題體現了圖論問題的重要性，這類問題演算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問題。每一個演算法都應該實現一遍，否則到比賽時再寫就晚了。
2.5 計算機演算法設計中的問題
計算機演算法設計包括很多內容：動態規劃、回溯搜索、分治演算法、分支定界。比如92 年B 題用分枝定界法，97 年B 題是典型的動態規劃問題，此外98 年B 題體現了分治演算法。這方面問題和ACM 程序設計競賽中的問題類似，推薦看一下《計算機演算法設計與分析》（電子工業出版社）等與計算機演算法有關的書。
2.6 最優化理論的三大非經典演算法
這十幾年來最優化理論有了飛速發展，模擬退火法、神經網路、遺傳演算法這三類演算法發展很快。近幾年的賽題越來越復雜，很多問題沒有什麼很好的模型可以借鑒，於是這三類演算法很多時候可以派上用場，比如：97 年A 題的模擬退火演算法，00 年B 題的神經網路分類演算法，象01 年B 題這種難題也可以使用神經網路，還有美國競賽89 年A 題也和BP 演算法有關系，當時是86 年剛提出BP 演算法，89 年就考了，說明賽題可能是當今前沿科技的抽象體現。03 年B 題伽馬刀問題也是目前研究的課題，目前演算法最佳的是遺傳演算法。
2.7 網格演算法和窮舉演算法
網格演算法和窮舉法一樣，只是網格法是連續問題的窮舉。比如要求在N 個變數情況下的最優化問題，那麼對這些變數可取的空間進行采點，比如在[a; b] 區間內取M +1 個點，就是a; a+(b-a)/M; a+2 (b-a)/M; …… ; b 那麼這樣循環就需要進行(M + 1)N 次運算，所以計算量很大。比如97 年A 題、99 年B 題都可以用網格法搜索，這種方法最好在運算速度較快
的計算機中進行，還有要用高級語言來做，最好不要用MATLAB 做網格，否則會算很久的。窮舉法大家都熟悉，就不說了。
2.8 一些連續數據離散化的方法
大部分物理問題的編程解決，都和這種方法有一定的聯系。物理問題是反映我們生活在一個連續的世界中，計算機只能處理離散的量，所以需要對連續量進行離散處理。這種方法應用很廣，而且和上面的很多演算法有關。事實上，網格演算法、蒙特卡羅演算法、模擬退火都用了這個思想。
2.9 數值分析演算法
這類演算法是針對高級語言而專門設的，如果你用的是MATLAB、Mathematica，大可不必准備，因為象數值分析中有很多函數一般的數學軟體是具備的。
2.10 圖象處理演算法
01 年A 題中需要你會讀BMP 圖象、美國賽98 年A 題需要你知道三維插值計算，03 年B 題要求更高，不但需要編程計算還要進行處理，而數模論文中也有很多圖片需要展示，因此圖象處理就是關鍵。做好這類問題，重要的是把MATLAB 學好，特別是圖象處理的部分。

『叄』 模型預測控制的方法

模型預測控制是一種基於模型的閉環優化控制策略，其演算法的核心是：可預測未來的動態模型，在線反復優化計算並滾動實施的控製作用和模型誤差的反饋校正。模型預測控制具有控制效果好、魯棒性強等優點，可有效地克服過程的不確定性、非線性和並聯性，並能方便的處理過程被控變數和操縱變數中的各種約束。從模型預測控制的基本原理出發，常見的有三種預測控制演算法：
1)基於非參數模型的模型預測控制
代表性演算法有模型演算法(MAC)和動態矩陣控制(DMC)。這類演算法分別採用脈沖響應模型和有限階躍響應模型作為過程預測模型，無需考慮模型結構和階次，可將過程時滯自然納入模型中，尤其適合表示動態響應不規則的對象特性，適合處理開環穩定多變數過程約束問題的控制。
2)基於ARMA或CARIMA等輸入輸出參數化模型的預測控制演算法。
這類演算法有經典自適應控制發展而來，融合了自校正控制和預測控制的優點。其反饋校正通過模型的在線辨識和控制率的在線修正以自校正的方式實現，其中最具代表性的是廣義預測演算法，它可應用於時變時滯較難控制的對象，並對系統的時滯和階次不確定有良好的魯棒性，但對於多變數系統，演算法實施較困難。
3)滾動時域控制。由LQ和LQG演算法發展而來
對於狀態空間模型，用有限時域二次性能指標再加終端約束的滾動時域控制演算法來保證系統穩定性。它已拓展到跟蹤控制和輸出反饋控制。各類模型預測控制演算法雖然在模型、控制和性能上存在許多差異，但其核心都是基於滾動時域原理，演算法中包含了預測模型、滾動優化和反饋校正三個基本原理。