(Parte 1 de 7)

Introdução à Pesquisa Operacional

Fernando Augusto Silva Marins

Professor Adjunto do Departamento de Produção - DPD

Faculdade de Engenharia do Campus de Guaratinguetá - FEG Universidade Estadual Paulista - UNESP

Apresentação 5 Pesquisa Operacional: origens, definições e áreas

1. A Pesquisa Operacional e o Processo de Tomada de Decisão 7

2. O que é a Pesquisa Operacional?9 3. Origens da Pesquisa Operacional10

4. Fases da Resolução de um Problema pela Pesquisa Operacional 13

5. Considerações Importantes19 Referências 21

Programação Linear 1. Introdução23 2. Modelagem24 3. Limitações45 4. Resolução Gráfica47 5. Forma Padrão54 6. Definições e Teoremas 58 7. Forma Canônica de um Sistema de Equações Lineares64 8. Método Simplex68 9. Método Simplex com Duas Fases88

3.1. Árvore de Valor Mínimo111
3.2. Caminho Mais Curto112
3.3. Fluxo Máximo116

Introdução à Teoria dos Grafos e à Otimização em Redes 1. Introdução99 2. Conceitos Básicos102 3. Algoritmos111 Referências 127

Modelo de Transporte Simples 1. Histórico e Formulação Matemática128 2. Algoritmo do Stepping Stone Method135 3. Resolução pelo Método Modificado (Modi) 144

4. Métodos para Encontrar uma Solução Básica Inicial para o Stepping Stone Method 147

4.1. Regra do Canto Esquerdo - RCE147
4.2. Método do Menor Custo Associado - MMC148

5. Ofertas e Demandas Desbalanceadas151 6. Degenerescência 152 7. Condições Proibidas e Embarque e Recepção157 Referências 159

4 Modelo da Designação

1. Introdução160 2. Definições e Notações161 3. Modelo Matemático163 4. Método Húngaro163 Referências 183

Introdução à Teoria das Filas: Modelos Markovianos 1. Introdução185 2. Estrutura Básica de um Sistema de Filas186 3. Processos de Nascimento e Morte192 4. Modelos de Filas Markovianas197 5. Comentários Gerais209 Apêndice 212 Referências 216

5 Apresentação

A Pesquisa Operacional (PO) é uma área da Engenharia de

Produção que proporciona aos profissionais, que têm acesso ao seu escopo, o acesso a um procedimento organizado e consistente que o auxiliará na difícil tarefa de gestão de recursos humanos, materiais e financeiros de uma organização. De fato, a Pesquisa Operacional oferece um elenco interessante de áreas, modelos e algoritmos que permitem ao gestor tomar decisão em problemas complexos, onde deve ser aplicada a ótica científica.

O material deste livro corresponde a um curso semestral introdutório à PO, abordando a Programação Linear, algoritmos para Modelos em Redes e modelos estocásticos da Teoria de Filas. O conteúdo vem sendo ministrado, há mais de 20 anos, no nível de graduação para os cursos de Engenharia Mecânica e de Engenharia de Produção Mecânica da Faculdade de Engenharia do Campus de Guaratinguetá (FEG) da UNESP; e desde 2008, em cursos de pósgraduação, LatoSensu e Stricto Sensu tem sido utilizado como apoio, principalmente pelos alunos que estão tendo acesso à PO pela primeira vez.

Entendendo a dificuldade dos professores em desenvolver o material didático para suas aulas, será disponibilizada, para os que adotarem o livro, uma senha para um sítio na Internet onde haverá os seguintes materiais de apoio:

a)Conjunto de slides em PowerPoint com o conteúdo dos vários capítulos do livro;

6 b)Arquivos com exercícios propostos sobre cada capítulo do livro; c)Softwares, com técnicas de Pesquisa Operacional, desenvolvidos por orientados do autor (Simon, Simulex e Hungar), endereços na Internet para o download de versões livres de importantes e úteis softwares (LINDO ), e, ainda, o endereço para acesso de software livre desenvolvido por outra instituição (PROLIN – Universidade Federal de

Viçosa). Manuais de usuário do Solver do Excel e do

LINDO desenvolvidos por professores de outra instituição (Universidade Federal de Ouro Preto).

O autor gostaria de agradecer ao Professor Heleno do

Nascimento Santos da UFV e aos Professores Aloísio de Castro Gomes Júnior e Marcone Jamilson Freitas Souza da UFOP, respectivamente, pela autorização do uso do software PROLIN e dos manuais do Solver e do LINDO. Agradece, ainda, a aluna Monique de Medeiros Takenouchi do curso de Engenharia de Produção Mecânica da FEG – UNESP pelo trabalho de adequação nos slides em PowerPoint, bem como ao mestrando Marco Aurélio Reis dos Santos pela revisão final do texto. Finalmente, o autor gostaria de agradecer a oportunidade oferecida pela Pró-Reitoria de Graduação da UNESP, por meio do Programa de Apoio à Produção de Material Didático, ao publicar este livro.

Guaratinguetá, novembo de 2009. Fernando Augusto Silva Marins

Pesquisa Operacional: origens, definições e áreas

1. A Pesquisa Operacional e o Processo de Tomada de Decisão

Um profissional que assume uma função em uma empresa logo se depara com situações onde deverá tomar algum tipo de decisão. À medida que este profissional vai ascendendo na carreira, os problemas e as decisões vão se tornando mais complexas e de maior responsabilidade. De fato, tomar decisões é uma tarefa básica da gestão, nos seus vários níveis, estratégico, gerencial (tático) ou operacional, devendo ser entendido que o ato de decidir significa fazer uma opção entre alternativas de solução que sejam viáveis de serem aplicadas à situação.

Apesar de cada gestor ter o seu próprio procedimento de análise e solução de problemas, pode-se, em geral, estabelecer algumas etapas que, necessariamente, devem ser observadas, configurando o que se denomina de papel do decisor:

(a) Identificar o problema – talvez seja a etapa mais difícil, pois, diferentemente dos livros, os problemas na prática não estão, inicialmente, claros, definidos e delimitados. Aqui é importante perceber quais são os demais sistemas que interagem com o sistema onde se insere o problema a ser tratado. É fundamental se ter uma equipe de analistas multidisciplinar para o problema seja visto de prismas diferentes e isso seja incorporado na sua solução;

(b) Formular objetivo (s) – nesta etapa devem ser identificados e

8 formulados (muitas vezes matematicamente) quais são os objetivos que deverão ser atingidos quando da solução do problema. Em alguns casos, podem-se ter vários objetivos que podem ser qualitativos (por exemplo, satisfação do cliente), quantitativos (custo ou lucros) ou ainda conflitantes;

(c) Analisar limitações –na seqüência deve-se levantar quais são as restrições que limitarão as soluções a serem propostas. Comumente, essas limitações dizem respeito ao atendimento de tempo/prazo, orçamento, demandas, capacidades (transporte, produção e armazenamento), tecnologia (equipamentos e processos), inventários (matéria-prima, subconjuntos, work in process e produtos acabados), entre outros;

(d) Avaliar alternativas – aqui, o decisor, após identificar quais são suas alternativas de ação, deverá utilizando algum procedimento escolher a “melhor solução” que poderá ser aplicada. Destaque-se que, muitas vezes a solução ótima pode não ter uma relação custobenefício que permita sua adoção pela empresa, e uma outra solução que atende esses requisitos pode vir a ser a escolhida. Nesse processo de avaliação de alternativas, o decisor poderá utilizar uma abordagem qualitativa ou quantitativa:

A abordagem qualitativa se aplica em problemas simples, corriqueiros, repetitivos, com pouco impacto financeiro ou social, onde é fundamental a experiência do decisor (ou de sua equipe de analistas) em situações anteriores semelhantes. Nestes casos, adota-se uma solução similar àquela já utilizada com sucesso num problema semelhante;

9 Já a abordagem quantitativa é a recomendada quando os problemas são complexos, novos, envolvem grande volume de recursos humanos, materiais e financeiros, têm alto impacto no ambiente onde se insere (empresa ou sociedade). Aqui, recomendase o uso dos preceitos da ótica científica e os métodos quantitativos (algoritmos) disponíveis a obtenção de uma solução.

Neste contexto é que a Pesquisa Operacional se insere, colaborando na formação de um profissional que deverá desenvolver um procedimento coerente e consistente de auxílio à tomada de decisão a ser adotado no decorrer da sua carreira.

2. O que é a Pesquisa Operacional?

Pode-se considerar que o nome Pesquisa Operacional (PO) é de origem militar, tendo sido usado pela primeira vez na Grã- Bretanha durante a Segunda Guerra Mundial. Em termos científicos, a PO é caracterizada por um campo de aplicações bastante amplo o que justifica a existência de várias definições, algumas tão gerais que podem se aplicar a qualquer ciência, e outras tão particulares que só são válidas em determinadas áreas de aplicação:

“É o uso do método científico com o objetivo de prover departamentos executivos de elementos quantitativos para a tomada de decisões com relação a operações sob seu controle";

“Propõe uma abordagem científica na solução de problemas: observação, formulação do problema, e construção de modelo científico (matemático ou de simulação”);

“Éamodelagem e tomada de decisão em sistemas reais,

10 determinísticos ou probabilísticos, relativos à necessidade de alocação de recursos escassos”.

A PO é uma ciência aplicada que utiliza técnicas científicas conhecidas (ou as desenvolve quando necessário), tendo como ponto de referência a aplicação do método científico. A PO tem a ver, portanto, com a pesquisa científica criativa em aspectos fundamentais das operações de uma organização. Pelo que foi dito antes, podem-se resumir os principais aspectos da PO como se segue:

Possui um amplo espectro de utilização, no governo e suas agências, indústrias e empresas comerciais e de serviço;

É aplicada a problemas associados à condução e a coordenação de operações ou atividades numa organização;

(Parte 1 de 7)

Comentários