1. Consider the following problem.

Maximize Z = 2 X1 + 2 X2 + 4 X3

Subject to 2 X1 + X2 + X3 = 2

3 X1 + 4 X2 + 2 X3 = 8

All Xi = 0

(a) Using the Big-M method, construct the complete first simplex tableau for the Simplex method and identify the corresponding initial (artificial) basic feasible solution. Also, identify the initial entering basic variable and the leaving basic variable. Work through the simplex method step by step to solve the problem.

(b) Using the two-phase method, construct the complete first simplex tableau for phase 1 and identify the corresponding initial (artificial) basic feasible solution. Also, identify the initial entering basic variable and the leaving basic variable. Work through phase 1 step by step.

(c) Construct the complete first simplex tableau for phase 2 and work through phase 2 step by step to solve the problem.
2

(d) Compare the sequence of basic feasible solutions obtained in part (a) with that in parts (b) and (c). Which of these solutions are feasible only for the artificial problem obtained by introducing artificial variables and which are actually feasible for the real problem?

Note: At the end of phase 1 (or Big-M method), if one or more artificial variables are in the basis with zero value, we can remove them from the basis with the following procedure and then start

phase 2:

(Step 1) Select the artificial variable with zero value to leave the basis. You need to designate its row as the pivot row and the entering variable can be any nonbasic and nonartificial variable with a nonzero value of coefficient in the pivot row. You need to perform the associated simplex iteration.

(Step 2) Remove the column of the (just-leaving) artificial variable from the tableau.

(Step 3) If there is another artificial variable in the basis with a zero value, then repeat steps 1 and 2. Otherwise, you may start with phase 2.

2. Consider the following problem (Show your procedure).

Maximize Z = 2X1 + 5X2

Subject to 3X1 + 2X2 = 6

2X1 + X2 = 2

X1 = 0 , X2 = 0

(a) Using the Big-M method, show the given LP problem has no feasible solution.

(b) Using the Two-phase method, show the given LP problem has no feasible solution.

(c) Using the graphical method, show the given LP problem has no feasible solution.

3. Consider the following problem (Show your procedure).

Minimize Z = 8X1 + 4X2

Subject to 3X1 + 4X2 = 6

5X1 +2X2 = 10

X1 +4X2 = 4

X1 = 0 , X2 = 0

(a) Solve the problem using the Big-M method.

(b) Solve the problem using the Two-phase method.

(c) Solve the problem using the graphical method.