1: Determine if the following problems are bounded or unbounded and then determine if they are feasible or infeasible (5pts each):
$\begin{array}{rr}\max & 6 x_{1}+8 x_{2}+5 x_{3}+9 x_{4} \ \text { s.t. } & 2 x_{1}+x_{2}+x_{3}+3 x_{4} \leq 5 \ & x_{1}+3 x_{2}+x_{3}+2 x_{4} \leq 3 \ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \ \max & 6 x_{1}+8 x_{2}+5 x_{3}+9 x_{4} \ \text { s.t. } \quad 2 x_{1}+x_{2}+x_{3}+3 x_{4} \geq 5 \ & x_{1}+3 x_{2}+x_{3}+2 x_{4} \geq 3 \ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \ \max & 6 x_{1}+8 x_{2}+5 x_{3}+9 x_{4} \ \text { s.t. } & 2 x_{1}+x_{2}+x_{3}+3 x_{4} \leq-1 \ & x_{1}+3 x_{2}+x_{3}+2 x_{4} \leq 3 \ x_{1}, x_{2}, x_{3}, x_{4} \geq 0\end{array}$

Solve following by hand using the simplex method (20 pts each):
$$
\begin{aligned}
\max \quad 6 x_{1}+8 x_{2}+5 x_{3}+9 x_{4} \
\text { s.t. } \quad 2 x_{1}+x_{2}+x_{3}+3 x_{4} \leq 5 \
x_{1}+3 x_{2}+x_{3}+2 x_{4} \leq 3 \
x_{1}, x_{2}, x_{3}, x_{4} \geq 0
\end{aligned}
$$
$$
\begin{aligned}
\max \quad x_{1}+3 x_{2} & \
\text { s.t. }-x_{1}-x_{2} & \leq-3 \
&-x_{1}+x_{2} & \leq-1 \
& x_{1}+2 x_{2} & \leq 4 \
x_{1}, x_{2} & \geq 0
\end{aligned}
$$

Solve the Klee-Minty problem, as described in the notes/text, for $\mathrm{n}=3$ (15 pts).

Suppose that you have been put in charge of managing the clothing supply for a small, newly established space colony. The colony has $n$ colonist each of whom need at least two pairs of shoes, three jump suits and a hat. You can make each of these products from some combination of cotton, synthetic threads and glue, all of which you need to import. You can also import already made clothing for a fixed cost. For each item that you produce in the factory you also incur a cost of $d$ per item (a pair of shoes, jumpsuit and hat each count as an ‘item’) for the use of electricity in your factory. Write down (but do not solve) a linear program to minimize the cost of acquiring all of the clothing which your colony requires. You may assume that you are allowed to make and import fractional quantities of each of these goods. (20 pts)
Hint: Let $\mathrm{x}=\left{x_{i}\right}_{i=1}^{6}=$ amount imported of cotton, thread, glue, shoes, jumpsuits, hats, and $\mathrm{c}=\left{c_{i}\right}_{i=1}^{6}$ be the cost of importing each of these raw materials and completed items
Bonus:(Up to $5 \mathrm{pts})$ : What can you say about this problem as $n$ changes?