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

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

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

== 把资源和收益排成一张表 ==
设两种产品的产量为 <math>x,y</math>，都允许连续分割。采用以下教学数据，各种资源分别使用自己的统一计量单位，收益使用同一货币单位。

<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>，所以模型为
<math display="block">\max\ 3x+2y,\qquad x+y\le4,\quad2x+y\le5,\quad x\ge0,\quad y\ge0.</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>。

两条资源边界的交点由
<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>。

[[File:Gezhi-linear-programming-theme.svg|frame|center|alt=第一象限内两种资源约束形成四边形，目标直线三x加二y等于九在一三处接触可行域|阴影内每一点都是可行产量。平移收益相同的虚线，最后接触可行域的位置为 (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>、九、八。为什么本例只检查顶点就够？这个凸四边形可以沿对角线分成两个三角形；三角形内每一点都可写成三个顶点的非负加权平均，权重和为一。线性目标在该点的值，也是顶点目标值的同一加权平均，不会超过其中最大值。因此至少有一个顶点达到最大收益。

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

== 用两行不等式证明答案 ==
图形有助于找到候选点，证明则可以更短。把两条资源约束相加：
<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>，利用产量非负，就有
<math display="block">3x+2y\le(u+2v)x+(u+v)y\le4u+5v.</math>
因此每组这样的 <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>x</math> 是产量向量，<math>y</math> 是资源权重向量。

任意一对可行解都满足
<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>
右边每项都非负。若差为零，每项必须为零：有剩余的资源必须对应零权重；正产量的产品必须对应恰好等于其单位收益的资源加权成本。这称为'''互补松弛'''。

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

'''强对偶定理'''进一步保证：有限维线性规划可行且有有限最优值时，原问题和对偶都能取得最优解，两边最优值相等。前面的不等式证明了弱对偶，强对偶的一般证明还需更多几何工具，可参阅 [https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/9f80ea2051c10cc0f8cf3839983c381a_MIT6_253S12_lec10.pdf MIT 线性规划对偶讲义]。

== 增加资源，收益能增加多少 ==
把第一种资源总量从四改为 <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>
十也是全域上界。此后第一种资源再增加，第二种资源仍限制了收益。

最优收益因此是分段函数
<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>
[[File:Gezhi-teaching-resource-value.svg|frame|center|alt=资源B增加时最优收益先以斜率三增长，在B等于二点五后斜率变一，到五后保持十|两个折点对应最优生产方案的变化：第二种资源开始限制产量，随后第一种资源不再稀缺。]]

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

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

== 不能只用一个“求解成功”概括的情况 ==
若约束是 <math>x\ge2</math> 和 <math>x\le1</math>，不存在可行方案。把第一条改写为 <math>-x\le-2</math>，再与第二条相加，得到矛盾 <math>0\le-1</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 斯坦福大学记录]。今天的线性规划把资源模型、多面体几何、对偶理论与算法联系在一起。

== 参考来源与延伸阅读 ==
* [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]。
* 先修：[[矩阵]]、[[优化]]；相关：[[最短路径]]、[[数学建模]]。
[[分类:优化与运筹]]