Formulating linear programs

Formulating linear programs

Spec 5.1 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A linear program has decision variables, an objective function and constraints.
  • Include non-negativity conditions: x≥0x\ge0, y≥0y\ge0.
  • "At most" gives ≤\le, "at least" gives ≥\ge and "exactly" gives ==.
  • Add a slack variable to ≤\le, subtract a surplus variable from ≥\ge and add an artificial variable to ≥\ge and ==.
  • Write the objective as P−3x−5y=0P-3x-5y=0 ready for the tableau.

Building a linear program

A linear program has decision variables, a linear objective to maximise or minimise, and linear constraints including non-negativity.

  • Decision variables: what you choose, such as xx tables and yy chairs per week, with units.
  • Objective function: the linear expression to maximise (profit) or minimise (cost).
  • Constraints: linear inequalities from limited resources or requirements, plus non-negativity x≥0x\ge0, y≥0y\ge0.

Translate words carefully. Write each variable's meaning and units first, so every coefficient has a unit you can check.

1234567824681012xy(0, 10)(6.67, 0)3x + 2y = 20
The constraint 3x + 2y ≤ 20: the shaded region below the line is allowed (with x, y ≥ 0).

At most

Wording:
no more than
Wording:
limited to

At least

Wording:
no fewer than
Wording:
a minimum of

Exactly

Wording:
equal to
Wording:
precisely

Worked example

Profit is £30 per table and £20 per chair, and cutting time (3 hours per table, 2 per chair) is at most 20 hours. Formulate the problem.

Which inequality represents "at least 5 units in total" for x+yx+y?

Slack variables

A slack variable is the unused amount of a resource. Add one to each ≤\le constraint to make it an equation.

To use the Simplex algorithm every constraint must be an equation. For a ≤\le constraint add a slack variable, the unused amount:

3x+2y≤20⇒3x+2y+s1=20,s1≥0.3x+2y\le20\quad\Rightarrow\quad3x+2y+s_1=20,\quad s_1\ge0.

If x=4x=4 and y=3y=3 then s1=20−12−6=2s_1=20-12-6=2: 2 hours are unused. If s1=0s_1=0 the constraint is binding.

At the origin each slack variable equals the right-hand side, giving a starting solution with the slack variables as the basic variables.

1234567824681012xy(4, 4): s₁ = 0(0, 10)3x + 2y + s₁ = 20
Below the line there is slack: at (4, 3) the time used is 18, so s₁ = 2 hours. On the line, as at (4, 4), s₁ = 0 and the constraint is binding.
  • 3x+2y≤203x+2y\le203x+2y+s1=203x+2y+s_1=20

For 2x+y≤92x+y\le9 with x=3x=3 and y=1y=1, what is the slack variable ss?

Surplus variables

A surplus variable is the amount over a minimum requirement. Subtract one from each ≥\ge constraint.

For a ≥\ge constraint the left-hand side exceeds the requirement, so subtract a surplus variable:

x+y≥5⇒x+y−s3=5,s3≥0.x+y\ge5\quad\Rightarrow\quad x+y-s_3=5,\quad s_3\ge0.

If x=4x=4 and y=3y=3 then s3=7−5=2s_3=7-5=2: 2 units more than the minimum.

At the origin the equation gives −s3=5-s_3=5, which is impossible because s3≥0s_3\ge0. So a surplus variable alone cannot give a starting solution.

12345678246810xy(3, 2): s₃ = 0(5, 0)x + y = 5
The constraint x + y ≥ 5: the shaded region on or above the line is allowed. At (4, 3), x + y = 7 so s₃ = 2; on the line, as at (3, 2), s₃ = 0.
  • x+y≥5x+y\ge5x+y−s3=5x+y-s_3=5

For x+2y≥8x+2y\ge8 with x=2x=2 and y=5y=5, what is the surplus variable?

Artificial variables

A surplus variable cannot give a starting solution, so add an artificial variable to ≥\ge and == constraints.

Add an artificial variable t1≥0t_1\ge0 to a ≥\ge constraint (and to an == constraint):

x+y−s3+t1=5.x+y-s_3+t_1=5.

Now x=y=0x=y=0, s3=0s_3=0, t1=5t_1=5 is a basic feasible solution, so the algorithm can start.

An artificial variable has no meaning in the real problem. A valid final answer must have t1=0t_1=0. The two-stage and big-M methods remove them.

  1. 1

    Subtract a surplus variable

    x + y − s₃ = 5

  2. 2

    At the origin

    −s₃ = 5 is impossible, since s₃ ≥ 0

  3. 3

    Add an artificial variable

    x + y − s₃ + t₁ = 5, so t₁ = 5 starts the algorithm

  4. 4

    Remove it again

    a valid final answer has t₁ = 0

Why a ≥ constraint needs an artificial variable.

≤\le

Add:
slack variable
Why:
Origin is a valid start

≥\ge

Add:
surplus and artificial
Why:
Surplus alone is negative at the origin

==

Add:
artificial only
Why:
Needs a starting basic variable

How many extra variables does x+y≥5x+y\ge5 need?

A worked formulation

Write each constraint, the objective and the extra variables, then check by substitution.

A company makes xx standard and yy deluxe boxes. Packing takes 4 and 6 minutes (at most 240 minutes). Ribbon use is 2 m and 5 m (at most 150 m). At least 10 boxes are made. Profit is £3 and £5 per box.

Count your extra variables: one per constraint, plus one artificial for each ≥\ge or ==.

Check: with x=20x=20, y=10y=10, s1=120−70=50s_1=120-70=50, s2=150−90=60s_2=150-90=60 and s3=30−10=20s_3=30-10=20 with t1=0t_1=0.

102030405060708010203040xy(37.5, 15)(0, 30)(60, 0)packingribbontotal ≥ 10
The three constraints for the boxes: packing 2x + 3y = 120, ribbon 2x + 5y = 150, total x + y = 10. Packing and ribbon meet at (37.5, 15).
  • Packing2x+3y≤1202x+3y\le120
  • Ribbon2x+5y≤1502x+5y\le150
  • Total boxesx+y≥10x+y\ge10

Worked example

Formulate as a linear program and write it with extra variables.

How many extra variables are needed in total for this problem?

Try an exam question

A factory makes xx standard and yy premium chairs per day. Each standard chair needs 2 hours of sanding and each premium chair 3 hours, with at most 48 hours available. At least 6 chairs must be made in total. Profit is £20 per standard and £35 per premium chair. Formulate this as a linear program, writing each constraint as an equation with slack, surplus and artificial variables as needed.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which inequality represents the cutting-time constraint?

1 mark, marked against the mark scheme

Revision notes