MATH 318: Operations Research

Spring 2023

Assignment 5

Due: Monday, March 27

READ: Hillier & Lieberman: Chapter 4, Section 7; Chapter 6, Sections 1 – 3.

PROBLEMS:  Part I: Write up clear and complete solutions for  the following problems from Hillier and Lieberman:

          4.6 – 14ab     (Solve the problem interactively using the IOR Tutorial software. Then annotate the output to show how to translate back to a solution of the original problem).

          4.6 – 17

          6.1 – 2

          6.1 – 3

          6.1 – 4

Part II

(A) Consider the linear programming problem:

Maximize Z = 2x + 6y + 9z
subject to
x + z ≤ 3 (resource 1)

y + 2z ≤ 5 (resource 2)

and

x, y, z ≥ 0

(i) Construct the dual problem for this primal problem.

(ii) Solve the dual problem graphically. Use this solution to identify the shadow prices for the resources in the primal problem.

(iii) Confirm your results from part (ii) by solving the primal problem by the simplex method and then identifying the shadow prices.

(B) Consider the following problem:

Maximize Z = x + 2y

subject to

-x + y ≤ -2

4x + y ≤ 4

and x, y ≥ 0.

(i) Demonstrate graphically that this problem has no feasible solutions.

(ii) Construct the dual problem.

(iii) Demonstrate graphically that the dual problem has an unbounded objective function.