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 Aj from ali to aji +8, where 8 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 e11, which is equal to 1. (a) Show that if & is small enough, B+SE is a basis matrix for the new problem. (b) Show that under the basis B + 8E, the vector xb of basic variables in the new problem is equal to (I + 8B-'E-'B-lb. (c) Show that if d 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 8 are ig- nored. The following approximation is known to be true: (I+8B-'E)-1 I -8B-SE. Using this approximation, show that d'exB~c'x* 8p1x1, where xi (respectively, p) is the first component of the optimal solution to the original primal (respectively, dual) problem, and xb has been defined in part (b).