數學建模中的演算法

A. 【數學建模演算法】(28)插值和擬合：最小二乘優化

在無約束最優化問題中，有些重要的特殊情形，比如目標函數由若干個函數的平方和構成。這類函數一般可以寫攜含成：

其中 ，一般假設 。我們把極小化這類函數的問題：

稱為最小二乘優化問題。

求解
s.t.
其中 為矩陣， 為向量。
Matlab函數為：
x=lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0)

解：程序如下：

給定輸入輸出數列 ，求參量 使得

Matlab中的函數為：
X=lsqcurvefit(FUN,X0,XDATA,YDATA,LB,UB,OPTIONS)
其中FUN是定義函數 的N文件。

解：這個問題即解最優化問題：

解這個問題要分知蘆兩步：
首先編寫待求函數：

已知函數向量 ，求 使得：

Matlab中的函數為：

用該函數求解例2：
首先編寫含有待求參數的函數：

之後調用函數lsqnonlin，編寫如下程序：

求解 非負 的 ，使得滿足
Matlab中的搭隱帶函數為：

編寫程序如下：

B. 【數學建模演算法】(16)排隊論：常用的幾種概率分布及產生

區間 內的 均勻分布 記做 。服從 分布的隨機變數又稱為隨機數，它是產生其他隨機變數的基礎。如若 為 分布，則 服從 。

以 為期望， 為方差的 正態分布 記做 。正態分布的應用十分廣泛。正態分布還可以作為二項分布一定條件下的近似。

指數分布 是單參數 的非對稱分布，記做 ，概率密度函數為：

數學期望為 ，方差為 。指數分布是唯一具有無記憶性的連續型隨機變數，既有 ，在排隊論，可靠性分析中有廣泛應用。

Gamma分布是雙參數 的非對稱分布，記做 ，期望是 。 時退化為指數分布。 個相互獨立，同分布（參數 ）的指數分布之和是Gamma分布 。Gamma分布可用於服務時間，零件壽命等。
Gamma分布又稱為埃爾朗分布。

Weibull分布是雙參數 的非對稱分布，記做 。 時退化為指數分布。作為設備，零件的壽命分布在可靠性分析中有非常廣泛的應用。

Beta分布是區間 內的雙參數，非均勻分布，記做 。

伯努利分布是 處取值的概率分別是 和 的兩點分布，記做 。用於基本的離散模型。

泊松分布與指數分布有密切的關系。當顧客平均到達率為常數 的到達間隔服從指數分布時，單位時間內到達的顧客數 服從泊松分布，即單位時間內到達 位顧客的概率為：

記做 。泊松分布在排隊服務，產品檢驗，生物與醫學統計，天文，物理等領域都有廣泛應用。

在獨立進行的每次試驗中，某事件發生的概率為 ，則 次實驗中該事件發生的次數 服從二項分布，即發生 次的概率為：

記做 。二項分布是 個獨立的伯努利分布之和。它在產品檢驗，保險，生物和醫學統計等領域有著廣泛的應用。
當 很大時， 近似於正態分布 ；當 很大， 很小，且 約為常數 時， 近似於

C. 數學建模應用的數學建模十大演算法

1、蒙特卡羅演算法,該演算法又稱隨機性模擬演算法，是通過計算機模擬來解決問題的演算法，同時可以通過模擬可以來檢驗自己模型的正確性。
2、數據擬合、參數估計、插值等數據處理演算法，通常使用Matlab作為工具。
3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題，通常使用Lindo、Lingo軟體實現。
4、圖論演算法，這類演算法可以分為很多種，包括最短路、網路流、二分圖等演算法，涉及到圖論的問題可以用這些方法解決。
5、動態規劃、回溯搜索、分治演算法、分支定界等計算機演算法。
6、最優化理論的三大非經典演算法：模擬退火法、神經網路、遺傳演算法（這些問題是用來解決一些較困難的最優化問題的演算法，對於有些問題非常有幫助，但是演算法的實現比較困難，需慎重使用）
7、網格演算法和窮舉法，網格演算法和窮舉法都是暴力搜索最優點的演算法，在很多競賽題中有應用，當重點討論模型本身而輕視演算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具。
8、一些連續離散化方法，很多問題都是實際來的，數據可以是連續的，而計算機只認的是離散的數據，因此將其離散化後進行差分代替微分、求和代替積分等思想是非常重要。
9、數值分析演算法（如果在比賽中採用高級語言進行編程的話，那一些數值分析中常用的演算法比如方程組求解、矩陣運算、函數積分等演算法就需要額外編寫庫函數進行調用）。
10、圖象處理演算法（賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab進行處理）。

D. 參加數學建模有哪些必學的演算法

1. 蒙特卡洛方法：
又稱計算機隨機性模擬方法，也稱統計實驗方法。可以通過模擬來檢驗自己模型的正確性。

2. 數據擬合、參數估計、插值等數據處理
比賽中常遇到大量的數據需要處理，而處理的數據的關鍵就在於這些方法，通常使用matlab輔助，與圖形結合時還可處理很多有關擬合的問題。

3. 規劃類問題演算法：
包括線性規劃、整數規劃、多元規劃、二次規劃等；競賽中又很多問題都和規劃有關，可以說不少的模型都可以歸結為一組不等式作為約束條件，幾個函數表達式作為目標函數的問題，這類問題，求解是關鍵。
這類問題一般用lingo軟體就能求解。

4. 圖論問題：
主要是考察這類問題的演算法，包括：Dijkstra、Floyd、Prime、Bellman-Ford，最大流、二分匹配等。熟悉ACM的人來說，應該都不難。

5. 計算機演算法設計中的問題：
演算法設計包括：動態規劃、回溯搜索、分治、分支定界法（求解整數解）等。

6. 最優化理論的三大非經典演算法：
a) 模擬退火法（SA）
b) 神經網路（NN）
c) 遺傳演算法（GA）

7. 網格演算法和窮舉演算法

8. 連續問題離散化的方法
因為計算機只能處理離散化的問題，但是實際中數據大多是連續的，因此需要將連續問題離散化之後再用計算機求解。
如：差分代替微分、求和代替積分等思想都是把連續問題離散化的常用方法。

9. 數值分析方法
主要研究各種求解數學問題的數值計算方法，特別是適用於計算機實現的方法與演算法。
包括：函數的數值逼近、數值微分與數值積分、非線性返程的數值解法、數值代數、常微分方程數值解等。
主要應用matlab進行求解。

10. 圖像處理演算法
這部分主要是使用matlab進行圖像處理。
包括展示圖片，進行問題解決說明等。

E. 數學建模中的數學模型和演算法有什麼關系，怎樣理解它們之間的聯系和區別

模型是將實際問題轉換為數學問題，演算法是求解模型的方法。

F. 數學建模演算法總結

無總結反省則無進步

寫這篇文章，一是為了總結之前為了准備美賽而學的演算法，而是將演算法羅列並有幾句話解釋方便以後自己需要時來查找。

數學建模問題總共分為四類：

1. 分類問題 2. 優化問題 3. 評價問題 4. 預測問題

我所寫的都是基於數學建模演算法與應用這本書

一 優化問題

線性規劃與非線性規劃方法是最基本經典的：目標函數與約束函數的思想

現代優化演算法：禁忌搜索；模擬退火；遺傳演算法；人工神經網路

模擬退火演算法：

簡介：材料統計力學的研究成果。統計力學表明材料中不同結構對應於粒子的不同能量水平。在高溫條件下，粒子的能量較高，可以自由運動和重新排列。在低溫條件下，粒子能量較低。如果從高溫開始，非常緩慢地降溫（此過程稱為退火），粒子就可以在每個溫度下達到熱平衡。當系統完全被冷卻時，最終形成處於低能狀態的晶體。

思想可用於數學問題的解決 在尋找解的過程中，每一次以一種方法變換新解，再用退火過程的思想，以概率接受該狀態（新解） 退火過程：概率轉化，概率為自然底數的能量/KT次方

遺傳演算法： 遺傳演算法是一種基於自然選擇原理和自然遺傳機制的搜索演算法。模擬自然界中的生命進化機制，在人工系統中實現特定目標的優化。

遺傳演算法的實質是通過群體搜索技術（？），根據適者生存的原則逐代進化，最終得到最優解或准最優解。

具體實現過程（P329~331）

* 編碼

* 確定適應度函數（即目標函數）

* 確定進化參數：群體規模M，交叉概率Pc，變異概率Pm，進化終止條件

* 編碼

* 確定初始種群，使用經典的改良圈演算法

* 目標函數

* 交叉操作

* 變異操作

* 選擇

改良的遺傳演算法

兩點改進 ：交叉操作變為了以「門當戶對」原則配對，以混亂序列確定較差點位置 變異操作從交叉操作中分離出來

二 分類問題（以及一些多元分析方法）

* 支持向量機SVM

* 聚類分析

* 主成分分析

* 判別分析

* 典型相關分析

支持向量機SVM： 主要思想：找到一個超平面，使得它能夠盡可能多地將兩類數據點正確分開，同時使分開的兩類數據點距離分類面最遠

聚類分析（極其經典的一種演算法）： 對樣本進行分類稱為Q型聚類分析 對指標進行分類稱為R型聚類分析

基礎：樣品相似度的度量——數量化，距離——如閔氏距離

主成分分析法： 其主要目的是希望用較少的變數去解釋原來資料中的大部分變異，將掌握的許多相關性很高的變數轉化成彼此相互獨立或不相關的變數。通常是選出比原始變數個數少，能解釋大部分資料中的變異的幾個新變數，及主成分。實質是一種降維方法

判別分析： 是根據所研究的個體的觀測指標來推斷個體所屬類型的一種統計方法。判別准則在某種意義下是最優的，如錯判概率最小或錯判損失最小。這一方法像是分類方法統稱。 如距離判別，貝葉斯判別和FISHER判別

典型相關分析： 研究兩組變數的相關關系 相對於計算全部相關系數，採用類似主成分的思想，分別找出兩組變數的各自的某個線性組合，討論線性組合之間的相關關系

三 評價與決策問題

評價方法分為兩大類，區別在於確定權重上：一類是主觀賦權：綜合資訊評價定權；另一類為客觀賦權：根據各指標相關關系或各指標值變異程度來確定權數

* 理想解法

* 模糊綜合評判法

* 數據包絡分析法

* 灰色關聯分析法

* 主成分分析法（略）

* 秩和比綜合評價法 理想解法

思想：與最優解（理想解）的距離作為評價樣本的標准

模糊綜合評判法 用於人事考核這類模糊性問題上。有多層次模糊綜合評判法。

數據包絡分析法 是評價具有多指標輸入和多指標輸出系統的較為有效的方法。是以相對效率為概念基礎的。

灰色關聯分析法 思想：計算所有待評價對象與理想對象的灰色加權關聯度，與TOPSIS方法類似

主成分分析法（略）

秩和比綜合評價法 樣本秩的概念： 效益型指標從小到大排序的排名 成本型指標從大到小排序的排名 再計算秩和比，最後統計回歸

四 預測問題

* 微分方程模型

* 灰色預測模型

* 馬爾科夫預測

* 時間序列（略）

* 插值與擬合（略）

* 神經網路

微分方程模型 Lanchester戰爭預測模型。。

灰色預測模型 主要特點：使用的不是原始數據序列，而是生成的數據序列 優點：不需要很多數據·，能利用微分方程來充分挖掘系統的本質，精度高。能將無規律的原始數據進行生成得到規律性較強的生成序列。 缺點：只適用於中短期預測，只適合指數增長的預測

馬爾科夫預測 某一系統未來時刻情況只與現在狀態有關，與過去無關。

馬爾科夫鏈

時齊性的馬爾科夫鏈

時間序列（略）

插值與擬合（略）

神經網路（略）