Sketching the Feasible Region (Edexcel International AS Maths: Decision 1): Revision Note

Introduction to Solving an LP Problem Graphically

How do I solve a linear programming problem graphically?

• For problems with two decision variables

  • Plot the constraints (inequalities) 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

    • There will be a connection to one (or both) of the other decision variables

    • All constraints can be rewritten in terms of just two of the decision variables

    • E.g. $x,y,z$ are the numbers of chairs, tables and desks made by a furniture manufacturer
      The number of desks produced is twice the number of tables, i.e. $z=2y$

  • 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?

• 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

    • This includes the non-negativity 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 $y\le mx+c$ or $y\ge mx+c$ may help

    • 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

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

  • 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 $R$

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