When the L.P. problem involves only two decision variables its solution may be obtained by graphical means. Consider the earlier example.
The shaded region OABCD contains all the points (x,y) which satisfy the constraints. The points form the set of feasible solutions. Clearly there are an infinite number of such points. We require that one which gives a maximum value of z. From z = 8x + 5y with rearranging we get y = – 8/5x + z/5, for different values of z this equation represents a family of straight lines each with a gradient -8/5. Z will be greatest when the family of parallel lines leave the feasible region i.e. at C (2.5,4.5). Point C’s values can be found using simultaneous equations of the lines which cross at that point. 3x +y = 12 and x + y = 7. By subtraction 2x = 5 \ x = 2.5 y = 4.5.
Hence Zmax = 8(2.5) + 5(4.5) = 42.5.
In the above problem we are producing bicycles and trucks. Yet our graphical solution gave us x being 2.5 and y being 4.5. Not very sensible, it is difficult to make half a truck! Some problems obviously must be integer solutions. In these cases we must “test” integer points within the feasible region. The integer point will usually be near the location were the family of profit lines left the feasible region. In our case near point C. Integer points near C yet still within the feasible region are (2,4), (2,5), (3,3). Putting these points in our objective function z = 8x + 5y gives z to be 36, 41 and 39 respectively. Hence our integer solution is a point (2,5) there the profit is £41.
If you find these difficult to follow there are lots more examples online. Many of the best lessons used to come from the Open University Math’s models which were broadcast on the BBC. I’m not sure if you can still find them as they are quite old now, but it might be worth checking the BBC’s archive – BBC iPlayer. If you’re not able to access the site because of location restrictions then this site can help to access via a BBC iPlayer DNS service.
The Simplex Method
The Simplex Method is an algebraic rather than graphical approach to solving Liner Programming problems. The advantage of the Simplex Method is that it can cope with grater than 2 variables which cannot be solved graphically.
The first step is to state the general Linear Programming problem in a standard form. We require a L.P. problem to be put into a form in which
- the object function is to be maximised e.g. Maximise z =
- all the variables are to be non-negative i.e. zero or positive because you cannot have negative amounts
III. all the constraints are to be equations (except for the non-negativity constraints) i.e. no >, , <, but only =.
- the right hand side constant of the constraints is positive or zero e.g. not x = 2 but x = 2 i.e. the RHS is +ve.
For further help see the below resources:
Additional: BBC iPlayer Access – Free Trial Offer