线性规划是在一些线性等式或不等式的约束条件下，求解线性目标函数的最大值或最小值的方法。

线性规划是在一些线性等式或不等式的约束条件下，求解线性目标函数的最大值或最小值的方法。

线性规划是在一组线性等式或不等式约束下，求解线性目标函数最大值或最小值的优化方法。其核心特征是目标函数和约束条件均为决策变量的一次函数，这使得问题具有明确的几何意义和高效的求解路径。从数学本质看，线性规划问题可表述为：在满足 $Ax = b$（等式约束）和 $x \geq 0$（非负约束）的条件下，求目标函数 $c^Tx$ 的极值，其中 $A$ 为 $m \times n$ 矩阵，$x$ 为 $n$ 维决策变量向量。

核心构成与标准形式

线性规划的通用模型包含三个要素：决策变量（待优化的变量 $x_1, x_2, ..., x_n$）、目标函数（形如 $\max/\min z = c_1x_1 + ... + c_nx_n$ 的线性表达式）和约束条件（由线性等式或不等式构成的限制条件）。为便于算法统一处理（如单纯形法），需将问题转化为标准形式，具体规则包括：

目标函数标准化：若求最大值，通过取负转化为最小值（如 $\max z \Leftrightarrow \min -z$）；

不等式约束转化：对 $\leq$ 约束添加非负松弛变量，对 $\geq$ 约束减去非负剩余变量，将其变为等式；

变量非负化：对无符号限制的自由变量，分解为两个非负变量之差（如 $x = x^+ - x^-, x^+, x^- \geq 0$）。

例如，将 $\max z = x_1 - 2x_2$ 转化为标准形式时，需改写为 $\min -z = -x_1 + 2x_2$，并通过添加松弛变量处理不等式约束。

几何意义与基本定理

线性规划的可行域（满足所有约束条件的解集合）是凸集，即任意两点连线仍在集合内。其核心几何特征为：最优解若存在，必位于可行域的顶点（极点）处。顶点对应数学上的基本可行解，即通过令 $n - m$ 个非基变量为 0，求解基变量得到的非负解。这一性质为求解提供了关键思路：只需在有限个顶点中搜索最优解，而非遍历整个可行域。

求解方法与应用场景

1. 图解法

适用于二维决策变量问题，通过绘制可行域和目标函数等值线，直观找到最优顶点。例如，对于 \(\max z = 2x_1 + x_2\)，在可行域中平移目标函数直线，与边界相切的顶点即为最优解。

2. 单纯形法

由丹齐格（Dantzig）于1947年提出，是求解高维问题的经典算法。其核心步骤包括：

初始基可行解：通过人工变量法构造初始顶点；

最优性检验：计算非基变量的检验数，若均非正（对 minimization 问题），当前解最优；

基变换：通过旋转运算替换基变量，迭代至最优解。

尽管单纯形法在最坏情况下复杂度为指数级，但实际应用中效率极高，仍是主流求解器的核心算法。

3. 内点法

1984年卡马卡（Karmarkar）提出的多项式时间算法，通过在可行域内部迭代逼近最优解，适用于大规模问题。

实际应用与价值

线性规划在资源分配、生产调度、物流优化等领域应用广泛。例如：

运输问题：在工厂产能和需求约束下，优化物资运输路径使成本最低；

任务分配：如外卖骑手派单，通过匹配订单与骑手，最小化总配送时间；

投资组合：在风险约束下最大化收益，或在收益目标下最小化风险。

其理论价值还体现在为非线性规划、整数规划等高级优化方法提供基础框架。理解线性规划的本质——通过凸集顶点搜索实现全局优化，不仅是解决实际问题的工具，更是理解优化理论中“线性结构”优越性的关键。

从丹齐格最初为美军后勤优化提出的模型，到如今支撑供应链管理的复杂系统，线性规划始终是“用数学优化决策”的典范。其成功源于对现实问题的精准抽象：当目标与约束均可简化为线性关系时，有限顶点的搜索便能高效找到全局最优解，这正是线性结构赋予的独特优势