Full version Linear Programming

Linear Programming

This print version free essay Linear Programming.

Category: Technology

Autor: reviewessays 23 November 2010

Words: 4238 | Pages: 17

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 equation for X1:

2*X1 + 3*X2 = 80

2*X1 = 80 - 3*X2

X1 = 40 - (3/2) * X2

Now substitute into the second equation:

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

(3/2)*(40 - (3/2)*X2)+ (1/2) *X2 = 40

3*(40-(3/2)*X2) + X2 = 80

120 - (9/2)*X2 + X2 = 80

(-7/2)*X2 = -40

X2 = 80/7

Amazing! We get the same value for X2. We calculate X1 the same way as before by substituting into either equation. I will not repeat that calculation.

So we find that by using either method, B = (22.86,11.43).

We will make 22.86 Aristorock sets and 11.43 Millionaire sets. The profit will be :

P = 50 * X1 + 60 * X2

P = 50 * 22.86 + 60 * 11.43

P = 1143 + 686

P = 1829

Now let's look at the second method to solve the model and that is the Corner Point Solution method. Here we must take advantage of the fact that the first point that the iso-profit lines will encounter is a corner point. Yet in this method we do not graph an iso-profit line. We just evaluate the profit at each corner and select the corner with the highest profit.

Point Coordinates (X1,X2) Profit (50 * X1 + 60 * X2)

A (0,26.67) 1600

B (22.86,11.43) 1829

C (26.67,0) 1333

D (0,0) 0

A) P = 50 * 0 + 60 * 26.67 = 1600

B) P = 50 * 22.86 + 60 * 11.43 =1829

C) P = 50 * 26.67 + 60 * 0 = 1333

D) P = 50 * 0 + 60 * 0 = 0

We see from the corner point analysis that the maximum profit does indeed occur at (22.86,11.43), the same point as we determined in the Isoprofit approach.

You might ask how we can produce 22.86 or 11.43 of anything. That is easily resolved by either one of two different explanations. The first is that the decimal portion of any unit can be regarded as a work-in-progress (to be resumed the next Monday). The second is that the numbers can be made integral by either rounding or by preserving the ratio of X1 to X2 .

Minimization: The author discusses minimization. It is exactly parallel to a maximization with the exception that we use a iso-cost line and approach the feasible region from below instead of from above.

Special Cases:

1) Infeasibility results from conflicting constraints. There is no feasible region and therefore there is no solution.

2) Unboundednous occurs when the feasible region extends forever. The solution is also unbounded and usually is of the form: Produce as many as possible.

3) Redundancy occurs when one constraint is overridden by another and is not required. This condition still results in a solution that can be derived from the model.

4) Alternate optimal solutions result from the condition in which the slope of the objective equation equals the slope of one of the constraints. It is easily recognized when the maximum profit occurs at two corner points. In this instance there are an innumerable number of optimal solution (all points on the line between the two corners). Any of these solutions will yield maximum profit.

Sensitivity: We can check the sensitivity of any parameter in the model by substituting a variable for that parameter and equating slopes of the profit and constraint lines. Let's look at our example above and see how sensitive the value for the profit resulting from Millionaires is to the solution. If we look at several iso-profit lines, we can see how the decision might change:

P is the original iso-profit line and clearly the solution is point B. If we look at P1 we can see the solution would change to point A. But with P2 the solution is indeterminant (alternate optimal solutions). The slope of P2 is the slope at which the decision changes and it is also equal to the slope of C1. Those two facts allow us to calculate the value for the profit of Millionaires which would change the decision. Since the slope does not involve the constant terms we can ignore them and set the slopes of the objective equation equal to the slope of C1. Note that we have replaced 60 by a in the objective equation

50 * X1 + a * X2 = P

a * X2 = - 50 * X1 + P

X2 = (- 50 / a) * X1 + P / a

slope = (- 50 / a)

C1

2*X1 + 3*X2 = 80

3 * X2 = - 2 * X1 +80

X2 = (- 2 / 3) * X1 +80

slope = (-2 / 3)

- 50 / a = - 2 / 3

a = - 50 * (- 3 / 2)

a = 75

This tells us that if the net from each Millionaire set was 75 instead of 60 the decision would change (sensitive within $15). Our model is not very sensitive with respect to amount of profit on each Millionare set in this case but you can see how this analysis could reveal some very important sensitivities.

More than two variables: I would like to discuss the general topic of linear programming and not restrict it to two variables. Let's consider three variables for a moment. In three variables the graph would be three dimensional and the figures representing linear objective equations and linear constraints would be two dimensional (planes). If you think about a number of these constraints intersecting then you get something like a multipanelled soccer ball with the feasible region on the inside. As the objective iso-profit planes approach the ball they will touch it first at a corner point. It is not hard for a computer to quickly solve for the corner points then evaluate the profit at each point to determine the optimum coordinates. However there is a slightly different algorythm that most computer programs use which gives successively better approximations with each iteration and given the computational power, many iterations can be quickly calculated.

The process is also true for dimensions greater than three but the visual reference breaks down after 3-D. Excel has a solver function that allows us to do all this automatically including sensitivity. I found it a little difficult to set up initially but it gave me a handy tool for doing linear programming with any number of variables

EXAMPLES

1. The Marriott Tub Company manufactures two lines of bathtubs, called model A and model B. Every tub required blending a certain amount of steel and zinc; the company has available a total of 25,000 pounds of steel and 6,000 pounds of zinc. Each model A bathtub require a mixture of 125 pounds of steel and 20 pounds of zinc, and each yields a profit to the firm of $90. Each model B tub produced can be sold for a profit of $70; it in turn requires 100 pounds of steel and 30 pounds of zinc. Find, by graphical LP, the best production mix of bathtubs.

Objective Equation:

P = 90 * X1 + 70 * X2

where,

X1 = number of type A

X2 = number of type B

Constraints:

C1 125 * X1 + 100 * X2 < 25000

C2 20 * X1 + 30 * X2 < 6000

Feasible Region:

Iso-profit Solution:

Let P = 210

210 = 90 * X1 + 70 * X2

It looks like it might be point C, but it really is too close to tell so let's go to the corner point method.

Corner Point:

Before we can proceed we need to find the coordinates for point B. We do that by solving the constraint equations simultaneously:

125 * X1 + 100 * X2 = 25000 C1 multiply by 3

20 * X1 + 30 * X2 = 6000 C2 multiply by 10

375 * X1 + 300 * X2 = 75000 C1^

-(200 * X1 + 300 * X2 = 60000) C2^

175 * X1 = 15000

X1 = 1500 / 175

X1 = 85.7

20 * X1 + 30 * X2 = 6000

20 * 85.7 + 30 * X2 = 6000

30 * X2 = 6000 - 20 * 85.7

X2 = 4286 / 30

X2 = 142.9

Corner Coordinates Profit

A (0,200) 14000

B (85.7,142.9) 17715

C (200,0) 18000

D (0,0) 0

P = 90 * X1 + 70 * X2

We guessed right with the iso-profit line. Point C is the greatest profit. The best production mix is no type B and 200 type A

2. The Sweet Smell Fertilizer Company markets bags of manure labeled "not less than 60 pounds dry weight." The packaged manure is a combination of compost and sewage wastes. To provide good-quality fertilizer, each bag should contain least 30 pounds of compost but not more than 40 pounds of sewage. Each pound of compost costs Sweet Smell 5 cents and each pound of sewage costs 4 cents. Use a graphical LP method to determine the least cost blend of compost and sewage in each bag.

This is a minimization. We do it in a similar fashion as optimization.

Objective Equation:

C = .05 * X1 + .04 * X2

Constraints:

C1 X1 + X2 > 60

C2 X1 > 30

C3 X2 < 40

Feasible Region:

Iso-Cost line:

C = .05 * X1 + .04 * X2

Let C = 2

2 = .05 * X1 + .04 * X2

Here it is easier to see that point Bis the minimum cost. So we must calculate the coordinates at that point only. No need to do a corner point analysis. The two constraints that meet at Bare C1 and C2.

C1 X1 + X2 = 60

C2 X1 = 30

X1 + X2 = 60

30 + X2 = 60

X2 = 30

B = (30,30)

C = .05 * X1 + .04 * X2

C = .05 * 30 + .04 * 30

C = 2.70

So minimum cost is 30 lbs of compost and 30 lbs of sewage at $2.70 a bag.

3. Consider the following LP formulations. Using a graphical approach, determine

a. which formulation has more thanone optimal solution.

b. which formulation is unbounded.

c. which formulation is infeasible.

d. which formulation is correct as it.

Formulation 1

maximize: 10X1 + 10X2

subject to: 2X1 ЎЬ 10

2X1 + 4X2 ЎЬ 16

4X2 ЎЬ 8

X1 ЎЭ 6

Formulation 2

maximize: X1 + 2X2

subject to: X1 ЎЬ 1

2X2 ЎЬ 2

X1 + 2X2 ЎЬ 2

Formulation 3

maximize: 3X1 + 2X2

subject to: X1 + X2 ЎЭ 5

X1 ЎЭ 2

2X2 ЎЭ 8

Formulation 4

maximize: 3X1 + 3X2

subject to: 4X1 + 6X2 ЎЬ 48

4X1 + 2X2 ЎЬ 12

3X2 ЎЭ 3

2X1 ЎЭ 2

The easiest way to see these is to look at the feasible regions and the iso-profit lines:

Formulation 1:

I just put C1 and C4 on the graph. You can see that they never intersect. c) the formation is infeasible!

Formulation 2:

In this formulation we see two of the four special cases cited by the author. a) Since the slope of P and C3 are the same (parallel lines), there are more than one optimal solution. The other special case is redundancy. C2 is redundant since all points satisfying C3 also satisfy C2.

Formulation 3:

This one is easy. The feasible region extends forever to the upper right. Since this is an Maximization problem, b) it is unbounded. If it were a minimization problem than it would be OK since we would approach the region with an iso-cost line from the lower left!

Formulation 4:

Here we have redundant constraints again but we still have a single solution. d) the formulation is correct as is.

4. Serendipity

The three princes of Serendip

Went on a little trip.

They could not carry too much weight;

More than 300 pounds made them hesitate.

They planned to the ounce. When they returned to Ceylon

They discovered that their supplies were just about gone

When, what to their joy, Prince William found

A pile of coconuts on the ground.

"Each will bring 60 rupees," said Prince Richard with a grin

As he almost tripped over a lion skin.

"Look out!" cried Prince Robert with glee

As he spied some more lion skins under a tree.

"These are worth even more -- 300 rupees each

If we can just carry them all down to the beach."

Each skin weighed fifteen pounds and each coconut, five,

But they carried them all and made it alive.

The boat back to the island was very small

15 cubic feet baggage capacity -- that was all.

Each lion skin took up one cubic foot

While eight coconuts the same space took.

With everything stowed they headed to sea

And on the way calculated what their new wealth might be.

"Eureka!" cried Prince Robert, "Our worth is so great

That there's no other way we could return in this state.

Any other skins or nut that we might have brought

Would now have us poorer. And now I know what --

I'll write my friend Horace in England, for surely

Only he can appreciate our serendipity."

Formulate and solve Serendipity by graphical LP in order to calculate "what their new wealth might be."

Problem 4. As I stated in the assignment, this is my favorite problem in the book. It is not a very difficult one (except for a small sticky point in one of the constraints), but the way it is posed is great. Let's tackle the solution:

Objective Equation:

P = 60 * X1 + 300 * X2

where,

X1 = number of coconuts

X2 = number of lion skins

Constraints:

C1 5 * X1 + 15 * X2 < 300

C2 (1/8) * X1 + 1 * X2 < 15

Many people try to use 8 instead of 1/8

Feasible Region:

Iso-profit Solution:

Let P = 4800

P = 60 * X1 + 300 * X2

By Iso-profit we can see that the solution is at the intersection of C1 and C2.

Before we can proceed we need to find the coordinates for that point. We do that by solving the constraint equations simultaneously:

5 * X1 + 15 * X2 = 300 C1

(1/8) * X1 + 1 * X2 = 15 C2 multiply by 40

5 * X1 + 15 * X2 = 300 C1

-(5 * X1 + 40 * X2 = 600) C2^

-25 * X2 = -300

X2 = -300 / (-25)

X2 = 12

5 * X1 + 15 * X2 = 300

5 * X1 + 15 * 12 = 300

5 * X1 = 300 - 15 * 12

X1 = 120 / 5

X1 = 24

P = 60 * X1 + 300 * X2

P = 60 * 24 +300 * 12

P = 5040

The princes brought back 24 coconuts and 12 lion skins with a profit of 5040 rupees.

QUIZ

My wife was disappointed that she couldn't find a time to meet you. She was impressed with the work you did on the inventory control problems we've been having. In fact she asked me to have you look at a couple more problems we've been having. Please complete the following tasks since your continued employment is, as always, contingent upon the continued successful completion of the projects I assign to you.

Miss Pebbles informs me that we have begun to sell both Family Rock CDs and Rock Hair. Unfortunately, for the next several months we must meet our initial promotional contract prices which were let at a loss of $.80 per Family Rock CD and $.20 per Rock Hair. I am concerned about losses and want them minimized. We have contractual obligations we have to meet. Our independent distributors require at least 1000 total (Family Rock CDs and Rock Hair) sale units per week and at least 400 Family Rock CDs and at least 300 Rock Hair per week.

a) Determine the best product mix per week that will meet our contractual obligations and minimize our loss. Let me know what our weekly loss will be until we complete these promotional contracts.

John Stones has been looking at our Aristorock and Millionaire lines. Our profit from a Aristorock set is $70 and our profit from a Millionaire set is $90. Inventory restrictions limit us to 50 or fewer Millionaires week. We are currently using the same boxes for both of the sets and we get 120 boxes per week from our supplier (total number of both sets). Mildred (have I introduced you to my wife yet?) demands, oops, I mean, strongly suggests, that we produce more Aristorocks than Millionaires.

b) Determine the optimum mix of products that will satisfy my wife, Mildred, and let me know the projected gain.

c) I am not sure about John's $90 figure for the Millionaires. How much would that have to change to alter our decision on product mix? (Do a sensitivity analysis.)

My wife was disappointed that she couldn't find a time to meet you. She was impressed with the work you did on the inventory control problems we've been having. In fact she asked me to have you look at a couple more problems we've been having. Please complete the following tasks since your continued employment is, as always, contingent upon the continued successful completion of the projects I assign to you.

Miss Pebbles informs me that we have begun to sell both Family Rock CDs and Rock Hair. Unfortunately, for the next several months we must meet our initial promotional contract prices which were let at a loss of $.80 per Family Rock CD and $.20 per Rock Hair. I am concerned about losses and want them minimized. We have contractual obligations we have to meet. Our independent distributors require at least 1000 total (Family Rock CDs and Rock Hair) sale units per week and at least 400 Family Rock CDs and at least 300 Rock Hair per week.

a) Determine the best product mix per week that will meet our contractual obligations and minimize our loss. Let me know what our weekly loss will be until we complete these promotional contracts.

John Stones has been looking at our Aristorock and Millionaire lines. Our profit from a Aristorock set is $70 and our profit from a Millionaire set is $90. Inventory restrictions limit us to 50 or fewer Millionaires week. We are currently using the same boxes for both of the sets and we get 120 boxes per week from our supplier (total number of both sets). Mildred (have I introduced you to my wife yet?) demands, oops, I mean, strongly suggests, that we produce more Aristorocks than Millionaires.

b) Determine the optimum mix of products that will satisfy my wife, Mildred, and let me know the projected gain.

c) I am not sure about John's $90 figure for the Millionaires. How much would that have to change to alter our decision on product mix? (Do a sensitivity analysis.)