Exercise 5.2 (Sensitivity with respect to changes in a basic column of A) In this problem (and the next two) we study the change in the value of the optimal cost when an entry of the matrix A is perturbed by a.small amount. We consider a linear programming problem in standard form, under the usual assumption that A has linearly independent rows. Suppose that we have an optimal basis B that leads to a nondegenerate optimal solution x*, and a nondegenerate dual optimal solution p. We assume that the first column is basic. We will now change the first entry of A1 from all to all + 8, where o is a small scalar. Let E be a matrix of dimensions m x m (where m is the number of rows of A), whose entries are all zero except for the top left entry ell, which is equal to 1. (a) Show that if 8 is small enough, B+SE is a basis matrix for the new problem. (b) Show that under the basis B + SE, the vector XB of basic variables in the new problem is equal to (I + 8B-]E) 'B-lb. (c) Show that if 8 is sufficiently small, B + SE is an optimal basis for the new problem. (d) We use the symbol ~ to denote equality when second order terms in 6 are ig- nored. The following approximation is known to be true: (I+6B-'E) -1 ~ I -B-'E. Using this approximation, show that CBXB ~ C'X* - Spixi, where x1 (respectively, p1) is the first component of the optimal solution to the original primal (respectively, dual) problem, and XB has been defined in part (b). I Exercise 5.3 (Sensitivity with respect to changes in a basic column of A) Consider a linear programming problem in standard form under the usual