pesquisa

Cap´ıtulo 5

Exerc´ıcios Fluxo M´ aximo Enunciados

Exerc´ıcios Fluxo M´ aximo Enunciados

78

Problema 1
De trˆes dep´ositos A, B e C, dispondo respectivamente de 20, 10 e 35 toneladas de um dado produto, pretende-se fazer chegar a trˆes destinos D, E e F, respectivamente 25, 20 e
20 toneladas do produto. As disponibilidades de transporte em cami˜ ao entre os diferentes pontos, s˜ ao as seguintes:

A
B
C

D
15
5
10

E
10
—
5

F
—
10
5

Estabele¸ca o melhor plano de transportes.
(Sugest˜
ao: considere um n´ o fict´ıcio agregando a oferta e um n´ o fict´ıcio agregando a procura). Exerc´ıcios Fluxo M´ aximo Enunciados

79

Problema 2
Considere a seguinte rede, em que os n´ umeros nos arcos representam a capacidade do arco
(quantidade de fluxo que o pode atravessar):

2
10
1

15

5
3

20

10

12
15

5

20

6

5

4

Determine o fluxo m´ aximo poss´ıvel (entre os n´ os 1 e 6) e represente os fluxos na rede na situa¸c˜ao de fluxo m´ aximo. Exerc´ıcios Fluxo M´ aximo Enunciados

80

Problema 3
Considere a seguinte rede, em que os n´ umeros nos arcos representam a capacidade do arco
(quantidade de fluxo que o pode atravessar):

2

15

2

5

4

15
5

1

20

3

15

7

3
10

5

4

4

10

6

Determine o fluxo m´ aximo poss´ıvel (entre os n´ os 1 e 7) e represente os fluxos na rede na situa¸c˜ao de fluxo m´ aximo. Cap´ıtulo 5

Exerc´ıcios de Fluxo M´ aximo Resolu¸ c˜ oes

Exerc´ıcios de Fluxo M´ aximo Resolu¸c˜ oes 82

Problema 1
O problema proposto ´e um problema de fluxo m´ aximo. Seguindo a sugest˜ ao do enunciado, acrescentou-se ao problema um n´o fict´ıcio (X) agregando a oferta dos dep´ ositos A, B e
C e um n´ o fict´ıcio (Y ) agregando a procura dos destinos D, E e F . A rede inicial est´ a representada na figura seguinte.

A

(15,0)
(10,0)

D

(20,0)

(25,0)
(5,0)

f=0

X

(10,0)