Information Technology > QUESTIONS & ANSWERS > EE236A Linear Programming Midterm (All)

EE236A Linear Programming Midterm

Document Content and Description Below

Problem 1 (7 points): Can you express the following problems as LPs? (If yes do so, if not, explain why). Note that we do not ask you to solve these problems, only to express them as LPs if possible.... 1. (2 points) Let x 2 Rn. min cT x subject to jjxjj1 ≤ 100 2. (2 points) For x1, x2 2 R min −2x1 − 3x2 subject to minfx1; x2g ≤ 4 x1; x2 ≥ 0 3. (3 points) Assume that we want to design a game, where the output x takes one of n possible values ai, with probability prob(x = ai) = pi, i = 1 : : : ; n. We also want that the probability we get the output a1 is higher than the probability we get any other output. Moreover, we want to minimize the expected value of the output, E(x) = nP i=1 piai. Can this optimization be expressed as an LP? 2Solution: 1. Yes, through the following LP min cT x subject to 1T y ≤ 100 −y ≤ x ≤ y 2. No, because the constraint minfx1; x2g ≤ 4 does not specify a convex set. 3. Yes, through the following LP min nP i=1 piai subject to pi ≥ 0; i = 1; · · · ; n nP i=1 pi = 1; p1 ≥ pi; i = 2; · · · ; n [Show More]

Last updated: 2 years ago

Preview 1 out of 8 pages

Buy Now

Instant download

We Accept: