线性规划：修订间差异

2026年9月20日 (日) 07:18的最新版本

线性规划（linear programming）是在一组线性约束下，使线性目标函数最大或最小的问题。它常用于分配有限资源、安排生产和运输。这里的变量可以连续取值；若产品件数等变量必须为整数，就需要进一步研究整数规划。

下面用同一个两产品模型，依次说明怎样建立约束、从图上找答案、用不等式证明最优，以及资源增加后答案怎样变化。

把资源和收益排成一张表

设两种产品的产量为 $x, y$ ，都允许连续分割。采用以下教学数据，各种资源分别使用自己的统一计量单位，收益使用同一货币单位。

项目	每单位产品 $x$	每单位产品 $y$	可用总量
第一种资源	1	1	4
第二种资源	2	1	5
单位收益	3	2	—

第一种资源的总消耗为 $x + y$ ，不能超过四；第二种资源为 $2 x + y$ ，不能超过五。产量不能为负，总收益是 $3 x + 2 y$ ，所以模型为 $max 3 x + 2 y, x + y \leq 4, 2 x + y \leq 5, x \geq 0, y \geq 0.$ “线性”表示变量只以常数倍相加的方式出现。这个模型假定单位资源消耗和收益不随产量改变；若有启用设备的固定成本或阶梯价格，就须修改模型。

先画出哪些方案可行

等式 $x + y = 4$ 是一条直线，不等式 $x + y \leq 4$ 取包含原点的一侧。第二条资源约束也给出一个半平面。再限制 $x, y \geq 0$ ，各区域共同部分就是可行域。

沿横轴，令 $y = 0$ ，两种资源分别要求 $x \leq 4$ 、 $x \leq 5 / 2$ ，所以横轴终点是 $(5 / 2, 0)$ 。沿纵轴，两个上限分别是四、五，所以纵轴终点是 $(0, 4)$ 。

两条资源边界的交点由 $x + y = 4, 2 x + y = 5$ 确定。第二式减第一式得 $x = 1$ ，代回得 $y = 3$ 。加上原点，可行域的四个顶点为 $(0, 0), (5 / 2, 0), (1, 3), (0, 4)$ 。

第一象限内两种资源约束形成四边形，目标直线三x加二y等于九在一三处接触可行域 — 阴影内每一点都是可行产量。平移收益相同的虚线，最后接触可行域的位置为 (1,3)。

收益相同的方案满足 $3 x + 2 y = c$ ，即 $y = - 3 x / 2 + c / 2$ 。改变 $c$ ，直线斜率不变，只是平行移动。向收益更高的方向移动，最后一次接触可行域时经过 $(1, 3)$ ，收益为九。

四个顶点收益分别为零、 $15 / 2$ 、九、八。为什么本例只检查顶点就够？这个凸四边形可以沿对角线分成两个三角形；三角形内每一点都可写成三个顶点的非负加权平均，权重和为一。线性目标在该点的值，也是顶点目标值的同一加权平均，不会超过其中最大值。因此至少有一个顶点达到最大收益。

这不保证最优点总唯一。若目标改为 $x + y$ ，从 $(0, 4)$ 到 $(1, 3)$ 的整条边都取得四，所有这些点都最优。

用两行不等式证明答案

图形有助于找到候选点，证明则可以更短。把两条资源约束相加： $(x + y) + (2 x + y) \leq 4 + 5, 3 x + 2 y \leq 9.$ 任何可行方案的收益都不会超过九。点 $(1, 3)$ 满足两条资源约束，且收益恰好为九，所以它一定全局最优。

这类证明包含两部分：一个可行方案给出已能达到的收益，一个对所有可行点成立的上界排除更好方案。两者相等，答案便得到核验，不依赖图上读数的精度。

如果简单相加不能恰好得到目标，还可以给资源约束加权。取非负数 $u, v$ ，得到 $(u + 2 v) x + (u + v) y \leq 4 u + 5 v .$ 只要 $u + 2 v \geq 3$ 、 $u + v \geq 2$ ，利用产量非负，就有 $3 x + 2 y \leq (u + 2 v) x + (u + v) y \leq 4 u + 5 v .$ 因此每组这样的 $u, v$ 都给出一个收益上界。寻找最小的上界，就是对偶问题： $min 4 u + 5 v, u + 2 v \geq 3, u + v \geq 2, u, v \geq 0.$ 本例取 $u = v = 1$ ，正好得到上界九。

对偶与剩余资源的关系

把原问题写成矩阵形式 $max {c^{𝖳} x : A x \leq b, x \geq 0}$ ，相应对偶为 $min {b^{𝖳} y : A^{𝖳} y \geq c, y \geq 0}$ 。这里 $x$ 是产量向量， $y$ 是资源权重向量。

任意一对可行解都满足 $c^{𝖳} x \leq y^{𝖳} A x \leq y^{𝖳} b .$ 第一步用产量非负和对偶约束，第二步用权重非负和资源约束。这称为弱对偶：原方案收益不超过对偶给出的上界。

把两端之差拆开，可得 $b^{𝖳} y - c^{𝖳} x = y^{𝖳} (b - A x) + (A^{𝖳} y - c)^{𝖳} x .$ 右边每项都非负。若差为零，每项必须为零：有剩余的资源必须对应零权重；正产量的产品必须对应恰好等于其单位收益的资源加权成本。这称为互补松弛。

本例两种资源在 $(1, 3)$ 处都用尽，两种产品产量也都为正，对应对偶两条约束都取等号。反过来，原、对偶均可行且满足互补松弛时，上下界相等，便能证明最优。

强对偶定理进一步保证：有限维线性规划可行且有有限最优值时，原问题和对偶都能取得最优解，两边最优值相等。前面的不等式证明了弱对偶，强对偶的一般证明还需更多几何工具，可参阅 MIT 线性规划对偶讲义。

增加资源，收益能增加多少

把第一种资源总量从四改为 $B$ ，第二种仍为五。问题成为 $max 3 x + 2 y, x + y \leq B, 2 x + y \leq 5, x, y \geq 0.$ 当资源很少时，第一种产品每份第一资源带来收益三，高于第二种产品的二。若 $0 \leq B \leq 5 / 2$ ，可以全部生产第一种： $x = B, y = 0$ 。第二资源消耗 $2 B \leq 5$ ，收益为 $3 B$ 。对任意可行点， $3 x + 2 y \leq 3 (x + y) \leq 3 B$ ，所以该方案最优。

当 $5 / 2 \leq B \leq 5$ ，两种资源同时用尽的交点满足 $x + y = B, 2 x + y = 5, x = 5 - B, y = 2 B - 5.$ 两个产量都非负，收益是 $B + 5$ 。把两条约束相加也给出上界 $B + 5$ ，所以这个方案最优。

当 $B \geq 5$ ，可以取 $x = 0, y = 5$ ，收益十。因为 $3 x + 2 y \leq 4 x + 2 y = 2 (2 x + y) \leq 10,$ 十也是全域上界。此后第一种资源再增加，第二种资源仍限制了收益。

最优收益因此是分段函数 $V (B) = {\begin{matrix} 3 B, & 0 \leq B \leq 5 / 2, \\ B + 5, & 5 / 2 \leq B \leq 5, \\ 10, & B \geq 5. \end{matrix}$

资源B增加时最优收益先以斜率三增长，在B等于二点五后斜率变一，到五后保持十 — 两个折点对应最优生产方案的变化：第二种资源开始限制产量，随后第一种资源不再稀缺。

图中每一段都由一个可行方案和一个匹配上界推导出来。折点是重新检查活跃约束的位置。

三个区间的斜率分别为三、一、零，表示增加一小单位第一资源所带来的边际收益。在原来的 $B = 4$ 附近，它等于一，与最优对偶权重 $u = 1$ 相同，因此对偶权重也常称影子价格。越过分段点后，最优生产结构改变，影子价格也随之改变。

不能只用一个“求解成功”概括的情况

若约束是 $x \geq 2$ 和 $x \leq 1$ ，不存在可行方案。把第一条改写为 $- x \leq - 2$ ，再与第二条相加，得到矛盾 $0 \leq - 1$ ，便证明了不可行。

若最大化 $x$ 而只有 $x \geq 0$ ，则可以让目标任意大，称为无界。但可行域无界不一定使目标无界：在同一可行域最小化 $x$ ，答案就是零。

变量若必须为整数，连续最优解也可能不适用。例如 $2 x + 2 y \leq 3$ 下，连续方案 $(0.75, 0.75)$ 可行，各自四舍五入成一后却违反约束。因此整数要求应在建模时写明，不能用事后四舍五入代替求解。

绝对值问题也能写成线性规划

用一个数 $z$ 接近观测一和四，若目标为 $| z - 1 | + | z - 4 |$ ，看起来出现了非线性符号。引入两个变量 $u, v$ ，要求 $u \geq z - 1, u \geq 1 - z, v \geq z - 4, v \geq 4 - z,$ 并最小化 $u + v$ ，就得到线性规划。前两条等价于 $u \geq | z - 1 |$ ，后两条等价于 $v \geq | z - 4 |$ ；取最小值时两者可以分别等于绝对值，所以转换保留了原目标的最优值与最优 $z$ 。

三角不等式给出目标至少为三。对任意 $1 \leq z \leq 4$ ，目标恰为 $(z - 1) + (4 - z) = 3$ ，因此整个区间最优。若把损失改为平方偏差，配方则给出唯一最优点 $z = 2.5$ ，参见最小二乘法。

算法与历史

二维问题可以画图，高维问题通常使用算法。单纯形法在基可行解之间改进目标，几何上常表现为沿顶点移动；退化时一次基变换可能仍停在同一点。内点法采用不同的路径逼近最优解。数值结果可以通过原约束残差、对偶约束和两边目标差复核。

Kantorovich 在 1939 年发表与生产组织有关的数学方法，Dantzig 在 1947 年发展单纯形法。两人的工作背景分别见 MacTutor 传记和斯坦福大学记录。今天的线性规划把资源模型、多面体几何、对偶理论与算法联系在一起。

参考来源与延伸阅读

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

@@ 第1行： / 第1行： @@
-'''线性规划'''（linear programming）是在由线性等式和不等式规定的可行域内，最大化或最小化线性目标函数的问题。它研究的是连续变量的优化；若部分变量必须取整数，就进入整数规划。名称中的“规划”来自资源配置与活动安排，并非专指编写程序。
+'''线性规划'''（linear programming）是在一组线性约束下，使线性目标函数最大或最小的问题。它常用于分配有限资源、安排生产和运输。这里的变量可以连续取值；若产品件数等变量必须为整数，就需要进一步研究整数规划。
+下面用同一个两产品模型，依次说明怎样建立约束、从图上找答案、用不等式证明最优，以及资源增加后答案怎样变化。
-== English overview ==
+== 把资源和收益排成一张表 ==
-<div lang="en" class="math-english-summary">
+设两种产品的产量为 <math>x,y</math>，都允许连续分割。采用以下教学数据，各种资源分别使用自己的统一计量单位，收益使用同一货币单位。
-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 class="math-table-scroll" role="region" aria-label="两产品的资源和收益" tabindex="0">
+{| class="wikitable"
+! 项目 !! 每单位产品 <math>x</math> !! 每单位产品 <math>y</math> !! 可用总量
+|-
+| 第一种资源 || 1 || 1 || 4
+|-
+| 第二种资源 || 2 || 1 || 5
+|-
+| 单位收益 || 3 || 2 || —
+|}
 </div>
-== 从产量问题建立线性模型 ==
+第一种资源的总消耗为 <math>x+y</math>，不能超过四；第二种资源为 <math>2x+y</math>，不能超过五。产量不能为负，总收益是 <math>3x+2y</math>，所以模型为
-设一种教学场景中生产两种可连续分割的产品，产量分别为 x、y，单位贡献分别为三和二。第一种资源每单位产品都消耗一份，总量四；第二种资源对 x 每单位消耗两份，对 y 消耗一份，总量五。于是问题是
+<math display="block">\max\ 3x+2y,\qquad x+y\le4,\quad2x+y\le5,\quad x\ge0,\quad y\ge0.</math>
-<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> 不是线性约束；常量乘以变量则仍是线性的。一个表达式可以通过引入辅助变量转化为线性形式，例如绝对值上界常能拆成两个线性不等式，但这种转换必须证明等价。
+== 先画出哪些方案可行 ==
+等式 <math>x+y=4</math> 是一条直线，不等式 <math>x+y\le4</math> 取包含原点的一侧。第二条资源约束也给出一个半平面。再限制 <math>x,y\ge0</math>，各区域共同部分就是可行域。
-== 用几何把所有候选点找全 ==
+沿横轴，令 <math>y=0</math>，两种资源分别要求 <math>x\le4</math>、<math>x\le5/2</math>，所以横轴终点是 <math>(5/2,0)</math>。沿纵轴，两个上限分别是四、五，所以纵轴终点是 <math>(0,4)</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。]]
+两条资源边界的交点由
+<math display="block">x+y=4,\qquad2x+y=5</math>
+确定。第二式减第一式得 <math>x=1</math>，代回得 <math>y=3</math>。加上原点，可行域的四个顶点为 <math>(0,0),(5/2,0),(1,3),(0,4)</math>。
-四个顶点的目标值依次为 0、15/2、9、8，因此最大值为九，在 (1,3) 达到。还需要说明为什么检查顶点就够：非空有界多面体中的每个点都可写成顶点的凸组合，线性目标在该点的值是对应顶点值的同一加权平均，不会超过顶点最大值。本例的可行域是一个紧的凸多边形，因而这一论证适用。
+[[File:Gezhi-linear-programming-theme.svg|frame|center|alt=第一象限内两种资源约束形成四边形，目标直线三x加二y等于九在一三处接触可行域|阴影内每一点都是可行产量。平移收益相同的虚线，最后接触可行域的位置为 (1,3)。]]
-“线性规划最优点总是唯一一个顶点”则不对。若目标改为 x+y，本例整段从 (0,4) 到 (1,3) 都给出四，整段都是最优解，其中内部点不是顶点。正确说法是在本例这样的非空有界多面体上，至少存在一个顶点最优解，而不是所有最优解都是顶点。一般多面体若含直线，甚至可能没有顶点，不能随意去掉前提。
+收益相同的方案满足 <math>3x+2y=c</math>，即 <math>y=-3x/2+c/2</math>。改变 <math>c</math>，直线斜率不变，只是平行移动。向收益更高的方向移动，最后一次接触可行域时经过 <math>(1,3)</math>，收益为九。
-== 不可行、无界与没有唯一解 ==
+四个顶点收益分别为零、<math>15/2</math>、九、八。为什么本例只检查顶点就够？这个凸四边形可以沿对角线分成两个三角形；三角形内每一点都可写成三个顶点的非负加权平均，权重和为一。线性目标在该点的值，也是顶点目标值的同一加权平均，不会超过其中最大值。因此至少有一个顶点达到最大收益。
-约束 x≥2 与 x≤1 无法同时满足，称为不可行。最大化 x、只约束 x≥0 时，目标可以任意大，称目标向上无界。可行域无界却不等于目标无界，例如最小化 x、约束 x≥0，最小值为零且在 x=0 取得。应分别检查集合的范围与目标沿可行方向怎样变化。
-软件返回“unbounded”通常指目标在可行方向无界，而不是仅说明图形延伸到无穷远；返回“infeasible”表示当前数学约束不能同时满足，不自动说明现实任务根本不可能。常见原因也可能是单位混用、符号写反或漏掉了允许的资源来源。建立小规模人工可核对例子，是排查模型错误的重要方法。
+这不保证最优点总唯一。若目标改为 <math>x+y</math>，从 <math>(0,4)</math> 到 <math>(1,3)</math> 的整条边都取得四，所有这些点都最优。
-== 对偶：给出别人也能核验的上界 ==
+== 用两行不等式证明答案 ==
-把两条资源约束分别乘以非负权重 u、v，相加得到
+图形有助于找到候选点，证明则可以更短。把两条资源约束相加：
+<math display="block">(x+y)+(2x+y)\le4+5,\qquad3x+2y\le9.</math>
+任何可行方案的收益都不会超过九。点 <math>(1,3)</math> 满足两条资源约束，且收益恰好为九，所以它一定全局最优。
+这类证明包含两部分：一个可行方案给出已能达到的收益，一个对所有可行点成立的上界排除更好方案。两者相等，答案便得到核验，不依赖图上读数的精度。
+如果简单相加不能恰好得到目标，还可以给资源约束加权。取非负数 <math>u,v</math>，得到
 <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>u+2v\ge3</math>、<math>u+v\ge2</math>，利用产量非负，就有
-<math display="block">\min\ 4u+5v\quad\text{subject to}\quad u+2v\ge3,\quad u+v\ge2,\quad u,v\ge0.</math>
+<math display="block">3x+2y\le(u+2v)x+(u+v)y\le4u+5v.</math>
-取 u=v=1，右侧为九；原问题已有 (1,3) 取得九，所以没有任何可行点能更好。这个证明只需加不等式，不必信任绘图精度或某个求解器。解与证书一起给出，是线性规划特别有用的结构。
+因此每组这样的 <math>u,v</math> 都给出一个收益上界。寻找最小的上界，就是'''对偶问题'''：
+<math display="block">\min\ 4u+5v,\qquad u+2v\ge3,\quad u+v\ge2,\quad u,v\ge0.</math>
+本例取 <math>u=v=1</math>，正好得到上界九。
-一般形式 <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 非负与原可行性。若允许某个变量取任意正负，其对应的对偶条件会改变，不能只搬公式不搬约定。
+== 对偶与剩余资源的关系 ==
+把原问题写成矩阵形式 <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>x</math> 是产量向量，<math>y</math> 是资源权重向量。
-== 强对偶和互补松弛的含义 ==
+任意一对可行解都满足
-有限维线性规划的强对偶定理说明，若原问题可行，且目标在可行域上具有有限上确界，则上确界能够达到，相应对偶也有最优解，两边最优值相等。这是比弱对偶更深的结论，需要多面体分离或其他论证；前面的小例子直接给出了相等证书，不构成一般定理的证明。本条在此陈述定理，完整证明可参考 [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">c^{\mathsf T}x\le y^{\mathsf T}Ax\le y^{\mathsf T}b.</math>
+第一步用产量非负和对偶约束，第二步用权重非负和资源约束。这称为'''弱对偶'''：原方案收益不超过对偶给出的上界。
-对于原对偶可行点，两者目标差可以写成
+把两端之差拆开，可得
 <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>(1,3)</math> 处都用尽，两种产品产量也都为正，对应对偶两条约束都取等号。反过来，原、对偶均可行且满足互补松弛时，上下界相等，便能证明最优。
-== 算法、整数要求和数值检验 ==
+'''强对偶定理'''进一步保证：有限维线性规划可行且有有限最优值时，原问题和对偶都能取得最优解，两边最优值相等。前面的不等式证明了弱对偶，强对偶的一般证明还需更多几何工具，可参阅 [https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/9f80ea2051c10cc0f8cf3839983c381a_MIT6_253S12_lec10.pdf MIT 线性规划对偶讲义]。
-单纯形法沿多面体的基可行解改善目标，常可理解为顶点间移动；退化时一次基变换可能不改变几何点，防循环规则便有意义。内点法通过另一类路径在区域内部附近逼近最优结构。算法选择涉及稀疏性、规模和数值条件，不应因为一个二维图简单就认为所有高维问题都适合手工枚举顶点。
-连续解若要求整数，直接四舍五入可能破坏约束或错过最佳整数点。例如只约束 <math>2x+2y\le3</math>、x,y≥0，连续点 (0.75,0.75) 可行，但两者各自四舍五入成一后违反约束。整数规划需要另外的离散处理；连续最优值可以提供界，却不自动给出合法整数方案。
+== 增加资源，收益能增加多少 ==
+把第一种资源总量从四改为 <math>B</math>，第二种仍为五。问题成为
+<math display="block">\max\ 3x+2y,\qquad x+y\le B,\quad2x+y\le5,\quad x,y\ge0.</math>
+当资源很少时，第一种产品每份第一资源带来收益三，高于第二种产品的二。若 <math>0\le B\le5/2</math>，可以全部生产第一种：<math>x=B,y=0</math>。第二资源消耗 <math>2B\le5</math>，收益为 <math>3B</math>。对任意可行点，<math>3x+2y\le3(x+y)\le3B</math>，所以该方案最优。
-本条主算例碰巧得到整数最优点，并不证明一般连续线性规划都会如此。只有满足特定矩阵结构等条件的模型，才能进一步保证相应的整数性；一个具体图上的巧合不能代替这种定理。判断是否允许连续分割，应由产量单位与现实决策规定，而不能等求解后发现分数不方便才临时四舍五入。
+当 <math>5/2\le B\le5</math>，两种资源同时用尽的交点满足
+<math display="block">x+y=B,\qquad2x+y=5,\qquad x=5-B,\quad y=2B-5.</math>
+两个产量都非负，收益是 <math>B+5</math>。把两条约束相加也给出上界 <math>B+5</math>，所以这个方案最优。
-实际求解后应检查原始单位下的约束残差、变量符号、目标重算值以及原对偶间隙。浮点数可能使一个理论上为零的量显示为极小正负数，容差需与问题尺度相配。不能为了让输出看起来可行就任意抹去明显违反约束的部分；修正后的点还需重新计算目标与证书。
+当 <math>B\ge5</math>，可以取 <math>x=0,y=5</math>，收益十。因为
+<math display="block">3x+2y\le4x+2y=2(2x+y)\le10,</math>
+十也是全域上界。此后第一种资源再增加，第二种资源仍限制了收益。
-== 灵敏度的完整分段：边际价值何时改变 ==
+最优收益因此是分段函数
-把第一种资源总量记为 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>，非负变量之和不可能小于负数，问题不可行，不应继续解释这条分段式。
+[[File:Gezhi-teaching-resource-value.svg|frame|center|alt=资源B增加时最优收益先以斜率三增长，在B等于二点五后斜率变一，到五后保持十|两个折点对应最优生产方案的变化：第二种资源开始限制产量，随后第一种资源不再稀缺。]]
-== 把绝对偏差变成线性规划 ==
-一个看起来含非线性符号的问题也可能有等价的线性表达。考虑用实数 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>B=4</math> 附近，它等于一，与最优对偶权重 <math>u=1</math> 相同，因此对偶权重也常称'''影子价格'''。越过分段点后，最优生产结构改变，影子价格也随之改变。
-== 可行性与无界性也能附带证书 ==
+== 不能只用一个“求解成功”概括的情况 ==
-最优方案可以用对偶界证明，某些失败状态也可以独立核验。对于矛盾约束 <math>x\ge2,x\le1</math>，把第一条写成 <math>-x\le-2</math>，再与第二条相加得到 <math>0\le-1</math>，直接证明没有可行点。一般情况下，对约束作具有适当符号的线性组合产生矛盾，是Farkas引理所组织的一类不可行证书。
+若约束是 <math>x\ge2</math> 和 <math>x\le1</math>，不存在可行方案。把第一条改写为 <math>-x\le-2</math>，再与第二条相加，得到矛盾 <math>0\le-1</math>，便证明了不可行。
-对最大化问题，如果已有可行点 <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> 都可行，目标却持续增加，因而目标无界。这是一个方便检查的充分证书。在一般符号约定下，方向应满足对应的衰退锥条件，不能总要求原变量非负以外的问题也使用同一形式。
+若最大化 <math>x</math> 而只有 <math>x\ge0</math>，则可以让目标任意大，称为无界。但可行域无界不一定使目标无界：在同一可行域最小化 <math>x</math>，答案就是零。
-这些证书说明优化软件的状态标签应该有数学内容：不可行可以给出矛盾组合，无界可以给出改进射线，最优可以给出原对偶匹配。浮点实现中的近似证书仍需要容差与残差检查，但比只有一个状态词更容易定位问题。
+变量若必须为整数，连续最优解也可能不适用。例如 <math>2x+2y\le3</math> 下，连续方案 <math>(0.75,0.75)</math> 可行，各自四舍五入成一后却违反约束。因此整数要求应在建模时写明，不能用事后四舍五入代替求解。
-== 不确定系数属于模型层的问题 ==
+== 绝对值问题也能写成线性规划 ==
-若资源消耗系数来自测量估计，精确解出一个固定线性规划，只能说明在那些数值下最优。实际消耗略高就可能违反容量约束。可以逐个检查代表性情景，也可以对规定的不确定范围建立稳健约束；这些处理会改变可行域和最优方案，必须明确采用哪种解释。
+用一个数 <math>z</math> 接近观测一和四，若目标为 <math>|z-1|+|z-4|</math>，看起来出现了非线性符号。引入两个变量 <math>u,v</math>，要求
+<math display="block">u\ge z-1,\quad u\ge1-z,\qquad 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>；取最小值时两者可以分别等于绝对值，所以转换保留了原目标的最优值与最优 <math>z</math>。
-同样，把两个现实目标合成一个加权和时，权重表达了偏好或单位换算，并非线性规划算法自动提供的事实。数学最优需要相对于所列目标、约束和系数来理解，不能脱离模型写成“现实中唯一最好的决定”。
+三角不等式给出目标至少为三。对任意 <math>1\le z\le4</math>，目标恰为 <math>(z-1)+(4-z)=3</math>，因此整个区间最优。若把损失改为平方偏差，配方则给出唯一最优点 <math>z=2.5</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 辅助） ==
+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 斯坦福大学记录]。今天的线性规划把资源模型、多面体几何、对偶理论与算法联系在一起。
-<div class="math-editorial-note">'''编者评注（AI 辅助）。''' 线性规划的入门重点不只是画可行域，而是学会同时从可行方案与全局界看问题。一个达到上界的方案，解释力远强于“软件说最优”。建议保留原问题、对偶证书和单位说明，再讨论资源价格或算法速度。这样既能发现符号错误，也能清楚地区分模型内部的最优结论与现实决策仍需作出的假设。</div>
 == 参考来源与延伸阅读 ==