Slide - Programação Inteira Pt 2 -2024-1

PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMAS DIVERSOS EXEMPLO 1. A universidade usa um modelo matemático que otimiza as preferências dos estudantes levando em consideração a limitação das salas de aula e os recursos da faculdade. Para demonstrar a aplicação do modelo, considere o caso simplificado de dez estudantes que devem selecionar 2 cursos eletivos entre os 6 oferecidos. A tabela ao lado apresenta contagens que representam a preferência de cada estudante para cursos individuais, sendo que a contagem 100 é a mais alta. Para simplificar, considera-se que a contagem de preferência para uma seleção de 2 cursos é a soma das contagens individuais. A capacidade do curso é o número máximo de estudantes que poderão assistir às aulas. Contagem de preferências por curso Estudante 1 2 3 4 5 6 1 20 40 50 30 90 100 2 90 100 80 70 10 40 3 25 40 30 80 95 90 4 80 50 60 80 30 40 5 75 60 90 100 50 40 6 60 40 90 10 80 80 7 45 40 70 60 55 60 8 30 100 40 70 90 55 9 80 60 100 70 65 80 10 40 60 80 100 90 10 Capacidade do curso 6 8 5 5 6 5 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMAS DIVERSOS SOLUÇÃO EXEMPLO 1. MAX PREFERÊNCIAS = 20*X11+40*X12+...+10*X10,6 s.a. X11+X12+X13+X14+X15+X16=2 (estudante 1 ................................... X10,1+X10,2+X10,3+X10,4+X10,5+X10,6=2 (estudante 10) X11+ X21+X31+...+X10,1<6 (capacidade curso 1) ............................................ X16+ X26+X36+...+X10,6<5 (capacidade curso 6) Xij É BINÁRIO. PROGRAMAÇÃO INTEIRA (PI) PROBLEMAS DIVERSOS (SOLUÇÃO EXEMPLO 1) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMAS DIVERSOS (SOLUÇÃO EXEMPLO 1) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA Usando a ferramenta Solver, encontra-se o seguinte resultado PROGRAMAÇÃO INTEIRA (PI) PROBLEMAS DIVERSOS PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA Uma rede de lanchonetes deseja construir quatro lojas na área de Curitiba. No passado a cadeia utilizou os serviços de seis empresas construtoras e, tendo ficado satisfeita com todas, convidou cada uma delas a cotar cada um dos serviços. As propostas finais (em milhares de dólares) estão indicadas no quadro a seguir. 1 2 3 4 5 6 Lanchonete 1 85.3 88.0 87.5 82.4 89.1 86.7 Lanchonete 2 78.9 77.4 77.4 76.5 79.3 78.3 Lanchonete 3 82.0 81.3 82.4 80.6 83.5 81.7 Lanchonete 4 84.3 84.6 86.2 83.3 84.4 85.5 Uma vez que a rede de lanchonetes deseja dispor das novas lojas prontas o mais rápido possível designará no máximo uma obra a cada uma das companhias construtoras. Que alocação resulta em custo total mínimo para a rede de lanchonetes? Companhias construtoras EXEMPLO 2. PROGRAMAÇÃO INTEIRA (PI) PROBLEMAS DIVERSOS PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA SOLUÇÃO EXEMPLO 2. Xij = 1, SE A LANCHONETE i FOR DESIGNADA À CONSTRUTORA j. ZERO EM CC. MIN CUSTO = 85,3*X11+88*X12+...+0*X66 X11+X12+...+X16=1; ............... X61+X62+...X66=1 X11+X21+...+X61=1 ..................... X16+...+X66 = 1 PROGRAMAÇÃO INTEIRA (PI) PROBLEMAS DIVERSOS PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA SOLUÇÃO EXEMPLO 2. PROGRAMAÇÃO INTEIRA (PI) PROBLEMAS DIVERSOS PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA SOLUÇÃO EXEMPLO 2. Usando a ferramenta Solver, encontra-se a seguinte solução. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA Consiste na decisão de que objetos colocar em uma mochila, de forma a maximizar uma função utilidade. Problema da Mochila 0-1 EXEMPLO 3. Sete projetos estão sob avaliação dentro de uma projeção de planejamento de 3 anos. A tabela abaixo dá os retornos esperados para cada projeto e os desembolsos anuais associados. Com o objetivo de maximizar o retorno, quais projetos devem ser selecionados na projeção de 3 anos? PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA SOLUÇÃO EXEMPLO 3. Modelo: Max R = 20x1 + 40x2 + 20x3 + 15x4 + 30x5 s.a. 5x1+4x2+3x3+7x4+8x5 <= 25 (ANO 1) x1+7x2+9x3+4x4+6x5 <= 25 (ANO 2) 8x1+10x2+2x3+x4+10x5 <= 25 (ANO 3) xj {0,1}, j=0,...5 ∈ Solução ótima: x1 = x2 = x3 = x4 = 1 e x5 = 0. R = 95 milhões PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA EXEMPLO 4. Considere que a empresa VVC esteja interessada em adquirir ou não participações que são definidas pela tabela abaixo: A VVC quer saber em qual oportunidade de investimento ela deve investir, a fim de maximizar o VPL? PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA SOLUÇÃO EXEMPLO 4. Modelo: Max R = 20xA+15xB+34xC+17xD+56xE+76xF+29xG s.a. 12xA+54xB+65xC+38xD+52xE+98xF+15xG<=200 (ANO 1) 34xA+94xB+28xC+21xE+73xF+48xG<=250 (ANO 2) 12xA+67xB+49xC+8xD+42xE+25xF+53xG<=150 (ANO 3) xj {0,1}, j=A,...G ∈ Solução ótima: xA =xE = xF = xG = 1 e xB = xC = xD = 0. R = 181. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA EXEMPLO 5. UM EXCURSIONISTA PLANEJA FAZER UMA VIAGEM PARA ACAMPAR. HÁ 5 ITENS QUE O EXCURSIONISTA DESEJA LEVAR CONSIGO, MAS ESTES, JUNTOS, EXCEDEM O LIMITE DE 60 KG QUE ELE SUPÕE SER CAPAZ DE CARREGAR. PARA AJUDAR A SI PRÓPRIO NO PROCESSO DE SELEÇÃO ELE ATRIBUI VALORES, POR ORDEM CRESCENTE DE IMPORTÂNCIA, A CADA UM DOS ITENS SEGUNDO A TABELA: ÍTEM 1 2 3 4 5 PESO(KG) 52 23 35 15 7 VALOR 100 60 70 15 15 QUE ITENS DEVEM SER LEVADOS DE FORMA A MAXIMIZAR O VALOR TOTAL SEM EXCEDER AS RESTRIÇÕES DE PESO? PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA SOLUÇÃO EXEMPLO 5. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA EXEMPLO 6. Há um conjunto com 10 itens e 3 mochilas A,B e C com capacidades 50, 25 e 40 kg, respectivamente. Sabendo-se que existe uma unidade de cada item e, que a cada item está associado um peso e um valor. Determine os itens que devem ser alocados em cada mochila de forma que o valor total seja maximizado. Item 1 2 3 4 5 6 7 8 9 10 Peso(kg) 16 18 14 22 8 10 12 6 14 8 Valor 6 8 5 12 8 4 6 2 8 2 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA SOLUÇÃO EXEMPLO 6. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA SOLUÇÃO EXEMPLO 6. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA SOLUÇÃO EXEMPLO 6. Usando a ferramenta Solver, encontra-se a solução PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA EXEMPLO 7. Seja um conjunto com 10 itens e uma mochila de capacidade 200 kg. Sabendo-se que existem várias unidades de cada item e que cada um deles está associado um determinado peso e valor, determine a quantidade de cada item que deve ser alocada na mochila para que o valor total seja maximizado. Item 1 2 3 4 5 6 7 8 9 10 Peso(kg) 29 35 25 20 15 20 18 12 30 8 Valor 6 8 5 12 9 2 5 2 7 4 Unidades 2 4 1 3 2 1 2 3 1 2 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA SOLUÇÃO EXEMPLO 7. VALOR MÁXIMO =84 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA EXEMPLO 8. Seja um conjunto com 10 itens e 3 mochilas A, B e C com capacidades 95, 50 e 45 kg, respectivamente. Sabendo-se que existem várias unidades de cada item e que cada um deles está associado um determinado peso e valor, determine a quantidade de cada item que deve ser alocada às mochilas para que o valor total seja maximizado. RESP.: VALOR MÁXIMO = 81 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA MOCHILA SOLUÇÃO EXEMPLO 2. RESP.: VALOR MÁXIMO = 81 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) EXEMPLO 5. ALOCAÇÃO DE PESSOAL (STAFF SCHEDULING) O departamento de polícia de uma cidade tem necessidades mínimas diárias de policiais mostradas na tabela abaixo. Cada pessoa trabalha 8 horas consecutivas. Ao montar o quadro de horário nada impede, por exemplo, que uma turma inicie os trabalhos no período 1, outra no período 2, nenhuma no período 3, etc. formule e resolva o modelo linear que determina a programação que empregue a menor quantidade total de pessoal. Horário 02-06 06-10 10-14 14-18 18-22 22-02 Necessidade de policiais 20 50 60 80 60 40 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO EXEMPLO 5. ALOCAÇÃO DE PESSOAL (STAFF SCHEDULING) Xj = NÚMERO DE POLICIAIS QUE INICIA NA HORA j, COM J=1(entrada às 02:00),2(entrada às 06:00),...,6(entrada às 22:00). MIN NÚMERO DE POLICIAIS = X1+X2+X3+X4+X5+X6 S.A. (02-06): X1+X6 >= 20 (06-10): X2+X1 >= 50 (10-14): X3+X2 >= 60 (14:18): X4+X3 >= 80 (18-22): X5+X4 >= 60 (22-02): X6+X5 >= 40 Xj >=0 E inteiras. SOLUÇÃO: X1= 50 ; X2=0; X3=60 ; X4=20 ; X5=40; X6=0 ; Z=170 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) EXEMPLO 6. ALOCAÇÃO DE PESSOAL (STAFF SCHEDULING) O administrador de um hospital deseja determinar o escalonamento dos enfermeiros. Para isso ele organiza um sistema de plantão dividindo o dia em 6 períodos de 4 horas. A tabela a seguir mostra o número mínimo de enfermeiros que devem estar presentes em cada horário. Horário 08-12 12-16 16-20 20-24 24-04 04-08 Qtde. enfermeiros 51 58 62 41 32 19 Cada enfermeiro cumpre um plantão de 8 horas, que pode começar no início de um destes períodos. No horário de 8 às 20 horas, o enfermeiro recebe $ 100 por hora de trabalho e $ 120 no horário noturno (20 h às 08h). Como o administrador deve escalar os enfermeiros de forma a minimizar o custo com a mão-de- obra? min 800x08+800x12+880x16+960x20+960x24+880x04 s.t. x08+x04>51 x12+x08>58 x16+x12>62 x20+x16>41 x24+x20>32 x04+x24>19 Xj>=0 e inteiras. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO DO EXEMPLO 6. ALOCAÇÃO DE PESSOAL (STAFF SCHEDULING) SOLUÇÃO ÓTIMA X08 = 51.00000 ; X16 = 28 ; X12 = 34 X20 = 13.00000 ; X24 = 19.00000 ; X04 = 0.000000