Report

Readings Readings Chapter 5 Advanced Linear Programming Applications BA 452 Lesson A.11 Other Advanced Applications 1 Overview Overview BA 452 Lesson A.11 Other Advanced Applications 2 Overview Data Envelopment Analysis measures the relative efficiency of operating units with the same goals and objectives, and the same types of resources. Applies to hospitals, banks, courts, … Revenue Management Problems are Resource Allocation Problems when inputs are fixed. Revenue Management Problems thus help airlines determine how many seats to sell at a discount. BA 452 Lesson A.11 Other Advanced Applications 3 Tool Summary Tool Summary Do not make integer restrictions, and maybe the solution are integers. • Second Example: IMD = number of Indianapolis-Memphis-Discount seats Use compound variables: • Second Example: IMD = number of Indianapolis-Memphis-Discount seats Constrain a weighted average with a linear constraint: • Third Example: Constrain the weighted average risk factor to be no greater than 55: 60X1 + 70X2 + 75X3 + 20X4 + 30X5 + 22X6 + 50X7 + 10X9 < 55(X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 + X10) Interpret the unrealistic assumptions needed for a linear formulation: • First Example: Assume the set of alternative inputs and outputs for a high school is convex. Thus if 100 teaching hours gets 20 more students admitted to college, then 10 teaching hours gets at least 2 admitted. • Second Example: Assume demand has only two values. • Third Example: Assume risk is a linear function of investment shares. BA 452 Lesson A.11 Other Advanced Applications 4 Tool Summary Tool Summary Critique the unrealistic or approximate variables used because data on better variables may not be available: • First Example: High school output is measured by only three variables. • Average SAT Scores, even though maximizing those scores is not the same as maximizing learning. • The number of High School Graduates, even though there is no accounting for learning beyond a minimal level. • The number of College Admissions, even though there is no accounting for the quality or selectivity of the colleges. • First Example: High school input is measured by only three variables. • Senior Faculty • Budget ($100,000's) • Senior Enrollments, even though there is no measure for the quality of those students before their senior year. BA 452 Lesson A.11 Other Advanced Applications 5 Data Envelopment Analysis Data Envelopment Analysis BA 452 Lesson A.11 Other Advanced Applications 6 Data Envelopment Analysis Overview Data Envelopment Analysis measures the relative efficiency of operating units with the same goals and objectives, and the same types of resources. Data Envelopment Analysis applies to fast-food outlets within the same chain, to hospitals, banks, courts, schools, and so on. BA 452 Lesson A.11 Other Advanced Applications 7 Data Envelopment Analysis Overview Data Envelopment Analysis creates a fictitious composite unit made up of an optimal weighted average (w1, w2,…) of existing units. An individual unit, k, can be compared by determining E, the fraction of unit k’s input resources required by the optimal composite unit to achieve k’s goals and objectives. If E < 1, unit k is less efficient than the composite unit, and is deemed relatively inefficient. If E = 1, there is no evidence that unit k is inefficient, but one cannot conclude that k is best without further information (such as the value of 1 point higher Average SAT Score compared with 1 more College Admission in the following example). BA 452 Lesson A.11 Other Advanced Applications 8 Data Envelopment Analysis Overview Min E s.t. Weighted outputs > Unit k’s output (for each measured output) Weighted inputs < E [Unit k’s input] (for each measured input) Sum of weights = 1 E, weights > 0 BA 452 Lesson A.11 Other Advanced Applications 9 Data Envelopment Analysis Question: The Langley County School District is trying to determine the relative efficiency of its three high schools. In particular, it wants to evaluate Roosevelt High. The district is evaluating performances on SAT scores, the number of seniors finishing high school, and the number of students admitted to college [outputs] as a function of the number of teachers teaching senior classes, the prorated budget for senior instruction, and the number of seniors enrolled [inputs]. Input Senior Faculty Budget ($100,000's) Senior Enrollments Roosevelt Lincoln Washington 37 25 23 6.4 5.0 4.7 850 700 600 Output Average SAT Score High School Graduates College Admissions Roosevelt Lincoln Washington 800 830 900 450 500 400 140 250 370 BA 452 Lesson A.11 Other Advanced Applications 10 Data Envelopment Analysis Answer: Define the decision variables E = Fraction of Roosevelt's input resources required by the composite high school w1 = Weight applied to Roosevelt's input/output resources by the composite high school w2 = Weight applied to Lincoln’s input/output resources by the composite high school w3 = Weight applied to Washington's input/output resources by the composite high school Define the objective function. Minimize the fraction of Roosevelt High School's input resources required by the composite high school: Min E BA 452 Lesson A.11 Other Advanced Applications 11 Data Envelopment Analysis Constrain the sum of the weights to one: (1) w1 + w2 + w3 = 1 Constrain each output of the composite school to be at least Roosevelt’s: (2) 800w1 + 830w2 + 900w3 > 800 (SAT Scores) (3) 450w1 + 500w2 + 400w3 > 450 (Graduates) (4) 140w1 + 250w2 + 370w3 > 140 (College Admissions) Constrain the inputs used by the composite high school to be no more than the multiple, E, of the inputs available to Roosevelt: (5) 37w1 + 25w2 + 23w3 < 37E (Faculty) (6) 6.4w1 + 5.0w2 + 4.7w3 < 6.4E (Budget) (7) 850w1 + 700w2 + 600w3 < 850E (Seniors) BA 452 Lesson A.11 Other Advanced Applications 12 Data Envelopment Analysis Interpretation: The output shows that the composite school is made up of equal weights of Lincoln and Washington. Roosevelt is 76.5% efficient compared to this composite school when measured by High School Graduates (because of the 0 slack on this constraint (#3)). It is less than 76.5% efficient if output were only measured by SAT Scores and College Admissions (there is positive slack in constraints 2 and 4.) BA 452 Lesson A.11 Other Advanced Applications 13 Revenue Management Revenue Management BA 452 Lesson A.11 Other Advanced Applications 14 Revenue Management Overview Revenue Management Problems are Resource Allocation Problems when inputs are fixed. Revenue Management Problems thus help airlines determine how many seats to sell at an early-reservation discount fare and many to sell at a full fare. Other applications include hotels, apartment rentals, car rentals, cruise lines, and golf courses. BA 452 Lesson A.11 Other Advanced Applications 15 Revenue Management Answer: 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. The Baltimore based plane flies to Tampa with a stopover in Memphis. Both planes have a coach section with a 120-seat capacity, and they arrive in Memphis at the same time. 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 on the next slide with their fares and forecasted demand. LeapFrog wants to determine how many seats it should allocate to each ODIF. BA 452 Lesson A.11 Other Advanced Applications 16 Revenue Management ODIF 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Origin Indianapolis Indianapolis Indianapolis Indianapolis Indianapolis Indianapolis Baltimore Baltimore Baltimore Baltimore Baltimore Baltimore Memphis Memphis Memphis Memphis Destination Memphis Austin Tampa Memphis Austin Tampa Memphis Austin Tampa Memphis Austin Tampa Austin Tampa Austin Tampa Fare Class D D D F F F D D D F F F D D F F ODIF Code IMD IAD ITD IMF IAF ITF BMD BAD BTD BMF BAF BTF MAD MTD MAF MTF Fare 175 275 285 395 425 475 185 315 290 385 525 490 190 180 310 295 Demand 44 25 40 15 10 8 26 50 42 12 16 9 58 48 14 11 BA 452 Lesson A.11 Other Advanced Applications 17 Revenue Management Answer: Define 16 decision variables, one for each ODIF. For example, IMD = number of seats allocated to Indianapolis-MemphisDiscount class. Fare ODIF ODIF Origin Destination Class 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 BA 452 Lesson A.11 Other Advanced Applications 18 Revenue Management Simplification: Although the Revenue Management problem is an Integer Linear Programming problem, it has a special form that allows it to be formulated without integer constraints, and the solutions turn out to be integers. BA 452 Lesson A.11 Other Advanced Applications 19 Revenue Management Define the objective function. Maximize total revenue: Max (fare per seat for each ODIF) x (number of seats allocated to the ODIF) Max 175IMD + 275IAD + 285ITD + 395IMF + 425IAF + 475ITF + 185BMD + 315BAD + 290BTD + 385BMF + 525BAF + 490BTF + 190MAD + 180MTD + 310MAF + 295MTF BA 452 Lesson A.11 Other Advanced Applications 20 Revenue Management Define the 4 capacity constraints, one for each flight leg: Indianapolis-Memphis leg (1) IMD + IAD + ITD + IMF + IAF + ITF < 120 Baltimore-Memphis leg (2) BMD + BAD + BTD + BMF + BAF + BTF < 120 Memphis-Austin leg (3) IAD + IAF + BAD + BAF + MAD + MAF < 120 Memphis-Tampa leg (4) ITD + ITF + BTD + BTF + MTD + MTF < 120 BA 452 Lesson A.11 Other Advanced Applications 21 Revenue Management Define the first 8 demand constraints, one for each ODIF: (5) IMD < 44 (6) IAD < 25 (7) ITD < 40 (8) IMF < 15 (9) IAF < 10 (10) ITF < 8 (11) BMD < 26 (12) BAD < 50 BA 452 Lesson A.11 Other Advanced Applications 22 Revenue Management Define the remaining 8 demand constraints, one for each ODIF: (13) BTD < 42 (14) BMF < 12 (15) BAF < 16 (16) BTF < 9 (17) MAD < 58 (18) MTD < 48 (19) MAF < 14 (20) MTF < 11 BA 452 Lesson A.11 Other Advanced Applications 23 Revenue Management Interpretation: Total revenue = $94,735.00, with the specified seat allocation. ODIF 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Origin Indianapolis Indianapolis Indianapolis Indianapolis Indianapolis Indianapolis Baltimore Baltimore Baltimore Baltimore Baltimore Baltimore Memphis Memphis Memphis Memphis Destination Memphis Austin Tampa Memphis Austin Tampa Memphis Austin Tampa Memphis Austin Tampa Austin Tampa Austin Tampa Fare Class D D D F F F D D D F F F D D F F BA 452 Lesson A.11 Other Advanced Applications ODIF Code IMD IAD ITD IMF IAF ITF BMD BAD BTD BMF BAF BTF MAD MTD MAF MTF Fare 175 275 285 395 425 475 185 315 290 385 525 490 190 180 310 295 24 BA 452 Quantitative Analysis End of Lesson A.11 BA 452 Lesson A.11 Other Advanced Applications 25