OR320/520 Fall '99 Prelim 1 Solution 1 a) The decision variables are : x_t = number of calculators produced in time period t during regular shift t = 1,..6 y_t = number of calculators produced in time period t during overtime hours t = 1,..6 i_t = number of calculators stored at the end of period t t = 0,..6 Note: We need to define the inventory variable i_t only to make the formulation easier, we can model without it too. Also, for the given problem, we need to make atleast 100 calculators in every time period, and so we need not keep track of calculators made at overtime cost separately. We can have a variable for the number of calculators made, the first 100 would be at regular and the rest at overtime cost. But this is specific to the given data, in general we would need separate variables for the 2 kinds of costs. In modeling problems, it is important that you have the formulation correct for all instances of data, and not just for the given data. Try, NOT solving the problem yourself, you get credit for the formulation not the solution! 1 b) The objective is to minimize total cost subject to (1) maintaining inventory balance for each time period, and (2) the production capacity constraints. Min [sum(t = 1..6) (10x_t + 12y_t + 0.5i_t)] s.t. i_(t-1) + x_t + y_t - i_t = d_t i.e. inventory in previous time period + total number produced in this time period - inventory for current time period = demand in current time period x_t <= 100 y_t <= 75 x_t, y_t, i_t >= 0, for t = 1..6 i_0 = 0, it is defined so that we can write the inventory balance constraint for the first time period same as for the rest of the time periods, and we start with no inventory on hand. i_6 = 0, since we do not keep any inventory at the end of June. In fact, i_6 >= 0 would be fine too since the objective function is trying to minimize cost and would try and make i_6 zero. Note: One common mistake was in the inventory balance constraints. Most of you made sure that what you produce in time period t - inventory at end of time period t >= demand in t. But this does not take into account the inventory from the previous time period. 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 sloution is reached. New optimal sloution 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.