题目

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$ 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)

解答

(a)

解法一

思路

展开

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

答题过程

展开

The objective is to

\boxed{\text{minimise }C=400x+550y+750z}.

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{aligned} z\leq&\,\frac14(x+y+z) \\ 4z\leq&\,x+y+z \\ 3z\leq&\,x+y. \end{aligned}

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{aligned} C=&\,400x+550y+750\bigg(\frac35y\bigg) \\ =&\,400x+550y+450y \\ =&\,\boxed{400x+1000y}. \end{aligned}

(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$ 。

答题过程

展开

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

y=5k,\qquad z=3k

for a positive integer $k$ . The least feasible choice near $V$ is $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{aligned} C=&\,400(12)+550(5)+750(3) \\ =&\,4800+2750+2250 \\ =&\,\pounds9800. \end{aligned}

Hence the total cost is

\boxed{\pounds9800}.

(e)(ii)

解法一

思路

展开

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

答题过程

展开

The optimal integer solution is

x=12,\qquad y=5,\qquad z=3.

Therefore the number of training days required for senior leaders is

\boxed{3}.

IAL 2020 Jan D1 Q7

题目

解答

(a)

解法一

思路

答题过程

(b)(i)

解法一

思路

答题过程

(b)(ii)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程

(e)(i)

解法一

思路

答题过程

(e)(ii)

解法一

思路

答题过程