【数学建模】常用基本模型总结

线性规划（Linear Programming)

• 运筹学的一个重要分支——数学规划。线性规划是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。
• 概念：可行解、最优解、可行域。
• Matlab中求解线性规划的命令为如下，x返回决策向量的取值；fval返回目标函数的最优值；f为价值向量。

[x,fval] = linprog(f,A,b,Aeq,beq,lb,ub)

• 很多看起来不是线性规划的问题，也可以通过变换转化为线性规划的问题来解决。
  比如对于以下数学规划问题：
  $$\begin{array}{c}\min \left|x_1\right|+\left|x_2\right|+\cdots +\left|x_n\right|\\ \text{ s.t. }\mathbf{A}\mathbf{x}⩽{\mathbf{b}}_{\circ }\end{array}$$
  只要注意到事实：
  对任意的 $x_i$，存在 $u_i,v_i\ge 0$ 满足 $x_i=u_i-v_i,\left|x_i\right|=u_i+v_i$
  所以取$u_i=\frac{x_i+|x_i|}{2},v_i=\frac{|x_i|-x_i}{2}$，记$\mathbf{u}={\left[u_1,\cdots ,u_n\right]}^{\mathrm{T}},\mathbf{v}={\left[v_1,\cdots ,v_n\right]}^{\mathrm{T}}$，
  从而把模型改写成：
  $$\begin{array}{ll}\min & {\sum }_{i=1}^n\left(u_i+v_i\right),\\ \text{ s.t. }& \{\begin{array}{l}[\mathbf{A},-\mathbf{A}]\left[\begin{array}{l}\mathbf{u}\\ \mathbf{v}\end{array}\right]⩽\mathbf{b},\\ \mathbf{u},\mathbf{v}⩾0。\end{array}\end{array}$$