Linear programming
- Linear programming is the process of taking various linear inequalities relating to some situation, and finding the "best" value obtainable under those conditions. A typical example would be taking the limitations of materials and labor, and then determining the "best" production levels for maximal profits under those conditions.
- In "real life", linear programming is part of a very important area of mathematics called "optimization techniques". This field of study (or at least the applied results of it) are used every day in the organization and allocation of resources. These "real life" systems can have dozens or hundreds of variables, or more. In algebra, though, you'll only work with the simple (and graph able) two-variable linear case.
- The general process for solving linear-programming exercises is to graph the inequalities (called the "constraints") to form a walled-off area on the x,y-plane (called the "feasibility region"). Then you figure out the coordinates of the corners of this feasibility region (that is, you find the intersection points of the various pairs of lines), and test these corner points in the formula (called the "optimization equation") for which you're trying to find the highest or lowest value.
Find the maximal and minimal value of z = 3x + 4y subject to the following constraints:
The three inequalities in the curly braces are the
constraints. The area of the plane that they mark off will be the feasibility
region. The formula "z =
3x + 4y" is
the optimization equation. I need to find the (x, y) corner points of the feasibility
region that return the largest and smallest values of z.
My first step is to solve each inequality for the
more-easily graphed equivalent forms:
It's easy to graph the system:
To find the corner points -- which aren't always
clear from the graph -- I'll pair the lines (thus forming a system of linear equations)
and solve:
y = –( 1/2 )x + 7
y = 3x |
y = –( 1/2 )x + 7
y = x – 2 |
y = 3x
y = x – 2 |
–( 1/2 )x + 7 = 3x
–x + 14 = 6x 14 = 7x 2 = x
y = 3(2) = 6
|
–( 1/2 )x + 7 = x – 2
–x + 14 = 2x – 4 18 = 3x 6 = x
y = (6) – 2 = 4
|
3x = x – 2
2x = –2 x = –1
y = 3(–1) = –3
|
corner point at (2, 6)
|
corner point at (6, 4)
|
corner pt. at (–1, –3)
|
So the corner points are (2, 6), (6, 4), and (–1, –3).
Somebody really smart proved that, for linear
systems like this, the maximum and minimum values of the optimization equation
will always be on the corners of the feasibility region.
So,
to find the
solution to this exercise, I only need to plug these three points into "z = 3x + 4y".
(2, 6): z = 3(2) + 4(6)
= 6 + 24 = 30
(6, 4): z = 3(6) + 4(4) = 18 + 16 = 34
(–1, –3): z = 3(–1) + 4(–3) = –3 – 12 = –15
(6, 4): z = 3(6) + 4(4) = 18 + 16 = 34
(–1, –3): z = 3(–1) + 4(–3) = –3 – 12 = –15
Then the
maximum of z = 34 occurs
at (6, 4),
and the minimum of z = –15 occurs at (–1, –3).
and the minimum of z = –15 occurs at (–1, –3).
Given
the following constraints, maximize and minimize the value of z=
–0.4x + 3.2y.
First I'll solve the fourth and fifth
constraints for easier graphing:
It's easy to graph the system:
To find the corner points -- which aren't always
clear from the graph -- I'll pair the lines (thus forming a system of linear equations)
and solve:
y = –( 1/2 )x + 7
y = 3x |
y = –( 1/2 )x + 7
y = x – 2 |
y = 3x
y = x – 2 |
–( 1/2 )x + 7 = 3x
–x + 14 = 6x 14 = 7x 2 = x
y = 3(2) = 6
|
–( 1/2 )x + 7 = x – 2
–x + 14 = 2x – 4 18 = 3x 6 = x
y = (6) – 2 = 4
|
3x = x – 2
2x = –2 x = –1
y = 3(–1) = –3
|
corner point at (2, 6)
|
corner point at (6, 4)
|
corner pt. at (–1, –3)
|
So the corner points are (2, 6), (6, 4), and (–1, –3).
Somebody really smart proved that, for linear
systems like this, the maximum and minimum values of the optimization equation
will always be on the corners of the feasibility region.
So,
to find the
solution to this exercise, I only need to plug these three points into "z = 3x + 4y".
(2, 6): z = 3(2) + 4(6)
= 6 + 24 = 30
(6, 4): z = 3(6) + 4(4) = 18 + 16 = 34
(–1, –3): z = 3(–1) + 4(–3) = –3 – 12 = –15
(6, 4): z = 3(6) + 4(4) = 18 + 16 = 34
(–1, –3): z = 3(–1) + 4(–3) = –3 – 12 = –15
Then the
maximum of z = 34 occurs
at (6, 4),
and the minimum of z = –15 occurs at (–1, –3).
and the minimum of z = –15 occurs at (–1, –3).
Given
the following constraints, maximize and minimize the value of z=
–0.4x + 3.2y.
First I'll solve the fourth and fifth
constraints for easier graphing:
The feasibility region looks like
this:
From the
graph, I can see which lines cross to form the corners, so I know which lines
to pair up in order to verify the coordinates. I'll start at the
"top" of the shaded area and work my way clockwise around the edges:
y = –x + 7
y = x + 5 |
y = –x + 7
x = 5 |
x = 5
y = 0 |
–x +
7 = x + 5
2 = 2x 1 = x
y = (1) + 5 = 6
|
y = –(5) + 7 = 2
|
[nothing
to do]
|
corner
at (1, 6)
|
corner
at (5, 2)
|
corner
at (5, 0)
|
y = 0
y = –( 1/2 )x + 2 |
y = –( 1/2 )x +
2
x = 0 |
x = 0
y = x + 5 |
–( 1/2 )x +
2 = 0
2 = (1/2)x 4 = x |
y = –( 1/2 )(0) + 2
y = 0 + 2 y = 2 |
y = (0) + 5 = 5
|
corner
at (4, 0)
|
corner
at (0, 2)
|
corner
at (0, 5)
|
Now I'll
plug each corner point into the optimization equation, z =
–0.4x + 3.2y:
(1, 6):
z = –0.4(1) + 3.2(6) = –0.4 + 19.2 = 18.8
(5, 2): z = –0.4(5) + 3.2(2) = –2.0 + 6.4 = 4.4
(5, 0): z = –0.4(5) + 3.2(0) = –2.0 + 0.0 = –2.0
(4, 0): z = –0.4(4) + 3.2(0) = –1.6 + 0.0 = –1.6
(0, 2): z = –0.4(0) + 3.2(2) = –0.0 + 6.4 = 6.4
(5, 2): z = –0.4(5) + 3.2(2) = –2.0 + 6.4 = 4.4
(5, 0): z = –0.4(5) + 3.2(0) = –2.0 + 0.0 = –2.0
(4, 0): z = –0.4(4) + 3.2(0) = –1.6 + 0.0 = –1.6
(0, 2): z = –0.4(0) + 3.2(2) = –0.0 + 6.4 = 6.4
(0, 5): z = –0.4(0) + 3.2(5) = –0.0 + 16.0 = 16.0
Then the
maximum is 18.8 at (1, 6) and the minimum
is –2 at (5, 0).
Given the inequalities, linear-programming exercise are
pretty straightforward, if sometimes a bit long.
The hard part is usually the
word problems, where you have to figure out what the inequalities are.
So I'll
show how to set up some typical linear-programming word problems.
- At a certain refinery, the refining process requires the production of at least two gallons of gasoline for each gallon of fuel oil. To meet the anticipated demands of winter, at least three million gallons of fuel oil a day will need to be produced. The demand for gasoline, on the other hand, is not more than 6.4 million gallons a day.
- If gasoline is selling for $1.90 per gallon and fuel oil sells for $1.50/gal, how much of each should be produced in order to maximize revenue?
- The question asks for the number of gallons which should be produced, so I should let my variables stand for "gallons produced".
x: gallons of gasoline produced
y: gallons of fuel oil produced
y: gallons of fuel oil produced
Since
this is a "real world" problem, I know that I can't have negative
production levels,
so the variables can't be negative.
This gives me my first
two constraints: namely, x > 0 and y > 0.
Since
I have to have at least two gallons of gas for every gallon of oil, then
x > 2y.
x > 2y.
For
graphing, of course, I'll use the more manageable form "y < ( 1/2 )x".
The
winter demand says that y >3,000,000; note that this
constraint eliminates the need for the "y > 0"
constraint. The gas demand says that x < 6,400,000.
I
need to maximize revenue R, so the optimization equation is R =
1.9x + 1.5y. Then the model for this word problem is as
follows:
R = 1.9x + 1.5y,
subject to:
x > 0
x < 6,400,000 Copyright © Elizabeth Stapel 2006-2011 All Rights Reserved
y > 3,000,000
y < ( 1/2 )x
x > 0
x < 6,400,000 Copyright © Elizabeth Stapel 2006-2011 All Rights Reserved
y > 3,000,000
y < ( 1/2 )x
Using
a scale that counts by millions (so "y = 3" on the
graph means "y is three million"), the above system
graphs as follows:
When you test the corner points at (6.4m, 3.2m), (6.4m, 3m), and (6m, 3m), you should get a maximal
solution of R = $16.96m at (x, y) = (6.4m, 3.2m).
- A calculator company produces a scientific calculator and a graphing calculator. Long-term projections indicate an expected demand of at least100 scientific and 80 graphing calculators each day. Because of limitations on production capacity, no more than 200 scientific and 170graphing calculators can be made daily. To satisfy a shipping contract, a total of at least 200 calculators much be shipped each day.
- If each scientific calculator sold results in a $2 loss, but each graphing calculator produces a $5 profit, how many of each type should be made daily to maximize net profits?
The question
asks for the optimal number of calculators, so my variables will stand for
that:
x: number of scientific calculators produced
y: number of graphing calculators produced
y: number of graphing calculators produced
Since they
can't produce negative numbers of calculators, I have the two
constraints, x > 0 and y > 0.
But in this case, I can ignore these constraints, because I already have that x > 100 Andy > 80.
The exercise also gives maximums: x < 200 and y < 170.
The minimum shipping requirement gives mix + y > 200; in other words, y > –x + 200.
The profit relation will be my optimization equation: P = –2x + 5y. So the entire system is:
But in this case, I can ignore these constraints, because I already have that x > 100 Andy > 80.
The exercise also gives maximums: x < 200 and y < 170.
The minimum shipping requirement gives mix + y > 200; in other words, y > –x + 200.
The profit relation will be my optimization equation: P = –2x + 5y. So the entire system is:
P = –2x + 5y, subject to:
100 < x < 200
80 < y < 170
y > –x + 200
100 < x < 200
80 < y < 170
y > –x + 200
The
feasibility region graphs as:
SEE THIS VIDEO! (learn something from this video).....
QUESTIONS?
Q:1
Define and discuss the linear programming technique, including assumptions of linear programming and accounting data used therein
Q:2 What is meant by the unit cost in linear programming problems?
Q:3Hale Company manufactures products A and B, each of which requires two processes, grinding and polishing. The contribution margin is $3 for A and $4 for B. A graph showing the maximum number of units of each product that can be processed in the two departments identifies the following corner points: A = 0, B = 20; A = 20, B = 10; A = 30, B = 0. What is the combination of A and B that maximizes the total contribution margin?
Q:4
What is the simplex method?
Define and discuss the linear programming technique, including assumptions of linear programming and accounting data used therein
Q:2 What is meant by the unit cost in linear programming problems?
Q:3Hale Company manufactures products A and B, each of which requires two processes, grinding and polishing. The contribution margin is $3 for A and $4 for B. A graph showing the maximum number of units of each product that can be processed in the two departments identifies the following corner points: A = 0, B = 20; A = 20, B = 10; A = 30, B = 0. What is the combination of A and B that maximizes the total contribution margin?
Q:4
What is the simplex method?
Q:5
The Golden Hawk Company wants to maximize the profits on the products A, B, C. The contribution margin for each product follows:
The Golden Hawk Company wants to maximize the profits on the products A, B, C. The contribution margin for each product follows:
| Product | Contribution Margin |
| A | $2 |
| B | $5 |
| C | $4 |
The production requirements and departmental capacities, by departments, are as follows:
| Department | Production Requirement By Product (Hours) | Departmental Capacity (Total Hours) | ||
| A | B | C | 30,000 | |
| Assembling | 2 | 3 | 2 | 38,000 |
| Painting | 1 | 2 | 2 | 28,000 |
| Finishing | 2 | 3 | 1 | |
Formulate the objective function and the constraints.
Q:6
Formulate the objective function and the constraints for a situation in which a company seeks to minimize the total cost of materials A and B. The per pound cost of A is $25 and B, $10. The two materials are combined to form a product that must weigh 50 pounds. At least 20 pounds of A and no more than 40 pounds of B can be used.
Formulate the objective function and the constraints for a situation in which a company seeks to minimize the total cost of materials A and B. The per pound cost of A is $25 and B, $10. The two materials are combined to form a product that must weigh 50 pounds. At least 20 pounds of A and no more than 40 pounds of B can be used.
Q:7
Discuss the components of a simplex tableau.
Discuss the components of a simplex tableau.
Q:8What is the purpose of a slack variable?
Q:9
A partial linear programming maximization simplex tableau for products x and y and slack variables s1 and s2 appears below:
A partial linear programming maximization simplex tableau for products x and y and slack variables s1 and s2 appears below:
| Mix | 0 | 6 | 7 | 0 | 0 | |
| Quantity | x | y | s1 | s2 | ||
| 7 | y | 4 | 2 / 3 | 1 | 1 / 3 | 0 |
| 0 | s2 | 4 | 4 / 3 | 0 | -1 / 3 | 1 |
(a) Computer the index row.
(b) Has an optimum solution been reached? Explain.
(c) Suppose that one unit of s1 were placed in the solution. What effect would this have on product y?
(b) Has an optimum solution been reached? Explain.
(c) Suppose that one unit of s1 were placed in the solution. What effect would this have on product y?
Q:10
What is the purpose of an artificial variable?
What is the purpose of an artificial variable?
No comments:
Post a Comment