2023-228

A company launched a new gadget C to be produced globally for North American and South American markets.

The company uses just-in-time as a logistic strategy with no warehouse. Still, it has a quality control standard with the assistance of laboratories in the United Kingdom, Spain, and South Africa.

The company has some contractors in the Asia-Pacific region that make two types of components, A and B, to create the C product.  In order to produce one container of product C, two containers of component A and three containers of component B are necessary.

In the graph above, we show the logistic circuit of factories, ensemble centers (located in Singapure, Dubai , and Egypt), quality control labs, and consumer centers for this operation.  The production flow of component A (blue arrows), component B (red arrows), and the distribution flow (purple arrows) is shown. The numbers near the arrows show the capacity to transport from one location to another.

Which of the statements below are compatible with a production and distribution scheme in the manufacturing supply chain that delivers the maximum quantity of gadgets while producing the minimum amount of components?

1. New York gets 20 gadgets, Japan produces 42 components B, and Australia produces 22 components A.
2. Sao Paulo gets 9 gadgets, India produces 75 components B, and Hong Kong produces 50 components A.
3. Sao Paulo gets 10 gadgets, India produces 74 components B, and Hong Kong produces 45 components A
4. New York gets 18 gadgets, Japan produces 40 components B, and Australia produces 20 components A

Chose the right answer.

1. I
2. I and II
3. II and IV
4. III and IV
5. None of the above.

Original idea by: Alexander Valle Rey

2023-227

Consider a flow network for the company "A", which needs to deliver products from the capital to 10 cities. Three of these cities are small and don't have direct delivery routes from the capital. However, each of these small cities can receive products from the other 7 cities.

Due to a special event, City "T", one of the three small cities, requires a delivery of 650 products. The flow capacities of the network are defined as follows:

• Company "A" can send a maximum of 150 products to each city that has a direct connection from the capital.
• Two of the 7 cities that can receive products directly from the capital can forward a maximum of 200 products each to City "T".
• The remaining 5 of the 7 cities can forward a maximum of 50 products each to City "T".
• The other two small cities don't require any products.

Given these conditions, how many of the 650 requested products can be delivered to City "T" for the event?

1. 500
2. 550
3. 600
4. 650
5. None of the above

Original idea by: Thaysa Bello

2022-190

Consider the flow network below with source 1 and sink 10, where the capacities are shown besides each link.

Select the correct alternative containing the maximum flow through this network and possible flow values from node 1 to nodes 2, 4, and 3, respectively, in a max flow solution.

1. The maximum flow of the network is 19 and the flow values from node 1 are 8, 5, and 9.
2. The maximum flow of the network is 18 and the flow values from node 1 are 7, 5, and 6.
3. The maximum flow of the network is 20 and the flow values from node 1 are 7, 5, and 8.
4. The maximum flow of the network is 19 and the flow values from node 1 are 7, 5, and 7.
5. None of the above.

Original idea by: Rubens de Castro Pereira

2022-189

Goods are transported by trucks from two orchards to three retailers. Some of the orchards cannot ship directly to some of the retailers. The capacities of the routes are limited by the number of trucks available and the number of trips made daily.  The following table shows in the margins the daily amounts of supply at the orchards and demand at the farms. The cell entries of the table specify the daily capacities of the associated routes.  All figures are in number of container boxes.

Determine the maximum amount of container boxes that can be shipped daily from orchards to retailers.

A. 24

B. 10

C. 54

D. 17

E. None of the above.

Original idea by: Muhammad Idrees

2022-188

Consider the flow network in the figure, where s and t are the source and sink, respectively, with an initial flow though paths in blue and red. Choose the alternative with the pair of augmenting paths that together push the largest amount of flow in the corresponding residual graph.

1. s-A-C-F-H-D-t and s-E-C-F-H-D-t
2. s-A-C-D-t and s-E-C-F-H-D-t
3. s-E-G-I-t and s-A-C-E-G-I-t
4. s-A-C-F-H-t and s-E-C-B-D-t
5. None of the above.

Original idea by: Lucca Bavia

2022-187

What is the maximum flow from S to T in the network from Figure 1?

Fig. 1: A flow network.

1. 19.
2. 20.
3. 21.
4. 22.
5. None of the above.

Original idea by: Gabriel Oliveira

2022-126

Consider the statements below about network flows, where s is the source and t the sink:

I) The maximal flow in the following network is 10:

II) Given the following graph with flow/capacity for each link:

 

The residual graph associated to the above solution is the following:  

III) The push-relabeled based algorithms are the ones which involves computing a residual network and looking for augmenting paths.

 

IV) The sum of the incoming flow of a vertex u has to be equal to the sum of the outgoing flow of u, except in the source and sink nodes 

Mark the alternative that list exactly the true statements:

a) only I and IV 

b) only I, II, and IV

c) only II and III

d) only III and IV

e) None of the above 

Original idea by: Levy Chaves

2022-124

Consider the two networks A and B above, where the numbers close to each edge represent its respective capacities of flow and π can only assume values greater or equal to 0:

Select the correct alternative below:

A) Independently of the value of π, the maximum flow of network A cannot be bigger than the value of the max flow of network B.

B) If the value of π is 0, the maximum flow of network A will be smaller than the value of the max flow of network B.

C) Depending on the value of π, network B may have a maximum flow bigger than network A.

D) Only if the value of π is bigger than 2 network A will have a bigger flow than network B.

E) None of the above.

Original idea by: Athyrson M. Ribeiro

2022-118

Consider the flow from S to T in the network below. Flow and capacity (F:C) are defined for each link. 

Which alternative represents possible values of flow/capacity for the variables x, y, w, z:

1. x=3, y=4, w=2, z=5
2. x=2, y=4, w=2, z=6
3. x=3, y=5, w=2, z=4
4. x=3, y=5, w=1, z=5
5. None of the above

Original Idea by: Iury Cleveston

2022-117

The push-relabel algorithm is one of many known algorithms used to find maximum flows. Consider the following statements about the push-relabel algorithm:

1. The push–relabel algorithm is one of the most efficient maximum flow algorithms. It allows the flow to exceed the edge's flow capacity, except from the source. It pushes as much flow as possible, and in the end, it saturates all edges from the source.
2. The push-relabel algorithm first steps are: Start with initial flow as zero, and then find augmenting paths and add them to the flow. When no more augmenting paths exist, return the resulting flow.
3. The push-relabel algorithm uses a labeling function to assign heights to the nodes, determining which ones should be selected for the push operation.
4. There is an implementation of the push-relabel algorithm that is called Edmonds-Karp algorithm. This implementation uses Breadth-First Search, which reduces the time complexity of the original algorithm.
5. Another differential from the push-relabel algorithm is that it also requires the construction of the level graph of the residual network.
   

Select the option that exactly list the correct statements:

1. I, II and III are correct.
2. I, III, IV and V are correct.
3. I and IV are correct.
4. I and III are correct.
5. None of the above.

Original idea by: Heitor Mattosinho

2022-116

Considers the following characteristics of algorithms that find the maximum flow in a flow network:

1. Uses a combination of BFS and DFS;
2. Uses BFS to find the shortest augmenting path (in terms of number of edges used);
3. Finds augmenting paths in an unspecified manner;
4. Maintains a "preflow" instead of finding augmenting paths.

Which algorithms below fit these characteristics, respectively?

1. Ford-Fulkerson, Edmonds-Karp, Dinitz, Push-Relabel;
2. Dinitz, Ford-Fulkerson, Edmonds-Karp, Push-Relabel;
3. Dinitz, Edmonds-Karp, Ford-Fulkerson, Push-Relabel;
4. Push-Relabel, Edmonds-Karp, Ford-Fulkerson, Dinitz;
5. None of the above.

Original idea by: Filipe Roberto.