優(yōu)化模型
數(shù)學規(guī)劃模型
整數(shù)線性規(guī)劃
在線性規(guī)劃模型中，規(guī)劃中的變量限制為整數(shù)時稱為整數(shù)線性規(guī)劃。
1. 變量全部限制為整數(shù)，稱為（完全）整數(shù)線性規(guī)劃
2. 變量部分限制為整數(shù)，稱為混合整數(shù)線性規(guī)劃
R 包：Rsymphony
主函數(shù)：
Rsymphony_solve_LP(obj, mat, dir, rhs, bounds = NULL,? types = NULL, max = FALSE, verbosity = -2, time_limit = -1, node_limit = -1, gap_limit = -1,? first_feasible = FALSE, write_lp = FALSE, write_mps = FALSE)
主函數(shù)參數(shù)：
| 主要參數(shù) | 作用? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
| :------: | ---------------------------------------------- |
|? obj? ? | 規(guī)劃目標系數(shù)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
|? mat? ? | 約束向量矩陣? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
|? dir? ? | 約束方向向量，'<','>'? ? ? ? ? ? ? ? ? ? ? ? ? |
|? rhs? ? | 約束值? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
|? bounds? | 上下限的約束，默認0~INF? ? ? ? ? ? ? ? ? ? ? ? |
|? type? | 限定目標變量額類型，‘B’：01規(guī)劃，‘C’代表連續(xù)值 |
|? max? ? | 邏輯值。T 求最大值，F(xiàn) 求最小值? ? ? ? ? ? ? ? |
example：
```? R
library(Rsymphony)
obj <- c(3, 1, 3)
mat <- matrix(c(3, 2, 1, 4, 1, 3, 2, 1, 2), nrow = 3)
dir <- c("<=", "<=", "<=")
rhs <- c(60, 40, 80)
max <- F
Rsymphony_solve_LP(obj, mat, dir, rhs, max = max)
非線性規(guī)劃
非線性規(guī)劃 (non-linear programming) 問題不要求目標函數(shù)、約束條件都為線性形式，較之線性
規(guī)劃問題以及由其發(fā)展出來的整數(shù)規(guī)劃、目標規(guī)劃，非線性規(guī)劃的應用更加廣泛，一般的線性規(guī)劃僅僅是非線性規(guī)劃的特例而已。
對于無約束或者約束條件相對簡單的非線性優(yōu)化問題，stats 包中的 optim()、optimize()、constrOptim()、nlm()、nlminb()等函數(shù)可以完美地解決，并且它們的使用方法相當簡單。
R包： Rdonlp2
安裝方法: install.packages("Rdonlp2", repos="http://R-Forge.R-project.org")
Solve constrained nonlinear minimization problem. 最大值形式需要變形
``` R
donlp2(par,fn, par.upper=rep(+Inf,length(par)), par.lower=rep(+Inf,length(par)), A=NULL, lin.upper=rep(+Inf,length(par)),
?lin.lower=rep(-Inf,length(par)), nlin=list(),nlin.upper=rep(+Inf,length(nlin)), nlin.lower=rep(-Inf,length(nlin)),
?control=donlp2.control(), control.fun=function(lst){return(TRUE)},env=.GlobalEnv,? ?name="Rdonlp2" )
```
對該函數(shù)眾多參數(shù)進行解釋：
>? par : 初始迭代向量
>? fn : 連續(xù)型函數(shù)
>? par.upper、par.lower : 自變量的上下限
>? A：線性約束矩陣
>? lin.upper、lin.lower : 線性約束條件的上下界
>? nlin : 非線性約束條件函數(shù)列表
>? nlin.upper、nlin.lower : 非線性約束條件的上下界
>? 其余參數(shù)可忽略。
```R
library(Rdonlp2)
p = c(10,10)? ? #迭代初始值
par.l = c(-100,-100); par.u = c(100,100) ## 目標值域
# 目標
fn = function(x){ x[1]^2*sin(x[2])+x[2]^2*cos(x[1])}
# 行構(gòu)成線性約束
A = matrix(c(1,1,3,-1),2,byrow=TRUE)
lin.l = c(2,1); lin.u = c(+Inf,3)?
# 構(gòu)成非線性約束
nlcon1 = function(x){ x[1]*x[2]}
nlcon2 = function(x){ sin(x[1])*cos(x[2])}
nlin.l = c(2,-Inf)
nlin.u = c(2,0.6)? #圖片的上界好像錯了，應該是0.6
# 求解
ret = donlp2(p, fn, par.u=par.u, par.l=par.l, A, lin.l=lin.l, lin.u=lin.u,nlin = list(nlcon1,nlcon2),nlin.u = nlin.u, nlin.l = nlin.l)
# 輸出結(jié)果
ret$par
# [1] 1.403076 1.425440
```
目標規(guī)劃
目標規(guī)劃建立模型的步驟為：
用**EXCEL**解似乎更方便。老師上課講過
有個包叫**goalprog**可以做目標規(guī)劃，但是我不會裝，網(wǎng)上沒找到教程。
---
動態(tài)規(guī)劃
手解或根據(jù)實際情況編程求解。
參考網(wǎng)站數(shù)學建模動態(tài)規(guī)劃的小案例之R代碼實現(xiàn)——生產(chǎn)計劃問題
微分方程組模型
1. 人口增長模型（種群增長模型）
簡單模型
? ? x{k}為第k年人數(shù)，r為增長率
Malthus模型
Logistic模型（阻滯增長模型）
? ? 人口相對增長率隨人口的增加而線性減少。
? r(N) = r - s * N r(N(t)) = r - r/N[max] * N
? Malthus模型和Logistic模型都是確定性模型，只考慮人口總數(shù)的連續(xù)時間模型。在研究過程中還發(fā)展了隨機性模型，考慮人口年齡分布的模型等。
? 人口模型的推廣
? 放射性元素的衰變規(guī)律（檢驗名畫的真?zhèn)?，考古年代的判斷?/p>
? 經(jīng)濟領域（通貨膨脹，利率，新產(chǎn)品的銷售，廣告宣傳等）
? 動植物生長規(guī)律（96年的全國大學生數(shù)學建模競賽題）
? 濃度的擴散（人體內(nèi)藥物的吸收，傳染病的傳播與流行等）
2. 傳染病模型
? 考慮**易感人群**、**潛伏期人群**、**感染者**、**健康有免疫者** 四者之間的轉(zhuǎn)化，建立模型。
3. 藥物在體內(nèi)的分布與排除 、捕食系統(tǒng)Volterra模型
圖論與網(wǎng)絡優(yōu)化模型
R包：igraph
1. 最短路徑問題
? shortest_paths()
? ```R
? distance_table(graph, directed = TRUE)
? mean_distance(graph, directed = TRUE, unconnected = TRUE)
? distances(graph, v = V(graph), to = V(graph),
? mode = c("all", "out","in"), weights = NULL, algorithm = c("automatic", "unweighted",
? ? "dijkstra", "bellman-ford", "johnson"))
? shortest_paths(graph, from, to = V(graph), mode = c("out", "all","in"), weights = NULL, output = c("vpath", "epath", "both"),predecessors = FALSE, inbound.edges = FALSE)
? all_shortest_paths(graph, from, to = V(graph), mode = c("out", "all","in"), weights = NULL)
? ```
2. 網(wǎng)絡最大流問題
? max_flow()
? ```?
? #Usage
? max_flow(graph, source, target, capacity = NULL)
? #Arguments
? graph ????????????The input graph.
? source ????????????The id of the source vertex.
? target ????????????The id of the target vertex (sometimes also called sink).
? capacity ????????????Vector giving the capacity of the edges. If this is NULL (the default) then the capacity edge attribute is used. Note that ????????????????????????????the weight edge attribute is not used by this function.
? ```
3. 最小費用最大流問題
4. 最小生成樹（MST）
? ```
? #Usage
? mst(graph, weights = NULL, algorithm = NULL, ...)
? #Arguments
? graph ????????????????????The graph object to analyze.
? weights ????????????????Numeric algorithm giving the weights of the edges in the graph. The order is determined by the edge ids. This is ????????????????????????????????ignored if? the unweighted algorithm is chosen. Edge weights are interpreted as distances.
? algorithm ????????The algorithm to use for calculation. unweighted can be used for unwieghted graphs, and prim runs Prim's algorithm for ????????????????????????????weighted graphs. If this is NULL then igraph tries to select the algorithm automatically: if the graph has an edge attribute ????????????????????????????called weight of the weights argument is not NULL then Prim's algorithm is chosen, otherwise the unwweighted ????????????????????????????algorithm is performed.
? ... ???????????????????????? Additional arguments, unused.
5. 旅行商問題（TSP）
? TSP(Traveling Salesman Problem)即旅行商問題，是數(shù)學領域中著名問題之一。這個問題是這樣的：假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是要求得的路徑長度為所有路徑之中的最小值。
? 目前比較主流的方法是采用一些隨機的、啟發(fā)式的搜索算法，比如遺傳算法、蟻群算法、模擬退貨算法、粒子群算法等。
? R包：tspmeta
? ```R
? coords.df <- data.frame(`####data######)
? # Numeric matrix of city coordinates, rows denote cities.
? coords.mx <- as.matrix(coords.df)
? # Compute distance matrix
? dist.mx <- dist(coords.mx)
? # Construct a TSP object
? tsp.ins <- tsp_instance(coords.mx, dist.mx )
? #
? tour <- run_solver(tsp.ins, method="2-opt")
? #Plot
? autoplot(tsp.ins, tour)
? ```
概率模型
決策樹（運籌學課本）
隨機存儲模型
? 1.確定設計變量和目標變量
? 2.確定目標函數(shù)的表達式
? ? 尋找設計變量和目標變量之間的關(guān)系，構(gòu)建目標函數(shù)
? 3.尋求約束條件
?隨機人口問題
? 把人口當作離散變量看待，初始人群為n0設全人群出生率λ和全人群死亡率μ，把出生與死亡當作相互獨立的事件。根據(jù)全概率公式、微分方程等：
? E(t)與指數(shù)模型形式上一致，D(t)表示人口Z(t)在E(t)附近波動的范圍（方差）。
Markov鏈模型
? 對于一個系統(tǒng)，由一個狀態(tài)轉(zhuǎn)至另一個狀態(tài)的轉(zhuǎn)換過程中，存在著轉(zhuǎn)移概率，并且這種轉(zhuǎn)移概率可以依據(jù)其緊接的前一種狀態(tài)推算出來，與該系統(tǒng)的原始狀態(tài)和此次轉(zhuǎn)移前的馬爾可夫過程無關(guān)。馬爾可夫鏈理論與方法已經(jīng)被廣泛應用于自然科學、工程技術(shù)和公用事業(yè)中。
組合優(yōu)化模型
多維背包問題（MKP）
二維指派問題(QAP)
R package: lpSolve
lp.assign()解決指派問題
#Description
Interface to lp\_solve linear/integer programming system specifically for solving assignment problems
#Usage
?lp.assign (cost.mat, direction = "min", presolve = 0, compute.sens = 0)
lp.transport()解決運輸問題
>Description
>Interface to lp\_solve linear/integer programming system specifically for solving transportation problems
>
>Usage
>lp.transport (cost.mat, direction="min", row.signs, row.rhs, col.signs, col.rhs, presolve=0, compute.sens=0, integers = 1:(nc*nr) )
車輛路徑問題(VRP)
車輛路徑問題(Vehicle Routing Problem，VRP)是組合優(yōu)化和運籌學領域研究的熱點問題之一，其主要研究滿足約束條件的最優(yōu)車輛使用方案以及最優(yōu)的車輛路徑方案?；诨拒囕v路徑問題的框架，研究滿足生產(chǎn)經(jīng)營和運作需要的各種車輛路徑問題.
知網(wǎng)論文：《車輛路徑問題的模型及算法研究綜述》
車間作業(yè)調(diào)度問題（JSP）
JSP問題描述：一個加工系統(tǒng)有M臺機器，要求加工N個作業(yè)，其中，作業(yè)i包含工序數(shù)為Li。令，則L為任務集的總工序數(shù)。其中，各工序的加工時間已確定，并且每個作業(yè)必須按照工序的先后順序加工。調(diào)度的任務是安排所有作業(yè)的加工調(diào)度排序，約束條件被滿足的同時，使性能指標得到優(yōu)化。
知網(wǎng)論文：《車間生產(chǎn)調(diào)度問題研究》
R優(yōu)化常用函數(shù)
nls(formula, data, start, control, algorithm,trace, subset, weights, na.action, model,lower, upper, ...)
用于擬合非線性模型.用summary(nls object)返回結(jié)果.
| Arguments | Descriptions? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
| ---------???? | ------------------------------------------------------------ |
| formula? | a nonlinear model formula including variables and parameters.用'~'符號把兩者隔開 |
| data? ? ? | an optional data frame in which to evaluate the variables in formula and weights. Can also be a list or an environment, but not a matrix. |
| start? ? | a named list or named numeric vector of starting estimates.? |
| trace? ? | logical value indicating if a trace of the iteration progress should be printed. Default is FALSE. |
optim(par, fn, gr = NULL, ..., method,lower = -Inf, upper = Inf, control = list(), hessian = FALSE)
| arguments | Descriptions? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
| --------- | ------------------------------------------------------- |
| par? ? ? | Initial values for the parameters to be optimized over. |
| fn? ? ? ? | A function to be minimized (or maximized)? ? ? ? ? ? ? |
