Linear programming — 线性规划

线性规划（Linear Programming，简称LP）是数学规划的一个分支，也是运筹学中广泛使用的一种方法，致力于研究和发展在线性约束条件下求解线性函数极值（最大值或最小值）问题的理论和方法。

LP是解决经济、管理、规划、物流等领域优化问题最强大和最常用的工具之一。

主题与目标

线性规划的主要任务是找到分配有限资源的最佳（最优）方式，以达成某个目标，而该目标和资源使用限制都可以用线性关系来表示。

线性规划可以解决以下实际问题：

标准的线性规划问题表述如下：

要求找到一组决策变量的值，以最大化或最小化一个线性目标函数。同时，这些决策变量受到一组线性等式和/或线性不等式形式的约束。通常，还会增加决策变量的非负性条件（其值必须大于或等于零），这通常是由问题的物理或经济意义决定的。

从数学上讲，这意味着处理线性函数以及线性方程/不等式组。

决策变量（可控变量）：在解决问题过程中需要确定的量（例如，不同产品的生产量、分配给不同目标的资源数量）。
目标函数：由决策变量构成的线性函数，其值需要被最大化或最小化。它量化了问题的目标（例如，总利润、总成本）。
约束条件：决策变量必须满足的一组线性等式和/或不等式。约束条件反映了资源限制、技术要求、计划任务及其他问题条件。
可行域（Feasible Region）：满足问题所有约束条件的决策变量取值集合。在几何上，多维空间中的可行域是一个凸多面体，可能无界或为空集。
可行解：属于可行域的任意一组变量值。
最优解：使目标函数达到其极值（最大值或最小值）的可行解。如果存在最优解，它总位于可行域的边界上，并且至少在可行域凸多面体的一个顶点上（线性规划基本定理）。

存在几种求解线性规划问题的主要方法：

图解法：适用于只有两个决策变量的问题。该方法可以在平面上直观地表示可行域和目标函数，通过分析可行域的顶点或移动目标函数的等值线来找到最优解。
单纯形法：由乔治·丹齐格（George Dantzig）开发的通用迭代算法。该方法从可行域的一个顶点依次移动到相邻顶点，在每一步都改进目标函数的值，直到找到最优解。它是求解LP问题最经典和最著名的方法。
内点法：在单纯形法之后出现的另一类算法。它们在可行域内部而非边界上移动以趋近最优解。这类方法对于求解超大规模的LP问题尤其有效。

每一个线性规划问题（称为原问题）都可以与另一个称为对偶问题的LP问题相对应。原问题和对偶问题之间联系紧密：

一个问题的解可以提供关于另一个问题解的信息。如果两个问题都存在最优解，则它们的目标函数最优值相等。对偶问题的变量具有重要的经济解释——它们对应于资源的影子价格（或对偶价格），显示当相应资源的约束发生微小变化时，原问题目标函数的最优值会改变多少。

线性规划在以下领域有广泛应用：

丹齐格 G. B. 线性规划及其应用与推广. 1966.
尤金 D. B., 戈尔什坦 E. G. 线性规划（理论、方法与应用）. 1969.
Taha, H. A. Operations Research: An Introduction. 10th ed. Pearson, 2017.
Hillier, F. S., Lieberman, G. J. Introduction to Operations Research. 11th ed. McGraw-Hill Education, 2021.