Problemas de Roteamento e Programação

Prévia do material em texto

/
CENTRO UNIVERSITÁRIO DA GRANDE DOURADOS
Curso: Engenharia de Produção
Semestre: 6º 
Disciplina: Pesquisa Operacional
Professor: Bárbara Helen Rodrigues Ramires Seribeli
ATIVIDADE 2 - REFERENTE AS AULA 05 A 08
1. Uma pessoa vai trabalhar de carro todos os dias. Como acabou de concluir um curso de análise de redes, essa pessoa sabe determinar o caminho mais curto até seu local de trabalho. A rede da Figura a seguir mostra as possíveis rotas entre sua casa e seu trabalho. Desta forma, determine para essa pessoa a trilha mais curta que saem do nó 1 e chegam ao 7. 
2. Você precisa fazer uma viagem de carro para outra cidade que jamais havia estado anteriormente. Portanto, você está estudando um mapa para determinar a rota mais curta para seu destino. Dependendo de qual rota você escolher, há cinco outras cidades (chamemos estas A, B, C, D, E) que talvez você passe durante o caminho. O mapa mostra a milhagem ao longo de cada estrada que conecta diretamente duas cidades sem qualquer cidade entre elas. Esses números são sintetizados na tabela a seguir, na qual um traço indica que não há nenhuma estrada conectando diretamente essas duas cidades sem passar por alguma outra cidade.
a) Formule esse problema como um problema do caminho mais curto desenhando uma rede em que nós representam cidades, ligações representam estradas e números indicam o comprimento de cada ligação em milhas. 
(b). Use o modelo formulado no item anterior para resolver esse problema do caminho mais curto e determine o caminho ótimo. 
c) Suponha que o Custo unitário por milha percorrida seja de R$ 17,00 qual é o valor do custo mínimo?
3. Escreva ao menos 2 exemplos de programação não linear que um engenheiro ou administrador pode encontrar no dia a dia de trabalho.
4. Em quais tipos de problemas deve-se analisar o Fluxo Máximo de uma rede? Cite exemplos. 
5. Resolva o Exemplo 1.1 da aula 8 (programação dinâmica) considerando que são usadas as seguintes rotas apresentadas na figura abaixo: 
6. Formule um problema de programação não linear que caracterize uma função quadrática. 
7. Uma ferramentaria fabrica dois produtos. Cada unidade do primeiro produto requer 03 (três) horas na máquina 1 e 02 (duas) horas na máquina 2. Cada unidade do segundo produto requer 02 (duas) horas na máquina 1 e 03 (três) horas na máquina 2. A máquina 1 se encontra disponível somente 08 (oito) horas por dia e a máquina 2 apenas 07 (sete) horas por dia. O lucro por unidade vendida é 16 para o primeiro produto e 10 para o segundo. A quantidade de cada produto produzido por dia tem de ser um valor inteiro. O objetivo é determinar o mix de volume de produção que maximizará o lucro. 
(a) Formule um modelo de PI (Programação Inteira) para esse problema.
8. Considere o problema de Programação Inteira a seguir
Max Z = 2x1 + 3x2
Sujeito a
x1+ x2 ≤ 3
x1 + 3x2 ≤ 6
x1, x2 ≥ 0
x1, x2 são inteiras
a) Solucione este problema graficamente de forma relaxada;
b) Use o algoritmo de ramificação e avaliação progressiva (Método B&B) para resolver este
 problema de Programação inteira.
image2.png
image4.png
image3.png
image1.png