Determine which type of network flow can be used to model each of the problem sc

Question

Determine which type of network flow can be used to model each of the problem scenarioslisted below. Give a 1 sentence explanation of your reasoning and define your nodes and arcs.(

a) Georgia State is planning a new building similar to the Mell building. They want tominimize the amount of electric cable that has to be laid in the building to connect allof the computers in the labs.

(b) You want to determine the capacity of a natural gas pipeline network.

(c) The machine shop in your production facility has asked you to help them choose theorder in which they process jobs to minimize the total cost of the changeovers incurredover the course of the work day.

(d) You have accepted an internship for the spring in Portland, Maine. You are planningthe drive up there and have mapped the potential places to stop for food and gas. Youwant to minimize the time that it takes to do the full drive.

(e) Imagine that you are a mountain goat herder. While your goats can run with east atany altitude in your area, you prefer to stay at a lower altitude whenever possible. Howdo you choose a route from the pasture near your home to the river where you take thegoats for water so that your maximum altitude is minimized?

Explanation / Answer

(a)

All buildings are to be connected using a minimum length of wires (arcs). We cannot leave even a single building (node) out of the network. So, the ideal model is a minimum spanning tree.

(b)

Irrespective of the route of the flow, we want to know how much gallons can pass through the network. So, we are interested in the maximum flow possible. So, the appropriate model is a Maxflow.

(c)

The route for the jobs is to be found which incurs the minimum cost. This is the shortest path problem.

(d)

All the stops (nodes) are to be covered and the flow should be unidirectional i.e. only one inlet and one outlet should be there for each stop (node). So, this is a traveling salesman (one directional) problem.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.