不等式约束下的线性规划;
线性规划(LP),也称为线性优化,是一种在其要求由线性关系表示的数学模型中实现最佳结果(例如最大利润或最低成本)的方法。线性规划是数学规划(也称为数学优化)的一种特殊情况。更正式地说,线性规划是一种优化线性 目标函数的技术,受线性等式和线性不等式 约束。它的可行域是一个凸多面体,它是一个集合,定义为有限多个半空间的交集,每个半空间都由一个线性不等式定义。它的目标函数是定义在这个多面体上的实值仿射(线性)函数。线性规划算法在多面体中找到一个点如果存在这样的点,则此函数具有最小(或最大值)值。
出于多种原因,线性规划是一个广泛使用的优化领域。运筹学中的许多实际问题可以表示为线性规划问题。线性规划的某些特殊情况,例如网络流问题和多商品流问题,被认为足够重要,可以对专门的算法进行大量研究。许多其他类型的优化问题的算法通过将线性规划问题作为子问题来解决。从历史上看,线性规划的思想启发了优化理论的许多核心概念,例如对偶性、 分解和凸性的重要性及其概括。
1