1.Solve the Linear program below to get all optimal solutions. What is the optimal cost?

max x₁+ 6x₂+ 4x₃

s.t. -x₁+ 2x₂+ 2x₃<=13

4x₁- 4x₂+ x₃<=20

x₁+2x₂+ x₃<=17

x₁>=1, x₂>=2, x₃>=3

2.Let P be the polyhedron consisting of points x belongs to R²satisfying the constraints

3x₁+ x₂? -3

-3x₁+ x₂? -2

x₁+ 3x₂? -1

x₁+ 5x₂= 5

We will see two different methods of either finding a feasible point or declaring the infeasibility of P.

(a) (Trying all basic solutions)

i. Identify all basic solutions and check that they are all feasible.

ii. Provide the additional arguments to show that P is infeasible. (I.e., show that if all basic solutions of P are feasible, then P is feasible.)

(b) Make use of phase 1 of the two phase method to declare that P= .