Programação Inteira: Conceitos e Métodos

1 Pesquisa Operacional II 6 Programação Inteira Faculdade de Engenharia Eng Celso Daniel Engenharia de Produção Profa Dra Lilian Kátia de Oliveira Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira São problemas de programação matemática em que a função objetivo bem como as restrições são lineares porém uma ou mais variáveis de decisão podem apenas assumir valores inteiros Esse problema pode apresentar dois tipos básicos Programação Inteira Total onde todas as variáveis de decisão são do tipo inteiro Programação Inteira Mista onde apenas uma parte das variáveis são do tipo inteiro enquanto outras são do tipo real 2 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira A primeira idéia que pode vir à mente é resolver o problema como se fosse um problema de programação linear e arredondar os valores ótimos encontrados para cada uma das variáveis de decisão inteiras Para problemas de grande porte isto geralmente gerará uma solução aceitável próxima do ótimo real sem a violação de nenhuma das restrições Para problemas menores esse tipo de procedimento poderá nos levar a soluções inviáveis ou não ótimas Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira 1 2 1 1 2 1 2 1 2 2 1 2 1 2 Otimizar sujeito a são inteiros n n n m m n n z f x x x g x x x b g x x x b b g x x x x x x 1 2 1 1 2 2 1 2 1 1 2 2 1 onde n n n n i i in n f x x x c x c x c x g x x x a x a x a x i n 3 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira Problema Relaxado A todo problema de programação inteira está associado um problema com a mesma funçãoobjetivo e as mesmas restrições com exceção da condição de variáveis inteiras A esse problema se dá o nome de Problema Relaxado Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira Solução Gráfica 1 2 3 4 5 1 2 3 4 5 1 2 1 2 1 2 1 2 1 2 1 2 1 2 Max 18 6 sa 5 428 100 800 20 6 142 30 10 135 3 0 0 e inteiros x x x x x x x x x x x x x x 4 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira Solução Gráfica x2 x1 528 574 Solução Ótima para PL Relaxado 1 2 1 2 1 2 1 2 1 2 1 2 1 2 Max 18 6 sa 5 428 100 800 20 6 142 30 10 135 3 0 0 e inteiros x x x x x x x x x x x x x x Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira Solução Gráfica Solução Ótima para PL Relaxado 528 574 Solução Ótima para Problema Inteiro 6 3 Solução Aproximada do PL Relaxado Ótimo 5 5 x2 x1 528 574 5 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira PL Relaxado Em um problema de MAXIMIZAÇÃO o valor ótimo da funçãoobjetivo do Problema Relaxado sempre representa um limite superior ao respectivo Problema Inteiro Em um problema de MINIMIZAÇÃO o valor ótimo da funçãoobjetivo do Problema Relaxado sempre representa um limite inferior ao respectivo Problema Inteiro Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira PL Relaxado Nenhum ponto inteiro vizinho ao ponto ótimo do problema relaxado é necessariamente viável Mesmo que um dos vizinhos seja viável Não é necessariamente o ponto ótimo inteiro Não é obrigatoriamente uma solução aceitável x2 x1 Solução Ótima para ProgInteira Solução Ótima para PL Relaxado 6 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Programação Inteira Solução por Enumeração Uma idéia que pode resultar em uma solução para um problema de programação inteira é a de se enumerar todas as possíveis soluções De forma exaustiva o valor da funçãoobjetivo é calculado para todas as soluções viáveis e é escolhido aquele que apresente o maior valor no caso de maximização ou o menor valor no caso de minimização Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira O problema com essa tática de solução está no fato de que ela só consegue ser aplicada a problemas pequenos O número de combinações possíveis de soluções cresce de forma exponencial isto é de forma muito rápida Ex Um PLI com 100 variáveis de decisão do tipo binárias assumem 0 ou 1 terá até 2100 soluções viáveis isto é 127 x 1030 soluções possíveis Programação Inteira Solução por Enumeração 7 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Algoritmo BranchandBound é mais utilizado atualmente para resolução de problemas do tipo PLI ou PLI misto É uma metodologia geral para solução de PLI e PLI misto e existem diversas variantes para tratar diversos tipos de problemas específicos A idéia geral é a de se dividir o conjunto de soluções viáveis em subconjuntos sem interseções entre si calculandose os limites superior e inferior para cada subconjunto e então eliminando certos subconjuntos de acordo com regras préestabelecidas Programação Inteira Algoritmo BranchandBound Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Comparativamente ao PL correspondente o PI levará muito mais tempo para obter um valor ótimo Isso está ligado ao fato que diversos problemas de PL são resolvidos sucessivamente para se obter a solução de um PI Se o problema for interrompido no meio do processo uma solução aproximada do problema inteiro pode ser gerada Programação Inteira Algoritmo de BranchandBound 8 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira A divisão do problema é interrompida quando uma das condições a seguir é satisfeita Essas condições são chamadas de testes de sondagem TS TS 1 O problema relaxado é infactível TS 2 A solução ótima do problema relaxado é inteira TS 3 O valor de qualquer solução factível do problema relaxado é pior que o valor da melhor solução factível atual solução incumbente Quando uma dessas três condições ocorre o subproblema pode ser descartado sondado pois todas as suas soluções factíveis estão implicitamente enumeradas Programação Inteira Algoritmo de BranchandBound Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira 1 2 1 2 1 2 1 2 Max 21 11 7 4 13 0 inteiros x x s a x x x x x x b a Ótimo 33 Ótimo 39 Exemplo Algoritmo BranchandBound PPI PPL Na Figura a têmse os pontos que representam as soluções factíveis do problema todos os pontos inteiros que satisfazem as restrições O problema de programação linear PPL obtido ao desconsiderarmos as restrições de integralidade das variáveis inteiras é conhecido como a relaxação linear do PPI ver Figura b 9 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Resolvendo o problema relaxado temse que Valor ótimo da solução 39 Valores das variáveis x1186 e x20 Logo o valor de x1 não é inteiro então dividimos o problema em dois subproblemas um onde consideramos o valor de x1 2 que vamos chamar de subproblema A outro consideramos x1 1 chamado de subproblema B Z39 x1186 x20 Exemplo Algoritmo BranchandBound Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Ótimo 375 Infactível A B Suproblema A Subproblema B 1 2 1 2 1 1 2 Max 21 11 7 4 13 2 0 x x s a x x x x x 1 2 1 2 1 1 2 Max 21 11 7 4 13 1 0 x x s a x x x x x Exemplo Algoritmo BranchandBound 10 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Não encontramos solução factível ao resolver o problema A então aplicando o TS1 podemos eliminálo Resolvendo o subproblema B temos Z 375 x1 1 e x2 15 Agora x2 não é inteiro logo particionamos o problema em dois considerando o subproblema C com a variável x21 e o subproblema D com x2 2 Z39 x1186 x20 Z375 x11 x215 x12 x11 TS1 A B Exemplo Algoritmo BranchandBound Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Suproblema C Subproblema D 1 2 1 2 1 2 1 2 Max 21 11 7 4 13 1 1 0 x x s a x x x x x x 1 2 1 2 1 2 1 2 Max 21 11 7 4 13 1 2 0 x x s a x x x x x x Ótimo 37 Ótimo 32 C D Exemplo Algoritmo BranchandBound 11 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Z39 x1186 x20 Z375 x11 x215 x12 x11 TS1 Z37 x1071 x22 x22 x21 A D C B Z32 x11 x21 TS2 Exemplo Algoritmo BranchandBound Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira A solução do subproblema C é igual a 32 x11 e x21 as duas variáveis são inteiras logo considerando o TS2 este problema pode ser sondado Resolvendo o subproblema D temos Z37 x1071 e x22 note que a variável x1 novamente não é inteira então particionamos o subproblema gerando dois novos subproblemas como mostramos a seguir Exemplo Algoritmo BranchandBound 12 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Suproblema E Subproblema F 1 2 1 2 1 2 1 1 2 Max 21 11 7 4 13 1 2 0 0 x x s a x x x x x x x 1 2 1 2 1 2 1 1 2 Max 21 11 7 4 13 1 2 1 0 x x s a x x x x x x x Infactível Ótimo 3575 3575 F E Exemplo Algoritmo BranchandBound Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Z39 x1186 x20 Z375 x11 x215 x12 x11 TS1 Z37 x1071 x22 x22 x21 A D C B Z32 x11 x21 TS2 x11 x10 F E Z3575 x10 x2325 TS1 Exemplo Algoritmo BranchandBound 13 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira O problema F é infactível logo podemos usar TS1 e eliminálo O subproblema E tem solução igual a 3575 e x10 e x2325 Suproblema G Subproblema H 1 2 1 2 1 2 1 2 1 2 Max 21 11 7 4 13 1 2 0 3 0 x x s a x x x x x x x x 1 2 1 2 1 2 1 2 1 2 Max 21 11 7 4 13 1 2 0 4 0 x x s a x x x x x x x x Exemplo Algoritmo BranchandBound Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Z39 x1186 x20 Z375 x11 x215 x12 x11 TS1 Z37 x1071 x22 x22 x21 A D C B Z32 x11 x21 TS2 x11 x10 F E Z3575 x10 x2325 TS1 x24 x23 H G Z33 x10 x23 TS1 TS2 Exemplo Algoritmo BranchandBound 14 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Resolvendo o subproblema G obtemos Z33 x10 e x23 logo a solução é inteira portanto aplicando o TS2 este problema pode ser sondado O subproblema H não tem solução factível e também pode ser sondado por TS1 Temos que nenhum nó pode ser ramificado logo a melhor solução inteira encontrada é dada pelo problema G e é a solução ótima do problema Na resolução do exemplo através do método BB podemos observar que muitas soluções não precisaram ser avaliadas explicitamente Isso fica mais claro quando se resolve problemas maiores Exemplo Algoritmo BranchandBound Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira A solução obtida num problema PLI ou PLI misto contém menos informações que o PL correspondente Algumas diferenças são Inexistência de análise de sensibilidade Esta análise deve ser efetuada alterandose o problema e obtendose nova solução Não provê informação similar ao preço de sombra Muitos softwares que realizam programação inteira são parte integrante de pacotes de PL e produzem análise de sensibilidade independente desta não ter valor no âmbito de programação inteira Nestes casos devemos desconsiderar estas análises Programação Inteira Algoritmo de BranchandBound 15 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Usando Solver do Excel Definindo Variáveis Inteiras e Binárias Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Lindo Variáveis Inteiras e Binárias Os comandos adicionais abaixo são colocados após o comando END ao final das restrições FREE Variável Remove os limites de não negatividade imposta a todas as variáveis por default GIN Variável Faz a Variável uma variável inteira geral INT Variável Faz a Variável uma variável inteira binária 16 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Problema de Orçamento de Capital Caso LCL Tecnologia SA Capital Requerido em mil R Proj NPV8 mil R Ano 1 Ano 2 Ano 3 Ano 4 Ano 5 1 10599 70 15 0 20 20 2 12890 80 20 25 15 10 3 13614 90 20 0 30 20 4 11738 50 30 40 0 20 Capital Disponível 200 70 70 70 70 A LCL Tecnologia SA tem que planejar seus gastos em PD A empresa préselecionou 4 projetos e deve escolher dentre esses quais deve priorizar em função de restrições orçamentárias Os dados relevantes encontramse na tabela abaixo Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Caso LCL Tecnologia SA Variáveis de Decisão Função Objetivo Maximizar o somatório NPV 1 se o projeto for selecionado 1234 0 se o projeto não for selecionado i i x i i 1 2 3 4 Max 10599 12890 13614 11738 x x x x 17 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Restrições Orçamentárias 1 2 3 4 1 2 3 4 2 4 1 2 3 1 2 3 4 70 80 90 50 200 Ano 1 15 20 20 30 70 Ano 2 25 40 70 Ano 3 20 15 30 70 Ano 4 20 10 20 20 70 Ano 5 x x x x x x x x x x x x x x x x x Caso LCL Tecnologia SA Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Caso LCL Tecnologia SA O Modelo 1 2 3 4 1 2 3 4 1 2 3 4 2 4 1 2 3 1 2 3 4 Max 10599 12890 13614 11738 sa 70 80 90 50 200 15 20 20 30 70 25 40 70 20 15 30 70 20 10 20 20 70 x x x x x x x x x x x x x x x x x x x x x 01 1234 ix i 18 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Caso LCL Tecnologia SA Solver do Excel Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Caso LCL Tecnologia SA Solver do Excel 19 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Caso LCL Tecnologia SA Solver do Excel Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Variáveis Binárias e Condições Lógicas As variáveis binárias também se prestam a selecionar alternativas que sejam condicionais No exemplo anterior imagine que não mais de um dos projetos 1 3 e 4 pudesse ser selecionado Deveríamos então adicionar Se apenas um dos projetos e apenas um dos projetos 1 2 e 4 tivesse que ser escolhido obrigatoriamente deveríamos incluir 1 3 4 1 x x x 1 2 4 1 x x x 20 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Imagine agora que o projeto 1 dependa de uma tecnologia que deve ser desenvolvida pelo projeto 2 isto é o projeto 1 só pode ser aprovado se e somente se o projeto 2 for aceito Deveríamos então incluir 1 2 1 2 1 2 1 2 1 2 0 0 nenhum dos projetos aceitos 1 1 ambos os projetos aceitos 0 0 1 apenas o projeto 2 foi aceito 1 0 inviável x x x x x x x x x x Variáveis Binárias e Condições Lógicas Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Tipo 1 Tipo 2 Tipo 3 Total Disponível Montagem 2hunid 3hunid 25hunid 600h Pintura 3hunid 2hunid 25hunid 500h Lucro Unitário R50 R60 R65 Preparação R5000 R4000 R3000 A LCL Equipamentos SA produz três tipos de furadeiras que necessitam de tempos diferentes na linha de montagem Para que cada tipo de furadeira seja fabricada um custo de preparação da fabrica é incorrido Suponha que todas as furadeiras do mesmo tipo serão produzidas de uma só vez apenas uma preparação por tipo Abaixo os dados relevantes à análise do problema Caso LCL Equipamentos SA 21 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Variáveis de Decisão Função Objetivo Quantidade a ser produzida do produto 123 1 se 0 123 0 se 0 i i i i x i i x y i x Caso LCL Equipamentos SA Variáveis Binárias 1 2 3 1 2 3 Max 50 60 65 5000 4000 3000 x x x y y y Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Restrições de Produção Restrições de ligação de Variáveis 1 2 3 1 2 3 2 3 25 600 3 2 25 500 x x x x x x 1 1 2 2 3 3 600 600 600 600 é um nº que é grande o suficiente x y x y x y Obs Caso LCL Equipamentos SA Variáveis Binárias 22 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Caso LCL Equipamentos SA O Modelo 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 2 3 3 Max 50 60 65 5000 4000 3000 sujeito a 2 3 25 600 3 2 25 500 600 600 600 0 123 01 123 i i x x x y y y x x x x x x x y x y x y x i y i Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Caso LCL Equipamentos SA Variáveis Binárias B7B10 23 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Caso LCL Equipamentos SA Variáveis Binárias Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Caso LCL Equipamentos SA Variáveis Binárias 24 Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Exercício Resolver o problema abaixo utilizando o algoritmo BranchandBound 1 2 1 2 1 2 1 2 Max 3 3 sa 4 12 6 4 24 0 e inteiros x x x x x x x x Pesquisa Operacional II Profa Dra Lilian Kátia de Oliveira Referências Bibliográficas LACHTERMACHER G Pesquisa operacional na tomada de decisão modelagem em Excel 2ª edição revista e atualizada Editora Campus 2004 HILLIER F S Introdução à pesquisa operacional Rio de Janeiro Editora Campus 1988 GOLDBARG M C e LUNA H P Otimização combinatória e programação linear modelos e algoritmos 2ª edição Editora Campus Rio de Janeiro 2005