In this video, I will be solving this maximization LP problem using this simplex tableau set up. 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 0s in the objective function and the all the variables will be nonnegative. Since we have two decision variables in the original problem, the simplex method starts by setting two of these 4 variables to zeros, then solving for the values of the other 2. For example, if we set x2 and s1 to 0, then x1 = 8. Plugging that into the second constraint equation, we obtain s2 = -12. This is called a basic solution. However, it not feasible because s2 = -12 violates the nonnegativity requirement. x2 and s1 that are set to zero here are called non-basic variables while x1 and s2 are called basic variables. Usually we start by setting x1 and x2 to zero. 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 nonnegativity as well. To set this up in a simplex tableau, we can begin with the objective coefficient row, 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 zero, they are the basic variables. These are also referred to as unit columns. Next, we place the basic variables in a column called Basis here, and place their objective function coefficients next to them in a column we refer to as cB. This shows that the initial basic feasible solution is s1 = 16 and s2 =12. Next, we introduce the zj row whose values are calculated by multiplying the cB values by the corresponding column values and adding the result. So for x1, it will be 0 * 2 + 0 * 3 which gives 0. And for x2, 0*4 + 0*2 which again is 0. And it will be zero for the rest as well. Our current objective function value will also be 0 here. The zj value (for the 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 – 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 row. For example, if x1 enters the basis and its value increases by 1, then the objective function increases by 7. What we have now is called the Initial Simplex Tableau. It has a basic feasible solution x1 and x2 =0, s1 = 16 and s2 = 12. x1 and x2 are equal to zero because they are the non-basic variables. We now perform iterations until all values in the net evaluation row are either negative or zero. 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’s another 7 on this row, you can any of them but for consistency, we prefer to the leftmost one. So x1 will 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 nonnegative value. For the first row, the ratio is 16/2 which gives 8. And for the second row, the ratio is 12/3 which gives 4. The minimum of the 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 key element or pivot element. This again is the initial simplex tableau and 3 here is our 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 elements so that the pivot column becomes a unit column. In essence, we convert the pivot element to 1 and the other value(s) in that column to zero. To do that we divide all the entries in the pivot row by the pivot element which is 3. So, 3 divided 3 is 1, 2 divided by 3 is 2/3 0 over 3 is 0 1 over 3 is 1/3 and 12/3 is 4. Next, we need to convert this 2 to zero by either adding or subtracting a multiple of the unit pivot element from it. And whatever operation we perform to make this 2 a zero, we perform it on all other elements in that row. Now, to make this 2 a zero, we can multiply this 1 by 2 and subtract it from this 2. In essence the elementary row operation is this: We take a row 1 element, subtract 2 times the corresponding new row 2 element, and assign the result to the new row 1 element. So 2 -2*1 = 0 as advertised. 4 – 2(2/3) = 8/3 1 – 2(0) = 1 0 – 2(1/3) = -2/3 and 16 – 2(4) = 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(0) + 7(1) which gives 7. For x2 column we have 0(8/3) + 7(2/3) which gives 14/3 0*1 + 7*0 gives 0. And this give 7/3. For the b column we have 0(8) + 7(4) which gives 28, the profit for the current solution. For the net evaluation row, we compute coefficients minus zj values. 7 – 0 gives 0 6 – 14/3 = 4/3 0 – 0 = 0 0 – 7/3 = -7/3 This first iteration is now done. We have a feasible solution of s1 = 8, x1 = 4, and objective function value of 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 optimal solution, each cj – zj must be less or equal to zero. Hence, we move on our next iteration. The new pivot column again will be the one with the most positive net evaluation row 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 values of the b column values by the positive pivot column values and select the row with the minimum ratio. So 8 divided by 8/3 is 8 * 3/8 which gives 3. ≤ And 4 divided by 2/3 is 4*3/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 (what is called degeneracy), we can choose any of the two, but we 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/3 is the key or pivot element as it is at the intersection of the pivot row and column. For the next iteration, x2 replaces s1 here and we place its objective function coefficient 6 in the 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/3. That is, multiplying them by 3/8. So 3/8 times 0 is 0. 3/8 times 8/3 is 1 as expected 3/8 times 1 is 3/8 3/8 times -2/3 is -1/4 and 3/8 times 8 is 3. Next, we make this column a unit column by making this entry in Row 2 zero. To do that, we multiply this new row 1 by 2/3 and then subtract it from the current row 2. That is R2(old) – (2/3)R1(new) will be assigned to R2(new). So 2/3 – 2/3(1) = 0 as required For x1 column, 1 – 2/3(0) = 1 For s1 column, 0 – 2/3(3/8) = -1/4 For s2 column, 1/3 – 2/3(-1/4) = 1/2 and for the b column, 4 – 2/3(3) = 2 Next, we calculate each zj values by multiplying basic objective coefficients by the column entries and adding the result. So, 6(0) + 7(1) = 7 6(1) + 7(0) = 6 6(3/8) + 7(-1/4) = 1/2 6(-1/4) + 7(1/2) = 2 For the b column 6(3) + 7(2) = 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/2 gives -1/2 0 – 2 = -2 Since all cj – zj elements are non-positive, we can’t improve on this solution so this is our optimal solution: X1 = 2, X2 = 3, s1 and s2 will be zeros because they’re non-basic. The optimal 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 labelled 1 to 6. The basic feasible solutions are the extreme or corner points of the feasible region, labelled 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 = 16, s2 = 12 and the value of the objective function is 0. After the first iteration, we obtained a solution of x1 = 4, s1 = 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 = 2 and x2 = 3. s1 and s2 are non-basic and are 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. 1. We converted the linear program problem into standard form by adding slack variables. 2. We developed the initial simplex tableau with x1 and x2 being non-basic variables 3. 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. 4. We then calculated the ratio of the b-column to the pivot column values. The minimum nonnegative ratio there determined the pivot row which corresponds to the variable leaving the basis. 5. We performed elementary row operations to make the column for the new basic variable a unit column. 6. 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.