Lingo - Modelos de Programacao Linear e Nao-Linear - Principais Comandos e Sets

1 Profª Dra Stella Jacyszyn Bachega Solução Computacional 2 Pressuposto Todos os tempos entre atendimentos são distribuídos de forma independente e idêntica de acordo com uma distribuição exponencial isto é o processo de entrada é de Poisson que todos os tempos de atendimento sejam distribuídos de forma independente e idêntica de acordo com outra distribuição exponencial e que o número de atendentes seja s qualquer inteiro positivo MMs Lingo O que é o LINGO LINGO Linear INteractive and General Optimizer Otimizador Linear Interativo e Geral Ferramenta simples para utilizar o poder da otimização linear ou nãolinear para formular problemas grandes concisamente resolvêlos e analisar a solução Modelos disponíveis Programação Linear Programação Nãolinear Programação Estocástica Programação Inteira 3 Principais Comandos Explicação Comando Usado para designar variáveis inteiras GINVAR Usado para designar variáveis binárias BINVAR Usado para designar que a variável é livre FREEVAR Usado para designar os valores pelos quais a variável VAR é limitada inferiormente e superiormente Aqui temos que LI é valor mínimo da variável e LS é o valor máximo ou seja LI VAR LS BNDLIVARLS Retorna o número de elementos no setname de um conjunto set SIZEsetname Permite envolver um índice ao final de um conjunto set e continuar indexando até o outro final do conjunto set WRAPINDEX LIMIT Comando que solicita minimizar uma função MIN Comando que solicita maximizar uma função MAX Símbolo para escrever uma linha de comentário Principais Comandos Seção SETS grupos de objetos relacionados SETS setname memberlist variablelist ENDSETS onde setname é o nome que você escolhe para designar o grupo de objetos memberlist lista de membros que constituem o grupo de objetos variablelist lista de variáveis ou constantes que tem as mesmas características do grupo de objetos Quando há mais de uma variável ou constante elas devem ser separadas por vírgula Obs os colchetes indicam que essas informações são opcionais 4 Principais Comandos SETS grupos de objetos relacionados Exemplos de lista de membros de um grupo de objetos Membros do grupo Exemplo Lista de Membros na forma implícita 1 2 3 4 5 15 1n TR3 TR4 TR204 TR3TR204 StringMStringN MON TUE WED THU FRI MONFRI dayMdayN OCT NOV DEC JAN OCTJAN monthMmonthN OCT2001 NOV2001 DEC2001 OCT2001DEZ2001 monthYearMmonthYearN Principais Comandos SETS grupos de objetos relacionados Demais comandos que podem ser usados com SETS SUMsetname setindexlist condqualifier expression Retorna a soma da expressão considerando o set setname FOR setname setindexlist condqualifier explist Gera as expressões contidas no explist para todos os membros do set setname O FOR trata de um comando de repetição MAXsetname setindexlist condqualifier expression Retorna a valor máximo da expressão considerando o set setname MINsetname setindexlist condqualifier expression Retorna a valor mínimo da expressão considerando o set setname PROD setname setindexlist condqualifier expression Retorna o produto da expressão considerando o set setname 5 Alguns comandos do LINGO para funções de probabilidade PEBA X é a probabilidade Erlang de um sistema de atendimento estar ocupado com X atendentes e uma carga de chegada de A com fila infinita permitida O resultado de PEB pode ser interpretado como a fração do tempo em que todos os servidores estão ocupados ou a fração de clientes que deve esperar em fila PELA X é a probabilidade Erlang de perda em um sistema com X atendentes e uma carga de chegada de A sem fila permitida O resultado de PEL pode ser interpretado como a fração de tempo em que todos os atendentes estão ocupados ou a fração de clientes perdidos devido a todos os atendentes estarem ocupados quando ocorre a chegada LINGO Alguns comandos do LINGO para funções de probabilidade PFSA X C retorna o número esperado de clientes que estão aguardando por ou em reparo em um sistema de atendimento com fonte finita de Poisson com X atendentes em paralelo C clientes e uma carga limitada A RANDSEED retorna um número pseudoaleatório entre 0 e 1 dependendo deterministicamente de uma semente LINGO 6 Principais Comandos SETS grupos de objetos relacionados Demais comandos que podem ser usados com SETS Seção Data Usada para ler os valores das constantes definidas na seção SETS Finalizase a seção com ENDDATA Principais Comandos Observações Devese colocar no final de cada comando Não há necessidade de digitar END ao final do modelo Os nomes das variáveis têm que ser iniciados por letras e podem ser seguidos por qualquer caractere alfanumérico É possível dar nome às linhas das restrições para isto basta digitar o nome da restrição entre colchetes ex Rest1 7 Determinação do número ótimo de atendentes em uma fila MMs A empresa Atraso Certo Ltda necessita saber a quantidade de atendentes que deve ser mantida para atender os seus clientes de forma a minimizar seu custo total por hora Alguns dados já foram determinados pela empresa 120 clientes por hora µ 120 clientes por hora Custo de um atendente por hora 2000 Custo de espera do cliente por hora 4800 LINGO LINGO Escreva o texto no início Número ótimo de atendentes em uma fila MMS Número ótimo de atendentes em uma fila MMS Quais são os valores das constantes e os atributos a serem considerados Seção DATA DATA ENDDATA 8 LINGO Quais são os valores das constantes Taxa total de chegada dos clientes clienteshora LAMBDA 120 Taxa de atendimento de um atendente padrão clienteshora MU 120 Custo de um atendente h CA 20 Custo do tempo do cliente h CT 48 Finalizar com ENDDATA LINGO Fator de utilização UTIL LAMBDA MU Quantidade esperada no sistema QS UTILATENDENTES UTILPEBUTIL ATENDENTES UTIL A necessidade é de pelo menos um número mínimo de atendentes ATENDENTES UTIL Número de atendentes deve ser um inteiro GINATENDENTES Minimizar o custoh total MIN CAATENDENTES CTQS Número ótimo de atendentes em uma fila MMs DATA Taxa total de chegada dos clientes LAMBDA 120 Taxa de atendimento de um atendente padrão clienteshora MU 120 Custo de um atendente h CA 20 Custo do tempo do cliente h CT 48 ENDDATA Fator de utilização UTIL LAMBDAMU Quantidade esperada no sistema quantidade esperando quantidade em atendimento PEB probabilidade de todos os atendentes estarem ocupados QS UTILATENDENTES UTILPEBUTIL ATENDENTES UTIL A necessidade é de pelo menos um número mínimo de atendentes ATENDENTES UTIL Número de atendentes deve ser um inteiro GINATENDENTES Minimizar o custoh total MIN CAATENDENTES CTQS 10 LINGO Até o momento os sistemas de filas foram considerados como uma única instalação de atendimento com um ou mais atendentes Entretanto sistemas de filas encontrados em estudos de PO são algumas vezes na realidade redes de filas Redes de Filas redes de instalações de atendimento onde clientes devem receber atendimento em algumas ou todas essas instalações Ex pedidos que estão sendo processados em uma ferramentaria devem ser direcionados por meio de uma sequência de grupos de máquinas instalações de atendimento Redes de Filas 11 Propriedade da equivalência Suponha que uma instalação de atendimento com s atendentes e uma fila infinita tenha uma entrada de Poisson com parâmetro e a mesma distribuição exponencial de tempo de atendimento com parâmetro µ para cada atendente o modelo MMs em que sµ Então a saída de estado estável dessa instalação de atendimento também é um processo de Poisson com parâmetro Redes de Filas Implicações da Propriedade da equivalência A implicação crucial desse fato para redes de filas é que se esses clientes tiverem de ir a outra instalação de atendimento para outros atendimentos essa segunda instalação também terá uma entrada de Poisson Com uma distribuição exponencial de tempos de atendimento a propriedade de equivalência também será válida para essa instalação que poderá então fornecer uma entrada de Poisson para uma terceira instalação etc Redes de Filas 12 Os sistemas de filas infinitas em série não são as únicas redes de filas em que o modelo MMs pode ser usado para analisar cada instalação de atendimento independentemente das demais Outro tipo proeminente de rede com essa propriedade uma solução em forma de produto é a rede de Jackson nome dado em homenagem ao responsável por ter caracterizado a rede pela primeira vez e ter demonstrado que essa propriedade era válida As características de uma rede de Jackson são as mesmas supostas para o sistema de filas infinitas em série exceto que agora os clientes visitam as instalações em ordens diferentes sendo possível que eles não visitem todas elas Para cada instalação seus clientes que chegam provêm tanto de fora do sistema de acordo com um processo de Poisson quanto de outras instalações Redes de Jackson Uma rede de Jackson é um sistema de m instalações de atendimento onde a instalação i i 1 2 m tem 1 Uma fila infinita 2 Clientes provenientes de fora do sistema de acordo com um processo de entrada de Poisson com parâmetro ai 3 si atendentes com uma distribuição exponencial de tempos de atendimento com parâmetro µi Redes de Jackson 13 Um cliente deixando a instalação i é direcionado para a instalação j j 1 2 m com a probabilidade pij ou deixa o sistema com probabilidade Redes de Jackson Qualquer rede desse tipo possui a seguinte propriedade fundamental Sob condições de estado estável cada instalação j j 1 2 m em uma rede de Jackson se comporta como se fosse um sistema de filas MMs independente com taxa de chegada Redes de Jackson i taxa de partida bem como a taxa de chegada para todos os clientes usando a instalação i pij proporção de clientes partindo da instalação i que em seguida vão para a instalação j ipij taxa na qual os clientes da instalação i chegam na instalação j 14 Determinação do número esperado de clientes no sistema e do tempo esperado no sistema em uma Rede de Jackson A empresa Job Shop Ltda deseja saber o número esperado de peças e o tempo de espera dessas peças no sistema produtivo Há três instalações onde os processamentos podem ser realizados seguindo as características de um ambiente job shop O número de operadores a taxa de atendimento e a taxa de chegada externa estão no quadro a seguir LINGO Taxa de chegada externa peças por hora Taxa de atendimento peças por hora Número de atendentes Instalação 1 10 1 INST1 4 10 2 INST2 3 10 1 INST3 As probabilidades das peças seguirem a rota de uma instalação para outra encontramse no quadro a seguir Encontre os dados solicitados por meio do uso do software LINGO LINGO INST3 INST2 INST1 Instalação 04 01 0 INST1 04 0 06 INST2 0 03 03 INST3 15 Comando usado do LINGO para funções de probabilidade PEBA X é a probabilidade Erlang de um sistema de atendimento estar ocupado com X atendentes e uma carga de chegada de A com fila infinita permitida O resultado de PEB pode ser interpretado como a fração do tempo em que todos os servidores estão ocupados ou a fração de clientes que deve esperar em fila LINGO LINGO Escreva o texto no início Modelo de uma rede de Jackson Modelo de uma rede de Jackson Quais são as variáveis e as constantes SETS setname memberlist variablelist ENDSETS SETS INSTALACAO NS MU LEXT LAMBDA N UTILIZACAO INSTXINST INSTALACAO INSTALACAO P ENDSETS 16 LINGO Quais são os valores das constantes e os atributos a serem considerados Seção DATA DATA ENDDATA Valores Nome da instalação número de atendentes taxa de atendimento e taxa de chegada externa INSTALACAO NS MU LEXT INST1 1 10 1 INST2 2 10 4 INST3 1 10 3 LINGO Valores Probabilidade P 0 1 4 6 0 4 3 3 0 Taxa total de chegada em cada instalação FOR INSTALACAO I LAMBDA I LEXT I SUM INSTALACAO J LAMBDA J P I J Utilização de cada instalação FOR INSTALACAO I UTILIZACAO I LAMBDA I MU I Finalizar com ENDDATA 17 LINGO Número de clientes esperados em determinada Instalação N I UTILIZACAO I NS I UTILIZACAO I PEB UTILIZACAO I NS I UTILIZACAO I Número esperado de clientes no sistema L SUM INSTALACAO I N I Tempo esperado no sistema WTOT LSUM INSTALACAO LEXT LINGO 18 LINGO LINGO Options Configure o LINGO Local optimal solution found Objective value 1040000 Objective bound 1040000 Infeasibilities 0000000 Extended solver steps 3 Total solver iterations 2169 Elapsed runtime seconds 059 Model Class MINLP Total variables 2 Nonlinear variables 1 Integer variables 1 Total constraints 3 Nonlinear constraints 1 Total nonzeros 5 Nonlinear nonzeros 1 20 Determine o número ótimo de atendentes em uma fila MMs Uma empresa deseja determinar a quantidade de atendentes que deve ser contratada para atender os seus clientes O intuito é minimizar seu custo total por hora Os dados já coletados pela empresa são Custo de espera do cliente por hora 3200 Custo de um atendente por hora 1600 µ 64 clientes por hora 64 clientes por hora Encontre os resultados e analise o relatório gerado Pratique Bibliografia Básica ARENALES M ARMENTANO V MORABITO R YANASSE H H Pesquisa Operacional para cursos de engenharia Rio de Janeiro Campos 2006 HILLIER F S LIEBERMAN G J Introdução à Pesquisa Operacional São Paulo McGrawHill 2006 TAHA H A Pesquisa Operacional uma visão geral São Paulo Pearson Prentice Hall 2008 21 Bibliografia Complementar ANDRADE E L Introdução à Pesquisa Operacional Métodos e Modelos para Análise de Decisões Rio de Janeiro LTC 2004 COLIN E C Pesquisa Operacional 170 aplicações em Estratégia Finanças Logística Produção Marketing e Vendas Rio de Janeiro LTC 2007 LACHTERMACHER G Pesquisa operacional na tomada de decisões Rio de Janeiro Campus 2007 MOREIRA D A Pesquisa Operacional Curso Introdutório São Paulo Thomson Learning 2007 PRADO D Teoria das Filas e da Simulação 3ª ed Editora INDG Tecnologia e Serviços Ltda 2006