Linear Programming

Linear Programming: As we have in the past, we will pose a problem and follow it through the steps of the model:

We have two types of boxed sets; the Aristorocks and the Millionaire sets. We have two people working in the boxing section and one person working in the shipping department. The Aristorocks take 2 hours to box and 3/2 hours to pack and ship. The Millionaires take 3 hours to box, but only 1/2 hour to pack and ship. Mr. Rock has decreed that he will not authorize any overtime. We make $50 per Aristorockand $60 per Millionaire. How many of each type should we produce each week to maximize profit?

We start by writing the Objective Equation. The objective equation is an equation that defines the thing we want to maximize (or minimize) in terms of the variables. I always explicitly write the variables down somewhere to the right of the equation so I won't mix them up later in the model. I also always use subscripts to identify them as is the convention when programming or using spread sheets. In this problem we want to maximize the profit:

P = 50* X1 + 60* X2

where,

X1 = the number of Aristorock sets per week

X2 = the number of Millionaire sets per week

The next step is to write the constraints. I designate the constraints using C and subscripts. (Sometimes it is easiest to write the inequality and the value first, see purple below.)

C1 2*X1 + 3*X2 < 80

C2 (3/2)*X1 + (1/2) *X2 < 40

Then we should check each of the constraints and the objective equation for linearity (no exponents other than 1). Our's are ok so we proceed

to plot the feasible region: I will detail the process for C1:

A line can be defined by just two points. So choose any two points and draw the line represented by the equality part of C1. The easiest two points are when X1 = 0 and when X2 = 0.

C1 2*X1 + 3*X2 < 80

Let X1 = 0 2 * 0 + 3 * X2 = 80

X2 = 80/3

(0,80/3)

Let X2 = 0 2 * X1 + 3 * 0 = 80

X1 = 40

(40,0)

Now we determine which side of the line the inequality exists on. To do that we pick any point not on the line and check if it satisfies the inequality. If it does, then that entire side of the line satisfies the inequality. Many times I choose the point (0,0) since it is so easy to calculate:

C1 2*X1 + 3*X2 < 80

2 * 0 + 3 * 0 < 80

0 < 80

Okay, (0,0) satisfies the inequality. So everything on that side of the line satisfies the inequality. See the green area.

We only use the first quadrant since negative values for the variables make no sense. How could we make a negative number of sets?

Now we do the same with the constraint (3/2)*X1 + (1/2) *X2 < 40.

Now we determine the feasible region by seeing which portion of the graph satisfies ALL of the constraints. For our problem the feasible region is shown below in green:

Now we utilize either the isoprofit or corner point method to determine the point within the feasible region which gives us the maximum profit. I will demonstrate both. Let's start with the isoprofit method: Let P be some arbitrary value and plot P on the axis. I choose 2400 as an arbitrary value for P. After you do several problems you will start to get the hang of what range to select for P, such that it is relatively close to the feasible region. We graph P the same way as we graphed the constraint lines (two points). P = 50 * X1 + 60 * X2

2400 = 50 * X1 + 60 * X2

What happens if we lower the value of P slightly? The slope of the line remains the same but the intercept is reduced by a small amount. If we do that several times we soon realize that the lines will drop until we intersect some point in the feasible region. The first point we touch will be the point of maximum profit since we are reducing the profit a little each time. We can also see that the point encountered will be a corner point. In this case it is the point B:

The only problem we have now is that we know the X1 and X2 values (coordinates) for A, C, and D, but not B. So we have to determine the point B by the simultaneous solution of two linear equations. Back in algebra we learned to do that by substitution or elimination. I'll review both methods:

Elimination: The idea is to reduce two equations to a single equation in one variable. We start with the equality versions of C1 and C2 .

C1 2*X1 + 3*X2 = 80

C2 (3/2)*X1 + (1/2) *X2 = 40

If we subtracted C2 from C1 we would end up with yet another equation which had both variables. So before we subtract, we must insure that the coefficients of one of the variables are the same in both equations. To do that we multiply C1 by 3 and C2

by 4.

C1^ 6*X1 + 9*X2 = 240

C2^ - (6*X1 + 2 *X2 = 160)

0*X1 + 7*X2 = 80

X2 = 80/7 = 11.43

Then we substitute 80/7 into either of the equations and solve for X1.

2*X1 + 3*X2 = 80

2*X1 + 3*80/7 = 80

2*X1 = 80 - 3*80/7

X1 = (80 - 3*80/7)/2

X1 = 40 - 120/7 = 22.86

Substitution: The idea for substitution is to solve one of the equations for a variable then substitute that variable into the other equation.

C1 2*X1 + 3*X2 = 80

C2 (3/2)*X1 + (1/2) *X2 = 40

Solve the first