Please help explain to me linear programming?

Question

I have a chapter test tomorrow and I cannot understand how to find the maxinum profit using linear programming. Here's a similar question to the one on the test. It's not homework. Please help. Thanks.

A lunch stand makes $.75 profit on each chef's salad and a $1.20 on each Caesar salad. On a typical weekday, it sells betwween 40 to 60 chef's salads and between 35 and 50 Caeser salads. The total number has never exceeded 100 salads. How many of each type should be prepared in order to maximize profit?

Answer 1

Start by defining variables.

Let x denote the number of chef's salads, and let y denote the number of Caesar salads. We're told the profit per salad for the two types, so we can write the objective function immediately:

P(x,y) = 0.75x + 1.2y

This is the function we want to maximize.

"it sells between 40 and 60 chef's salads" means

40 ≤ x ≤ 60, or equivalently,

x ≥ 40 and x ≤ 60

"it sells between 35 and 50 Caesar salads" means

35 ≤ y ≤ 50 or equivalently

y ≥ 35 and y ≤ 50

"The total number has never exceeded 100 salads" means

x + y ≤ 100

(We would usually need to add the constraints x ≥ 0 and y ≥ 0 because negative quantities of salads make no sense, but we already have x ≥ 40 and y ≥ 35 so the "non-negativity" constraints aren't needed here.)

Now, you need to find the region of the xy-plane that satisfies all of these constraints. This is sometimes called the feasible region. It will be a polygon-shaped region. It can be proved that the maximum and minimum values of the objective function over the feasible region occur at vertices of this polygon. So you need to find where those vertices are.

40 ≤ x ≤ 60 defines a vertical "band" between x=40 and x=60. 35 ≤ y ≤ 50 defines a horizontal "band" between y=35 and y=50. The intersection of these is a rectangle whose corners are at (40,35), (60,35), (40,50), and (60,50). Finally, graph x+y=100, which is a line that connects the points (100,0) and (0,100). Note that this line cuts through the rectangle mentioned above. Since the constraint is x+y ≤ 100, its graph is the part of the xy-plane below and to the left of the line. The feasible region is that part of the rectangle mentioned above that is below and to the left of the line x+y=100. You really do need to graph this, fairly carefully (not just a sketch) to see what's happening. The line cuts off the upper right corner of the rectangle.

Now, find the vertices of the feasible region. You will find that they are (40,35), (40,50), (50,50), (60,40), and (60,35). Evaluate your objective function P(x,y) = 0.75x + 1.2y at each of these points. The point that gives the largest value of P is the choice that maximizes profit and satisfies all of the constraints.