Let s be a scalar.

Consider the linear programs zs= max x1 + x2

s.t. x1 + sx2 s

sx1 x2 s

x1 0, x2 0. studied in the previous homework. 1. Write down the dual of (Ps)

. 2. Do you think the dual problem is always feasible? If so, please provide a solution for the dual which is always feasible regardless of the value of s. If not, provide a counter example. 3. Find all values of s for which the problem (Ps) has an optimal solution. Find the value of zsin these cases and provide a primal feasible solution and a dual feasible solution that achieve this objective value.

4. Find all values of s for which the problem (Ps) is unbounded. Provide a clear argument that the problem is indeed unbounded for these values of s. Also, please argue that for these cases, the dual is infeasible.