Seminar 4:
Duality of LP and sensitivity analysis, transportation pro-
blem
Problem 1: (Hillier and Lieberman, 6.7-18.)
Ken and Larry, Inc., supplies its ice cream parlors with three flavors of ice cream:
chocolate, vanilla, and banana. Because of extremely hot weather and a high
demand for its products, the company has run short of its supply of ingredients:
milk, sugar, and cream. Hence, they will not be able to fill all the orders received
from their retail outlets, the ice cream parlors. Owing to these circumstances, the
company has decided to choose the amount of each flavor to produce that will
maximize total profit, given the constraints on supply of the basic ingredients.
The chocolate, vanilla, and banana flavors generate, respectively, $1.00, $0.90,
and $0.95 of profit per gallon sold. The company has only 200 gallons of milk,
150 pounds of sugar, and 60 gallons of cream left in its inventory. The technology
of the production is described by the table
chocolate vanilla banana
milk 0.45 0.5 0.4
sugar 0.5 0.4 0.4
cream 0.1 0.15 0.2
For each of the following parts, answer the question using sensitivity report in
the Excel Solver. Note: Each part is independent (i.e., any change made to the
model in one part does not apply to any other parts).
a) What is the optimal solution and total profit?
b) Suppose the profit per gallon of banana changes to $1.00. Will the optimal
solution change, and what can be said about the effect on total profit?
c) Suppose the profit per gallon of banana changes to 92 cents. Will the optimal
solution change, and what can be said about the effect on total profit?
d) Suppose the company discovers that 3 gallons of cream have gone sour and
so must be thrown out. Will the optimal solution change, and what can be
said about the effect on total profit?
e) Suppose the company has the opportunity to buy an additional 15 pounds
of sugar at a total cost of $15. Should they? Explain.
Problem 2:(Hillier and Lieberman, 8.2-9.) The Cost-Less Corp. supplies
its four retail outlets from its four plants. The shipping cost per shipment from
each plant to each retail outlet is given below
Retail Outlet
1 2 3 4
Plant 1 $500 $600 $400 $200
Plant 2 $200 $900 $100 $300
Plant 3 $300 $400 $200 $100
Plant 4 $200 $100 $300 $200
Plants 1, 2, 3, and 4 make 10, 20, 20, and 10 shipments per month, respectively.
Retail outlets 1, 2, 3, and 4 need to receive 20, 10, 10, and 20 shipments per
month, respectively. The distribution manager, Randy Smith, now wants to
determine the best plan for how many shipments to send from each plant to the
respective retail outlets each month. Randy’s objective is to minimize the total
shipping cost.
a) Use the northwest corner rule to construct an initial basic feasible solution.
b) Use the index method to construct an initial basic feasible solution.
c) Use the VAM method to construct an initial basic feasible solution.
d) Compare the objective values of basic solutions obtained by a-c.
Problem 3: Consider the transportation problem having 4 suppliers and 3 customers
with unit costs of transport given by the following parameter table:
S1 S2 S3 S4 request
C1 11 11 7 12 50
C2 6 9 6 10 200
C3 5 8 11 10 150
capacity 120 90 70 120
a) Formulate mathematical model for this transportation problem
b) Introduce a dummy line to balance the problem if necessary.
c) Use the northwest corner rule to construct an initial basic feasible solution.
d) Starting with the initial basic solution from part (b), interactively apply
the transportation simplex method (MODI) to obtain an optimal solution.
e) Check the solution using Excel Solver