知识点：线性规划
知识点概述
线性规划（Linear Programming, LP）是研究在一组线性等式和不等式约束下，最大化或最小化一个线性目标函数的问题。它是凸优化最基本的形式，也是运筹学中理论最成熟、应用最广泛的分支。
详细解释
- 标准形式: 任何LP问题都可以转化为等价的标准形式。
- 几何意义:
- 可行域: 由线性约束定义的可行域是一个多面体（Polyhedron）。
- 最优解: 如果LP问题有最优解，那么一定可以在可行域多面体的某个顶点（Vertex）上达到。
- 求解算法:
- 单纯形法 (Simplex Method): 一种经典的LP求解算法。它从可行域的一个顶点开始，沿着边（Edge）移动到相邻的、目标函数值更优的顶点，直到找到最优解。
- 内点法 (Interior-Point Method): 从可行域内部的一个点开始，通过一系列迭代逐步逼近最优解。内点法在理论上是多项式时间的，对于求解大规模LP问题通常比单纯形法更高效。
学习要点
- 掌握线性规划的标准形式。
- 理解LP可行域（多面体）和最优解（在顶点达到）的几何特性。
- 知道单纯形法和内点法是求解LP的两大主流算法。
实践应用
- 生产调度: 在资源（人力、原材料、机器时间）有限的情况下，如何安排生产以最大化利润。
- 运输问题: 如何以最低成本将货物从一系列起点（工厂）运到一系列终点（仓库）。
- 网络流: 计算网络中的最大流量。
关联知识点
- 前置知识: 9-核心概念-线性和非线性规划, 21-核心概念-凸集
- 后续知识: 66-理论方法-线性规划内点法, 53-理论方法-对偶理论
- 相关知识: 48-核心概念-整数规划