Trabalho - Programação Inteira - Programação Linear e Inteira 2020-2

Nome: Frederico Guilherme Madeira Vaz Matrícula: 17.2.8224 Disciplina: Programação Linear e Inteira – ENP012 Professor: Alexandre Xavier Trabalho de Programação Inteira 1) Seja o modelo dado por P0: [fo] max = 4*x1 + 5*x2 + 3*x3 + 2*x4; (π+1)*x1 + (α+1)*x2 + (β+1)*x3 + (µ+1)*x4 <= 50; (π+1)*x1 + (α+2)*x2 <= 20; (β+3)*x3 + (µ+4)*x4 <= 25; x1, x2, x3, x4 >= 0 e inteiro π, α, β e µ são os quatro últimos números de sua matrícula. Matrícula: 17.2.8224, logo: π = 8, α =2, β = 2, µ = 4 Então: [fo] max = 4*x1 + 5*x2 + 3*x3 + 2*x4 9*x1 + 3*x2 + 3*x3 + 5*x4 <= 50; 9*x1 + 4*x2 <= 20; 5*x3 + 8*x4 <= 25; x1, x2, x3, x4 >= 0 e inteiro Seja P1 o problema com somente x1 inteiro, P2 o problema com somente x2 inteiro, P3 o problema somente com x3 inteiro e P4 o problema com somente x4 inteiro. Resolva P1, P2, P3 e P4 e responda qual dos problemas é a solução mais próxima de P0. Resolva e crie um documento em PDF com o modelo implementado e as soluções de cada problema com sua resposta. • Modelo implementado: • Solução de P1 P1 => x1 = 0, x2 = 4.750000, x3 = 4.600000, x4 = 0, Fo = 37.55000; • Solução de P2 P2 => x1 = 0.3333333, x2 = 4, x3 = 4.600000, x4 = 0, Fo = 35.13333; • Solução de P3 P3 => x1 = 0, x2 = 4.750000, x3 = 4, x4 = 0.3750000, Fo = 36.50000; • Solução de P4 P4 => x1 = 0, x2 = 4.750000, x3 = 4.600000, x4 = 0, Fo = 37.55000; Resposta: A solução mais próxima da solução inteira (PO) é P1 e P4 2) Seja o modelo dado por: [fo] max = (β+1)*x1 + (µ+1)*x2; -2*x1 + 2*x2 <= 5; 2*x1 + 4*x2 <= 13; 2*x1 - 2*x2 <= 5; x1, x2 >= 0 e inteiro β e µ são os dois últimos números de sua matrícula Matrícula: 17.2.8224, logo: β = 2, µ = 4, logo: [fo] max = 3*x1 + 5*x2; -2*x1 + 2*x2 <= 5; 2*x1 + 4*x2 <= 13; 2*x1 - 2*x2 <= 5; x1, x2 >= 0 e inteiro a) Identifique todas as soluções inteiras viáveis do problema. x = (3, 1), Q(x) = 14 x = (2, 2), Q(x) = 16 b) Resolva o problema pelo método Branch&Bound e mostre a árvore gerada ao longo da execução do método. Se as duas variáveis forem fracionárias em algum nó, escolha sempre x1 para ramificar. Se seu número de matrícula for par use a busca em largura, se for ímpar use a busca em profundidade.