查看“︁线性规划”︁的源代码

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


== English overview ==
<div lang="en" class="math-english-summary">
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.
</div>

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

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

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

[[File:Gezhi-linear-programming.svg|frame|center|alt=两条资源约束围成的可行域与最优顶点一三，虚线目标值为九|阴影区域满足两种资源限制和非负条件；虚线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，相加得到
<math display="block">(u+2v)x+(u+v)y\le4u+5v.</math>
若再有 <math>u+2v\ge3</math>、<math>u+v\ge2</math>，利用 x、y 非负可知 <math>3x+2y\le4u+5v</math>。于是每组满足这些条件的 u、v 都为所有可行生产方案提供上界。寻找尽可能小的这种上界，就得到对偶问题：
<math display="block">\min\ 4u+5v\quad\text{subject to}\quad u+2v\ge3,\quad u+v\ge2,\quad u,v\ge0.</math>
取 u=v=1，右侧为九；原问题已有 (1,3) 取得九，所以没有任何可行点能更好。这个证明只需加不等式，不必信任绘图精度或某个求解器。解与证书一起给出，是线性规划特别有用的结构。

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

== 强对偶和互补松弛的含义 ==
有限维线性规划的强对偶定理说明，若原问题可行，且目标在可行域上具有有限上确界，则上确界能够达到，相应对偶也有最优解，两边最优值相等。这是比弱对偶更深的结论，需要多面体分离或其他论证；前面的小例子直接给出了相等证书，不构成一般定理的证明。本条在此陈述定理，完整证明可参考 [https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/9f80ea2051c10cc0f8cf3839983c381a_MIT6_253S12_lec10.pdf MIT 6.253 Lecture 10 的线性规划对偶定理与Farkas引理论证]。

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

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

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

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

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

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

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

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

== 灵敏度的完整分段：边际价值何时改变 ==
把第一种资源总量记为 B，第二种保持5，目标仍为 <math>3x+2y</math>。当 <math>0\le B\le5/2</math> 时，先全部生产单位第一资源贡献更高的产品x，取 <math>x=B,y=0</math>，第二资源仍足够，目标为3B。对偶权重 <math>u=3,v=0</math> 给出同样上界，因此这不仅是直观建议，也是可验证的最优方案。

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

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

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

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

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

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

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

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

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

== 历史背景 ==
Kantorovich 在 1939 年发表与生产组织相关的数学方法，Dantzig 在 1947 年发展单纯形法。两者所处的问题背景与后续影响可分别查阅 [https://mathshistory.st-andrews.ac.uk/Biographies/Kantorovich/ MacTutor]和[https://news.stanford.edu/stories/2005/05/george-b-dantzig-operations-research-professor-dies-90 斯坦福大学记录]。线性规划还涉及对偶、几何与算法复杂度等多方面发展，不宜用一个名字概括全部发现史。

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

== 参考来源与延伸阅读 ==
* [https://web.stanford.edu/~boyd/cvxbook/ Boyd 与 Vandenberghe：Convex Optimization]，第4章的线性规划、第5章的对偶与敏感性分析。
* [https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/9f80ea2051c10cc0f8cf3839983c381a_MIT6_253S12_lec10.pdf MIT 6.253 Lecture 10]：线性规划对偶定理及Farkas引理。
* [https://mathshistory.st-andrews.ac.uk/Biographies/Kantorovich/ MacTutor：Kantorovich]；[https://news.stanford.edu/stories/2005/05/george-b-dantzig-operations-research-professor-dies-90 Stanford：Dantzig]。
* 先修：[[矩阵]]、[[优化]]；相关：[[最短路径]]、[[数学建模]]。
[[分类:优化与运筹]]