CVP and linear programming - Linear programming formulation ...

Learning Outcomes

After reading this article, you will be able to formulate linear programming problems for CVP analysis, construct graphical representations of constraints and objectives, identify feasible regions, and determine the optimal solution for two-variable resource allocation situations. You will gain the ability to interpret linear programming graphs and apply these techniques to maximise or minimise a quantitative objective, as required in the ACCA Performance Management exam.

ACCA Performance Management (PM) Syllabus

For ACCA Performance Management (PM), you are required to understand linear programming formulation and graphical solution as part of planning under scarcity. This article addresses the following syllabus points:

• Identify situations with multiple limiting factors where linear programming is appropriate
• Formulate linear programming models with an objective function and relevant constraints
• Construct and interpret linear programming graphs for problems with two variables
• Determine and interpret feasible regions and optimal solutions graphically
• Solve graphical linear programming problems to maximise or minimise an objective such as contribution or cost
• Recognise and calculate slack and shadow prices from a graphical solution

Test Your Knowledge

Attempt these questions before reading this article. If you find some difficult or cannot remember the answers, remember to look more closely at that area during your revision.

1. Which of the following is the main purpose of the feasible region in linear programming?
   1. To represent all possible combinations of products
   2. To identify profit for each combination
   3. To indicate the set of solutions which satisfy all constraints
   4. To show only the minimum cost solution
2. When graphing a constraint such as 4x+6y≤604x + 6y \leq 604x+6y≤60, what does the region below the line represent?
   1. Infeasible solutions
   2. All combinations using more than 60 resources
   3. All combinations using no more than 60 resources
   4. Only the maximum profit combinations

3. True or false? The optimal solution to a linear programming problem always lies at a corner (vertex) of the feasible region.

4. Explain what is meant by an iso-contribution (objective) line in the context of linear programming.

5. What does slack represent in a resource constraint on a linear programming graph?

Introduction

Linear programming is a mathematical technique used to find the most profitable or cost-efficient combination of activities when dealing with multiple limiting factors. In the ACCA PM exam, you may be required to formulate a linear programming problem and use graphical methods to find the optimal production plan.

Key Term: linear programming
A quantitative technique for optimising (maximising or minimising) a linear objective function, subject to a set of linear constraints.

FORMULATING A LINEAR PROGRAMMING PROBLEM

The key steps in any linear programming problem are as follows:

Step 1: Define the Decision Variables

Identify the unknowns to be determined. For example, let $x$ = number of units of Product X, $y$ = number of units of Product Y.

Key Term: decision variable
A symbolic representation (typically $x$, $y$) of the unknown quantities to be optimised.

Key Term: objective function
The linear expression to be maximised (e.g., total contribution) or minimised (e.g., total cost).

Step 2: State the Objective Function

Clearly specify the aim of the problem (maximise contribution or minimise cost, etc.) in terms of the decision variables.

Example: Maximise contribution $C = 4x + 6y$

Step 3: Formulate the Constraints

Write linear inequalities to reflect all restrictions faced (e.g., resource or market constraints).

Example constraints:

• Labour hours: $2x + 5y \leq 60$
• Materials: $4x + 3y \leq 48$
• Non-negativity: $x \geq 0, y \geq 0$
• Maximum demand: $y \leq 10$

Key Term: constraint
A linear restriction on the values of the decision variables, representing limited resource or market conditions.

GRAPHICAL SOLUTION TO A LINEAR PROGRAMMING PROBLEM

Linear programming problems involving two variables can be solved using a graph. The solution proceeds as follows:

Step 1: Draw the Constraint Lines

Each constraint is drawn as a straight line on a graph, with one variable on each axis. Find two points to plot each constraint by setting variables to zero in turn.

For $2x + 5y \leq 60$:
If $x = 0$, $y = 12$.
If $y = 0$, $x = 30$.

Step 2: Identify the Feasible Region

Key Term: feasible region
The set of all points on the graph that simultaneously satisfy all constraints; these are the possible solutions.

Shade or mark the area on the graph that fulfils all constraints. Only points inside this region are valid solutions.

Step 3: Draw the Objective (Iso-Contribution) Line

To find the optimal solution, draw a line representing a given value of the objective function (an iso-contribution line):

For example: $C = 4x + 6y = 24$

Plot at least two points for this line (e.g., $x = 0, y = 4$; $y = 0, x = 6$), draw the line, and note that all such lines are parallel.

Key Term: iso-contribution line
A line on a graph where every point yields the same value for the objective function (e.g., same total contribution).

Step 4: Find the Optimal Solution at a Vertice (Corner Point)

Slide the iso-contribution (objective) line as far as possible in the direction of increasing the objective (upwards/right for maximisation) without leaving the feasible region. The last point it touches within the feasible region is the optimal solution.

Key Term: optimal solution
The specific values for each decision variable that provide the highest or lowest value for the objective function while respecting all constraints.

Worked Example 1.1

A manufacturer produces two products, Alpha and Beta. The contribution per unit is $6 and $9, respectively. Each Alpha requires 2 hours of labour and 1 kg of material. Each Beta requires 1 hour of labour and 3 kg of material. Each week, there are 16 hours of labour and 18 kg of material available. Market demand limits Alpha to a maximum of 6 units per week and Beta to 5 units per week. How should the manufacturer allocate resources to maximise total contribution?

Answer:

1. Let $x$ be Alpha units, $y$ Beta units.
2. Objective: Maximise $C = 6x + 9y$
3. Constraints:
   • Labour: $2x + y \leq 16$
   • Material: $x + 3y \leq 18$
   • Market: $x \leq 6$, $y \leq 5$
   • Non-negativity: $x, y \geq 0$

Draw all above as lines on a graph.

• Feasible region bounded by all constraints.
• Draw iso-contribution line and move it as far as possible in feasible region.
• Compare intersections to determine which yields the highest $C$.
• Suppose at intersection $x = 3$, $y = 5$: test if this is within all constraints.
• $2(3) + 5 = 6 + 5 = 11 \leq 16$ ✓
• $3 + 3(5) = 3 + 15 = 18 \leq 18$ ✓
• Both within market constraints.
• Substituting, $C = 6(3) + 9(5) = 18 + 45 = 63$.

The manufacturer should make 3 Alpha and 5 Beta per week for a maximum contribution of $63.

Exam Warning

In linear programming graphical questions, never select a point inside the feasible region unless it lies at a corner (vertex); optimal solutions always occur at a vertex.

SLACK, SHADOW PRICES AND INTERPRETING GRAPHICAL SOLUTIONS

Slack

Key Term: slack
The amount by which a constraint is not binding at the optimal solution—i.e., unused resource.

If, at the optimal point, one or more constraints are not fully utilised, the problem is said to have slack for those resources.

Shadow Price

Key Term: shadow price
The improvement in the objective function (e.g., contribution) for one more unit of a scarce resource, keeping all other data constant.

Shadow price can be read from the change in optimum value when a constraint is relaxed by one unit.

Worked Example 1.2

At the optimal point in the previous example, only 16 hours of labour and 18 kg of material are available, and the solution is 3 Alpha and 5 Beta. If the manufacturer obtains 1 extra unit of labour, by how much does the total contribution increase?

Answer:

Plot both the current and new feasible regions. Find the new optimal point by increasing the right-hand side of the labour constraint to 17. Calculate the corresponding new solution. The shadow price is the difference in contribution between the two optimal points.

Revision Tip

Always label axes, constraints, the feasible region, and iso-contribution lines clearly on your sketch. This maximises clarity in the exam and supports interpretation questions.

Summary

Linear programming provides a structured approach to finding the optimal allocation of scarce resources, subject to multiple constraints. The graphical method is suitable for problems with two variables, allowing you to identify the feasible region, apply the objective function, and determine the best production plan at a constraint vertex. Understanding slack and shadow price helps interpret managerial implications of changing resources.

Key Point Checklist

This article has covered the following key knowledge points:

• Steps for formulating linear programming problems: define variables, objective function, and constraints
• Drawing and interpreting constraints and feasible regions on a graph
• Using iso-contribution/objective lines to determine optimal solutions
• Identifying the optimal solution at a feasible region vertex
• Meaning and implications of slack and shadow prices in a resource constraint
• Importance of careful, stepwise working and clear graph labelling in the exam

Key Terms and Concepts

• linear programming
• decision variable
• objective function
• constraint
• feasible region
• iso-contribution line
• optimal solution
• slack
• shadow price