ADDITIONAL L.P.
EXERCISES
A Production Routing Problem
El Paso Industrial Corporation (EPIC) manufactures two products that can be produced
on two different production lines. Both products have their lowest production costs when
produced on the more modern of the two production lines. However, the modern
production line does not have the capacity to handle the total production. As a result,
some production will have to be routed to the older production line. The following data
show total production requirements, production line capacities, and production costs.
Production Cost/Unit Minimum
Modern Old Production
Product Line Line Requirements
Gizmo $3.00 $5.00 500 units
Dubya $2.50 $4.00 700 units
Production Capacities 800 units 600 units
Mr. Geek N. Hacker formulates an LP model for this production routing problem,
defining the decision variables as follows:
xij number of product i to produce on production line j
with i 1 for product Gizmo and i 2 for product Dubya
and j 1 for the modern production line and j 2 for the old production line.
Mr. Hacker then uses Storm for Windows 4.0 to solve the problem, and obtains the output
shown below and on the next page.
EPIC - Production Routing
PROBLEM DATA IN EQUATION STYLE
Minimize
3 X11 + 5 X12 + 2.5 X21 + 4 X22
Subject to
CONSTR 1 1 X11 + 1 X12 >= 500
CONSTR 2 1 X21 + 1 X22 >= 700
CONSTR 3 1 X11 + 1 X21 <= 800
CONSTR 4 1 X12 + 1 X22 <= 600
0 <= X11
0 <= X12
0 <= X21
0 <= X22
EPIC - Production Routing
OPTIMAL SOLUTION - DETAILED REPORT
Variable Value Cost Red. cost Status
1 X11 500.0000 3.0000 0.0000 Basic
2 X12 0.0000 5.0000 0.5000 Lower bound
3 X21 300.0000 2.5000 0.0000 Basic
4 X22 400.0000 4.0000 0.0000 Basic
Slack Variables
5 CONSTR 1 0.0000 0.0000 4.5000 Lower bound
6 CONSTR 2 0.0000 0.0000 4.0000 Lower bound
7 CONSTR 3 0.0000 0.0000 1.5000 Lower bound
8 CONSTR 4 200.0000 0.0000 0.0000 Basic
Objective Function Value = 3850
EPIC - Production Routing
OPTIMAL SOLUTION - DETAILED REPORT
Constraint Type RHS Slack Shadow price
1 CONSTR 1 >= 500.0000 0.0000 4.5000
2 CONSTR 2 >= 700.0000 0.0000 4.0000
3 CONSTR 3 <= 800.0000 0.0000 -1.5000
4 CONSTR 4 <= 600.0000 200.0000 0.0000
Objective Function Value = 3850
EPIC - Production Routing
SENSITIVITY ANALYSIS OF COST COEFFICIENTS
Current Allowable Allowable
Variable Coeff. Minimum Maximum
1 X11 3.0000 -1.5000 3.5000
2 X12 5.0000 4.5000 1.9531E+34
3 X21 2.5000 2.0000 4.0000
4 X22 4.0000 2.5000 4.5000
EPIC - Production Routing
SENSITIVITY ANALYSIS OF RIGHT-HAND SIDE VALUES
Current Allowable Allowable
Constraint Type Value Minimum Maximum
1 CONSTR 1 >= 500.0000 100.0000 700.0000
2 CONSTR 2 >= 700.0000 300.0000 900.0000
3 CONSTR 3 <= 800.0000 600.0000 1200.0000
4 CONSTR 4 <= 600.0000 400.0000 Infinity
2
a. Provide a brief interpretation of the optimal solution in the language of the given
problemi.e., a real world solution specified in English.
b. Write out the LP model in standard form.
c. Surplus variables pertain to (encircle letter corresponding to the right answer):
A. constraints 1 and 2.
B. constraints 3 and 4.
C. all four constraints.
D. none of the four constraints.
d. Identify which of the four constraints are binding constraints.
e. Provide a brief interpretation in the language of the problemin Englishof the
slack of 200.000 reported for constraint 4.
f. If the cost of producing product Dubya on the modern production line is actually
$4.50 per unit, will the optimal solution change? Explain briefly why or why not.
g. If the cost of producing product Gizmo on the old production line is actually
$7.50, will the optimal solution change? Explain briefly why or why not.
h. If the capacity of the modern production line were to be increased to 1,000 units,
then the optimal VOF would ____________________ [increase or decrease?].
By how much? Explain/show computation for your answers.
i. If the requirement for Dubyas were to be increased to 800 units, by how much
would the optimal VOF change? Explain/show computation for your answer.
j. If the requirement for Gizmos were to be increased to 800 units, by how much
would the optimal VOF change? Explain/show computation for your answer.
3
A Project Investment Portfolio Problem*
Bubba Corporation has $30 million available for the coming year to allocate to its three
subsidiaries. Because of commitments to stability of personnel employment and for other
reasons, the corporation has established a minimal level of funding for each subsidiary.
These minimal funding levels are $3 million, $5 million, and $8 million, respectively.
Owing to the nature of its operation, subsidiary 2 cannot utilize more than $17 million
without major new capital expansion. The corporation is unwilling to undertake such
expansion at this time. Each subsidiary has the opportunity to conduct various projects
with the funds it receives. A rate of return (as a percent of investment) has been
established for each project. In addition, certain of the projects permit only limited
investment. The data of each project are given.
Rate of Upper Limit
Subsidiary Project Return of Investment
1 8% $6 million
A 2 6% $5 million
3 7% $9 million
4 5% $7 million
B 5 8% $10 million
6 9% $4 million
7 10% $6 million
C 8 6% $3 million
a. Formulate this problem as a linear programming model. (It is suggested that
000,000 be dropped when specifying investment figures in your model.)
b. Solve the problem using Storm for Windows 4.0.
c. If the rate of return on project 1 were only 7.5%, would the optimal investment
portfolio changeall other figures remaining the same?
d. If the rate of return on project 2 were only 7.5%, would the optimal investment
portfolio changeall other figures remaining the same?
e. Interpret the nonzero shadow prices reported in the Storm output. What is the
meaning of a negative shadow price?
* Problem borrowed from Linear Programming and Network Flows, 2/e, by Bazaraa,
Jarvis and Sherali (Wiley, 1990).
4
A Machine Scheduling Problem*
El Paso del Norte Steel Corporation produces four sizes of I beams: small, medium, large,
and extra large. These beams can be produced on any of three machines: A, B, and C.
The lengths in feet of the I beams that can be produced on the machines per hour are as
follows:
I-Beam Machine
Size A B C
Small 300 600 800
Medium 250 400 700
Large 200 350 600
Extra Large 100 200 300
Each machine can be used up to 40 hours per week, and hourly operating costs of
machines A, B, and C are $30.00, $50.00, and $80.00, respectively. Weekly requirements
of the different sizes of I beams are 10,000, 8,000, 6,000, and 6,000 feet.
a. Formulate the machine scheduling problem as an LP model.
b. Solve the problem using Storm for Windows 4.0.
* Problem borrowed from Linear Programming and Network Flows, 2/e, by Bazaraa,
Jarvis and Sherali (Wiley, 1990).
