MATH318: Linear Programming
Names:
The purpose of this exercise is to practice formulating a problem,
identifying the feasible region, finding the extreme points of the
feasible region, and identifying the optimal solution. The worksheet
also introduces the concepts of redundant constraints and infeasibility.
Problem 1 (Modified from problem 36, page 276.) Consolidated
Electronics has two employee training programs -- Leadership and
Problem Solving. The training programs are delivered to 20 employees
at a time. Leadership training is a 3 day program and costs
$10,000 per offering; Problem Solving lasts 2 days and costs $8,000.
Consolidated Electronics' management has decided that at least 15
training programs should be offered total, with at least 6 of these on
Leadership and at least 6 on Problem Solving. However, they do not
wish their employees to use more than 1000 days of training. (One
Leadership training program occupies 20 employees for 3 days, so
requires 60 days of training time.)
- Formulate a linear programming model for which the
objective is to minimize the money spent on teaching training
programs. (I.e. you wish to spend as little money as possible.)
- Graph the feasible region by hand or using Graphmatica.
Copy your graph below.
- Determine the coordinates of each extreme point.
- Find the minimal cost solution.
- Would changing the minimum number of training programs in
Problem Solving from 6 to 4 affect your answer? How or why not?
- Which (if any) of the solutions represented by the extreme points
minimizes total time spent in training programs? How do you know?
Problem 2 According to http://www.whitehouse.gov/omb/budget/fy2006/tables.html,
the U.S. government received approximately $2 trillion in funds during
the year 2005. Approximately $1.3 trillion had already been promised
to programs such as Medicare and Social Security, leaving
approximately $700 billion in "discretionary" funds for budget items
like defense and education.
Suppose the Department of Defense required at least $440 billion to
function and that the total spending by other government departments
(Education, Health and Human Services, Food and Drug Administration,
Energy, etc.) was required to be at least $480 billion.
Suppose further that every $100 billion
spent on defense increased taxpayer satisfaction by 5% while every
$100 billion spent on other services increased satisfaction by 3%.
- Formulate a linear programming problem to maximize
taxpayer satisfaction subject to the constraints on discretionary
spending.
- Graph the constraints as when finding the feasible region
- Can you find a solution that maximizes taxpayer satisfaction?
Why or why not?
Problem 3 (Modified from problem 28, page 274.) Tom's,
Inc. produces Western Foods Salsa and Mexico City Salsa. Western
Foods Salsa is a blend of 5% pepper sauce, 50% tomato sauce and 45%
crushed tomatoes. Mexico City Salsa consists of 30% fresh tomatoes,
5% pepper sauce, 20% tomato sauce and 45% crushed tomatoes.
During the winter months, Tom's Inc. can only purchase up to 280
pounds of fresh tomatoes per month while the other ingredients have
effectively unlimited availability. The price per pound of the
ingredients is: $.96 for fresh tomatoes, $2.10 for pepper sauce, $.34
for tomato sauce and $.44 for crushed tomatoes. From this one can calculate
that materials costs are $.473/lb for Western Foods salsa and $.659/lb for
Mexico City salsa (ignoring the cost of packaging.)
Tom's has a contract with a chain of grocery stores that
requires them to produce at least 1000 pounds of salsa per month.
Tom's sells Western Foods Salsa for $1.64/pound and Mexico City
Salsa for $1.93/pound; shipping costs are paid by the purchaser.
- Formulate a linear programming model to help Tom's decide
how many pounds of each type of salsa to make during the winter months
to maximize their total profits.
- Graph the feasible region for this linear programming
model.
- Can you find an optimal solution to this problem?
Why or why not?