线性规划问题的可行域 $R$ 如图 4 所示。

边界构成可行域的一部分。

从可行域中排除的区域已被阴影标记。

已知其中一个约束条件为

$3x + 2y \geq 48$

(a) 写出其余四个约束条件。

可行域的五个顶点分别标记为 A、B、C、D 和 E。

目标函数的形式为

$P = ax + by$

其中 $a$ 和 $b$ 是整数。

该目标函数

• 在顶点 E 处取得最小值 $202\frac{5}{7}$
• 在顶点 C 处取得最大值 $576\frac{2}{3}$

(b) 确定 $a$ 和 $b$ 的值，清楚展示运算过程。

另一个目标函数的形式为

$Q = x + ky$

其中 $k$ 是一个正常数。

该目标函数在顶点 A 处取得最小值，在顶点 C 处取得最大值。

(c) 确定 $k$ 的取值范围，清楚展示运算过程。

逐条观察图中可行域位于各直线的哪一侧。可以选取可行域内一个明显的点代入直线两边，判断不等号方向；题目说明边界属于可行域，所以均使用包含等号的不等号。

The remaining four constraints are

先联立顶点 E 与 C 所在的两条边界直线，求出它们的精确坐标。再把两个顶点坐标分别代入 $P=ax+by$，利用题目给出的最小值和最大值建立关于整数 $a,b$ 的两个一次方程。

Vertex E is the intersection of

and

Solving these equations gives

Vertex C is the intersection of

and

so

At E, $P=202\frac57=\frac{1419}{7}$, hence

At C, $P=576\frac23=\frac{1730}{3}$, hence

Solving the simultaneous equations gives

Therefore, $P=11x+13y$.

目标函数等值线 $x+ky=Q$ 的斜率为 $-1/k$。要使等值线在 A 处取得最小值，其斜率必须越过 A 相邻边界 $3x+2y=48$ 的斜率；要使其在 C 处取得最大值，则还必须受 C 相邻边界 $2x+y=70$ 的斜率限制。分别比较即可得到 $k$ 的上下界。

The objective line

has gradient $-1/k$.

The boundary $3x+2y=48$ has gradient $-3/2$. For the minimum to occur at A,

so, since $k>0$,

The boundary $2x+y=70$ has gradient $-2$. For the maximum to occur at C,

so

Combining the two conditions,

官方评分资料也允许直接比较相邻顶点的目标函数值。A 要比相邻顶点 E 给出更小的 $Q$，而 C 要比相邻顶点 D 给出更大的 $Q$；这两个比较分别产生 $k$ 的上界与下界。

The relevant vertices are

For A to give a smaller value than E,

Hence

For C to give a larger value than D,

Hence

Therefore,

还可以把两条决定范围的边界直线改写成与目标函数 $x+ky$ 相同的形式。改写后的 $y$ 系数正好给出两个临界值，再由可行域中目标线移动的方向判断严格不等号。

Rearranging the boundary through A,

Therefore, for the minimum to occur at A,

Similarly, the boundary through C can be written as

Therefore, for the maximum to occur at C,

Hence