New version page

UW-Madison CS 525 - Final Examination CS 525

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

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≥

View Full Document
Download Final Examination CS 525
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...

Join to view Final Examination CS 525 and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Examination CS 525 2 2 and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?