2 a) The current basic feasible solution is given by [x1 x2 x3 x4 x5 x6 x7]^T = [3 3/2 0 0 5/2 2 0]^T. Here, the symbol ^T indicates the transpose. The objective function value is given by 12, the right hand side value corresponding to row 0 in the tableau. The solution is optimal since all row 0 coefficients of the nonbasic variables are NONNEGATIVE. There are alternative optimal solutions since both x3 and x4 have 0 as row 0 coefficients, and hence their values can be increased without changing the objective function value. 2 b) The current optimal solution has x2 = 3/2. Consider Row 4 in the final simplex tableau. Rewriting it as an equality, we have x2 + 1/2 x3 - 3/2 x4 + 1/4 x7 = 3/2 >From part (a), we know that we can increase the nonbasic variables x3 and x4 without changing the objective function value. Therefore, keeping x7 = 0, the above equality can be expressed as x2 = 3/2 - 1/2 x3 + 3/2 x4. (*) Let's rewrite each of the remaining rows in the simplex tableau as an equality: (x7 is still set to 0). x1 = 3 - x4 (1) x5 = 5/2 + 1/2 x3 - 3/2 x4 (2) x6 = 2 - x3 (3) Let's fix x4 = 0. Then, by (*), if we set x3 = 1, we get x2 = 1. (Note that we are allowed to choose any nonnegative value for x3 and x4 as long as the resulting solution is nonnegative). We need to be careful here since we altered the value of a nonbasic variable and it might lead to a change in the values of the basic variables as well. From (1),(2) and (3), plugging in x3 = 1, and x4 = 0, we obtain: x1 = 3 x5 = 3 x6 = 1. Hence, one optimal solution with x2 = 1 (which is not basic since there are only two variables set at 0) is given by [x1 x2 x3 x4 x5 x6 x7]^T = [3 1 1 0 3 1 0]^T. Consider (*) again. Now, let's fix x3 = 0. Then, by setting x4 = 1/3, we have x2 = 2. Then, from (1), (2) and (3), plugging in x3 = 0, x4 = 1/3, we get: x1 = 8/3 x5 = 2 x6 = 2 Therefore, an optimal solution with x2 = 2(which, again, is not basic by the same reason) is given by [x1 x2 x3 x4 x5 x6 x7]^T = [8/3 2 0 1/3 2 2 0]^T. 2 c) Rewrite row 0 in the equality form. z + 1/2 x7 = 12 Therefore, z = 12 - 1/2 x7. Clearly, increasing x7 from 0 will only decrease the objective function value. Hence, any feasible solution with x7 = 0 will have the optimal objective value 12, and vice versa. Another way to look at it is, consider the last constraint 6x1 + 4x2 + 2x3 <= 24 ==> 2(3x1 + 2x2 + x3) <= 24 ==> Z <= 12 If x7 = 0 then any feasible solution would be satisfying this constraint as equality i.e 6x1 + 4x2 + 2x3 = 24 ==> 3x1 + 2x2 + x3 = 12 ==> Z = 12, hence the feasible solution with x7 = 0 is optimal. 2 d) After preforming all the steps as indicated in the question, the tableau looks like: --------------------------------------------------------------------------- x1 x2 x3 x4 x5 x6 rhs --------------------------------------------------------------------------- W -1 0 0 x1 1 0 1 1 3 x5 -1/2 3/2 1 5/2 x6 1 0 2 x2 1 1/2 3/2 3/2 --------------------------------------------------------------------------- W 0 1 2 x1 1 1 0 3 x5 3/2 1 1/2 7/2 x3 1 0 1 2 x2 1 -3/2 -1/2 1/2 --------------------------------------------------------------------------- Here, the optimal solution is reached. New optimal solution is : (3,1/2,2,0,7/2,0) 2 e) When we eliminated x7, by (c) we are now restricting to feasible solutions that maximized Z. Among these, the best solution has been found with row 0 coefficients ( with W objective) => 0. The Maximum possible solution for Z is 12 and maximum possible solution for W is 2 and we were able to obtain a solution which could maximize to the best possible extent both Z and W at the same time. Thus we can conclude that subject to primary objective being maximized, the secondary objective has also been maximized. 2 f) Since we have a zero row 0 corfficient ( of x4), we could still improve a tertiary objective by keeping Z and W maximum. For example, the tertiary objective could be Max V= -x1. Now, we'd increase x4.(Try it! - Do similar operations as you did to obtain an optimal solution for W) 3 a) Entering variable: x2 (since it has the most negative row 0 coefficient) Leaving variable : x3 (since it has one of the minimum ratios). 3 b) The only variable that is eligible to enter the basis is x1, but when we do the min-ratio test, the min ratio is 0, so we cannot increase x1. The feature of the basic feasible solution that signals this difficulty is that one of the basic variables, x4, is currently zero. We could tell this would happen in Tableau A when there was a tie in the min ratio test for x3 and x4 leaving the basis. 3 c) If x2 had entered the basis and x5 left at Tableau A, x2 would have increased too much, forcing x3 and x4 to go negative, resulting in an infeasible solution. If x2 had entered the basis and x4 left, we would have had a similar result to Tableau B, with a degenerate solution with basic variable x3 equal to zero. 3 d) -------------------------------------------------- B.V. Eqn.# Z X1 X2 X3 X4 X5 | RHS -------------------------------------------------- Z 0 1 0 0 -2 3/2 0 | 3 x2 1 0 0 1 -1/2 1/2 0 | 3/2 x1 2 0 1 0 -1 1/2 0 | 0 x5 3 0 0 0 -3/2 -1/2 1 | 1/2 -------------------------------------------------- The objective function value remained constant at 3, and none of the values of the variables have changed. Such is the nature of degenerate solutions. We are looking at the same solution but choosing different variables to express the objective function. 3 e) Yes, we can conclude that the problem is unbounded from tableau A itself. If we choose x1 to enter basis, all the entries in the column under x1 are <= zero. Hence, the problem is unbounded. We can choose to enter x1 since it has a negative coefficient, even though it is not the most negative coefficient. At the same time, conclusion about degeneracy( although it was not asked for) in the next table may also be drawn because on choosing x2 as entering variable, the minimum ratio test yields the same result for both the x3 and x4, resulting in a tie for the leaving variable.