CS/ECE/ISyE 524 Homework 4: Network Flows and Duality

    1. [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.



Duration

Maximum
Cost of
Task
Description

Predecessors
reduction
reduction


(in weeks)







(in weeks)
($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  oor
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 o  ce
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
{







    a) What is the earliest possible date of completion for the construction? Note that the last two columns of the table are not relevant for this part of the problem.

        i) [0.5 points] Write down the mathematical model of this optimization problem, including a description of the decision variables, objective function, constraints and parameters.

        ii) [1 points] Implement the problem in Julia. What is the earliest date of completion?

    b) The town council wants the builder to expedite the project. As an incentive, the council will pay a bonus of $30k/week for each week the work nishes early. To accomplish this, the builder may employ additional workers and rent more equipment to cut down on the total time. The last two columns of the table show the maximum number of weeks that can be saved per task and the associated additional cost per week incurred by the extra work. When will the project be completed if the builder is acting in a way that maximizes his pro t?

        i) [0.5 points] Write down the mathematical model of the new optimization problem. including a description of the decision variables, objective function, constraints and parameters.

        ii) [1 points] Implement the problem in Julia. When will the project be  nished?








1 of 2
CS/ECE/ISyE 524    Introduction to Optimization    L. Roald,    Spring 2022


    2. [3 points] Car rental. A small car rental company has a eet 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 ies). 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.


    3. [3 points] The chess problem. A small joinery makes two di erent sizes of boxwood chess sets. The small set requires 3 hours of machining on a lathe, and the large set requires 2 hours. There are four lathes with skilled operators who each work a 40 hour week, so we have 160 lathe-hours per week. The small chess set requires 1 kg of boxwood, and the large set requires 4 kg. Unfortunately, boxwood is scarce and only 200 kg per week can be obtained. When sold, each of the large chess sets yields a pro t of $8, and one of the small chess set has a pro t of $5. The problem is to decide how many sets of each kind should be made each week so as to maximize pro t.

        i) [1 point] Write out the primal LP. Plot the feasible set and solve the LP graphically. Be sure to label the axes and indicate units. Label the optimal point and nd the optimal objective.

        ii) [2 points] Derive the dual problem. Repeat all the same steps as in part a), and verify that the optimal dual objective is the same as the primal objective.






























2 of 2