Introdução à Pesquisa Operacional: História e Desenvolvimento

Pesquisa Operacional Oficina 1 Introdução Prof Victor Diogho Heuer de Carvalho Campus do Sertão Universidade Federal de Alagoas Conteúdo da Oficina 1 História e Áreas da Pesquisa Operacional Introdução à Programação Matemática Princípios de Programação Dinâmica 1ª Revolução Industrial 1780 a 1860 aproximadamente 1ª Fase mecanização da indústria e da agricultura 2ª Fase aplicação da Força motriz à indústria 3ª Fase desenvolvimento do sistema fabril 4ª Fase aceleração dos transportes e comunicações Precedentes Históricos da Pesquisa Operacional 2ª Revolução Industrial 1860 a 1914 aproximadamente Marcos Industria do aço 1856 Aperfeiçoamento do dínamo 1873 Motor de combustão interna motos de ciclo de Otto 1876 Administração Científica Frederick W Taylor 1856 1915 Princípio eliminar o desperdício e as perdas sofridas pelas industrias e elevar os níveis de produtividades por meio da aplicação de métodos e técnicas formais da engenharia industrial Precedentes Históricos da Pesquisa Operacional Precedentes Históricos da Pesquisa Operacional Teoria Clássica da Administração Jules Henri Fayol 18411925 Princípio pensamento focado no todo organizacional e sua estrutura para garantir a eficiência de todas as partes envolvidas sejam os setores da empresa ou as pessoas Marco Histórico Primeira Guerra Mundial 1914 1917 Precedentes Históricos da Pesquisa Operacional Segunda Guerra Mundial 1939 1945 A Pesquisa Operacional PO tem seu inicio atribuído às operações e ações militares ocorridas durante a Segunda Guerra Mundial Necessidade de alocar recursos escassos de forma eficiente nas diversas operações militares Estados Unidos e Reino Unido convocaram cientistas de diversas áreas para auxiliar na resolução de problemas formando as primeiras equipes de PO com enfoque multidisciplinar Precedentes Históricos da Pesquisa Operacional PósGuerra e Era de Ouro Os mesmos cientistas que atuaram no contexto bélico continuaram suas atividades dentro da PO agora no contexto organizacional após a guerra Era de ouro da PO 1945 a 1970 com sua rápida expansão como área de aplicação no mercado além de pesquisas científicas para desenvolvimento de ferramentas George Dantzig foi um dos pioneiros nessa área criando do algoritmo Simplex em 1947 Sociedades Profissionais de PO O Operational Research Club em Londres foi a primeira fundada em 1948 Esta sociedade publicou o primeiro número da revista Operatinal Research Quaterly em março de 1950 permanecendo com esse nome até 1978 quando mudou para Journal of the Operational Research Society Atualmente se chama Operational Research Society Atualmente o INFORMS Institute for Operations Research and the Management Science fundada em 1995 é a maior sociedade em operação na área de PO Sociedades Profissionais de PO EURO Association of European Operational Research Societies fundado em 1975 SOBRAPO Sociedade Brasileira de Pesquisa Operacional fundada em 1969 Mas afinal o que é a Pesquisa Operacional The Guide to Operatinal Research INFORMS Por meio de uso de técnicas como a modelagem matemática para analisar situações complexas a PO dá aos executivos o poder para Tomar decisões mais efetivas Construir sistemas mais produtivos baseados em dados mais completos Considerar todas as alterativas possíveis Realizar previsões cuidadosas de resultados Estimar riscos Usar ferramentas e técnicas modernas de decisão O que pode ser incluído na PO Programação Matemática Linear e NãoLinear Programação Dinâmica Processos Estocásticos Teoria da Decisão Decisão Multicritério Decisões em Grupo e Negociação Métodos de Estruturação de Problemas Teoria dos Jogos MetaHeurísticas Simulações Ao lado estão alguns dos principais tópicos associados à Pesquisa Operacional e à Ciência da Gestão para apoio à tomada de decisão nas organizações Introdução à Programação Matemática A Programação Matemática é uma área de estudo com foco em problemas de otimização para alcançar um objetivo de maximização ou minimização por meio de um modelo matemático que pode ser linear ou nãolinear Temos então a Programação Linear e a NãoLinear Programação Linear Nesta disciplina o foco será a Programação Linear Para que um modelo seja considerado como Linear ele deve atender às seguintes hipóteses 1 Aditividade 2 Proporcionalidade 3 Fracionamento ou Divisibilidade 4 Certeza Programação Linear Vamos demonstrar essas hipóteses através de um problema Regsdale 2009 A Blue Ridge Hot Tubs fabrica e vende dois modelos de banheiras a AquaSpa e a HydroLux Howie Jones proprietário e gerente da empresa precisa decidir quanto de cada tipo de banheira produzir em seu ciclo de produção Howie compra cubas de fibra de vidro préfabricadas de um fornecedor local e adiciona a elas a bomba e a tubulação para criar suas banheiras Esse fornecedor pode abastecer Howie com quantas cubas ele precisar Howie instala o mesmo tipo de bomba em ambos os modelos de banheira Ele terá apenas 200 bombas disponíveis durante seu próximo ciclo de produção Do ponto de vista da fabricação a principal diferença entre os dois modelos de banheira é a quantidade de tubulação e de trabalho necessários Cada AquaSpa requer nove horas de trabalho e 12 pés de tubulação Cada HydroLux requer seis horas de trabalho e 16 pés de tubulação Howie espera ter 1566 horas de trabalho de produção e 2880 pés de tubulação disponíveis durante o próximo ciclo de produção Howie tem lucro de 35000 em cada AquaSpa que vende e 30000 em cada HydroLux comercializada Perguntase quantas AquaSpas e HydroLuxes devem ser produzidas se quisermos maximizar o lucros durante o próximo ciclo de produção Programação Linear Modelo matemático do problema da Blue Ridge Hot Tubes Max z 350x1 300x2 Sujeito a x1 x2 200 9x1 6x2 1566 12x1 16x2 2880 x1 0 x2 0 Programação Linear Aditividade supõe que toda função linear seja a função objetivo ou as restrições é a soma das contribuições individuais das respectivas atividades O problema da Blue Ridge Hot Tubes atende totalmente à essa hipótese Podese verificar que todas as funções que compõem o modelo são somas das contribuições individuais de cada um dos tipos de banheiras x1 e x2 sem que haja a possibilidade de um produto cruzado entre x1 e x2 Exemplo de produto cruzado na função objetivo z 350x1 300x2 x1x2 Este caso viola a hipótese da aditividade Max z 350x1 300x2 Sujeito a x1 x2 200 9x1 6x2 1566 12x1 16x2 2880 x1 0 x2 0 Programação Linear Proporcionalidade supõe que a contribuição de cada atividade ao valor da função objetivo z é proporcional ao nível de atividade xj conforme representado pelo termo cj xj na função objetivo O problema da Blue Ridge Hot Tubes também atende totalmente à essa hipótese Note que para x1 na função objetivo haverá um incremento proporcional de R 350 de lucro vezes a quantidade produzida Se forem produzidas 2 unidades esse lucro será de R 700 3 unidade R 1050 e assim por diante O mesmo pode ser observado para x2 com sua respectiva margem de lucro A violação dessa hipótese poderia ocorrer por exemplo com a realização de economia de escala com o emprego de maquinário ou processos mais eficientes para aumentar a produtividade da fábrica Max z 350x1 300x2 Sujeito a x1 x2 200 9x1 6x2 1566 12x1 16x2 2880 x1 0 x2 0 Programação Linear Divisibilidade ou Fracionalidade supõe que as variáveis de decisão que compõem o modelo podem assumir quaisquer valores inclusive nãointeiros que satisfaçam as restrições funcionais e de não negatividade O modelo do problema da Blue Ridge Hot Tubes também atende à essa hipótese Os valores assumidos por x1 e x2 no modelo podem ser valores tanto inteiros como frações de um total Caso houvesse alguma restrição por exemplo que determinasse que os valores das variáveis de decisão fossem obrigatoriamente inteiros essa hipótese não poderia ser assumida Max z 350x1 300x2 Sujeito a x1 x2 200 9x1 6x2 1566 12x1 16x2 2880 x1 0 x2 0 Programação Linear Certeza supõe que o valor atribuído a cada parâmetro de um modelo de programação linear é uma constante conhecida Em problemas reais a certeza é algo difícil de ser assumido já que os modelos de programação linear são formulados para selecionar alguma medida futura Condições futuras sempre introduzem algum grau de incerteza Isso nos leva à condução de análises de sensibilidade após a obtenção de uma solução de algum modelo para verificar o impacto de mudanças nas variáveis do problema Programação Linear Gráfico do Problema da Blue Ridge Hot Tubs Obtido com o PHP Simplex Programação Linear Solução do Problema da Blue Ridge Hot Tubs Obtida com o PHP Simplex Introdução e Exemplos Programação Dinâmica O que é a Programação Dinâmica Técnica matemática para tomar uma sequencia de decisões inter relacionadas por meio de um procedimento sistemático para determinar as combinações de decisões ótimas Os problemas desta natureza podem ser representados por grafos Problema da Diligência Problema modelo desenvolvido para auxiliar na introdução dos conceitos de programação dinâmica Ele trata de um caçador de fortunas que precisa fazer uma jornada pelos Estados Unidos partindo do Missouri por meio de diligência com o objetivo de se juntar à Corrida do Ouro na California Preocupado com sua segurança já que a jornada envolvia diversos riscos ele criou uma maneira de determinar a melhor rota Eram oferecidas apólices de seguros para os passageiros da diligência Em razão do custo da apólice para qualquer viagem de diligência se basear em cuidadosa avaliação de segurança da viagem a rota mais segura seria aquela com a apólice de seguro de vida total mais barata Problema da Diligência O grafo ao lado representa o conjunto de rotas possíveis para as diligências com os custos de apólices associados Problema da Diligência As quatro tabelas a seguir contém o custo da apólicepadrão para a viagem em diligencia do estado i para o estado j B C D A 2 4 3 E F G B 7 4 6 C 3 2 4 D 4 1 5 H I E 1 4 F 6 3 G 3 3 J H 3 I 4 A questão central portanto é qual a rota que minimiza o custo total das apólices Problema da Diligência Para resolver o problema vamos trazer a solução de traz para frente logo de J para A Custo Destino H 3 J I 4 J Neste caso o custo mínimo 3 será saindo de H para J Estágio 1 Problema da Diligência Soma dos Custos Mínimos Destinos com menores custos H I E 1 3 4 4 4 8 4 H F 6 3 9 3 4 7 7 I G 3 3 6 3 4 7 6 H Custo Destino H 3 J I 4 J Estágio 2 Problema da Diligência Soma dos Custos Mínimo s Destinos com menores custos E F G B 7 4 11 4 7 11 6 6 12 11 E ou F C 3 4 7 2 7 9 4 6 10 7 E D 4 4 8 1 7 8 5 6 11 8 E ou F Soma dos Custos Mínimos Destinos com menores custos H I E 1 3 4 4 4 8 4 H F 6 3 9 3 4 7 7 I G 3 3 6 3 4 7 6 H Estágio 3 Problema da Diligência Soma dos Custos Mínimo Destino com Menor custo B C D A 2 11 13 4 7 11 3 8 11 11 C ou D Soma dos Custos Mínimo s Destinos com menores custos E F G B 7 4 11 4 7 11 6 6 12 11 E ou F C 3 4 7 2 7 9 4 6 10 7 E D 4 4 8 1 7 8 5 6 11 8 E ou F Estágio 4 Problema da Diligência Grafo com a solução ótima Há três rotas ótimas com os mesmos custos custo 11 A C E H J A D E H J A D F I J Referências HILLIER F S LIEBERMAN GJ Introdução à Pesquisa Operacional 9ª Ed AMGH Editora 2013 MOREIRA Daniel Augusto Pesquisa Operacional curso introdutório 2 ed São Paulo Cengage Learning 2010 REGSDALE Cliff T Modelagem e Análise da Decisão São Paulo Cengage Learning 2011 Autoria e Uso da Apresentação Esta apresentação foi desenvolvida pelo Prof Victor Diogho Heuer de Carvalho para uso na disciplina de Pesquisa Operacional e é propriedade do Group of Engineering in Decision Making and Artificial Intelligence GEDAI Todo uso deste material deverá fazer referência também ao seu autor e ao referido grupo Campus do Sertão Delmiro Gouveia