线性规划

线性规划(LP)是最小化或最大化线性目标函数受边界，线性等式和不等式约束。例子包括加工工业的混合、制造业的生产计划、金融业的现金流匹配以及能源和交通运输的规划。

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

\ [\ min_ {x} \左\ {f ^ {\ mathsf {T}} x \ \} \]

受以下限制:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(不等式约束)}\ \A_{eq}x = b_{eq} & \quad & \text{(等式约束)}\ \lb \leq x \leq ub & \quad & \text{(绑定约束)}\end{eqnarray}\]

你可以使用MATLAB^®实现以下常用算法来解决线性优化问题:

• 内点:使用原始-对偶预测-校正算法，特别适用于具有结构或可以使用稀疏矩阵定义的大规模线性程序。
• 单纯形:使用一个系统的过程来生成和测试线性程序的候选顶点解。单纯形算法和相关的双单纯形算法是线性规划中应用最广泛的算法。

对于线性规划的一些特殊情况，其中约束具有网络结构的算法通常比通用的内点算法和单纯形算法更快。特殊情况包括:

• 最大网络流量:使用增宽路径和推-重标签算法。
• 最短路径:使用Dijkstra、Bellman-Ford和搜索算法。
• 线性分配:使用二部匹配算法。

有关算法和线性规划的更多信息，请参见优化工具箱™．