Lesson LINEAR PROGRAMMING PROBLEMS AND SOLUTIONS 2

this lesson includes problems pertaining to linear programming and their solutions.

PROBLEM NUMBER 5

An elementary school wants to send children on a field trip to a museum. The museum staff has informed the school that tours can be scheduled for no more than 50 total people and the school must provide at least one adult chaperone for every 9 students.

Make a list of constraints.
graph the feasible region.
calculate and label the vertices.

SOLUTION TO PROBLEM NUMBER 5

the people that will be at the field trip will be adults and children.

let x = the number of adults
let y = the number of children

the total number of people that can attend is 50.
the equation for this constraint would be:
x + y <= 50

there must be at least one adult for every 9 children.
the equation for this constraint would be the ratio equation of:
x/y >= 1/9
cross multiply to get:
9x >= y
divide both sides of this equation by 9 to get:
x >= y/9

since x or y can't be negative, we have 2 more constraint equations.
they are:
x >= 0
y >= 0

we have 4 constraint equations.
they are:
x + y <= 50
x >= y/9
x >= 0
y >= 0

in order to graph these equations, we have to solve each equation for y in all equations that have y in them to get:

y <= 50 - x
y <= 9x
x >= 0
y >= 0

you graph the equality portion of these equations to generate the lines of each equation.
x = 0 is a vertical line that is the same as the y-axis.
y = 0 is a horizontal line that is the same as the x-axis.

then you look for the area on the graph that satisfies the requirements of the original equations for graphing.

the area of the graph that satisfies all of the constraints is called the region of feasibility.

your maximum or minimum solution lies at the intersection of the boundaries of the region of feasibility.

the graph of these constraint equations is shown below:


the intersection of the line y = 9x and the y-axis is the point (0,0).
that is one of the intersection points of the region of feasibility.

the intersection of the line y = 50-x and the x-axis is the point (50,0).
that is one of the intersection points of the region of feasibility.

the intersection of the line y = 50 - x and the line y = 9x is equal to (5,45).
that is one of the intersection points of the region of feasibility.
it is found in the following manner:
since both expressions are equal to y, then set both expressions equal to each other to get:
50 - x = 9x
add x to both sides of this equation to get 10x = 50
divide both sides of this equation to get x = 5.
substitute 5 for x in either equation to get y = 45.
the intersection point is (5,45)

the region of feasibility is on or below the line y = 9x and on or to the right of the line x = 0 and on or above the line y = 0 and on or below the line y = 50 - x.

that's the shaded region in the graph.

the intersection points of the boundaries of the feasibility region are:

(0,0)
(5,45)
(50,0)

if you had an objective function for this problem, you would then test the objective function at these points of intersection to find the maximum or minimum solution of the objective function.

PROBLEM NUMBER 6

A group of artists has decided to produce hand-drawn cards for Valentine's Day and donate the money generated to charity.
The artists will produce ink drawings and watercolors.
They have volunteered to spend at most 120 hours for preparation of the cards and a maximum of 60 hours for packaging the cards.
The preparation of an ink drawing takes 0.3 hours and the preparation of a watercolor takes 0.5 hours.
The packaging of each requires 0.2 hours.

Make a list of the constraints and sketch the feasible region and label the vertices.

SOLUTION TO PROBLEM NUMBER 6

let x = the number of ink drawings.
let y = the number of watercolor drawings.

it takes .3 hours to prepare an ink drawing and .5 hours to prepare a watercolor drawing.
the total hours available for preparation is 120.
the equation for this constraint is:
.3x + .5y <= 120

it takes .2 hours to package an ink drawing or a watercolor drawing.
the total hours available for packaging is 60.
the equation for this constraint is:
.2x + .2y <= 60

2 other constraints are:
x >= 0
y >= 0

this is because the number of cards can't be negative.

your total constraint equations are:

.3x + .5y <= 120
.2x + .2y <= 60
x >= 0
y >= 0

to graph these equations, you have to solve for y in those equations that have y in them.

the equations for graphing are shown below.

y <= (120-.3x)/.5
y <= (60-.2x)/.2
x >= 0
y >= 0

you graph the equality part of these equations and then you look for the area on the graph that satisfies the original equations for graphing.

that area is called the region of feasibility.

x = 0 is a vertical line that is the same as the y-axis.
y = 0 is a horizontal line that is the same as the x-axis.

the intersection points of the lines that bound the region of feasibility are where the maximum or minimum solution of the objective function will be.

the graph of the constraint equations is shown below:


the region of feasibility is the shaded region in the graph.

the intersection points of interest are calculated as follows:

when x = 0, the equation of y = (120-.3x)/.5 becomesy = 120/.5 which results in y = 240.
the intersection point is (0,240).

when y = 0, the equation of y = (60 - .2x).2 becomes 0 = (60 - .2x)/.2.
multiply both sides of this equation by .2 to get:
60 - .2x = 0
add .2x to both sides of this equation to get:
.2x = 60
divide both sides of this equation by .2 to get:
x = 60/.2 = 300.
the intersection point is (300,0).

the intersection point for the equations of y = (120-.3x)/.5 and y = (60-.2x)/.2 are calculated as follows:
since both expressions are equal to y, then set each expression equal to each other to get:
(120-.3x)/.5 = (60-.2x)/.2
multiply both equations by 1 to get:
2*(120-.3x) = 5*(60-.2x)
simplify to get:
240 - .6x = 300 - x
add x to both sides of this equation and subtract 240 from both sides of this equation to get:
.4x = 60
divide both sides of this equation by .4 to get:
x = 150
replace x with 150 in either of the 2 equations to get y = 150.
the intersection point for these 2 lines is (150,150)
when x = 150, y = 150.

the points of intersection of the lines bounding the area of feasibility are:
(0,0)
(0,240)
(150,150)
(300,0)

if this equation had an objective function, then the objective function would be analyzed at thee intersection points to find the maximum or minimum solution for the objective function.

PROBLEM NUMBER 7

A company produces 2 portable CD players.
They are called the Shuffle Man and the Walk On.
The profits per unit are $20 for the Shuffle Man and $15 for the Walk On.
The product time (in hours) for one unit of each product is given in the chart.
The company has at most 750 worker-hours of manufacturing time available and 200 worker-hours of shipping time available each day.
At least 300 Shuffle Man players and 500 Walk On players must be produced each day.

Write the profit function to be maximized.
How many of each product should be produced each day?
What will the profit be?
If the profits for each Shuffle Man falls to $16 per unit, how many of each product should be produced?
What will the new total profit be?

The table for hours of manufacturing time and shipping time required for each product is shown below.

        product          manufacturing time          shipping time

        shuffle man                .4                       .1
        walk on                    .6                       .2

SOLUTION TO PROBLEM NUMBER 7

let x = the number of shuffle man players to be produced.
let y = the number of walk on players to be produced.

the profit equation is going to be the number of shuffle man players times $20 plus the number of walk on players times $15.

let p = profit and this equation becomes:

p = 20x + 15y

this is the objective function that we wish to maximize.

since the total manufacturing time available is 750 hours, then the constraint equation for manufacturing time will be:

.4x + .6y <= 750

since the total shipping time available is 200 hours, then the constraint equation for shipping time will be:

.1x + .2y <= 200

since the number of shuffle man players and walk on players produced can't be negative, then the additional constraint equations will be:

x >= 0
y >= 0

since the number of shuffle man players produced each day has to be greater than or equal to 300, then the constraint equation for the number of shuffle man players produced each day will be:
x >= 300

since the number of walk on players produced each day has to be greater than or equal to 500, then the constraint equation for the number of walk on players produced each day will be:

y >= 500

all the constraint equations are:

.4x + .6y <= 750
.1x + .2y <= 200
x >= 0
y >= 0
x >= 300
y >= 500

to graph these equations, we solve for y in all equations that have y in them to get:

y <= (750-.4x)/.6
y <= (200-.1x)/.2
x >= 0
y >= 0
x >= 300
y >= 500

we graph the equality portion of these equations to get the lines of each equation.

x = 0 is a vertical line that is the same as the y-axis.
y = 0 is a horizontal line that is the same as the x-axis.
x = 300 is a vertical line at x = 300.
y = 500 is a horizontal line at y = 500.

the graph of these constraint equations looks like this:



the area of feasibility is the area of the graph that satisfies the constraint equations.

the area of feasibility would be:

on or below the line of y = (750-.4x)/.6
on or below the line of y = (200-.1x)/.2
on or to the right of the line x = 0
on or above the line of y = 0
on or to the right of the line of x = 300
on or above the line of y = 500

on or above the line of y = 500 takes precedence over on or above the line of y = 0.
on or to the right of the line of x = 300 takes precedence over on or to the right of x = 0.
on or below the line of y = (200-.1x)/.2 takes precedence over on or below the line of (750-.4x)/.6

the area of feasibility is bounded by the lines of:
x = 300
y = 500
y = (200-.1x).2

the points of intersection are:
(300,500)
(300,850)
(1000,500)

the objective function is:

p = 20x + 15y

this objective function is analyzed at the points of intersection to get:

points of intersection            p = 20x + 15y
(300,500)                             13,500
(300,850)                             18,750
(1000,500)                            27,500 *****

profit is maximized when 1000 shuffle man players are produced and 500 walk on players are produced.

the constraint equations have to have been met in order for this solution to be valid.

the original constraint equations were:

.4x + .6y <= 750 (maximum number of manufacturing hours)
.1x + .2y <= 200 (maximum number of shipping hours)
x >= 0
y >= 0
x >= 300 (minimum number of shuffle man players to be produced)
y >= 500 (minimum number of walk on players to be produced)

at the intersection points, these constraints are calculated as shown in the following table.

                   hours of           hours of     number of              number of
                   manufacturing      shipping     shuffle man players    walk on players
   
(300,500)               420              130             300                    500
(300,850)               630              200             300                    850
(1000,500)              700              200             1000                   500

hours of manufacturing had to be less than or equal to 750 and it is.
hours of shipping had to be less than or equal to 200 and it is.
number of shuffle man players produced had to be greater than or equal to 300 and they are.
number of walk on players produced had to be greater than or equal to 500 and they are.

all the constrains are met.

if the profit on the shuffle man players is reduced to $16.00, then the objective function has to be re-analyzed with the new numbers as follows:

points of intersection            p = 16x + 15y
(300,500)                             12,300
(300,850)                             17,550
(1000,500)                            23,500 *****

note that the constraints did not change.
only the objective function was changed.

profit is maximized when 1000 shuffle man players are produced and 500 walk on players are produced.

this is the same as when the profit on the shuffle man players was $20.000.
in this case, it didn't make a difference.