According to the wonderful Math Studies textbook...
Linear programming was developed in the years immediately following the second world war. The first uses were in ensuring that scarce resources such as food and fuel were distributed as efficiently as possible.
There are several stages to solving a linear programming problem.
Examples
1 metre of power cable costs $2 and 1 metre of coaxial cable costs $3. Kristina has $60 to spend. Stage 1 is to identify the variables. In many cases the best way to do this is to look at the last part of the question. What are you asked to find? In this case it is the amount of each type of cable that Kristina can afford to buy. These need to be given letter labels. It is best to use pronumerals that can easily be identified with what they represent. In this case let p equal the number of metres of power cable that Kristina can buy and c equal the number of metres of coaxial cable. You will probably find these easier to remember than x and y. Also, note that it is not necessary to know what coaxial cable is in order to answer this question!
Stage 2 is to set up constraints. In this case, Kristina cannot buy a negative amount of either type of cable so p is greater than or equal to 0, and c is greater than or equal to 0. Also, there is a financial restraint. It can help to write the information a table of costs:
This leads to the third constraint: 2p + 3c is less than or equal to 60.
Stage 3 is to identify the 'objective function.' It can help to look at the question again to help identify this. In this case, Kristina wants to buy as much cable of either type as possible. In mathematical terms, Kristina wants to maximize A = p + c (the total length of cable bought is p + c). The objective function is not just an equation, but contains whether it is desired to maximise the function.
Stage 4 is to use the techniques developed in the previous section to graph the constraints.
The unshaded region is known as the feasible region. Every point on the diagram represents an amount of each type of cable that Kristina might try to buy. Points that are inside the feasible region (such as p=5 and c=10) represent amounts that Kristina can afford to buy (they are feasible). Points that are in the shaded region represent amounts of cable that Kristina cannot buy.
Stage 5. It is required to find the solution that gives the largest value of A = p + c, with the values of p and c taken from points in the feasible region. Since there are an infinite number of points in the feasible region, it seems that this will be a very long job. It is, fortunately, not necessary to try every point as the optimal solutions to linear programming problems always lie on the boundaries of the feasible region. More than this, the optimal solutions are almost always found at the vertices (corners) of the feasible region. For simple problems such as this, the optimal solution can be found by evaluating the objective function at each vertex. In this case, the vertices are p=0, c=0, A=0 (the origin), p=30, c=0, A=30 and p=0, c=20, A=20. The largest value of the objective is 30 and the full solution is that Kristina should buy 30 metres of power cable which will cost her $60. Remember to give an answer in terms of the original problem.
Today, linear programming is a commonly used method in business management in making decisions on operating procedures.
Stage 1: Define the variables.
Stage 2: Write the constraints of the problem as inequalities.
Stage 3: Find the objective function.
Stage 4: Plot graphs of the inequalities and identify the 'feasible region' for the problem.
Stage 5: Use the objective function to find the optimal solution to the problem.
Write the information as inequalities and show the feasible region of the graph.
What is the largest amount of cable that Kristina can afford to buy?
Solution:
Power cable, p metres
Coaxial cable, c metres
Total
$2 per metre
$3 per metre
$60
2p
+
3c
is less than or equal to
60
