solving-a-linear-programming-problem-graphically

课 Progress

0% Complete

Introduction to solving an LP problem graphically

How do I solve a linear programming problem graphically?

For problems with two decision variables
- the constraints (inequalities) are plotted 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
  - but there will be a connection to one (or both) of the other decision variables such that all constraints can be rewritten in terms of just two of them
    
    e.g.
    
    $x comma space y comma space z$ are the numbers of chairs, tables and desks made by a furniture manufacturer but the number of desks produced is twice the number of tables (i.e. $z equals 2 y$ )
- 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?

Technically, 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
- including the non-negativity constraint/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 less or equal than m x plus c$ or $y greater or equal than m x plus c$ may help
    - but 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
  - be careful with graphing software – these will often shade the part of the graph that does satisfiy an inequality
  - but it is easier to see a ‘blank’ area rather than an area shaded several times
  - a workaround to this is to reverse the inequality sign when typing the inequality into the software
- 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 each inequality/line around the edge of the graph

Examiner Tips and Tricks

Exam questions will provide a graph for you to accurately plot the inequalities on or provide an accurate graph with some or all of the inequalities already plotted

Worked Example

A linear programming problem is formulated as

Maximise

<img alt=”P equals 30 x plus 40 y” data-mathml='<math ><semantics><mrow><mi>P</mi><mo>=</mo><mn>30</mn><mi>x</mi><mo>+</mo><mn>40</mn><mi>y</mi></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%22102%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%3EP%3C%2Fmi%3E%3Cmo%3E%3D%3C%2Fmo%3E%3Cmn%3E30%3C%2Fmn%3E%3Cmi%3Ex%3C%2Fmi%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E40%3C%2Fmn%3E%3Cmi%3Ey%3C%2Fmi%3E%3C%2Fmath%3E–%3E%3Cdefs%3E%3Cstyle%20type%3D%22text%2Fcss%22%3E%40font-face%7Bfont-family%3A’math1564b4c0e54101ac57a0cb68c16’%3Bsrc%3Aurl(data%3Afont%2Ftruetype%3Bcharset%3Dutf-8%3Bbase64%2CAAEAAAAMAIAAAwBAT1MvMi7iBBMAAADMAAAATmNtYXDEvmKUAAABHAAAADxjdnQgDVUNBwAAAVgAAAA6Z2x5ZoPi2VsAAAGUAAABK2hlYWQQC2qxAAACwAAAADZoaGVhCGsXSAAAAvgAAAAkaG10eE2rRkcAAAMcAAAADGxvY2EAHTwYAAADKAAAABBtYXhwBT0FPgAAAzgAAAAgbmFtZaBxlY4AAANYAAABn3Bvc3QB9wD6AAAE%2BAAAACBwcmVwa1uragAABRgAAAAUAAADSwGQAAUAAAQABAAAAAAABAAEAAAAAAAAAQEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAgICAAAAAg1UADev96AAAD6ACWAAAAAAACAAEAAQAAABQAAwABAAAAFAAEACgAAAAGAAQAAQACACsAPf%2F%2FAAAAKwA9%2F%2F%2F%2F1v%2FFAAEAAAAAAAAAAAFUAywAgAEAAFYAKgJYAh4BDgEsAiwAWgGAAoAAoADUAIAAAAAAAAAAKwBVAIAAqwDVAQABKwAHAAAAAgBVAAADAAOrAAMABwAAMxEhESUhESFVAqv9qwIA%2FgADq%2FxVVQMAAAEAgABVAtUCqwALAEkBGLIMAQEUExCxAAP2sQEE9bAKPLEDBfWwCDyxBQT1sAY8sQ0D5gCxAAATELEBBuSxAQETELAFPLEDBOWxCwX1sAc8sQkE5TEwEyERMxEhFSERIxEhgAEAVQEA%2FwBV%2FwABqwEA%2FwBW%2FwABAAACAIAA6wLVAhUAAwAHAGUYAbAIELAG1LAGELAF1LAIELAB1LABELAA1LAGELAHPLAFELAEPLABELACPLAAELADPACwCBCwBtSwBhCwB9SwBxCwAdSwARCwAtSwBhCwBTywBxCwBDywARCwADywAhCwAzwxMBMhNSEdASE1gAJV%2FasCVQHAVdVVVQAAAQAAAAEAANV4zkFfDzz1AAMEAP%2F%2F%2F%2F%2FWOhNz%2F%2F%2F%2F%2F9Y6E3MAAP8gBIADqwAAAAoAAgABAAAAAAABAAAD6P9qAAAXcAAA%2F7YEgAABAAAAAAAAAAAAAAAAAAAAAwNSAFUDVgCAA1YAgAAAAAAAAAAoAAAAoQAAASsAAQAAAAMAXgAFAAAAAAACAIAEAAAAAAAEAADeAAAAAAAAABUBAgAAAAAAAAABABIAAAAAAAAAAAACAA4AEgAAAAAAAAADADAAIAAAAAAAAAAEABIAUAAAAAAAAAAFABYAYgAAAAAAAAAGAAkAeAAAAAAAAAAIABwAgQABAAAAAAABABIAAAABAAAAAAACAA4AEgABAAAAAAADADAAIAABAAAAAAAEABIAUAABAAAAAAAFABYAYgABAAAAAAAGAAkAeAABAAAAAAAIABwAgQADAAEECQABABIAAAADAAEECQACAA4AEgADAAEECQADADAAIAADAAEECQAEABIAUAADAAEECQAFABYAYgADAAEECQAGAAkAeAADAAEECQAIABwAgQBNAGEAdABoACAARgBvAG4AdABSAGUAZwB1AGwAYQByAE0AYQB0AGgAcwAgAEYAbwByACAATQBvAHIAZQAgAE0AYQB0AGgAIABGAG8AbgB0AE0AYQB0AGgAIABGAG8AbgB0AFYAZQByAHMAaQBvAG4AIAAxAC4AME1hdGhfRm9udABNAGEAdABoAHMAIABGAG8AcgAgAE0AbwByAGUAAAMAAAAAAAAB9AD6AAAAAAAAAAAAAAAAAAAAAAAAAAC5BxEAAI2FGACyAAAAFRQTsQABPw%3D%3D)format(‘truetype’)%3Bfont-weight%3Anormal%3Bfont-style%3Anormal%3B%7D%3C%2Fstyle%3E%3C%2Fdefs%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20font-style%3D%22italic%22%20text-anchor%3D%22middle%22%20x%3D%225.5%22%20y%3D%2216%22%3EP%3C%2Ftext%3E%3Ctext%20font-family%3D%22math1564b4c0e54101ac57a0cb68c16%22%20font-size%3D%2216%22%20text-anchor%3D%22middle%22%20x%3D%2219.5%22%20y%3D%2216%22%3E%3D%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%2237.5%22%20y%3D%2216%22%3E30%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20font-style%3D%22italic%22%20text-anchor%3D%22middle%22%20x%3D%2250.5%22%20y%3D%2216%22%3Ex%3C%2Ftext%3E%3Ctext%20font-family%3D%22math1564b4c0e54101ac57a0cb68c16%22%20font-size%3D%2216%22%20text-anchor%3D%22middle%22%20x%3D%2264.5%22%20y%3D%2216%22%3E%2B%3C%2Ftext%3

Further Maths: Decision 1