Trabalho Redes - P.O.

Prévia do material em texto

Universidade Federal de Viçosa INF280 – Pesquisa Operacional I Departamento de Informática TRABALHO Prof.: Luciana Brugiolo Gonçalves 
Para cada um dos problemas apresentados, utilize as estratégias vistas em sala de aula para determinar o que se pede. O trabalho pode ser feito em DUPLA e deve ser entregue até a data da terceira prova.
Problema 1 
Considere o grafo ao lado com cinco vértices, onde os valores associados aos arcos indicam a capacidade máxima de fluxo que é possível passar por cada arco. Dadas estas informações, o objetivo é determinar o fluxo máximo que é possível enviar do nó fonte F para o nó terminal T. 
A rede de fluxo abaixo descreve uma distribuição de fluxo que respeita as capacidades dos arcos. Esta foi obtida após serem considerados os caminhos FCT, FAT e FBCT. Construa a rede residual associada a esta distribuição e verifique se é possível inserir mais fluxo ou se este já é máximo.
 
Problema 2 
A tabela abaixo mostra os custos de transporte entre três depósitos (Depósito 1, Depósito 2 e Depósito 3), e as Lojas 1, 2, 3 e 4 de uma determinada franquia. Mostra ainda a quantidade de mercadoria disponível em cada depósito e a demanda em cada loja. Deseja-se saber como efetuar o transporte para atender a demanda a custo mínimo.
Custo de Transporte
Oferta das fontes
Loja 1
Loja 2
Loja 3
Loja 4
Origem
Depósito 1
45
50
65
85
75
Depósito 2
35
40
70
80
125
Depósito 3
90
70
40
70
100
Demanda de cada destino
80
70
65
85
Encontre uma solução para o problema por algum dos métodos vistos na disciplina (Identifique o método utilizado).
Para a solução obtida no item anterior, utilizando o método dos multiplicadores, determine a solução ótima para o problema. 
Problema 3 
A Century Studios está prestes a começar a produção de seu mais importante filme do ano. O produtor do filme decidiu usar o método Pert/CPM para ajudar no planejamento e controle desse projeto. Ele identificou as oito principais atividades necessárias para produzir o filme, entre elas: desenvolvimento da ideia, desenvolvimento da estética do filme, definição da equipe e elenco, definição do cenário, escolha dos equipamentos, filmagem, edição e adição de efeitos sonoros e música. Suas relações de precedência e duração são apresentadas na tabela abaixo. 
	Atividades
	Atividades Predecessoras
	Duração (semanas)
	A
	-
	5
	B
	-
	3
	C
	A
	4
	D
	A
	6
	E
	B
	5
	F
	B
	7
	G
	C, E
	9
	H
	D, F
	8
Para este projeto, destaque as atividades críticas e calcule a folga associada às demais atividades (use para isto o tempo de início/fim mais cedo e mais tarde de cada tarefa). 
Indique o tempo necessário para a conclusão de todas as atividades.
Problema 4 
Considere uma empresa que deseja conectar todos seus diversos departamentos utilizando cabos de fibra ótica. A empresa deseja instalar esta conexão ao menor custo possível e sabe-se que as despesas são proporcionais ao comprimento total do cabo de fibra ótica necessário para se realizar estas conexões. Se cada nó do grafo representa um departamento da empresa e as arestas representam os pares de departamentos que podem ser conectados, determine o conjunto de arestas que conectam todos os nós de forma que comprimento total de fibra ótica utilizada seja o menor possível. Informe o algoritmo utilizado, a ordem de seleção das arestas e o custo da solução.
 Problema 5
A Copa do Mundo do Brasil está aí e ao todo temos 12 capitais brasileiras onde temos jogos. Além de Brasília (DF), teremos jogos no Rio de Janeiro (RJ), São Paulo (SP), Belo Horizonte (MG),Porto Alegre (RS), Cuiabá (MT), Curitiba (PR), Fortaleza (CE), Manaus (AM), Natal (RN), Recife (PE) e Salva-dor (BA). A Copa de 2014 começou com o jogo de Brasil x Croácia no dia 12 de junho, na capital paulista, no mais novo estádio: a Arena Corinthians, também conhecida como Itaquerão, que também sediou jogos de outros campeões mundiais, como Uruguai x Inglaterra. A decisão final da Copa será no Rio de Janeiro, no mais famoso estádio brasileiro, o Maracanã, no dia 13 de julho.
Temos turistas espalhados em todas as 12 cidades onde os jogos ocorreram e ainda ocorrerão. Foi solicitado que você os ajude na tarefa de determinar a forma mais econômica de sairem de cada uma destas cidades para chegarem à cidade do Rio de Janeiro. 
Para isso você deve estimar o custo para cada uma das conexões destacadas no mapa (arestas) e, usando um dos algoritmos vistos na disciplina, determinar o que se pede.