Final ExaminationCS 525 - Spring 2002Monday, May 13, 2002Write out your final solution to each problem clearly and unambiguously.Instructions (Please read carefully): If a problem has no solutions,many solutions, or is infeasible or unbounded, you must clearly state this tobe the case and justify your statement. When the problem is unbounded,give a direction of unboundedness.There are FIVE (5) questions. All questions are worth the same numberof points.Problems 1 and 5 each can be solved in three pivots or fewer.1. Solve the following linear program.min x1+ 3x2+ 4x3subject to 3x1+ x2− x3≥ −1,x1− x2+ 2x3≥ 3,x1+ 2x2+ x3≥ 2,x1, x2, x2≥ 0.2. Suppose that at iteration k in the infeasible path-following interior-point method (Algorithm IPF), the algorithm takes a step length ofαk. Express the values of the following two vectors:Axk+1− bA0yk+1+ sk+1− c1in terms of αk, the previous iterate (xk, yk, sk), and the problem dataA, b, and c.(Note that c and p in the class notes are used interchangeably; theyboth denote the cost vector for the primal linear program.)3. Consider the linear programminx,yc0x + d0y subject to Ax + By ≥ b, x ≥ 0, y ≥ 0,where A is a square matrix that satisfies A ≥ I (where I is the identitymatrix), and c ≤ 0. Suppose that this problem has a solution.(i) Write down the dual for this problem.(ii) By using the properties of A and c, find the solution of the dual.(Explain your reasoning.)(iii) What is the optimal objective value of the original (primal) prob-lem? (Give reasons for your answer.)4. Given the following linear program, define a Phase I problem (by addingartificial variables and defining an appropriate objective). Give a basicfeasible starting point for the Phase I problem. (Do not try to solveit.)min −3x1+ 4x2+ 7x3subject to x1+ 3x2+ 4x3= 10,−x1+ 2x2+ x3= −5,−1 ≤ x1≤ 4,0 ≤ x2≤ 1,−1 ≤ x3.5. Solve the following quadratic program by Lemke’s method.min 2x21+ x22+ 2x1x2− x1− x2subject to x1+ 2x2≥ 2,x1≥ 0, x2≥