OPTIMIZATION - 3AGI3 & 1A Mastère GSI ENIT 2009-2010

Homework Assignment #2

Exercise 1.
On the following network, X, Y, Z and T represent different terminal zones within a
town and A, B and C are three gates for exiting the town. The arcs represent
unidirectional links. All vehicles departing from one terminal may choose any path
(in an undetermined way) towards one of the gates, at a speed that is roughly
constant. We assume that, beyond the outskirts of the town, there is no traffic
congestion.

The capacity of each link is given in number of vehicles per hour, as shown on the
arcs of the following network:

1000 800
X 1 A

300 600
500

400 1000
Y 2 B

200 800
900
600
Z 3
700
800
700
T C

Consider the arc flows given in the following table:

Arc (i,j) (X,1) (Y,1) (Y,2) (Z,2) (Z,3) (T,3) (T,C) (1,A) (1,B) (1,2) (2,B) (2,3) (3,B) (3,C)
Flow 1.000 500 400 500 600 700 700 800 400 300 1.000 200 800 700

1. Apply the algorithm of Ford-Fulkerson to determine the maximal value flow

vector, starting from the above solution.

2. Give a minimum capacity cut.

Exercise 2.
A manufacturer has to transport 200 tons of material from one factory to a
construction site that is far away. The transportation companies that are contacted
can only offer a limited transportation capacity. The basic itineraries are described
in the following table. Node 1 represents the factory and node 6 designates the
construction site. Each arc corresponds to a roadway or a railway link with a given
capacity (in tons) and a unit transportation cost (TND/ton).

In addition, node 2 is a hub of unlimited capacity and from which may depart heavy
trucks. Merchandise grouping cost at this hub is equal to 5TND/ton. The company
wants to know how much material it can expedite on the different itineraries in
order to transport the material at a minimum cost.

1
OPTIMIZATION - 3AGI3 & 1A Mastère GSI ENIT 2009-2010

Node Successors Mode Capacity (t) Cost (TND/t)

1 2 Route 150 50
3 Rail 150 15
2 5 Route 300 20
4 Rail 50 10
3 2 Route 200 30
4 Route 100 60
4 6 Route 150 60
5 6 Route 100 40

1. What are the simplifications you can make regarding node 5? How can you
transform the hub (node 2) cost into a cost on an arc?

2. Will the capacity offered by the different transporters be able to accommodate

the required 200 tons (without any consideration of cost)?

3. Identify the manufacturer problem and solve it using one of the network
programming models.

4. What should you do to determine the maximum quantity of merchandise that

can flow through the network at a minimum cost?

Exercise 3.
A manager of a software development project has broken down the project into 5
modules. He wants to assign these modules to the 5 programmers of the company.
Experience has shown that imposing a task on the employees does not give good
results. That is why the manager has asked the programmers to give their preferred
tasks, as shown on the table below:
Programmer Preferred
modules
Programmer 1 Module 3, 4 or 5
Programmer 2 Module 1
Programmer 3 Module 1 or 2
Programmer 4 Module 1, 2 or 5
Programmer 5 Module 2

Notice that a programmer cannot be assigned to more than one module and that a
module cannot be divided between the programmers.

1. After modeling this problem as a network, that has to be clearly presented,

find an optimal assignment of programmers to modules. Will the manager
be able to execute all modules while taking into account the preferences of
the programmers?

2. Now, in addition to all the above, the project manager has to respect a
budget constraint. He has to assign the modules to programmers such as
total cost is minimized. By considering the salary of each employee and the

2
OPTIMIZATION - 3AGI3 & 1A Mastère GSI ENIT 2009-2010

necessary time to finish each module, he defines a cost associated to the

assignment of each programmer to each module, as indicated in the
following table:

Necessary cost to complete the module (TND)

Programmer
1 2 3 4 5
1 180 140 160
2 240
3 240 240
4 320 300 240
5 320

a) Formulate the problem as a network (give all necessary explanations)

b) Find the new optimal assignment while, again, taking into account the
programmers’ preferences.

Exercise 4.
A company buys and sells 4 types of electrical switches denoted by D1, D2, D3 and
D4. It has the possibility of buying them from 5 suppliers denoted by F1, F2, F3, F4
and F5. The purchase prices of these switches depend on the supplier and are given
in the following table. If a supplier does not produce one type of switch, the
corresponding cell in the table is marked by (*). Example: Supplier F2 does not
produce D2 and D3.
F1 F2 F3 F4 F5
D1 100 110 95 100 90
D2 250 * 230 * 210
D3 180 * 175 190 185
D4 140 150 120 * 135

The available quantities of each type of switch per week as well as the quantities
that the company would like to buy per week are given in the following table:
F1 F2 F3 F4 F5 Quantity to buy per week
D1 500 200 200 200 300 1000
D2 100 * 400 * 400 500
D3 400 * 400 1000 200 1500
D4 1000 500 500 * 1000 2000

The company wants to determine the quantity of each type of switch to buy from
each supplier so as to minimize its total purchase cost.

1. Show that this problem can be modeled as a maximum value-minimum cost

flow on a network. Give the set of nodes, the set of arcs and the data on the
arcs while providing necessary justifications. Do not solve.

3
OPTIMIZATION - 3AGI3 & 1A Mastère GSI ENIT 2009-2010

2. The switches D3 and D4 are equivalent (one could replace the other).
Therefore, the company can propose one type or the other to its customers.
The company then decides to buy 3000 switches per week of types D3 and D4
together.
How can one include this new data in the maximum value-minimum cost flow
model? Justify your answer.

Exercise 5.
A school board wants to choose, among 7 students, representatives in its Scientific
Committee. The students have competencies in 5 different fields: Mathematics,
Physics, Art, Literature, and Engineering. The competencies of the different
students in the different fields are given in the table below:

Field Competent
students
Mathematics 1, 2, 4
Physics 1, 3, 5
Art 3, 4, 6
Literature 4, 6, 7
Engineering 1, 2, 5

A student who has competencies in more that one field has to be assigned to
exclusively one field. Moreover, at most 2 students from the same field can be part
of the Committee.

1. Formulate this problem as a network model that should be carefully

described (nodes, arcs, values on arcs, type of problem).

2. Transform the network so that at most 3 students are selected from the two
fields of Mathematics and Physics, combined.

3. The students belong to 4 different clubs. The following table shows the
affiliation of students to the different clubs.

Club Affiliated
students
1 1, 2, 3, 7
2 1, 3, 5
3 3, 4, 5
4 1, 2, 4, 6

In addition to the previous constraints, in other words:

• a student who has competencies in more that one field has to be
assigned to exclusively one field,
• at most 2 students from the same field can be part of the Committee,
each club has to be represented in the Committee by at most one student,
and each student can represent only one club.

Give the corresponding network.