目錄

什么是動態規劃

怎么使用動態規劃？

例題：最短路線問題

2020b-問題一

穩定性分析

靈敏度分析?

---

什么是動態規劃

基本想法：將原問題轉換為一系列相互聯系的子問題，然后通過逐層遞推求得最后的解

基本思想：解決最優解問題，滿足最優性原理（最優策略的任何一部分子策略必需是最優的）

在這類問題中，可能會有許多可行解，每一個解都對應一個值，我們希望找到具有最優值的解。

動態規劃算法中蘊含著遞歸的思想，但是遞歸問題中會出現某些子問題被計算多次，而如果利用動態規劃算法，可以把已經計算過的子問題的解給裝起來，然后用到的時候再拿出來，減少計算次數。

例如：斐波拉契數列

遞歸求法

//定義主函數
#include<stdio.h>
int main()
{int F(int n); //數組printf("%d\n",F(5));return 0;
}
//Fibonacci數列的遞歸算法
int F(int n)
{// 進行條件判斷if(n<=1){return 1;}else{return F(n-1)+F(n-2);}
}

動態規劃求法

#include<stdio.h>
int main()
{int Fibonacci(int n);printf("%d\n",Fibonacci(5));return 0;
}
int Fibonacci(int n)
{//申請一個數組存放子問題的解 int f[n+1],i;f[0]=1;f[1]=1;for(i=2;i<=n;i++){f[i]=f[i-1]+f[i-2];}return f[n];
}

---

怎么使用動態規劃？

1.將過程分為恰當的階段

2.找變量，定義決策變量

3.明確目標，寫出目標函數

4.列約束，尋找對于得到最優解的約束條件

5.寫出狀態轉移方程，根據狀態才可作出決策

---

例題：最短路線問題

根據題目，可以分為七個階段

解題時只需將每一條路徑全都定義出來，然后導入數據大致就可解出答案

但是為了掌握其他導入數據的方法，我們考慮通過xlsx導入數據，通過一頓操作，輸入數據，空值使用-1代替

然后寫入空值，選擇內容，“ctrl+h”-定位-空值- ‘-1’ -“ctrl+enter”?

還需要定義數據名稱，拖拽選中數據，在左上角進行定義（可以看下面的另一張表格圖）

??

model:

sets:
vertex/V1..V16/:V;? //定義一個名為V的頂點集合（把它理解成一個點，還沒有賦值）

road(vertex,vertex):R_D2;? ?//定義一個名為R_D2的道路集合
?

RR(road)|R_D2(&1,&2)#gt#0:D;? ?//定義一個名為D的距離矩陣，其元素是道路集合R_D2中的元素，且距離大于0

endsets

原本沒有加粗行的定義，但是因為數據中空值用-1代替，所以我們需要將非-1的值拿出來

`xx(xx)`這是正常的變量定義，`|`這個符號表示過濾，后面表示R_D2數據要大于等于0，并賦值為D。不難發現，這個過濾的語言只是多了`|`and`#`，其他與bash語言是比較相近的。?

經上述操作就可以篩選出非空的路程值

data:
R_D2=@ole('D:\jianmo\R.xlsx');
enddata

下面進行數據導入

參考：lingo基礎入門Day 11——lingo外部訪問數據、文本文件、電子表格、數據庫_lingo讀取excel數據-CSDN博客

利用ole函數

• 訪問Excel電子表格的關鍵是在Excel中定義數據庫
• 定義數據塊的方法是先選擇單元格區域，從右鍵菜單中選定義名稱，本題定義為R_D2
• 用lingo訪問Excel電子表格前，應當先用Excel打開相應的數據文件，否則不能讀寫數據。

寫出約束

運用for函數遍歷出所有D的情況

@for(RR(i,j):D(i,j)=R_D2(i,j));

將起點（V1）的值設置為0

運用for函數與min函數對集進行循環，計算除起點外的其他頂點的最短路徑值。

對于每個頂點i（除了起點），將其值設置為所有可能的前驅頂點j的最短路徑值加上從j到i的距離的最小值。

V(1)=0;

@for(vertex(i)|i#gt#1:V(i)=@min(RR(j,i):V(j)+D(j,i)));

end

---

2020b-問題一

?2020全國大學生數學建模競賽論文展示（B125） - 2020全國大學生數學建模競賽論文展示 - 中國大學生在線 (moe.gov.cn)

2020全國大學生數學建模競賽B題講評：穿越沙漠 - 2020數學建模賽題講評 - 中國大學生在線 (moe.gov.cn)

---

?

穩定性分析

李雅普諾夫（第二方法）穩定性分析+例題_證明李亞普諾夫atp+pa=-q-CSDN博客

這個我看不太懂?

---

靈敏度分析?

數學建模評價類方法01——靈敏度分析_數學建模靈敏度分析怎么寫-CSDN博客

上面的鏈接寫的很好?

在解題時，結果會受到多個因素的影響，有一些因素是固定的，有一些因素在實際中是有變化的，此時，我們通過取該因素周圍值，進行計算，如果對結果有影響，那我們就說這是敏感的，那究竟有多敏感，就要進行靈敏度分析，看結果與變化率的關系。