Programação Linear Inteira Formulação de Modelos-2020-1

16 Programação Linear Inteira – Formulação de Modelos © 2020 Prof. Sérgio F. Mayerle 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 11  Exemplo 1 – Aplicação financeira  Exemplo 2 – Balanceamento de linha de montagem  Exemplo 3 – Contratação de especialistas  Exemplo 4 – Localização de antenas celulares  Exemplo 5 – Programação das provas finais 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 11 Exemplo 1 – Aplicação financeira Um empreendedor pode aplicar seu dinheiro em 5 projetos de investimento, cujos dados são apresentados abaixo: Fluxo de Caixa Anula (R$ 1.000,00) Projeto Ano 0 Ano 1 Ano 2 Ano 3 I (100,00) 170,00 II (150,00) 220,00 III (100,00) 150,00 IV (50,00) 80,00 V (70,00) 130,00 Formule um modelo que ajude o investidor a determinar os projetos que maximizam o seu capital ao final do ano 3, considerando que:  o capital inicial disponível é de R$ 220.000,00 e não poderá ser tomado empréstimo;  todo capital disponível poderá ser aplicado na poupança que rende juros de 10 % a.a;  I e V são projetos mutuamente exclusivos. 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 11 MODELO MODEL: [Z] MAX = S3; [M0] S0 = 220 – 100 * X1 – 150 * X2 – 50 * X4; [M1] S1 = 1.1 * S0 + 80 * X4 – 100 * X3 – 70 * X5; [M2] S2 = 1.1 * S1 + 170 * X1; [M3] S3 = 1.1 * S2 + 220 * X2 + 150 * X3 + 130 * X5; [COMP] X1 + X5 < 1; @BIN(X1); @BIN(X2); @BIN(X3); @BIN(X4); @BIN(X5); END 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 11 Exemplo 2 – Balanceamento de linha de montagem Em uma linha de montagem existem 8 tarefas que podem ser realizadas como indicado abaixo: Tarefa Tempo da Tarefa (min) Tarefas Predecessoras 1 7 - 2 6 - 3 8 - 4 8 1 , 2 5 1 2 , 3 6 6 4 , 5 7 7 5 8 8 6 , 7 Considere que um trabalhador é posicionado em cada estação de trabalho e pode realizar um certo número de tarefas em sua estação. Considere, ainda, que a cada 15 minutos uma unidade do produto deve sair da linha de produção. Formule um modelo de programação matemática que determine quantas estações de trabalho devem ser utilizadas, e quais as tarefas que deve ser alocadas a cada estação. 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 11 MODELO 1 1 1 1 1 1 . : 1 1,..., 1,..., {0,1} , nk n k ik k i nk ik k n i ik i nk nk ik jk k k ik Min z P x s a x i n T x TC k nk k x k x i j x i k                        onde kP é uma penalidade crescente associada à alocação de tarefas no posto de ordem k ; iT é o tempo de realização da tarefa  1,...,  i m  , e TC é o tempo de ciclo da linha de montagem. A variável   0,1 ik x  indica se a tarefa  1,...,  i m  será alocada ao posto   1,..., k nk  . 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 11 Exemplo 3 – Contratação de especialistas Para realizar negociações comerciais com diversos países, uma empresa precisa contratar profissionais qualificados e treinados em diversos idiomas (inglês, francês, espanhol, italiano, alemão, russo, chinês e japonês). Após um rigoroso processo de seleção, restaram 8 candidatos, cujos dados estão apresentados na tabela abaixo: Candidato 1 2 3 4 5 6 7 8 Salário (R$) 17.000 17.400 15.800 17.600 16.600 18.000 16.800 17.200 Idiomas Inglês Francês Italiano Chinês Inglês Espanhol Russo Japonês Inglês Francês Alemão Chinês Inglês Italiano Japonês Inglês Espanhol Alemão Francês Alemão Russo Japonês Espanhol Italiano Russo Chinês Francês Espanhol Italiano Japonês Formule um modelo que ajude a selecionar os candidatos que satisfaçam as necessidade comerciais da empresa, e que proporcionem à mesma o menor custo com a folha de pagamento. 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 11 MODELO MODEL: [Z] MIN = 17 * X1 + 17.4 * X2 + 15.8 * X3 + 17.6 * X4 + 16.6 * X5 + 18 * X6 + 16.8 * X7 + 17.2 * X8; [ING] X1 + X2 + X3 + X4 + X5 >= 1; [FRA] X1 + X3 + X6 + X8 >= 1; [ITA] X1 + X4 + X7 + X8 >= 1; [CHI] X1 + X3 + X7 >= 1; [ESP] X2 + X5 + X7 + X8 >= 1; [RUS] X2 + X6 + X7 >= 1; [JAP] X2 + X4 + X6 + X8 >= 1; [ALE] X3 + X5 + X6 >= 1; @BIN(X1); @BIN(X2); @BIN(X3); @BIN(X4); @BIN(X5); @BIN(X6); @BIN(X7); @BIN(X8); END 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 11 Exemplo 4 – Localização de antenas celulares Formular os modelo de Programação Inteira para determinar a solução para o problema de localização de antenas de rádio em sistemas de telefonia celular. MODELO     1 1 1 . : 1 1,..., 1,..., 0,1 1,..., 1,..., 0,1 1,..., n j j j n ij ij j m i ij j i ij j Min z c y s a a x i m d x Q y j n x i m j n y j n                      onde jc é o custo de instalação da antena  1,...,  j n  ; Q é a capacidade de atendimento à demanda de uma antena; id demanda da região  1,...,  i m  ; o parâmetro 1 ij a  se a antena  1,...,  j n  dá cobertura à região  1,...,  i m  e 0 ij a  em caso contrário. A variável   jy  0,1 indica se a antena  1,...,  j n  será instalada; a variável   ijx  0,1 indica que a demanda da região  1,...,  i m  será atendida pela antena  1,...,  j n  . 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 11 Exemplo 5 – Programação das provas finais Formular o modelo de Programação Inteira para determinar o programa de provas finais de um curso, considerando que cada aluno tem um elenco de provas a realizar, nenhum aluno pode ter duas provas no mesmo dia, e o período de provas seja o mais curto possível. MODELO   1 1 1 . : 1 1,..., 1 1,..., 0,1 1,..., 1,..., e m n k ik i k n ik k ik jk i j ik Min z P x s a x i m x x k n A A x i m k n                       onde kP é uma penalidade crescente, associada a alocação de uma prova no dia k ; a variável   0,1 ik x  indica se a prova da disciplina  1,...,  i m  será alocada no dia  1,...,  k n  ; e, finalmente, iA e j A são os conjuntos de alunos matriculados, respectivamente, nas disciplinas   , 1,..., i j m  . 16 Programação Linear Inteira – Formulação de Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 11 F I M (© 2020 Prof. Sérgio Mayerle)