Respostas do livro da unidade 4 - APENDICE_U4_PO_PM

Prévia do material em texto

APÊNDICE
UNIDADE 4
Pesquisa 
operacional: 
programação 
matemática
2 U4 - Programação Inteira
UNIDADE 4: Programação Inteira
Gabarito 1. Faça valer a pena - Seção 4.1
1. Alternativa Correta: C 
Resposta Comentada: 
A solução do problema relaxado envolve considerá-lo um problema de 
Programação Linear. Para que a solução seja possível, devemos ignorar a 
restrição de integralidade, ou seja, devemos aceitar que todas as variáveis 
de decisão sejam reais.
2. Alternativa Correta: D 
Resposta Comentada: 
Muitos problemas de otimização discreta envolvem a ocorrência ou não 
de um determinado evento e a decisão fica sujeita a duas alternativas. Esse 
é um típico caso de problema a ser resolvido pela Programação Binária.
3. Alternativa Correta: A 
Resposta Comentada: 
O problema do caixeiro viajante é, provavelmente, o mais conhecido e 
estudado da PI. Consiste em determinar uma rota de custo mínimo de tal 
forma que ela passe por todas as cidades ou clientes de uma rede uma 
única vez e retorne ao ponto de partida.
Apêndice
Gabaritos comentados com resposta-padrão
3 U4 - Programação Inteira
Gabarito 2. Faça valer a pena - Seção 4.2
1. Alternativa Correta: C 
Resposta Comentada: 
O método de solução gráfica dos problemas de PI e PL envolve um gráfico 
cartesiano de eixos ortogonais em que as variáveis são postas nos eixos 
da ordenada e da abcissa, o que impossibilita utilizar o método com 
problemas de mais de duas variáveis.
2. Alternativa Correta: A 
Resposta Comentada: 
A procura por uma solução ótima por enumeração completa nem sempre 
é razoável, dependendo do número de variáveis. Considerando um 
problema com x variáveis de decisão que possam assumir valores de 1 
a n, teríamos nx pontos para enumerar e testar o que é muito trabalhoso 
mesmo com o auxílio de computadores.
3. Alternativa Correta: D 
Resposta Comentada: 
O algoritmo Branch and Bound baseia-se em ramificar os problemas 
originais em subproblemas menores e posteriormente solucionam-se os 
subproblemas gerando limite superior (em problemas de maximização) 
ou limite inferior (para problemas de minimização). As soluções dos 
subproblemas são combinadas até que se encontre uma solução ótima 
para o problema original.
4 U4 - Programação Inteira
Gabarito 3. Faça valer a pena - Seção 4.3
1. Alternativa Correta: B 
Resposta Comentada: 
Observando o modelo podemos notar que se trata de um problema de 
Programação Inteira Mista, pois apenas uma das variáveis de decisão deve 
ser inteira. Portanto,a outra variável poderá ser fracionada. Problemas de 
Programação Inteira Pura possuem todas as variáveis são inteiras.
2. Alternativa Correta: D 
Resposta Comentada: 
A etapa inicial de solução dos problemas de Programação Inteira através 
do algoritmo Branch and Bound é a resolução do problema original 
relaxado. No caso de problema de Programação Binária deve-se ignorar 
(relaxar) a restrição das variáveis serem binárias e solucionar o problema 
original com um problema de Programação Linear.
3. Alternativa Correta: E 
Resposta Comentada: 
Problemas de mistura são problemas típicos de Programação Linear. 
Problemas de maximização ou de minimização dizem respeito ao 
objetivo do estudo do problema, ou seja, a função objetivo. Os 
problemas de localização são problemas de Programação Binário, pois 
um local pode ou não ser escolhido, portanto, as variáveis podem ser 
somente uma ou outra (0 ou 1). No problema da mochila itens devem 
ser escolhidos de forma a otimizar a utilização da mochila, novamente, 
itens devem ser escolhidos ou não.