浙江 2011 · 数学 q05

冷启动：约束里两个 $>$，题面中间一句「为整数」

题面给的是

$$\begin{cases}x+2y-5>0\\ 2x+y-7>0\\ x\geq 0,\ y\geq 0\end{cases}$$

其中 $x$、$y$ 取整数，要让 $z=3x+4y$ 最小。

（转写里四个选项被连成了一整行，不等式组也被写成了 array；校订层已按卷面把选项分行、把式子换成等价的 cases，字符一个没动。）

两处「不标准」，都不是排版细节，都是题眼：

1. 前两条用的是严格不等号 $>$，不是 $\geq$。 边界那两条直线上的点，一个都不算数。
2. $x$、$y$ 被限定为整数。 可行域从一片连续的区域，变成了一堆孤立的格点。

卷面末尾的「点评」推荐的正是角点法：画可行域 ⇒ 求各个角点 ⇒ 逐一代入 ⇒ 验证。这道题恰好是角点法失灵的那一类，而且失灵得很彻底——照着做出来的数根本不在选项里：

$$x+2y=5,\quad 2x+y=7\ \Longrightarrow\ (x,y)=(3,1),\qquad z=3\cdot 3+4\cdot 1=13 .$$

$(3,1)$ 甚至是个整点，可它让两条约束同时取等，而两条都是严格不等号——它在可行域外面。剩下两个角点 $(5,0)$、$(0,7)$ 同理也在边界上，$z$ 分别是 $15$ 与 $28$。$13$ 和 $15$ 都不在选项里，这本身就是命题人留的提示：这题不是角点法能收场的。

所以整道题的骨架只有两句话：先证 $z$ 到不了更小，再找一个点把 $16$ 取到。 下面三条路，分别是「把候选压成有限个数一遍」「把下界算出来」「借选择题的四个数反查」。

解法一：先拿一个可行整点卡住上界，再一层一层数格点

怎么想到的。 整点有无穷多个，直接「逐个代入」是做不完的。可只要先随手找到一个可行的整点，它的 $z$ 值就成了一道天花板：比它还大的点从此不必看了。而 $x$、$y$ 都非负、系数 $3$ 与 $4$ 都为正，天花板一压下来，剩下的候选就只剩有限个。有限就能数完，数完就是证明。

第一步：找一个可行的整点。 试 $(4,1)$：

$$4+2\cdot 1=6>5,\qquad 2\cdot 4+1=9>7,\qquad 4\geq 0,\ 1\geq 0 .$$

四条全过，$(4,1)$ 可行，$z=3\cdot 4+4\cdot 1=16$。于是

$$z_{\min}\leq 16 .$$

第二步：把搜索范围压成有限。 假设某个可行整点满足 $z=3x+4y<16$。因为 $x\geq 0$、$y\geq 0$，两个加项都非负，所以

$$4y\leq 3x+4y<16\ \Longrightarrow\ y<4\ \Longrightarrow\ y\in\{0,1,2,3\},$$ $$3x\leq 3x+4y<16\ \Longrightarrow\ x<\tfrac{16}{3}\ \Longrightarrow\ x\in\{0,1,2,3,4,5\}.$$

只剩 $4\times 6=24$ 个格子要查——注意这一步用到的只有「系数为正、变量非负」，与可行域的形状无关。

第三步：每一层只需要看最左边那个点。 固定 $y$ 之后，$z=3x+4y$ 关于 $x$ 是递增的，所以这一层里 $z$ 最小的可行点，就是最小的那个可行 $x$。而两条约束对 $x$ 的要求是

$$x>5-2y\qquad\text{与}\qquad x>\frac{7-y}{2},$$

取两者中较大的那个下界，再往上找最小的整数即可：

第四步：读表。 $y=0$ 那层最小的可行 $x$ 是 $6$，已经超出第二步给的 $x\leq 5$，所以这一层里根本没有 $z<16$ 的点；$y=1,2,3$ 三层的最小值分别是 $16$、$17$、$21$，也都不小于 $16$。于是 $z<16$ 的可行整点一个都不存在，即 $z_{\min}\geq 16$。与第一步的 $z_{\min}\leq 16$ 合起来：

$$z_{\min}=16,\qquad\text{选 B}.$$

这条路为什么是完整的证明。 关键在第二步：先有上界，枚举才有尽头。 很多人做这类题是「在图上挨着边界看几个点，挑个最小的」——那只能得到「$\leq$」，得不到「$=$」。上界一给，无穷的搜索就塌缩成一张四行的表，表里每一格都算过，结论才立得住。

解法二：整数把严格不等号收紧，闭区域上的角点法这才可用

怎么想到的。 角点法之所以在这题失灵，是因为可行域不闭（严格不等号）而且候选不连续（只要整点）。第一个毛病其实可以治：$x$、$y$ 都是整数，那么 $x+2y$ 也是整数，而比 $5$ 大的整数里最小的是 $6$。于是

$$x+2y>5\iff x+2y\geq 6,\qquad 2x+y>7\iff 2x+y\geq 8 \qquad(x,y\in\mathbf{Z}).$$

注意这是「等价」，不是「放缩」——在整点上，收紧前后的解集一模一样，没丢任何一个点，也没混进任何一个点。

第一步：换一个闭区域。 记

$$D'=\{(x,y):x+2y\geq 6,\ 2x+y\geq 8,\ x\geq 0,\ y\geq 0\}.$$

它是四个闭半平面的交，故是闭的凸集；朝右上方无界。原问题的可行整点，恰好就是 $D'$ 里的整点。

第二步：先在 $D'$ 上做连续问题。 这一步允许 $x$、$y$ 取实数——放宽了限制，最小值只会变小或不变，所以算出来的是一个下界。$D'$ 无界，但可行域无界当成目标函数没有最值这个坑这里不成立：$D'$ 的无穷远方向都落在第一象限里（沿 $(d_1,d_2)$ 走要保持在 $D'$ 内需 $d_1\geq 0$、$d_2\geq 0$），而 $z=3x+4y$ 沿这些方向严格增大，所以最小值存在，并且由最优解在可行域顶点落在 $D'$ 的顶点上。

$D'$ 的三个顶点（相邻两条边界联立）：

$$\begin{aligned} x+2y=6\ \cap\ 2x+y=8&:\quad (x,y)=\Big(\tfrac{10}{3},\tfrac{4}{3}\Big), & z&=10+\tfrac{16}{3}=\tfrac{46}{3},\\ x+2y=6\ \cap\ y=0&:\quad (6,0),\ \text{且}\ 2\cdot 6+0=12\geq 8\ \checkmark, & z&=18,\\ 2x+y=8\ \cap\ x=0&:\quad (0,8),\ \text{且}\ 0+16=16\geq 6\ \checkmark, & z&=32. \end{aligned}$$

三者取小，连续最小值是 $\dfrac{46}{3}\approx 15.33$。（用平移目标直线看同样一目了然：把 $3x+4y=c$ 这族平行线从左下往右上推，第一次碰到 $D'$ 的就是那个交点。）

第三步：把下界向上取整。 对任何可行整点，

$$z\geq\frac{46}{3}=15.33\dots$$

而 $z=3x+4y$ 在整点上取整数值，比 $15.33\dots$ 大的整数里最小的是 $16$，所以

$$z\geq 16 .$$

第四步：验这个下界够得着。 $(4,1)$ 在 $D'$ 里（$6\geq 6$、$9\geq 8$），且 $z=16$。下界被取到了，它就是最小值。

$$z_{\min}=16,\qquad\text{选 B}.$$

这条路的价值。 它把「角点法」从答案降格成了下界——降格之后，那套熟悉的工具反而重新可用了。整数规划里这是最常用的一招：先解连续松弛拿下界，再找整数解去够它；两边一碰上，就不必枚举了。

解法三：四个选项逐个反查——只问「这个值够不够得着」

怎么想到的。 这是选择题，题面已经担保最小值就在 $14$、$16$、$17$、$19$ 这四个数里。既然如此，就不必去「求」最小值，只需要对每个候选问一句：存不存在可行整点使 $z$ 恰好等于它？ 从最小的那个数开始问，第一个「存在」的就是答案。

问 $14$：$3x+4y=14$ 有没有可行整点？ 先在 $x\geq 0$、$y\geq 0$ 的整点里解这个方程：$4y\leq 14$ 给 $y\leq 3$，逐个试——

• $y=0$：$3x=14$，$x$ 不是整数；
• $y=1$：$3x=10$，不是整数；
• $y=2$：$3x=6$，$x=2$，得 $(2,2)$；
• $y=3$：$3x=2$，不是整数。

整个第一象限里，$z=14$ 只有 $(2,2)$ 这一个整点。 代回约束：

$$2\cdot 2+2=6\ \not>\ 7 .$$

第二条约束过不去（第一条 $2+4=6>5$ 倒是过了——只差一点，这正是命题人把 $14$ 摆进选项的原因）。所以 $14$ 够不着。

问 $16$：$3x+4y=16$ 呢？ $y=1$ 时 $3x=12$、$x=4$，得 $(4,1)$；代回约束 $6>5$、$9>7$，全过。$16$ 够得着。

收口。 最小值不大于 $16$（$(4,1)$ 作证），又不等于 $14$（无可行整点），而它必是四个数之一，故

$$z_{\min}=16,\qquad\text{选 B}.$$

这条路的边界要说清楚。 它依赖「答案在选项里」这个前提：上面证到的其实只有「$z_{\min}\leq 16$ 且 $z_{\min}\neq 14$」，至于 $13$、$12$、$\dots$ 这些不在选项里的值，一个都没查过。填空题或解答题不能这么写，选择题可以。 考场上它最快：两次「解方程 + 代回」，二十秒。

真要补严格，缺的不是「再查一个 $15$」，是一条下界。 两条约束相加即可得到：

$$(x+2y)+(2x+y)>5+7\ \Longrightarrow\ 3x+3y>12\ \Longrightarrow\ x+y>4 .$$

$x+y$ 是整数，故 $x+y\geq 5$；再由 $y\geq 0$，

$$z=3x+4y=3(x+y)+y\geq 3\cdot 5+0=15 .$$

于是只剩 $15$ 要单独排：$3x+4y=15$ 的非负整点是 $(5,0)$ 与 $(1,3)$，前者 $5+0=5\not>5$、后者 $2\cdot 1+3=5\not>7$，两个都不可行。补上这半页，第三条路才是不依赖选项的完整证明——但那时它已经不比解法一、解法二短了，这正是它只适合选择题的原因。

三条路怎么选

考场上写哪条：解法三。 选项给了四个具体的数，反查比正求快一个数量级。

解法一是唯一一条不用任何「线性规划知识」的路——它只用到「系数为正、变量非负 ⇒ 有上界就有有限搜索范围」。这一招在数列、计数题里同样好使，值得完整做一遍。

解法二适合两种情况：一是把 $3x+4y$ 换成别的目标、或把 $14$ 这类干扰项换掉，反查法就失效了，而下界法照样能用；二是当格点很多、枚举不动的时候（比如常数从 $5$、$7$ 换成 $50$、$70$），下界法的工作量几乎不变。

易错

其一，角点求出来就直接代。 这是本题的正坑：$(3,1)$ 由两条边界联立解出来，还恰好是整点，$z=13$ 看着漂亮极了。可它让两条严格不等号同时取等，在可行域外面。 求出角点之后必须代回每一条原约束验一遍：凡是取到等号的那条，看它用的是 $\geq$ 还是 $>$。是 $>$，这个角点就出局。（整点最优直接取角点这条把两种失效情形并在一起说了。）

其二，把连续最优值当成整数最优值。 就算把边界补上（改成 $\geq$），连续最小值也是 $13$（在 $(3,1)$ 处）；本题因为严格不等号，闭化之后连续最小值是 $\dfrac{46}{3}\approx 15.33$。这两个数都不是答案，它们只是下界。下界必须再配一个具体的整点才能升级成最小值——解法二的第四步不是形式，是必须的一步。

其三，只找到 $(4,1)$ 就下结论。 「我试出来 $(4,1)$ 给 $16$，选 B」——这只证到 $z_{\min}\leq 16$。万一有个点给 $15$ 呢？必须补上「更小的取不到」那一半：解法一用有限枚举补，解法二用下界补，解法三用「$14$ 无解 + 答案在选项里」补。三条路的下半场都是在做这件事。

其四，把严格不等号读成非严格。 转写把 $x+2y-5>0$ 抄成 $\geq$，或者画图时把边界画成实线，答案就变成 $13$——而 $13$ 不在选项里，这时候大多数人会回头检查，倒还救得回来。真正危险的是反过来：$(2,2)$ 处 $2x+y=6$，与 $7$ 只差 $1$，若把 $>7$ 记成 $>5$ 或看漏了一条约束，$14$ 就成了「答案」——选项 A 就是为这个准备的。

其五，以为区域无界就没有最小值。 可行域朝右上方伸向无穷，但可行域无界当成目标函数没有最值这条提醒的正是：无界的是区域，$z$ 涨还是跌得看目标函数。这里 $z=3x+4y$ 的两个系数都为正，而区域的无穷远方向都在第一象限里，所以 $z$ 只会越走越大——最小值一定存在，没被拦住的是最大值。