Finding the Optimal Solution (Edexcel International A Level Maths): Revision Note

Objective Line

What is the objective line?

• The objective function (for an LP problem with two decision variables) is of the form 

  • Rearranged, this is of the form ''

  • So for a particular value of , there is a straight line graph

    • This is the objective line

How does an objective line indicate where the optimal solution is?

• In a linear programming problem,  is usually unknown

  • It is the quantity that is to be maximised or minimised

• In maximisation problems, increasing the value of

  • 'moves' the objective line away from the origin

  • and towards the upper boundaries of the feasible region

• In minimisation problems, decreasing the value of 

  • 'moves' the objective line closer to the origin

  • and towards the lower boundaries of the feasible region

• Therefore, the optimal solution to a linear programming problem occurs

  • when an objective line passes through a vertex of the feasible region

• The vertex at which this occurs will depend on the gradient of the objective line

How do I find the optimal solution to a linear programming problem using an objective line?

• Whether maximising or minimising, for the objective function 

  • Choose a value of that is a multiple of and 

  • Plot the objective line

    • This is usually easiest by considering the two points where and where 

  • Using your ruler, keep it parallel to the objective line just drawn

    • Move it away from the origin for a maximisation problem

    • Move it towards the origin for a minimisation problem

  • The last vertex of the feasible region that your ruler passes through will be the optimal solution to the problem

Vertex Method

What is the vertex method?

• The vertex method is a way to find the optimal solution to a linear programming problem

• The optimal solution to a linear programming problem lies on a vertex of the feasible region

• By finding the coordinates of these vertices, the decision variables values can be deduced

• The maximum or minimum objective function can be determined

  • by substituting each of these sets of decision variables into the objective function

How do I find the optimal solution from the vertex method?

• STEP 1
  Find the coordinates of each vertex of the feasible region

  • If the plot of the region is accurate, these may be able to be read directly from the graph

  • On less accurate diagrams, some vertices may be obvious

    • such as the origin or any vertices along an axis

  • Otherwise find the vertices by solving each pair of the inequalities as simultaneous equations

    • E.g. For the inequalities  and 

    • Solve the simultaneous equations  and 

• STEP 2
  Substitute the coordinates of each vertex into the objective function and evaluate it

• STEP 3
  Determine which set of decision variables lead to the maximum or minimum objective function as required by the problem

  • This will be the optimal solution