Formulating a Linear Programming Problem (Edexcel A Level Further Maths: Decision Maths 1)

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

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)

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.