1. (Airline Network Revenue Management) Consider an airline network with four flight legs: LGA-ORD, ORD->LAX, LAX-SFO, ORD->SFO. The capacity for each flight leg is 360. We have 6 different flight routes, whose departure airport and arrival airport are, Departure LGA LGA LGA ORD ORD LAX Arrival ORD LAX SFO LAX SFO SFO In order to fulfill these 6 flight routes using no more than 2 flight legs, the resource require- ment matrix is, LGA-ORD LGA-LAX LGA SFO ORD LAX ORD SFO, ORD-SFO, LAX-SFO LGA-ORD 1 1 0 0 0 0 ORD->LAX 0 0 1 0 0 ORD-SFO 0 0 0 LAX-SFO 0 0 0 0 0 Thus, we have 7 types of customers to fulfill. There are T = 2000 periods to sell tickets to these 7 types of passengers. In each period, there will be one customer arriving, with probability 01 = 0.1, 02 = 0.1, 03 = 0.1, 04 = 0.2, 05 = 0.15, 06 = 0.05, 07 = 0.3. The prices of these flights are P1 = 12, P2 = 15, P3 = 30, PA = 5, Ps = 25, P6 = 20, P7 = 17. Put them with the resource requirement table, we have LGA-ORD LGA-LAX LGA-SFO ORD LAX ORD SFO, ORD SFO, LAX-SFO LGA-ORD 1 1 1 0 0 0 0 ORD->LAX 0 1 0 0 0 ORD-SFO 0 0 1 0 1 0 0 LAX-SFO 0 0 0 0 0 1 1 0.1 0.1 0.1 0.2 0.15 0.05 0.3 P 12 15 30 5 25 20 17 Now, we are ready to decide our policy of accepting customers. Let x,, j = 1, ...,7 be our decision variables of whether we should accept jth-type customer when he arrives. x;s aredetermined by solving, where (-3" is the capacity vector, 3; is the vector of resource requirement for with-type customer. 11' is the dual vector. Here, we assume the type-distribution {0,317 = 1, ..., 7} of arrival customer and the prices charged to them are same in all periods. Therefore, in T periods, we get T91- demands of type i. (a) The dual-based policy is to accept type j EEK-:1 iij S P5, and reject type j otherwise. Find all the types of customers we will accept. (b) Consider a resolving policy to update the dual prices after every A = 2'0 periods. In other words, after every 20 random arrivals, we resolve the resulting linear program to compute new dual prices and use the new dual prices to make the accept / reject decisions for the next 2|] periods. Howr does the expected revenue compare with keeping the dual prices xed? Note that you may have to do several simulation runs to compute the expected revenue. (c) Now consider the version, where we do not recompute the dual prices until the end of the horizon. Instead we recompute the dual prices until T = 15m and then use the last computed dual prices for the rest of the horizon. Compare the expected revenue with parts a) and b)