CSE524 Homework 3-Minimax and Network Flows Solution

See the course website for instructions and submission details.
10:00 10:20 10:40 11:00 11:20 11:40 Lunch 1:00 1:20 1:40 2:00 2:20 2:40
Manuel 0 0 1 1 0 0 0 1 1 0 0 0 0
Luca 0 1 1 0 0 0 0 0 1 1 0 0 0
Jule 0 0 0 1 1 0 1 1 0 1 1 1 1
Michael 0 0 0 1 1 1 1 1 1 1 1 1 0
Malte 0 0 0 0 0 0 1 1 1 0 0 0 0
Chris 0 1 1 0 0 0 0 0 1 1 0 0 0
Spyros 0 0 0 1 1 1 1 0 0 0 0 0 0
Mirjam 1 1 0 0 0 0 0 0 0 0 1 1 1
Matt 1 1 1 0 0 0 0 0 0 1 1 0 0
Florian 0 0 0 0 0 0 0 1 1 0 0 0 0
Josep 0 0 0 0 0 0 1 1 1 0 0 0 0
Joel 1 1 0 0 0 1 1 1 1 0 0 1 1
Tom 1 1 1 0 1 1 0 0 0 0 0 1 1
Daniel 0 1 1 1 0 0 0 0 0 0 0 0 0
Anne 1 1 0 0 1 1 0 0 0 0 0 0 0
2. Car rental. A small car rental company has a fleet of 94 vehicles distributed among its 10 agencies. The location of every agency is given by its geographical coordinates x and y in a grid based on miles. We assume that the road distance between agencies is approximately 1.3 times the Euclidean distance (as the crow flies). The following table indicates the coordinates of all agencies, the number of cars required the next morning, and the stock of cars in the evening preceding this day.
Agency number 1 2 3 4 5 6 7 8 9 10
x coordinate 0 20 18 30 35 33 5 5 11 2
y coordinate 0 20 10 12 0 25 27 10 0 15
Required cars 10 6 8 11 9 7 15 7 9 12
Cars present 8 13 4 8 12 2 14 11 15 7
Supposing the cost for transporting a car is $0.50 per mile, determine the movements of cars that allow the company to re-establish the required numbers of cars at all agencies, minimizing the total cost incurred for transport.
1 of 2
3. Building a stadium. A town council wishes to construct a small stadium in order to improve the services provided to the people living in the district. After the invitation to tender, a local construction company is awarded the contract and wishes to complete the task within the shortest possible time. All the major tasks are listed in the following table. Some tasks can only start after the completion of certain other tasks, as indicated by the “Predecessors” column. See hw3data.ipynb for the data.
Task Description Duration (in weeks) Predecessors Maximum reduction
(in weeks) Cost of reduction ($1k/wk)
1 Installing the construction site 2 none 0 –
2 Terracing 16 1 3 30
3 Constructing the foundations 9 2 1 26
4 Access roads and other networks 8 2 2 12
5 Erecting the basement 10 3 2 17
6 Main floor 6 4,5 1 15
7 Dividing up the changing rooms 2 4 1 8
8 Electrifying the terraces 2 6 0 –
9 Constructing the roof 9 4,6 2 42
10 Lighting of the stadium 5 4 1 21
11 Installing the terraces 3 6 1 18
12 Sealing the roof 2 9 0 –
13 Finishing the changing rooms 1 7 0 –
14 Constructing the ticket office 7 2 2 22
15 Secondary access roads 4 4,14 2 12
16 Means of signalling 3 8,11,14 1 6
17 Lawn and sport accessories 9 12 3 16
18 Handing over the building 1 17 0 –
2 of 2