CS524 Homework 3- Minimax and Network Flows Solution

See the course website for instructions and submission details.
(Starter code is supplied on Canvas for Questions 2 and 3.)
1. (3 points) 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.
2. (3 points) 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 –
1 of 2
Hour of day 1 2 3 4 5 6 7 8 9 10 11 12
Demand (MWh) 43 40 36 36 35 38 41 46 49 48 47 47

Hour of day
(cont’d)) 13 14 15 16 17 18 19 20 21 22 23 24
Demand (MWh) 48 46 45 47 50 63 75 75 72 66 57 50
The mayor of Hamilton is concerned because the high electricity use during evening hours is costing the city a lot of money. There is also risk of black-outs at around 7pm (1900 hours) because the average demand is dangerously close to Powerco’s 75 MW limit.
To address these issues, the mayor purchased a large battery with a storage capacity of 30 MWh. The idea is that extra electricity could be purchased early in the day (at the lower rate), stored in the battery, and used later in the day when demand (and prices) are high.
a) Write a LP model to answer this question: How much does it cost for a day’s supply of electricity with the battery in operation? Assume that the battery begins the day completely drained. Also, to be safe from possible black-outs, limit the amount of electricity purchased every hour to a maximum of 65 MWh.
b) Make a plot that shows (i) the typical energy demand vs time of day (ii) the electricity purchased using the strategy found in part (a) vs time of day. (Draw both plots on the same graph.) During which hours is it necessary to purchase electricity at the higher rate?
c) Make a plot that shows the battery charge vs. time of day. (Draw this one on a different graph from the previous part.)
d) By modifying your model from part (a), answer this question: How much would a day of supply cost if the battery had an infinite capacity? In this scenario, how much of the battery’s capacity is actually used? (That is, what is the maximum amount of charge stored in the battery at any time?)
e) Repeat parts (b) and (c) to plot the energy demand, electricity purchased, and battery charge vs time of day for the answer from part (d). During which hours is it necessary to purchase electricity at the higher rate?
(Starter code for the first plotting question is supplied.)
2 of 2