Solving a Linear Programming Problem Graphically (Edexcel A Level Further Maths): Revision Note

Introduction to Solving an LP Problem Graphically

How do I solve a linear programming problem graphically?

• For problems with two decision variables

  • the constraints (inequalities) are plotted accurately on a graph

  • this leads to the feasible region

  • the optimal solution will be one of the vertices of the feasible region

• In harder problems

  • there may be a third decision variable

    • but there will be a connection to one (or both) of the other decision variables such that all constraints can be rewritten in terms of just two of them

      e.g.

      are the numbers of chairs, tables and desks made by a furniture manufacturer but the number of desks produced is twice the number of tables (i.e.  )

  • the optimal solution may not give integer values for the decision variables but the context demands they are

    • e.g.  is it possible to make 3.65 chairs and 4.2 tables per day?

Feasible Region

What is the feasible region?

• Technically, the feasible region is the set of all values that satisfy all the constraints in a linear programming problem

• In practice, this is the area on a graph that satisfies all of the inequalities

  • including the non-negativity constraint/inequality

How do I find the feasible region?

• To find the feasible region

  • accurately plot each inequality (constraint) on a graph

    • plot each inequality as a straight line

      • rearranging to the form or  may help

      • but it can be easier to determine two points that lie on each line, plot and join them up

    • draw the line solid for inequalities involving ≤ or ≥, or dotted for inequalities involving > or <

      • (< and > are rare in linear programming problems)

  • shade the part of the graph not satisfied by each inequality

    • be careful with graphing software - these will often shade the part of the graph that does satisfiy an inequality

    • but it is easier to see a 'blank' area rather than an area shaded several times

    • a workaround to this is to reverse the inequality sign when typing the inequality into the software

  • the feasible region is the area on the graph left unshaded

    • it is the area that satisfies all of the inequalities

    • it is usually labelled with the capital letter 

• Label each inequality/line around the edge of the graph

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

• Similarly, in minimisation problems, decreasing the value of  'moves' the objective line closer to the origin and towards the lower boundaries of the feasible region

• It therefore follows that the optimal solution to a linear programming problem occurs when an objective line passes through a vertex of the feasible region

  • which vertex this is 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, and keeping it parallel to the objective line just drawn move it away (for maximisation) or towards (for minimisation) the origin

  • 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 values for the decision variables can be deduced

• Substituting each of these sets of decision variables into the objective function allows the maximum or minimum objective function to be determined

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

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

  • If an accurate plot of the region is provided or drawn, 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 (i.e. the decision variables) 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

Integer Solutions

What do we mean by integer solutions?

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

• The values of the decision variables at this vertex may not take integer values

• However the context of the problem may demand that the decision variables take integer values

  • Decision variables are often a 'number of things'

    • is it possible for the furniture manufacturer to make 3.65 chairs per day?

    • for public health reasons, it would not be appropriate for a food factory to leave a tin of beans partially produced overnight !

• This is what is meant by the phrase integer solutions

How do I find the integer solutions to a linear programming problem?

• Find the optimal solution of the linear programming problem as usual

  • using the objective line or vertex method

• Consider the four points with integer coordinates that surround the optimal solution

  • e.g.

    for an optimal solution of , the four surrounding points would be (3, 4), (3, 5), (4, 5) and (4, 4)

• Check whether each of these four points satisfies all of the constraints

  • it may be obvious that one (or more) do not but they should still be mentioned

• For those coordinates that do satisfy all the constraints

  • evaluate the objective function () at each of the coordinates

  • the integer solution will be the point that maximises or minimises the objective function as required

• The integer solution may not be the optimal solution

  • Depending on the exact nature (gradient) of the objective line

    • The objective line 'moves away' from the boundary of the feasible region when an integer solution is found

    • So there could be another integer solution inside (or on the boundary of) the feasible region some way from the optimal solution

    • This other integer solution may be closer to the boundary of the feasible region than the one just found

  • You will not be expected to find this other integer solution, just to recognise that the integer solution found using the above process is not necessarily optimal