Mr. Lovr, a lonely gentleman, does not want to spend Valentine’s day alone in 2011. As one of his New Year’s resolutions, he intends to send roses to nine of his lady friends. Being an avid procrastinator, however, he waits until the last minute and finds out that only eight flower shops in his city still have roses available. For lack of better names, let’s call those flower shops F1, F2, F3, …, F8. The number of bouquets of roses available at each shop are, respectively, 4, 4, 3, 2, 2, 2, 2, and 1. Based on how well he knows each of his potential valentines, whom we’re going to call V1, V2, V3, …, V9, he calculates how many bouquets he needs to send to each of them to increase his chances of going on at least one date. The numbers are, respectively, 3, 2, 2, 2, 2, 2, 2, 2, and 3. At this point, a light bulb goes off in Mr. Lovr’s head, and he remembers from his Operations Research class that this is a transportation problem. But there’s something missing…Ah! The costs! He calls each of the eight flower shops and asks how much it would cost to ship one bouquet of roses to the addresses of each of his nine lady friends. He then compiles the following table of costs (in dollars):
He also remembers that because the total supply is equal to the total demand, he can write all of the constraints in this problem as equalities. Essentially, he has to say that, for each flower shop, the number of bouquets that it ships has to be equal to the number of bouquets that it has. Similarly, he needs one constraint for each valentine saying that the number of bouquets that they receive has to be equal to the number that they want (according to his estimates above). To avoid suspicion, he also decides that it’s better for each flower shop to send no more than one bouquet to the same person. So far, so good, but he needs a specific shipment plan because he’s running out of time.
He opens up an Excel spreadsheet and creates the following layout of cells (he chose pink to make it more romantic):
Somewhere else in his spreadsheet he also typed the table of costs shown above. To his surprise, he even remembered to use the SUMPRODUCT function to calculate the total cost expression. He clicks “Solve” and finds out that the cheapest way to send all 20 bouquets will cost him $38. Not bad…but wait a second…something amazing happened! He cannot believe his eyes! The optimal solution exhibits a very curious pattern! Could it be a Valentine’s Day miracle? Could it be the power of love? If you want to see for yourself, download Mr. Lovr’s spreadsheet, open Excel Solver, and solve the model (no setup necessary, just click the “Solve” button). (NOTE: this spreadsheet has been tested with Excel 2007 under Windows XP, and with Excel 2008 under Mac OS X Snow Leopard. I’m not sure the “trick” will work in earlier Excel versions. For a free download of Excel Solver for Mac OS X, go here.)
Thanks to my love for giving me the idea for this blog post.