Question 1. Solve the following LP's by hand, using the simplex method and starting from * = 0: (a) min 2x1 + 312 -13 s.t. 1+2 wdso (7) Hint: relate this to the duality seen in (a) and (b)]. It is suggested to use Gurobi to answer the next two questions. For both of them we take n = 2, m = 3, and v1 = (1, 3) , v2 = (2, 1) , v3 = (1, 1) , and we ask if there exist ); 2 0, i = 1, ..., m, such that (6) holds: (d) when w = (1, 10) ? Give a vector of the Mi's such that (6) if the answer is yes, and if the answer is no, a vector de R" such that v. d 0. (e) when w = (3, 2)? Question 5. The goal of this question is to go through the proof (that we skipped in class) of the duality theorem using the separating hyperplane theorem. The separating hyperplane theorem states that if C is a convex set of R and x E R is not in C, then there is a y e Rd and a such that z y - o 2 0 for all z E C and x y - a x y. Consider the primal LP VP = mine r s.t. Ax = b and its dual VD = maxb y s.t. A y S c We assume Vp is finite, which means that the primal problem is feasible and bounded. (a) Introduce C= (1, W) ER X RM : r= tVp -C X, ; TER, teR.) w = th - Ax, and show that C is convex, and that C is a cone, that is (r, w) E C and * 2 0 implies (Ar, Aw) E C.(b) Show that (1,0) @ C. By the separating hyperplane theorem, deduce that there is (s, y) E R x Rm such that 30 ty 0 => 0 and t > 0. (e) Noting that t = 0 implies yTA Vp, show that y is optimal for the dual