Problem 3 (Math 526 only) (Modzed from GET 2.5.10} Consider a linear program (P) max{z:cT:c:A:1::b,:r:?j}. The following will establish that the Simplex method with Bland's Rule, i.e., the smallest subscript rule, never cycles and, therefore, terminates after nitely many iterations. Suppose, on the contrary, that the Simplex method cycles through the bases B1 , Ba, . . . , 3;, BH] : B1. Let J denote the set of indices that become basic at some point of the cycle: J:: {iHZE Bj1,i 33-2 for somejhjg {1,...,t}}. Note that J is a nite set, so there must be a maximum index in J; let I; :2 max{j : j E J}. The next several exercises will establish the desired contradiction. (a) (h) (C) (d) (B) Suppose that d E R\" such that Ad : , i.e., d is in the null space of A. Show that for anyr y E R\" and E z: c ATy we have ETd : ch. Suppose that we choose If]. to enter the basis in the iteration corresponding to the basis BE, i.e., q tf Be and q E Ba\". Let F: denote the coefcients of a: in the objective hmction of (P) in canonical form for Be. What are the signs of the entries of E indexed by Na :: {j : j (3? Be}? Justify your HDI-lWEl' . Suppose that in the iteration corresponding to the basis Bf, we choose mg. to leave the basis, i.e., q E B; and q 95 BE\". Let ls: denote the index of the pivot column for this iteration. That is I]: enters the basis. Let g, denote the kth column of A, the coe'icient matrix of (P) in canonical form corresponding to 33. When pivoting, the basic feasible solution 3 corresponding to B! is mapped to the basic feasible solution 33' corresponding to Bf+1 by 33" = a: + td, where 053 = .;,., d}; = 1, d3: = 0 otherwise, (3.3.1) 1 and t is chosen by the ratio test. [i] Show that it satises Ad 2 0. (ii) What are the signs of the entries of d? Justify your answer. Suppose that F: and E" are the coeicient vectors for the objective of (P) in canonical form with respect to BE and 33 respectively. Show that E := E E" belongs to the row space of A. Conclude that Td = U. Hint: Consider the denition of E and 3. You should be able to express their dierenee as a linear combination of rows of A. Use the signs of E and (1 obtained in the previous parts to show that 67%