he feasible region of an optimization problem over variable x in Rn is the set of all feasible

solutions to the problem.

Consider the following LPs over variable x in Rn:

maxc$$x:Ax$<=$b $,$ and $($P$1)$ minc$$x:Bx$=$d$,$x$>=0,($P$2)$

for some matrices A$,$ B and vectors b$,$ c$,$ d$.$ Let S and T be the feasible regions of the LPs $($P$1)$ and $($P$2).$ Define the set U as the so called Minkowski difference

U :$=\{$y $$ z : y in S$,$ z in T $\},$ and the optimization problem $($P$3)$ as

maxc$$x:x in U $.($P$3)$

$($a$)$ Rewrite the problem $($P$3)$ as an LP$.$

$($b$)$ What are the possible outcomes for $($P$3)$ if $($P$1)$ and $($P$2)$ are both feasible? Justify your answer.

Determine whether the following statements are true or false. Justify your answer with a proof or a counter$-$example.

$($c$)$ Suppose $($P$1),($P$2),$ and $($P$3)$ are feasible. Then $($P$3)$ is bounded if and only if $($P$1)$ and $($P$2)$ are both bounded.

$($d$)$ Suppose $($P$1),($P$2),$ and $($P$3)$ are feasible. Then $($P$3)$ has an optimal solution if and only if $($P$1)$ and $($P$2)$ both have an optimal solution.