MATH318: Linear Programming

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.)

  1. 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.)






  2. Graph the feasible region by hand or using Graphmatica. Copy your graph below. graph paper

  3. Determine the coordinates of each extreme point.







  4. Find the minimal cost solution.





  5. Would changing the minimum number of training programs in Problem Solving from 6 to 4 affect your answer? How or why not?




  6. 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, 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%.

  1. Formulate a linear programming problem to maximize taxpayer satisfaction subject to the constraints on discretionary spending.






  2. Graph the constraints as when finding the feasible region graph paper
  3. 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.


  1. 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.





  2. Graph the feasible region for this linear programming model.









  3. Can you find an optimal solution to this problem? Why or why not?