Livro Pesquisa Operacional

Embed Size (px)

Text of Livro Pesquisa Operacional

Introduo Pesquisa OperacionalFernando Augusto Silva MarinsProfessor Adjunto do Departamento de Produo - DPDFaculdade de Engenharia do Campus de Guaratinguet - FEGUniversidade Estadual Paulista - UNESP2SUMRIOApresentao 5Pesquisa Operacional: origens, definies e reas1.APesquisaOperacionaleoProcessodeTomadade Deciso72. O que a Pesquisa Operacional? 93. Origens da Pesquisa Operacional 104.FasesdaResoluodeumProblemapelaPesquisa Operacional135. Consideraes Importantes 19Referncias 21Programao Linear1. Introduo 232. Modelagem 243. Limitaes 454. Resoluo Grfica 475. Forma Padro 546. Definies e Teoremas587. Forma Cannica de um Sistema de Equaes Lineares 648. Mtodo Simplex 689. Mtodo Simplex com Duas Fases 883Referncias 97Introduo Teoria dos Grafos e Otimizao em Redes1. Introduo 992. Conceitos Bsicos 1023. Algoritmos 1113.1. rvore de Valor Mnimo 1113.2. Caminho Mais Curto 1123.3. Fluxo Mximo 116Referncias 127Modelo de Transporte Simples1. Histrico e Formulao Matemtica 1282. Algoritmo do Stepping Stone Method 1353. Resoluo pelo Mtodo Modificado (Modi)1444. Mtodos para Encontrar uma Soluo Bsica Inicial para o Stepping Stone Method1474.1. Regra do Canto Esquerdo - RCE 1474.2. Mtodo do Menor Custo Associado - MMC 1485. Ofertas e Demandas Desbalanceadas 1516. Degenerescncia 1527. Condies Proibidas e Embarque e Recepo 157Referncias 1594Modelo da Designao1. Introduo 1602. Definies e Notaes 1613. Modelo Matemtico 1634. Mtodo Hngaro 163Referncias 183Introduo Teoria das Filas: Modelos Markovianos1. Introduo 1852. Estrutura Bsica de um Sistema de Filas 1863. Processos de Nascimento e Morte 1924. Modelos de Filas Markovianas 1975. Comentrios Gerais 209Apndice 212Referncias 2165ApresentaoA PesquisaOperacional (PO) uma readaEngenharia de Produo queproporciona aosprofissionais, quetm acesso aoseu escopo, o acesso a um procedimento organizado e consistente que o auxiliar na difcil tarefa de gesto de recursos humanos, materiais e financeirosdeumaorganizao.Defato,aPesquisaOperacional ofereceumelencointeressantedereas,modelosealgoritmosque permitemaogestortomardecisoemproblemascomplexos,onde deve ser aplicada a tica cientfica. Omaterialdestelivrocorrespondeaumcursosemestral introdutrio PO, abordando a Programao Linear, algoritmos para ModelosemRedesemodelosestocsticosdaTeoriadeFilas.O contedovemsendoministrado,hmaisde20anos,nonvelde graduaopara os cursos de Engenharia Mecnica ede Engenharia deProduoMecnicadaFaculdadedeEngenhariadoCampusde Guaratinguet(FEG)daUNESP;edesde2008,emcursosdeps-graduao,LatoSensueStrictoSensutemsidoutilizadocomo apoio, principalmente pelos alunos que esto tendo acesso PO pela primeira vez.Entendendo a dificuldade dos professores em desenvolver o materialdidticoparasuasaulas,serdisponibilizada,paraosque adotaremolivro,umasenhaparaumstionaInternetondehaver os seguintes materiais de apoio:a) ConjuntodeslidesemPowerPointcomocontedodos vrios captulos do livro;6b) Arquivos com exerccios propostos sobre cada captulo do livro;c) Softwares,comtcnicasdePesquisaOperacional, desenvolvidospororientadosdoautor(Simon,Simulexe Hungar), endereos na Internet para o download de verses livres de importantes e teis softwares (LINDO), e, ainda, oendereoparaacesso desoftwarelivredesenvolvidopor outrainstituio(PROLINUniversidadeFederalde Viosa).ManuaisdeusuriodoSolverdoExceledo LINDOdesenvolvidosporprofessoresdeoutra instituio (Universidade Federal de Ouro Preto).OautorgostariadeagradeceraoProfessorHelenodo NascimentoSantosdaUFVeaosProfessoresAlosiodeCastro GomesJnioreMarconeJamilsonFreitasSouzadaUFOP, respectivamente, pela autorizao do uso do software PROLIN e dos manuais do Solver e do LINDO. Agradece, ainda, a aluna Monique deMedeirosTakenouchidocursodeEngenhariadeProduo MecnicadaFEGUNESPpelotrabalho deadequao nosslides emPowerPoint,bemcomoaomestrandoMarcoAurlioReisdos Santospelarevisofinaldotexto.Finalmente,oautorgostariade agradeceraoportunidadeoferecida pelaPr-ReitoriadeGraduao da UNESP, por meio do Programa de Apoio Produo de Material Didtico, ao publicar este livro.Guaratinguet, novembo de 2009.Fernando Augusto Silva Marins7Pesquisa Operacional: origens, definies e reas1. A Pesquisa Operacional e o Processo de Tomada de DecisoUmprofissionalqueassumeumafunoemumaempresa logosedeparacomsituaesondedevertomaralgumtipode deciso. medida que este profissional vai ascendendo na carreira, osproblemaseasdecisesvosetornandomaiscomplexasede maior responsabilidade. De fato, tomar decises uma tarefa bsica dagesto,nosseusvriosnveis,estratgico,gerencial(ttico)ou operacional,devendoserentendidoqueoatodedecidirsignifica fazeruma opoentrealternativasdesoluo quesejamviveis de serem aplicadas situao.Apesardecadagestorteroseuprprioprocedimentode anliseesoluodeproblemas,pode-se,emgeral,estabelecer algumasetapasque,necessariamente,devemserobservadas, configurando o que se denomina de papel do decisor:(a)Identificaroproblematalvezsejaaetapamaisdifcil,pois, diferentementedoslivros,osproblemasnaprticanoesto, inicialmente,claros,definidosedelimitados.Aquiimportante perceber quais so os demais sistemas que interagem com o sistema ondeseinsereoproblemaasertratado.fundamentalseteruma equipedeanalistasmultidisciplinarparaoproblemasejavistode prismas diferentes e isso seja incorporado na sua soluo;(b)Formularobjetivo(s)nestaetapadevemseridentificadose 8formulados (muitas vezes matematicamente) quais so os objetivos quedeveroseratingidosquandodasoluodoproblema.Em algunscasos,podem-setervriosobjetivosquepodemser qualitativos(porexemplo,satisfaodocliente),quantitativos (custo ou lucros) ou ainda conflitantes;(c) Analisar limitaes na seqncia deve-se levantar quais so as restries que limitaro as solues a serem propostas. Comumente, essaslimitaesdizemrespeitoaoatendimentodetempo/prazo, oramento,demandas,capacidades(transporte,produoe armazenamento),tecnologia(equipamentoseprocessos), inventrios(matria-prima,subconjuntos,workinprocesse produtos acabados), entre outros;(d)Avaliar alternativas aqui, odecisor, aps identificar quais so suasalternativasdeao,deverutilizandoalgumprocedimento escolheramelhorsoluoquepoderseraplicada.Destaque-se que,muitasvezes asoluotimapodenoteruma relaocusto-benefcio que permita sua adoo pela empresa, e uma outra soluo queatendeessesrequisitospodeviraseraescolhida.Nesse processo de avaliao de alternativas, o decisor poder utilizar uma abordagem qualitativa ou quantitativa:Aabordagemqualitativaseaplicaemproblemas simples, corriqueiros, repetitivos, com pouco impacto financeiro ou social,ondefundamentalaexperinciadodecisor(oudesua equipedeanalistas)emsituaesanterioressemelhantes.Nestes casos, adota-se uma soluo similar quela j utilizada com sucesso num problema semelhante;9Jaabordagemquantitativaarecomendada quando osproblemassocomplexos,novos,envolvemgrandevolumede recursoshumanos,materiaisefinanceiros,tmaltoimpactono ambiente onde se insere (empresaou sociedade). Aqui, recomenda-se o uso dos preceitos da tica cientfica e os mtodos quantitativos (algoritmos) disponveis a obteno de uma soluo.NestecontextoqueaPesquisaOperacionalseinsere, colaborando na formao de um profissional que dever desenvolver umprocedimentocoerenteeconsistentedeauxliotomadade deciso a ser adotado no decorrer da sua carreira.2. O que a Pesquisa Operacional?Pode-se considerar que o nome Pesquisa Operacional (PO) deorigemmilitar,tendosidousadopelaprimeiraveznaGr-Bretanha durante a Segunda Guerra Mundial. Em termos cientficos, a PO caracterizada por um campo de aplicaes bastante amplo o quejustificaaexistnciadevriasdefinies,algumastogerais quepodemseaplicaraqualquercincia,eoutrastoparticulares que s so vlidas em determinadas reas de aplicao:ousodomtodocientficocomoobjetivodeprover departamentos executivos de elementos quantitativos para a tomada de decises com relao a operaes sob seu controle";Propeumaabordagemcientficanasoluode problemas:observao,formulaodoproblema,econstruode modelo cientfico (matemtico ou de simulao); amodelagemetomadadedecisoemsistemasreais, 10determinsticosouprobabilsticos,relativosnecessidadede alocao de recursos escassos.A PO uma cincia aplicada que utiliza tcnicas cientficas conhecidas (ou as desenvolve quando necessrio), tendo como ponto derefernciaaaplicaodomtodocientfico.APOtemaver, portanto,comapesquisacientficacriativaemaspectos fundamentaisdasoperaesdeumaorganizao.Peloquefoidito antes,podem-seresumirosprincipaisaspectosdaPOcomose segue:Possuiumamploespectrodeutilizao,no governoesuasagncias,indstriaseempresascomerciaisede servio;aplicadaaproblemasassociadosconduo e a coordenao de operaes ou atividades numa organizao;Adotaumenfoquesistmicoparaos problemas;Busca a soluo tima para o problema;Usaumametodologiadetrabalhoemequipe (engenharia,computao,economia,estatstica,administrao, matemtica, cincias comportamentais).3. Origens da Pesquisa OperacionalComodescritoporLss(1981),desdeosculoIIIA.C. quandoHieron,ImperadordaSiracusa,solicitoudeArquimedesa idealizaodemeiosparaacabarcomocerconavaldosromanos, liderespolticosemilitarestmconsultadooscientistasparaa 11soluodeproblemastticoseestratgicos.NosculoXVII, PascaleFermat,inventoresdanoodeesperanamatemtica,e maisrecentemente,Taylor,BoreleErlangmodelaramalguns problemas e forneceram solues para os respectivos modelos. No que diz respeito a aplicaes industriais, as sementes da POforamlanadashmuitasdcadas,nastentativasdeusaro mtodo cientifico na gerncia de sistemas e organizaes de grande porte, logo em seguida 1a. Revoluo Industrial. OinciodaPO,noOcidente,geralmenteatribudos iniciativasdosserviosmilitaresnoinciodaSegundaGuerra Mundial.Tm-se,porexemplo,estudosrelacionadoscomo desenvolvimentoeusodo radar,problemadealocao eficiente de recursos escassos s vrias operaes militares, problema da dieta e outrosmais.Asequipesdeanalistasoperacionais,comoforam chamadasnaquelapoca,comearamaseexpandirnaGr-Bretanha, no Canad, na Austrlia e nos Estados Unidos.OrpidocrescimentodaPOnops-guerradeve-seao desenvolvimentodetcnicasespecficas,taiscomoomtodo SimplexparaaProgramaoLinear,eaograndeprogresso alcanadonod