Formulating linear programs
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: , .
- "At most" gives , "at least" gives and "exactly" gives .
- Add a slack variable to , subtract a surplus variable from and add an artificial variable to and .
- Write the objective as 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 tables and 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 , .
Translate words carefully. Write each variable's meaning and units first, so every coefficient has a unit you can check.
| At most | At least | Exactly | |
|---|---|---|---|
| Wording | no more than | no fewer than | equal to |
| Wording | limited to | a minimum of | precisely |
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.
- 1
Define = tables and = chairs per week.
- 2
Cutting time used is , at most 20, so .
- 3
Add non-negativity: , .
- 4
The objective is to maximise profit .
Which inequality represents "at least 5 units in total" for ?
Slack variables
A slack variable is the unused amount of a resource. Add one to each constraint to make it an equation.
To use the Simplex algorithm every constraint must be an equation. For a constraint add a slack variable, the unused amount:
If and then : 2 hours are unused. If 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.
For with and , what is the slack variable ?
Surplus variables
A surplus variable is the amount over a minimum requirement. Subtract one from each constraint.
For a constraint the left-hand side exceeds the requirement, so subtract a surplus variable:
If and then : 2 units more than the minimum.
At the origin the equation gives , which is impossible because . So a surplus variable alone cannot give a starting solution.
For with and , what is the surplus variable?
Artificial variables
A surplus variable cannot give a starting solution, so add an artificial variable to and constraints.
Add an artificial variable to a constraint (and to an constraint):
Now , , 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 . The two-stage and big-M methods remove them.
- 1
Subtract a surplus variable
x + y − s₃ = 5
- 2
At the origin
−s₃ = 5 is impossible, since s₃ ≥ 0
- 3
Add an artificial variable
x + y − s₃ + t₁ = 5, so t₁ = 5 starts the algorithm
- 4
Remove it again
a valid final answer has t₁ = 0
| Add | slack variable | surplus and artificial | artificial only |
|---|---|---|---|
| Why | Origin is a valid start | Surplus alone is negative at the origin | Needs a starting basic variable |
- Add:
- slack variable
- Why:
- Origin is a valid start
- 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 need?
A worked formulation
Write each constraint, the objective and the extra variables, then check by substitution.
A company makes standard and 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 or .
Check: with , , , and with .
- Packing
- Ribbon
- Total boxes
Worked example
Formulate as a linear program and write it with extra variables.
- 1
Packing: , which simplifies to .
- 2
Ribbon: . Total: . Also .
- 3
Objective: maximise .
- 4
Add and to the first two; subtract and add in the third.
- 5
Rewrite the objective as .
How many extra variables are needed in total for this problem?
Try an exam question
A factory makes standard and 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]
- [1]Objective: maximise , written .
- [1]Sanding: becomes .
- [1]Total chairs: becomes .
- [1]Non-negativity: , with .
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
Which inequality represents the cutting-time constraint?
1 mark, marked against the mark scheme