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