Minimize $Z = 3X_1 - X_2$

Subject to $2X_1 + X_2 ≥ 2 \\ X_1 + 3X_2 ≤ 3 \\ X_2 ≥ 4 \\ X_1, X_2 ≥ 0$

Before starting to solve this problem, take a close look at the constraints.

We have $X_1 + 3X_2 ≤ 3 and X_2 ≥ 4$

Supposing $X_1$ is 0, which is the bare minimum value for $X_1$, since $X_1, X_2 ≥ 0$ specifies the non-negativity constraint.

So we have to find a value of $X_2$ such that it’ll be atleast equal 4 (according to $X_2 ≥ 4$) while at the same time being at most equal to 1, (according to $3X_2 ≤ 3, X_1 = 0$), while not being less than 0, due to the non-negativity constraint.

Quite logically, it follows that this is impossible, i.e. for $X_2$ to lie between 0 & 1, and to be atleast 4 or more. In other words, the solution will turn out to be infeasible.

Please note, the non-negativity constraint limits the range of the solution allowed. If solved graphically, you will notice a solution is actually present, but the solution does not lie in the first quadrant of the graph (does not satisfy $X_1, X_2 ≥ 0$) and hence the solution is infeasible.

The main solution is as follows:

We have to minimize the function $Z = 3X_1 - X_2$

The first and third constraints are of the type ‘≥’, hence we introduce surplus as well as artificial variables into them. The second constraint is of the type ‘≤’, hence we introduce a slack variable into it.

So the constraints become:

$2X_1 + X_2– S_1+ A_1 = 2 \\ X_1 + 3X_2+ S_2 = 3 \\ X_2– S_2 + A_2 = 4$

We convert the minimization function to a maximization function by multiplying the whole function by ‘-1’. So the minimization function becomes:

$Z = −3X_1+ X_2 + 0S_1 + 0S_2 +0S_3 – MA_1– MA_2$ which has to be maximized.

The sum is then solved as a usual simplex sum is solved.  

The iteration ends here, since all Cj – Zj values are negative, and it is not possible to find the next entering variable.

The presence of an artificial variable in the base indicates that the solution is infeasible.