Baixe Apostila e outras Notas de estudo em PDF para Informática, somente na Docsity! Pesquisa Operacional Professor José Arnaldo Barra Montevechi montevechimunifei.edu.br The 6.15% 4 º Universidade Federal de Itajubá Instituto de Engenharia de Produção e Gestão 2007 Curso de Pesquisa Operacional 2 1. PESQUISA OPERACIONAL: HISTÓRIA E CONCEITOS 1.1 Introdução O objetivo do curso é apresentar alguns METODOS MATEMÁTICOS essenciais à Pesquisa Operacional (PO). Este capítulo pretende dar a origem e as idéias fundamentais da PO. Infelizmente, um curso introdutório de PO não pode responder completamente as perguntas: a) O que deve (o aluno) aprender sobre PO se pretende ser um economista (dirigente, gerente, administrador) mais que um especialista? b) O que deve (o aluno) aprender sobre PO tendo em vista que deseja aplicá-la a problemas reais? No contexto destas duas perguntas o objetivo principal do curso é: 1) Introduzir as idéias mais importantes em PO, as quais são fundamentais e permanentes. 2) Dar o curso em nível que o aluno possa entender e apreciar a força e as limitações inerentes a PO. 3) Preparar e motivar futuros especialistas em PO. 4) Apresentar e aplicar alguns métodos de PO (METODOLOGIA). 1.2 Notas Históricas Desde o advento da primeira revolução industrial o mundo tem apresentado um notável desenvolvimento e crescimento em tamanho e complexidade de suas organizações. Os caminhos da PO podem ser traçados a muitas décadas atrás, quando foi aplicada a administração cientifica às organizações. Como a tendência natural é aumentar a complexidade e a especialização das organizações, torna-se mais e mais dificil alocar seus recursos disponíveis pelas suas várias atividades de maneira a obter a melhor eficiência para a organização. Entretanto, o termo PO é geralmente atribuído aos serviços militares durante a Segunda Grande Guerra Mundial (1939). Os dirigentes militares chamaram equipes de cientistas para estudar problemas estratégicos e táticos associados com a defesa aérea e terrestre do pais. Seu objetivo era determinar a melhor utilização efetiva dos recursos militares limitados. Curso de Pesquisa Operacional 5 2. MÉTODO DA PESQUISA OPERACIONAL 2.1 Introdução Um estudo de PO consiste em construir um modelo da situação fisica. Um modelo de PO é definido como uma representação idealizada de um sistema organizacional. Este sistema pode já ser existente ou pode ainda ser uma idéia a espera de execução. No primeiro caso, o objetivo do modelo é analisar as operações do sistema para verificar sua performance. No segundo, o objetivo e identificar a melhor estrutura do futuro sistema. A complexidade de um sistema real resulta do grande número de variáveis que comandam as operações do sistema, embora um sistema real possa envolver um número substancial de variáveis, geralmente uma pequena fração destas variáveis domina as operações do sistema. Então, a simplificação do sistema real em termos de um modelo condensado, identificando apenas as variáveis dominantes e as relações entre elas, é o empregado. Exemplo 1: A fabricação de um produto experimenta certo número de operações desde o tempo de sua concepção pelo projetista, até chegar às mãos do consumidor. Após a aprovação do projeto, a ordem de produção é transmitida ao Departamento de Produção (DP), a qual requisita o material necessário do Departamento de Material (DM). O Departamento de Material satisfaz a requisição do seu estoque ou entra em ligação com o Departamento de Compras para comprar o material necessário para atender à requisição do DP. Após a fabricação do produto, o Departamento de Vendas, em conjunção com o Departamento de Marketing, assume a responsabilidade para distribuílo para os consumidores. Suponha que o objetivo é determinar o nível de PRODUÇÃO DA INDÚSTRIA. Observando o sistema vê-se que um grande número de variáveis influi diretamente no nível de produção. Segue alguns exemplos destas variáveis: a) DEPARTAMENTO DE PRODUÇÃO: Avaliar máquinas - horas, homens - hora, especificar a segiência de operações nas máquinas, números de itens defeituosos, razão de inspeção, etc. bt) DEPARTAMENTO DE MATERIAL: Avaliar o estoque de material, taxa média de saída e entrada de material, limitações de armazenagem. Curso de Pesquisa Operacional 6 c) DEPARTAMENTO DE MARKETING: Calcular as vendas, intensificar as campanhas promocionais, capacidade de distribuição de produtos, efeito dos produtos competitivos. Cada uma das variáveis acima afeta (direta ou indiretamente) o nível da produção. É uma tarefa ingrata tentar estabelecer relações explicitas entre estas variáveis e o nível de produção. Definindo o sistema em função de suas variáveis dominantes, ele pode ser representado por duas variáveis: 1º - Uma, representando a taxa de produção do item; 2º - Uma, representando sua razão de consumo. Para se determinar a taxa de produção, variáveis tais como avaliação máquina - hora, homem- hora, sequenciamento e avaliação do material devem ser consideradas no cálculo da taxa de produção. A razão de consumo é determinada em termos das variáveis associadas com o Departamento de Marketing. É fácil agora pensar em termos do sistema real adotado. Para a taxa de produção e consumo, podem-se estabelecer medidas para o excesso ou falta em estoque para um dado nível de produção. Um modelo abstrato do sistema pode então ser construido para balancear os custos do excesso ou falta de estoque. Por exemplo, pode-se estar interessado em determinar o nível de produção para um máximo de itens em estoque abaixo de certo limite. Em geral, não há regras fixas para determinar o nível de abstração citado. A validade do modelo representando o sistema depende principalmente da criatividade, insight, e imaginação dos analistas de PO e a equipe de trabalho no projeto. Embora não seja possível fixar regras acerca de como um modelo é construído, pode-se socorrer das presentes idéias sob os possíveis tipos de modelos de PO, suas estruturas e características gerais. Em um estudo de PO ocorrem normalmente as seguintes fases: 1. Formulação (ou definição) do problema; 2. Construção do modelo matemático; 3. Obtenção de uma solução a partir do modelo; 4. Teste do modelo e avaliação da solução obtida; 5 Estabelecimento de controle sobre a solução; Curso de Pesquisa Operacional 7 6. Implantação da solução. 2.2 Formulação do Problema Para se obter a solução de um problema, necessitasse antes formulá-lo de modo a tornar possível a pesquisa. Ao contrario dos exemplos que serão apresentados no decorrer do curso, a maioria dos problemas práticas são trazidos a uma equipe de pesquisa operacional de uma maneira vaga e imprecisa. Em consequência, o primeiro passo consiste em estudar o sistema e estabelecer de uma maneira bem definida o problema a ser considerado. Para isto vários elementos devem ser determinados exatamente tais como, os objetivos a atingir, as restrições que devem ser consideradas, o inter-relacionamento entre o setor a ser estudado e outros setores da organização, as possíveis linhas de ação alternativas, etc. Como todas as conclusões serão obtidas a partir desta formulação, esta fase tem importância capital para o estudo e a formulação inicial deve ser continuamente revista à luz dos novos dados obtidos durante as fases posteriores. Para determinação dos objetivos apropriados é necessário identificar a pessoa (ou pessoas) que toma as decisões relativas ao sistema em estudo, investigar seus objetivos e analisá-los a fim de estabelecer precisamente os principais objetivos a atingir a fim de que não sejam eliminadas metas ou alternativas de valor. Por sua natureza a pesquisa operacional preocupa-se em resolver os problemas da organização considerada como um todo e não somente os de alguns de seus setores. Por isto, os objetivos formulados devem ser aqueles de toda a organização, não significando, entretanto, que cada problema deva ser resolvido em um estudo de toda organização. Na realidade os objetivos fixados devem ser tão específicos quanto possíveis, desde que englobem as principais metas de tomada de decisão e mantenham um grau razoável de consistência com os objetivos de nível mais elevado da organização. Os efeitos laterais em outros setores da organização devem, então, ser considerados somente para verificar se estão coerentes com estes objetivos de nivel mais elevado. Para formular um problema precisa-se, pois, examinar os seguintes aspectos: 1. Quem toma a decisão? 2. Quais os objetivos? (A partir destas informações e de outros dados estabelecemos uma medida de desempenho, para avaliar as alternativas de ação). Curso de Pesquisa Operacional 10 variáveis de decisão. Em geral, a solução ótima do modelo é obtida quando os melhores valores correspondentes das variáveis de decisão são substituídos na PO, enquanto satisfazem as restrições. Os modelos matemáticos, em PO, podem ser especificados, geralmente, como determinar os valores das variáveis de decisão xj, j= 1,2,..,n a qual otimiza Z = f (xi, X>,..., Xn) sujeito a uma série de restrições. Na maioria dos sistemas 1eais, as restrições de não - negatividade aparece como condição natural. Antes da construção de um modelo matemático deve-se responder a 4 perguntas: 1) Qual é a medida de efetividade do objetivo? Isto é, como será expressa a solução do problema (em reais economizados, unidades vendidas, itens produzidos, etc.) 2) Quais são os fatores sob controle (variáveis controladas)? Isto é, quais aspectos do problema podem-se fazer alguma coisa? 3) Quais são os fatores não controlados (as variáveis não controladas)? Isto é, quais aspectos do problema têm-se de aceitar como dados? 4) Quais são as relações entre estes fatores e os objetivos? Isto é, pode esta relação ser expressa em forma de relações matemáticas que constituirão um modelo do problema? Otimização é geralmente tomada para significar a maximização ou minimização da FO. Analistas trabalhando no mesmo problema independentemente podem chegar a modelos diferentes e também a funções objetivo (FO) também diferentes. Por exemplo, o analista A pode preferir maximizar os lucros, enquanto o analista B pode preferir minimizar os custos. Os dois critérios não são equivalentes no sentido que com as mesmas restrições os dois modelos não devem produzir a mesma solução ótima. Isto pode ser mostrado claramente, enquanto o custo deve estar sob o controle imediato da organização no qual o estudo é feito, o lucro deve ser efetuado por fatores incontroláveis, tais como a situação de mercado ditada pelos competidores. Não se deve pensar que a solução ótima do modelo é a melhor solução do problema. Ela é a melhor somente se o critério adotado pode ser justificado como verdadeiro para toda organização. Na prática, torna-se muito dificil incluir todos os objetivos (possibilidades conflitantes) num critério simples (singular), pois isto pode resultar numa função matemática complexa para a qual nenhuma solução técnica pode ser prontamente obtida, porque alguns objetivos são também inatingíveis para serem quantificados. Curso de Pesquisa Operacional 11 Por exemplo, na determinação da política do nível ótimo de estoque, o verdadeiro objetivo deve incluir os objetivos (metas) conflitantes dos departamentos de produção, material, vendas e finanças. Quando o critério objetivo do modelo representa algum, mas não todos os aspectos conflitantes, chamam de uma solução sub - ótima, e que pode não ser a melhor para a organização como um todo. Após o modelo matemático ser construído, pode ser necessário simplificá-lo para ser tratado analiticamente. Algumas simplificações comuns incluem: a) Transformar variáveis discretas em contínuas; b) Linearizar funções não lineares; c) Eliminar algumas das restrições. 2.4 Obtenção de uma Solução a partir do Modelo Em modelos matemáticos, isto e, feito usando técnicas de otimização bem definidas, o modelo é dito de solução ótima. Se modelos de simulação ou heurísticos são usados, o conceito de solução ótima não é bem definido e a solução neste caso é usada para obter soluções aproximadas do sistema. Como um modelo é mais uma representação ideal do que exata, só pode-se afirmar que a solução ótima para o modelo será provavelmente a melhor possível para o problema real, devido aos fatores imponderáveis e as incertezas associadas ao problema. 2.5 Teste do Modelo e avaliação da Solução obtida Uma das primeiras lições da PO, é que não é geralmente suficiente confiar somente na intuição. Isto se aplica não somente na obtenção da solução de um problema, como também na avaliação do modelo que foi formulado para representar este problema. O critério indicado para julgar a validade de um modelo é verificar se ele prediz ou não os efeitos relativos das linhas de ação alternativas com suficiente precisão de maneira a permitir uma satisfatória decisão. Devido à dificuldade de comunicar e relacionar todos os aspectos e sutilezas de um problema operacional complexo existe a possibilidade que a equipe de pesquisas operacionais ou não tenha considerado todos os aspectos relevantes da situação ou não os tenha interpretado apropriadamente. Antes de aplicar testes mais elaborados é conveniente verificar se o modelo não apresenta erro. Um novo exame na formulação do problema e sua comparação com o modelo podem Curso de Pesquisa Operacional 12 revelar alguns desses erros. Outra verificação muito usada consiste em verificar se todas as expressões matemáticas estão dimensionalmente corretas. Finalmente, ou a equipe de PO, ou o pessoal que deverá tomar decisões podem observar detalhes na solução obtida que surgiram particulares omissões ou erros no modelo. Outros procedimentos mais sistemáticos podem ainda ser empregados. 2.6 Estabelecimento de controle sobre a Solução Quando uma solução for usada repetidamente, esta solução só permanecerá válida para o problema real enquanto o modelo respectivo permanecer válido. Entretanto, as condições variam constantemente no caso real. Em consequência, se essas variações invalidarem o modelo, é vital que isto seja verificado tão cedo quanto possível de maneira que o modelo, sua solução e resultante linha de ação possam ser convenientemente modificados. Assim sendo, sempre que uma solução e resultante estratégia para uma ação futura são aplicadas repetidamente, esta solução deve ser mantida sob controle. Este controle é feito identificando-se os parâmetros críticos, determinando-se estatisticamente as variações relevantes nesses parâmetros e finalmente ajustando a solução e consequente linha de ação sempre que uma variação é observada. 2.7 Implantação da solução A última fase de um estudo de pesquisa operacional consiste em implantar a solução final. Esta fase é critica porque aqui, porque aqui, os beneficios do estudo são obtidos. Em conseqiiência é importante para a equipe de PO participar do desenvolvimento desta fase, não só para assegurar-se que a solução é corretamente transformada em um procedimento operacional como também para corrigir qualquer imperfeição descoberta na solução. 2.8 Conclusão Os problemas de PO têm as seguintes características: 1) Compilação de dados anteriores, relativos a operações de produção, vendas ou outros setores da empresa; 2) Análise dos dados colhidos através de técnicas estatísticas; 3) Criação do modelo matemático destinado a previsão e decisão no tocante as mesmas operações no futuro. Curso de Pesquisa Operacional 15 3.4 Modelos de Designação O mais simples tipo de modelo de alocação envolve a distribuição de um numero de tarefas para o mesmo numero de recursos (homens). Isto é chamado um problema de designação (atribuição). Este tipo de problema torna-se mais complexo se alguma das tarefas requer mais que um recurso e se os recursos podem ser usados para mais de uma tarefa. Um exemplo disto é o problema de transportes. 3.5 Modelos de Competição A teoria dos jogos dá um conceito estrutural dentro do qual a maioria dos problemas de competição pode ser formulada. Ela tem sido usada efetivamente pelos negócios (transações comerciais) para desenvolver estratégias de publicidade, políticas de preços, e escolha do momento oportuno (senso de oportunidade, timming) para introdução de novos produtos. As teorias estatísticas da decisão e simulação têm sido empregadas com sucesso nos jogos. O processo de Markov é um método de predizer variações competitivas no tempo de clientes fieis a uma marca (determinado produto) e cotas atuais de mercado são conhecidas. 3.6 Técnicas de Otimização Clássicas Às técnicas de otimização clássica ou tradicional são associadas com o procedimento de cálculo do máximo ou minimo. Resumidamente, quando uma característica pode ser representada por uma equação a uma variável que pode ser representada graficamente como uma curva continua uniforme, os valores de máximo e minimo da curva podem ser obtidos pelo conjunto das primeiras derivadas iguais a zero. Então, o sinal algébrico da segunda derivada daquele conjunto de pontos é examinado para a obtenção de solução do problema. Quando dois parâmetros estão envolvidos, por exemplo, x e y para determinar a variável z, o máximo e minimo podem ser encontrados pela aplicação de derivadas parciais num processo similar ao empregado para uma variável. As áreas de cálculo necessárias são: diferenciação, integração, derivadas parciais, e os multiplicadores de Lagrange. Estas técnicas matemáticas as quais são aplicadas para otimização de problemas são capazes de diretamente selecionar a melhor decisão sem a necessidade de muitos passos interativos. Curso de Pesquisa Operacional 16 3.7 Modelos de Reposição Problemas de reposição são geralmente de dois tipos: aqueles envolvendo itens que degeneram num período de tempo e aqueles que falham após certo tempo de uso. O primeiro grupo refere-se ao ativo fixo das empresas - máquinas, caminhões e equipamentos - os quais são itens altamente custosos. Aqueles no segundo tipo são relativamente baratos — tubos de vácuo, pneumáticos, válvulas, tubos e itens semelhantes. A programação dinâmica é usada para obtenção das soluções do primeiro tipo. A teoria estatística amostral e probabilidade podem ser empregadas na solução do segundo tipo. 3.8 Modelos de Estoques Modelos de estoques são os que dizem respeito com duas decisões: quanto ordenar num determinado tempo e quando ordenar esta quantidade para minimizar o custo total. Custo de movimentação, custos de ordens de armazenamento (estocagens), e custo de déficits são determinados assim como uma medida de efetividade dos custos (modelo) podendo ser usados pelos gerentes para selecionar um balanço apropriado entre custos e déficits. À decisão pelo critério do minimo custo pode também ser obtida pelo cálculo, teoria de probabilidades, programação dinâmica e simulação pelo computador. 3.9 Modelos de Filas Filas, algumas vezes referida como teoria das linhas de espera, trata (diz respeito) com chegadas uniformes ou aleatórias num serviço ou meios de processamento de capacidade limitada. O objetivo deste modelo é permitir determinar se o número ótimo de pessoas ou meios necessários para servir clientes quando considerando o custo do serviço e o custo de espera. Um problema de estoque pode ser visto como um problema de filas. Itens em estoque podem ser considerados como um meio de serviço ocioso esperando por clientes. À demanda pelo estoque é uma chegada para serviço e a saída do estoque pode ser considerada como uma fila de clientes A teoria das filas faz uso da teoria das probabilidades e cálculo. Curso de Pesquisa Operacional 17 3.10 Técnicas de Simulação Simulação presta-se ao emprego dos computadores, gera fator como potencial de vendas ou atrasos na expedição pelo exame de tabelas de números aleatórios que são essenciais aos programas. O computador mostra a saída de resultados que (poderiam) teriam sido obtidos se o critério de decisão tivesse sido usado. Números aleatórios são usados para simular chegadas e tempo de serviços. 3.11 Modelos de Programação Dinâmica A maioria dos problemas de programação dinâmica requer o uso de um computador para manipular a grande quantidade de dados (informações). Os modelos de programação dinâmica são extremamente usados para processo que se estende por vários períodos de tempo ou eventos. Ao invés de otimizar cada decisão como ela ocorre à programação dinâmica leva em consideração os efeitos da decisão de hoje nos futuros períodos de tempo. 3.12 Modelos de Rotas Um dos mais famosos problemas de rota é o do "Caixeiro Viajante". O objetivo é selecionar o caminho (itinerário que parte de sua própria cidade, passa através de cidades apenas uma vez, e retorna para sua cidade, pela menor distância em termos de tempo ou dinheiro. O modelo de rotas tem sido aplicado à produção onde o número de produtos ou itens produzidos (fabricados) é análogo ao de cidades. Trocam-se os custos de produção correspondentes aos custos de viagens entre cidades). 3.13 Métodos heurísticos Métodos heurísticos indicam aprendizado ou avaliação de sistemas. Os métodos heurísticos usam regras de manusear e avaliar, instruídos para explorar o caminho mais provável para se chegar a uma conclusão. Isto recoloca em check todas as alternativas (também para muitas quantidades aproximadas) para encontrar a melhor solução. Curso de Pesquisa Operacional 20 4.3.1 Exemplo para discutir a obtenção da função objetivo e as restrições: Giapetto fabrica dois tipos de brinquedos de madeira: soldados e trens. Um soldado é vendido por $27 e usa $10 de matéria prima. Cada soldado que é fabricado tem um custo adicional de $14 relativo à mão de obra. Um trem é vendido por $21 e gasta $9 de matéria prima. O custo de mão de obra adicional para cada trem é de $10. A fabricação destes brinquedos requer dois tipos de mão de obra: carpintaria e acabamento. Um soldado necessita de 2 horas para acabamento e 1 de carpintaria. Um trem necessita de 1 hora para acabamento e 1 hora de carpintaria. Cada semana, Giapetto pode obter qualquer quantidade de matéria prima, mas tem a disposição até 100 horas de acabamento e 80 de carpintaria. A demanda por trens é ilimitada, mas a venda de soldados é de no máximo 40 por semana. Giapetto quer maximizar seu lucro diário (receitas-custo). Formular o modelo matemático que poderá ser usado por Giapetto para maximizar seu lucro semanal. Solução: Definindo o objetivo “ Sabendo que a matéria prima necessária é obtida sem problemas, Giapetto tem como objetivo maximizar o lucro semanal (receitas - custos). “ Vamos então formular matematicamente a situação de Giapetto com o objetivo de maximizar o lucro semanal. Curso de Pesquisa Operacional 21 Primeiro ponto importante: Variáveis de decisão “ Em qualquer modelo de PL, as variáveis de decisão devem descrever completamente as decisões a serem feitas. “ Caso de Giapetto: quantos soldados e trens devem ser feitos na semana? Variáveis de decisão “ X1 = número de soldados produzidos cada semana; “ X2 = número de trens produzidos a cada semana. Segundo ponto importante: Função objetivo “ Em qualquer modelo de PL, o decisor quer maximizar ou minimizar alguma função das variáveis de decisão. “ Caso de Giapetto: custos fixos (aluguel, seguro) não depende dos valores de X1 e X2, assim ele pode se concentrar em maximizar a venda da semana. Curso de Pesquisa Operacional 22 Função objetivo Y Receitas e custos: podem ser expressos em termos das variáveis Xl e X2. Y Seria tolice Giapetto produzir mais soldados que ele possa vender, assim assumimos que todos brinquedos produzidos podem ser vendidos. Y Receita da semana = receita dos soldados + receita dos trens > Receita da semana = $/soldado * soldado /semana + $/trem * trem/semana Receita por semana = 27*X1 + 21*X2 Também podemos escrever: Y“ Custos de M.P. “ Custos de MO. 10*X1 + 9*X2 14*X1 + 10*X2 Então Giapetto quer maximizar: (27X1 + 21X2) - (10X1 + 9X2) - (14X1 + 10 X2) = 3X1 + 2X2 Assim o objetivo de Giapetto é escolher X1 e X2 para maximizar 3X1 + 2X2 Função objetivo maximizar Z = 3X1 + 2X2 ou max Z = 3X1 + 2X2 Curso de Pesquisa Operacional 25 Quarto ponto importante: Restrições adicionais Para completar a formulação do problema: “X1>0 *X2>0 Significa que Xle x2 precisam satisfazer todas as restrições P.L. - todos os termos X são de max Z = 3X1 + 2X2 expoente 1 as sujeito a: restrições são inequações 2X1 + X2 < 100 lineares X1+X2 <80 Ts X1 <40 O problema de Giapetto é típico de muitos outros, onde precisa-se maximizar lucros sujeitos a recursos limitados X1 >0 X2 >0 4.3.2 Exercícios - Obter a formulação matemática para alguns casos 1) Uma determinada empresa automobilística fabrica carros de luxos e caminhonetes. A empresa acredita que os mais prováveis clientes são homens e mulheres com altos rendimentos. Para abordar estes grupos, a empresa decidiu por uma campanha de propagandas na TV, e comprou 1 minuto do tempo de comercial de 2 tipos de programa: comédia e transmissão de futebol. Cada comercial durante o programa de comédias é visto por 7 milhões de mulheres e 2 milhões de homens com grande poder aquisitivo. Cada comercial durante a transmissão de futebol é visto por 2 milhões de mulheres e 12 milhões de homens com grande Curso de Pesquisa Operacional 26 poder aquisitivo. Um minuto de comercial durante o programa de comédias custa $50000, e durante a transmissão de futebol 8100000. A empresa gostaria que pelo menos 28 milhões de mulheres e 24 milhões de homens de grande poder aquisitivo assistissem sua propaganda. Obter a programação matemática que irá permitir a empresa atender as suas necessidades de propaganda a um mínimo custo. 2) Uma empresa fabrica carros e caminhonetes. Cada veículo precisa ser trabalhado nas seções de pintura e montagem. Se a seção de pintura trabalhar só com caminhonetes, 40 por dia podem ser pintados. Se estiver trabalhando somente com carros, 60 por dia é sua capacidade. Se a seção de montagem estiver trabalhando somente com caminhonetes, 50 podem ser montados por dia. O mesmo número é possível para carros se este for o único produto na linha. Cada caminhonete contribui $300 para o lucro, e cada carro $200. Obter a formulação matemática que determinará a programação de produção que maximizará o lucro da empresa. 3) Supondo que a empresa do exemplo anterior, por necessidades dos vendedores, tem de produzir pelo menos 30 caminhonetes e 20 carros diariamente, qual será a nova formulação do problema? 4.4 Solução de um problema de PL —- Método gráfico Um problema de P.L. só pode ser resolvido graficamente desde que o modelo, em estudo, apresentar duas variáveis. Implicações implícitas da FO em PL max Z = 3X1 + 2X2 “A contribuição para a função objetivo de cada variável de decisão é proporcional ao valor da variável de decisão; “A contribuição para a função objetivo para cada variável é independente dos valores de outras variáveis de decisão. Curso de Pesquisa Operacional 27 Definição “ Região de solução para um problema de PL: éo conjunto de todos os pontos que satisfazem todas as restrições do problema. Região de solução Giapetto: X1 = 40 X2 = 20 Restrições: 2X1 + X2 < 100 X1+X2<80 X1<40 X1>0 Xx2>0 D região de solução ok 2*40+20 < 100 ok 40+20 < 80 ok 40 < 40 ok 40 >0 ok 20 > 0 Região de solução Giapetto: X1 = 15 X2='70 Restrições: 2X1 + X2 < 100 X1+X2<80 X1<40 Xx1>0 Xx2>0 ok 2*15+70 < 100 não 15+70 > 80 ok 15 < 40 ok 15>0 ok 70 > 0 Curso de Pesquisa Operacional 30 x2 (9 Polígono DGFEH - região de solução 1 Região convexa simplex x1 Encontrando a solução ótima “ Após a identificação da região de solução, nós devemos procurar a solução ótima, que será o ponto da região que leva ao maior valor de: Z = 3X1+2X2 Encontrando a solução ótima “ Para encontrar a solução ótima, nós precisamos desenhar uma linha sobre a qual todos os pontos levem ao mesmo valor de Z. Y Escolhe-se qualquer ponto da região de solução: (20, 0): Z = 3X1+2X2 = 60 Assim (20, 0) cai sobre a reta: Z=3X1+2X2=60 X2 =30- 3/2X1 Curso de Pesquisa Operacional 31 Encontrando a solução ótima Y3X1 +2X2 = 60 Y tem coeficiente angular = -3/2 Y Assim todas as retas 3X1+2X2 = constante terão o mesmo coeficiente angular. Importante: uma vez desenhada a reta, podemos encontrar todas as outras pelo movimento paralelo da reta que desenhamos . x2 (4) s Retas iso-lucro Indica o ponto ótimo - G (20, 60) x1 Lucro de Giapetto YZ = 3*20 + 2*60 = 180 Curso de Pesquisa Operacional 32 4.4.1 Exemplos Resolver graficamente os exercicios 1, 2 e 3, formulados anteriormente no item 4.3, e as seguintes formulações: D) MaxZ=5X+ 2X Sujeito a: X<3 M<4 X+28<9 X2>0 X2>0 2) MaxZ =2X,-1X, Sujeito a: X -X<l 2X +*%,>6 X2>0 X2>0 4.4.2 Casos possíveis Pela discussão apresentada neste item, foi visto que um problema de PL com duas variáveis, necessariamente cairão em um dos 4 casos possíveis, sendo eles: 1) Caso 1: a formulação tem solução única; 2) Caso 2: a formulação tem múltiplas soluções; 3) Caso 3: a formulação não tem solução; 4) Caso 4: a formulação não tem fronteira, a região de solução permite arbitrários valores para Z (grandes valores de Z, para problemas de max, e pequenos valores de Z, para problemas de min). E qualquer outra formulação, com maior número de variáveis, também sempre se enquadrará em um destes casos. Curso de Pesquisa Operacional 35 Ativo circulante Obrigações Caixa 10000 Contas a receber 3000 Estoques 7000 Dívidas em bancos 10000 A empresa precisa determinar quantos gravadores e rádios deverão produzidos em Dezembro. A demanda é alta o suficiente para garantir que todos os produtos fabricados serão vendidos. Todas as vendas são feitas a crédito, pagamentos por produtos fabricados em Dezembro não serão recebidos até primeiro de Fevereiro de 07. Durante Dezembro, a empresa irá receber $2000 e precisará pagar $1000 devido ao empréstimo bancário e $1000 referente ao seu aluguel. Em primeiro de janeiro de 07, a empresa receberá um carregamento de matéria prima no valor de $2000, que será pago em Fevereiro de 07. A gerência decidiu que em primeiro de janeiro de 07 precisa ter pelo menos $4000 em caixa. Também o banco exige que a razão entre dinheiro disponível e financiamento seja de pelo menos 2. Para maximizar o lucro da produção em Dezembro, o que deveria empresa produzir durante este mês? 4.5.4 Exemplo 4: problema de Blending (mistura) Uma refinaria produz 3 tipos de gasolina (gasolina 1, gasolina 2 e gasolina 3). Cada tipo é produzido pela mistura de 3 tipos de petróleo (petróleo 1, petróleo 2 e petróleo 3). Os preços de venda por barril da gasolina e da compra de petróleo são: Preço de venda por barril Preço de compra por barril Gasolina 1 70 Petróleo 1 45 Gasolina 2 so Petróleo 2 35 Gasolina 3 50 Petróleo 3 25 A refinaria pode comprar até 5000 barris de cada tipo de petróleo por dia. Os 3 tipos de gasolina se diferem na octanagem e no enxofre presente. O petróleo misturado para fabricar a gasolina 1 precisa ter uma octanagem média de pelo menos 10 e conter quando muito 1% de enxofre. O petróleo misturado para fabricar a gasolina 2 precisa ter uma octanagem média de pelo menos 8 e conter quando muito 2% de enxofre. O petróleo misturado para fabricar a gasolina 3 precisa ter uma octanagem média de pelo menos 6 e conter quando muito 1% de enxofre. A taxa de octanagem e de enxofre que contém os 3 tipos de petróleo são as seguintes: Octanagem | Enxofre Petróleo 1 12 0.5% Petróleo 2 6 2% Petróleo 3 8 3% Curso de Pesquisa Operacional 36 Custa $4 para transformar 1 barril de petróleo em 1 barril de gasolina, e a refinaria pode produzir até 14000 barris por dia. Os clientes da refinaria necessitam das seguintes quantias de cada tipo de gasolina: gasolina 1 — 3000 barris por dia; gasolina 2 — 2000 barris por dia; gasolina 3 — 1000 barris por dia. A empresa considera sua obrigação atender a estas demandas. A empresa também tem a opção de propagandas para estimular a demanda por seus produtos. Cada 1$ gasto diariamente em propaganda de um tipo particular de gasolina incrementa a demanda diária desta gasolina em 10 barris. Por exemplo, se a refinaria decide gastar $20 diariamente para divulgar a gasolina 2, o aumento da demanda diária desta gasolina será de 200 barris. Formular o problema para que a refinaria maximize seu lucro diário. Usando Programação Linear para resolver problemas de decisão multi períodos Até aqui, todas as formulações discutidas são exemplos estáticos, ou modelos de 1 período. Nos modelos estáticos, se assume que todas as decisões são feitas em um simples instante do tempo. Nos exemplos a seguir será mostrado como a Programação Linear pode ser usada para determinar decisões ótimas em multi períodos, ou modelos dinâmicos. Modelos dinâmicos aparecem quando o decisor toma decisões em mais de um ponto do tempo. Em um modelo dinâmico, decisões tomadas durante o período de tempo corrente influem em decisões de períodos futuros. Por exemplo, considere uma empresa que precisa determinar quantas unidades de um produto devem ser fabricadas cada mês. Se ele produzir uma quantidade grande no mês corrente, poderia reduzir o número de unidades a produzir nos meses futuros. Os 3 próximos exemplos ilustram como decisões iniciais afetam decisões posteriores. 4.5.5 Exemplo 5: Um modelo de estoques Uma empresa de barcos precisa determinar quantos veleiros devem ser produzidos durante cada um dos 4 próximos trimestres. A demanda de cada um dos trimestres é: primeiro trimestre, 40 veleiros; segundo trimestre, 60 veleiros; terceiro trimestre, 75 veleiros; quarto trimestre, 25 veleiros. A empresa quer atender a demanda prontamente. No início do primeiro trimestre, a empresa tem 10 veleiros em estoque. No início de cada trimestre, a empresa precisa decidir quantos veleiros devem ser produzidos durante o trimestre. Por simplicidade, assume-se que os veleiros fabricados durante um trimestre podem ser usados para atender a demanda deste trimestre. Durante cada trimestre, a empresa pode produzir até 40 veleiros com Curso de Pesquisa Operacional 37 sua mão de obra regular a um custo de $ 400 por veleiro. Tendo de trabalhar com horas extras durante o trimestre, a empresa pode produzir veleiros a mais a um custo total de $ 450 por barco. No final de cada trimestre (após ter ocorrido a produção e a demanda do trimestre ter sido atendida), um custo de transporte ou armazenagem de $ 20 por barco ocorre. Usar a programação linear para determinar a sequência de produção para minimizar a soma dos custos de produção e estoques durante os 4 próximos trimestres. 4.5.6 Exemplo 6: Modelos de financiamento multi período O exemplo a seguir ilustra como a programação linear pode ser usada para problemas de gerenciamento de fluxo de caixa. A chave é determinar as relações de dinheiro nas mãos durante diferentes períodos. Uma empresa de investimentos precisa determinar a estratégia de investimento para os próximos 3 anos. Atualmente a empresa tem $100.000 disponível para investir. Os investimentos A, B, C, D e E estão disponíveis. O fluxo de caixa associado com investir $1 em cada opção é dado na tabela a seguir. 0 1 2 3 -$1 $0.50 $1 $0 $0 -$81 $0.50 $1 -$81 $1.2 $0 $0 -81 $0 $0 $1.9 $0 $0 -$81 $1.5 Por exemplo, 1$ investido na opção B requer um pagamento de $1 no ano 1 e retorna $0.50 no ano 2 e $1 no ano 3. Para assegurar que o portfólio da empresa seja diversificado, a política da empresa é a de aplicar até $ 75.000 em um único investimento. Adicionalmente aos investimentos A-E, a empresa pode obter taxas de 8% ao ano mantendo o dinheiro não investido em fundos do mercado. Ganhos dos investimentos podem ser imediatamente reinvestidos. Por exemplo, o dinheiro recebido no ano 1 do investimento C pode ser imediatamente reinvestido na opção B. A empresa tem como diretriz não emprestar dinheiro de fundos, assim o dinheiro disponível para investimento a qualquer tempo é limitado ao disponivel. Formular a programação linear que maximiza o dinheiro em mãos no ano 3. Curso de Pesquisa Operacional 40 4.6 Solução de problema de PL - Método SIMPLEX Nas formulações anteriores, problemas com mais de duas variáveis não poderiam ser solucionados com o método gráfico. Desta forma é necessário o estudo de outro procedimento para a busca de soluções. Agora, será apresentado mais um procedimento geral para resolução de problemas de programação linear, denominado "Método Simplex” e que foi desenvolvido em1947 por George B. Dantzig. O método simplex é um método interativo (algoritmo) utilizado para achar, algebricamente, a solução ótima de um problema de P.L. 4.6.1 Teoremas Básicos Teorema 1 - O conjunto de todas as soluções compatíveis do modelo de programação linear é um conjunto convexo cujos vértices (pontos extremos) correspondem a soluções básicas viáveis. Teorema 2 - Se a função objetiva possui um máximo (minimo) finito, então pelo menos uma solução ótima é um ponto extremo do conjunto convexo do teorema 1. 4.6.2 Procedimentos do Método Simplex Supondo o seguinte problema para maximização: Max z= 5X, + 2X, Sujeito a: X<3 X<4 X1+2X<9 X1, X>0 A solução gráfica do problema é a seguinte: Curso de Pesquisa Operacional 41 E (0,4) c(3,3) x Pontos extremos A (0,0) B(3,0) ABCODE Sabe-se que a solução ótima do modelo é uma solução compativel básica do sistema, ou seja, um ponto extremo do polígono ABCDE. O método simplex, para ser iniciado, necessita conhecer uma solução compativel básica (solução inicial) do sistema, isto é, um dos pontos A, B, C, D ou E do trapézio. Suponha-se que essa solução seja o ponto A. O método simplex verifica se a presente solução é ótima. Se for o processo está encerrado. Se não for ótima, é porque um dos pontos adjacentes fornece um valor maior que o ponto A. Neste caso, o método simplex faz então à mudança do ponto A para o ponto extremo adjacente que mais aumente o valor da função objetivo. No caso o ponto B. Agora, tudo que foi feito para o ponto extremo A é feito para o ponto extremo B. O processo finaliza quando se obtém um ponto extremo onde todos os pontos extremos a ele adjacentes, fornecem valores menores que a função objetivo. Como fazer, algebricamente, a mudança de um ponto extremo para outro, a ele adjacente? Achar, portanto, a próxima solução básica (ponto extremo adjacente) exige a escolha de uma variável básica para deixar a base atual, tornando-se não básica, e a escolha de uma variável não básica para entrar na base em sua substituição. O método simplex compreenderá, portanto, os seguintes passos: 1. Achar uma solução compatível básica inicial. 2. Verificar se a solução atual é ótima. Se for, pare. Caso contrário siga para o passo III. 3. Determinar a variável não-básica que deve entrar na base. 4. Determinar a variável básica que deve sair da base. 5 Achar a nova solução compatível básica, e voltar ao passo II. Curso de Pesquisa Operacional 42 4.6.3 O Método Simplex A seguir será mostrado passo a passo o método simplex. Definição Geral de Programação Linear: Maximizar ou Minimizar Z=C1X1+C,X+... + Ch Xn sujeito a: anXi +anRi+...... +amk (<ou=ou >) b anXi +agX +... + ama (<ou=ou >) b, anXi +agX +... + a3nXn (<ou=ou >) bz ami + ami +... + amXn (<ou=ou >) bm Xi, Xo, X3, Kn>0 O Método Simplex é aplicado diretamente quando: 1. Todas as restrições são < bi 1. Todososb;>0 2. Se quiser maximizar Z Quando uma dessas condições não é atendida estamos em presença de um caso particular. O Método Simplex será estudado, acompanhando a seguinte formulação: Maximizar Z = 3x1 + 2x2 + 5x3 Sujeito a x1+2x2+x3< 430 3x1 + 2x3 < 460 xl+ 4x2 < 420 x1,x2,x3>0 Primeiro passo: Transformar o sistema de M desigualdades lineares restritivas em um sistema de M equações lineares. Para isso adiciona-se a cada uma das desigualdades uma variável não-negativa chamada “Variável de Folga”. Curso de Pesquisa Operacional 45 Base Z X, X X: Xs Xs Xe b bi/aie equac. z 1 4.5 -2 0 0 2.5 0 1150 0 0 =05 0 1 =0:5 o 200 100 1 y 0 1.5 0 1 0 0.5 0 230 ind. 2 0 1 4 0 o 0 1 420 105 3 Como na primeira linha da coluna de X> aparece um número negativo, a solução ainda não é a ótima. Oitavo passo: Repetir todos os passos, do 4º ao 7º, tantas vezes quanto forem necessárias, até que a solução ótima seja encontrada. O resultado final da tabela anterior aparece na próxima iteração, e como não existem mais números negativos na primeira linha a solução é ótima. O resultado é mostrado a seguir. Base | 2 | x x X K Xs K b bi/aie | equac. Z 1 4 0 0 1 2 0 1350 0 X, 0 -0.25 1 0 0.5 -0.25 0 100 1 X: 0 15 0 1 0 0.5 0 230 2 X6 0 2 0 0 -2 1 1 20 3 O máximo Z é 1350, para X, = 100, X; = 230 e X6= 20. 4.6.4 O problema do GIAPETTO pelo simplex Resolvendo o problema de Giapetto pelo simplex Max Z = 3X1 + 2X2 sujeito a: 2X1 + X2 < 100 X1+X2 <80 X1 <40 Xx1>0 X2>0 Curso de Pesquisa Operacional 46 Converter o problema de PL na forma canônica Solução básica inicial O problema pode ser representado assim: zilxilixz |x3 | xs | xs | b | Razão Li 20 0 0 0 0 1 1 0 0 100 foo/2=50 0 1 0 1 080, |so/1=80 õ õ õ õ 1777740, Juo/1=40 [5 ft Curso de Pesquisa Operacional 47 Segunda iteração Terceira iteração Quarta iteração Zz |x |x2 | x3 | x4 | x5 b | Razão Base | 1 0 0 1 1 o 180 x2 o o 1 a 2 o 0 x5 º º º 1 1 1 20 x1 º 1 º 1 «a o 20 Curso de Pesquisa Operacional 50 4.7.2 O procedimento do método “Big M” Para empregar o método “Big M”, procede-se da seguinte maneira: 1. Acrescentam-se as variáveis de folga as restrições do tipo (>) ou (<) para torná-las equações. No caso (<) soma-se, no (>) subtrai-se a variável de folga. No caso de restrições (>) ou (=) a bi, bi > 0; adiciona-se às restrições mais uma variável não negativa, chamada variável de artificial (X1), uma para cada restrição que for necessária. A adição das variáveis artificiais às equações causa uma violação das respectivas restrições. Esta violação é contornada, assegurando-se que estas variáveis artificiais sejam iguais à zero na solução final. Isto é feito atribuindo-se uma penalidade muito grande para estas variáveis artificiais na função objetivo. Tal penalidade será designada por (-M) para os problemas de maximização, sendo M > 0. Substituem-se as variáveis artificiais da FO, pelo seu valor tirado das equações restritivas onde aparecem. Procede-se da maneira usual do Simplex. Obs: Se a variável artificial for diferente de zero na solução final, o problema não tem solução. Resolver as seguintes formulações: 1) Min Z = 2X, + 3X, Sujeito a: 12X, + 1/4X <4 X1+3%X,>20 X+%X=10 X>0 X>0 2) Min Z = 2X, +3X, Sujeito a: 2X +X,>4 X-Xo2>-1 X2>0 X2>0 Curso de Pesquisa Operacional 51 4.7.3 O Método das duas fases Primeira fase: formular um novo problema, trocando a função objetivo original por uma artificial, representada pela soma das variáveis artificiais. Como o objetivo é tornar nulas todas as variáveis, devemos minimizar, primeiramente, a função objetivo artificial W, levando-se em conta os seguintes fatos, no algoritmo simplex: AFOéW; b. AFO Z do problema principal é tratada como qualquer outra variável durante a operação de pivotagem; c. A decisão a respeito da variável que sai da base não inclui a linha correspondente a Z. Resolvido o simplex para o problema artificial e obtida a solução ótima, W = W, encerra-se a primeira fase do processo. Neste caso, têm-se duas hipóteses: 19 W> O : neste caso o problema principal não tem solução; a) W= O : existe uma solução inicial para o problema principal. Passa-se a segunda fase. Segunda Fase: Inicia-se a segunda fase tomando-se as seguintes providências: a. Suprimem-se todas as variáveis artificiais; b. Suprime-se a função objetivo artificial e trabalha-se com a função objetivo do problema principal. Resolver as formulações do item anterior, e a proposta a seguir pelo método das duas fases. Max Z =-1X, +2X, Sujeito a: X+RX2>2 AX+XK>1 X<3 X2>0 X2>0 Curso de Pesquisa Operacional 52 5. SOFTWARES A utilização de programação linear é recomendada para problemas de maior porte, em que muitas variáveis e restrições devem ser consideradas. Por isso, o desenvolvimento de algoritmos computacionais eficientes e precisos tem sido a maior preocupação entre os pesquisadores. Programas adequados existem, virtualmente, para cada sistema computacional comercial desenvolvido nos últimos 20 anos. Problemas de grande porte requerem sistemas computacionais potentes e, portanto, sistemas paralelos têm sido utilizados nos últimos anos. Entretanto, problemas menores podem ser resolvidos em um computador pessoal utilizando um dos softwares desenvolvidos para resolução de problemas de programação linear, como por exemplo, XPress-MP LINDO e MINOS. Para problemas considerados médios, é recomendável a utilização de planilhas eletrônicas com recursos para resolução de problemas. Exemplos destas planilhas são o "What's Best?" (LINDO Systems) para Lotus 1-2-3, o Microsoft Excel e Borland Quattro e ainda o solver para microsoft Excel. Todos eles são ferramentas poderosas, apesar de sua aparência simples. O Solver do Excel será utilizado em alguns exemplos apresentados. Outro programa que também será visto é o LINDO. O instituto de pesquisa operacional e ciências administrativas (INFOR-MS) publicam, eventualmente, pesquisas sobre os softwares de programação matemática em seu periódico OR/MS Today. O relatório de 1995 apresenta softwares que rodam em computadores pessoais e destaca softwares capazes de atacar problemas maiores tanto quanto extensões de planilhas eletrônicas. 5.1 Uma introdução ao uso do LINDO LINDO (Linear Interactive and Discrete Optimizer) foi desenvolvido por Linus Schrage (1986). Ele é um programa de computador que pode ser usado para resolver problemas de programação linear, inteira e quadrática. Para ilustrar seu uso, vamos usar o exemplo de Giapetto, discutido anteriormente, e que foi sintetizado na seguinte formulação: Curso de Pesquisa Operacional 55 Max Z = 3X1+ 2X2 Função objetivo Sujeita a: 2X1+X2 <100 Restrição quanto a tempo de acabamento X1+X2<80 Restrição quanto a tempo de carpintaria X1<40 Restrição de venda máxima de soldados Estas equações podem ser representadas de maneira diferente, através da utilização de matrizes. Esta representação está exposta a seguir: X1=número | X2 = número de de soldados trens maximizar 3 2 Sujeito as limite restrições 2 1 < 100 1 1 < 80 1 0 < 40 Lucro bruto Solução Lo A [Lo Com exceção da última linha, denominada solução, as demais restrições expostas nas matrizes já eram conhecidas. A linha de solução representa os valores atribuídos a XI e X2 antes de qualquer otimização. No estado atual, ambos XI e X2 são definidos como zero o que resulta em um lucro bruto de zero unidade. O primeiro estágio de uso Solver é escrever esta matriz na planilha, como apresentado na Figura 5.1. Como em qualquer planilha, é muito importante observar que algumas células contêm valores constantes, mas outras contêm fórmulas as quais assumem os valores que são exibidos nas mesmas. Neste exemplo, as células D4, D5, D6 e E8 contêm fórmulas. As demais contêm textos, que são utilizados para deixar o exemplo mais claro, ou contêm valores. Curso de Pesquisa Operacional 56 Ae a E UR RETRO [88] arquivo Editar Exibir Inserir Formatar Ferramentas Dados Janela ajuda Deneresres| > o jaelzasuinsa|= -|B [faria Fo s[N TS ERTRE [E-9-A- EM =] =| A ] B ] T l [5 LE Tr 1 - Números de soldados: procuzido: K2 - Número de trens procuzicos: Maximize 3 2 limites Restrição acabamento 2 1 100 100 Restrição de carpintaria 1 1 so so Restrição dedemanda de soldados 1 o 20 40 Lucro solução 20 so 180 Figura 5.1 - Formulação básica do problema. Ujma rápida explicação da Figura 5.1 é a seguinte: 1. Neste exemplo, as colunas B e C possuem os valores dos coeficientes das expressões utilizadas na formulação algébrica e na tabela anteriormente. A linha 2 contém os valores dos coeficientes da função objetivo (2 e 1). As linhas 4 a 6 apresentam os valores dos coeficientes das restrições descritas anteriormente. A linha 8 contém os valores dados inicialmente para X1 e X2 antes de qualquer otimização. A coluna D possui suas linhas com valor zero, porém suas células representam a utilização das três restrições. Assim, a célula D4 contém a fórmula: = $B$8*$B4 + $C$8*$C4 Observe que as referências às células B10 e C10 são ambas absolutas. Assim, esta fórmula estendida da célula D4 a D6 é dada por: D4 = $B$8*$B4 + $C$8*8C4 DS = $B$8*$B5 + $C$88*8C5 D6 = $B$8*$B6 + 8C$88*8C6 Curso de Pesquisa Operacional 57 A coluna E foi utilizada para que os limites máximos e mínimos das restrições fossem observados, a qual é frequentemente conhecida como right-hand-sides (abreviada como RHS por muitas pessoas). Assim, existe um limite de 100 horas para acabamento, de 80 horas para carpintaria e venda máxima de 40 soldados. A coluna D, como mencionado anteriormente, é usada para armazenar a utilização atual dos recursos. Assim, a célula D4 representa a quantidade da restrição horas de acabamento que foi utilizada e seu valor é zero, uma vez que as células B8 e C8 contêm valor zero antes de qualquer otimização. Finalmente, uma célula da planilha deve ser utilizada para armazenar o resultado da otimização (neste caso, o valor do lucro semanal obtido); nesta planilha, este valor está contido na célula E8. 5.2.2 Janela de Parâmetros do Solver Utilizando os botões do mouse ou o teclado, devemos selecionar o Solver a partir do menu de ferramentas do Microsoft Excel. A Figura 5.2 apresenta a janela que irá aparecer na tela. Esta janela de parâmetros do Solver é utilizada quando o usuário fornece ao Solver as informações necessárias para que o mesmo busque a solução otimizada. LEE [onde Efe Igual a: Cemár o Comin Cwalorde: Jo Fechar | Células variáveis: 5 Estimar ubmeter às restrições; Opções O lisrar | Redefinir tudo x Excluir — mi | Figura 5.2 — Janela de parâmetros do Solver. Para chegarmos à solução ótima do exemplo, o Solver precisa das seguintes informações: 1. Onde o valor da função objetivo será armazenado? Este valor representa o resultado da otimização dado pela combinação de valores de X1 e X2 determinada. Neste caso, o resultado será armazenado na célula E8. Isto significa que a célula E8 deve conter a fórmula apropriada para a otimização, a qual, neste caso, é dada por: = $B$2*$B$8 + Curso de Pesquisa Operacional 60 É importante observar que muitas outras informações, além do valor ótimo das variáveis estudadas, podem ser obtidas a partir da solução fornecida para um problema de programação linear. Um bom pacote computacional como o Solver fornece relatórios que ajudam o usuário a entender muito mais sobre a solução apresentada. O Solver fornece três relatórios padrão e permite que sua solução seja exportada para outro pacote se uma análise mais detalhada for necessária. 5.2.3 O Relatório de Resultados do Solver O relatório resume os resultados da pasta de trabalho e também fornece algumas informações a mais. Estas informações extras podem ser calculadas pelo usuário, mas é importante guardá- las em algum lugar. O relatório da otimização para o problema apresentado é mostrado na Figura 5.6 e possui três partes, como descrito abaixo: e Célula de destino (Máximo): apresenta o máximo lucro obtido pelo Solver. Se este fosse um problema de minimização, esta seção iria conter o valor minimo. e Células ajustáveis: mostram as variáveis de entrada, seus valores após a solução ótima e seus valores iniciais (zero, neste caso). Restrições: indica a utilização de cada um dos recursos ao final da otimização. A coluna de status classifica as restrições como obrigatória (restrição com utilização máxima) ou não- obrigatória estas últimas são as que apresentam algum recurso que não foi utilizado - indicado pelo valor diferente de zero na coluna diferencial (slacks - folgas). Os outros dois relatórios fornecem mais informações sobre a sensibilidade da solução ótima, informações que podem ser importantes por várias razões. Primeiro, porque são raros os casos de programação matemática em ciências administrativas nos quais todos os coeficientes ou valores do modelo são conhecidos com precisão. Geralmente, alguns coeficientes são conhecidos e várias serão aproximações, estimativas ou até mesmo hipóteses. O que fazer, se os valores tomados forem errados? Qual será o efeito destes erros na solução? Assim, uma solução alternativa não tão ótima pode ser algumas vezes, melhor que uma solução ótima que se toma sensível aos valores atribuídos aos coeficientes. A segunda razão que torna importante a análise de sensibilidade está relacionada à idéia de que o mundo é dinâmico e, por isso, as coisas estão mudando constantemente. Por exemplo, pode ser verdade que esta semana a matéria-prima tenha certo custo, porém, se o periodo observado for um mês, este Curso de Pesquisa Operacional 61 custo pode ser diferente. Assim, é importante conhecer quais são os efeitos que as mudanças nos coeficientes podem gerar na solução ótima. fale E T E E 5 Microsoft Excel &.0 Relatório de resposta l 1 Planil PastaZ]Pland Relatório criado: 25103/98 22:42:39 Célula de destino (Má) Célula Nome $SE38 solução Lucro Células ajustâveis nal Yalor final 0 180 Célula Nome Yalor original Yalor final $B$8 solução X1 - Números de soldados produzidos 0 20 $0C48 solução K2- Número de tens produzidos 0 E Restrições Célula Nome valor da célula Fórmula Status Transigência $Dg4 Restrição acabamento 100 PDg4c=PESA Agrupar 0 $D$5 Restrição de carpintaria 80 $0$5<=$E$5 Agrupar 0 $D$5 Restrição dedemanda de soldados 20 $0$8<=$E$€ Sem agrupar 20 Figura 5.6 - Relatório de resposta para o problema Curso de Pesquisa Operacional 62 6. CASOS PARTICULARES NO SIMPLEX 6.1 Caso de múltiplas soluções Se um problema de PL (programação linear) tem mais de uma solução, nós dissemos que o problema tem múltiplas soluções alternativas. Vejamos como identificar isto no Simplex. A análise será feita através do seguinte problema: Um fabricante de móveis fornece os seguintes produtos: mesas, armários e cadeiras. A fabricação de cada tipo de produto requer chapas de mogno e dois tipos de mão de obra, uma para acabamento e outra para carpintaria. A quantidade de recursos para cada tipo de produto é dada na tabela abaixo. Recurso | armário mesa cadeira Mogno sm om? Im? Horas de 4 2 1.5 acabamento Horas de 2 1.5 0.5 carpintaria No momento, 48 m? de chapas de mogno, 20 horas de acabamento e 8 horas de carpintaria estão disponíveis. O armário é vendido por $60, a mesa por $35 e a cadeira por 820. A empresa acredita que a demanda por armários e cadeiras seja ilimitada, mas que o mercado adquire no máximo 5 mesas. Uma vez que os recursos estejam disponíveis, a empresa deseja maximizar o seu lucro. A formulação do problema é a seguinte: Variáveis de decisão: X1 = número de armários a serem produzidos X2 = número de mesas a serem produzidas X3 = número de cadeiras a serem produzidas Max Z = 60X1 + 35X2 + 20X3 Sujeito a: 8X1 + 6X2 + X3 < 48 (restrição de mogno) 4X1 + 2X2 + 1.5X3 < 20 (restrição de acabamento) Curso de Pesquisa Operacional 65 E Tonstraint Display <untitled> (Max IKTe2A2 (O .D25X1-+.016566EX2c=1 O 02K1+.02k2-1 O none - Comer Points Constraints x1 x2 Z o o o E õ 120 0 50 100 20,00023,29,99977 20,00023 |29.99977 [1200002 Isoprofit Line X1 6.2 Caso de solução ilimitada Este caso ocorre quando a variável que entra na base não possui em sua coluna nenhum coeficiente positivo. Os programas de computador apresentam a última solução básica antes que a solução se torne ilimitada. Um caso de solução ilimitada é o seguinte: Max Z =2X1 —-X2 Sujeito a: X1I-X2<1 2X1+X2>6 X1,X2>0 O gráfico e solução do problema pelo QM for Windows é visto na figura a seguir. Na outra figura mostra-se que a variável que vai entrar na base é a X3, mas todos os coeficientes são negativos, configurando o caso de solução ilimitada. Curso de Pesquisa Operacional 66 - 7 Constraint Display <untitle d> O Max 2X1-1X2 O 1x11X2e=1 É 2X141X2>=B (o none Constraints Solution: Unbounded Isoprofit Lir Comer Points Coefficient of ER o -0.333 1.3332 40.333 [a Ro Rec Re ci ce) É a ec Rd Re] 6.3 Problema da degeneração No desenvolvimento do simplex, a linha pivô é a restrição que apresenta o menor quociente não negativo, na divisão dos termos independentes pelos coeficientes positivos da variável que entra. Pode ocorrer que haja mais de um resultado nessas condições. Deve-se escolher arbitrariamente um deles para calcular a solução. Entretanto, essa solução apresentará variáveis básicas com valor nulo. A saída de uma variável básica nula provoca o aparecimento de outra variável básica nula na solução seguinte, sem alteração do valor do objetivo. Neste caso, a solução é chamada degenerada. Se os coeficientes da função objetivo retornam não negativos em alguma iteração, o caso não apresenta dificuldade. O problema aparece Curso de Pesquisa Operacional 67 quando a iteração leva a longos circuitos, sem caracterizar a solução ótima. Embora o caso seja raro, há maneiras de solucioná-lo. Entretanto, a discussão deste caso não é relevante a nível deste curso. Curso de Pesquisa Operacional 70 7.2 Exercício Fazer análise semelhante para o problema a seguir. No programa de produção do próximo período, uma determinada empresa escolheu 3 produtos Pl, P2 e P3. O quadro abaixo mostra os montantes solicitados por unidade na produção. Produto Lucro por Horas de Horas de uso de Demanda unidade trabalho máquina máxima P1 2100 6 12 800 P2 1200 4 6 600 P3 600 6 2 600 Os preços de venda foram fixados por decisão política e as demandas foram estimadas tendo em vista estes preços. A empresa pode obter um suprimento de 4800 horas de trabalho durante o periodo de processamento e pressupõe-se usar três máquinas que podem prover 7200 horas de trabalho. Estabelecer um programa ótimo de produção para o periodo. Analisar os coeficientes das variáveis de folga da solução final. Curso de Pesquisa Operacional 71 8. DUALIDADE 8.1 Fundamento da dualidade Em determinadas situações, a quantidade de cálculos necessária para resolver um modelo linear pelo método Simplex pode ser reduzida. O modelo inicial chamado Primal, pode ser substituído por outro modelo chamado Dual, cuja solução é mais rápida. Será mostrado que uma vez conhecida à solução do Dual, conhece-se em consegiiência a solução do Primal, o que resolve o problema. Seja o seguinte problema, que será chamado de Primal: Max Z =2X1 + 3X2 + X3 Sujeito a: 3X1 + 4X2 +2X3< 10 2X1 + 6X2 + X3<20 X1I-X2-X3<30 X1,X2,X3>0 A obtenção do Dual se processa da seguinte maneira: para cada restrição será atribuida uma variável de decisão (Yi). A função objetivo do Dual será de minimização e cada uma de suas parcelas será o produto da variável Yi pelo termo da direita da restrição correspondente. Cada variável de decisão do Primal gera uma restrição no Dual. Neste caso o sinal será >, e o termo da direita será o coeficiente da variável Primal na função objetivo. Todas as variáveis do Dual serão não negativas. O quadro a seguir sintetiza as regras básicas para obtenção do Dual. Quadro Resumo para passar do Primal para o Dual e vice-versa PRIMAL DUAL (MAX) >> (MIN) Restrição E é < Yr>0 Restrição E é= Yy é qualquer Restrição E é > Yr<0 Xp20 Restrição Pé > Xp qualquer Restrição Pé = Xe <0 Restrição Pé < DUAL PRIMAL (MAX) <[[D———1 (MIN) Curso de Pesquisa Operacional 72 Assim, o Dual será formulado da seguinte maneira: Min W = 10Y1 +20Y2+30Y3 Sujeito a: 3Y1+2Y2+Y3>2 4Y1+6Y2-Y3>3 2Y1+Y2-Y32>1 Y1,Y2,Y3>0 De modo análogo, para o problema de minimização e sinais de > no Primal, o Dual é obtido como mostrado no exemplo a seguir. Primal: Min Z = 10X1 + 20X2 + 30X3 Sujeito a: Variável Dual 3X1+2X2+X3>2 > Y1 4X1+6X2-X3>3 > Y2 2X1+X2-X3>1 > Y3 X1,X2,X3>0 Dual: Max W=2Y1+3Y2+Y3 Sujeito a: Termos da direita 3yY1+4Y2+2Y3<10 > Coeficiente de X1 2Y1+6Y2+Y3<20 > Coeficiente de X2 Y1-Y2-Y3<30 > Coeficiente de X3 Y1,Y2,Y3>0 A solução ótima Primal corresponde à solução ótima Dual com Z = W. O coeficiente da variável de decisão na função objetivo Primal é o valor da variável de folga correspondente na solução Dual. O coeficiente da variável de folga da função objetivo Primal é o valor da Curso de Pesquisa Operacional 75 As variáveis de decisão do Dual representam os recursos do Primal. Assim Y1 = 1, esta variável de decisão representa a primeira restrição (acabamento) e seu valor é o mesmo do coeficiente da variável de folga X3 do Primal. Seu significado é, portanto que para cada unidade adicional do recurso acabamento o lucro será incrementado de 1. Y2 =, esta variável de decisão representa a segunda restrição (carpintaria) e seu valor é o mesmo do coeficiente da variável de folga X4 do Primal. Seu significado é, portanto que para cada unidade adicional do recurso carpintaria o lucro será incrementado de 1. A função objetivo Dual mede, então, a capacidade do estoque de recursos gerarem lucros. 8.4 Exercício Suponha que um problema de produção tenha como modelo: Max L=XI1 +0,3X2 +3X3 Sujeito a: X1+X2+X3<10 2X1 + X2+ 4X3<12 X1-3X2 -X3<9 X1,X2eX3>0 e que o quadro final de solução pelo Simplex seja: L X1 X2 Xx3 XxF1 XF2 XF3 b 1 0.5 0.45 0 0 0.75 0 9 0 0.5 0.75 0 1 -0.25 0 7 0 0.5 0.25 1 0 0.25 0 3 0 1.5 3.25 0 0 0.25 1 12 Onde Xi são as decisões de fabricação dos produtos Pi e XFi as sobras dos recursos Ri no programa. O objetivo é maximizar o lucro devido à produção e comercialização dos produtos. Responder as seguintes perguntas: 1. Qual a solução mostrada no quadro? 2. Quais os recursos escassos? 3. O que ocorreria se por um motivo de força maior tivesse que fabricar uma unidade de P12? 4. Se alguém quisesse adquirir uma unidade do recurso R1, você estaria disposto a vender? Qual o preço que compensa a venda? Curso de Pesquisa Operacional 76 5. Se alguém insistir em comprar uma unidade do recurso R2, que preço de venda compensaria o fato dele ser escasso? Construa o modelo Dual do problema? Obter a solução do Dual. O que significa a variável dual Y1? Oo 9 q a O que mede a função objetivo Dual? 10. O que mede o lado esquerdo da Segunda restrição Dual? E o lado direito? 11. Em termos de valores interno e externo, como podemos justificar a não fabricação de P2 no programa? 12. Em termos de valores interno e externo, como podemos justificar a fabricação de P3? 13. Quanto você pagaria por uma unidade adicional do recurso R2? Por quê? 14. Quanto você pagaria por uma unidade adicional do recurso R3? Por quê? Curso de Pesquisa Operacional 77 9. ANÁLISE DE SENSIBILIDADE Análise de sensibilidade se refere a como mudança na formulação de um problema de programação linear, afeta a solução ótima. Reconsiderando o problema de Giapetto. Max Z = 3X1 + 2X2 Sujeito a: 2X1 + X2 < 100 (Restrição de acabamento) XI + X2 < 80 (Restrição de carpintaria) XI < 40 (Restrição de demanda) X1,X2>0 Onde: X1 = Número de soldados X2 = Número de trens Solução ótima é Z = 180, X1 = 20, X2 = 60, ponto identificado no gráfico abaixo. As variáveis básicas são X1, X2 e X5 (variável de folga da restrição de demanda). A questão que se coloca em análise de sensibilidade é como alterações nos coeficientes da função objetivo e no lado direito das inequações que representam as restrições afetam a solução ótima. Giapetto Restrição de acabamento Restrição de demanda Restrição de carpintaria o 80] x 9.1 Mudança nos coeficientes da função objetivo Se a contribuição para o lucro de cada soldado crescer, parece lógico que a decisão ótima para o problema seria produzir mais soldados (o que faria X3 se tornar não básica). De forma análoga se a contribuição decrescer a decisão lógica seria a produção de apenas trens (X1 se Curso de Pesquisa Operacional 80 Como exemplo, o coeficiente de X1 na função objetivo pode alterar entre 2 e 4, que a solução continuaria sendo X1 = 20, X2 = 60 e X5 = 20. Já X2 pode variar entre 1,5 e 3. Já os valores de bi, por exemplo, b2, pode variar entre 60 e 100, que a base continuaria sendo X1, X2 e X5. Na figura a seguir encontram-se os resultados destas variações possíveis apresentadas pelo programa QM for Windows. Esta janela é acessada no menu WINDOW opção Ranging. Giapetto Solution Variable Value |Reduced| Original) Lower) Upper xi 20. D. 3. 2. 4. x CUR h. 2. 15 3, Constraint Dual|:/Surplus | Original Lower Upper Constraint 1 1. D, 100, 80, 120, Constraint 2 L D. 80. 60. 100. Constraint 3 D, 20, 40, 20.) Infimty Na figura a seguir esta o relatório que se obtém através do Excel, selecionando quando utilizado o Solver a emissão do relatório de sensibilidade. 1 Microsoft Excel 8.0 Relatório de sensibilidade 2 |Planilha: [Pastai]Plan1 3 |Relatório criado: 09/02/99 04:12:59 4 5 E [Células ajustáveis f Valor Reduzido Objetivo Permissível Permissível 8 Célula Nome Final Custo Coeficiente Acréscimo Decréscimo a sSBSO x 20 Ú ã 1 1 iD| SC 2 Go b 2 1 0a “u 12 |Restrições 13 Valor Sombra Restrição Permissível Permissível 14 Célula Nome Final Preço Lateral R.H. Acréscimo Decréscimo 15] SEM 100 1 100 20 20 16] SES eo 1 eo 20 20 17| SES 20 b 40 1E+550 20 tg lá [4 [H, Relatório de sensibilidade 1, Relatóriode limites! ZE[4] Curso de Pesquisa Operacional 81 9.3 Exercício Suponha que um problema de produção tenha como modelo: Max Z =2100X1 +1200X2 + 600X3 Sujeito a: 1) 6X1 + 4X2 + 6X3 < 4800 2) 12X1 + 16X2 + 2X3 < 7200 3)X1 <800 4) X2 < 600 5) X3 < 600 X1, X2 e X3 >0 Onde: Xi são as decisões de produção dos bens Pi. O objetivo é maximizar o lucro pela venda desses produtos. Restrições: 1. Horas de máquina para a produção dos bens; 2. Horas de mão de obra para a produção; 3. Demanda de Pl; 4. Demanda de P2; 5. Demanda de P3. O quadro final de solução pelo Simplex é o seguinte: Z|/M X2 X3 | XF1 | XF2 | XF3 | XF4 | XF5 b 1 0 1.4 0 50 150 0 0 0 1320000 0 0 -0.8 1 0.2 -0.1 0 0 0 240 0 1 1.467 0 |-0.033/| 01 0 0 0 560 0 0 -1.467 0 10.033 | -01 1 0 0 240 0 0 1 0 0 0 0 1 0 600 0 0 0.8 0 -0.2 01 0 0 1 360 Questões: 1. Qual coeficiente de estabilidade para o coeficiente de X19 O que isto significa? 2. Qual o coeficiente de estabilidade para o coeficiente de X37 O que isto significa? 3. Qual o coeficiente de estabilidade para o coeficiente de XF3? O que isto significa? Curso de Pesquisa Operacional 82 Qual o coeficiente de estabilidade para o coeficiente de XF1? O que isto significa? Um novo produto, que use 3 horas de máquina, 5 horas de mão de obra e com demanda garantida de 200 unidades para um lucro máximo de $ 800, teria interesse no programa? Qual o limite para aquisição do recurso R1, aos custos correntes, que mantém a informação contida em seu custo de oportunidade? Idem para o recurso R2. O que significa a informação contida no custo de oportunidade do recurso R5? Curso de Pesquisa Operacional 85 Dentro deste polígono encontram-se os pontos candidatos a solução do problema Figura 10.3 — Pontos candidatos à solução do problema 10.2 Por que programação inteira? Vantagens de restringir variáveis para obter valores inteiros: 1. Mais realista 2. Maior flexibilidade Desvantagens: 1. Mais dificil de modelar 2. Pode ser bem mais difícil de solucionar O mistério da programação inteira: e Alguns programas de inteiros são fáceis (é possível resolver os problemas com milhões de variáveis); e Alguns programas de inteiros são dificeis (até mesmo 100 variáveis podem ser dificeis); e Expertise e experiência são essenciais para saber o que é o que! e E uma área de pesquisa ativa em várias Universidades. Todos os programas de inteiros possuem igualdades e desigualdades lineares e algumas ou todas as variáveis devem ser inteiras. Tipos de programação inteira: e Se todas as variáveis devem ser inteiras, então esse programa pode ser chamado de programa puro de inteiros. e Setodas as variáveis devem ser O ou 1, o programa é chamado de programa binário de inteiros ou um programa de inteiros O -1. Curso de Pesquisa Operacional 86 Se algumas variáveis forem números fracionários e outros números inteiros, então o problema é chamado programação inteira mista (PIM). 10.3 Como modelar restrições “lógicas” Exemplos: 1. 2 3. 4 São selecionados exatamente 3 estoques. Se o estoque 2 for selecionado, o estoque 1 também o será. Se o estoque 1 for selecionado, então o estoque 3 não será selecionado. O estoque 4 ou 5 é selecionado, mas não os dois. São selecionados exatamente 3 estoques: Imaginando um exemplo com 6 variáveis de decisão, e todas binárias, a restrição pode ser a mostrada em 10.3. + txt, dx tax =3 (10.3) Se o estoque 2 for selecionado, o estoque 1 também o será: A restrição da programação inteira é mostrada em (10.4). 10.4 X 2X (04) Curso de Pesquisa Operacional 87 11. PROBLEMA DO TRANSPORTE 11.1 Objetivo do Problema do Transporte Minimizar o custo de todo o volume de transporte, obedecendo às necessidades de recebimento do destino e capacidade de envio da fonte. Conhecemos os custos unitários de transporte de cada origem para cada destino (Cij). Deseja- se decidir quanto transportar de cada origem para cada destino (Xij). Este problema pode ser melhor analisado pela representação apresentada na figura 11.1 Problema do Transporte Origens Destinos Disponibilidades Custo Demandas 10 ão ir ê FADA rHEsETIE ce E s a B PN . => e. =, “= = E AS E 2 TREE E E— dl FADA Figura 11.1 — Exemplo do problema de transporte Primeiro passo: Variáveis de decisão Para este caso: a empresa precisa determinar a quantidade a ser transportada de cada origem para cada destino. Assim: Xij = quantidade a ser transportada da origem i para o destino j; 1=1,2:;3;4; j=1,2;3; Segundo passo: Função objetivo Objetivo: Minimizar o custo de transporte, que é dado por: Curso de Pesquisa Operacional 90 Exercício 2 Determinar a melhor programação de transporte. Os lucros unitários e as disponibilidades e necessidades do produto estão no quadro abaixo. Destinos | Origens / D3 Disponibilidades o 200 360 o 240 440 03 50 200 Necessidades 340 Exercício 3 Determinar a melhor programação de transporte de maneira a se ter o menor custo. Não é possível abastecer D3 a partir de Ol. Destinos / rigens / o 12 0 tá 03 E Necessidades 20 Curso de Pesquisa Operacional 91 12. REDES Problemas de rede Casos especiais de problemas de programação lincar que são mais bem analisados através de uma representação gráfica. Importantes problemas de otimização, tais como problemas de logistica e de energia, produção e outros, são eficientemente resolvidos e modelados como problemas de rede. Problemas de rede Modelos de rede facilitam a visualização das relações entre os componentes do sistema, aumentando o entendimento do problema e de seus possíveis resultados. * E uma modelagem muita usada. Terminologia * Redes, nós e arcos: Curso de Pesquisa Operacional 92 Problemas de rede (Classificação usual) * Problemas de transporte e rede de distribuição; * Problemas de menor caminho; * Problemas de fluxo máximo. 12.1 Problemas de distribuição Problemas de Distribuição * Problemas que consideram múltiplas fontes, centros consumidores e locais intermediários por onde os produtos simplesmente passam são denominados problemas de distribuição. O problema de transporte já estudado é uma simplificação do problema de rede de distribuição. Curso de Pesquisa Operacional 95 Primeiro passo: Variáveis de decisão Curso de Pesquisa Operacional 96 Terceiro passo: restrições * Restrição 02 — nó 02 * —X23-X24 -X26 -X27 -X28 5 - 600 * Restrição 03 — nó 03 * X13+X23 -X34-X35 5 200 * Restrição 04 — nó 04 * X14+X24+X34 <350 Curso de Pesquisa Operacional 97 Terceiro passo: restrições * Restrição 05 — nó 05 * X15+X35 < 150 * Restrição 06 —- nó 06 * X26 <300 * Restrição 07 — nó 07 * X27-X78 <150