Chapter 5 – Advanced Linear Programming Applications
True / False
1. Revenue management methodology was originally developed for the banking industry.
a.
True
b.
False
False
1
Revenue management
2. The goal of portfolio models is to create a portfolio that provides the best balance between risk and return.
a.
True
b.
False
3. DEA is used to measure the relative efficiency of two (or more) units in different industries, such as a bank and a
school.
a.
True
b.
False
False
1
Data envelopment analysis
4. If the inputs of the composite unit in DEA are greater than the inputs for an individual unit, then the composite is more
efficient.
a.
True
b.
False
False
1
Data envelopment analysis
5. It is possible for DEA to show all operating units to be relatively inefficient.
a.
True
b.
False
False
1
Data envelopment analysis
6. DEA does not necessarily identify the operating units that are relatively efficient.
a.
True
b.
False
True
1
Data envelopment analysis
Chapter 5 – Advanced Linear Programming Applications
7. DEA will show all but one operating unit to be relatively inefficient in the case where an operating unit producing the
most of every output and also consumes the least of every input.
a.
True
b.
False
True
1
8. For a two-person, zero-sum, mixed-strategy game, it is necessary to solve the LP for each player in order to learn both
players’ optimal strategies.
a.
True
b.
False
False
1
9. If a pure strategy solution exists for a two-person, zero-sum game, it is the optimal solution to the game.
a.
True
b.
False
True
1
10. In a two-person, zero-sum, pure-strategy game, there is no advantage to either player to switch from its strategy even
if one of the players discovers the other player’s strategy in advance.
a.
True
b.
False
True
1
11. In portfolio models, risk is minimized by diversification.
a.
True
b.
False
12. Revenue management methodology can be applied in the case of nonperishable assets.
a.
True
b.
False
True
1
13. In a revenue management model, dual prices tell reservation agents the revenue loss associated with overbooking each
Chapter 5 – Advanced Linear Programming Applications
ODIF.
a.
True
b.
False
False
1
Revenue management
14. In game theory, the player seeking to maximize the value of the game selects a maximax strategy.
a.
True
b.
False
False
1
Game theory: competing for market share
15. The analysis of a two-person, zero-sum game begins with checking to see whether a pure strategy exists.
a.
True
b.
False
True
1
Game theory
16. Revenue management methodology enables an airline to maximize the number of full-fare seats it sells on each flight.
a.
True
b.
False
False
1
Revenue management
Multiple Choice
17. Revenue management methodology was originally developed for
a.
a cruise line.
b.
an airline.
c.
a car rental company.
d.
a hotel chain.
b
1
Revenue management
18. The overall goal of portfolio models is to create a portfolio that provides the best balance between
a.
short-term and long-term investments.
b.
gains and losses.
c.
risk and return.
d.
liquidity and stability.
Chapter 5 – Advanced Linear Programming Applications
19. The composite unit in DEA
a.
has as output a weighted average of the outputs of the individual units.
b.
has as input a weighted average of the inputs of the individual units.
c.
has outputs greater than or equal to the outputs of any individual unit.
d.
All of the alternatives are correct.
d
1
Data envelopment analysis
20. Modern revenue management systems maximize revenue potential for an organization by helping to manage
a.
pricing strategies.
b.
reservation policies.
c.
short-term supply decisions.
d.
All of the alternatives are correct.
d
1
Revenue management
21. A DEA linear programming model involving 4 input measures and 3 output measures will have
a.
7 constraints.
b.
8 constraints.
c.
12 constraints.
d.
13 constraints.
b
1
Data envelopment analysis
22. In general, every DEA linear programming model will include a constraint that requires the weights for the operating
units to sum to
a.
1.
b.
the number of operating units.
c.
100.
d.
any arbitrary value.
1
Data envelopment analysis
23. For a two-person, zero-sum, mixed-strategy game, it is necessary to solve the LP for only one of the players to learn
the optimal strategies for both players.
a.
1.
b.
the number of operating units.
c.
100.
1
Portfolio models and asset allocation
Chapter 5 – Advanced Linear Programming Applications
d.
any arbitrary value.
a
1
Game theory
24. For a two-person, zero-sum, mixed-strategy game, each player selects its strategy according to
a.
what strategy the other player used last.
b.
a fixed rotation of strategies.
c.
a probability distribution.
d.
the outcome of the previous game.
c
1
Game theory
25. If it is optimal for both players in a two-person, zero-sum game to select one strategy and stay with that strategy
regardless of what the other player does, the game
a.
has more than one equilibrium point.
b.
will have alternating winners.
c.
will have no winner.
d.
has a pure strategy solution.
d
1
Game theory
26. A linear programming application used to measure the relative efficiency of operating units with the same goals and
objectives is
a.
game theory.
b.
asset allocation.
c.
data envelopment analysis.
d.
revenue management.
c
1
Data envelopment analysis
27. In data envelopment analysis, the percentage of an individual operating unit’s resources that are available to the
composite operating unit is the
a.
efficiency index.
b.
saddle point.
c.
maximin.
d.
minimax.
a
1
Data envelopment analysis
28. To develop a portfolio that provides the best return possible with a minimum risk, the linear programming model will
Chapter 5 – Advanced Linear Programming Applications
have an objective function which
a.
minimizes the maximum risk.
b.
minimizes total risk.
c.
maximizes return and minimizes risk.
d.
maximizes the minimum return.
29. Revenue management methodology enables an airline to
a.
maximize the number of full-fare seats it sells on each flight.
b.
minimize the number of discount-fare seats it sells on each flight.
c.
increase the average number of passengers per flight.
d.
decrease the number of overbooked flights.
c
1
Revenue management
Subjective Short Answer
30. The Eastern Washington County School Corporation is interested in comparing educational performance at four
elementary schools and has hired you to prepare a DEA model to do so. After detailed conversations with the corporation
administrative staff and the building principals, you have isolated the following input and output measurements:
Input Measures
Output Measures
Average classroom size
Percent of children in remedial classes
Percent of students on reduced price lunch
Average first grade score on standard test
Average number of parent volunteer hours per week
Average fifth grade score on standard test
Data is collected for each school on each measure
School
Archer
Hayes
Ralston
Creekside
Inputs
Classroom size
21
28
32
20
% reduced lunch
10
8
25
2
Avg. vol. hours
30
46
15
64
Outputs
% remediation
15
12
19
3
1st grade score
83
84
62
85
5th grade score
76
72
53
79
Develop the DEA model that would evaluate the efficiency of Ralston Elementary School.
Let
A = the weight applied to inputs and outputs for Archer Elementary
H = the weight applied to inputs and outputs for Hayes Elementary
R = the weight applied to inputs and outputs for Ralston Elementary
C = the weight applied to inputs and outputs for Creekside Elementary
Min
s.t.
A + H + R + C = 1
.15A + .12H + .19R + .03C ≥ .19
Chapter 5 – Advanced Linear Programming Applications
31. Mountainside State Park has four visitor centers. To study the operation of these centers, a DEA model has been
developed that compares inputs (size, number of staff, weekly hours of operation) and outputs (% of visitors attending
educational program, daily sales in gift shop). The computer solution is shown below. What can you conclude about the
efficiency of the North center?
LINEAR PROGRAMMING PROBLEM
Min
1E+0wn+0ws+0we+0ww
s.t.
1) −400E+400wn+1200ws+2400we+1500ww<0
2) −3E+3wn+6ws+10we+7ww<0
3) −56E+56wn+108ws+92we+108ww<0
4) −49E+49wn+83ws+56we+72ww>0
5) −38E+38wn+425ws+1200we+630ww>0
6) +1wn+1ws+1we+1ww=1
OPTIMAL SOLUTION
Objective Function Value = 1.000
Variable
Value
Reduced Cost
E
1.000
0.000
wn
1.000
0.000
ws
0.000
0.000
we
0.000
0.000
ww
0.000
0.000
Constraint
Slack/Surplus
Dual Price
1
0.000
0.008
2
0.000
0.000
3
0.000
0.001
4
0.000
−0.034
5
0.000
−0.013
6
0.000
−1.000
evidence that the North center is inefficient.
1
Data envelopment analysis
32. The output shows the solution to a DEA model where facilities in Seaview (S), Farmington (F), Lewiston (L), and San
Domingo (D) are compared. The inputs, in order, are number of machines, size of work force, and goodness of location.
The outputs, in order, are production, quality rating, and on-time completion percentage. The model examines the
efficiency of Lewiston.
MIN
0S+0F+0L+0D+1E
S.T.
1) 1S+1F+1L+1D=1
83A + 84H + 62R + 85C ≥ 62
76A + 72H + 53R + 79C ≥ 53
21A + 28H + 32R + 20C ≤ 32E
.10A + .08H + .25R + .02C ≤ .25E
30A + 46H + 15R + 64C ≤ 15
Data envelopment analysis
Chapter 5 – Advanced Linear Programming Applications
2) 5S+22F+36L+15D−36E<0
3) 400S+1500F+3150L+1060D−3150E<0
4) 24S+13F+32L+17D−32E<0
5) 800S+2900F+1860L+1700D+0E>1860
6) 95S+92F+83L+94D+0E>83
7) 83S+85F+90L+91D+0E>90
OPTIMAL SOLUTION
Objective Function Value = 0.510
Variable
Value
Reduced Cost
S
0.000
0.385
F
0.167
0.000
L
0.000
0.490
D
0.833
0.000
E
0.510
0.000
Constraint
Slack/Surplus
Dual Price
1
0.000
1.365
2
2.208
0.000
3
474.479
0.000
4
0.000
0.031
5
40.000
0.000
6
10.667
0.000
7
0.000
−0.021
a.
Is the Lewiston plant efficient? Why or why not? If not, which plants should it emulate in
order to improve?
b.
How much more production does the composite facility provide than the Lewiston site?
c.
What is the quality rating for the composite facility?
should emulate Farmington and San Domingo.
b.
40
c.
83 + 10.667 = 93.667
1
Data envelopment analysis
33. Consider a two-person, zero-sum game where the payoffs listed below are the winnings for Player A. Identify the pure
strategy solution. What is the value of the game?
Player B Strategies
Player A Strategies
b1
b2
b3
a1
5
5
4
a2
1
6
2
a3
7
2
3
Value of game: Gain of 4 for Player A; loss of 4 for Player B.
1
Game theory
Chapter 5 – Advanced Linear Programming Applications
34. Consider a two-person, zero-sum game where the payoffs listed below are the winnings for Company X. Identify the
pure strategy solution. What is the value of the game?
Company Y Strategies
Company X Strategies
y1
y2
y3
x1
3
5
9
x2
8
4
3
x3
7
6
7
Value of game: Gain of 6 for Company X; loss of 6 for Company Y.
1
Game theory
35. Consider the following two-person, zero-sum game. Payoffs are the winnings for Company X. Formulate the linear
program that determines the optimal mixed strategy for Company X.
Company Y Strategies
Company X Strategies
y1
y2
y3
x1
4
3
9
x2
2
5
1
x3
6
1
7
Max
s.t.
4PA1 + 2PA2 + 6PA3 − GAINA ≥ 0
(Strategy B1)
3PA1 + 5PA2 + 1PA3 − GAINA ≥ 0
(Strategy B2)
9PA1 + 1PA2 + 7PA3 − GAINA ≥ 0
(Strategy B3)
(Probabilities must sum to 1)
(Non-negativity)
1
Game theory
36. Shown below is the solution to the linear program for finding Player A’s optimal mixed strategy in a two-person, zero-
sum game.
OBJECTIVE FUNCTION VALUE = 3.500
VARIABLE
VALUE
REDUCED COSTS
PA1
0.050
0.000
PA2
0.600
0.000
PA3
0350
0.000
GAINA
3.500
0.000
CONSTRAINT
SLACK/SURPLUS
DUAL PRICES
1
0.000
−0.500
2
0.000
−0.500
3
0.000
0.000
4
0.000
3.500
a.
What is Player A’s optimal mixed strategy?
Chapter 5 – Advanced Linear Programming Applications
b.
What is Player B’s optimal mixed strategy?
c.
What is Player A’s expected gain?
d.
What is Player B’s expected loss?
a.
Player A’s optimal mixed strategy:
b.
Player B’s optimal mixed strategy:
c.
Player A’s expected gain: 3.500
d.
Player B’s expected loss: 3.500
1
Game theory
37. Portfolio manager Max Gaines needs to develop an investment portfolio for his conservative clients. His task is to
determine the proportion of the portfolio to invest in each of the five mutual funds listed below so that the portfolio
provides the best return possible with a minimum risk. Formulate the maximin linear program.
Annual Returns (Planning Scenarios)
Mutual Fund
Year 1
Year 2
Year 3
Year 4
International Stock
22.37
26.73
6.46
−3.19
Large-Cap Blend
14.88
18.61
10.52
5.25
Mid-Cap Blend
19.45
18.04
5.91
−1.94
Small-Cap Blend
13.79
11.33
−2.07
6.85
Intermediate Bond
7.29
8.05
9.18
3.92
Max M
(Scenario 1)
(Scenario 2)
(Scenario 3)
(Scenario 4)
(Total proportion must equal 1)
1
Portfolio models and asset allocation
38. Portfolio manager Max Gaines needs to develop an investment portfolio for his clients who are willing to accept a
moderate amount of risk. His task is to determine the proportion of the portfolio to invest in each of the five mutual funds
listed below so that the portfolio provides an annual return of no less than 3%. Formulate the appropriate linear program.
Annual Returns (Planning Scenarios)
Mutual Fund
Year 1
Year 2
Year 3
Year 4
International Stock
22.37
26.73
6.46
−3.19
Large-Cap Blend
14.88
18.61
10.52
5.25
Mid-Cap Blend
19.45
18.04
5.91
−1.94
Small-Cap Blend
13.79
11.33
−2.07
6.85
Chapter 5 – Advanced Linear Programming Applications
Intermediate Bond
7.29
8.05
9.18
3.92
Max 13.093IS + 12.315LC + 10.365MC + 7.475SC + 7.110IB
22.37IS + 14.88LC + 19.45MC + 13.79SC + 7.29IB ≥ 3
(Scenario 1)
26.73IS + 18.61LC + 18.04MC + 11.33SC + 8.05IB ≥ 3
(Scenario 2)
6.46IS + 10.52LC + 5.91MC − 2.07SC + 9.18IB ≥ 3
(Scenario 3)
(Scenario 4)
IS + LC + MC + SC + IB = 1
(Total proportion must equal 1)
IS, LC, MC, SC, IB ≥ 0
(Non-negativity)
1
Portfolio models and asset allocation
39. Hervis Car Rental in Austin, TX has 50 high-performance Shelby-H Mustangs in its rental fleet. These cars will be in
greater demand than usual during the last weekend in July when the Central Texas Mustang Club holds its annual rally in
Austin. At times like this, Hervis uses a revenue management system to determine the optimal number of reservations to
have available for the Shelby-H cars.
Hervis has agreed to have at least 60% of its Shelby-H Mustangs available for rally attendees at a special rate. Although
many of the rally attendees will request a Saturday and Sunday two-day package, some attendees may select a Saturday
only or a Sunday only reservation. Customers not attending the rally may also request a Saturday and Sunday two-day
package, or make a Saturday only or Sunday only reservation. Thus, six types of reservations are possible. The cost for
each type of reservation is shown here.
Two-Day
Saturday
Sunday
Package
Only
Only
Rally
125
$75
$65
Regular
$150
$85
$75
The anticipated demand for each type of reservation is as follows:
Two-Day
Saturday
Sunday
Package
Only
Only
Rally
20
10
15
Regular
10
20
25
Hervis Car Rental would like to determine how many Shelby-H Mustangs to make available for each type of reservation
in order to maximize total revenue.
a.
Define the decision variables.
b.
Formulate a linear programming model for this revenue management application.
a.
RATW = number of reservations available for rally attendees for two days
RGTW = number of reservations available for regular customers for two days
RASA = number of reservations available for rally attendees for Saturday only
RGSA = number of reservations available for regular customers for Saturday only
RASU = number of reservations available for rally attendees for Sunday only
RGSU = number of reservations available for regular customers for Sunday only
b.
Max 125RATW + 155RGTW + 75RASA + 90RGSA + 65RASU + 80RGSU
s.t.
RATW + RETW + RASA + RGSA ≤ 50
(Shelby-H Saturday Capacity)
Chapter 5 – Advanced Linear Programming Applications
40.
LeapFrog Airways provides passenger service for Indianapolis, Baltimore, Memphis, Austin, and Tampa. LeapFrog has
two WB828 airplanes, one based in Indianapolis and the other in Baltimore. Each morning the Indianapolis based plane
flies to Austin with a stopover in Memphis, and the Baltimore based plane flies to Tampa with a stopover in Memphis.
Both planes have a coach section with a 120–seat capacity.
LeapFrog uses two fare classes: a discount fare D class and a full fare F class. Leapfrog’s products, each referred to as an
origin destination itinerary fare (ODIF), are listed below with their fares and forecasted demand.
ODIF
Origin
Destination
Fare Class
ODIF Code
Fare
Demand
1
Indianapolis
Memphis
D
IMD
175
44
2
Indianapolis
Austin
D
IAD
275
25
3
Indianapolis
Tampa
D
ITD
285
40
4
Indianapolis
Memphis
F
IMF
395
15
5
Indianapolis
Austin
F
IAF
425
10
6
Indianapolis
Tampa
F
ITF
475
8
7
Baltimore
Memphis
D
BMD
185
26
8
Baltimore
Austin
D
BAD
315
50
9
Baltimore
Tampa
D
BTD
290
42
10
Baltimore
Memphis
F
BMF
385
12
11
Baltimore
Austin
F
BAF
525
16
12
Baltimore
Tampa
F
BTF
490
9
13
Memphis
Austin
D
MAD
190
58
14
Memphis
Tampa
D
MTD
180
48
15
Memphis
Austin
F
MAF
310
14
16
Memphis
Tampa
F
MTF
295
11
Develop a linear programming model for LeapFrog’s problem situation and determine how many seats LeapFrog should
allocate to each ODIF.
Chapter 5 – Advanced Linear Programming Applications
Chapter 5 – Advanced Linear Programming Applications
Essay
41. List several industries in which revenue management has been applied and list several different types of decisions
being made with the aid of the methodology.
42. List several types of organizations with multiple operating units where data envelopment analysis might be applied
and give examples of possible inputs and outputs for each organization.
43. Describe the steps used to determine when a two-person, zero-sum game has a pure-strategy solution.
44. Write a summary of the DEA approach and explain how you would interpret the solution.
45. Explain the differences between the LP formulations for a conservative portfolio and moderate-risk portfolio.
Chapter 5 – Advanced Linear Programming Applications
46. Explain the difference between a pure strategy and a mixed strategy in game theory.
47. Explain the logic of a DEA model. On what basis can the facility being evaluated be judged as relatively inefficient?