Prentice Hall's Online Lesson Quiz Enter Web Code: aga–0304
Linear programming is one of the main applications of mathematics used in business and the social sciences. The process known as linear programming is used to find minimum cost, maximum profit, the maximum amount of learning that can take place under given conditions, and so on.
The procedures for solving linear programming problems were developed in 1947 by George Dantzig, while working on the problem of allocating supplies for Air Force troops during World War II, in a way that minimized total cost. Today, business and industry are quick to use Dantzig's methods when solving problems related to warehouse locations, factory designs, and utilizing resources among many other problems.
constraints - the inequalities limiting the problem at hand.
feasible region - the shaded polygonal area created by the intersection of the graphs of inequalities. It is the location where every constraint is met or satisfied.
unbounded - a function where no maximum value exists. The shaded regions of the constraints do not form a closed figure.
objective quantity - a function in two variables f(x,y) that is the objective to maximize or minimize, such as profit, etc.
If there is a maximum or a minimum value of the linear objective function, it occurs at one or more vertices of the feasible region.
- Graph each inequality on a coordinate axes system.
- Find the feasible region by shading correctly.
- Determine the vertices of the feasible region (polygon) that are formed.
- Evaluate each coordinate in the objective quantity.
- Determine the maximum (highest value) and the minimum (lowest value) by using substitution.
Example 1:
Graph:
Graph each inequality.
Locate the feasible region.
Identify the vertices of the polygon. (feasible region)
Evaluate the vertices by using the objective quantity.
In this example the feasible region created is a triangle with three vertices.
(1,0); (1, 4); and (3, 0)
f(x,y) = 3x + y f(1,0) = 3(1) + (0) = 3
f(1,4) = 3(1) + 4 = 7
f(3,0) = 3(3) + (0) = 9
A maximum value occurs at f(3,0) = 9; while a minimum value occurs at f(1,0)= 3.
Applications of Linear Programming
A Practical Application
The Widget Manufacturing company makes two products, Alpha Widgets and Beta Widgets. Each Alpha Widget gives a profit of $3, while each Beta Widget earns $7. The company must manufacture at least one Alpha Widget per day to satisfy its customers, but no more than five because of the number of employees needed to create the item. Also, the number of Beta Widgets produced cannot exceed six per day. As a further constraint, Alpha Widgets cannot exceed the number of Beta Widgets.
How many of each Widget should the company produce in order to obtain the maximum profit?
Begin by translating the statements of the story into symbols:
Let A = the number of Alpha Widgets to be produced daily.
Let B = the number of Beta Widgets to be produced daily.According to the story given above, the company must produce at least one Alpha Widget (one or more) so,
Also, no more than 5 Alpha Widgets may be produced:
Not more than six Beta Widgets may be made in one day, so
And the trickiest of all, the number of Alpha Widgets may not exceed the number of Beta Widgets:
Finally, the number of Alpha Widgets and Beta Widgets cannot be negative:
and
Summarize all the constraints placed on production:
Graph the inequalities and shade the feasible region, noting the vertices of the polygon created:
Write an objective quantity or Profit expression:
Since each Alpha Widget gives a profit of $3, the daily profit of a widgets is 3a dollars. Likewise, the profit from the production of b Beta Widgets is 7b dollars per day. The total daily profit is therefore
Profit= f (a, b) = 3a + 7b
The basic idea of linear programming says that in a case such as this, the maximum (or minimum) profit will be found at a corner of the graph. By looking at the figure of the graph above, we see that the vertices occur at (1,1), (1,6), (5, 5), and (5, 6).
We should then check each corner point in the objective quantity to find the maximum profit.
(A,B)
3A + 7B
f(A,B)
(1, 1)
3(1) + 7(1)
10 minimum
(1, 6)
3(1) + 7(6)
45
(5, 5)
3(5) + 7(5)
50
(5, 6)
3(5) + 7(6)
56 maximum
Maximum profit of $56 per day will be obtained if five Alpha Widgets and six Beta Widgets are made each day.
