How is a \le constraint made into an equation?

Add a slack variable: 3x+2y\le20\to3x+2y+s1=20.

What does a slack variable represent?

The unused amount of a resource.

What does a slack variable of 0 mean?

The constraint is binding: the resource is fully used.

How is a \ge constraint made into an equation?

Subtract a surplus variable: x+y\ge5\to x+y-s=5.

What does a surplus variable represent?

The amount by which the requirement is exceeded.

Why is an artificial variable needed?

A surplus variable alone gives -s=5 at the origin, so there is no starting basic feasible solution; t1 provides one.

Formulating linear programsEdexcel A-Level Further Maths: Flashcards

Card 1 of 130 of 13 known

Question

What are the three parts of a linear program?

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

What are the three parts of a linear program?: Decision variables, an objective function to maximise or minimise, and linear constraints (with non-negativity).
What does 'at most' translate to?: $\le$
What does 'at least' translate to?: $\ge$
How is a $\le$ constraint made into an equation?: Add a slack variable: $3x+2y\le20\to3x+2y+s_1=20$ .
What does a slack variable represent?: The unused amount of a resource.
What does a slack variable of 0 mean?: The constraint is binding: the resource is fully used.
How is a $\ge$ constraint made into an equation?: Subtract a surplus variable: $x+y\ge5\to x+y-s=5$ .
What does a surplus variable represent?: The amount by which the requirement is exceeded.
Why is an artificial variable needed?: A surplus variable alone gives $-s=5$ at the origin, so there is no starting basic feasible solution; $t_1$ provides one.
Write $x+y\ge5$ with surplus $s_3$ and artificial $t_1$ .: $x+y-s_3+t_1=5$
Which constraint types get an artificial variable?: $\ge$ and $=$ constraints.
What must an artificial variable equal in a genuine solution?: Zero.
Rewrite the objective $P=3x+5y$ for a Simplex tableau.: $P-3x-5y=0$

Exam questions on Formulating linear programs

A workshop makes $x$ tables and $y$ chairs each week. Each table needs 3 hours of cutting time and each chair needs 2 hours. There are at most 20 hours of cutting time available each week.
Find the value of $s_1$ when $x=4$ and $y=3$ , and state what it represents in context.2 marks
A farmer mixes $x$ kg of feed A and $y$ kg of feed B. Each kilogram of either feed supplies 1 unit of a vitamin, and the mixture must supply at least 5 units of the vitamin in total.
An artificial variable $t_1$ is also added to this constraint. Write down the equation and explain why $t_1$ is needed.2 marks
A company makes $x$ standard gift boxes and $y$ deluxe gift boxes each day. A standard box needs 4 minutes of packing and 2 metres of ribbon; a deluxe box needs 6 minutes of packing and 5 metres of ribbon. Each day there are 240 minutes of packing time and 150 metres of ribbon available, and at least 10 boxes must be made. Profit is £3 per standard box and £5 per deluxe box. The company wishes to maximise its daily profit $P$ (in pounds).
Formulate this situation as a linear programming problem.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).