0
1.8kviews
Solve the LP problem by using Simplex method:

Maximize $Z = 5X_1 + 3X_2$

Subject to $X_1 + X_2 ≤ 2 \\ 5X_ + 2X_2 ≤ 10 \\ 3X_1 + 8X_2 ≤ 12\\ X_1, X_2 ≥ 0$

1 Answer
0
23views

We have to maximize the function $Z = 5X_1 + 3X_2$

All the constraints are of the type ‘≤’ (i.e. less than). Hence, slack variables (Si) have to be introduced:

$X_1 + X_2 + S_1 = 2 \\ 5X_1 + 2X_2 + S_2 = 10 3X_1 + 8X_2 + S_3 = 12$

So the maximization function now becomes: $Z = 5X_1 + 3X_2 + 0S_1 + 0S_2 + 0S_3$

The matrix can now be formed as follows:

enter image description here

Cj values are the co-efficients of the variables in the maximization function.

As can be seen, $S_1, S_2 \ \& \ S_3$ form an identity matrix, & hence they enter the base:

enter image description here

NOTE: The Cj – Zj values (i.e. the row pertaining to “Cj – Zj →”) are obtained as follows:

enter image description here

$Cj – Σ(co-efficient of S_i × bij)$

So first Cj – Zj value (of the first column i.e. $X_1$) is obtained as:

$C_1 – \{(a_1 × b_{11}) + (a_2 × b_{21}) + (a_3 × b_{31})\}$

We can now proceed with the first iteration as follows:

enter image description here

The value in this box is obtained by multiplying the value of the co-efficient in the base, with its corresponding RHS value (in the same row), & adding up all these multiplied values for all the rows present (in this case, three rows). So in this case, the value ‘0’ is obtained by: $(0 × 2) + (0 × 10) + (0 × 12) = 0$

From the above table, the largest of the Cj – Zj values becomes the entering variable. Since 5 is largest, $X_1$ enters. The corresponding ‘θ’ values are then calculated:

(NOTE: θ = RHS value ÷ corresponding row value of entering variable)

enter image description here

So $θ_1 = 2 ÷ 1 = 2, θ_2 = 10 ÷ 5 = 2, θ_3 = 12 ÷ 3 = 4$

Now we have to select minimum, non-negative θ value as the leaving variable. However, both $S_1 \ \& \ S_2$ can be selected. However, we select $S_1$ as the leaving variable, since the pivot element is already ‘1’ & hence reduces number of calculations.

Since $X_1$ has entered the base in place of $S_1$, an identity matrix has to be formed of $X_1, S_2 \ \& \ S_3$. The operations carried out to do that is shown in the next table. Further, the 2nd iteration is also carried out in the next table.

enter image description here

The iteration ends here, since all the Cj – Zj values are zero, or less than zero.

Therefore: $X_1 = 2, X_2 = 0, \ \& \ Z_{\max} = 10$

Please log in to add an answer.