Lista 4-III unidade

Lista 4-III unidade

Universidade Federal Rural do Semi-Árido Disciplina: Pesquisa Operacional

Professora: Adricia Fonseca Mendes Monitor: João Víctor Nunes Lopes

1. Explique como funciona o algoritmo Branch-and-Bound (B&B). O que significa

‘Branch’ e qual sua relação com o algoritmo? O que significa ‘Bound’ e qual sua relação com o algoritmo? 2. Resolva esse problema de PLI por meio do algoritmo BranchandBound. Indique a solução do problema relaxado e compare seus valores com a solução achada pelo algoritmo B&B.

3. Resolva esse problema de PLI por meio do algoritmo BranchandBound.

2𝑥1 + 𝑥2≤ 13

a) Explique o porquê de cada poda. b) Por meio da solução gráfica, demonstre onde estão localizadas a solução ótima do problema relaxado, e a solução ótima inteira encontrada por meio do algoritmo. Compare esses dois valores graficamente. c) Porque em alguns problemas devemos utilizar variáveis inteiras? Cite pelo menos dois exemplos envolvendo a necessidade de variáveis inteiras com o processo produtivo.

Lista 4 – I Unidade

4. A árvore a seguir foi encontrada por meio do algoritmo Branch-and-Bound. Indique e justifique as razões pelo qual os subproblemas foram podados.

a) Poda 1? b) Poda 2? c) Poda 3? d) Poda 4? e) Poda 5? f) Qual a solução ótima desse problema?

5. (QUESTÃO DESAFIO) Aplique o algoritmo Branch-and-Bound para a solução do seguinte problema de PLI.

2𝑥1+ 𝑥2 + 4𝑥3 ≥ 9

Comentários