1. [3 points] Car rental. A small car rental company has a fleet of 94 vehicles distributed among its 10 agencies. The location of every agency is given by its geographical coordinates x and y in a grid based on miles. We assume that the road distance between agencies is approximately 1.3 times the Euclidean distance (as the crow flies). The following table indicates the coordinates of all agencies, the number of cars required the next morning, and the stock of cars in the evening preceding this day.
Agency number 1 2 3 4 5 6 7 8 9 10 x coordinate 0 20 18 30 35 33 5 5 11 2 y coordinate 0 20 10 12 0 25 27 10 0 15 Required cars 10 6 8 11 9 7 15 7 9 12 Cars present 8 13 4 8 12 2 14 11 15 7 Supposing the cost for transporting a car is $0.50 per mile, determine the movements of cars that allow the company to re-establish the required numbers of cars at all agencies, minimizing the total cost incurred for transport.
2. [3 points] The chess problem. A small joinery makes two different sizes of boxwood chess sets. The small set requires 3 hours of machining on a lathe, and the large set requires 2 hours. There are four lathes with skilled operators who each work a 40 hour week, so we have 160 lathe-hours per week. The small chess set requires 1kg of boxwood, and the large set requires 4kg. Unfortunately, boxwood is scarce and only 200 kg per week can be obtained. When sold, each of the large chess sets yields a profit of $8, and one of the small chess set has a profit of $5. The problem is to decide how many sets of each kind should be made each week so as to maximize profit.
a) Write out the primal LP. Plot the feasible set and solve the LP graphically. Be sure to label the axes and indicate units. Label the optimal point and find the optimal objective.
b) Repeat all the same steps as in part a) but for the dual LP this time. Verify that the optimal dual objective is the same as the optimal objective of part a).
3. [3 points] Stigler’s supplement. Consider Stigler’s diet problem from Homework 2. To help further lower the cost of your diet, a friend offers to sell you calcium supplements. Each calcium pill contains 500 mg of calcium.
a) What is the most you would be willing to pay per pill? Hint: use duality!
b) Suppose you can buy calcium pills at a cost $0.01 each. What is your new optimal diet? How much money does it save compared to the original optimal diet that didn’t have access to the calcium supplement?
