Question 1: An artificial variable with value zero occurs in an optimal basis for an auxiliary problem in of of two ways: 1. in a constraint that only involves artificial variables, or 2. in a constraint that involves at least one variable from the original problem. We consider how to deal with both situations. (a) Suppose a basic artificial variable occurs in a constraint that only involves other artificial variables: (i) Show that the rank of the original constraint matrix was less than the number of constraints. (ii) Why can this situation not happen if the original problem started with every constraint in inequality form? (iii) If the RHS of this constraint is not zero, show that the original system was infeasible. (iv) If the RHS of the constraint is zero, conclude that the constraint can be deleted to eliminate the artificial variable from the system. (b) Suppose a basic artificial variable occurs in an optimal tableau in a constraint involving at least one variable from the original problem. If the right hand side of this constraint is zero, show that there is another feasible basis in which the artificial variable does not occur. Hint: you may not be able to make a normal simpler pivot, but because the RHS is zero, any pivot involving this row will not break feasibility or change the object value, even if you ignore normal sign rules for selecting entering and leaving variables. Hint 2: you might want to work through question 2 before answering this question. The pivots used in 2(c) and 2(d) are examples of what you want to do here. This question asks you to describe those operations abstractly. Question 1: An artificial variable with value zero occurs in an optimal basis for an auxiliary problem in of of two ways: 1. in a constraint that only involves artificial variables, or 2. in a constraint that involves at least one variable from the original problem. We consider how to deal with both situations. (a) Suppose a basic artificial variable occurs in a constraint that only involves other artificial variables: (i) Show that the rank of the original constraint matrix was less than the number of constraints. (ii) Why can this situation not happen if the original problem started with every constraint in inequality form? (iii) If the RHS of this constraint is not zero, show that the original system was infeasible. (iv) If the RHS of the constraint is zero, conclude that the constraint can be deleted to eliminate the artificial variable from the system. (b) Suppose a basic artificial variable occurs in an optimal tableau in a constraint involving at least one variable from the original problem. If the right hand side of this constraint is zero, show that there is another feasible basis in which the artificial variable does not occur. Hint: you may not be able to make a normal simpler pivot, but because the RHS is zero, any pivot involving this row will not break feasibility or change the object value, even if you ignore normal sign rules for selecting entering and leaving variables. Hint 2: you might want to work through question 2 before answering this question. The pivots used in 2(c) and 2(d) are examples of what you want to do here. This question asks you to describe those operations abstractly