Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Linear Equations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search