Reconsider Prob. 8.2-23. Now suppose that trucks (and their drivers) need to be hired to do the hauling, where each truck can only be used to haul gravel from a single pit to a single site. Each truck can haul 5 tons, and the cost per truck is five times the hauling cost per ton given earlier. Only full trucks would be used to supply each site.

(a) Formulate this problem as an assignment problem by constructing the appropriate cost table, including identifying the assignees and tasks.

(b) Obtain an optimal solution.

(c) Reformulate this assignment problem as an equivalent transportation problem with two sources and three destinations by constructing the appropriate parameter table.

(d) Obtain an optimal solution for the problem as formulated in part (c).

Prob. 8.2-23

A contractor, Susan Meyer, has to haul gravel to three building sites. She can purchase as much as 18 tons at a gravel pit in the north of the city and 14 tons at one in the south. She needs 10, 5, and 10 tons at sites 1, 2, and 3, respectively. The purchase price per ton at each gravel pit and the hauling cost per ton are given in the table below.

Susan wishes to determine how much to haul from each pit to each site to minimize the total cost for purchasing and hauling gravel.

(a) Formulate a linear programming model for this problem. Using the Big M method, construct the initial simplex tableau ready to apply the simplex method (but do not actually solve).

(b) Now formulate this problem as a transportation problem by constructing the appropriate parameter table. Compare the size of this table (and the corresponding transportation simplex tableau) used by the transportation simplex method with the size of the simplex tableaux from part (a) that would be needed by the simplex method.

(c) Susan Meyer notices that she can supply sites 1 and 2 completely from the north pit and site 3 completely from the south pit. Use the optimality test (but no iterations) of the transportation simplex method to check whether the corresponding BF solution is optimal.

(d) Starting with the northwest corner rule, interactively apply the transportation simplex method to solve the problem as formulated in part (b).

(e) As usual, let c_ij denote the unit cost associated with source i and destination j as given in the parameter table constructed in part (b). For the optimal solution obtained in part (d), suppose that the value of c_ij for each basic variable x_ij is fixed at the value given in the parameter table, but that the value of c_ij for each nonbasic variable x_ij possibly can be altered through bargaining because the site manager wants to pick up the business. Use sensitivity analysis to determine the allowable range to stay optimal for each of the latter c_ij, and explain how this information is useful to the contractor.