$($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($SFODIA$),$ 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 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 j $.$ 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 $1750\mathrm{.}2$ SFO$-$DIA M $1000\mathrm{.}075$ DIA$-$STL Y $1250\mathrm{.}25$ DIA$-$STL M $750\mathrm{.}15$ SFO$-$DIA$-$STL Y $2600\mathrm{.}25$ SFO$-$DIA$-$STL M $1750\mathrm{.}025($a$)(1$ point$)$ Let Dt $0$ be the number of time$-$periods from t to $300$ in which no request arrived, and Dt j be the $($random$)$ demand for product j from t to $300.$ What is the average value of D$10?$ What about for D$51?($b$)(5$ points$)$ Let Vt$($x$)$ be the value function at beginning of period t with state x$.$ Write down a linear program that computes the fluid approximation V F luid $1([100,120])$ and compute its value using iPython$/$Excel$.($c$)(5$ points$)$ Compute the randomized$-$LP approximation V R $1([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 F luid $1([100,120])$ with V R $1([100,120])($d$)(5$ points$)$ Write down the dual of the fluid approximation LP for computing V F luid $1([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.