Formulating a Linear Programming Problem (Edexcel International A Level Maths: Decision 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)
    • They may have restrictions (constraints) 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
  • E.g. A furniture manufacturer could produce chairs and  tables per week
• Varying the decision variables will vary the quantity that is to be maximised or minimised
  • E.g. 12 chairs and 3 tables may lead to a profit of £200
  • or 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 problem?

• 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
  • Mathematically, constraints are represented by inequalities involving the decision variables
  • E.g. Constraints for a furniture manufacturer could include glue drying time or the amount of paint 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.