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

Introduction to Linear Programming

What is linear programming?

• Linear programming, often abbreviated to LP, is a means of solving problems that

  • involve working with a set of constraints

  • require a quantity to be maximised or minimised

• Typical uses of linear programming problems including finance and manufacturing

  • For example, a furniture manufacturer may make a mixture of chairs and tables

    • they would want to minimise their costs (of raw materials, manufacturing time)

    • they would want to maximise their profit (chairs may make more profit than tables)

    • but would be restricted (constrained) by things such as build time and the amount of raw materials available

Decision Variables in Linear Programming

What are decision variables?

• In a linear programming problem, decision variables are the quantities that can be varied

  • are usually used as the decision variables

  • A furniture manufacturer, it could be that they produce chairs and  tables (per day/week)

• Varying the decision variables will vary the quantity that is to be maximised or minimised

  • 12 chairs and 3 tables may lead to a profit of £200, whilst 3 chairs and 12 tables may lead to a profit of £160

• The values that the decision variable may take will depend upon the constraints

  • A furniture manufacturer can't make endless chairs and tables to gain unlimited profit !

What is the objective function in a linear programming?

• The objective function is the quantity in a linear programming problem that requires optimising

  • The objective of a furniture manufacturer may be to maximise its profits

  • they may also wish to minimise their costs

• The objective function is the aim of a linear programming problem

  • It is a function of the decision variables

  • is usually used for maximising problems (, profit)

  • is usually used for minimising problems (, costs)

Constraints & Inequalities in Linear Programming

What are constraints in linear programming?

• The constraints in a linear programming problem are the restrictions the problem is contained within

  • These restrictions are called constraints

    • Mathematically they are represented by inequalities involving the decision variables

  • for a furniture manufacturer constraints could include glue drying time and the amount of paint/varnish available

• Decision variables are usually zero or positive as they represent a 'number of things'

  • the constraint  is usually included

  • this is called the non-negativity constraint

How do I formulate a linear programming problem?

• Formulating a linear programming problems involves

  • defining the decision variables

  • deducing the constraints as inequalities

  • determining the objective function

  • writing the problem out formally

• STEP 1
  Define the decision variables

  • Read the question carefully to gather what quantities can be varied

  • Typically these will be a 'number of things'

• STEP 2
  Write each constraint (given in words) as a mathematical inequality

  • Where possible, inequalities should be simplified, e.g.   simplifies to 

  • Each inequality will be in terms of the decision variables

• STEP 3
  Determine the objective function

  • This will be the quantity that is required to be maximised or minimised

  • Typically this would be maximising profit or minimising costs

• STEP 4
  Formulate the linear programming problem by writing it in a formal manner

  • This is of the form
    Maximise      
    <objective function>
    subject to    
     <constraints>

  • Include the non-negativity constraint, e.g.