题目

Problem

A bakery makes three types of doughnut. These are ring, jam and custard. The bakery has the following constraints on the number of doughnuts it must make each day.

The total number of doughnuts made must be at least 200
They must make at least three times as many ring doughnuts as jam doughnuts
At most 70% of the doughnuts the bakery makes must be ring doughnuts
At least a fifth of the doughnuts the bakery makes must be jam doughnuts

It costs 8 pence to make each ring doughnut, 10 pence to make each jam doughnut and 14 pence to make each custard doughnut. The bakery wants to minimise the total daily costs of making the required doughnuts.

Let $x$ represent the number of ring doughnuts, let $y$ represent the number of jam doughnuts and let $z$ represent the number of custard doughnuts the bakery makes each day.

(a) Formulate this as a linear programming problem stating the objective and listing the constraints as simplified inequalities with integer coefficients.

(6)

On a given day, instead of making at least 200 doughnuts, the bakery requires that exactly 200 doughnuts are made. Furthermore, the bakery decides to make the minimum number of jam doughnuts which satisfy all the remaining constraints.

Given that the bakery still wants to minimise the total cost of making the required doughnuts, use algebra to

(b) (i) calculate the number of each type of doughnut the bakery will make on that day,

(ii) calculate the corresponding total cost of making all the doughnuts.

(5)

(Total 11 marks)

题目中文翻译

一家面包店制作三种类型的甜甜圈：环形、果酱和奶油。面包店对每天必须制作的甜甜圈数量有以下约束。

制作的甜甜圈总数必须至少 200 个
环形甜甜圈必须至少是果酱甜甜圈的三倍
面包店制作的甜甜圈中最多 70% 必须是环形甜甜圈
面包店制作的甜甜圈中至少五分之一必须是果酱甜甜圈

制作每个环形甜甜圈成本为 8 便士，每个果酱甜甜圈为 10 便士，每个奶油甜甜圈为 14 便士。面包店希望最小化制作所需甜甜圈的每日总成本。

设 $x$ 表示环形甜甜圈数量， $y$ 表示果酱甜甜圈数量， $z$ 表示面包店每天制作的奶油甜甜圈数量。

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

(6)

在某一天，面包店要求恰好制作 200 个甜甜圈，而不是至少 200 个。此外，面包店决定制作满足所有剩余约束的最少数量的果酱甜甜圈。

已知面包店仍然希望最小化制作所需甜甜圈的总成本，使用代数方法

(b) (i) 计算面包店当天将制作的每种甜甜圈的数量，

(ii) 计算制作所有甜甜圈的相应总成本。

(5)

（总分 11 分）

解答

(a)

解法一

思路

展开

先用三种甜甜圈的单位成本写出目标函数，再逐句翻译约束。两个百分比条件先以总数 $x+y+z$ 表示，随后展开并整理成整数系数不等式。

答题过程

展开

Let $P$ be the total daily cost in pence. The objective is

\boxed{\begin{aligned} &\,\text{minimise }P\\[4mm] =&\,8x+10y+14z \end{aligned}}.

The total number of doughnuts must be at least $200$ , so

x+y+z\geq200.

There must be at least three times as many ring doughnuts as jam doughnuts, so

x\geq3y.

At most $70\%$ may be ring doughnuts. Therefore

x\leq\frac{7}{10}(x+y+z).

Multiplying by $10$ and simplifying gives

3x\leq7y+7z.

At least one fifth must be jam doughnuts, so

y\geq\frac15(x+y+z).

Multiplying by $5$ and simplifying gives

x+z\leq4y.

Hence the constraints, with integer coefficients, are

\boxed{\begin{aligned} x+y+z\geq&\,200,\\ x\geq&\,3y,\\ 3x\leq&\,7y+7z,\\ x+z\leq&\,4y,\\ x,y,z\geq&\,0. \end{aligned}}

In context, $x$ , $y$ and $z$ are integers.

(b)(i)

解法一

思路

展开

总数固定为 200 后，70% 与五分之一条件直接给出 $x\leq140$ 和 $y\geq40$ 。题目另外指定果酱甜甜圈取最少，因此先令 $y=40$ 。把 $z=200-x-y$ 代入成本函数后，可看出成本随 $x$ 增加而下降，所以在约束范围内取最大的 $x$ 。

答题过程

展开

Since exactly $200$ doughnuts are made,

x+y+z=200.

The percentage constraints give

x\leq\frac{7}{10}(200)=140

and

y\geq\frac15(200)=40.

The bakery chooses the minimum possible number of jam doughnuts, so

y=40.

Also,

\begin{align*} z=&\,200-x-y\\[4mm] =&\,160-x. \end{align*}

Substituting into the cost function,

\begin{align*} P=&\,8x+10(40)\\[4mm] &\,\hspace{2pt}+14(160-x)\\[4mm] =&\,2640-6x. \end{align*}

Thus the cost is minimised by taking the greatest permitted value of $x$ , namely

x=140.

This also satisfies $x\geq3y$ , since $140\geq120$ . Finally,

z=200-140-40=20.

Therefore the bakery makes

\boxed{\begin{aligned} &\,140\text{ ring},\\[4mm] &\,40\text{ jam},\\[4mm] &\,20\text{ custard doughnuts} \end{aligned}}.

解法二

思路

展开

把取到边界的条件写成方程，再联立求解。总数恰为 200，果酱数量最少时五分之一的约束取等号。固定果酱数量后，环形比奶油便宜，把一个奶油换成环形会减少 6 便士，所以成本最低时环形数量达到七成的上限。将这两个边界方程与总数方程联立，最后检查其余约束。

答题过程

展开

The total number is exactly $200$ . To make the fewest jam doughnuts, take equality in $x+z\leq4y$ . With the number of jam doughnuts fixed, replacing a custard doughnut by a ring doughnut reduces the cost by $14-8=6$ pence. Thus the cheapest choice has as many ring doughnuts as permitted, giving equality in $3x\leq7y+7z$ .

The three simultaneous equations are therefore

\begin{align*} x-4y+z=&\,0, \\[4mm] 3x-7y-7z=&\,0, \\[4mm] x+y+z=&\,200. \end{align*}

Subtracting the first equation from the third gives

5y=200,

so $y=40$ . Hence $x+z=160$ , and the second equation becomes

\begin{align*} &\,3x-280-7z=0, \\[4mm] &\,3x-280 \\[4mm] &\,\hspace{2pt}-7(160-x)=0, \\[4mm] &\,10x-1400=0. \end{align*}

Therefore $x=140$ and $z=160-140=20$ . These numbers are non-negative integers and satisfy the remaining constraint, since $140\geq3(40)$ . Thus the bakery makes

\boxed{\begin{aligned} 140&\text{ ring doughnuts},\\ 40&\text{ jam doughnuts},\\ 20&\text{ custard doughnuts}. \end{aligned}}

(b)(ii)

解法一

思路

展开

把 (b)(i) 得到的三种数量代回成本函数。由于单价以便士给出，先得到总便士数，再换算为英镑。

答题过程

展开

The total cost is

\begin{align*} P=&\,8(140)+10(40)\\[4mm] &\,\hspace{2pt}+14(20)\\[4mm] =&\,1120+400+280\\ =&\,1800\text{ pence}. \end{align*}

Therefore the corresponding total cost is

\boxed{\pounds18}.

D1 2020 Oct Q8

题目

解答

(a)

解法一

思路

答题过程

(b)(i)

解法一

思路

答题过程

解法二

思路

答题过程

(b)(ii)

解法一

思路

答题过程