题目

Problem

Martin is making three types of cake for a picnic. The three types of cake are carrot cake, apple cake and chocolate cake. Along with other ingredients,

each carrot cake contains 275 grams of flour, 300 grams of sugar and 5 eggs
each apple cake contains 200 grams of flour, 400 grams of sugar and 2 eggs
each chocolate cake contains 100 grams of flour, 400 grams of sugar and 3 eggs

If Martin makes only one type of cake then he has enough time to prepare 15 carrot cakes or 20 apple cakes or 30 chocolate cakes.

Martin has 5.5 kilograms of flour and 70 eggs available and he has promised the picnic organisers that he will make at least 18 cakes in total.

Martin plans to make a selection of these cakes and wants to minimise the total amount of sugar that he uses.

Let $x$ be the number of carrot cakes made, $y$ the number of apple cakes made and $z$ the number of chocolate cakes made.

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

(6)

A further constraint is that $y = 2z$ .

(b) Explain what this constraint means in the context of the question.

(1)

The constraint $y = 2z$ reduces the problem to the following:

Minimise $P = 300x + 600y$

subject to

$11x + 10y \leq 220$ $10x + 7y \leq 140$ $x + y \leq 15$ $2x + 3y \geq 36$ $x \geq 0, \quad y \geq 0$

(4)

(d) Use the objective line method to find the optimal number of each type of cake that Martin should make, and the amount of sugar used.

(4)

(e) Determine how much flour and how many eggs Martin will have left over after making the optimal number of cakes.

(2)

题目中文翻译

Martin 正在为野餐制作三种类型的蛋糕。三种蛋糕分别是胡萝卜蛋糕、苹果蛋糕和巧克力蛋糕。除其他配料外，

每个胡萝卜蛋糕含有 275 克面粉、300 克糖和 5 个鸡蛋
每个苹果蛋糕含有 200 克面粉、400 克糖和 2 个鸡蛋
每个巧克力蛋糕含有 100 克面粉、400 克糖和 3 个鸡蛋

如果 Martin 只制作一种蛋糕，他有足够的时间准备 15 个胡萝卜蛋糕或 20 个苹果蛋糕或 30 个巧克力蛋糕。

Martin 有 5.5 千克面粉和 70 个鸡蛋可用，他已经向野餐组织者承诺总共至少制作 18 个蛋糕。

Martin 计划制作这些蛋糕的一种选择，并希望最小化使用的糖总量。

设 $x$ 为制作的胡萝卜蛋糕数量， $y$ 为制作的苹果蛋糕数量， $z$ 为制作的巧克力蛋糕数量。

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

另一个约束是 $y = 2z$ 。

(b) 解释此约束在问题背景中的含义。

约束 $y = 2z$ 将问题简化为以下内容：

最小化 $P = 300x + 600y$

约束条件

$11x + 10y \leq 220$ $10x + 7y \leq 140$ $x + y \leq 15$ $2x + 3y \geq 36$ $x \geq 0, \quad y \geq 0$

(d) 使用目标线法找到 Martin 应该制作的每种蛋糕的最优数量以及使用的糖量。

(e) 确定 Martin 制作最优数量的蛋糕后剩余的面粉和鸡蛋数量。

解答

(a)

解法一

思路

展开

目标是使糖的总用量最小。面粉、鸡蛋和准备时间都是资源上限，所以写成不超过型约束；蛋糕总数至少为 18，写成不小于型约束。时间约束由“只做某一种时最多可做的数量”写成各类型占用时间比例之和不超过 1，再化成整数系数。

答题过程

展开

The objective is

\boxed{\text{Minimise }P=300x+400y+400z}.

The flour constraint is

275x+200y+100z\leq 5500,

or, equivalently,

11x+8y+4z\leq 220.

The egg constraint is

5x+2y+3z\leq 70.

The preparation-time constraint is

\frac{x}{15}+\frac{y}{20}+\frac{z}{30}\leq 1,

which becomes

4x+3y+2z\leq 60.

The remaining constraints are

x+y+z\geq 18

and

x\geq 0,\qquad y\geq 0,\qquad z\geq 0.

(b)

解法一

思路

展开

等式 $y=2z$ 表示苹果蛋糕数量恰好是巧克力蛋糕数量的两倍；不能解释成“至少”或“至多”。

答题过程

展开

Martin makes twice as many apple cakes as chocolate cakes. Equivalently, apple cakes and chocolate cakes are made in the ratio

\boxed{2:1}.

(c)

解法一

思路

展开

把四条约束的边界直线画满坐标轴范围，并根据不等号判断各自允许的一侧。前三条约束取直线下方， $2x+3y\geq36$ 取直线上方；再与第一象限相交并标记为 $R$ 。

答题过程

展开

The boundary-line intercepts are:

Boundary	$x$ -intercept	$y$ -intercept	Required side
$11x+10y=220$	20	22	Below
$10x+7y=140$	14	20	Below
$x+y=15$	15	15	Below
$2x+3y=36$	18	12	Above

Together with $x\geq0$ and $y\geq0$ , these half-planes define the feasible region $R$ . The completed diagram, including the objective line used in part (d), is:

(d)

解法一

思路

展开

目标函数 $P=300x+600y$ 的等值线斜率为 $-\frac12$ 。将目标线平行地向原点方向移动，最后接触可行域的位置是 $x+y=15$ 与 $2x+3y=36$ 的交点。求得 $x,y$ 后，再用 $y=2z$ 求 $z$ 。

答题过程

展开

An objective line has equation

300x+600y=P,

so its gradient is $-\frac12$ . Moving this line towards the origin, the last point of contact with $R$ is the intersection of

x+y=15

and

2x+3y=36.

Since $2x+2y=30$ , subtraction gives $y=6$ , and hence $x=9$ . Also, $y=2z$ , so

z=3.

Thus Martin should make

\boxed{9\text{ carrot},\ 6\text{ apple and }3\text{ chocolate cakes}}.

The minimum amount of sugar is

300(9)+400(6)+400(3) =\boxed{6300\text{ g}}.

(e)

解法一

思路

展开

把最优数量 $x=9,y=6,z=3$ 分别代入面粉与鸡蛋用量，先算总消耗，再从现有的 5500 克面粉和 70 个鸡蛋中减去。

答题过程

展开

The amount of flour used is

275(9)+200(6)+100(3)=3975\text{ g}.

Therefore the flour remaining is

5500-3975=\boxed{1525\text{ g}}.

The number of eggs used is

5(9)+2(6)+3(3)=66.

Therefore the number of eggs remaining is

70-66=\boxed{4}.

IAL 2023 Jan D1 Q6

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程

(e)

解法一

思路

答题过程