1) Resolver o PPL abaixo, usando o - Prof. Sérgio Mayerle
Transcrição
1) Resolver o PPL abaixo, usando o - Prof. Sérgio Mayerle
Universidade Federal de Santa Catarina EPS7005 – Pesquisa Operacional Prova I (02/05/2012) 1) Resolver o PPL abaixo, usando o método Simplex. Min z = 20 x1 + 15 x2 s.a: 2 x1 + x2 ≥ 20 x1 + 2 x2 ≥ 16 x1 + x2 ≥ 2 x1 ≥ 4 (3 pontos) x2 ≥ 8 2) Considere o PPL abaixo. Verifique se a solução ( x1 , x2 , x3 , x4 , x5 ) = (0,11,9,0,0) é ótima. Max z = 4 x1 + 4 x2 + 6 x3 + 4 x4 − 2 x5 2 x1 + x2 + x3 + x4 ≤ 20 s.a: x2 + x4 + x5 ≤ 15 x1 + 2 x3 + x4 + x5 ≤ 18 x1 , x2 , x3 , x4 , x5 ≥ 0 (2 pontos) 3) A fábrica WW produz 2 tipos de whisky, Glorius Blend e Super Blend, a partir de 3 maltes importados: Sir Roses, Highland Wind e Old Frenzy. Os fornecedores só conseguem garantir 2.000 litros de Sir Roses, 2.500 litros de Highland Wind e 1.200 litros de Old Frenzy, ao preço de 350, 250 e 200 euros por barril de 100 litros. Um litro de Glorious Blend é vendido por 3,40 euros, enquanto que para um litro de Super Blend esse valor é de 3,80 euros. Por questões de sabor e qualidade, é necessário que o Glorious Blend contenha pelo menos 60% de Sir Roses e no máximo 20% de Old Frenzy. Do mesmo modo, o Super Blend terá que conter pelo menos 15% de Sir Roses e no máximo 60% de Highland Wind. Admitindo-se que não existam outros custos de produção, encontre as quantidades a produzir de cada mistura de modo a maximizar o lucro do processo. (2 pontos) 4) Sete mil e quinhentos soldados formam um exército que precisa cruzar simultaneamente o Mediterrâneo. Dois tipos de embarcações estão disponíveis, com as seguintes características: Característica Consumo de combustível por viagem Tripulação necessária Capacidade Tipo 1 Tipo 2 12.000 litros 7.000 litros 250 pessoas 100 pessoas 2.000 soldados 1.000 soldados Apenas 55.000 litros de combustível e 900 tripulantes estão disponíveis. Destes, 300 estão habilitados a operar as embarcações do tipo 1, 400 estão habilitados a operar embarcações do tipo 2, enquanto o restante poderá ser usado em qualquer um dos dois tipos de embarcação. O exército pagará à companhia de navegação US$ 20.000,00 por cada viagem em embarcação do tipo 1 e US$ 10.000,00 por cada viagem em embarcação do tipo 2. Assumindo que a companhia de navegação possua um número suficiente de embarcações dos tipos 1 e 2, formule um modelo de programação linear que minimize o custo total desta operação. (3 pontos) GABARITO Questão 01: Construindo o PPL dual, tem-se: Max w = 20 y1 + 16 y2 + 2 y3 + 4 y4 + 8 y5 s.a: 2 y1 + y2 + y3 + y4 ≤ 20 y1 + 2 y2 + y3 + y5 ≤ 15 y1 , y2 , y3 , y4 , y5 ≥ 0 Resolvendo o PPL dual através do tableau: Encontra-se a seguinte solução ótima para o problema primal: Questão 2: Considerando a solução fornecida, tem-se o seguinte valor para as variáveis de folga: S1 = 20 − x2 − x3 = 20 − 11 − 9 = 0 S 2 = 15 − x2 = 15 − 11 = 4 S3 = 18 − 2 x3 = 18 − 2 × 9 = 0 Portanto, a variável de folga S2 precisa estar na base, com a seguinte partição: x2 xB = x3 S 2 1 1 0 B = 1 0 1 0 2 0 x1 x 4 xR = x5 S1 S3 2 1 0 1 0 R = 0 1 1 0 0 1 1 1 0 1 1 0 −0,5 B = 0 0 0, 5 −1 1 0, 5 −1 cBT = [ 4 6 0] cRT = [ 4 4 −2 0 0] 1 0 −0, 5 20 11 xˆB = B b = 0 0 0,5 15 = 9 −1 1 0,5 18 4 −1 1 0 −0,5 2 1 0 1 0 ∆z = c − c B R = [ 4 4 −2 0 0] − [ 4 6 0] 0 0 0, 5 0 1 1 0 0 = −1 1 0, 5 1 1 1 0 1 T R T B −1 ∆z = [ −5 −1 −3 −4 −1] Portanto, a partição obtida corresponde a base ótima. Questão 3: Os dados do problema encontram-se no diagrama abaixo, juntamente com o modelo: Sir Roses 2.000 litros € 350 / barril Highland Wind 2.500 litros € 250 / barril Old Frenzy 1.200 litros € 200 / barril Max 3, 4( x11 + x21 + x31 ) + 3,8( x12 + x22 + x32 ) − 3,5( x11 + x12 ) − 2,5( x21 + x22 ) − 2( x31 + x32 ) s.a : x11 + x12 ≤ 2000 x21 + x22 ≤ 2500 x31 + x32 ≤ 1200 x11 ≥ 0, 6( x11 + x21 + x31 ) x31 ≤ 0, 2( x11 + x21 + x31 ) x12 ≥ 0,15( x12 + x22 + x32 ) x22 ≤ 0, 6( x12 + x22 + x32 ) xij ≥ 0 ∀i, j onde: xij = quantidade do malte i no whisky j Glorious Blend € 3,40 / litro Sir Roses > 60% Old Frenzy < 20% Super Blend € 3,80 / litro Sir Roses > 20% Highland Wind < 60% Questão 4: Considere as seguintes variáveis: x1 = Número de embarcações/viagens do tipo 1 a serem contratadas; x2 = Número de embarcações/viagens do tipo 2 a serem contratadas; t1 = Número de tripulantes polivalentes alocados às embarcações do tipo 1; t2 = Número de tripulantes polivalentes alocados às embarcações do tipo 2; Min s.a: z = 20.000 x1 + 10.000 x2 12.000 x1 + 7.000 x2 ≤ 55.000 t1 + t2 ≤ 200 250 x1 ≤ 300 + t1 100 x2 ≤ 400 + t2 2.000 x1 + 1.000 x2 ≥ 7.500 x1 , x2 , t1 , t2 ≥ 0 e x1 , x2 , t1 , t2 ∈ ℤ (1) (2) (3) (4) (5) (6) (7) Na formulação acima a função (1) minimiza os custos da operação; a restrição (2) garante não se gastar mais combustível que o disponível; a restrição (3) limita o número de tripulantes polivalentes; as restrições (4) e (5) limitam o número de viagens em embarcações do tipo 1 e 2, considerando a disponibilidade de tripulantes; a restrição (6) assegura o transprte de todos os soldados; e a condição (7) garante a não-negatividade e integridade das variáveis.