The U.S. Department of Transportation (DOT) is planning to build a new interstat

Question

The U.S. Department of Transportation (DOT) is planning to build a new interstate to run from Detroit, Michigan, to Charleston, South Carolina. A number of different routes have been proposed and are summarized in Figure 5.44, where node 1 represents Detroit and node 12 represents Charleston. The numbers on the arcs indicate the estimated construction costs of the various links (in millions of dollars). It is estimated that all of the routes will require approximately the same total driving time to make the trip from Detroit to Charleston. Thus, the DOT is interested in identiying the least costly atermative a. Formulate an LP model to determine the least costly construction plarn

Explanation / Answer

Let Xij be the set of binary integers such that Xij=1 when the route from node-i to node-j is on the shortest route and Xij=0 otherwise.

(i,j) = {(1,2), (1,3), (1,4), (2,5), (2,6), (3,6), (4,6), (4,7), (4,9), (5,6), (5,8), (5,9), (6,9), (7,9), (7,10), (8,11), (9,11), (9,12), (10,11), (10,12), (11,12)}

Objective function:
Minimize Z = Total cost = 1X12 + 3X13 + 2X14 + 4X25 + 3X26 + 2X36 + 2X46 + 3X47 + 4X49 + 1X56 + 3X58 + 3X59 + 2X69 + X79 + 2X7,10 + 3X8,11 + 1X9,11 + 2X9,12 + 3X10,11 + 5X10,12 + 3X11,12

Subject to,

X12 + X13 + X14 = 1
X12 - X25 - X26 = 0
X13 - X36 = 0
X14 - X46 - X47 - X49 = 0
X25 - X56 - X58 - X59 = 0
X26 + X36 + X46 + X56 - X69 = 0
X47 - X79 - X7,10 = 0
X58 - X8,11 = 0
X49 + X59 + X69 + X79 - X9,11 - X9,12 = 0
X7,10 - X10,11 - X10,12 = 0
X8,11 + X9,11 + X10,11 - X11,12 = 0
X9,12 + X10,12 + X11,12 = -1

Xij = {0,1}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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