Unformatted text preview:

Final ExaminationCS 525 - Fall 2009Monday, December 21, 2009, 10:05a-12:05p.Each question is worth the same number of points.No electronic devices, notes, or books allowed, except that you may bringone standard-size sheet of paper, handwritten on both sides, into the test.You need to give reasoning and justify all your answers, quoting anytheorems you use.1. Solve the following linear program: If it is unbounded, give a directionof unboundedness.min 4x1− 12x2− x3subject to 2x1+ x3≥ 2,3x2+ x3= 1,x1free, x2, x3≥ 0.2. Solve the following linear program for all values of the parameter t inthe interval (−∞, ∞). For each piec e of the solution indicate clearly:parameter range, solution x(t), and optimal objective value z(t).min −x1+ t(x1+ x2)subject to − x1+ x2≥ −1,−x2≥ −3,x1, x2≥ 0.13. Consider the following quadratic program:min x21+ 2x1x2+2x22+ x1subject to x1+ 2x2≥ 3,x1− x2≥ −2,x1, x2≥ 0.(a) Write down KKT conditions for this problem.(b) Solve the problem using Lemke’s method.(c) Does the solution change if we change the coefficient of x1in theobjective from 1 to 4? Explain.4. Given a matrix A, show that exactly one of the following two statementsis true:I. There is a vector x such that Ax > 0 (that is, all components ofAx are strictly positive);II. There is a vector u such that A0u = 0, u ≥ 0, and u 6= 0.5. A husband and wife are deciding how to spend their evening. The wifeprefers to go to a baseball game, while the husband would prefer to visitan art gallery, but in either case, they would like to go out together.In formulating their decision as a bimatrix game, the loss matrix entryfor each person is 4 if they go to separate events, 1 if they go to theirpreferred event together, and 2 if they go together to their less favoredevent together.(a) Write down the loss matrix A for the wife and B for the husband.Let strategy 1 be “attend baseball” and strategy 2 be “visit artgallery”.(b) If the randomized strategy vectors for the husband and wife aredenoted by x and y, respectively, show that ¯x = (1, 0)0and ¯y =(1, 0)0is a Nash equilibrium pair.(c) Show that ¯x = (0.6, 0.4)0and ¯y = (0.4, 0.6)0is also a Nash equi-librium


View Full Document

UW-Madison CS 525 - Final Examination

Download Final Examination
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

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

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

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

or

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

Already a member?