QUESTION 1 (from Applied Mathematical Programming by by Bradley, Hax, and Magnanti) Consider the linear program: maxz = 9x2 + x3 2x5 x6 5x2 + 50x3 +x4 + x5 = 10 x1 15x2 + 2x3 = 2 x2 +x3 +x5 +x6 = 6 xj 20 V]: 1, ...,6 a) Find an initial basic feasible solution, specify values of the decision variables, and tell which are basic. b) Transform the system of equations to the canonical form for carrying out the simplex routine. c) Is your initial basic feasible solution optimal? Why? d) How would you select a column in which to pivot in carrying out the simplex algorithm? e) Having chosen a pivot column, now select a row in which to pivot and describe the selection rule. How does this rule guarantee that the new basic solution is feasible? Is it possible that no row meets the criterion of your rule? If this happens, what does this indicate about the original problem? f) Without carrying out the pivot operation, compute the new basic feasible solution. g) Perform the pivot operation indicated by (d) and (e) and check your answer to (f). Substitute your basic feasible solution in the original equations as an additional check. h) Is your solution optimal now? Why