Linear programming: the cake shop and the hotel

Linear programming sounds like something from an engineering degree. It's a way to find the best mix when you can't have everything.

Take a small cake shop that bakes two cakes. A chocolate cake makes ₹500 profit and a vanilla cake ₹400. Assume every cake sells.

Three things limit the day. The baker has 16 hours, and a chocolate cake takes 2 while a vanilla takes 1. The oven has 10 hours, and each cake needs 1. There's 3 kg of flour. Chocolate uses 300 g and vanilla 200 g.

Call the chocolate cakes X and the vanilla cakes Y.

Profit = 500X + 400Y
Baker: 2X + Y ≤ 16
Oven: X + Y ≤ 10
Flour: 0.3X + 0.2Y ≤ 3

Draw those limits on a graph and you get a shape. Every point inside it is a day the shop can actually bake. Profit rises in a straight line, so the best day always sits at a corner of that shape. You only have to check the corners.

All vanilla: 10 cakes before the oven runs out. ₹4,000.
All chocolate: 8 cakes before the baker runs out. ₹4,000.
Where the baker and oven lines cross: 6 chocolate and 4 vanilla. ₹4,600.

So the shop bakes 6 and 4. Most owners would bake all chocolate because it earns more per cake. But chocolate eats baker time. Per baker hour, vanilla earns ₹400 and chocolate ₹250. Per oven hour, chocolate wins. Each cake wins on a different bottleneck, so the answer is a mix. Flour doesn't matter at all. There's 400 g left over.

The bit I use most comes next. At 6 and 4, one more oven hour is worth ₹300 and one more baker hour ₹100. More flour is worth nothing. If you're going to spend, buy oven time first. These are called shadow prices.

Hotels run on the same maths, mostly without the name.

Rooms. A hotel has 100 rooms on a Saturday and four segments asking for them. Rank them by what each leaves after channel costs, and fill from the top. In my example the OTA rate is the highest on paper, but direct leaves more once commission is off. The net rate of the last segment you take is the bid price, ₹9,310 here. Anything below it gets turned down.

Groups. A 40-room group at ₹8,500 net looks like good business. It pushes out transient guests worth ₹3.77 lakh. The group pays ₹3.40 lakh, so the hotel loses ₹37,100 by saying yes. It needs ₹9,428 a room to break even.

Rosters. Put in the staff you need each hour and the shifts you're allowed. It finds the cheapest roster that covers every hour.

Kitchens. How much of each dish to prep, given cooks, burners and covers.

Excel has it built in. Data, Solver, Simplex LP. The cake shop and the room night are both in the workbook with this note, with every step written out.