线性规划

最大程度地减少受约束的线性函数

线性规划 (LP) 涉及尽可能地减少或增加受边界、线性等式和不等式约束的目标函数。示例问题包括工程中的设计优化、生产中的利润最大化、金融业中的投资组合优化以及能源和交通行业中的调度。

线性规划是寻找将函数最小化的向量 x 的数学问题:

\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]

受线性约束:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(inequality constraint)} \\A_{eq}x = b_{eq} & \quad & \text{(equality constraint)} \\lb \leq x \leq ub & \quad & \text{(bound constraint)}\end{eqnarray}\]

通常使用下列算法求解线性规划问题:

  • 内点法:采用原始-对偶预估-校正算法,尤其适合于具有特殊结构或可通过稀疏性矩阵定义的大规模问题。
  • 动态序列法:最小化对动态序列(局部动态的约束子序列)每次迭代时的目标,直至得到解。
  • 单纯形法:使用系统规划生成并测试线性规划的候选顶点解。单纯形算法是进行线性规划的最常用算法。

有关算法和线性规划的更多信息,请参阅 Optimization Toolbox


示例与具体方法


软件参考

另请参阅: Optimization Toolbox, Global Optimization Toolbox, 整数规划, 二次规划, 非线性规划, 多目标优化, 遗传算法, 模拟退火