3. (LP-based Allocations and Bid-prices for Network RM; 16 points) In this problem, we will implement the LP-based approximation methods we studied in class to derive allocation decisions for a simple network. We want to sell tickets on two flights, Flight 1 from San Francisco (SFO) to Detroit (DIA), and Flight 2 from DIA to St. Louis (STL); a person flying from SFO to STL needs a seat on both flights. Consider selling tickets over 300 time periods, with initial capacity of 100 on Flight 1 (SFO- DIA), and 120 on Flight 2 (DIA-STL). The airlines offers a total of 6 products. In particular, for each origin-destination (OD) pair, there are two fare classes: class Y corresponding to the full-fare 0-1 economy class ticket, and class M corresponding to the discount-fare economy class ticket. In each period, the airlines gets at most one request for a particular product, where product j is requested with probability \; . The fares and per-period request probabilities for the products are given in the following table. Product Class Total Fare Per-period arrival probability SFO-DIA Y 175 0.2 SFO-DIA M 100 0.075 DIA-STL Y 125 0.25 DIA-STL M 75 0.15 SFO-DIA-STL Y 260 0.25 SFO-DIA-STL M 175 0.025 (a) (1 point) Let D, be the number of time-periods from t to 300 in which no request arrived, and Dy be the (random) demand for product j from t to 300. What is the average value of D!? What about for D? (b) (5 points) Let V.(x) be the value function at beginning of period t with state x. Write down a linear program that computes the fluid approximation Fluid ([100, 120]) and compute its value using iPython/Excel. (c) (5 points) Compute the randomized-LP approximation VR ([100, 120]) using k = 1000 samples using a Jupyter ipython notebook. Download your code as pdf via latex (see Download as in the dropdown menu) and attach it to your assignment submission. Compare V Fluid (100, 120]) with VR([100, 120]) (d) (5 points) Write down the dual of the fluid approximation LP for computing VFluid ([100, 120]), and use it to compute shadow prices for each flight-leg (use either Excel or iPython). Based on these, compute the bid prices for each product. 3. (LP-based Allocations and Bid-prices for Network RM; 16 points) In this problem, we will implement the LP-based approximation methods we studied in class to derive allocation decisions for a simple network. We want to sell tickets on two flights, Flight 1 from San Francisco (SFO) to Detroit (DIA), and Flight 2 from DIA to St. Louis (STL); a person flying from SFO to STL needs a seat on both flights. Consider selling tickets over 300 time periods, with initial capacity of 100 on Flight 1 (SFO- DIA), and 120 on Flight 2 (DIA-STL). The airlines offers a total of 6 products. In particular, for each origin-destination (OD) pair, there are two fare classes: class Y corresponding to the full-fare 0-1 economy class ticket, and class M corresponding to the discount-fare economy class ticket. In each period, the airlines gets at most one request for a particular product, where product j is requested with probability \; . The fares and per-period request probabilities for the products are given in the following table. Product Class Total Fare Per-period arrival probability SFO-DIA Y 175 0.2 SFO-DIA M 100 0.075 DIA-STL Y 125 0.25 DIA-STL M 75 0.15 SFO-DIA-STL Y 260 0.25 SFO-DIA-STL M 175 0.025 (a) (1 point) Let D, be the number of time-periods from t to 300 in which no request arrived, and Dy be the (random) demand for product j from t to 300. What is the average value of D!? What about for D? (b) (5 points) Let V.(x) be the value function at beginning of period t with state x. Write down a linear program that computes the fluid approximation Fluid ([100, 120]) and compute its value using iPython/Excel. (c) (5 points) Compute the randomized-LP approximation VR ([100, 120]) using k = 1000 samples using a Jupyter ipython notebook. Download your code as pdf via latex (see Download as in the dropdown menu) and attach it to your assignment submission. Compare V Fluid (100, 120]) with VR([100, 120]) (d) (5 points) Write down the dual of the fluid approximation LP for computing VFluid ([100, 120]), and use it to compute shadow prices for each flight-leg (use either Excel or iPython). Based on these, compute the bid prices for each product