In this video, I will be solving this maximization problem using this simplex tableau setup. Writing it in standard form, we add slack variables to the constraints because they are less than or equal to constraints, and also change the inequalities to equalities. The coefficients of the slack variables will be zeros in the objective function, and all the variables will be non-negative.
Since we have two decision variables in the original problem, The simplex method starts by setting two of these four variables to zeros, then solving for the values of the other two. For example, if we set x2 and s1 to 0, then x1 equals 8. Plugging that into the second equation, we obtain s2 equals negative 12. This is called a basic solution. However, it is not feasible because s2 equals negative 12 violates the non-negativity requirement. x2 and s1 that are set to 0 here are called non-basic variables, while X1 and X2 are called basic variables. Usually we start by setting X1 and X2 to 0. In that case, S1 will be 16 and S2 will be 12. In essence, we've made X1 and X2 non-basic, so that S1 and S2 are the basic variables.
This is called a basic feasible solution. Feasible because it satisfies non-negativity as well. To set this up in a simple XW, we can begin with the objective coefficient rho.
which we call the C row or the Cj row. Then the coefficients of the variables in the constraints, which we refer to as the A matrix. And their right sides, called the B column or quantity column. Since S1 and S2 have 1 in their columns, with the other value being 0, they are called basic variables. These are also referred to as unit columns.
Next, we place the basic variables in a column called basis here. And place the objective function coefficients next to them in a column we refer to as the Cb column. This shows that the initial basic feasible solution is S1 equals 16 and S2 equals 12. Next, we introduce the Zj row whose values are calculated by multiplying the Cb values by the corresponding column values and adding the results.
So for X1, it will be 0 times 2 plus 0 times 3 which gives 0. And for X2, 0 times 4 plus 0 times 2 which again is 0. And it will be 0 for the rest as well. our current objective function value will also be zero here. The Zj value for basic variables represents their unit contribution to the objective function value or profit.
But for the non-basic variables, it represents the amount of profit forgone or given up if a unit of the variable is added to the current solution. Next, we have the Cj minus Zj row which is calculated by taking each objective coefficient minus the Zj value. It represents the net change in the value of the objective function.
or profit if one unit of each variable enters the solution. So it is referred to as the net evaluation rule. For example, if X1 enters the basis and its value increases by 1, then the objective function increases by 7. What we now have here is called the initial simplex tableau.
It has a basic feasible solution X1 and X2 equals 0, S1 equals 16, and S2 equals 12. X1 and X2 are equal to 0 because they are the non-basic variables. We now perform iterations until all values in the net evaluation row are either negative or 0. This happens when we reach an optimal solution. Next, to determine which of the non-basic variables to make basic, we select the entry with the highest positive value in the net evaluation row.
That is the variable that provides the largest net improvement to the objective function. In this case, the variable is X1 with the largest value of 7 here. If there is a tie, that is, if there is another 7 on this row, you can select any of them but for consistency, we prefer the leftmost one. So X1 would be the new basic variable entering the basis.
We refer to the corresponding column as the key column or pivot column. But which current basic variable will X1 replace? S1 or S2?
To determine that, we calculate ratios of the B column values relative to their corresponding pivot column values and choose the row with the minimum value. For the first row, the ratio is 16 over 2 which gives 8. And for the second row, the ratio is 12 over 3 which gives 4. The minimum of these two is 4. Therefore, S2 will be leaving the basis to be replaced by X1. This row with the minimum value is called the Key Row.
or pivot row and the value at the intersection of the pivot row and pivot column is referred to as the key element or pivot element. This again is the initial simplex tableau and 3 here is a pivot element. We will perform the first iteration down here. As noted earlier, S2 left the basis and has been replaced by X1 while S1 is still in the basis. The coefficient of S1 in the objective function is 0 and the coefficient of X1 is 7. We now apply what we call elementary row operations to manipulate the tableau element so that the pivot column becomes a unit column.
In essence, we convert the pivot element to 1 and the other values in that column to 0. To do that, we divide all the entries in the pivot row by the pivot element which is 3. So 3 divided by 3 is 1. 2 divided by 3 is 2 thirds. 0 over 3 is 0. 1 over 3 is 1 third. And 12 over 3 is 4. Next, we need to convert these two to 0, either by adding or subtracting a multiple of the unit pivot element from it. And whatever operation we perform to make these two a 0, we perform it on all other elements in that row.
Now to make these two a 0, we can multiply this 1 by 2 and subtract it from these two. In essence, the elementary row operation is this. We take a row 1 element. subtract 2 times the corresponding new row2 element and assign the result to the new row1 element.
So 2 minus 2 times 1 is 0 as advertised. 4 minus 2 times 2 thirds is 8 thirds. 1 minus 2 times 0 is 1. 0 minus 2 one-third is negative two-thirds. And 16 minus 2 times 4 is 8. For Zj, we take the sum of the products of the objective coefficients of the basic variables and the columns.
So for the first column, we have 0 times 0 plus 7 times 1, which gives 7. For column X2, we have 0 times 8 thirds plus 7 times 2 thirds, which gives 14 thirds. 0 times 1 plus 7 times 0 gives 0. This one gives 7 thirds. And for the column B, we have 0 times 8 plus 7 times 4, which gives 28. And that is the profit for the current solution. For the net evaluation row, we compute coefficients minus Zj values. 7 minus 7 gives 0. 6 minus 14 thirds gives 4 thirds.
0 minus 0 gives 0. 0 minus 7 thirds gives negative 7 thirds. The first iteration is now done. We have a feasible solution of S1 equals 8, X1 equals 4, and the objective function value is 28. This is however not optimal yet since we still have a positive value in the net evaluation row, indicating that the profit can still improve.
Recall that for our optimal solution, each Cj minus Zj must be less or equal to 0. Hence, we move on to our next iteration. The new pivot column again will be the one with the most positive net evaluation entry. That is the variable that will bring the greatest improvement to the objective function value which is x2 in this case.
To determine the pivot row, we divide the B column values by the positive pivot column values and select the row with the minimum ratio. So, 8 divided by 8 8 thirds is 8 times 3 over 8 which gives 3. And 4 divided by 2 thirds is 4 times 3 over 2 which gives 6. The minimum of the two ratios is 3. Therefore, the S1 row is the pivot row. If there is a tie in the ratios, that is, suppose this 6 is also a 3, we can choose any of the two, but we'll prefer to choose the topmost one for consistency. Now, recall that the basic variable in the pivot row will be leaving the basis.
and the non-basic variable in the pivot column will be entering it. In essence, S1 will be leaving the basis and X2 will be replacing it. And 8 over 3 is the key of pivot element as it is at the intersection of the pivot row and pivot column. For the next iteration, X2 replaces S1 here and will place its objective function coefficient 6 in the CB column here.
X1 stays with its coefficient of 7. Next, we convert the pivot element to 1 in the new tableau by dividing the entries in the current pivot column by 8 thirds. That is multiplying them by 3 over 8. So 3 over 8 times 0 is 0. 3 over 8 times 8 thirds is 1 as expected. 3 over 8 times 1 is 3 over 8. 3 over 8 times negative 2 thirds is negative 1 quarter.
And 3 over 8 times 8 is 3. Next, we make this column a unit column by making this entry in row 2, 0. To do that, we multiply this new row 1 by 2 thirds and then subtract it from the current row 2. That is, all row 2 values minus 2 thirds times new row 1 values will be assigned to the new row 2. So, 2 thirds minus 2 thirds times 1 equals 0 as required. For x1 column, 1 minus 2 thirds times 0 is 1. For s1 column, 0 minus 2 thirds times 3 over 8 is negative 1 quarter. 1 over 3 minus 2 thirds times negative 1 over 4 is half. And for the B column, 4 minus 2 thirds times 3 equals 2. Next, we calculate each cj value by multiplying the basic objective coefficients by the column entries and adding the results. So 6 times 0 plus 7 times 1 equals 7. 6 times 1 plus 7 times 0 equals 6. 6 times 3 over 8 plus 7 times negative 1 quarter equals 1 half.
6 times negative 1 quarter plus 7 times 1 half equals 2. And for the B column, 6 times 3 plus 7 times 2 equals 32. And that's the objective function value for this iteration. For the net evaluation row, we do 7-7 which gives 0, 6-6 also gives 0, 0-1-1-1 gives negative 1, and 0-2 gives negative 2. Since all cj-zj elements are non-positive, we can't improve on this solution. So this is our optimal solution.
x1 equals 2, x2 equals 3, s1 and s2 will be 0s because they are non-basic, and the objective function value will be 32. Now, let's see how this relates to the graphical solution of the LP problem. The basic solutions are the extreme points, labeled 1 to 6. The basic feasible solutions are the extreme or corner points of the feasible region, labeled 1 to 4 in green. The solution in the initial simplex tableau occurs at corner point 1, where x1 and x2 are zeros, as they are non-basic.
S1 is 16, S2 is 12, and the value of the objective function is zero. After the first iteration, we obtain a solution of x1 equals 4, s1 equals 8. Both x2 and s2 were non-basic and therefore zeros. And that corresponds to point 2 here with an objective function value of 28. The result of the final iteration corresponds to the optimal solution point at corner 3 where x1 is 2 and x2 is 3. s1 and s2 are non-basic and therefore zeros, and the optimal objective function value is 32. In summary, here are the steps we used in solving the maximization problem using simplex tableau.
We converted the linear program problem into standard form by adding slack variables. We developed the initial simplex tableau with x1 and x2 being non-basic variables. We selected the non-basic variable with the largest positive value in the net evaluation row and made it a basic variable. That gave us the pivot column. We then calculated the ratio of the B column to the pivot column values.
The minimum non-negative ratio there determined the pivot row, which corresponds to the value leaving the basis. We performed elementary row operations to make the column for the new basic variable a unit column. We repeated steps 3, 4, and 5 until the net evaluation row has no positive entry, which means we had an optimal solution.
And that's it. Thanks for watching.