$x$ 和 $y$ 的线性规划问题描述如下。

最大化 $P = kx + y$，其中 $k$ 是常数

约束条件：

$3y \geq x$ $x + 2y \leq 130$ $4x + y \geq 100$ $4x + 3y \leq 300$

(a) 在答案本的图 1 上添加线条和阴影来表示这些约束条件。由此确定可行域并标注为 $R$。

(b) 对于 $k = 0.8$ 的情况

(i) 使用目标线法找到可行域的最优顶点 $V$。必须画出并标注目标线，并清楚标注顶点 $V$。

(ii) 计算 $V$ 的坐标，由此计算 $V$ 处相应的 $P$ 值。

已知对于不同的 $k$ 值，$V$ 不是 $R$ 的最优顶点，

(c) 确定 $k$ 的可能取值范围。必须清楚说明方法和计算过程。

先把四个不等式改写成边界直线，并利用两组截距画线。然后逐一判断不等式所要求的半平面：$3y\geq x$ 取直线 $3y=x$ 上方，$x+2y\leq130$ 与 $4x+3y\leq300$ 取各自直线下方，$4x+y\geq100$ 取直线上方。四个半平面的交集就是可行域 $R$。

Draw the four boundary lines using the following points:

The feasible region is above $3y=x$ and $4x+y=100$, and below $x+2y=130$ and $4x+3y=300$.

当 $k=0.8$ 时，目标线为 $0.8x+y=P$，斜率是 $-0.8$。先画任意一条这种斜率的直线，再保持平行向使 $P$ 增大的方向移动；最后接触可行域的顶点就是最优顶点 $V$。

For $k=0.8$, an objective line has equation

and gradient $-0.8$. Moving this line parallel in the direction of increasing $P$, its final point of contact with $R$ is the intersection of

This vertex is labelled $V$.

由 (b)(i)，$V$ 是直线 $x+2y=130$ 与 $4x+3y=300$ 的交点。联立求出坐标后，代入 $P=0.8x+y$。

At $V$,

Multiplying the first equation by $4$ and subtracting the second gives

so $y=44$. Hence

Therefore

The corresponding value of $P$ is

采用顶点值比较。与 $V=(42,44)$ 相邻、可能在目标线转动后取代它的顶点是 $(10,60)$ 和 $(60,20)$。分别令这两个顶点的目标值严格大于 $V$ 的目标值，便得到 $V$ 不再最优的两个范围。严格不等号很重要，因为临界值处 $V$ 仍是最优点之一。

At $V=(42,44)$,

For $(10,60)$ to give a greater value than $V$,

For $(60,20)$ to give a greater value than $V$,

Hence $V$ is not the optimal vertex when

采用目标线斜率比较。顶点 $V$ 两侧边界的斜率分别为 $-\frac12$ 与 $-\frac43$，而目标线 $kx+y=P$ 的斜率为 $-k$。当目标线斜率处于这两个边界斜率之间时，$V$ 是最优顶点；所以题目所求是这个闭区间之外的 $k$。

The two boundary lines meeting at $V$ are

with gradients $-\frac12$ and $-\frac43$, respectively. The objective line

has gradient $-k$. Vertex $V$ is optimal when

that is, when

Therefore $V$ is not optimal when