[go: up one dir, main page]
Scribd
Upload
34 views3 pages

(OR1) Network Optimization Exercises

The document presents a series of exercises focused on deterministic models in operations research, specifically network optimization models. It includes questions on finding the shortest path, formulating problems related to route planning, determining minimum spanning trees, and maximizing flow in networks. Additionally, it discusses cost minimization for a tractor purchase at an airport, requiring the application of specific algorithms from a referenced textbook.

Uploaded by

Trần Thị Ngọc Bích
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
34 views3 pages

(OR1) Network Optimization Exercises

The document presents a series of exercises focused on deterministic models in operations research, specifically network optimization models. It includes questions on finding the shortest path, formulating problems related to route planning, determining minimum spanning trees, and maximizing flow in networks. Additionally, it discusses cost minimization for a tractor purchase at an airport, requiring the application of specific algorithms from a referenced textbook.

Uploaded by

Trần Thị Ngọc Bích
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Student Name: …

Student ID: …

DETERMINISTIC MODELS IN OR
PRACTICE EXERCISES – Network Optimization Models

Question 1
Find the short est path through each of the following networks,where the num bers represent
actual distances between the corresponding nodes.

Question 2
You need to take a trip by car to another town that you have never visited before. Therefore, you
are studying a map to determine the shortest route to your destination. Depending on which route
you choose, there are five other towns (call them A, B, C, D, E) that you might pass through on
the way. The map shows the mileage along each road that directly connects two towns without
Student Name: …
Student ID: …
any intervening towns. These numbers are sum marized in the following table, where a dash
indicates that there is no road directly connecting these two towns without going through any
other towns.

a) Formulate this problem as a shortest-path problem by drawing a network where nodes


represent towns, links represent roads, and numbers indicate the length of each link in
miles.
b) Use the Algorithm to the Seervada Park Shortest-Path Problem (Introduction to
Operations Research by Hillier and Lieberman, 9 th ed., p.364) to solve this shortest path
problem.

Question 3
Reconsider the networks shown in Question 1. Use the algorithm described in Sec. 9.4
(Introduction to Operations Research by Hillier and Lieberman, 9 th ed.) to find the minimum
spanning tree for each of these networks.

Question 4
For the network shown below, use the augmenting path algorithm described in Sec. 9.5
(Introduction to Operations Research by Hillier and Lieberman, 9 th ed.) to find the flow pattern
giving the maximum flow from the source to the sink, given that the arc ca pacity from node i to
node j is the number nearest node i along the arc between these nodes.
Student Name: …
Student ID: …

Question 5
At a small but growing airport, the local airline company is purchasing a new tractor for a
tractor-trailer train to bring luggage to and from the airplanes. A new mechanized luggage
system will be installed in 3 years,so the tractor will not be needed after that. However,because it
will receive heavy use,so that the running and maintenance costs will increase rapidly as the
tractor ages, it may still be more economical to replace the tractor after 1 or 2 years. The
following table gives the total net discounted cost associated with purchasing a tractor (purchase
price minus trade-in allowance, plus running and maintenance costs) at the end of year iand trad
ing it in at the end of year j (where year 0 is now).

The problem is to determine at what times (if any) the tractor should be replaced to minimize the
total cost for the tractors over 3 years.
a) Formulate this problem as a shortest-path problem.
b) Use the algorithm described in Sec. 9.3 (Introduction to Operations Research by Hillier
and Lieberman, 9th ed.) to solve this shortest path problem.

You might also like