题目

Problem

A school is planning to run several training days next year for its new teachers, middle leaders and senior leaders.

Next year, the school will need to run

at least 20 training days in total,
at most twice as many training days for new teachers when compared to the total number of training days required for both middle and senior leaders,
at most 25% of the training days for senior leaders.

The costs of running a training day for new teachers, middle leaders and senior leaders are £400, £550 and £750 respectively.

The school wants to minimise the total cost of running the training days.

Let $x$ be the number of training days required for new teachers. Let $y$ be the number of training days required for middle leaders. Let $z$ be the number of training days required for senior leaders.

(a) Formulate this information as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.

(6)

The school decides that the number of training days for middle leaders and the number of training days for senior leaders should be in the ratio 5:3

This reduces two of the constraints to $5x \le 16y$ and $4y \le 5x$ .

(b) (i) Express the constraint representing the requirement for a total of at least 20 training days as a simplified inequality with integer coefficients in terms of $x$ and $y$ only.

(ii) Express the objective in the form $ax + by$ where $a$ and $b$ are integers.

(3)

(c) Represent the constraints in $x$ and $y$ only on Diagram 1 in the answer book. Hence determine, and label, the feasible region $R$ .

(4)

(d) Use the objective line method to locate the optimal vertex, $V$ , of the feasible region. You must make your objective line clear and label the optimal vertex, $V$ .

(3)

(e) Hence, determine

(i) the total cost of running the training days,

(ii) the number of training days required for senior leaders.

(2)

(Total 18 marks)

题目中文翻译

一所学校计划明年为其新教师、中层领导和高级领导开办若干培训日。

明年，学校需要开办：

总共至少 20 天培训日，
新教师的培训日天数，最多为中层领导和高级领导所需培训日总天数的两倍，
高级领导的培训日天数，最多占总培训日天数的 25%。

为新教师、中层领导和高级领导开办培训日的成本分别为 400 英镑、550 英镑和 750 英镑。

学校希望最小化开办培训日的总成本。

设 $x$ 为新教师所需的培训日天数。设 $y$ 为中层领导所需的培训日天数。设 $z$ 为高级领导所需的培训日天数。

(a) 将此信息表述为一个线性规划问题。说明目标函数，并将约束条件列为具有整数系数的简化不等式。

(6)

学校决定，中层领导的培训日天数与高级领导的培训日天数之比应为 5:3。

这将其中两个约束条件简化为 $5x \le 16y$ 和 $4y \le 5x$ 。

(b) (i) 将代表总共至少 20 天培训日要求的约束条件，表示为仅含 $x$ 和 $y$ 且具有整数系数的简化不等式。

(ii) 将目标函数表示为 $ax + by$ 的形式，其中 $a$ 和 $b$ 为整数。

(3)

(4)

(d) 使用目标函数线方法确定可行区域的最优顶点 $V$ 。你必须清楚画出目标函数线并标记最优顶点 $V$ 。

(3)

(e) 由此，确定：

(i) 开办培训日的总成本，

(ii) 高级领导所需的培训日天数。

(2)

（总分 18 分）

解答

(a)

解法一

思路

展开

把三类培训日的每日费用乘以对应天数，得到需要最小化的总成本。三条文字约束分别对应总天数下界、新教师天数上界以及高级领导所占比例上界；百分比约束需要移项，化成整数系数不等式。

答题过程

展开

The objective is to

\boxed{\begin{aligned} &\,\text{minimise }C\\[4mm] &\,=400x+550y+750z \end{aligned}}.

The total number of training days gives

x+y+z\geq20.

There may be at most twice as many days for new teachers as for the other two groups combined, so

x\leq2(y+z).

At most $25\%$ of all training days may be for senior leaders. Hence

\begin{align*} z\leq&\,\frac14(x+y+z) \\[4mm] 4z\leq&\,x+y+z \\[4mm] 3z\leq&\,x+y. \end{align*}

Thus the constraints are

\boxed{ \begin{aligned} x+y+z&\geq20, \\ x&\leq2y+2z, \\ 3z&\leq x+y, \\ x,y,z&\geq0, \end{aligned}}

where $x,y,z$ are integers.

(b)(i)

解法一

思路

展开

比例 $y:z=5:3$ 等价于 $3y=5z$ ，所以 $z=3y/5$ 。把它代入总天数约束，再乘以 5 清除分母。

答题过程

展开

Since $y:z=5:3$ ,

3y=5z,

z=\frac35y.

Substituting into $x+y+z\geq20$ gives

x+y+\frac35y\geq20.

Multiplying by $5$ gives

\boxed{5x+8y\geq100}.

(b)(ii)

解法一

思路

展开

同样把 $z=3y/5$ 代入原目标函数，合并两个关于 $y$ 的成本项。

答题过程

展开

The objective becomes

\begin{align*} &\,C=400x+550y\\[4mm] &\,\hspace{2pt}+750\bigg(\frac35y\bigg)\\[4mm] &\,=400x+550y+450y\\[4mm] &\,=\boxed{400x+1000y}. \end{align*}

(c)

解法一

思路

展开

画出三条边界线 $5x+8y=100$ 、 $4y=5x$ 、 $5x=16y$ 。分别用轴截距或给定点定位直线，再根据不等号方向保留位于总数边界上方、同时夹在两条过原点直线之间的区域，并明确标记为 $R$ 。

答题过程

展开

Draw the following boundary lines:

Boundary	Two points on the line	Required side
$5x+8y=100$	$(0,12.5)$ and $(20,0)$	$5x+8y\geq100$
$4y=5x$	$(0,0)$ and $(10,12.5)$	$4y\leq5x$
$5x=16y$	$(0,0)$ and $(20,6.25)$	$5x\leq16y$

The feasible region is the unbounded region above $5x+8y=100$ and between the two lines through the origin. Label this region $R$ .

(d)

解法一

思路

展开

目标线可约成 $2x+5y=k$ 。先画一条具有正确斜率的目标线，再向原点方向平行移动以减小成本；它最后接触可行域的位置是 $5x+8y=100$ 与 $5x=16y$ 的交点。

答题过程

展开

An objective line has the form

400x+1000y=C,

or equivalently

2x+5y=k.

For example, draw $2x+5y=20$ , which passes through $(10,0)$ and $(0,4)$ . Moving this line parallel towards the origin, the last point of contact with $R$ is the intersection of

5x+8y=100

and

5x=16y.

Since $5x=16y$ , substitution gives

16y+8y=100,

y=\frac{25}{6},\qquad x=\frac{40}{3}.

Therefore label the continuous optimal vertex

\boxed{V=\bigg(\frac{40}{3},\frac{25}{6}\bigg)}.

The completed graph, including the objective line and $V$ , is:

(e)(i)

解法一

思路

展开

培训日数必须为整数，且 $y:z=5:3$ ，所以写成 $y=5k,z=3k$ 。先考虑 $k=1$ ，即 $y=5,z=3$ ；由总天数约束取成本最低的最小整数 $x=12$ ，费用为 9800 英镑。再检查 $k\geq2$ ：仅中层和高级领导的费用就至少为 10000 英镑，因此这些比例不可能得到更低费用。

答题过程

展开

Because the numbers of training days are integers and $y:z=5:3$ , write

y=5k,\qquad z=3k

for a positive integer $k$ . First consider $k=1$ , giving $y=5$ and $z=3$ .

The total-days constraint then requires

x+5+3\geq20,

so $x\geq12$ . The other constraints allow $x=12$ , and since its coefficient in the objective is positive, the minimum occurs at $x=12$ .

Therefore the minimum total cost is

\begin{align*} &\,C=400(12)+550(5)\\[4mm] &\,\hspace{2pt}+750(3)\\[4mm] &\,=4800+2750+2250\\[4mm] &\,=\pounds9800. \end{align*}

For any integer $k\geq2$ , the cost of the middle and senior leaders’ training days alone is

\begin{align*} &\,550(5k)+750(3k)\\[4mm] &\,=5000k\geq10000>9800. \end{align*}

Adding the non-negative cost of the new teachers’ training days cannot reduce this amount, so no such value of $k$ gives a cheaper solution.

Hence the total cost is

\boxed{\pounds9800}.

(e)(ii)

解法一

思路

展开

由 (e)(i) 的最优整数方案 $y=5,z=3$ ，直接读取高级领导对应的变量 $z$ 。

答题过程

展开

The optimal integer solution is

\begin{align*} x=&\,12,\\[4mm] y=&\,5,\\[4mm] z=&\,3. \end{align*}

Therefore the number of training days required for senior leaders is

\boxed{3}.

D1 2020 Jan Q7

题目

解答

(a)

解法一

思路

答题过程

(b)(i)

解法一

思路

答题过程

(b)(ii)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程

(e)(i)

解法一

思路

答题过程

(e)(ii)

解法一

思路

答题过程