A PESQUISA OPERACIONAL

MOD 5

Problema de caminho mínimo, fluxo máximo e mínima arborescência

4 (Darlan)- Para a rede abaixo, resolva um modelo linear que forneça o caminho mais curto entre os nós A e B.

[pic 1]

Resposta: Distancia = 27

6 (Darlan)- Resolva, para a rede abaixo, o problema da mínima arborescência. Use o algoritmo de Prim e Kruskal.

[pic 2]

Resposta: comprimento mínimo = 35.

9 (Maria)- Obter o fluxo máximo na rede abaixo, sendo o nó 1 a origem e os nós 8 e 9 os destinos

[pic 3]

Resposta: fluxo máximo = 2500

10 (Maria)- Seja a seguinte rede:

[pic 4]

1. Utilize o algoritmo de Ford e Fulkerson para obter o fluxo máximo.
2. Construa o modelo de programação linear inteira.

Resposta: fluxo máximo = 16

11- Use o algoritmo de Ford e Fulkerson e modelo matemático de PL para obter o fluxo máximo na rede abaixo, sendo o nó 1 a origem e 5 o destino

[pic 5]

Resposta: fluxo máximo = 55

12- A rede

[pic 6]

        Dá as distâncias em km entre pares de cidades 1,2,...,8. Use o algoritmo de Dijkstra para achar o caminho mais curto entre as seguintes cidades.

1. Cidades 1 e 8;    (b) Cidades  2 e 6.

Resposta: (a) distância mínima = 8. (b) distância mínima = 5.

13- Seja uma rede de telecomunicações conectando vários terminais de retransmissores para atender chamadas telefônicas. A configuração física do sistema para determinar quantas chamadas podem ser feitas entre quaisquer 2 transmissores deve ser calculada, ou seja, devemos quantificar o número máximo de chamadas que o sistema pode acomodar. Cada chamada entre 2 retransmissores pode ser tratada como unidade de fluxo. O fluxo total, ou seja, o número de chamadas através da rede deve ser maximizada. A figura abaixo mostra a rede de retransmissores para a companhia de telefone. Maximizar o fluxo de chamadas, considerando que o nó A é a origem e o nó L o destino.

[pic 7]

Resposta: fluxo máximo = 14

14- Uma TV a cabo está em vias de fornecer serviços por cabo a cinco novas áreas onde estão em desenvolvimento projetos residenciais. A rede abaixo mostra as possíveis conexões de TV entre as cinco áreas. As conexões (em km) dos cabos são mostradas em cada arco. Determine a rede mais econômica.

[pic 8] 

                               

Resposta: comprimento mínimo = 16

...