线性规划

线性规划（linear programming）是在由线性等式和不等式规定的可行域内，最大化或最小化线性目标函数的问题。它研究的是连续变量的优化；若部分变量必须取整数，就进入整数规划。名称中的“规划”来自资源配置与活动安排，并非专指编写程序。

English overview

Linear programming optimizes a linear objective subject to linear equality and inequality constraints. Its feasible region is a polyhedron, so algebraic constraints and geometric structure describe the same problem from different viewpoints. Variables are continuous unless integrality is explicitly required. A feasible problem may have a unique optimum, multiple optima, or an objective that is unbounded in the improving direction.

This article builds a two-variable resource-allocation model, enumerates its vertices, and proves optimality with a matching dual bound. The dual variables assign nonnegative weights to resource constraints; every such feasible weighting gives an upper bound for a maximization problem. Equality between a feasible objective and a dual bound is an independently checkable certificate. We explain weak duality directly, state the conditions for strong duality in finite-dimensional linear programming, and interpret complementary slackness without assuming that every resource is always scarce. The simplex method and interior-point methods are introduced as different algorithmic approaches rather than universal guarantees of practical speed. Historical notes distinguish Kantorovich's early resource-allocation work from Dantzig's development of the simplex method. Modeling limitations include indivisible decisions, uncertain coefficients, and objectives that do not capture the actual decision maker's priorities.

从产量问题建立线性模型

设一种教学场景中生产两种可连续分割的产品，产量分别为 x、y，单位贡献分别为三和二。第一种资源每单位产品都消耗一份，总量四；第二种资源对 x 每单位消耗两份，对 y 消耗一份，总量五。于是问题是 $$max3x+2y\text{subject to}x+y\le 4,2x+y\le 5,x\ge 0,y\ge 0.$$ 所有系数都是示例设定，不代表某家工厂的实测数据。这里假定单位贡献与消耗不随产量变化，产品可以连续分割，资源没有其他用途。若有阶梯价格、启用设备的固定费用或整数批量限制，线性模型可能不足，需要重新建模。

线性意味着目标和约束中的变量只以一次项线性组合出现，系数必须是已知常量。$xy\le 5$、$x^2+y^2\le 5$ 不是线性约束；常量乘以变量则仍是线性的。一个表达式可以通过引入辅助变量转化为线性形式，例如绝对值上界常能拆成两个线性不等式，但这种转换必须证明等价。

用几何把所有候选点找全

每个线性不等式在平面上给出一个半平面，可行域是这些半平面的交。本例顶点为 (0,0)、(5/2,0)、(1,3)、(0,4)。中间顶点由两条资源边界联立：相减得 x=1，再得 y=3。把 y=0 代入得到 x≤5/2，把 x=0 代入得到 y≤4，不能只看一条资源线的坐标截距。

阴影区域满足两种资源限制和非负条件；虚线3x+2y=9在顶点(1,3)支撑可行域。将两条资源约束相加，便得到同一个目标上界9。

四个顶点的目标值依次为 0、15/2、9、8，因此最大值为九，在 (1,3) 达到。还需要说明为什么检查顶点就够：非空有界多面体中的每个点都可写成顶点的凸组合，线性目标在该点的值是对应顶点值的同一加权平均，不会超过顶点最大值。本例的可行域是一个紧的凸多边形，因而这一论证适用。

“线性规划最优点总是唯一一个顶点”则不对。若目标改为 x+y，本例整段从 (0,4) 到 (1,3) 都给出四，整段都是最优解，其中内部点不是顶点。正确说法是在本例这样的非空有界多面体上，至少存在一个顶点最优解，而不是所有最优解都是顶点。一般多面体若含直线，甚至可能没有顶点，不能随意去掉前提。

不可行、无界与没有唯一解

约束 x≥2 与 x≤1 无法同时满足，称为不可行。最大化 x、只约束 x≥0 时，目标可以任意大，称目标向上无界。可行域无界却不等于目标无界，例如最小化 x、约束 x≥0，最小值为零且在 x=0 取得。应分别检查集合的范围与目标沿可行方向怎样变化。

软件返回“unbounded”通常指目标在可行方向无界，而不是仅说明图形延伸到无穷远；返回“infeasible”表示当前数学约束不能同时满足，不自动说明现实任务根本不可能。常见原因也可能是单位混用、符号写反或漏掉了允许的资源来源。建立小规模人工可核对例子，是排查模型错误的重要方法。

对偶：给出别人也能核验的上界

把两条资源约束分别乘以非负权重 u、v，相加得到 $$(u+2v)x+(u+v)y\le 4u+5v.$$ 若再有 $u+2v\ge 3$、$u+v\ge 2$，利用 x、y 非负可知 $3x+2y\le 4u+5v$。于是每组满足这些条件的 u、v 都为所有可行生产方案提供上界。寻找尽可能小的这种上界，就得到对偶问题： $$min4u+5v\text{subject to}u+2v\ge 3,u+v\ge 2,u,v\ge 0.$$ 取 u=v=1，右侧为九；原问题已有 (1,3) 取得九，所以没有任何可行点能更好。这个证明只需加不等式，不必信任绘图精度或某个求解器。解与证书一起给出，是线性规划特别有用的结构。

一般形式 $max\{c^{𝖳}x:Ax\le b,x\ge 0\}$ 的对偶为 $min\{b^{𝖳}y:A^{𝖳}y\ge c,y\ge 0\}$。对任意两组可行解，$c^{𝖳}x\le y^{𝖳}Ax\le y^{𝖳}b$，这就是弱对偶。第一步用 x 非负与对偶可行性，第二步用 y 非负与原可行性。若允许某个变量取任意正负，其对应的对偶条件会改变，不能只搬公式不搬约定。

强对偶和互补松弛的含义

有限维线性规划的强对偶定理说明，若原问题可行，且目标在可行域上具有有限上确界，则上确界能够达到，相应对偶也有最优解，两边最优值相等。这是比弱对偶更深的结论，需要多面体分离或其他论证；前面的小例子直接给出了相等证书，不构成一般定理的证明。本条在此陈述定理，完整证明可参考 MIT 6.253 Lecture 10 的线性规划对偶定理与Farkas引理论证。

对于原对偶可行点，两者目标差可以写成 $$b^{𝖳}y-c^{𝖳}x=y^{𝖳}(b-Ax)+(A^{𝖳}y-c{)}^{𝖳}x.$$ 右侧每个乘积项都非负。最优值相等时，所有这些项都必须为零：某资源有剩余，其权重便必须为零；某产品产量为正，其对应对偶约束必须紧。反过来，若可行且满足这些互补条件，差为零，由弱对偶即可证明最优。这就是互补松弛的核心推导。

需要避免“每条紧约束都有正影子价格”的误解：乘积为零只保证正权重对应零剩余，零剩余不强迫权重大于零。退化或冗余约束可以紧却没有边际价值。对偶解也可能不唯一，因此经济解释必须说明使用哪组最优乘子与允许的扰动范围。

灵敏度：一份资源值多少

在本例最优结构保持不变的小幅变化范围内，u=v=1 表示两种资源右端各增加一小单位，最优目标的一阶变化分别是一。可直接检验：把第一资源总量改为 4+δ，第二仍为五，两条活跃边界交点为 $x=1-\delta ,y=3+2\delta$，目标变成 $9+\delta$。只要 $-3/2\le \delta \le 1$，这些产量保持非负，该点可行且达到原对偶权重给出的上界。区间之外需要重新分析，边界处导数也可能不再唯一。

这个计算不能被夸大为“无论增加多少资源，每单位都永远值一”。当 δ 超过一，表达式中的 x 变负，原最优结构失效；必须重新分析。影子价格通常是局部或分段的敏感性信息，并且以模型的目标、单位与其他条件不变为前提。

算法、整数要求和数值检验

单纯形法沿多面体的基可行解改善目标，常可理解为顶点间移动；退化时一次基变换可能不改变几何点，防循环规则便有意义。内点法通过另一类路径在区域内部附近逼近最优结构。算法选择涉及稀疏性、规模和数值条件，不应因为一个二维图简单就认为所有高维问题都适合手工枚举顶点。

连续解若要求整数，直接四舍五入可能破坏约束或错过最佳整数点。例如只约束 $2x+2y\le 3$、x,y≥0，连续点 (0.75,0.75) 可行，但两者各自四舍五入成一后违反约束。整数规划需要另外的离散处理；连续最优值可以提供界，却不自动给出合法整数方案。

本条主算例碰巧得到整数最优点，并不证明一般连续线性规划都会如此。只有满足特定矩阵结构等条件的模型，才能进一步保证相应的整数性；一个具体图上的巧合不能代替这种定理。判断是否允许连续分割，应由产量单位与现实决策规定，而不能等求解后发现分数不方便才临时四舍五入。

实际求解后应检查原始单位下的约束残差、变量符号、目标重算值以及原对偶间隙。浮点数可能使一个理论上为零的量显示为极小正负数，容差需与问题尺度相配。不能为了让输出看起来可行就任意抹去明显违反约束的部分；修正后的点还需重新计算目标与证书。

灵敏度的完整分段：边际价值何时改变

把第一种资源总量记为 B，第二种保持5，目标仍为 $3x+2y$。当 $0\le B\le 5/2$ 时，先全部生产单位第一资源贡献更高的产品x，取 $x=B,y=0$，第二资源仍足够，目标为3B。对偶权重 $u=3,v=0$ 给出同样上界，因此这不仅是直观建议，也是可验证的最优方案。

当 $5/2\le B\le 5$ 时，最优交点为 $x=5-B,y=2B-5$，目标为 $B+5$，对应对偶证书仍为 $u=v=1$。当 $B\ge 5$ 时，取 $x=0,y=5$，目标为10；此时对偶权重 $u=0,v=2$ 给出上界10，说明额外第一资源已没有价值。因此完整价值函数为 $$V(B)=\{\begin{array}{cc}3B,& 0\le B\le 5/2,\\ B+5,& 5/2\le B\le 5,\\ 10,& B\ge 5.\end{array}$$ 三个区间的边际贡献分别是3、1和0，在连接点处价值函数连续但有折角。影子价格改变对应约束结构改变，而不是对偶理论失效。若 $B<0$，非负变量之和不可能小于负数，问题不可行，不应继续解释这条分段式。

把绝对偏差变成线性规划

一个看起来含非线性符号的问题也可能有等价的线性表达。考虑用实数 z 同时接近观测1和4，目标是最小化 $|z-1|+|z-4|$。引入变量u、v，施加 $$u\ge z-1,u\ge 1-z,v\ge z-4,v\ge 4-z,$$ 并最小化 $u+v$。前两条等价于 $u\ge |z-1|$，后两条等价于 $v\ge |z-4|$；在最小化目标下，最优解可令两者分别等于绝对值，因此转换不会改变最优值或z的最优选择。

三角不等式给出原目标至少为 $|4-1|=3$。对所有 $1\le z\le 4$，目标等于 $(z-1)+(4-z)=3$，所以整段都是最优解。这里不是求导后只挑某个中点，而是明确识别了全部最优位置。若目标改成平方偏差，则最优点是中点2.5；不同损失的几何结构带来不同结论，参见最小二乘法。

本例的z允许任意正负，标准化时可以写为两个非负变量的差。一个原变量可能对应多种这种拆分，但这不改变可表达的z或目标最优值。把等式换成一对反向不等式、把最小化改成负目标的最大化，也都是代数等价转换；它们改变算法输入形式，却不应改变原问题的含义。

可行性与无界性也能附带证书

最优方案可以用对偶界证明，某些失败状态也可以独立核验。对于矛盾约束 $x\ge 2,x\le 1$，把第一条写成 $-x\le -2$，再与第二条相加得到 $0\le -1$，直接证明没有可行点。一般情况下，对约束作具有适当符号的线性组合产生矛盾，是Farkas引理所组织的一类不可行证书。

对最大化问题，如果已有可行点 $x_0$，又找到方向d使 $Ad\le 0,d\ge 0,c^{𝖳}d>0$，那么每个 $x_0+td$ 在 $t\ge 0$ 都可行，目标却持续增加，因而目标无界。这是一个方便检查的充分证书。在一般符号约定下，方向应满足对应的衰退锥条件，不能总要求原变量非负以外的问题也使用同一形式。

这些证书说明优化软件的状态标签应该有数学内容：不可行可以给出矛盾组合，无界可以给出改进射线，最优可以给出原对偶匹配。浮点实现中的近似证书仍需要容差与残差检查，但比只有一个状态词更容易定位问题。

不确定系数属于模型层的问题

若资源消耗系数来自测量估计，精确解出一个固定线性规划，只能说明在那些数值下最优。实际消耗略高就可能违反容量约束。可以逐个检查代表性情景，也可以对规定的不确定范围建立稳健约束；这些处理会改变可行域和最优方案，必须明确采用哪种解释。

同样，把两个现实目标合成一个加权和时，权重表达了偏好或单位换算，并非线性规划算法自动提供的事实。数学最优需要相对于所列目标、约束和系数来理解，不能脱离模型写成“现实中唯一最好的决定”。

历史背景

Kantorovich 在 1939 年发表与生产组织相关的数学方法，Dantzig 在 1947 年发展单纯形法。两者所处的问题背景与后续影响可分别查阅 MacTutor和斯坦福大学记录。线性规划还涉及对偶、几何与算法复杂度等多方面发展，不宜用一个名字概括全部发现史。

编者评注（AI 辅助）

编者评注（AI 辅助）。 线性规划的入门重点不只是画可行域，而是学会同时从可行方案与全局界看问题。一个达到上界的方案，解释力远强于“软件说最优”。建议保留原问题、对偶证书和单位说明，再讨论资源价格或算法速度。这样既能发现符号错误，也能清楚地区分模型内部的最优结论与现实决策仍需作出的假设。

参考来源与延伸阅读

• Boyd 与 Vandenberghe：Convex Optimization，第4章的线性规划、第5章的对偶与敏感性分析。
• MIT 6.253 Lecture 10：线性规划对偶定理及Farkas引理。
• MacTutor：Kantorovich；Stanford：Dantzig。
• 先修：矩阵、优化；相关：最短路径、数学建模。