formulating-a-linear-programming-problem

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 <img alt=”x plus 2 y less or equal than 4″ data-mathml='<math ><semantics><mrow><mi>x</mi><mo>+</mo><mn>2</mn><mi>y</mi><mo>≤</mo><mn>4</mn></mrow><annotation encoding=”application/vnd.wiris.mtweb-params+json”>{“language”:”en”,”fontFamily”:”Times New Roman”,”fontSize”:”18″,”autoformat”:true}</annotation></semantics></math>’ height=”22″ role=”math” src=”data:image/svg+xml;charset=utf8,%3Csvg%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20xmlns%3Awrs%3D%22http%3A%2F%2Fwww.wiris.com%2Fxml%2Fmathml-extension%22%20height%3D%2222%22%20width%3D%2272%22%20wrs%3Abaseline%3D%2216%22%3E%3C!–MathML%3A%20%3Cmath%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F1998%2FMath%2FMathML%22%3E%3Cmi%3Ex%3C%2Fmi%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E2%3C%2Fmn%3E%3Cmi%3Ey%3C%2Fmi%3E%3Cmo%3E%26%23×2264%3B%3C%2Fmo%3E%3Cmn%3E4%3C%2Fmn%3E%3C%2Fmath%3E–%3E%3Cdefs%3E%3Cstyle%20type%3D%22text%2Fcss%22%3E%40font-face%7Bfont-family%3A’math1ba105c9de6d5a994ee733008af’%3Bsrc%3Aurl(data%3Afont%2Ftruetype%3Bcharset%3Dutf-8%3Bbase64%2CAAEAAAAMAIAAAwBAT1MvMi7iBBMAAADMAAAATmNtYXDEvmKUAAABHAAAADxjdnQgDVUNBwAAAVgAAAA6Z2x5ZoPi2VsAAAGUAAABCmhlYWQQC2qxAAACoAAAADZoaGVhCGsXSAAAAtgAAAAkaG10eE2rRkcAAAL8AAAADGxvY2EAHTwYAAADCAAAABBtYXhwBT0FPgAAAxgAAAAgbmFtZaBxlY4AAAM4AAABn3Bvc3QB9wD6AAAE2AAAACBwcmVwa1uragAABPgAAAAUAAADSwGQAAUAAAQABAAAAAAABAAEAAAAAAAAAQEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAgICAAAAAg1UADev96AAAD6ACWAAAAAAACAAEAAQAAABQAAwABAAAAFAAEACgAAAAGAAQAAQACACsiZP%2F%2FAAAAKyJk%2F%2F%2F%2F1t2eAAEAAAAAAAAAAAFUAywAgAEAAFYAKgJYAh4BDgEsAiwAWgGAAoAAoADUAIAAAAAAAAAAKwBVAIAAqwDVAQABKwAHAAAAAgBVAAADAAOrAAMABwAAMxEhESUhESFVAqv9qwIA%2FgADq%2FxVVQMAAAEAgABVAtUCqwALAEkBGLIMAQEUExCxAAP2sQEE9bAKPLEDBfWwCDyxBQT1sAY8sQ0D5gCxAAATELEBBuSxAQETELAFPLEDBOWxCwX1sAc8sQkE5TEwEyERMxEhFSERIxEhgAEAVQEA%2FwBV%2FwABqwEA%2FwBW%2FwABAAADAID%2FqwKAAqsAAwAHAAsALxgBALEJAD%2BxCAXksQIF9LEBBPSxBgX0sQME5LEFBPSxBAX0sQcBEDyxAAYQPDAxEwcBNRM1ARcBNSEVgQEB%2FwH%2BAAEB%2F%2F4AAatW%2FwBWAapW%2FwBW%2FlZVVQAAAAEAAAABAADVeM5BXw889QADBAD%2F%2F%2F%2F%2F1joTc%2F%2F%2F%2F%2F%2FWOhNzAAD%2FIASAA6sAAAAKAAIAAQAAAAAAAQAAA%2Bj%2FagAAF3AAAP%2B2BIAAAQAAAAAAAAAAAAAAAAAAAAMDUgBVA1YAgAMAAIAAAAAAAAAAKAAAAKEAAAEKAAEAAAADAF4ABQAAAAAAAgCABAAAAAAABAAA3gAAAAAAAAAVAQIAAAAAAAAAAQASAAAAAAAAAAAAAgAOABIAAAAAAAAAAwAwACAAAAAAAAAABAASAFAAAAAAAAAABQAWAGIAAAAAAAAABgAJAHgAAAAAAAAACAAcAIEAAQAAAAAAAQASAAAAAQAAAAAAAgAOABIAAQAAAAAAAwAwACAAAQAAAAAABAASAFAAAQAAAAAABQAWAGIAAQAAAAAABgAJAHgAAQAAAAAACAAcAIEAAwABBAkAAQASAAAAAwABBAkAAgAOABIAAwABBAkAAwAwACAAAwABBAkABAASAFAAAwABBAkABQAWAGIAAwABBAkABgAJAHgAAwABBAkACAAcAIEATQBhAHQAaAAgAEYAbwBuAHQAUgBlAGcAdQBsAGEAcgBNAGEAdABoAHMAIABGAG8AcgAgAE0AbwByAGUAIABNAGEAdABoACAARgBvAG4AdABNAGEAdABoACAARgBvAG