最优解在可行域顶点

结论

设可行域 $D$ 是有界闭的凸多边形，$z=ax+by$ 是线性目标函数，则 $z$ 在 $D$ 上的最大值与最小值都在 $D$ 的顶点处取得。

为什么

分两步，都只用「线性函数沿直线是均匀变化的」这一件事：

1. 在一条线段上，线性函数的最值在端点。 沿线段走，$z$ 要么一路增、要么一路减、要么恒定——中间不会冒出一个比两端都大的值。
2. 把区域上的点赶到顶点。 可行域里任取一点，先沿某个方向走到边界（$z$ 不减），再沿这条边走到它的一个端点，也就是顶点（$z$ 仍不减）。于是任何一点的 $z$ 值都不超过某个顶点的 $z$ 值。

怎么用

• 把可行域的全部顶点求出来（相邻两条边界直线联立），逐个代进 $z=ax+by$，最大的就是最大值、最小的就是最小值。
• 好处是不需要比较斜率：不必判断目标直线该往哪个方向平移，算几个数比大小即可。

边界条件

• 有界是前提。可行域无界时最值可能不存在（$z$ 沿某个方向一路涨到无穷），这时顶点里最大的那个不是最大值。用这条之前先看一眼区域封不封口。
• 闭也是前提。约束里有严格不等号（$<$）时顶点本身不在可行域内，最值取不到，只能谈上确界。
• 最优解不一定唯一：目标直线恰与某条边平行时，那整条边上的点都是最优解——但顶点里仍然取得到最值，所以这条结论不受影响。