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$

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:

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:

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

$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:

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)

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.

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$