Page 298 -

278 CHAPTER 6 SIMPLEX-BASED SENSITIVITY ANALYSIS AND DUALITY

Photo Chemicals management requires that at least 30 litres of product 1 and at least 20
litres of product 2 be produced. They also require that at least 80 kilos of a perishable raw
material be used in production. A linear programming formulation of the problem is as
follows:

Min 1x 1 þ 1x 2
s:t:
1x 1 30 Minimum product 1
1x 2 20 Minimum product 2
1x 1 þ 2x 2 80 Minimum raw material
x 1 ; x 2 0

a. Write the dual problem.
b. Solve the dual problem. Use the dual solution to show that the optimal production plan
is x 1 ¼ 30 and x 2 ¼ 25.
c. The third constraint involves a management request that the current 80 kilos of a
perishable raw material be used. However, after learning that the optimal solution calls
for an excess production of five units of product 2, management is reconsidering the
raw material requirement. Specifically, you have been asked to identify the cost effect if
this constraint is relaxed. Use the dual variable to indicate the change in the cost if only
79 kilos of raw material have to be used.
16 Consider the linear programme:
Max 3x 1 þ 2x 2
s:t:
1x 1 þ 2x 2 8
2x 1 þ 1x 2 10
x 1 ; x 2 0
a. Solve this problem using the Simplex method. Keep a record of the value of the
objective function at each extreme point.
b. Formulate and solve the dual of this problem using the graphical procedure.
c. Compute the value of the dual objective function for each extreme-point solution of the
dual problem.
d. Compare the values of the objective function for each primal and dual extreme-point
solution.
e. Can a dual feasible solution yield a value less than a primal feasible solution? Can you
state a result concerning bounds on the value of the primal solution provided by any
feasible solution to the dual problem?

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.