Practice Problem 3
(1) Consider the following problem.
You are given the information that the nonzero variables in the optimal solution are x2 and x3. Describe how
you can use this information to adapt the simplex method to solve this problem in the minimum possible
number of iterations.
(2) Consider the following problem.
Work through the simplex method to demonstrate that Z is unbounded.
(3) Consider the following problem.
Work through the simplex method to find all the optimal BF solutions.
(4) Consider the following problem.
(a) Solve this problem graphically.
(b) Using the Big M method, construct the complete first (initial) simplex tableau for the simplex method
and identify the corresponding initial BF solution. Also identify the initial entering basic variable and the
leaving basic variable.
(c) Continue from part (b) to work through the simplex method step by step to solve the problem.
(5) Consider the following problem.
(a) Using the two-phase method, construct the complete first simplex tableau for phase 1 and identify the
corresponding initial BF solution. Also identify the initial entering basic variable and the leaving basic
variable.
(b) Work through phase 1 step by step.
(c) Construct the complete first simplex tableau for phase 2.
(d ) Work through phase 2 step by step to solve the problem.
(6) Consider the following problem.
(a) Using the Big M method, work through the simplex method step by step to solve the problem.
(b) Using the two-phase method, work through the simplex method step by step to solve the problem.
(c) Compare the sequence of BF solutions obtained in parts (a) and (b). 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?
(7) Consider the following problem.
(a) Demonstrate graphically that this problem has no feasible solutions.
(b) Use a computer package based on the simplex method to determine that the problem has no feasible
solutions.
(c) Using the Big M method, work through the simplex method step by step to demonstrate that the problem
has no feasible solutions.
(d) Repeat part (c) when using phase 1 of the two-phase method.
(8) Consider the following problem.
(a) Solve this problem graphically.
(b) Reformulate this problem so that it has only two functional constraints and all variables have
nonnegativity constraints.
(c) Work through the simplex method step by step to solve the problem.
(9) Consider the following problem.
(a) Reformulate this problem so that all variables have nonnegativity constraints.
(b) Work through the simplex method step by step to solve the problem.
(10) Consider the following problem.
Work through the simplex method step by step to demonstrate that this problem does not possess any
feasible solutions.
(11) You are given the following linear programming problem.
(a) Solve this problem graphically.
(b) Use graphical analysis to find the shadow prices for the resources.
(c) Determine how many additional units of resource 1 would be needed to increase the optimal value of Z
by 15.
