ORIE 5132 : Service Systems and Online Markets Sample Final 1 (Spring 2021) Problems 1. Suppose we have a total of C seats and a single fare class. The price per seat is fixed at p. As we discussed in class, since there is possibility of no-shows, we would like to sell more tickets than the capacity to maximize the expected revenue. Let q be the number of overbooked seats, i.e., we sell a total of (C+q) seats. Assume that the demand is such that we can sell all (C + q) seats for any q. Now suppose that the number of no-shows is uniformly distributed between 0 and · (C + q) for some 0 < < 1 (this approximately models a scenario with probability of no-show for every customer). Moreover, assume q < (C+ q). Note that unlike the model discussed in class, the distribution of number of no-shows depends on the total number of tickets sold, and in particular, depends on q. If the number of no-shows is smaller than q, then we pay a penalty of = 2p (i.e. twice the price of the ticket) per customer who can not be served. We would like to find q that maximizes the expected profit. Consider that a fractional number of customers can be no-shows and we can sell a fractional number of tickets to simplify computations. (a) What is the pdf for the number of no-shows? (b) Write the expression for expected profit, ⇧(q). (c) Compute optimal overbooking limit q⇤ that maximizes expected profit. (d) Can we formulate the problem as a newsvendor problem with underage and overage costs? Why or why not? 2. Consider a mixture of MNL model with n products andK segments with segment probabilities ✓1, . . . , ✓K and parameters vjk > 0 for all products j 2 {1, . . . , n}, and v0k = 1 for all segment k = 1, . . . ,K. The prices of the products are p1 . . . pn. Prove or disprove by a counterexample. To give a counter-example, you can choose any values for n, K, parameters vjk for product j, segment k and any prices p1, . . . , pn satisfying p1 . . . pn. (a) Let S⇤ be the optimal unconstrained assortment. Then 1 2 S⇤, i.e., highest price product is contained in S⇤. (b) Consider two assortments S1, S2 with S1 ( S2 (S1 is strictly a subset of S2). Then P (0|S2) < P (0|S1), i.e., the probability of no-purchase decreases if you o↵er a bigger set of products. (c) The optimal unconstrained assortment is nested by price, i.e., S⇤ = {1, . . . , j} for some j 2 [n]. 3. You are selling coats and forecast that the demand function is D(p) = 1000 5p. (a) What is the optimal price and what is your revenue under this price? (b) From past experience you notice that you can actually segment the market perfectly. You notice that customers who are willing to pay at least 50 will always be attracted to buy online and customers who are willing to pay less than 50 will always go to the store. What prices would you choose for the store and for the website (assuming there is no delivery cost)? 1 4. Chi Chi Cafe´ (CCC) serves tea and co↵ee to its customers. A customer first places his or her order at the register. Half of the orders are for tea, and the other half are for co↵ee. Homer prepares the co↵ee orders, and Marge prepares the tea orders. On average, it takes two minutes to take a customer’s order at the register. Marge spends on average three minutes preparing a tea order. When the process operates at capacity Homer’s utilization is 80%. The order is taken by another resource named Chi Chi. Figure 1 (a) What is the bottleneck of the process? What is the process’ capacity (in orders per hour)? (b) What is the theoretical flow time of a Tea order (in minutes)? 5. Consider a network revenue management problem where we have 4 customer types and 2 resources to satisfy the customer demand. In each period, one customer with a random type arrives. The probability that type is j is given by ✓j for j = 1, 2, 3, 4 where ✓1 = 1 4 , ✓2 = 1 4 , ✓3 = 1 4 , ✓4 = 1 4 . The resource requirements for di↵erent customer types is given by the following matrix where each column j represents the requirements for customer type j. 2 4 5 7 3 2 1 0 For instance, each customer of type 1 requires 2 units of resource 1 and 3 units of resource 2. The revenue for each customer type is 1. Suppose there are T = 200 periods, and we have 200 units of resource 1 and 150 units of resource 2. We want to design a policy of accepting customers such that the expected revenue is maximized. (a) Consider an o✏ine problem where we assume that a total of 50 customers of each of the 4 types arrive. Let xj , j = 1, 2, 3, 4 be our decision variables of whether we should accept jth-type customer or not. Formulate the problem of maximizing the profit in the o✏ine (average) problem as an LP. We can assume that 0  xj  1 instead of xj 2 {0, 1}. (b) Let ⇡1 and ⇡2 denote the dual variables corresponding to the resource constraints for resource 1 and resource 2 respectively. Ignore xj  1 constraints for all j = 1, . . . , 4. Formulate the dual LP with variables ⇡1 and ⇡2 ignoring the upper bound constraints xj  1. Note that the dual is a LP in two variables and 4 constraints. (c) Find an optimal solution for the dual LP. Since the dual is an LP in two variable, you can use a graphical method to solve. (d) Design a dual based policy to solve the network revenue management problem. In other words, you need to design a policy or a rule that decides at any point of time, whether we should accept or reject customer type j. 6. You are running a 2nd price auction and there are 5 bidders. Bidders valuations are privately known to bidders and are drawn independently from Uniform[0, 80]. 2 (a) What is the expected revenue for the seller in this auction? (b) Suppose you run, instead of a regular price auction, a 2nd price auction with a reserve price. Recall from HW4, that in a 2nd price auction with a reserve price, the item is allocated to the highest bidder only if his bid is above the reserve price, in which case his payment is max(reserve price, 2nd highest bid). If no one bids above the reserve price, the item is not allocated. Assume that bidding a true value is a dominant strategy for each bidder and the optimal reserve price is the median of the distribution of valuations. What is the probability (with 5 players) that the 2nd price auction with a reserve price will generate a higher revenue than the regular second price auction ? 7. SuperCall caters to a heterogeneous customer population. Not surprisingly, customers’ annual spending on the company’s product decreases the more they wait each time they need to call SuperCall’s call center. Series A in the graph below shows that the greater the service time of a customer (actual handling time, not including waiting) the bigger the e↵ect of each minute of waiting time on the customer’s annual spending. Bigger spenders, it turns out, have more questions/inquiries but are also more impatient: For a customer with a 14 minute service time the company loses roughly $4 per minute that this customer has to wait for service. The service time of a customer can be estimated with relative precision by the automatic system (“tell me in a few words what you are calling about ...”) and this information can be used to prioritize customers. (a) How would you recommend that customers be prioritized? Shorter processing time first? Longer processing time first? (b) How would you recommend prioritizing customers if the relationship between handling time and delay sensitivity follows, instead, the linear series B ? Figure 2 3
















































































































学霸联盟