A Brief Introduction to Linear Programming
Getting Started with some Simple Linear Programming Examples
Aug 13, 2009
Linear programming (or LP) is a mathematical problem solving technique that:
- makes various assumptions about a set of data
- works within well defined constraints
- produces a solution by modelling these assumptions and constraints
Some linear programming examples could be:
- a shop has a set budget of to fill a set of shelves and two products with different cost prices. How should the shop distribute the products to maximise their profits?
- a coal fired power station can use two different types of coal; one is cheaper but more polluting; the other is more expensive but burns cleaner. How can the power station produce the most electricity for the least cost and with the minimum pollution?
- a taxi driver can take a longer route with faster flowing traffic or a shorter route with slower traffic. Which one is most cost effective?
Having defined some problems, the next step is to identify the assumptions.
Linear Programming Assumptions
In order order for LP to work it must makes some basic assumptions:
- divisibility - all variables must be real
- non-negativity - a variables must be positive
- linearity - the relationships between any variables must be linear
If the linear programming examples fulfil these criteria then the next step is to understand any constraints imposed on the variables (often referred to as the decision variables).
Linear Programming Constraints
Any decision variables will have constraints imposed upon them by the LP assumptions, for example:
Other constraints will be imposed by the problem itself. For instance, the constraints for the shop in the first of the above linear programming examples could be:
- a budget of $2,500 for filling the shelves:
- item x costs the shop $20 and item y costs $35
- item x gives a profit of $8 and y $12
- the shelves can contain a maximum of 100 items
So, the budget constraint is:
And if the shelves can only fit 100 items then:
And, of course, there is a constrain due to the profit to be made. So if the shop makes $8 on item x and $12 on item y then:
where z is the maximum profit.
Linear Programming Solutions
In order to solve these linear programming examples the programmer needs a generic model that takes account of the assumptions and constraints but without any specific values. For example it could be some simple VBScript:
It's then just a matter running the subroutine with the specific values for the linear programming example:
In this linear programming example the optimal values of x an y will be calculated to be 67 and 33 (as shown in figure 1) and the profit (if everything is sold) will be $932. This generic model can then be used to see the effect of, for example, raising the cost of item y to $40. This time x will be 75, y will be 25 and the profit $900.
The linear programming examples in this article have, of course, been very simple. In the real world there will be several, if not hundreds, of decision variables and constraints. However, the examples do show how easy it is to build a generic model from the constraints and the assumptions, and that this model can then be applied to any set of similar values.
 |
 |
