Scribd
Upload
290 views12 pages

Case 9.2 Aiding Allies PDF

Uploaded by

kodandapanipodisetti6
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
290 views12 pages

Case 9.2 Aiding Allies PDF

Uploaded by

kodandapanipodisetti6
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

CASE 9.

2 AIDING ALLIES

(a)
(b)
The president only cares about the time it takes to get troops and supplies to Russia. So we need to find the
shortest path between US cities and the Russia Cities. We need to only consider the arcs entering and leaving the
airfields because the air travel will be faster than traveling by ships.
By using excel we can find out that the shortest path from US to St. Petersburg is Boston-London-St. Petersburg,
and the total travel time is 12.709. The shortest path from US to Moscow is Boston-London-Moscow with a time
of 13.207. Lastly, the shortest path from US to Rostov is Boston-Berlin-Rostov with a total time of 13.9528.

(C)
The President must satisfy each Russian city's military requirements at minimum cost. Therefore, this
problem can be solved as a minimum-cost network flow problem. The two nodes representing supply
nodes with supply of 500 each (we measure all weights in 1000 tons). The three nodes representing Saint
Petersburg, Moscow, and Rostov are demand nodes with demands of-320, -440, and-240, respectively.
All nodes representing European airfields and ports are transshipment nodes. We measure the flow along
the arcs in 1000 tons. For some arcs, capacity constraints are given. All arcs from the European ports into
Saint Petersburg have zero capacity. All truck routes from the European ports into Rostov have a
transportation limit of 2,500*16=40,000 tons. Since we measure the arc flows in 1000 tons, the
corresponding arc capacities equal 40. An analogous computation yields arc capacities of 30 for both the
arcs connecting the nodes London and Berlin to Rostov. For all other nodes we determine natural arc
capacities based on the supplies and demands at the nodes. We define the unit costs along the arcs in

the network in $1000 per 1000 tons (or, equivalently, $/ton). For example, the cost of transporting 1 ton
of material from Boston to Hamburg equals $30,000 /240 = $125, so the costs of transporting 1000 tons
from Boston to Hamburg equals $125,000.

The objective is to satisfy all demands in the network at minimum cost. The following spreadsheet
shows the entire linear programming model.
The total cost of the operation equals $412.867 million. The entire supply Saint Petersburg is
supplied from Jacksonville via London. The entire supply for Moscow is supplied from Boston via Hamburg.
Of the 240 (=240,000 tons) demanded by Rostov, 60 are shipped from Boston via Istanbul, 150 are
shipped from Jacksonville via Istanbul, and 30 are shipped from Jacksonville via London. The paths to
ship supplies to Saint Petersburg, Moscow, and Rostov are highlighted on the following network diagram.
( d)

Now the President wants to maximize the amount of cargo transported from the US to the Russian cities.
In other words, the President wants to maximize the flow from the two US cities to the three Russian
cities. All the nodes representing the European ports and airfields are once again transshipment nodes.
The flow along an arc is again measured in thousands of tons. The new restrictions can be transformed
into arc capacities using the same approach that was used in part ( c ). the objective is now to maximize
the combined flow the three Russian cities.
The linear programming spreadsheet model describing the maximum flow problem appears as
follows.
The spreadsheet shows all the amounts that are shipped between the various cities. The total supply for
Saint Petersburg, Moscow, and Rostov equals 225,00 tons, 104,800 tons, and 192,400 tons, respectively.
The following network diagram highlights the paths used to ship supplies between the US and the
Russian Federation.
(e)
Cost to Reestablish Communication
Between
Lines ($1,000)
Rostov Orenburg 120
Kazan Samara 95
Perm Yekaterinburg 85
Perm Ulfa
125 (one of two paths)
Yekaterinburg Ulfa
Ulfa Orenburg 75
Ulfa Samara
100 (one of two paths)
Saratov Samara
Saratov Orenburg 95
Total cost 695
Total cost: $ 695,000

There are four possible solutions that meet the conditions of the problem.

Because Saint Petersburg and Moscow Rostov are connected cities, seven Russian cities, with the exception of the
three cities (Saint Petersburg, Moscow, Rostov), need only be connected directly or indirectly to one of these three
cities. Then, on the existing Netflow, the three nodes, St. Petersburg, Moscow and Rostov, are combined into one
node

(St. Petersburg + Moscow + Rostov = Union)

The newly combined node shares the arcs of the existing nodes.

The arcs that overlap with other nodes are replaced by the arcs with the lowest cost. Such arcs should be taken
into account when converting to the original node from which of 3 cities.
Apply the algorithm of Minimum Spanning Tree problem on new Netflow.

Start the algorithm on random node (Yekaterinburg)

Since the distance between Yekaterinburg and Ufa and the distance between Perm and Ufa are the same, two
cases occur, 3-1 and 3-2. Similarly, the distance between Ufa and Saratov and the distance between Samara and
Saratov are the same, resulting in two cases 6-1 and 6-2.

You might also like