Part 1: single-stage allocation problem
Suppose there are three oil refineries--Amoco, BP and Chevron-- supplying gasoline to seven cities--Tic, Urp, Vat, Wag, Xyz, Yeti and Zed. This table includes the cities' and refineries' X-Y locations, the cities' monthly gasoline demands, and the refineries' monthly capacities. Copy and paste these data into a blank worksheet.
You can create a bubble-plot "map" of the cities sized by demand, another bubble-plot of the refineries sized by capacity, and then copy and paste the refineries plot into the cities plot. (I used a third-party Excel add-in to label the bubbles.)
Your objective is to determine the set of gasoline allocations from refineries to cities that minimizes aggregate straight-line delivery costs (assuming constant cost per mile per barrel). The figure below shows how to set up the worksheet to accomplish this.
First, you need to calculate the straight-line distances between the cities and refineries. (Use the Pythagorean theorem: square the difference in the X's and the difference in the Y's, add them, and take the square root; the illustration doesn't show the entire formula, but you get the idea!)
Then, initialize the allocation table (which I highlighted in yellow) with zeroes, and enter the row and column sum formulas in the adjacent column and row. Next, use the SUMPRODUCT function to sum the products of barrels allocated from each refinery i to city j multiplied by the distance between refinery i and city j. This calculates the aggregate transportation cost of the allocation pattern.
Now use Solver to find the least-cost set of allocations from refineries to cities that satisfies two constraint sets:
Specify the SUMPRODUCT cell (green) as the value to be minimized by adjusting the allocation cells (yellow), and specify the constraints: cities' deliveries = demands, and refineries' deliveries ≤ refinery capacities.
Check the "Make Unconstrained Variables Non-Negative" box. Choose the "Simplex LP" solving method. Solve.
When you get the Solver solution, select the Sensitivity Report so it's saved along with the solution. Examine the shadow prices in the Sensitivity Report, and summarize the solution:
Part 2: two-stage allocation problem
Now let's include the oil fields that supply these refineries. Now your objective is to determine the allocations of crude from oil fields to refineries, and the allocations of refined petroleum to cities, that minimize the total cost of satisfying all the cities' demands.
This table includes the X-Y locations and monthly pumping capacities of ten fields. Copy and paste these data into a new worksheet, and create the combined matrix of straight-line distances of both oil fields and cities from the three refineries:
Set up an expanded allocation table to solve the combined problem:
find the least-cost set of allocations from oilfields to refineries
and from refineries to cities that satisfies four constraint sets:
Your setup should look something like this:
Analyze the allocations and the Sensitivity Report shadow prices: