Practice Exam 2, Math 354

Sections 01-02, Fall 2024

1:  (40 pts.)  Consider the following linear programming problem: maximize

z = 3x1 + 2x2 − x3 + 3x4,

subject to the constraints

The final tableau to this linear programming problem is given by

(a)  (4 pts.)  What basic feasible solution does the tableau above represent?

(b)  (10 pts.) What is the dual problem to the linear programming problem above, and what is its optimal solution and optimal value?

(c)  (6 pts.)  Use complementary  slackness theorem to find the values of slack variables of the dual problem at the optimal solution.

(d)  (20 pts.)  What is the optimal solution to this programming problem if we add the con- straint that x1 , x2 , x3 , x4  are integers?

2:  (30 pts.)  Consider the following linear programming problem: maximize

z = 3x1 + x2 + 2x3,

subject to the constraints

The final tableau to this linear programming problem is given by

(a)  (5 pts.)  Suppose the objective function is replaced with z = 3x1  + c2(′)x2  + 2x3 .  Find the range of ∆c2  = c2(′) − c2  such that the solution corresponding to the final tableau is still optimal.

(b)  (10 pts.)  Suppose the objective function is replaced with z = c1(′)x1  + x2  + 2x3 .  Find the range of ∆c1  = c1(′) − c1  such that the solution corresponding to the final tableau is still optimal.

(c)  (15 pts.)  Suppose the first constraint above is replaced with x1  − 3x2  + 3x3  ≤ 10.  What is the new optimal solution?

3:  (30 pts.) For the following transportation problem.

(a)  (6 pts.) Use minimal cost method to construct an initial basic feasible solution. (b)  (6 pts.) Use Vogel’s method to construct an initial basic feasible solution.

(c)  (18 pts.) Starting with the basic feasible solution in part (a), find the optimal solution, and the minimal cost.