平面区域与线性目标

半平面、可行域与顶点判定

二元一次不等式 $Ax+By+C\ge0$（$A,B$ 不全为零）表示一个闭半平面：边界为 $Ax+By+C=0$，取不在边界上的一点代入，即可判断满足不等式的一侧。严格不等式排除边界。多个约束同时成立的点集叫可行域。

若可行域是非空有界闭多边形，线性目标 $z=ux+vy$ 一定在某个顶点取得最大值，也在某个顶点取得最小值。

证明。 线性约束的交集是凸集。把凸多边形分成以顶点为顶点的三角形，其中每个点都可写成某个三角形三个顶点的非负加权平均，权重和为一（可用面积权重证明）。因此可行域中任一点 $P$ 都是顶点 $V_i$ 的凸组合 $P=\sum\lambda_iV_i$，且

这个加权平均不超过最大顶点值，也不低于最小顶点值。若一条边的两端都取到同一最优值，则整条边都取到该值；$u=v=0$ 时目标恒为零，所有可行点都最优。

平移等值线的操作步骤与边界检查

目标 $z=ux+vy$ 中 $(u,v)\ne(0,0)$ 时，$ux+vy=z$ 是一族平行直线。沿法向量 $(u,v)$ 平移距离 $s$，目标值增加 $s\sqrt{u^2+v^2}$，因此这个方向是目标增大的方向。

1. 画每个约束的半平面并取交集，标明边界是否包含。
2. 画一条等值线，例如 $ux+vy=0$，确定目标增加和减小的方向。
3. 平移等值线，找仍与可行域相交的极端位置；有界闭多边形可用上一节的顶点判定逐个计算。
4. 检查所求位置是否实际属于可行域，并记录整条边同时最优的情况。

无界区域必须另判目标是否有界。例如 $x\ge0,y\ge0$ 上，$x+y$ 最小值为零而无最大值；目标 $x$ 的最小值也是零，整条非负 $y$ 轴都取到。边界不包含时可能只有上确界或下确界，下面的三角形例子说明这一点。