Dionis Mucollari 8-4 January 13, 2011

Linear Programming

In this section you will learn to…

Ø  Solve Linear Programming problems

By…

Ø  Writing and graphing a set of constraints for a linear programming problem.

Ø  Using linear programming to find a max or min value of and objective function.

Words you will need to know:

  1. Linear Programming
  2. Constraints
  3. Objective function
  4. The Corner Point principle
  5. Feasible Region

Definitions:

What is Linear Programming?

Linear programming is a method of finding a maximum or minimum value of a function that satisfies a given set of conditions called constraints. The solution to the set of constraints can be graphed as a feasible region.

What are constraints?

In linear programming terms, constraints are just the inequalities in the linear programming problem.

What is the objective function?

Objective functions are the functions that are to be maximized or minimized in the problem

What is the Corner Point Principle?

When doing linear programming you look for the maximum and minimum values of the system, the corner point principle states that when graphed, the maximum and minimum values of the system are located at the vertices of the feasible region.

What is the feasible region?

When graphed, a system of linear equations has an area that meets the constraints of all the inequalities and contains all the possible solutions to the system of linear equations.

Performing linear Programming

Step 1: Write out a system of inequalities for the problem you are trying to solve.

Here is a problem we can solve:

Caliyah is going to have a party. She wants to get cheese crackers and punch. Her mother gave only $40 to buy as many boxes of crackers and bottles of punch as she can without them weighing more than 30 lbs. Cheese cracker boxes cost $4 each and weigh 1 lbs each. Bottles of punch cost $1.50 each and weigh 4 lbs each. How many boxes of crackers and bottles of punch can she get without exceeding the limits?

Let X= number of bottles of punch

Let Y= number of boxes of crackers

Now we set up a system of linear inequalities. Lets let the first one deal with weight. Punch weighs 4 lbs. and crackers weigh 1 lbs. each and combined they can’t weigh more than 30 lbs. This would be shown as…

30 ³ Y+4X

Now lets let the second one deal with price. Caliyah can’t spend more than $40, punch costs $1.50 each and crackers cost $4 each. We would show this as

40 ³ 4Y+1.5X

Since this is a real life situation and there can’t be negative bottles of punch or negative boxes of crackers, you must include these two inequalities…

Y ³ 0

X ³ 0

When this system of linear inequalities is graphed it looks something like this…

30 ³ Y+4X 40 ³ 4Y+1.5X Y ³ 0 X ³ 0

The green part is the feasible region all the points in there fit all the inequalities or constraints.

Solving:

The question asks that Caliyah bring home the maximum amount of each item without exceeding any of the constraints, thus our objective function is born.

I=X+Y

Total amount of numbers = Number of bottles of punch + number of boxes of crackers

This will give us the answer to the question and it is found at one of the vertices of the graph, which are indicated on our graph as white circles.

When you plug those coordinates of the vertices into the equation you will get four answers, this particular problem is asking us to find the maximum amount of items so the largest answers is the answer to the problem. This can be shown more easily in a table.

Coordinates of the Vertices / Plugged into the objective function / Total
0,0 / 0+0 / 0
7.5,0 / 7.5+0 / 7.5
5.5,7.93 / 5.5+7.93 / 13.43
0,10 / 0+10 / 10

What Caliyah must do is buy 5.5 bottles of punch and 7.93 boxes of crackers. Note that since this has to do with the real world you won’t be able to buy ½ a bottle of punch or .93 boxes of crackers so the answer would be more like 5 bottles of punch and 8 boxes of crackers because those are the largest amount of items that still fit all inequalities and don’t go into decimals.

Now that we’ve done one together try doing one yourself…

Solution:

OR

Now Do this…

Solution:

And finally, do this..

Ø  First make your system of inequalities

Ø  Then graph the feasible region

Ø  Then look at what the question is asking you to do and form a objective function

Ø  Now take the vertices of the feasible region and plug them into the objective function.

*Hint: Using a table will really help and this problem is asking for a maximum value.

The Solution is…

The community should buy 9 large buses and 0 little buses for the objective function to be maximized.