Transcript Linear Programming - piercemathresources

Linear Programming
A Summary
What??
Linear Programming is an algebraic
strategy used to find optimal solutions.
– Uses linear inequalities called constraints.
– The solution of the set of constraints is called
the feasible region.
• How do we identify the feasible region?
– The function to be maximized is called the
objective function.
Warm Up
1) Solve the following
system of equations:
x y 7
2x  y  8
3 x  15
x5
5 y  7
y2
(5,2)
2) Graph the solution:
 y  2x  3
y  x  5


x  0
 y  1
Connections
On a piece of graph paper, graph all the
numbers x and y whose sum is less
than or equal to 8.
What mathematical statement can
represent these points?
Answer : x  y  8
Suppose we add the constraints:
2 x5
y2
How does this
change your graph?
Connections Continued
Given the graph we just found, solve the
following:
If D = x – y, find the least and
greatest possible values for D within
the region.
D is our OBJECTIVE FUNCTION!
1) What are our critical (test)
points?
Hint: Find the points of
intersection for the lines!
2) Test these points to find the
largest and smallest values for D.
Smallest: (2,6)
Largest: (5,2)
(2,2)( 2,6)(5,3)(5,2)
D
(2,2) : 2  2  0
(2,6) : 2  6  4
(5,3) : 5  3  2
(5,2) : 5  2  3
Practice
 Choose one of the following
problems to solve.
 For each problem, clearly
identify the following:
– The linear equalities that
produce the constraints.
– Graph the feasible region.
– Identify the test points.
– State the objective function.
– Find the solution.
Manufacturing
 A ski manufacturer makes two types of skis and has a





fabricating department and a finishing department.
A pair of downhill skis requires 6 hours to fabricate and 1 hour
to finish.
A pair of cross-country skis requires 4 hours to fabricate and 1
hour to finish. The fabricating department has 108 hours of
labor available per day.
The finishing department has 24 hours of labor available per
day.
The company makes a profit of $40 on each pair of downhill
skis and a profit of $30 on each pair of cross-country skis.
Find the maximum profit.
Transportation
 Trenton, Michigan, a small community, is trying to
establish a public transportation system of large and small
vans.
 It can spend no more that $100,000 for both sizes of
vehicles and no more than $500 per month for
maintenance.
 The community can purchase a small van for $10,000 and
maintain it for $100 per month.
 The large vans cost $20,000 each and can be maintained
for $75 per month.
 Each large van carries a maximum of 15 passengers and
each small van carries a maximum of 7 passengers.
 We need to maximize the number of passengers.
Business
 A tourist agency can sell up to 1200 travel packages for a







football game.
The package includes airfare, weekend accommodations, and
the choice of two types of flights: a nonstop flight or a two-stop
flight.
The nonstop flight can carry up to 150 passengers.
The two-stop flight can carry up to 100 passengers.
The agency can locate no more than 10 planes for the travel
packages.
Each package with a non-stop flight sells for $1200 and each
package with a two-stop flight sells for $900.
Assume that each plane will carry the maximum number of
passengers.
Find the maximum revenue.
Health
 A school dietician wants to prepare a meal of meat and
vegetables that has the lowest possible fat and that meets
the FDA recommended daily allowance of iron and
protein.
 The minimums are 20 mg of iron and 45 grams of protein.
 Each 3 oz serving of meat contains 45 grams of protein, 10
mg of iron, and 4 grams of fat.
 Each 1 cup serving of vegetables contains 9 grams of
protein, 6 mg of iron, and 2 grams of fat.
 Let x be the number of 3 oz servings of meat and let y be
the number of 1 cup servings of vegetables
 Find the minimum number of grams of fat for the given
constraints.
Agriculture
 A farmer has 90 acres available for planting millet and
alfalfa.
 See costs $4 per acre for millet and $6 per acre for alfalfa.
 Labor costs are $20 per acre for millet and $10 per acre
for alfalfa.
 The expected income is $110 per acre for millet and $150
per acre for alfalfa.
 The farmer intends to spend no more than $480 for seed
and $1400 for labor.
 Find the maximum income.
Review
 Identify x and y.
 Write a system of




inequalities based on the
given constraints.
Graph the inequalities to find
the feasible region.
Find the vertices to use as
test points.
Write the objective function
to be maximized or
minimized.
Substitute the test points to
find the minimum or
maximum value.