The Transportation Safety Administration needs to train 200 airport security screeners in new procedures over 4 days while maintaining enough daily screening capacity. A linear program is formulated to determine the minimum-cost training plan. It assigns screeners to be trained on each day as decision variables, with the objective of minimizing total 4-day training costs. Constraints ensure sufficient daily screening capacity and that all 200 screeners are trained. The optimal solution trains 0, 28, 23 and 149 screeners on days 1 through 4, with a total cost of $147,580.
The Transportation Safety Administration needs to train 200 airport security screeners in new procedures over 4 days while maintaining enough daily screening capacity. A linear program is formulated to determine the minimum-cost training plan. It assigns screeners to be trained on each day as decision variables, with the objective of minimizing total 4-day training costs. Constraints ensure sufficient daily screening capacity and that all 200 screeners are trained. The optimal solution trains 0, 28, 23 and 149 screeners on days 1 through 4, with a total cost of $147,580.
The Transportation Safety Administration needs to train 200 airport security screeners in new procedures over 4 days while maintaining enough daily screening capacity. A linear program is formulated to determine the minimum-cost training plan. It assigns screeners to be trained on each day as decision variables, with the objective of minimizing total 4-day training costs. Constraints ensure sufficient daily screening capacity and that all 200 screeners are trained. The optimal solution trains 0, 28, 23 and 149 screeners on days 1 through 4, with a total cost of $147,580.
The Transportation Safety Administration needs to train 200 airport security screeners in new procedures over 4 days while maintaining enough daily screening capacity. A linear program is formulated to determine the minimum-cost training plan. It assigns screeners to be trained on each day as decision variables, with the objective of minimizing total 4-day training costs. Constraints ensure sufficient daily screening capacity and that all 200 screeners are trained. The optimal solution trains 0, 28, 23 and 149 screeners on days 1 through 4, with a total cost of $147,580.
Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 1 of 12
Indian School of Business
Mohali, India Decision Models & Optimization Term II, 2016
Prof. Anjani Jain Prof. Ziv Katalan
Yale School of Management The Wharton School Yale University University of Pennsylvania anjani.jain@yale.edu katalan@wharton.upenn.edu
Instructions This examination is open book and open notes. Calculators are allowed, but not laptop or handheld computers capable of running spreadsheets. The examination will last exactly two hours; feel free to ask questions during the examination if there is any confusion. Write all your answers in the space provided within this exam booklet.
In all multiple-choice questions, you need only check the correct answer. We will not consider supplementary explanations when grading these questions.
Final Examination Good luck! Question Part points out of Last Name: _____________________ 1 a 2 b 2 First Name: _____________________ c 2 d 2 Section: _____________________ e 2 f 2 g 3 total 15
2 total 10
3 a 4 b 3 c 2 d 2 e 3 f 3 g 4 h 4 total 25
Total 50 Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 2 of 12
The Transportation Safety Administration’s (TSA’s) Philadelphia International Airport operation
employs 200 officers who screen carry-on baggage. Each screener can handle 400 carry-on bags per day.
The officers must be trained in new security procedures. Training an officer takes one day, and during this day an employee-in-training can screen only 300 bags. After s/he is trained, an officer using the new procedures will be able to screen 440 bags per day, 10% more than the current rate.
Currently screeners make $180 per day. Employees-in-training will receive an extra $10 ($190 for the day), and fully trained employees will make $200 per day.
The TSA wants the Philadelphia operation to train all 200 screeners within the next 4 days. At the same time, on each day the facility must maintain enough capacity to process the projected volumes of baggage shown in Table 1.
Day 1 2 3 4 Bags 70,220 76,400 78,820 67,140 Table 1: Projected Numbers of Bags to Screen Each Day
The following linear program determines a least-cost plan for training the employees.
Decision Variables
i = 1,2,3,4 index for the day
Ti = number of employees undergoing security training on day i
Objective Function
Min{790 T1 + 770 T2 + 750 T3 + 730 T4}
For example, the 4-day cost of an employee trained on day 2 equals $770 (= $180+$190+$200+$200).
Non-negativity Ti ≥ 0,i=1,2,3,4 Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 3 of 12
Here is a Spreadsheet Implementation of the LP
A B C D E F G H I 1 Decision Variables: Number to Train Each Day Total Number to 2 T1 T2 T3 T4 Trained Train 3 0.00 28.00 23.00 149.00 200 = 200 4 5 Total 6 4-day cost of an employee trained on day… Cost 7 $ 790 $ 770 $ 750 $ 730 $ 147,580.00 8 9 Capacity of employee trained on day… Capacity Bags 10 day 1 day 2 day 3 day 4 Available to Screen 11 300 400 400 400 80,000.00 >= 70,220 (day 1) 12 440 300 400 400 77,200.00 >= 76,400 (day 2) 13 440 440 300 400 78,820.00 >= 78,820 (day 3) 14 440 440 440 300 67,140.00 >= 67,140 (day 4)
Constraints Final Shadow Constraint Allowable Allowable Cell Name Value Price R.H. Side Increase Decrease $F$11 capac. day 1 80,000 0 70,220 9,780.00 1E+30 $F$12 capac. day 2 77,200 0 76,400 800.00 ######### $F$13 capac. day 3 78,820 0.14 78,820 1,120.00 3,920.00 $F$14 capac. day 4 67,140 0.24 67,140 1,568.00 5,488.00 $F$3 total trained 200 599.39 200 6.38 0.95
Answer each of the following questions. Each question is independent of the others. For your answers you may assume that fractional numbers of employees can be trained each day.
a) (2 points) Suppose that the total 4-day cost of training an employee on day 2 decreases by $10 and the problem is re-solved. Which one of the following statements holds? ( ) The overall cost and the optimal solution values all stay the same. ( ) The overall cost stays the same but the optimal solution values change. ( ) The overall cost changes but the optimal solution values stay the same. ( ) The overall cost and the optimal solution values all change. Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 4 of 12
b) (2 points) The allowable increase for the objective function coefficient of T1 has been hidden. Given the LP results and the rest of the sensitivity report, what can you say about the hidden value? ( ) The allowable increase is infinite. ( ) The allowable increase equals $790. ( ) The allowable increase equals $20. ( ) The allowable increase equals $0.
c) (2 points) Suppose that the number of bags to be screened on day 3 decreases by 3,000 and the problem is re-solved. Which one of the following statements holds? ( ) The overall cost goes down by $420 but the solution values stay the same. ( ) The overall cost goes down by $420 and the solution values change. ( ) The overall cost does not change and the solution values stay the same. ( ) The overall cost does not change but the solution values change.
d) (2 points) Suppose that the number of bags to be screened on day 4 increases by 1,600 and the problem is re-solved. Which one of the following statements holds? ( ) The overall cost goes up by at most $384, maybe less. ( ) The overall cost goes up by exactly $384. ( ) The overall cost goes up by at least $384, maybe more. ( ) It cannot be determined from the sensitivity report which of the above cases is true.
e) (2 points) The allowable increase and decrease for Capacity on Day 2 have been hidden. Given the LP results and the rest of the sensitivity report, what is the allowable decrease? ( ) The allowable decrease equals 0. ( ) The allowable decrease equals 800. ( ) The allowable decrease equals 76,400. ( ) The allowable decrease is infinite.
f) (2 points) The TSA is considering transferring an additional screener from another location. The moving cost for the employee is $2,000, and she would be trained and paid using the same scheme, along with the 200 current screeners. After re-running the LP, which one of the statements below will be true? ( ) Transferring and training the screener will increase TSA’s costs by less than $2,650. ( ) Transferring and training the screener will increase TSA’s costs between $2,650 and $2,730. ( ) Transferring and training the screener will increase TSA’s costs between $2,730 and $2,790. ( ) The increase in costs to TSA cannot be determined. Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 5 of 12
g) (3 points) TSA wants to ensure that, if more than 20 employees are trained on day 2, then at least 30 will be trained on day 3. Extend the original formulation to ensure this. Your formulation must be an integer LP.
New decision variables, if any:
Change to objective function, if any:
New or modified constraints, if any:
Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 6 of 12
2. Princeton Review (10 points)
Princeton Review offers preparation (“prep”) classes for students taking standardized tests, and its West Philadelphia location is scheduling upcoming classes for the GMAT and GRE. Table 1 shows the demand for the coming course period. Class GMAT GRE Demand (students) 212 238 Table 1: Estimated Student Demand for Prep Classes Test prep instructors are people who have previously done well on the tests who then undergo additional training. Table 2 shows the numbers of instructors available to teach each course. Class GMAT GRE Instructors Available 14 15 Table 2: Numbers of Instructors Available to Teach Prep Classes The West Philadelphia location has 30 classrooms that can be used to teach sections of the courses. Each room requires one instructor and can serve up to 12 or 25 students, depending on its size. Rooms cannot be split between courses. Each instructor can only teach one course. Table 3 shows the number of small and large classrooms Classroom Size 12 25 Rooms Available 20 10 Table 3: Numbers of Rooms Available for Prep Classes Instructors are paid $5,000 for teaching a course in a small classroom and $8,000 per large classroom. Instructors are not paid if they do not teach a course. Princeton Review wants to assign classes to rooms to minimize its instructor costs, while accommodating the demand listed in Table 1. Formulate a linear program to solve Princeton Review’s problem.
Decision Variables
Objective Function
Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 7 of 12
Constraints
Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 8 of 12
3. Metro Corp’s Nirvana Real Estate Development Project (25 points)
The MetroCorp Syndicate’s (MCS) flagship project Nirvana comprises 250 prestigious villas on 100 acres of land. The Nirvana project is expected to be completed in three years.
Financing of the project:
MCS has raised 400mm rupees (Rs) in capital to invest in the project. In addition, MCS has negotiated a revolving line of credit with semi-annual interest of 3.5%. Any surplus can be invested in a short-term savings account bearing 3% interest semi-annually.
Project Development costs:
The development costs (in Rs mm) during the next three years are listed in the table below.
Semi-Annual Time Index ( t ) 0 1 2 3 4 5 6
Development Cost Ct 400 350 300 200 300 250 100
Unit Prices, Demand and Revenue from Sales
The initial price P0 of a villa at the launch of the project (t = 0) is Rs 9mm. The unit price Pt follows a log-Normal process with annual return parameters of = 5% and standard deviation = 20%. The demand for villas in each six-month period is uncertain and is modeled as a random variable Dt.1 The expected demand for each period is listed in the table below.
Semi-Annual Time Index ( t ) 0 1 2 3 4 5 6
Mean Demand (# of villas) 10 18 23 33 45 56 63
If there are any unsold villas at the end of the project (t = 6), MCS plans to offer them at 30% of the last selling price P6. All unsold inventory can be sold quickly at that heavily discounted price.
MCS is using an annual hurdle rate of 25% and would like to develop a simulation model to estimate the Net Present Value (NPV) of the project, as well as the lowest cash position during the life of the project.
Random Variables
Pt = Price of a villa in period t where t = 1, …, 6 and P0 = Rs 9mm.
Dt = Demand for villas in period t where t = 0, …, 6.
Denote by It = Inventory of unsold villas at the beginning of period t (t = 1, …, 6) and I0 = 250. Ct = Development cost (in Rs mm) in period t where t = 0, …, 6 (e.g., C4 = 300). Bt = Amount borrowed (in Rs mm) at the end of period t where t = 0, …, 6. St = Amount saved (in Rs mm) at the end of period t where t = 0, …, 6.
1 Monthly demand is an integer number generated by a Triangular distribution with time-dependent parameters. Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 9 of 12
a) (4 points) Using the above notation, write general expressions/formulae for the calculation of the semi-annual revenue in period t = 5, R5, the inventory of unsold units at the start of period t = 6, I6, and the semi-annual revenue in period t = 6, R6. You may use any mathematical or spreadsheet functions in the formulae.
R5 =
I6 =
R6 =
b) (3 points) Given the above notation, use the balances at the end of period t = 2 and the cash inflows and outflows during period t = 3 to write general expressions/formulae for the calculations of the cash balance, the amount borrowed, and the savings amount at the end of period t = 3: CB3, B3, and S3. You may use any mathematical or spreadsheet functions in the formulae.
CB3 =
B3 =
S3 =
MCS has run the simulation model to evaluate the project NPV and minimum cash balance position during the project duration.
NPV = Present Value of CB6 – Initial Investment = e-(0.25x3)CB6 – 400
min CB = min{CB0, CB1, …, CB6}
Below are the frequency and cumulative distributions and summary statistics of the simulation results for the NPV and min CB. Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 10 of 12
e.g., on the horizontal axis of the min CB Distribution, (-600,-550] signifies -600 < min CB ≤ -550 Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 11 of 12
c) (2 points) Based on the above simulation results, what is the approximate 95% confidence interval for the true expected NPV.
( ) [26.9, 55.7]
( ) [34.1, 48.5]
( ) [-272.5, 355.1]
( ) [-586.3, 668.9]
d) (2 points) Based on the above simulation results, what is the approximate number of trials used in the simulation run?
( ) 50
( ) 1,000
( ) 1,900
( ) 2,400
( ) 10,000
e) (3 points) Based on the simulation results, within what range lies the estimated probability that the true expected NPV is positive?
( ) between 0% and 5%
( ) between 5% and 25%
( ) between 25% and 50%
( ) between 50% and 75%
( ) between 75% and 95%
( ) between 95% and 100%
f) (3 points) Based on the above simulation results, within what range lies the estimated probability that the actual min CB will be less than - 300mm (negative 300 million) Rs?
( ) between 0% and 10%
( ) between 10% and 30%
( ) between 30% and 50%
( ) between 50% and 70%
( ) between 70% and 90%
( ) between 90% and 100%
Decision Models & Optimization Make-Up Final Examination Term II, 2016 Page 12 of 12
g) (4 points) Suppose the original simulation were re-run using 4 times as many trials.
(i) The sample median of the NPV
( ) is likely to increase ( ) is likely to stay the same ( ) is likely to decrease
(ii) A 99% confidence interval for the true expected NPV
( ) will be roughly ¼ of the original ( ) will be roughly ½ of the original ( ) will be roughly the same as the original ( ) will be roughly twice that of the original ( ) will be roughly four times that of the original
h) (4 points) Suppose the original simulation were re-run using the same number of trials, but with volatility of = 40% rather than the original 20%.
(i) The sample range of the min CB Distribution (i.e., maximum – minimum)
( ) is likely to grow ( ) is likely to stay the same ( ) is likely to shrink
(ii) The mean standard error of the min CB
( ) is likely to increase ( ) is likely to stay the same ( ) is likely to decrease
