整点最优直接取角点

线性规划的小题有一句流传很广的口诀：画区域 ⇒ 求角点 ⇒ 逐个代入 ⇒ 比大小。它省事，但它是有前提的——最优解在可行域顶点那条结论要求可行域有界且闭，而且默认 $x$、$y$ 取遍实数。

题面只要动了这两处中的任何一处，角点法就不再是「一定对」的方法，而是「先给个参考值」的方法。

第一处：严格不等号 ⇒ 角点不在可行域里

约束写成 $x+2y-5>0$ 而不是 $\geq 0$ 时，边界那条直线上的点一个都不算。两条边界的交点当然更不算——它同时落在两条被排除的直线上。

于是会出现这样的局面：角点算出来 $z$ 最小，可那个 $z$ 取不到；真正的最小值落在离角点最近的可行点上，比它大。把角点的值直接抄下来，等于把一个开区间的端点当成了最小值。

判法很直白：角点求出来之后，把它代回每一条原约束验一遍，凡是取到等号的那条用的是不是严格不等号。是，这个角点就出局。

第二处：整数条件 ⇒ 角点往往根本不是整点

「若 $x$、$y$ 为整数」这半句话，把可行域从一片连续的区域换成了一堆孤立的格点。这时候：

• 角点的坐标常常是分数（两条边界联立解出来的），压根不在候选之列；
• 就算角点恰好是整点，它旁边那些格点也不一定按连续情形的规律排布——离连续最优点最近的格点，未必是整点里最优的那个；
• 反过来，整数最优值一定不小于连续最优值（可行的整点是可行的实数点的一部分），所以连续最优只能当下界用，不能当答案用。

这条「只能当下界」其实是有用的：$z$ 的连续最小值算出来是 $15.33\dots$，而 $z$ 在整点上取整数值，于是立刻得到 $z\geq 16$；再随手找一个 $z=16$ 的可行整点，就把最小值夹死了。把角点法的结果从「答案」降格成「下界」，它反而变成了正确解法的一部分。

那整点题该怎么做

两条路都要先拿到一个可行的整点，用它的 $z$ 值把搜索范围压成有限的：

• 逐层枚举：固定 $y=0,1,2,\dots$，每层解出最小的可行整数 $x$，算一个 $z$。上界卡住了 $y$ 能取到多大，所以只有有限层。
• 先收紧再松弛：$x$、$y$ 是整数时 $x+2y>5$ 与 $x+2y\geq 6$ 等价（左边是整数，比 $5$ 大就至少是 $6$）。把每条严格不等号都收紧成非严格的，可行域变成闭的，角点法这才重新可用；此时算出的最优值仍是下界，还要再验一次它取得到。

一句话记号

角点法给的是「实数、闭区域」下的答案。 题面写了严格不等号，先验角点在不在域里；题面写了「为整数」，那个数只能当下界，答案要另找。