优化概念

线性规划

最简单的数学规划类型是线性规划。要使你的数学规划成为线性规划，你需要满足以下条件：

• 决策变量必须是实数变量；

• 目标必须是线性表达式；

• 约束条件必须是线性表达式。

线性表达式是任何形式的表达式

\[a_1 x_1 + a_2 x_2 + a_3 x_3 + ... a_n x_n \{<= , =, >=\} b\]

其中 \(a_i\) 和 \(b\) 是已知常数，而 \(x_i\) 是变量。解决线性规划的过程称为线性规划。线性规划通过修正单纯形法（也称为原始单纯形法）、对偶单纯形法或内点法来完成。一些求解器如 cplex 允许你指定使用哪种方法，但我们不会在这里进一步详细讨论。

整数规划

整数程序与线性程序几乎相同，但有一个非常重要的例外。整数程序中的一些决策变量可能需要只有整数值。这些变量被称为整数变量。由于大多数整数程序包含连续变量和整数变量的混合，它们通常被称为混合整数程序。虽然从线性编程的改变是微小的，但对求解过程的影响是巨大的。整数程序可能是非常难以解决的问题，目前有很多研究正在寻找“好”的方法来解决整数程序。整数程序可以使用分支定界法来求解。

对于任何合理大小的MIP，随着整数变量数量的增加，求解时间呈指数增长。