Linear Programming: Simplex Method Algebraic Solution

The problem is a linear programming problem.
The objective function to maximize is:

Subject to the constraints:

We will solve this problem using the algebraic method (simplex method). First, we convert the inequalities into equalities by introducing slack variables and .

The problem becomes:
Maximize
Subject to:

We can write the objective function as .

Initial Simplex Tableau:

Step 1: Identify the entering variable.
The entering variable is the non-basic variable with the most negative coefficient in the Z-row. In this case, it is with a coefficient of -2. So, is the entering variable.

Step 2: Identify the leaving variable.
To find the leaving variable, we calculate the ratio of the RHS to the coefficients of the entering variable in each constraint row.
For :
For :
The smallest non-negative ratio is 1, which corresponds to the row. So, is the leaving variable. The pivot element is 3 (the coefficient of in the row).

Step 3: Perform pivot operations.
Make the pivot element 1 by dividing the row by 3.
New row (now row):

Now, make all other elements in the column zero.

New Simplex Tableau:

Step 4: Check for optimality.
There is still a negative coefficient in the Z-row (-1/3 for ). So, the solution is not optimal. We repeat the process.

Step 1: Identify the entering variable.
The entering variable is (coefficient -1/3).

Step 2: Identify the leaving variable.
Calculate ratios:
For :
For :
The smallest non-negative ratio is , which corresponds to the row. So, is the leaving variable. The pivot element is .

Step 3: Perform pivot operations.
Make the pivot element 1 by multiplying the row by .
New row (now row):

Now, make all other elements in the column zero.

Final Simplex Tableau:

Step 4: Check for optimality.
All coefficients in the Z-row are non-negative. Therefore, the current solution is optimal.

The optimal values for the decision variables are:

The maximum value of the objective function is:

Let’s verify the solution with the original objective function:
.

And verify the constraints:
(satisfied)
(satisfied)
(satisfied)

The final answer is .