Answer to Question #283394 in Operations Research for Andinet

Question

9. A company manufactures two products P1 and P2. Profit per unit for P1 is $200 and for

P2 is $300. Three raw materials M1, M2 and M3 are required. One unit of P1 needs 5 units of M1 and 10 units of M2. One unit of P2 needs 18 units of M2 and 10 units of M3. Availability is 50 units of M1, 90 units of M2 and 50 units of M3.

A. Formulate as LPP

B. Find the optimal by using simplex method

Answer 1

Solution:

Let x₁ - number of units for P1, x₂ - number of units for P2.

LPP:

maximize z = 200*x₁ + 300*x₂

Subject to 5x₁ $\le$ 50;

10*x₁ + 18*x₂ $\le$ 90;

10x₂ $\le$ 50;

x₁, x₂ $\ge$ 0.

Next to add one slack variable for each inequality:

5x₁ + y₁ = 50;

10*x₁ + 18*x₂ + y₂ = 90;

10x₂ + y₃ = 50;

We rewrite the objective function z = 200*x₁ + 300*x₂ as -200*x₁ - 300*x₂ + z = 0

Then construct the initial simplex tableau. Each inequality constraint appears in its own row:

From the table above we can find basic solution: y₁ = 50, y₂ = 90, y₃ = 50, z = 0.

The most negative entry in the bottom row identifies the pivot column. This corresponds to x₂ , because -300 is most negative. Next calculate the quotients. The smallest quotient identifies a row. The element in the intersection of the column identified as x₂ and the row identified in this step is identified as the pivot element. Following the algorithm, in order to calculate the quotient, we divide the entries in the far right column by the entries in column x₂ , excluding the entry in the bottom row.

90:18 = 5 and 50:10 = 5. In this situation we have two equal values, let's choose the second row of the table above, but in general the smallest of the two quotients is needed.

Next make our pivot element by dividing the entire second row by 18. The result follows.

To obtain a zero in the entry first above the pivot element, we multiply the second row by -18/2 and add it to row 1. We get

To obtain a zero in the element below the pivot, we multiply the second row by 360 and add it to the last row:

We see that there are no more negative entries in the bottom row, we are finished. Because of positive values in the bottom row x₂ = 0 and y₂ = 0. Hence x₁ = 9 and z = 1800