Description

Homework 6
(12:00 p.m.)

******************************************************************************************** Note: 1. Your homework submission must be typewritten.

2. Show only the solutions and do not copy the problems in the submission.
********************************************************************************************

1. Read Readings 7 and 8.

2. (1) Lone Star Club is a water-front resort in the suburb of Miami, FL. Club management is in the process of installing a new security system, which will be connected to all residential, commercial, and recreational areas of the resort as shown in the network below. The objective is to link these sites using the least amount of cable (in miles). Use the greedy algorithm to help the club solve the problem.

(2) Treat the above problem as the shortest path problem and apply the Dijkstra’s algorithm to find (a) the shortest route from Area 1 to each of the other nine areas and (2) the associated shortest distance.

3. Desert Energy Corporation discovered a large natural gas field in the northwestern part of the State of Texas several months ago. It just built a pipeline system to transport the natural gas from Dumas to the firm’s headquarters in Amarillo. In the network shown below, the gas flow capacities are in thousands of cubic feet per minute. Use the Ford-Fulkerson algorithm to determine the maximal flow from the entry at Dumas to the exit at Amarillo per minute.

2

4. A large logistics company in Little Rock, AR, has to ship a new product from three manufacturing plants (A, B, and C) to three warehouses (X, Y, and Z). The transportation cost (in dollars/unit) from each plant to each warehouse, the supply (in units) at each plant, and the demand (in units) at each warehouse are shown below:

Warehouse
Plant X Y Z Supply
—————————————————————————————–
A 11 5 8 40,000
B 8 9 12 100,000
C 13 10 7 80,000
—————————————————————————————–
Demand 90,000 60,000 70,000

The transportation matrix for the transportation problem is shown below:

(1) Use the northwest-corner method to obtain an initial feasible solution.

(2) Use the modified distribution (MODI) method for cell evaluation to find the optimal solution to the problem.

(3) What is the optimal shipping schedule and what is the minimum total shipping cost?