2 lista - 3U

Prévia do material em texto

UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO
CENTRO DE ENGENHARIA – MOSSORÓ
BACHARELADO EM ENGENHARIA DE PRODUÇÃO
PESQUISA OPERACIONAL
Prof. Drª. Miriam Karla Rocha
LISTA 3
QUESTÃO 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.
max 𝑧 = 4𝑥1 + 5𝑥2
𝑠. 𝑎:
5𝑥1 + 7𝑥2 ≤ 44
4𝑥1 + 2𝑥2 ≤ 27
𝑥1, 𝑥2 ≥ 0
𝑥1, 𝑥2 𝑠ã𝑜 𝑖𝑛𝑡𝑒𝑖𝑟𝑜𝑠
RESPOSTA
	Através do solver e desconsiderando a restrição de x1 e x2 serem inteiros, é possível encontrar a solução relaxada, achando x1, x2 e Z. Achando o no1 2 o no2, resolvi seguir o no1 e deixar o no2 em espera:
	Função objetivo
	33,83333
	
	
	
	x1
	5,611111
	
	x2
	2,277778
	
	Restrições
	
	
	r1
	44
	<=
	44
	r2
	27
	<=
	27
	s1
	5,61
	<=
	5
	s3
	2,28
	<=
	2
	s4
	5,61
	>=
	3
	s5
	5,61
	<=
	4
	s6
	5,61
	>=
	5
Atualizando as restrições com o solver, fui encontrando os nós, os nós infactíveis são por terem R maior que a restrição. Ao chegar no nó 11 é possível podar o nó 2 por dominância. Os nós podados por otimalidade são serem uma solução ótima e possuírem dois números inteiros. O nó 13 foi excluído por dominância por sua solução ser menor que a solução ótima da 11. Sendo assim a solução ótima deste problema é a do nó11.
Maria José Ferreira Lopes