Ans-5

c Wen Shen. All rights reserved. Answer key to Homework 5, Math 484, Linear Programming These are just answer keys. The students should provide more details in their home work. Chapter 3.6, Problem 1 (b) Adding two artificial variables x 4 , x 5 , and let w = x 4 + x 5 , we set up the LP: Minimize w with x 1 + x 2 + x 4 = 1 2 x 1 + x 2 - x 3 + x 5 = 3 - 3 x 1 - 2 x 2 + x 3 = - 4 + w Setting up the tableau and using LP Assistant, we get: Since w reaches it minimum of 1, which is strictly positive, we conclude that the original constraint is not feasible. Chapter 3.6, Problem 2 (a) Adding artificial variables x 4 , x 5 , and let w = x 4 + x 5 , we use LP Assistant to compute the tableau: 1

c Wen Shen. All rights reserved. We observe that w reaches 0 at its minimum, so the constraints are feasible. The final answer: z min = 3 2 attained at (0 , 29 2 , 11 2 ). 2

c Wen Shen. All rights reserved. (d) Introducing 3 slack variables x 3 , x 4 , x 5 , we can put the LP in standard form: Minimize z with x 1 - x 2 + x 3 = 3 2 x 1 - x 2 + x 4 = 0 x 1 + x 2 - x 5 = 12 - 3 x 1 + x 2 = z We see that x 3 , x 4 can already be used as basic variables, but not x 5 . We need to introduce only one new artificial variable x 6 , and let w = x 6 : x 1 - x 2 + x 3 = 3 2 x 1 - x 2 + x 4 = 0 x 1 + x 2 - x 5 + x 6 = 12 - 3 x 1 + x 2 = z - x 1 - x 2 + x 5 = - 12 + w Note that we modified the expression for w = x 6 to contain only none basic variables. We have the follow tableau: We see that w is driven to 0, so the original LP has feasible solution. Also, while z has - 1 3 in front of x 5 term, the column vector contains all negative terms. Thus, the minimum value for the LP is unbounded below. 4

c Wen Shen. All rights reserved. (e) The LP will be in standard form if we change it into a minimization problem: Minimize - x 1 - 2 x 2 - 3 x 3 - 4 x 4 = z. None of these can be used as basic variable. So we introduce 3 artificial variables x 5 , x 6 , x 7 , and set them up in the tableau. We see that the minimum value for w is 10 > 0, so the LP has no feasible solutions. 5

c Wen Shen. All rights reserved. (d) Changing it into a minimization problem, and adding 3 artificial variables, we send it to LP Assistant and obtain the following tableau: We see that w reaches 0 where x 6 is still in the basic variable. However, a 64 = - 8 6 = 0. By pivoting at this position, we removed x 6 from basic variables. Therefore, there is no redundancy. We conclude that z min = 6, attained at (0 , 1 , 2 , 0). Back to the original problem, the max is -6, attained at (0 , 1 , 2 , 0). 7

c Wen Shen. All rights reserved. (g) By adding 3 artificial variables and using LP Assistant, we get We see that w is driven to 0 after one step, where x 6 , x 7 are still both in the basic variables. After pivoting at a 74 = 2, we removed x 7 . But now the second row for 6 has all 0 coefficients. Thus, there is one redundant equation. Neglecting this row, we continue with the process to minimize z , and reach the final conclusion that z min = 25 attained at (15 , 0 , 0 , 10). 8