1.线性规划模型：用于寻找最优解的数学模型。
Maximize (or Minimize c₁x₁ + c₂x₂ + … + cnxn subject to a₁₁x₁ + a₁₂x₂ + … + a₁nxn ≤ b₁ a₂₁x₁ + a₂₂x₂ + … + a₂nxn ≤ b₂ … am₁x₁ + am₂x₂ + … + amnxn ≤ bm x₁, x₂, …, xn ≥ 0
线性规划有两种基本问题类型，即最大化问题和最小化问题。最大化问题是求目标函数最大值的问题，而最小化问题则是求目标函数最小值的问题。这个问题的解可以是无解的、唯一解的或者有无限多个解。
§1 线性规划
1.1 线性规划的实例与定义
编辑
总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最 小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往 也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我 们建立有效模型的关键之一。
线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以 是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性 规划的标准形式为
编辑
编辑
从上面的图解过程可以看出并不难证明以下断言：
（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域 R 的 “顶点”。 上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n 维 空间中，满足一线性等式 ∑= = n i ai xi b 1 的点集被称为一个超平面，而满足一线性不等式 ∑= ≤ n i ai xi b 1 （或∑= ≥ n i ai xi b 1 ）的点集被称为一个半空间（其中( , , a1 L an 为一n 维行 向量，b 为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面 体。易见，线性规划的可行域必为多胞形（为统一起见，空集Φ 也被视为多胞形）。 在一般n 维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点 可以看成为边界直线的交点，但这一几何概念的推广在一般n 维空间中的几何意义并不 十分直观。为此，我们将采用另一途径来定义它。
编辑
2.整数规划模型：将线性规划中的变量限制为整数。
一般的整数规划模型可以写作如下形式：
$s.t.$ $Ax \leq b$
其中 $x=(x_1,x_2,...,x_n$ 为决策变量，$c=(c_1,c_2,...,c_n$ 为目标函数系数，$A$ 为系数矩阵，$b$ 为右端向量，$Z^n$ 为整数点集。
常用的求解整数规划问题的方法有：
-
割平面法：在每个迭代中，加入一些不在整数点上的线性约束条件，形成一个新的松弛问题，不断进行线性规划求解，直到找到整数最优解。
以上三种方法是目前比较常用的整数规划问题求解方法。同时，还有一些其他的求解方法，例如：整数拟合法、分支限界法、遗传算法等。在实际应用中，根据具体问题的特性选择合适的求解方法是非常重要的。
3.混合整数规划模型：包含线性规划和整数规划两种变量。
混合整数规划模型的一般形式为：
其中，$f(x$是目标函数，$x$是决策变量，$Ax \le b$和$A_{eq} x = b_{eq}$是线性约束条件，$x \in Z^{n}_+$是非负整数约束条件，$x_j \in {0,1}$是$0/1$整数约束条件。
4.最小生成树模型：求加权无向连通图的最小生成树。
下面是最小生成树的基本算法：
-
Kruskal算法：按照边的权重从小到大排序，依次加入生成树，如果加入某条边会形成环，则不加入该边。
最小生成树在实际应用中有广泛的应用，如网络设计、交通运输、电力系统等领域。
5.最短路径模型：寻找两点之间最短路径。
最短路径定义 在一个有向图中，从源点 s 到终点 t 的路径中，每一条边都有一个边权，称这个路径的长度为这条路径上所有边权的和，也叫做路径的权值。在这个有向图中，找到一条从源点 s 到终点 t 的路径，使得这条路径的权值最小，这个问题就被称为最短路径问题。
Dijkstra 算法： Dijkstra 算法是一种贪心算法，用于解决无负权边的单源最短路径问题。它从起点开始，通过逐步扩展最短路径来逐步找到所有节点的最短路径。在每一步中，它找到距离起点最近的未标记节点，并标记该节点。然后，它计算通过该节点到达其他未标记节点的距离，并更新其距离。
- 应用场景 最短路径算法在现实生活中有很多应用场景，例如导航系统中的路径规划、电信网络中的路由选择、物流配送中的路径优化等。
6.网络流模型：求解最大流或最小割问题。
- 网络流
网络流是指在一个网络中，沿着网络中的边从源节点流向汇节点的流量。在建模过程中，我们通常会将网络抽象为一个有向图，其中每个节点代表一个网络节点，每条有向边代表两个节点之间的连接，每个边上有一个容量限制，表示该边能够通过的最大流量。
- 最大流
- 最小割
最小割问题是指将网络划分为源节点和汇节点两个部分，使得两个部分之间的边的容量之和最小。最小割的求解可以通过最大流问题来得到答案。
- 费用流
以上是全国大学生数学建模竞赛中网络流模型的详细解释，掌握这些知识对于成功解决竞赛中的相关问题非常重要。
7.最优化模型：寻找最优解的模型，可包括线性规划、非线性规划等。
-
混合整数规划模型：该模型在整数规划的基础上，引入一些变量可以取实数的情况。求解方法包括分支定界法、割平面法、分枝定界法等。
-
动态规划模型：该模型适用于具有最优子结构性质的问题。采用递推思想，将问题分解为一系列的子问题，并通过比较不同的选择来确定最优解。
-
模拟退火模型：该模型模拟物体在高温环境下的运动，通过模拟过程中的随机跳跃来寻找问题的最优解。
-
神经网络模型：该模型是由多个节点构成的网络，通过学习训练来寻找问题的最优解。常用的神经网络包括前馈神经网络、反馈神经网络、卷积神经网络等。
线性规划模型：该模型可以描述在一定约束条件下，如何最大化或最小化一个线性目标函数。常用的解决方法包括单纯形法、内点法、网络单纯形法等。
8.优化模型：寻找次优解的模型。
-
约束条件：对决策变量的限制条件，通常包括等式约束和不等式约束等。
决策变量：需要优化的变量，通常是某个系统或者过程中可以调整的变量。
优化模型通常有以下几种类型：
-
非线性规划：目标函数或约束条件中至少有一个是非线性的。
-
混合整数规划：有些决策变量可以取整数值，有些必须取实数值。
-
最小生成树：在带权图中选择一棵生成树，使其边权之和最小。
-
网络流：在网络中寻找最大流或最小割。
不同类型的优化模型有不同的解法和算法，对于每一种模型，需要选择适当的方法来求解最优解。
9.动态规划模型：利用递推关系求解最优解问题。
在全国大学生数学建模竞赛中，动态规划模型是常用的一种模型之一，常见的问题类型包括最优化问题、路径问题、序列问题等等。下面分别介绍这些问题类型的动态规划模型。
- 最优化问题 最优化问题是动态规划模型中最为常见的问题类型之一。通常情况下，最优化问题都具有以下两个特点：
- 具有最优子结构：原问题的最优解包含子问题的最优解。
- 具有无后效性：子问题的解只与子问题有关，与其他问题无关。
- 状态定义：设 $f[i][j]$ 表示将前 $i$ 件物品放入容量为 $j$ 的背包中所获得的最大价值。
- 状态转移方程：对于第 $i$ 件物品，有两种情况：
- 不放入背包，此时最大价值为 $f[i-1][j]$；
- 放入背包，此时最大价值为 $f[i-1][j-w[i]]+v[i]$，其中 $w[i]$ 表示第 $i$ 件物品的重量，$v[i]$ 表示第 $i$ 件物品的价值。
- 最终答案为 $\max{f[i-1][j], f[i-1][j-w[i]]+v[i]}$。
- 路径问题 路径问题也是动态规划模型中的一个重要问题类型。在路径问题中，我们需要在一个有向图中寻找一条满足一定条件的路径，通常情况下这个条件是路径的最优性。
以最短路径问题为例，其动态规划模型如下：
- 状态定义：设 $f[i][j]$ 表示从起点到节点 $i$ 的最短路径长度。
- 状态转移方程：对于节点 $i$ 的每个入边 $(k, i$，有 $f[i] = \min{f[k]+w(k,i}$，其中 $w(k,i$ 表示边 $(k,i$ 的权值。
- 最终答案为 $f[n]$，其中 $n$ 表示终点。
- 序列问题 序列问题也是动态规划模型中常见的问题类型之一。通常情况下，序列问题需要在给定的序列中寻找满足一定条件的子序列。
10.随机模型：考虑随机变量和概率分布。
-
随机优化：将优化问题中的一些参数引入随机性，以便更好地描述现实情况，比如考虑生产过程中的随机因素，或者在资源分配问题中考虑随机需求。
马尔可夫过程：描述一系列随机事件，其中每个事件的发生只与前一次事件有关。这种模型在时间序列分析、自然语言处理、图像处理等领域都有广泛的应用。
11.蒙特卡洛模型：通过随机模拟的方法来求解问题。
12.模拟模型：模拟真实系统，以得出模型输出。
13.贪心模型：通过每个阶段的最优选择，得到全局最优解。
14.排队模型：考虑顾客到达、等待、服务、离开等因素。
15.插值模型：通过已知数据点，估计在其他点的函数值。
16.拟合模型：找到一条曲线，以最小化数据点和曲线之间的误差。
17.回归模型：寻找一个函数，以最小化数据点和函数之间的误差。
18.博弈模型：模拟决策者的行为和策略。
19.决策模型：选择最佳决策，以最小化风险或成本。
20.排列组合模型：考虑排列组合问题，如选择、分配、抽样等。
21.图论模型：利用图来表示问题，以解决最短路径、最大流等问题。
22.统计模型：对样本进行统计分析，以推断总体特征。
23.时间序列模型：通过对时间序列的预测，实现规划和决策。
24.时空模型：将时间和空间因素考虑在内。
25.分形模型：通过分形几何的概念，对复杂系统进行建模。
26.非线性规划模型：包含非线性约束的最优化问题。
27.多目标规划模型：考虑多个目标和约束条件的最优化问题。
28.组合优化模型：寻找一组对象的最佳排列、分配等。
算法模型及案例代码知识分享（纯干货）：
提取码：fid3