Hobbies And Interests
A Linear Programming Example
The example used in this article is as follows. A widget manufacturer makes two types of widget: type A and type B. The manufacturing process for both widgets has two steps. Widget A needs two hours of processing in step one and one hour of processing in step two. Widget B needs one hour of processing in step one and three hours of processing in step two. The widget company has 40 worker-hours of labor available for step one and 60 worker-hours available for step two. The company makes $20 profit on each widget A and $15 on each widget B. To maximize profit what number of each widget should be produced? What is this maximum profit?
Checking the Problem is Solvable
A problem must have the following properties for it to be solvable using linear programming. All the variables must be continuous. This means they can be expressed as fractions rather than just whole numbers. There must be a single objective to be either maximized or minimized and the constraints and the objective must be linear. This means the terms must be either a single value or a single value multiplied by an unknown value. In the example, hours and profit are both continuous. The "number of widgets" is a whole number, however it can be assumed to be continuous during the problem and then rounded to the nearest whole number at the end. The objective to be maximized is the profit. The constraints are single values. This means the problem is solvable.
Indentifying the Variables
The variables in the problem are the things we can choose to change in order to maximize the output. In the example, these things are the number of widget As and the number of widget Bs the manufacturing company makes. These are labelled A and B respectively.
Identifying the Constraints
The constraints are the things given in the problem that cannot be changed. In all linear programming problems the number of each of the variables must be set at greater than or equal to zero:
A >= 0
B >= 0
This is because it is impossible to manufacture a negative amount of something. In the example, the other constraints are the number of worker-hours available to work on each of the steps and the number of worker-hours required for each step for each widget. These can be expressed in two equations:
2A + B <= 40
A + 3B <= 60
Finding the Profit Function
The profit function produces the profit for a given number of A and B. It can be written as:
f(A,B) = 20A + 15B
It is important to recognize that the profit function does not produce the maximum profit on its own. It will produce the profit for any combination of A and B, regardless of whether that combination is possible or optimizes profit.
Finding the Solution
In linear programming problems with only two variables it is possible to solve the problem by drawing a two-dimensional graph where the two axes of the graph correspond to the two variables. If there are more than two variables the problem must be solved mathematically. In the example, the solution is found mathematically as follows. Because the profit is to be maximized, the solution must lie at the extreme edge of what is possible. This means the identified constraints can be expressed as a set of simultaneous equations:
2A + B = 40
A + 3B = 60
Solving this set of simultaneous equations gives A = 12 and B = 16. This means that if the company makes 12 widgets of type A and 16 widgets of type B the profit will be maximized. Substituting these values into the profit function gives:
f(12,16) = 20(12) + 15(16)
f(12,16) = 480
This means the maximum profit is $480.