Typical Algebraic Linear Programming Problem

Date: 08/07/2004 at 10:21:21
From: Louise
Subject: Linear Programming

A manufacturing plant has a contract to supply 72 machines per week. 
For this, they employ x artisans and y apprentices, but can not 
accomodate more than 16 employees.  The ratio of apprentices:artisans 
may not be more than 9:2, or smaller than 1:2.  An artisan can 
manufacture 9 machines per week, and an apprentice can produce 6 
machines per week.

1. Represent the information as inequalities
2. Represent the inequalities graphically, and indicate the feasible 
   region
3. An artisan earns $600 per week and an apprentice $300. Use the 
   graph to determine how the manager of the plant has to employ to 
   ensure minimum expenses.
4. What are the minimum expenses per week?

I know that I need to write equations for all the conditions and graph
them to find the feasible region, then check the corner points, but
I'm struggling.  Can you help?

Date: 08/09/2004 at 12:11:51
From: Doctor Mike
Subject: Re: Linear Programming

Hi Louise,
 
This technique involves finding straight lines which form the 
boundaries of a region of the plane containing all possible solutions.  
A point (x,y) inside or on the boundary will give a solution which 
satisfies all the requirements.  The BEST solution will happen where 
two of those boundary lines intersect.  Which two?  You have to check 
ALL of them. 
  
The thing you want to check at each of these intersections is the 
total expenses, that is, the total amount to pay out to all the 
employees.  Since there are x artisans each making $600 per week and y 
apprentices each making $300 per week, the expenses for a week are 
given by

  600x + 300y

Now we need to find all the possible points (x,y) to try in that
expression and see which one gives the smallest result for expenses.

The first step is to find the straight line equations that represent
the constraints given in the problem.  These equations may start out
as inequalities.  For example, you are told that there can not be more
than 16 employees.  That becomes the inequality  

  x + y <= 16  (I use "<=" for "less than or equal to")

Every ordered pair (x,y) which satisfies this INEQUALITY satisfies the 
requirement about the number of employees.  The pair (2,7) is in that 
region, and the sum 2 + 7 is 9, which certainly is less than 16.
 
Every ordered pair (x,y) which satisfies the EQUATION x + y = 16 is
ON the boundary, or edge, of the region.  The pair (2,14) is on that
boundary line since 2 + 14 = 16.
  
Let's look at the other requirements or constraints in the problem. 
Since each artisan makes 9 machines per week and each apprentice makes
6, the total number of machines produced in a week is 9x + 6y.  The
total number of machines must be at least 72, though they can make
more than that and put the extras in inventory.  So this constraint is

  9x + 6y >= 72

Putting that in slope/intercept form, we get

  y >= -1.5x + 12

Now for what may be the hard part: the ratios.  That's a fancy way of 
talking about fractions.  Since the ratio of apprentices to artisans 
has to be less than 9:2, we can write

  y/x <= 9/2

Similarly, the ratio has to be greater than 1:2, so

  y/x >= 1/2

You should review what you've learned about working with inequalities
to see that these mean the same as the inequalites

  2y <= 9x and 2y >= x

Finally, remember that x and y stand for the number of employees of a
certain type, so these numbers cannot be less than zero and must be
integers since you can't have negative or partial employees.

We now have 4 constraints on the feasible region.  Let's write them 
all out in original form and in slope/intercept form:

  x + y <= 16           y <= -x + 16
  9x + 6y >= 72         y >= -1.5x + 12
  2y <= 9x              y <= 4.5x
  2y >= x               y >= 0.5x

So there you have the 4 boundary lines.  Get out a piece of graph 
paper and draw a sketch to show those boundary lines.  I've made one
you can look at here:

     

As you may recall, for each inequality you will shade on one side of
the boundary line or the other, depending on whether the inequality is
greater than or less than.  I think the easiest way to determine which
side to shade is to simply try a point like (0,0) or (1,1) in the
original statement and see if it makes the inequality true.  If it
does, shade the side that contains that point.  If it doesn't, shade
the other side.

Once you've tested and shaded all four inequalities, you want to find
the overall region that makes all four statements true.  Here's my
picture showing that region:

     

So any (x,y) point that falls within that shaded region meets all four
conditions of the problem.  The question then becomes choosing which
of those possible points gives the smallest value for the weekly
expenses, which we talked about above as

  600x + 300y

Again, it's known that the extreme values (maximum or minimum) will
occur at one of the corners of the feasible region.  So we only need
to test those four points to see which one gives the smallest result.

Finding the coordinates of the corners involves solving a system of
equations.  For example, the left-most corner is at the intersection
of these two lines

  y = 4.5x
  y = -1.5x + 12

By substituting the first equation into the second for y, we get

  4.5x = -1.5x + 12
    6x = 12
     x = 2

Substituting x = 2 into the first equation yields

  y = 4.5(2)
  y = 9

Thus, the coordinates of the left corner are (2,9).  Hiring 2 artisans
and 9 apprentices would result in weekly expenses of $3900:

  600x + 300y
  600(2) + 300(9)
  1200 + 2700
  3900

Now you need to find and check the other three corners to see which
one results in the lowest expenses.  This can be a lot of work, and
you need to be careful at each step to make sure you don't make
calculation errors.

Sometimes you can save yourself some work, though.  Often in these
problems, the lines intersect at clean integer points, so drawing your
graph very accurately may let you find the coordinates of a corner
point without having to do more algebra.  Also, keep in mind what your
variables represent.  In this problem, they represent numbers of
people, so we know that they can't be non-integer values, which may
save some time.

This problem is very typical of linear programming problems.  It is
not overly easy, but also it is not overly complicated.  Go through
ALL the details of this problem and you'll understand the linear
programming process better.  

Good luck.  Write back to us to say how you are doing or if you have
further questions.

- Doctor Mike, The Math Forum
  http://mathforum.org/dr.math/