Linear programming, for example to find the maximum profit from a set of conditions.
… Constructing the inequalities from the given conditions. This will usually be a multiplication and addition involving the two quantities, for example 30x + 40y <= 35
… To plot each inequality line, set the value of one variable to zero and find the other variable. Shade on the side of each line that you DON’T want.
It can be useful to find the ‘zero points’ before you draw up the graph axes, as then you will know what scale to use.
… The region which is bounded by all the lines you have drawn is called the ‘feasible region’.
… Then make an equation for the ‘objective function’ from the information given, which is usually about the total profit. Choose a value for the profit and then plot this line on your graph so you can see the GRADIENT of the line.
To choose an appropriate value for profit, it can be useful to match it approximately to the relative values in the other equations.
For example, if the objective function is:
P = 3x + 4y
and one of the lines on our graph is:
30 = 4x + 2y
Then it makes sense to make P about ten times bigger than the x and y values:, so we could use P = 40:
40 = 3x + 4y
This line will then be easy to plot on the graph.
… Then move the objective function line UP as far as possible (if you are maximising the function) or DOWN (if you are minimising it). Note that the origin is often NOT a feasible point :).
… The optimum point will lie on or close to a vertex of the feasible region. If the variables can only be whole number, then find the nearest whole numbers WITHIN the feasible region. For this reason, it can be useful to plot your graph using squared paper with a simple scale on each axis.
Travelling Salesman (Upper and Lower Bounds)
Upper bound – (using the Nearest Neighbour algorithm)
… Choose a starting node (may be given in the question)
… Join this node to the nearest node
… Continue – join your new node to the nearest node (as long as it hasn’t already been used) – when you have included all nodes join the last node you picked back to the start.
… The best upper bound is the smallest answer.
Finding the Lower bound
… Delete one of the vertices (often told which one)
… Find a minimum spanning tree (Kruskals or Prims) for the remaining vertices
… Add to the spanning tree the lengths of two smallest edges from the deleted vertex
… You may need to repeat this for all vertices. Note that the best LOWER BOUND is the biggest answer!
The minimum tour
… The best lower bound < minimum tour < best upper bound