Solved Problems
Solved Problem M8-1
Don Yale, president of Hardrock Concrete Company, has plants in three locations and is currently working on three major construction projects, located at different sites. The shipping costs per truckload of concrete, plant capacities, and project requirements are provided in the accompanying table.
Formulate an initial feasible solution to Hardrock’s transportation problem using the northwest corner rule.
Then evaluate each unused shipping route (each empty cell) by applying the stepping-stone method and computing all improvement indices. Remember to do the following:
Check that supply and demand are equal.
Load the table via the northwest corner method.
Check that there are the proper number of occupied cells for a “normal” solution—namely,
Find a closed path to each empty cell.
Determine the improvement index for each unused cell.
Move as many units as possible to the cell that provides the most improvement (if there is one).
Repeat steps 3 through 6 until no further improvement can be found.
Solution
Northwest corner solution:
Using the stepping-stone method, the following improvement indices are computed:
Since all indices are greater than or equal to zero (all are positive or zero), this initial solution provides the optimal transportation schedule—namely, 40 units from 1 to A, 30 units from 1 to B, 20 units from 2 to B, 30 units from 2 to C, and 30 units from 3 to C.
Had we found a path that allowed improvement, we would move all units possible to that cell and then check every empty cell again. Because the plant 3 to project A improvement index was equal to zero, we note that multiple optimal solutions exist.
Solved Problem M8-2
The initial solution found in Solved Problem M8-1 was optimal, but the improvement index for one of the empty cells was zero, indicating another optimal solution. Use a stepping-stone path to develop this other optimal solution.
Solution
Using the plant 3 to project A stepping-stone path, we see that the lowest number of units in a cell where a subtraction is to be made is 20 units from plant 2 to project B. Therefore, 20 units will be subtracted from each cell with a minus sign and added to each cell with a plus sign. The result is shown here:
Solved Problem M8-3
Prentice Hall, Inc., a publisher headquartered in New Jersey, wants to assign three recently hired college graduates—Jones, Smith, and Wilson—to regional sales districts in Omaha, Dallas, and Miami. But the firm also has an opening in New York and would send one of the three there if it were more economical than a move to Omaha, Dallas, or Miami. It will cost $1,000 to relocate Jones to New York, $800 to relocate Smith there, and $1,500 to move Wilson. What is the optimal assignment of personnel to offices?
Solution
The cost table has a fourth column to represent New York. To balance the problem, we add a dummy row (person) with a zero relocation cost to each city.
Subtract the smallest number in each row and cover zeros (column subtraction will give the same numbers and therefore is not necessary).
Subtract the smallest uncovered number (200) from each uncovered number, add it to each square where two lines intersect, and cover all zeros.
Subtract the smallest uncovered number (100) from each uncovered number, add it to each square where two lines intersect, and cover all zeros.
Subtract the smallest uncovered number (100) from each uncovered number, add it to squares where two lines intersect, and cover all zeros.
Since it takes four lines to cover all zeros, an optimal assignment can be made at zero squares. We assign
Dummy (no one) to Dallas
Wilson to Omaha
Smith to New York
Jones to Miami
Solved Problem M8-4
PetroChem, an oil refinery located on the Mississippi River south of Baton Rouge, Louisiana, is designing a new plant to produce diesel fuel. Figure M8.11 shows the network of the main processing centers along with the existing rate of flow (in thousands of gallons of fuel). The management at PetroChem would like to determine the maximum amount of fuel that can flow through the plant, from node 1 to node 7.
Figure M8.11
Solution
Using the maximal-flow technique, we arbitrarily choose path 1–5–7, which has a maximum flow of 5. The capacity are then adjusted, leaving the capacity from 1 to 5 at 0 and the capacity from 5 to 7 also at 0. The next path arbitrarily selected is 1–2–4–7, and the maximum flow is 3. When capacities are adjusted, the capacity from 1 to 2 and the capacity from 4 to 7 are 1, and the capacity from 2 to 4 is 0. The next path selected is 1–3–6–7, which has a maximum flow of 1, and the capacity from 3 to 6 is adjusted to 0. The next path selected is 1–2–5–6–7, which has a maximum flow of 1. After this, there are no more paths with any capacity. Arc 5–7 has capacity of 0. While arc 4–7 has a capacity of 1, both arc 2–4 and arc 5–4 have a capacity of 0, so no more flow is available through node 4. Similarly, while arc 6–7 has a capacity of 4 remaining, the capacity for arc 3–6 and the capacity for arc 5–6 are 0. Thus, the maximum flow is The flows are shown in Figure M8.12.
Figure M8.12
Solved Problem M8-5
The network of Figure M8.13 shows the highways and cities surrounding Leadville, Colorado. Leadville Tom, a bicycle helmet manufacturer, must transport his helmets to a distributor based in Dillon, Colorado. To do this, he must go through several cities. Tom would like to find the shortest way to get from Leadville to Dillon. What do you recommend?
Figure M8.13
Solution
The problem can be solved using the shortest-route technique. The nearest node to the origin (node 1) is node 2. Give this a distance of 8 and put this in a box next to node 2. Next, consider nodes 3, 4, and 5, since there is an arc to each of these from either node 1 or node 2, and both of these have their distances established. The nearest node to the origin is 3 (coming through node 2), so the distance to put in the box next to node 3 is Then consider nodes 4, 5, and 6. The node nearest the origin is node 4, which has a distance of 18 (directly from node 1). Then consider nodes 5 and 6. The node with the least distance from the origin is node 5 (coming through node 2), and this distance is 22. Next, consider nodes 6 and 7, and node 6 is selected, since the distance is 26 (coming through node 3). Finally, node 7 is considered, and the shortest distance from the origin is 32 (coming through node 6). The route that gives the shortest distance is 1–2–3–6–7, and the distance is 32. See Figure M8.14 for the solution.
