Baixe o app para aproveitar ainda mais
Prévia do material em texto
PESQUISA OPERACIONAL AULA 1 Prof. José de Souza Leal Neto CONVERSA INICIAL Pesquisa Operacional (PO): o termo provavelmente é desconhecido para a grande maioria dos estudantes. Entretanto, como qualquer disciplina que se estuda, no início tudo pode parecer complicado e nebuloso, mas, com a dedicação adequada aos estudos, os termos se tornarão familiares. Além disso, será possível identificar os benefícios advindos da aplicação das técnicas e dos métodos da Pesquisa Operacional na rotina das empresas. Assim, nesta primeira aula será apresentado como surgiu a PO, definição, características, além das fases de um estudo de PO, modelo e modelagem e programação linear. É claro que não se esgota o que se pode aprender de PO, mas é o início. Ok, tudo entendido, mas para que serve a PO? Uma referência inicial e importante é saber que a PO é constituída de conhecimentos que apoiam a tomada de decisão dos gestores: são ferramentas, um meio, e não um fim, mas a resposta à pergunta ocorrerá com o desenvolvimento da disciplina. O desafio é: você será capaz de perceber, ao final do curso, que o conhecimento proporcionado pela disciplina te dará um diferencial competitivo como administrador? Creio que sim, mas, para isso, é preciso ir além destas aulas: é necessário fazer diferentes abordagens no estudo de problemas a fim de explorar potenciais soluções (explorar cenários); observar a rotina diária a partir da perspectiva da PO. É, em suma, pensar diferente. Seja bem-vindo (a) à primeira aula de Pesquisa Operacional. CONTEXTUALIZANDO Como você conseguiria tornar a sua empresa ou o seu setor mais competitivo? Como poderia aumentar a produtividade? Essas são perguntas diárias, que gestores são sempre solicitados a responder e, para tal, precisam conhecer o processo para identificar problemas/oportunidades e, também, necessitam de informações/dados para a tomada de decisão. O conhecimento do processo é de fundamental importância para a tomada de decisão, pois não é possível tomar decisão acertada sem conhecimento de causa. Se o gestor está familiarizado com o processo, será capaz de perceber a existência de problema e onde ele está ou de identificar 2 uma oportunidade de melhoria. Sem conhecer o processo, não há como delinear um escopo nem definir objetivos. Quanto às informações/dados, via de regra, os gestores não dispõem das necessárias para a tomada de decisão. Podem até identificar que informações/dados são necessárias para a adequada tomada de decisão, mas esses nem sempre estão disponíveis oportunamente. E se as informações/dados estão disponíveis, provavelmente será necessário processá-las, ou seja, tratá-las estatisticamente. Pode ainda acontecer que as informações/dados necessárias sejam desconhecidas pelo gestor de forma parcial ou, até mesmo, em sua totalidade. Mesmo com o conhecimento do problema/oportunidade e com disponibilidade de informações/dados, ainda permanecerão incertezas. A percepção da existência do problema/oportunidade está correta? A oportunidade de melhoria trará benefícios para a empresa? É possível resolver tecnicamente o problema/melhoria? Quais insumos/recursos são plenamente usados no processo? Quais insumos/recursos são subutilizados? Em condições apropriadas, ao se empregarem técnicas de modelagem matemática e eficientes algoritmos computacionais, a PO pode subsidiar o decisor na análise dos mais variados aspectos e situações de um problema complexo, permitindo a tomada de decisões efetivas e a construção de sistemas mais produtivos (Sobrapo, 2017). Neste momento, antes de nos aprofundarmos na PO, tenha sempre em mente que as técnicas de modelagem matemática e os algoritmos computacionais são poderosos, mas não é a panaceia de todos os problemas administrativos, pois possuem suas limitações, como quaisquer outros recursos técnicos. TEMA 1 – HISTÓRICO E CONCEITOS DA PESQUISA OPERACIONAL Em suas devidas proporções, pode-se afirmar que empresas travam uma guerra contra suas concorrentes, e ampliando um pouco o conceito, que esta guerra é uma guerra entre cadeias logísticas. Mas, para obter vantagem sobre a concorrência é necessário empregar métodos e técnicas diferenciadas a fim de obter um diferencial competitivo. Um diferencial competitivo pode ser obtido por quem gerencia melhor os seus recursos empresariais, que são escassos. A PO se desenvolveu para gerenciar recursos escassos e obteve sucesso. Hoje é 3 possível fazer uso dos métodos e técnicas da PO no ambiente corporativo e, por conseguinte, obter um diferencial competitivo em relação à concorrência. Assim, no presente tema é apresentada a PO, a sua origem, o seu objetivo, as suas principais características e as suas possíveis aplicações. Histórico: O termo Pesquisa Operacional, remete às origens da área, cujo interesse inicial foi a gestão eficiente de operações (basicamente de logística militar). Assim, o desenvolvimento da PO foi fruto do esforço de guerra dos Aliados no início dos anos 40, e, tal esforço tinha por objetivo desenvolver métodos para resolver problemas de operações militares. O sucesso dessas aplicações levou o mundo acadêmico e empresarial a utilizar as técnicas então criadas, em problemas de administração. Com o avanço metodológico e computacional (velocidade de processamento, capacidade de armazenamento, recuperação de informações, descentralização de ações pelo uso de microcomputadores etc.), além da existência de demandas de outras áreas, ocorreu a ampliação do campo de atuação para além das operações militares. A modernização da PO pode ser identificada pelo desenvolvimento de modelos mais versáteis, mais rápidos e, sobretudo, interativos, que permitam maior participação do homem no desenrolar dos cálculos (Sobrapo, 2017; Andrade, 2009). O que é Pesquisa Operacional? A Sociedade Brasileira de Pesquisa Operacional (Sobrapo) define Pesquisa Operacional (PO) como a área de conhecimento que estuda, desenvolve e aplica métodos analíticos avançados para auxiliar na tomada de melhores decisões nas mais diversas áreas de atuação humana. Características da Pesquisa Operacional: a partir do que é escrito a respeito da PO, pode-se ser capaz de enumerar diversas características (Andrade, 2009; Sobrapo, 2017), entre as quais: Emprega métodos envolvendo programação matemática, simulação, teoria dos jogos, teoria das filas, análise de redes, teoria de decisão, aprendizado de máquina e ciência dos dados. Tais métodos são capazes de apresentar soluções efetivas para problemas aplicados, determinando a melhor utilização de recursos limitados e otimizando as operações empresariais (ambientes complexos e competitivos). Demanda por trabalho em equipe (multidisciplinar), com estreita cooperação entre líderes (tomadores de decisão), analistas e 4 stakeholders, por ser necessário um esforço sistêmico. Portanto, ocorre uma demanda natural de interação entre as áreas de administração, engenharias, computação e matemática. Emprega modelos, o que permite realizar „experimentações‟, ou seja, estudar cenários, viabilizando a análise de possibilidades e uma tomada de decisão melhor avaliada e testada antes de ser efetivamente implementada. Necessita de profissionais (face à interação multidisciplinar) capazes de compreender e resolver problemas em diversas áreas (flexibilidade de aplicações) e usar métodos analíticos e com foco em resultados. Aplicações da Pesquisa Operacional:segundo a Sobrapo (2017), a PO é empregada em áreas consideradas estratégicas, como energia, prospecção e exploração de petróleo, gerência de operações, logística, finanças, marketing, planejamento e gestão de sistemas de serviços, segurança da informação, administração industrial, gestão da qualidade, análise locacional, entre outras, de interesse civil e militar. Modelo e modelagem, uma abordagem: é possível encontrar diversos softwares desenvolvidos (de prateleira) para uso imediato, mas eles nem sempre atendem todas as necessidades, não é verdade? Porém, esse tipo de software possui, na maioria das vezes, menor custo do que se fosse desenvolvido para atender necessidades específicas. Perceba que há diferenças entre usar uma solução pronta e desenvolver uma solução que atenda pré-requisitos. Assim, faz-se necessário apresentar os conceitos de „modelo‟ e de „modelagem‟ a serem empregados nesta disciplina, pois há uma pequena sutileza no emprego dos referidos conceitos. Ao se empregar o conceito de “modelo”, deve-se entendê-lo como um algoritmo (etapas a serem seguidas) ou modelo matemático previamente elaborado para solucionar um problema recorrente. Esse “modelo” pode ser usado para resolver problemas similares, dado que as condições usadas para a elaboração do modelo nem sempre são encontradas na realidade. Para problema de baixa complexidade, o emprego de um „modelo‟ pronto pode ser o mais indicado pelos benefícios obtidos, tais como menor custo do que a “modelagem”, menor prazo para obter a solução etc. Quanto à “modelagem”, deve-se entender como a elaboração específica de um algoritmo ou modelo matemático para um problema a ser resolvido, que 5 possui escopo e objetivos bem definidos, ou seja, será construído um modelo “sob medida”, “personalizado”. O modelo proposto deverá atender os requisitos/especificações impostos pelo problema, ou seja, deverá considerar as condições existentes no momento do estudo. Entretanto, a “modelagem” possui algumas desvantagens, como o fato de requerer tempo para o desenvolvimento do modelo (prazos maiores), possuir maior custo em relação ao emprego de “modelo” etc. Saiba mais Estude um pouco mais e se familiarize com a terminologia empregada em PO. Para isso, leia as páginas 12 a 14 (Item 1.1) do livro-texto, disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788544302194/pa ges/13>. BARBOSA, M. A.; ZANARDINI, R. A. D. Iniciação à pesquisa operacional no ambiente de gestão. 2. ed. rev., atual. e ampl. Curitiba: Intersaberes, 2014. Leia também as páginas 1 e 2 (Item 1.1) do TAHA, disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788576051503/pa ges/1>. TAHA, H. A. Pesquisa Operacional: uma visão geral. 8. ed. São Paulo: Pearson Prentice Hall, 2008. Vídeo: O que é pesquisa operacional? Uma resposta mais “dinâmica” pode ser encontrada em: <https://youtu.be/tX6Rw7KJGjE>. Tema de pesquisa: confirme ou refute os argumentos usados acima, que caracterizaram diferenças entre modelo e modelagem. Encontre exemplos. TEMA 2 – FASES DE ESTUDO DA PESQUISA OPERACIONAL Não há como resolver um problema, em especial quantitativo, sem ter um algoritmo, uma sequência de etapas a serem seguidas. Desde o início, a Toyota adotou a forma de resolver os problemas: observar e estudar o processo, e aí começou o seu sucesso. Além disso, o que argumentar contra dados numéricos? Se forem adequadamente trabalhados por uma metodologia consolidada, os resultados serão confiáveis. O presente tema tem por objetivo apresentar as diversas fases necessárias para o desenvolvimento de um estudo de PO. 6 Fases de um estudo de pesquisa operacional: provavelmente você terá algumas dúvidas sobre as fases de um estudo de PO, porque não há uma unanimidade quanto elas, mas você poderá identificar algumas fases comuns nas propostas de diferentes autores, pois são indispensáveis para o desenvolvimento de um trabalho de PO. Tais fases são as seguintes: a. Estudo do problema. O escopo do problema deve ser adequadamente definido. O contexto do problema deve ser estudado de forma detalhada a fim de identificar o nível de complexidade e, consequentemente, escolher a técnica/ferramenta de PO mais apropriada para solucionar o problema. b. Levantamento e tratamento de dados. Os trabalhos de PO são quantitativos, e consequentemente é necessário levantar e tratar dados numéricos estatisticamente. O conjunto final de dados a ser empregado deve ser confiável. c. Definição da metodologia a ser empregada. O tipo de problema determinará a escolha do método/ferramenta de PO a ser empregada, e consequentemente a metodologia estará mais ou menos definida. Se for um modelo, a metodologia está definida. Se for necessário realizar uma modelagem, existem referências metodológicas na bibliografia de PO, entretanto pode ser necessário realizar adequações da metodologia à realidade do problema em estudo. d. Análise dos resultados obtidos. Da análise dos resultados obtidos, deve ser possível obter subsídios para identificar as atividades/recursos a serem priorizadas na elaboração da proposta de solução. e. Implementação de proposta. A análise dos resultados finais deve gerar recomendações ou propostas possíveis de serem implementadas a fim de solucionar ou minimizar o problema estudado. Provavelmente, você não encontrará, na bibliografia, uma proposta de generalização das fases de um estudo de PO, conforme apresentada acima. Isso se deve ao fato de que, em geral, os autores não fazem distinção entre “modelo” e “modelagem”. Entretanto, as fases apresentadas anteriormente estarão sempre presentes, implícita ou explicitamente, nos estudos de PO. 7 Saiba mais Leia o Item 1.3 do livro texto e avalie a abordagem proposta. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788544302194/pa ges/19>. BARBOSA, M. A.; ZANARDINI, R. A. D. Iniciação à pesquisa operacional no ambiente de gestão. 2. ed. rev., atual. e ampl. Curitiba: Intersaberes, 2014. O Item 1.6 apresenta a proposta de fases de um estudo de TAHA. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788576051503/pa ges/5>. TAHA, Handy A. Pesquisa Operacional: uma visão geral. 8. ed. São Paulo: Pearson Prentice Hall, 2008. TEMA 3 – MODELO Quando se fala em modelo, vem-nos à mente a ideia de uma referência, de um padrão. O objetivo do modelo em PO é basicamente representar um fenômeno físico, uma realidade existente. Porém, o modelo a ser usado não pode ser muito simplificado nem muito complexo. Se for simplificado demais, poderá não representar a realidade adequadamente; e se for complexo em demasia, pode não ser exequível. Somente com a experiência o profissional encontrará o equilíbrio entre o simples e o complexo. Este tema tem por objetivo apresentar o conceito de modelo e os tipos de modelo que podem ser empregados em PO. Definição: modelo significa, entre outras definições, tudo o que serve para ser imitado, uma representação (Michaelis, 2001). Também pode-se encontrar definições como: modelo matemático, representação matemática de um fenômeno físico humano etc. feita para que se possa melhor estudar o original; e modelo reduzido, reprodução em pequena escala de um aparelho ou de um conjunto. Resumidamente, pode-se definir “modelo” como uma representação simplificada da realidade. Tipos de modelo: na bibliografia da PO, não há umaunanimidade quanto aos tipos de modelo. A partir da tipologia proposta por alguns autores (Andrade, 8 2009; Chwif; Medina, 2006; Lactermacher, 2009), foi sintetizada uma classificação de possíveis tipos de modelo, conforme apresentado a seguir: Modelos conceituais: relacionam de maneira sequencial e lógica as interações e as atividades existentes no processo em estudo, de modo a possibilitar o estudo do processo e alcançar os objetivos definidos. É o tipo de modelo recomendado para as etapas iniciais do processo de modelagem. Modelos físicos: são modelos reduzidos em escala, tais como modelos de aeronaves, maquetes de edificações etc. Não são empregados em PO. Modelos heurísticos: são construídos quando a complexidade do problema é de tal ordem que a utilização de relações matemáticas é inviável ou extremamente dispendiosa. Esses modelos baseiam-se em regras empíricas ou intuitivas que, após se obter uma solução para o problema, permitem avançar para uma solução mais aprimorada. Modelos matemáticos: necessitam que as informações e as variáveis relevantes do problema sejam quantificáveis. Consequentemente, as grandezas são representadas por variáveis de decisão, e se usam expressões/funções matemáticas para descrever as relações entre elas e a operação do sistema. A metodologia da PO é mais indicada para solucionar problemas que podem ser representados por modelos matemáticos. Tais modelos podem ser classificados quanto ao nível de incerteza existente entre as relações das variáveis, como determinísticos (sem incerteza; as informações relevantes são tidas como conhecidas; modelos de otimização) ou probabilísticos (quando uma ou mais variáveis de decisão não são conhecidas; modelos de simulação). Modelos simbólicos, diagramáticos ou icônicos: usam símbolos gráficos para representar um sistema de maneira estática (o seu comportamento no tempo não é considerado), por exemplo: fluxograma de processo, mapas rodoviários, estações de metrô, estações de ônibus, organograma organizacional de empresa e outros. As suas limitações são não apresentar elementos quantitativos e não permitir apresentar muitos detalhes. O seu uso é mais adequado para documentar projetos e servir ferramenta de comunicação (visual). A priori, não são empregados em PO. 9 Saiba mais Leia os Itens 1.2 e 1.3 do TAHA e consolide a compreensão do conceito de modelo. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788576051503/pa ges/3>. TAHA, Handy A. Pesquisa Operacional: uma visão geral. 8. ed. São Paulo: Pearson Prentice Hall, 2008. Leia o artigo indicado no link. Na leitura, identifique o objetivo do estudo e a solução proposta. A solução é genérica ou é para um problema específico? Disponível em: <http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101- 74382000000100007>. Para conhecer a dinâmica de modelagem de simulação de eventos discretos, acesse o site do fabricante do Simul8 (inglês), disponível em: <https://www.simul8.com/products/guidedtours/watch_video.php?videoId=3> e <https://www.simul8.com/products/guidedtours/watch_video.php?videoId=6>; ou o vídeo do YouTube (português), disponível em: <https://youtu.be/Oecazr39BNo>. TEMA 4 – MODELAGEM Empresas podem até possuir processos semelhantes, porém o ritmo, os colaboradores, a operação, a cultura, entre outros são específicos de cada uma delas. Portanto, cada empresa possui sua “personalidade” e, por conseguinte, problemas específicos, os quais podem ser rotineiros ou complexos. Para resolver um problema complexo com aplicação de PO, provavelmente é necessário elaborar uma solução específica, ou seja, usar uma metodologia de modelagem para obter um modelo “sob medida”. Assim, este tema tem por objetivo apresentar propostas metodológicas de modelagem que as empresas podem usar para resolver problemas complexos com aplicação de PO. Definição: o dicionário Michaelis (2001) define “modelagem” como a operação de modelar e também define “modelar” como a ação de fazer o modelo ou o molde. Portanto, é possível afirmar que modelar é criar um modelo. 10 Vantagens e desvantagens: o emprego de modelagem, na opinião de Lachtermacher (2009), apresenta as seguintes vantagens, porque os modelos forçam: • Os decisores a explicitarem seus objetivos. • A identificação e a disponibilidade das diferentes decisões que influenciam os objetivos e dos relacionamentos entre as decisões. • A identificação das variáveis a serem incluídas e as condições em que serão quantificáveis. • O reconhecimento de limitações. Pode-se acrescer também como vantagem que os modelos possibilitam a comunicação de suas ideias, e a sua compreensão facilita o trabalho em grupo. Entre as desvantagens estão que a modelagem pode consumir tempo e ser dispendiosa e que a experiência profissional é diretamente proporcional à complexidade do modelo a ser elaborado. Metodologias de modelagem: na bibliografia de PO, é possível encontrar metodologias de modelagem bastante similares. A seguir são apresentadas as propostas de Lachtermacher (2009) e Andrade (2009), bem como a metodologia de autoria de Sargent (2014) para modelos de simulação, por ser mais detalhada e indicar a necessidade de se ser cientificamente rigoroso quando elaborar modelos mais complexos. Lachtermacher (2009) propõe um processo de resolução de um problema em cinco etapas consecutivas, conforme indicado na Figura 1. Tais etapas podem ser repetidas, quando se fizer necessário. O autor não apresenta maiores esclarecimentos a respeito das etapas, mas elas são de fácil compreensão. 11 Figura 1 – Processo de resolução de um problema Identificação do Problema Formulação do Modelo Análise dos Cenários Interpretação dos Resultados Implementação e Motoração Figura 1 - Processo de resolução de um problema (Lachtermacher, 2009) Fonte: Lachtermacher (2009). Figura 2 – Fases de um estudo de Pesquisa Operacional Definição do Problema Construção do Modelo Solução Avaliação do Modelo Validação Experiência do Modelo e Intuição Implementação do Resultados Figura 2 - Fases de um estudo de Pesquisa Operacional (ANDRADE, 2009) Por sua vez, Andrade (2009) indica a existência de fases em um estudo Pesquisa Operacional, conforme apresentado na Figura 2. É necessário lembrar 12 que, conforme argumentado anteriormente, são etapas de elaboração de um modelo, ou seja, são etapas de um processo de modelagem. Na perspectiva de Andrade (2009), na fase de definição do problema deve-se descrever os objetivos do estudo de forma exata, para delinear a concepção do modelo; identificar as alternativas existentes de decisão; e identificar limitações, restrições e exigências do sistema. Na fase de construção do modelo, deve-se escolher o modelo mais apropriado (programação linear, simulação, entre outros) para a representação do sistema, tendo como referência a definição do problema. A solução do modelo é função do modelo adotado. A programação linear poderá fornecer uma solução, dita “ótima”, e a simulação proporciona uma solução a partir da análise dos resultados obtidos. A fase de validação do modelo ocorre se o modelo for capaz de forneceruma previsão aceitável e compatível do comportamento do sistema real e a resposta fornecida pelo modelo puder subsidiar uma decisão que possa ser factível. A fase implementação da solução é realizada após avaliadas as vantagens que pode proporcionar, bem como a sua validade. Ela pode ser materializada em regras operacionais. Por fim, é realizada uma avaliação final do modelo e dos resultados obtidos. Apesar de ser uma metodologia voltada para simulação, pode-se considerar a metodologia de modelagem proposta por Sargent (2014) como a mais completa. A partir de uma metodologia mais completa, como a de Sargent, é mais fácil adaptar as etapas existentes ao nível de complexidade do problema em estudo do que incluir requisitos em outras metodologias que não são detalhadas/rigorosas. Na versão simplificada do processo de modelagem proposta por Sargent (2014), apresentada na Figura 3, o problema é o sistema real/proposto, ideia, situação, política ou fenômeno a ser modelado; o modelo conceitual é a representação matemática/lógica/gráfica do problema desenvolvido para um estudo específico; e o modelo computacional é o modelo conceitual implementado em um computador, ou seja, faz-se uso de uma linguagem de programação para implementar o modelo conceitual (com o devido rigor, é possível empregar software de simulação). 13 O modelo conceitual é desenvolvido na fase de análise e modelagem, o modelo computacional é desenvolvido na fase de programação computacional e implementação, e as inferências a respeito do problema são obtidas a partir de experimentos no modelo computacional na fase de experimentação. A partir da experimentação são estudados cenários, dos quais pode-se extrair subsídios para elaborar procedimentos a serem implementados. Além disso, os dados relacionados ao problema, após o devido tratamento estatístico, devem ser dados válidos para nortear o desenvolvimento do modelo conceitual e para serem empregados no modelo computacional. Figura 3 – Versão simplificada do processo de modelagem Fonte: Sargent (2014), adaptado. A validação do modelo conceitual tem por objetivo verificar o quanto a proposta do modelo está adequada ao processo em estudo. A verificação do modelo computacional é realizada para identificar a existência de algum erro na programação (ou no emprego do software). A validação operacional é realizada para avaliar se os dados obtidos com o modelo são coerentes com os dados reais. Após validado e verificado, o modelo está apto para ser usado. Agora, seria interessante você rever as fases indicadas no Tema 2 e procurar identificá-las nas diversas metodologias apresentadas acima. Saiba mais 14 Leia o Item 1.2 do livro texto e busque construir referenciais a partir das propostas de modelagem apresentadas. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788544302194/pa ges/15>. BARBOSA, M. A.; ZANARDINI, R. A. D. Iniciação à pesquisa operacional no ambiente de gestão. 2. ed. rev., atual. e ampl. Curitiba: Intersaberes, 2014. A respeito de modelagem, leia o Item 1.4 do TAHA. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788576051503/pa ges/3>. TAHA, Handy A. Pesquisa Operacional: uma visão geral. 8. ed. São Paulo: Pearson Prentice Hall, 2008. TEMA 5 – PROGRAMAÇÃO LINEAR (PL) Uma decisão é mais fácil de ser tomada quando se referência em uma quantidade, porque a decisão se torna dicotômica, ou seja, se aceita ou se rejeita a quantidade. Se uma empresa dispõe de dados numéricos apropriados a respeito de suas atividades, provavelmente será capaz de elaborar uma modelagem de PL. Um modelo de PL deve gerar, a princípio (pode não haver uma solução), uma resposta numérica específica, por exemplo com quais produtos de seu portfólio e em que quantidades se consegue o maior lucro. A PL tem por objetivo “alocar da melhor forma possível (isto é, de forma ótima) recursos limitados para atividades que competem entre si. [...] envolve selecionar o nível de certas atividades que competem por recursos escassos que são necessários par realizar essas mesmas atividades” (Hillier; Lieberman, 2010), ou seja, definir o quanto cada recurso será consumido. Este tema tem por objetivo iniciar o estudo de programação linear, apresentando seu objetivo, suas aplicações, suas características e sua forma padrão. Histórico: um breve histórico da Programação Linear é apresentado a seguir: A Programação Linear foi desenvolvida conceitualmente após a Segunda Guerra Mundial, pelo soviético Kolmogorov, com o objetivo de resolver problemas de logística militares. A primeira aplicação de PL foi feita em 1945, por Stigler em um problema referente à composição de uma mistura. O grande marco na evolução dos estudos de PL, contudo, ocorreu em 1947, com o desenvolvimento pelo jovem matemático Dantzig do 15 método que denominou “método simplex”. Dantzig, matemático da força aérea e em contato com questões relacionadas à logística percebeu que problemas que envolviam limitação de recursos podiam ser resolvidos por meio de uma sistemática de busca de solução ótima entre um conjunto de possíveis soluções. O rápido avanço dos computadores fez com que a Programação Linear passasse a ser utilizada como ferramenta de gestão empresarial. Tanto que o russo Kantorovich ganhou o Prêmio Nobel em Economia pelo desenvolvimento de conceitos de planejamento ótimo. Mais recentemente, em 1984, Karmakar desenvolveu um algoritmo que se tem mostrado superior ao simplex para a resolução de problemas extremamente grandes. Contudo, o método simplex continua sendo o mais utilizado nos dias de hoje, inclusive como base lógica das planilhas eletrônicas. (Corrar; Theóphilo; Bergmann, 2007) Programação linear: de forma objetiva, Hillier e Lieberman (2010) informam que, para descrever um problema, a programação linear faz uso de um modelo matemático e que “o adjetivo linear significa que todas as funções matemáticas nesse modelo são necessariamente funções lineares”. De forma semelhante, Lachtermacher (2009) registra que a programação linear é um ramo da programação matemática em que a função-objetivo e as restrições são representadas por funções lineares. A programação linear é um algoritmo que pode ser usado para solucionar problemas diários das empresas, pois estas se deparam rotineiramente com a escassez de produtos ou matérias-primas e, consequentemente, precisam determinar o melhor emprego (solução ótima) daqueles recursos escassos. A solução obtida pela programação linear é chamada de solução ótima (a melhor solução entre soluções possíveis), de acordo com o modelo matemático, pois determinará o emprego dos recursos escassos da forma mais eficiente e eficaz. A solução ótima (otimização do emprego de recursos) poderá resolver problemas em que seja necessário obter uma maximização ou uma minimização de uma determinada quantidade (lucro, custo, receita, tempo, quantidade de produtos...). Tal quantidade é chamada de objetivo, pois depende de um ou mais recursos escassos (Lachtermacher, 2009); é uma função matemática, com uma variável dependente (objetivo) e variáveis independentes (recursos escassos). Aplicações e objetivos: a programação linear pode ser aplicada em diversas áreas, como (Lachtermacher,2009; Andrade, 2009): Na administração/problemas de produção Na análise de investimentos Na alocação de recursos limitados 16 No planejamento regional Na logística No custo/organização de transportes Na localização da rede de distribuição Na designação de equipes Em problemas de mistura de componentes Ao se fazer uso do algoritmo da programação linear, busca-se responder questões do tipo (Andrade, 2009): Considerando as presentes condições de produção, ou seja, o cenário real, quais produtos e que quantidade, entre vários, devem ser produzidos para se obter o maior lucro possível? Para atender determinadas especificações (restrições; limitações), qual é a composição da mistura (por exemplo: do alimento; da ração; da tinta...) que corresponde ao custo mínimo? Definidas as localizações da produção, dos fornecedores e dos pontos de consumo, como estabelecer os circuitos de distribuição de modo a minimizar o custo total? Ou minimizar o tempo total? Definidas as condições de trabalho, como designar o contingente de mão de obra entre as diferentes tarefas e especialidades, com o objetivo de minimizar as despesas ou maximizar a eficiência? Definidas as condições de trabalho, como designar os equipamentos para atividades de forma a minimizar o tempo de operação ou minimizar as despesas? Conhecido o valor nutricional dos alimentos que compõem uma ração, qual quantidade de cada um deve ser usada a fim de satisfazer condições nutricionais mínimas e dar ao animal o crescimento desejado ao custo mínimo? Considerando determinadas condições de produção, quais insumos são plenamente usados? Quais insumos possuem estoque/disponibilidade para uso? Forma-padrão: diz-se que um problema de programação linear está na forma padrão se a formulação matemática está no seguinte modelo: Maximizar = 1 1 + 2 2 + ⋯ + , 17 sujeito às restrições 11 1 + 12 2 + ⋯ + 1 ≤ 1 21 1 + 22 2 + ⋯ + 2 ≤ 2 .................................................. 1 1 + 2 2 + ⋯ + ≤ e 1 ≥ 0, 2 ≥ 0, ..., ≥ 0 A terminologia comum para o modelo de programação linear é (Hillier; Lieberman, 2010): Função objetivo: é a função 1 1 + 2 2 + ⋯ + que está sendo maximizada. Restrições: são as limitações do tipo 1 1 + 2 2 + ⋯ + ≤ , com ( = 1, 2, … , ). Restrições de não negatividade (ou condições não negativas): ≥ 0, com ( = 1, 2, … , ). Constantes numéricas (números): , e . Variáveis de decisão: são as variáveis independentes 1, 2, … , , que se deseja conhecer; é a variável dependente. Em um primeiro momento, você pode considerar que a forma-padrão é uma “sopa de letras”, mas não se assuste. Lembre-se que, quando se inicia o estudo de um assunto novo, tudo parece difícil e complicado, mas, com o desenvolvimento do tema, a terminologia perderá o mistério e se tornará mais familiar. Você estudou outras disciplinas „diferentes‟ e superou, não é verdade? Esta também será superada. Prosseguindo, Hillier e Lieberman (2010) apresentam de forma didática outras formas legítimas que podem fazer parte de problemas de programação linear. São as seguintes: 1. Minimizar em vez de maximizar a função objetivo: Minimizar = 1 1 + 2 2 + ⋯ + . 2. Algumas restrições com desigualdades do tipo maior do que ou igual a: 1 1 + 2 2 + ⋯ + ≥ , para alguns valores de i, com ( = 1, 2, … , ). 3. Algumas restrições na forma de equação: 18 1 1 + 2 2 + ⋯ + = , para alguns valores de i, com ( = 1, 2, … , ). 4. Eliminar as restrições não negativas para algumas das variáveis de decisão: irrestrita em sinal para alguns valores de j, com ( = 1, 2, … , ). Os autores destacam que qualquer problema que misture algumas dessas outras formas legítimas com as partes remanescentes do modelo na forma-padrão ainda será um problema de programação linear. Entretanto, em razão dos objetivos da disciplina, os problemas a serem resolvidos serão os mais simples e didáticos possíveis. Hipóteses: a resolução de problemas de programação linear é referenciada nas seguintes hipóteses (Lachtermacher, 2007; Hillier; Lieberman, 2010): Proporcionalidade: o valor da função objetivo é diretamente proporcional ao nível de atividade de cada variável de decisão. Essa hipótese descarta qualquer expoente que não seja 1 para qualquer variável em qualquer termo de qualquer função (seja a função objetivo ou a função que se encontra do lado esquerdo na declaração de uma restrição). Aditividade: as variáveis de decisão são entidades totalmente independentes, não pode haver interdependência entre elas, isto é, não pode haver termos cruzados (termos que envolvem o produto de duas ou mais variáveis), tanto na função objetivo como nas restrições. Toda função em um modelo de programação linear (seja a função objetivo ou a função que se encontra do lado esquerdo na declaração de uma restrição), é a soma das contribuições individuais das respectivas atividades. Divisibilidade: qualquer variável de decisão pode assumir quaisquer valores, inclusive valores fracionários. Certeza: pressuposto que todos os parâmetros do modelo (as constantes aij, bi e cj) são constantes conhecidas. Em aplicações reais, a hipótese da certeza raramente é satisfeita de forma precisa. Como haverá sempre um nível de incerteza, é importante realizar a análise de sensibilidade após uma solução ter sido classificada como ótima segundo os valores de parâmetros assumidos. 19 Saiba mais Agora, leia com atenção o Item 2.1 do livro texto. Na leitura, identifique a terminologia e o vínculo com o modelo de programação linear. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788544302194/pa ges/27>. BARBOSA, M. A.; ZANARDINI, R. A. D. Iniciação à pesquisa operacional no ambiente de gestão. 2. ed. rev., atual. e ampl. Curitiba: Intersaberes, 2014. Se deseja ampliar o conhecimento sobre programação linear, acesse: <https://www.youtube.com/watch?v=IqVlEplz9G4>. Alguns conceitos apresentados no vídeo serão abordados na próxima aula. NA PRÁTICA A partir do que foi exposto nesta primeira aula, apresente no fórum um problema de forma mais detalhada possível e que seja recorrente em uma empresa de sua escolha. Em seguida, discuta com os demais alunos sobre a possibilidade de se empregar as fases de um estudo de pesquisa operacional. Como as fases seriam descritas? Como operacionalizar tais fases? Leia o caso de ensino sugerido, faça uma análise da situação e depois responda o solicitado. Terminadas a atividade de estudo, a análise e a elaboração da proposta de solução para o caso de ensino, você receberá uma resposta possível para o caso de ensino, proposta pelo professor que o elaborou. Orientações para realizar a atividade: 1. Leia o caso de ensino atentamente e os temas da rota. 2. Identifique no texto desta rota de aprendizagem quais conceitos-chaves que você utilizará para responder as questões apresentadas no caso de ensino. 3. Compreenda que os conceitos são subsídios/ferramentas que te auxiliarão na solução do problema apresentado. 4. Bons estudos e bom trabalho! Caso de Ensino nº 1: A padaria Le Petit Pain A Le Petit Pain está localizada em um bairro onde a maioria da população é composta por pessoas com mais de 60 anos. Os pães vendidos pela padaria 20 são famosos na cidade e, por isto, no fim do dia, há clientes de outros bairros, o que tem incrementado as vendas e também as reclamações dos moradores do bairro em razão do tempo gasto em fila. Os moradores locais preferem comprar na LePetit Pain em razão da sua localização, mas, para evitar as filas, anteciparam o horário de suas compras, no período da tarde. Agora, a mudança da frequência gerou um problema para a gerência da padaria. A Le Petit Pain nem sempre consegue produzir a quantidade adequada de pães para atender os moradores do bairro nem os outros consumidores, pois há dias em que há falta de pães, e em outros dias há excesso de produção de pães. Se você fosse o gerente da Le Petit Pain, que ações desenvolveria para resolver o problema? Respostas possíveis: Para o caso de ensino apresentado, é possível propor soluções em dois cenários. Cenário 1: Redução do tempo gasto em fila (recurso escasso: caixas) Avaliar a situação atual, levantando dados referentes a: chegada de clientes (quantidade, horário e dia da semana); tempo gasto em fila; tempo gasto pelo caixa em atendimento; Realizar o tratamento estatístico dos dados, preferencialmente por dia da semana e horário. Soluções possíveis: o Aumentar o número de caixas no período de maior frequência; o Separar pelo menos um caixa como preferencial no período de maior frequência; o Treinar os caixas a fim de reduzir o tempo de atendimento; Verificar se a solução implementada resolve o problema. Cenário 2: Produção de quantidade adequada de pães (recurso escasso: pães) Avaliar a situação atual, levantar dados referentes a: chegada de clientes (quantidade, horário e dia da semana); produção de pães (quantidade por horário e dia da semana); Realizar o tratamento estatístico dos dados, preferencialmente por dia da semana e horário. Solução possível: produzir a quantidade de pães em compatibilidade com a provável frequência dos clientes. Verificar se a solução implementada resolve o problema. FINALIZANDO Nesta primeira aula, foram apresentados diversos conceitos sobre PO, provavelmente conceitos desconhecidos. Entre o que foi apresentado, é importante realçar as seguintes ideias-chave: os recursos são escassos, mas podem ser melhor empregados/alocados; para obter uma solução mais consistente para um problema, é necessário dispor de dados para empregá-los 21 em uma metodologia que possua uma sequência de etapas organizadas (um algoritmo) e bem definidas; modelos já elaborados são melhor empregados para solucionar problemas mais simples; e usar um processo de modelagem para solucionar problemas mais complexos. Por fim, o estudo de Programação Linear foi iniciado e será aprofundado nas próximas aulas. Os objetivos do caso de ensino são fazer o aluno elaborar a solução conforme as fases de um estudo de PO e identificar intuitivamente qual é o recurso escasso. Como o problema foi previamente definido, esperava-se que o aluno identificasse a necessidade de dispor de dados quantitativos para poder elaborar propostas de solução mais consistentes. 22 REFERÊNCIAS ANDRADE, E. L. de. Introdução à pesquisa operacional: métodos e modelos para análise de decisões. 4. ed. Rio de Janeiro: LTC, 2009. CHWIF, L.; MEDINA, A. C. Modelagem e simulação de eventos discretos: teoria & prática. 2. ed. São Paulo: Ed dos Autores, 2006. CORRAR, L. J.; THÉOPHILO, C. R.; BERGMANN, D. R. Programação linear. In: CORRAR, L. J.; THÉOPHILO. Pesquisa operacional para decisão em contabilidade e administração: contabilometria. 1. ed. 3. reimp. São Paulo: Atlas, 2007. HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9. ed. Porto Alegres: McGraw-Hill, 2010 LACHTERMARCHER, G. Pesquisa operacional na tomada de decisões: modelagem em Excel. 4. ed. Rio de Janeiro: Elsevier, 2009. MICHAELIS. Dicionário da língua portuguesa. São Paulo: Editora Melhoramentos, 2001. SARGENT, R. G. Verification and Validation of Simulation Models. In: Proceedings of 2014 Winter Simulation Conference, 2014, Savannah, GA. pp 118-131. Disponível em: <http://informssim.org/wsc14papers/includes/files/013.pdf>. Acesso em: 22 nov. 2017. SOCIEDADE Brasileira De Pesquisa Operacional (SOBRAPO). Disponível em: <http://www.sobrapo.org.br/>. Acesso em: 22 nov. 2017. 23 PESQUISA OPERACIONAL AULA 2 Prof. José de Souza Leal Neto CONVERSA INICIAL Na aula passada, começamos o estudo de Pesquisa Operacional (PO), e foram apresentados diversos conceitos relacionados à disciplina. Lembre-se que o objetivo da PO é fazer com que as operações sejam eficientes e eficazes. Para isso, deve-se gerenciar os recursos críticos, os recursos escassos. Ao final da aula, foi apresentada a Programação Linear (PL), cujo estudo será prosseguido agora. Nesta segunda aula, haverá menos conceitos e mais aplicações práticas. As aplicações serão inicialmente simples para que seja possível construir um conhecimento a respeito do processo de solução (algoritmo) proposto pela PL. Em seguida, os exemplos de aplicações se tornarão mais elaborados, mas não se espera exaurir, no tempo disponível para a disciplina, o que a PL pode proporcionar. O passo inicial será “como” realizar a construção do modelo matemático de PL, na forma-padrão, de um problema apresentado, ou seja, “como” identificar as restrições existentes e transformá-las em inequações matemáticas, bem “como” identificar o que se deseja conhecer (variáveis de decisão) e usar isso na construção da função objetivo. O passo seguinte é um didático e tem por objetivo fazer com que o aluno compreenda o processo de solução adotado pela PL. Serão apresentadas soluções gráficas para problemas com duas variáveis de decisão. No “mundo real” é praticamente inusitado encontrar um problema que possua apenas duas variáveis de decisão, mas tal situação será adotada para fins didáticos. Lembre-se que o fato de ser possível elaborar de um modelo matemático de PL não significa que haja uma solução. Então, mãos à obra, vamos começar a segunda aula de Pesquisa Operacional. CONTEXTUALIZANDO As empresas possuem diversos tipos de problemas para os quais os administradores devem encontrar soluções. Entre esses diversos tipos de problema, há aqueles que podem ser solucionados empregando a modelagem de programação linear. Para o administrador saber se a modelagem de programação linear é apropriada para o problema, ele deve, em primeiro lugar, conhecer de que tipo 2 de resposta necessita. Se for um valor numérico definido, o uso de PL poderá atender o escopo do problema. Conforme apresentado na aula anterior, a PL possui na forma-padrão uma função objetivo = 1 1 + 2 2 + ⋯ + , que pode ser de maximização ou de minimização, conforme o tipo do problema. Caso haja solução para o problema de PL, a função objetivo Z será expressa por um valor numérico. Prosseguindo, é necessário determinar quais são as variáveis de decisão 1, 2, … , que deverão compor a função objetivo. Não se pode esquecer que uma modelagem não deve gerar um modelo simples em demasia nem complexo por excesso. Assim, uma proposta é empregar o método da curva ABC para identificar as variáveis de decisão (itens) que possuem maior influência na função objetivo. Por fim, o administrador deve identificar as restrições a que estão sujeitas as variáveis de decisão no contexto do problemaem estudo. Estas restrições são expressas geralmente por inequações. Assim, será possível escrever o contexto do problema e construir o modelo do problema de PL na forma-padrão. As etapas comentadas acima estão inseridas nas fases de estudo do problema, levantamento e tratamento de dados e definição da metodologia a ser empregada. Consequentemente, a fase seguinte é a solução do problema. Nesta aula, será apresentado o processo de se estruturar um problema de PL, ou seja, escrever o enunciado da situação-problema proposta em sentenças matemáticas, conforme a forma-padrão da formulação matemática da PL, bem como solucionar graficamente o problema. A solução gráfica será limitada a duas variáveis de decisão para melhor compreensão da lógica de solução proposta pela programação linear. TEMA 1 – MODELAGEM EM PROGRAMAÇÃO LINEAR Para “transformar” uma situação-problema para uma equação matemática, é necessário um pouco de experiência, e a experiência vem com a prática. Assim, para se obter experiência, deve-se iniciar a prática com problemas mais simples, e, após o domínio do conceito e da rotina de atividades, será mais fácil trabalhar com problemas de maior complexidade. Não é objetivo desta disciplina abstrair um problema a partir de um contexto específico, mas, a partir do enunciado de um problema, realizar a modelagem de um problema de programação linear. A modelagem se tornará de mais fácil execução se você 3 conhecer quais são os elementos necessários para elaborar as sentenças matemáticas que compõem a forma-padrão de um problema de programação linear. Assim, no presente tema, serão desenvolvidos exercícios de modelagem em programação linear. Na forma-padrão: em um primeiro momento, pode haver dificuldade para se obter as sentenças matemáticas que vão compor a forma-padrão de um determinado problema de PL. Somente praticando a modelagem de problemas de PL é que se conseguirá superar a dificuldade de interpretação e ser capaz de identificar os dados necessários para a formulação matemática na forma-padrão. A tarefa se tornará mais fácil se for realizada com critério. Logicamente, é necessário ler o problema para compreender o contexto. Recomenda-se uma segunda leitura com o objetivo de identificar os verbos existentes e, principalmente, o que é solicitado – uma pergunta –, o objetivo do estudo. Em regra, a solicitação do problema determina as variáveis de decisão e, por conseguinte, poder-se-á construir a função objetivo, que é a expressão matemática por meio da qual se relacionam as variáveis de decisão e o objetivo a ser atingido (Corrar; Theóphilo; Bergmann, 2007). Cada variável de decisão deve ser identificada por escrito, e cada variável deve ser usada na mesma unidade de medida. Após a definição da função objetivo, é a vez de construir as expressões matemáticas das restrições existentes. As restrições são basicamente as limitações dos recursos associados a cada variável de decisão, ou, na abordagem de Corrar, Theóphilo e Bergmann (2007), “as restrições são limitações impostas sobre os possíveis valores que podem ser assumidos pelas variáveis de decisão”. Para os problemas de PL de Maximização tem que haver pelo menos uma restrição do tipo ≤ (menor ou igual), e para os problemas de Minimização tem que haver pelo menos uma restrição do tipo ≥ (maior ou igual). Para finalizar, um cuidado e uma dica. O cuidado necessário é que devemos deixar todas as constantes com valores positivos, mesmo que seja necessário modificar o sinal da inequação. A dica é: no processo de construir a forma-padrão, fazer uma tabela – mesmo que de forma mental – que tenha em sua primeira linha as variáveis de decisão, e que cada variável de decisão determine uma coluna. As linhas inferiores deverão ser preenchidas pelas restrições e em harmonia com os dados relativos para cada variável de decisão (coluna). Agora, procure identificar essas orientações nos exemplos abaixo. 4 Exemplo 1: Problema de maximização. Para iniciar o estudo de problemas de PL, escolhemos um exemplo simples, que permitirá visualizar a construção do modelo de PL na forma-padrão, mas nem sempre os problemas são apresentados de forma estruturada como o proposto por Corrar, Theóphilo e Bergmann (2007) a seguir. A indústria Maximóveis fabrica dois tipos de produtos: cadeiras e mesas. Os produtos apresentam as margens de contribuição por unidade conforme a Tabela 2.1. Tabela 2.1 – Margens de contribuição unitárias dos produtos Produto Margem de contribuição por unidade ($) Cadeiras 10 Mesas 8 Os produtos são processados por dois departamentos: montagem e acabamento. Ao passar por esses departamentos, cada unidade do produto consome determinado número de horas, conforme indicado na Tabela 2.2. Tabela 2.2 – Consumo de tempo nos departamentos Departamento Consumo de horas pelos produtos (por un.) Cadeiras Mesas Montagem 3 3 Acabamento 6 3 Os departamentos apresentam, contudo, limitação em sua capacidade produtiva, como mostra a Tabela 2.3. TABELA 2.3 – Capacidade produtiva dos departamentos Departamento Capacidade máxima disponível em horas Montagem 30 Acabamento 48 Deseja-se saber qual é a melhor combinação possível de cadeiras e mesas a serem produzidas, de forma a obter a maior margem de contribuição total. Solução proposta: Antes de resolver o problema de programação linear, é necessário elaborar a formulação matemática para obter forma-padrão, conforme descrito a seguir. 5 3. Identificar as variáveis de decisão ( 1, 2): as variáveis de decisão são as quantidades que se deseja conhecer. De uma forma irreverente, para identificar as variáveis de decisão, às vezes basta fazer a pergunta: “show me the money?”. No problema em estudo, o que está associado ao dinheiro? Quais itens aumentam a margem de contribuição? Cadeiras e mesas. Portanto, temos 1: cadeiras; e 2: mesas. A unidade de medida para expressar a quantidade de cadeiras e de mesas é “unidade” (o uso de 1 e de 2 para designar cadeiras ou mesas é indiferente). 4. Definir a função objetivo: a função objetivo = 1 1 + 2 2 + ⋯ + será então, Maximizar = 10 1 + 8 2. Verifique que cada unidade de cadeira participa com $10 e cada unidade de mesa participa com $8 para a margem de contribuição da empresa. Assim, se soubermos qual é a combinação ótima de quantidade de cadeiras e de quantidade de mesas a serem produzidas e vendidas, conheceremos a maior margem de contribuição total. Por isso, o presente problema de PL é de maximização. 5. Expressar matematicamente as restrições existentes: a partir das Tabelas 2.2 e 2.3, verifica-se que a produção de cadeiras e mesas depende dos departamentos de montagem e de acabamento. Tais departamentos produzem um ou outro produto, ou seja, cadeiras e mesas competem pela disponibilidade de tempo nestes departamentos, os quais possuem uma capacidade máxima disponível. Então, a função matemática que expressa a restrição do departamento de montagem é 3 1 + 3 2 ≤ 30, e a que expressa a restrição do departamento de acabamento é 6 1 + 3 2 ≤ 48. Observe que as constantes são positivas. 6. Obter a forma-padrão: conforme apresentado anteriormente, é possível imaginar o uso de uma tabela esquemática, dado a sua praticidade para estruturar o problema de PL na forma-padrão. Espera-se que, com o tempo, a tabela seja dispensável, por se saber como compor o problema de PL na forma-padrão. Assim, a tabela teria o seguinte formato: Função objetivo Maximizar Z= 10 1 + 8 2 Sujeito às restriçõesMontagem 3 1 + 3 2 ≤ 30 Acabamento 6 1 + 3 2 ≤ 48 e 1 ≥ 0; 2 ≥ 0 6 O problema apresentado acima possui a formulação matemática, na forma-padrão, para ser empregado no algoritmo da PL na seguinte forma: Maximizar = 10 1 + 8 2, sujeito às restrições Montagem 3 1 + 3 2 ≤ 30 Acabamento 6 1 + 3 2 ≤ 48 5. 1 ≥ 0, 2 ≥ 0 sendo, 1: cadeiras (un.), e 2: mesas (un.). Pode ser que você tenha estranhado o acréscimo de informações na estrutura na forma-padrão. As informações foram acrescidas para facilitar a identificação das restrições, bem como das variáveis de decisão. A estrutura inicial da forma-padrão foi respeitada. Exemplo 2: Problema de maximização. No desenvolvimento deste novo exemplo, o roteiro de modelagem será observado, mas com menos observações. Na leitura inicial, procure compreender e identificar o que é solicitado. Identifique se é um problema de maximização ou de minimização. Na segunda leitura, atente para os verbos e identifique as variáveis de decisão e as suas restrições. Por fim, estruture mentalmente uma tabela, com as variáveis de decisão no topo das colunas e as restrições preenchendo as linhas. Então, considere o problema a seguir. Um artesão é especializado em pintura decorativa de pratos cerâmicos e vende seu artesanato em uma feira que funciona todas as noites. Ele realiza uma pintura básica em pratos rústicos e grandes e uma pintura refinada nos pratos delicados e pequenos. Os pratos grandes são vendidos por $ 4,00, e os pratos pequenos, por $ 6,00. Ele consegue vender pelo menos 3 pratos grandes e somente 4 pratos pequenos por noite. Os pratos grandes são pintados em 54 minutos, e os pratos pequenos são pintados em 1 hora e 36 minutos. Antes das vendas noturnas, o artesão desenvolve seus projetos em jornadas diárias de trabalho de 8 horas. Para melhor empregar seu tempo, ele deseja saber quantos pratos de cada tipo ele precisa pintar para obter a maior receita possível. Solução proposta de modelagem do problema de programação linear: 7 Identificar as variáveis de decisão ( 1, 2). Vamos à pergunta: “show me the money?”. O artesão obtém receita vendendo pratos grandes e pratos pequenos. Portanto, temos, 1: pratos cerâmicos grandes; e 2: pratos cerâmicos pequenos. A unidade de medida para expressar a quantidade de pratos é “unidade” (o uso de 1 e de 2 para designar pratos grandes ou pratos pequenos é indiferente). Definir a função objetivo: como o artesão deseja aumentar a sua receita, o problema de PL é de maximização. A função objetivo = 1 1 + 2 2 + ⋯ + será então, maximizar = 4 1 + 6 2. Expressar matematicamente as restrições existentes: uma restrição é o tempo disponível. Assim, o artesão possui a seguinte restrição: 0,9 1 + 1,6 2 ≤ 8, com o tempo em horas, ou, 54 1 + 96 2 ≤ 480, com o tempo em minutos. A outra restrição é referente à venda pratos grandes, que é expressa como: 1 1 + 0 2 ≥ 3, pois o artesão vende no mínimo 3 pratos por noite. A última restrição é referente à venda de pratos pequenos, que possui a seguinte formulação: 0 1 + 1 2 ≤ 4. Você deve atentar quando for tratar de demanda, pois esta deve, a priori, ser trabalhada por produto para ser possível identificar a quantidade específica em que cada produto deve ser produzido. Se a demanda for tratada como um mix de produtos, a informação das quantidades a serem produzidas provavelmente será deturpada. Obter a forma-padrão: a partir dos dados anteriores, é possível montar o seguinte modelo matemático para o problema de programação linear: Maximizar = 4 1 + 6 2, sujeito às restrições Tempo de trabalho 0,9 1 + 1,6 2 ≤ 8 Pratos grandes (venda) 1 1 + 0 2 ≥ 3 Pratos pequenos (venda) 0 1 + 1 2 ≤ 4 e1 ≥ 0, 2 ≥ 0 sendo, 1: pratos grandes (un.), e 2: pratos pequenos (un.). 8 Saiba mais Leia o Item 2.2 do livro texto e estude os exercícios resolvidos. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788544302194/pa ges/29>. BARBOSA, M. A.; ZANARDINI, R. A. D. Iniciação à pesquisa operacional no ambiente de gestão. 2. ed. rev., atual. e ampl. Curitiba: Intersaberes, 2014. Leia também as páginas 6 e 7 (Item 2.1) do TAHA e procure resolver pelo menos um problema do conjunto de problemas 2.1ª. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788576051503/pa ges/7>. TAHA, H. A. Pesquisa Operacional: uma visão geral. 8. ed. São Paulo: Pearson Prentice Hall, 2008. Para consolidar conceitos de modelagem, assista ao vídeo no endereço a seguir: <https://www.youtube.com/watch?v=4AbjF8Lehe8>. TEMA 2 – VARIÁVEIS DE DECISÃO E RESTRIÇÃO NO PLANO CARTESIANO Neste momento é necessário relembrar alguns conceitos matemáticos que serão empregados para desenvolver uma forma de resolver problemas de programação linear, que é a solução gráfica. Não há como fugir da matemática, mesmo no curso de Administração. Lembre-se de que uma gestão será mais eficiente e eficaz se for baseada em dados numéricos e, principalmente, na sua interpretação, que se torna mais fácil se for realizada na forma gráfica. Assim, os conceitos matemáticos revistos no presente tema também serão úteis para serem aplicados em outras disciplinas do curso, além de melhorar o desempenho das funções de administrador. O plano cartesiano. Para melhor compreensão do Tema 3, é necessário relembrar conceitos básicos de matemática. O sistema de coordenadas cartesianas (plano cartesiano) é usado para fazer a localização gráfica de pares de números reais e tem por base duas retas perpendiculares. O eixo horizontal 5. denominado eixo dos “x”, e o eixo vertical é denominado o eixo dos “y”. Para locar um ponto P, um ponto qualquer, no plano cartesiano é usado um par ordenado ( , ), onde determina a posição de P no eixo x, e determina a posição de P no eixo de y. O primeiro termo do par ordenado, 9 denominado de abscissa, é sempre usado no eixo horizontal – eixo dos x –, e o segundo termo do par ordenado, denominado ordenada, é sempre usado no eixo vertical – eixo dos y. Também é possível locar uma reta no plano cartesiano a partir de uma relação entre y e x. Veja os exemplos na Figura 1 de locação de ponto e de reta: o ponto P (3, 5) locado no plano cartesiano, possui igual a 3 e igual a 5; a reta + 2 = 4, com ≥ 0 e ≥ 0 pode ser locada a partir dos pontos (0, 4) e (2, 0). Para obter tais pontos pertencentes à referida reta, basta fazer = 0 na reta, para obter = 4 e, em seguida, fazer = 0 na reta, para obter = 2. Figura 1 – Exemplo de locação de ponto e de reta Figura 2 – Exemplo de locação de retas As variáveis de decisão e restrições no plano cartesiano: o uso do plano cartesiano na construção de solução gráfica de um problema de PL permitirá a visualização e a compreensão do significado de restrições. Por ora, vamos acrescer mais alguns conceitos de matemática. Inicialmente, faremos algumas adaptações nas designações dos eixos. 10 De forma indiferente, podemos designar tanto o eixo como eixo 1 e o eixo como eixo 2; como, o eixo como eixo 2 e o eixo como eixo 1. O resultado final será o mesmo. No entanto, a fim de evitar confusão, adotaremos a opção de designar o eixo como eixo 1 e o eixo como eixo 2. Na Figura 2 há diferentes exemplos de locação de retas de provenientes das equações de restrições. No momento, vamos nos ater apenas à locação. Assim, sejam as seguintes equações a serem plotadas no planocartesiano: 2,5 1 + 4 2 = 10 3 1 + 2 2 = 9 2 = 3 d.1 = 4,5 A equação c. é uma reta horizontal, com valor da ordenada constante e igual a 3. A equação d. é uma reta vertical, com valor da abscissa constante e igual a 4,5. A reta a ser obtida a partir da equação a. pode ser traçada definindo dois pontos pertencentes à reta: um no eixo das ordenadas ( 2), que é obtido fazendo 1 = 0 e, consequentemente, a equação ficará 4 2 = 10, o que definirá o valor de 2 = 104 = 2,5, assim o primeiro ponto será o par ordenado (0, 2,5). Para se determinar o outro ponto, faz-se o raciocino idêntico, só que em relação ao eixo das abscissas ( 1), então, o ponto é obtido fazendo 2 = 0 e, consequentemente, a equação ficará 2,5 1 = 10, o que definirá o valor de 1 = 2,510 = 4, assim o segundo ponto terá o par ordenado (4, 0). De forma semelhante à reta anterior, a reta obtida a partir da equação b. pode ser traçada a partir da definição de dois pontos que lhe pertencem: um no eixo das ordenadas ( 2), que é obtido fazendo 1 = 0 e, consequentemente, a equação ficará 2 2 = 9, o que definirá o valor de 2 = 29 = 4,5, assim o primeiro ponto será o par ordenado (0, 4,5). Para se determinar o outro ponto, faz-se o raciocino idêntico, só que em relação ao eixo das abscissas ( 1), então o ponto é obtido fazendo 2 = 0 e, consequentemente, a equação ficará 3 1 = 9, o que definirá o valor de 1 = 39 = 3, assim o segundo ponto terá o par ordenado (3, 0). Após a locação das retas será possível calcular as suas interseções, os seus pontos comuns, os pares ordenados que pertencem simultaneamente às 11 duas retas. Agora, vamos calcular algebricamente os pares ordenados de P1 e P2, apresentados na Figura 2. a. Cálculo de P1: sejam as retas, 3 1 + 2 2 = 9 2 = 3 como 2 = 3 já está definida, basta fazer a substituição de seu valor na outra equação e se obter o valor de 1. Assim, tem-se 3 1 + 2 ∙ (3) = 9 → 3 1 = 9 − 6 → 1 = 33 = 1. Portanto, o par ordenado de P1 é (1, 3). b. Cálculo de P2: sejam as retas, 2,5 1 + 4 2 = 10 3 1 + 2 2 = 9 Para determinar o par ordenado de P2, uma forma de solução prática e rápida consiste em multiplicar linearmente uma ou as duas equações por um valor (multiplicar todos os termos da equação pelo valor definido), de forma a ser possível eliminar uma das incógnitas após somar os termos semelhantes das equações. Operacionalizando estas etapas, temos: a. Se o objetivo for eliminar 2, será necessário multiplicar todos os termos da segunda equação por um múltiplo do coeficiente de 2 a fim de se igualar os valores dos coeficientes da variável 2; o valor é negativo porque os coeficientes possuem o mesmo sinal. As operações são: 2,5 1 + 4 2 = 10 2,5 1 + 4 2 = 10 somando as equações, temos: 3 + 2 = 9 (−2) −6 − 4 = −18 −3,5 = −8 ∴ = 8 ≅ 1 2 1 2 1 1 3,5 2,29 substituindo o valor de = 8 na segunda equação, tem-se 3 ( 8 ) + 2 = 9 → 1 3,5 3,5 2 2 = 9 − 24 → 2 = (9 3,5)−24 → = 7,5 = 7,5 ≅ 1,07 . Portanto, o par 2 3,5 2 3,5 2 (2 3,5) 7 ordenado de P2 é (2,29, 1,07). b. Se o objetivo for eliminar 1, será necessário multiplicar todos os termos da primeira equação pelo coeficiente de 1 da segunda equação e 12 multiplicar todos os termos da segunda equação pelo coeficiente de 1 da primeira equação. Um dos dois valores de multiplicação terá que ser negativo quando os sinais dos coeficientes da variável a ser eliminada forem iguais. As operações são: 2,5 1 + 4 2 = 10 (3) 7,5 1 + 12 2 = 30 somando as equações, temos: 3 + 2 = 9 (−2,5) −7,5 − 5 = −22,5 7 = 7,5 ∴ = 7,5 ≅ 1,07 1 2 1 2 2 2 7 e após as devidas substituições, o par ordenado de P2 é igual ao calculado na letra a) acima. A representação e a interpretação das inequações (restrições) serão desenvolvidas no Tema 3. Saiba mais Para entender relembrar os conceitos de reta com mais detalhe, acesse o endereço a seguir e assista ao vídeo: <https://www.youtube.com/watch?v=- F01tW-kVOE>. TEMA 3 – SOLUÇÃO GRÁFICA Após a elaboração do modelo matemático de programação linear na forma-padrão, pode-se empregar um processo de resolução do problema. A solução gráfica é um processo e é usada como referencial didático no estudo da programação linear, porque a sua aplicação é inviável nos problemas reais, que possuem mais de três variáveis de decisão. No entanto, a solução gráfica permite ao aluno visualizar em uma perspectiva gráfica as limitações impostas pelas diferentes restrições (inequações) e o processo de solução do problema, o que será abordado neste tema. Solução gráfica: a solução gráfica permite apresentar no máximo três variáveis de decisão, porém sua montagem é bastante trabalhosa. Entretanto, soluções gráficas serão usadas para fins didáticos de problemas com duas variáveis de decisão, por ser de fácil compreensão e visualização. Vale lembrar o que foi comentado anteriormente, de que dificilmente haverá um problema de programação linear com apenas duas variáveis de decisão no “mundo real”. Na elaboração da solução gráfica, apenas a parte (quadrante) do plano cartesiano que possui abscissa e ordenada “positivas” será usada. Isso se deve 13 ao fato de que as variáveis de decisão deverão ser sempre maiores ou iguais a zero ( 1 ≥ 0 e 2 ≥ 0). Um roteiro simples para elaborar a solução gráfica é o seguinte: a. Traçar as retas originárias das inequações que definem as restrições; b. Determinar os pontos de interseção entre as retas (esta etapa pode ser executada após a letra c., para se calcular apenas os pontos de interesse); c. Identificar a área que as inequações definem como verdade (área comum às inequações): a área determina todos os pontos que atendem as inequações; e d. De forma pragmática, testar as possíveis soluções (vértices) para encontrar o valor da função objetivo. Solução gráfica do exemplo 1. A forma-padrão do problema do exemplo 1 é a seguinte: Maximizar = 10 1 + 8 2, sujeito às restrições Montagem 3 1 + 3 2 ≤ 30 Acabamento 6 1 + 3 2 ≤ 48 e 1 ≥ 0, 2 ≥ 0 sendo, 1: cadeiras (un.), e 2: mesas (un.) Etapas da solução: a. Traçar as retas originárias das inequações que definem as restrições: determinar um par ordenado no eixo das abscissas e um para ordenado no eixo das ordenadas. Em seguida, locar os pontos e traçar a reta. - montagem: 3 1 + 3 2 = 30, com 1 = 0, tem-se 3 2 = 30 → 2 = 303 = 10 Assim, um par ordenado é (0, 10). Fazendo 2 = 0, tem-se 3 1 = 30 → 1 = 303 = 10. Assim, o outro par ordenado é (10, 0). - acabamento: 6 1 + 3 2 = 48, com 1 = 0, tem-se 3 2 = 48 → 2 = 483 = 16. Assim, um par ordenado é (0, 16). Fazendo 2 = 0, tem-se 6 1 = 48 → 1 = 48 6 = 8. Assim, o outro par ordenado é (8, 0). 14 b. Determinar o ponto de interseção entre as retas: 3 1 + 3 2 = 30(−2) −6 1 − 6 2 = −60 somando as equações, temos: 6 + 3 = 48 6 + 3 = 48 −3 = −12 ∴ = 12 = 4 1 2 1 2 2 2 3 fazendo 2 = 4 na segunda equação, tem-se 6 1 + 3 (4) = 48 → 6 1 = 48 − 12 → 1 = 366 = 6 . Portanto, o par ordenado é (6, 4). A Figura 3a apresenta o plano cartesiano com as retas e o ponto de interseção. Figura 3a – Retas e ponto de interseção15 Figura 3b – Área que atende as inequações c. Identificar a área que as inequações definem como verdade (área comum às inequações): para isso, basta substituir o ponto (0, 0) na inequação, se o valor a esquerda for menor que o valor da direita da inequação, o ponto (0, 0) faz parte da área que atende a inequação. Assim, 3 (0) + 3(0) = 0 ≤ 30 (Verdadeiro) 6(0) + 3(0) = 0 ≤ 48 (Verdadeiro) Portanto, a área que atende as duas inequações é apresentada na Figura 3b. A área hachurada (preenchida) é a que atende simultaneamente as duas inequações, e nela estão localizadas todas as soluções possíveis. d. De forma pragmática, testar as possíveis soluções (vértices) para encontrar o valor da função objetivo. O que se deseja saber é: qual é a melhor combinação possível de cadeiras e mesas a serem produzidas, de forma a obter a maior margem de contribuição total. Para isso, a função objetivo é maximizar = 10 1 + 8 2, consequentemente a solução estará nos pontos mais distantes da origem (0, 0), porque se deseja a maior contribuição. Os pontos mais afastados são: (0, 10): = 10(0) + 8(10) = 80 (6, 4): = 10(6) + 8(4) = 92 (8, 0): = 10(8) + 8(0) = 80 e. Solução: para se obter a maior contribuição, deve-se produzir 6 cadeiras e 4 mesas. A maior contribuição será $92,00. 16 Solução gráfica do exemplo 2. A solução será menos comentada do que a realizada no exemplo 1 por ser a mesma sequência de eventos. A forma- padrão é: Maximizar = 4 1 + 6 2, sujeito às restrições Tempo de trabalho 0,9 1 + 1,6 2 ≤ 8 Pratos grandes (venda) 1 1 + 0 2 ≥ 3 Pratos pequenos (venda) 0 1 + 1 2 ≤ 4 e1 ≥ 0, 2 ≥ 0 sendo, 1: pratos grandes (un.), e 2: pratos pequenos (un.). Etapas da solução: a. Traçar as retas originárias das inequações que definem as restrições: determinar um par ordenado no eixo das abscissas e um para ordenado no eixo das ordenadas. Em seguida, locar os pontos e traçar a reta. - tempo: 0,9 1 + 1,6 2 = 8, com 1 = 0, tem-se 2 = 1,68 = 5. Assim, um par ordenado é (0, 5). Fazendo 2 = 0, tem-se 1 = 0,98 ≅ 8,89. Assim, o outro par ordenado é (8,89, 0). - pratos grandes: é a reta 1 = 3. - pratos pequenos: é a reta 2 = 4. Determinar o ponto de interseção entre as retas: 0,9 1 + 1,6 2 = 8 e 1 = 3, como 1 = 3, tem-se 0,9(3) + 1,6 2 = 8 1,6 2 = 8 − 2,7 ∴ 2 = 5,31,6 ≅ 3,3125. Portanto, o par ordenado é (3, 3,31). A Figura 4a apresenta o plano cartesiano com as retas e o ponto de interseção. Figura 4a – Retas e ponto de interseção 17 Figura 4b – Área que atende as inequações Identificar a área que as inequações definem como verdade (área comum às inequações): para isso, basta substituir o ponto (0, 0) na inequação e comparar o valor obtido à esquerda com o valor à direita da inequação. Se for verdadeiro, a região que possui pontos que satisfazem a inequação está localizada entre a reta e o ponto (0, 0); se falso, a região que atende a inequação está localizada após a reta, afastando-se do ponto (0, 0). Assim, 0,9(0) + 1,6(0) = 0 ≤ 8 (Verdadeiro) 1(0) + 0 2 = 0 ≥ 3 (Falso), então os valores (região) que atende inequação estão localizados à direita da reta, afastando-se do ponto (0, 0). 0 1 + 1(0) = 0 ≤ 4 (Verdadeiro) Portanto, a área que atende as três inequações é apresentada na Figura 4b. A área hachurada é a que atende as simultaneamente as três inequações, e nela estão as soluções possíveis. 18 b. De forma pragmática, testar as possíveis soluções (vértices) para encontrar o valor da função objetivo. O que se deseja saber é: quantos pratos de cada tipo são necessários pintar para se obter a maior receita possível. Para isso, a função objetivo é maximizar = 4 1 + 6 2, consequentemente a solução estará nos pontos mais distantes da origem (0, 0), porque se deseja a maior receita. Os pontos mais afastados são: (3, 3,31): = 4(3) + 6(3) = 30 (8,89, 0): = 4(8,89) + 6(0) = 35,55 c. Solução: para se obter a maior receita, o artesão deve pintar 8 pratos grande e obter $ 35,55. (o valor 3,31 significa que foram pintados 3 pratos pequenos e um ficou inacabado; o valor 8,89 significa que foram pintados 8 pratos grande e um ficou inacabado. Entretanto, apenas pratos completamente pintados podem ser vendidos, não é verdade?) Saiba mais Leia o Item 2.3 do livro texto, estude os exercícios resolvidos e resolva as questões para revisão. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788544302194/pa ges/33>. BARBOSA, M. A.; ZANARDINI, R. A. D. Iniciação à pesquisa operacional no ambiente de gestão. 2. ed. rev., atual. e ampl. Curitiba: Intersaberes, 2014. Leia o Item 2.2.1 do TAHA e procure resolver os exercícios do conjunto de problemas 2.2ª. Disponível em: <http://uninter.bv3.digitalpages.com.br/users/publications/9788576051503/pa ges/9>. TAHA, H. A. Pesquisa Operacional: uma visão geral. 8. ed. São Paulo: Pearson Prentice Hall, 2008. Acesse os links para assistir a exemplos de solução gráfica: <https://www.youtube.com/watch?v=7jMMPSXDrHs> e <https://www.youtube.com/watch?v=OJ3jIPOvw-A>. 19 TEMA 4 – TERMINOLOGIA PARA SOLUÇÕES: SOLUÇÕES INEXISTENTES, ILIMITADAS E MÚLTIPLAS O conhecimento da terminologia empregada para referenciar os diversos tipos de solução possível para problemas de programação linear facilitará a compreensão da abordagem dos diferentes autores que tratam de programação linear e inclusive o desenvolvimento desta disciplina. Assim, este tema tem por objetivo apresentar, além da terminologia de tipos de soluções, os teoremas que caracterizam a abordagem de solução, própria da programação linear. Terminologia: para tratar de tipos de soluções para modelos de programação linear, usa-se a seguinte terminologia (Lachtermacher, 2007; Hillier, Lieberman, 2010): Solução: qualquer especificação de valores para as variáveis de decisão, independentemente de ser desejável ou mesmo ser uma opção admissível. Solução viável: é aquela para a qual todas as restrições são satisfeitas. Por exemplo, na Figura 5, verifica-se que P1 e P2 são soluções viáveis. Solução inexistente: existe a possibilidade de que o problema de programação linear não possua solução viável, ou seja, não existe solução para o problema. Tal situação é apresentada na Figura 6. Solução inviável: é aquela para a qual pelo menos uma das restrições é violada. Por exemplo, na Figura 5, verifica-se que P3 não atende a restrição ≤ , e P4 não atende a restrição + ≤ . Região de soluções viáveis: é o conjunto de todas as soluções viáveis – como exemplo, a área hachurada nas Figuras 3b, 4b e 5. 20 Figura 5 – Soluções (Hillier; Lieberman, 2010) Figura 6 – Solução inexistente (Hillier; Lieberman, 2010) Solução ótima: uma solução viável que tem o valor mais favorável da função objetivo, isto é, maximiza (maior valor) ou minimiza (menor valo) a função objetivo em toda a região viável, podendo ser única ou não. Soluções ótimas múltiplas: é a situação em que há um número infinito de soluções ótimas, cada uma com o mesmo valor ótimo da função objetivo. Na Figura 7, o segmento de reta, em vermelho,
Compartilhar