Section A
HAL produces two types of computers: PCs and VAXes. The computers are produced in two locations: New York and Los Angeles. New York can produce up to 800 computers and Los Angeles up to 1,000 computers. HAL can sell up to 900 PCs and 900 VAXes. The profit associated with each production site and computer sale is as follows: New York – PC,
$600; VAX, $800; Los Angeles – PC, $1000; VAX, $1300. The skilled labour required to build each computer at each location is as follows: New York – PC, 2 hours; VAX, 2 hours; Los Angeles – PC, 3 hours; VAX, 4 hours. A total of 4,000 hours of labour are available. Labour is purchased at a cost of $20 per hour. Let
XNP = PCs produced in New York, XLP = PCs produced in Los Angeles, XNV = VAXes produced in New York,
XLV = VAXes produced in Los Angeles, L = labour hours used.
HAL has formulated the following linear programme to determine the optimal product mix.
Max 600XNP + 1000XLP + 800XNV + 1300XLV – 20L
Subject to:
2XNP + 3XLP + 2XNV + 4XLV – L <= 0 (Constraint 1)
XNP + XNV <= 800 (Constraint 2)
XLP + XLV <= 1000 (Constraint 3)
XNP + XLP <= 900 (Constraint 4)
XNV + XLV <= 900 (Constraint 5)
L <= 4000 (Constraint 6)
All variables >= 0
After solving this model with Excel Solver, the following answer and sensitivity reports were obtained.
Continued overleaf…
Microsoft Excel 11.0 Answer Report
Target Cell (Max)
Cell Name Original Value Final Value
$I$7 0 1360000
Adjustable Cells
Cell Name Original Value Final Value
$C$7 XNP 0 0
$D$7 XLP 0 800
$E$7 XNV 0 800
$F$7 XLV 0 0
$G$7 L 0 4000
Constraints
Cell Name Cell Value Formula Status Slack
$H$9 Constraint 1 0 $H$9<=$J$9 Binding 0
$H$10 Constraint 2 800 $H$10<=$J$10 Binding 0
$H$11 Constraint 3 800 $H$11<=$J$11 Not Binding 200
$H$12 Constraint 4 800 $H$12<=$J$12 Not Binding 100
$H$13 Constraint 5 800 $H$13<=$J$13 Not Binding 100
$H$14 Constraint 6 4000 $H$14<=$J$14 Binding 0
Microsoft Excel 11.0 Sensitivity Report
Adjustable Cells
Cell Name Final
Value Reduced
Cost Objective
Coefficient Allowable
Increase Allowable
Decrease
$C$7 XNP 0 -200 600 200 1E+30
$D$7 XLP 800 0 1000 200 25
$E$7 XNV 800 0 800 1E+30 133.333
$F$7 XLV 0 -33.333 1300 33.333 1E+30
$G$7 L 4000 0 -20 1E+30 313.333
Constraints
Cell Name Final
Value Shadow
Price Constraint
R.H. Side Allowable
Increase Allowable
Decrease
$H$9 Constraint 1 0 333.333 0 300 2400
$H$10 Constraint 2 800 133.333 800 100 150
$H$11 Constraint 3 800 0 1000 1E+30 200
$H$12 Constraint 4 800 0 900 1E+30 100
$H$13 Constraint 5 800 0 900 1E+30 100
$H$14 Constraint 6 4000 313.333 4000 300 2400
Using the information above, answer each of the following questions. Each question is independent of the others.
a) Interpret (i.e., what is the meaning of) the objective function and the different constraints of the LP model. Discuss also the optimal solution and objective function value and indicate what constraints are binding. [15%]
b) Interpret the shadow prices of constraints 5 and 6. If 3000 hours of skilled labour were available, what would be HAL’s profit? [15%]
c) Suppose an outside contractor offers to increase the capacity of New York to 850 computers at a cost of $5000. Should HAL hire the contractor? (Your answer should be ‘yes’ or ‘no’ with explanation.) [15%]
Continued overleaf…
d) What would be the new profit if the profit of VAXes decreases by $50? Will the optimal solution be different? [15%]
e) HAL is considering the production of laptops. Laptops can be produced in New York only. There is no limitation on the amount of laptops that can be sold in the market. The total production capacity (including laptops) at New York remains at 800 units. A laptop requires 1.5 hours of skilled labour and would generate a profit of $600. Should HAL produce laptops? (Your answer should be ‘yes’ or ‘no’ with explanation.) [25%]
f) Suppose that the total PC production should be at least twice as large as the total VAX production. Does the current production plan satisfy this condition? If not, how can HAL find the new optimal production plan? [15%]
Question 3.
Braneast Airlines must determine how many airplanes should serve the Boston -New York
– Washington air corridor and which flights to fly. Braneast may fly any of the daily flights shown in the table below. Each flight can be selected at most once. Braneast cannot fly on any other time than those shown in the table. It is possible, though, for an airplane to stay put in the same city for an hour or more. The fixed cost of operating an airplane is
$1000 per day.
Leaves Arrives Flight Revenue ($) Variable Cost of Flight ($)
City Time City Time
NY 9 am Wash 10 am 900 400
NY 2 pm Wash 3 pm 600 350
NY 10 am Bos 11 am 800 400
NY 4 pm Bos 5 pm 1200 450
Wash 9 am NY 10 am 1100 400
Wash 3 pm NY 4 pm 900 350
Wash 10 am Bos 12 noon 1500 700
Wash 5 pm Bos 7 pm 1800 900
Bos 10 am NY 11 am 900 500
Bos 2 pm NY 3 pm 800 450
Bos 11 am Wash 1 pm 1100 600
Bos 3 pm Wash 5 pm 1200 650
Answer the following questions:
(a) Formulate a minimum cost network flow model that can be used to maximise Braneast’s daily profit. Draw a time-expanded network and clearly explain the meaning of the different nodes and arcs. Define the variables, and write down the objective function and one example of each different type of constraint. [80%]
(b) By inspecting your drawing, find a feasible (but not necessarily optimal) solution to the problem. Show this solution on your network. Briefly discuss the flight schedule and the resulting profit. [20%]
Continued overleaf…
Question 4.
Section B
a) Describe the main components of a queuing system. [40%]
b) Consider the following two queuing systems:
o system 1 has two separate queues each with a single server with exponential service times 12 customers/hour and in each queue, customers arrive at a rate 10 customers/hour (Poisson distributed)
o system 2 has a single queue but two identical parallel servers, each server operating at an exponential rate 12 customers/hour, and customers arrive in the queue at a rate 20 customers/hour (Poisson distributed)
Using appropriate queuing models, evaluate the performance of both systems and calculate the average waiting time for a customer; the average number of customers in a queue and in the system, and the average server utilisation. Which system performs best? [30%]
c) In the past few years, the traffic problems into Nottingham have become worse. Now, Derby Road is congested about half of the time. The normal travel time to work for Luc is only 15 minutes when he takes Derby Road and there is no congestion. With congestion, however, it takes Luc 40 minutes to get to work using Derby Road. If Luc decides to take Wollaton Road, it takes 30 minutes, regardless of the traffic conditions. Luc’s utility for travel time is U(15 minutes) = 0.9; U(30 minutes) = 0.7 and U(40 minutes) = 0.2. Determine (i) the route that minimises Luc’s expected travel time; (ii) the route that maximises Luc’s utility; (iii) whether Luc is a risk seeker or risk avoider when it comes to travel time (Hint: plot the utility curve).
[30%]
Continued overleaf…
Question 5.
a) Explain why random numbers are commonly needed in simulation, and briefly outline how these are used. [15%]
b) Ashcroft Airlines flies a six-passenger commuter flight once a day to Gainesville, Florida. A non-refundable one-way fare with a reservation costs $129. The daily demand for this flight is given in the table below, along with the probability distribution of no-shows. A no-show has a reservation but does not arrive on time at the gate and forfeits the fare. Ashcroft currently overbooks at most three passengers per flight. If there are not enough seats for all the passengers at the gate, each passenger that cannot board the flight is refunded the passenger’s fare and also $150 voucher good on any other trip. The fixed cost for a flight is $450.
Demand Probability No-shows Probability
5 0.05 0 0.15
6 0.11 1 0.25
7 0.20 2 0.26
8 0.18 3 0.23
9 0.16 4 0.11
10 0.12
11 0.10
12 0.08
` i) Set up a flow chart showing the logical sequence of events for simulating Ashcroft’s expected profit for this flight. Provide all the details of the formulas used for relevant calculations. [20%]
ii) Using the two-digit random numbers below (in the order as they appear), calculate Ashcroft’s profit per flight and replicate your calculations 10 times. Organise all your calculation in a table. Calculate the expected profit, the occupancy rate of the plane and the probability that Ashcroft profit per flight is higher than £100? Briefly comment on the reliability of your results. [50%]
Random number sequence: 69 56 30 32 66 79 55 24 80 35 10 98 92 92
88 82 13 04 86 31 12 23 40 93 13 42 51 16 17 29 62 08 59 41 47
72 25 96 58 14 68 15 18 99 13 05 03 83 34 78 50 89 98 93 70 11
iii) Explain how you could use this model to investigate Ashroft’s overbooking strategy (no calculations required). [15%]
`