Introdução Pesquisa Operacional

Introdução Pesquisa Operacional

(Parte 1 de 2)

1 - Introdução à pesquisa operacional Pesquisa Operacional

Prof. Erico Lisboa 1 http://www.ericolisboa.eng.br

CAPÍTULO 1

INTRODUÇÃO À PESQUISA OPERACIONAL 1

1.1 O Desenvolvimento da Pesquisa Operacional

Durante a Segunda Guerra Mundial, um grupo de cientistas foi convocado na Inglaterra para estudar problemas de estratégia e de tática associados com a defesa do país. O objetivo era decidir sobre a utilização mais eficaz de recursos militares limitados. A convocação deste grupo marcou a primeira atividade formal de pesquisa operacional.

Os resultados positivos conseguidos pela equipe de pesquisa operacional inglesa motivaram os Estados

Unidos a iniciarem atividades semelhantes. Apesar de ser creditada à Inglaterra a origem da Pesquisa Operacional, sua propagação deve-se principalmente à equipe de cientistas liderada por George B.

Dantzig, dos Estados Unidos, convocada durante a Segunda Guerra Mundial. Ao resultado deste esforço de pesquisa, concluído em 1947, deu-se o nome de Método Simplex.

Com o fim da guerra, a utilização de técnicas de pesquisa operacional atraiu o interesse de diversas outras áreas. A natureza dos problemas encontrados é bastante abrangente e complexa, exigindo portanto uma abordagem que permita reconhecer os múltiplos aspectos envolvidos. Uma característica importante da pesquisa operacional e que facilita o processo de análise e de decisão é a utilização de modelos. Eles permitem a experimentação da solução proposta. Isto significa que uma decisão pode ser mais bem avaliada e testada antes de ser efetivamente implementada. A economia obtida e a experiência adquirida pela experimentação justificam a utilização da Pesquisa Operacional.

Com o aumento da velocidade de processamento e quantidade de memória dos computadores atuais, houve um grande progresso na Pesquisa Operacional. Este progresso é devido também à larga utilização de microcomputadores, que se tornaram unidades isoladas dentro de empresas. Isso faz com que os modelos desenvolvido pelos profissionais de Pesquisa Operacional sejam mais rápidos e versáteis, além de serem também interativos, possibilitando a participação do usuário ao longo do processo de cálculo.

1.2 Modelagem

Um modelo é uma representação de um sistema real, que pode já existir ou ser um projeto aguardando execução. No primeiro caso, o modelo pretende reproduzir o funcionamento do sistema, de modo a aumentar sua produtividade. No segundo caso, o modelo é utilizado para definir a estrutura ideal do sistema.

A confiabilidade da solução obtida através do modelo depende da validação do modelo na representação do sistema real. A validação do modelo é a confirmação de que ele realmente representa o sistema real. A diferença entre a solução real e a solução proposta pelo modelo depende diretamente da precisão do modelo em descrever o comportamento original do sistema.

Um problema simples pode ser representado por modelos também simples e de fácil solução. Já problemas mais complexos requerem modelos mais elaborados, cuja solução pode vir a ser bastante complicada.

1 - Introdução à pesquisa operacional Pesquisa Operacional

Prof. Erico Lisboa 2 http://www.ericolisboa.eng.br

1.3 Estrutura de Modelos Matemáticos Em um modelo matemático, são incluídos três conjuntos principais de elementos:

(1) variáveis de decisão e parâmetros: variáveis de decisão são as incógnitas a serem determinadas pela solução do modelo. Parâmetros são valores fixos no problema;

(2) restrições: de modo a levar em conta as limitações físicas do sistema, o modelo deve incluir restrições que limitam as variáveis de decisão a seus valores possíveis (ou viáveis);

(3) função objetivo: é uma função matemática que define a qualidade da solução em função das variáveis de decisão.

Para melhor ilustrar ao conjuntos acima, considere o seguinte exemplo:

"Uma empresa de comida canina produz dois tipos de rações: Tobi e Rex. Para a manufatura das rações são utilizados cereais e carne. Sabe-se que:

ü a ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a ração Rex utiliza 4 kg de carne e 2 kg de cereais; ü o pacote de ração Tobi custa $ 20 e o pacote de ração Rex custa $ 30; ü o kg de carne custa $ 4 e o kg de cereais custa $ 1; ü estão disponíveis por mês 10 0 kg de carne e 30 0 kg de cereais. Deseja-se saber qual a quantidade de cada ração a produzir de modo a maximizar o lucro."

Neste problema as variáveis de decisão são as quantidades de ração de cada tipo a serem produzidas. Os parâmetros fornecidos são os preços unitários de compra e venda, além das quantidades de carne e cereais utilizadas em cada tipo de ração. As restrições são os limites de carne e cereais e a função objetivo é uma função matemática que determine o lucro em função das variáveis de decisão e que deve ser maximizada.

1.4 Técnicas Matemáticas em Pesquisa Operacional

A formulação do modelo depende diretamente do sistema a ser representado. A função objetivo e as funções de restrições podem ser lineares ou não-lineares. As variáveis de decisão podem ser contínuas ou discretas (por exemplo, inteiras) e os parâmetros podem ser determinísticos ou probabilísticos.

O resultado dessa diversidade de representações de sistemas é o desenvolvimento de diversas técnicas de otimização, de modo a resolver cada tipo de modelo existente. Estas técnicas incluem, principalmente: programação linear, programação inteira, programação dinâmica, programação estocástica e programação não-linear. Programação linear é utilizada para analisar modelos onde as restrições e a função objetivo são lineares; programação inteira se aplica a modelos que possuem variáveis inteiras (ou discretas); programação dinâmica é utilizada em modelos onde o problema completo pode ser decomposto em subproblemas menores; programação estocástica é aplicada a uma classe especial de modelos onde os parâmetros são descritos por funções de probabilidade; finalmente, programação não-linear é utilizada em modelos contendo funções não-lineares.

Uma característica presente em quase todas as técnicas de programação matemática é que a solução ótima do problema não pode ser obtida em um único passo, devendo ser obtida iterativamente. É escolhida uma solução inicial (que geralmente não é a solução ótima). Um algoritmo é especificado para determinar, a partir desta, uma nova solução, que geralmente é superior à anterior. Este passo é repetido até que a solução ótima seja alcançada (supondo que ela existe).

1 - Introdução à pesquisa operacional Pesquisa Operacional

Prof. Erico Lisboa 3 http://www.ericolisboa.eng.br

1.5 Fases do Estudo de Pesquisa Operacional Um estudo de pesquisa operacional geralmente envolve as seguintes fases:

(1) definição do problema; (2) construção do modelo;

(3) solução do modelo; (4) validação do modelo; (5) implementação da solução.

Apesar da seqüência acima não ser rígida, ela indica as principais etapas a serem vencidas. A seguir, é apresentado um resumo da cada uma das fases.

1.5.1 Definição do problema A definição do problema baseia-se em três aspectos principais:

ü descrição exata dos objetivos do estudo; ü identificação das alternativas de decisão existentes; ü reconhecimento das limitações, restrições e exigências do sistema.

A descrição dos objetivos é uma das atividades mais importantes em todo o processo do estudo, pois a partir dela é que o modelo é concebido. Da mesma forma, é essencial que as alternativas de decisão e as limitações existentes sejam todas explicitadas, para que as soluções obtidas ao final do processo sejam válidas e aceitáveis.

1.5.2 Construção do modelo

A escolha apropriada do modelo é fundamental para a qualidade da solução fornecida. Se o modelo elaborado tem a forma de um modelo conhecido, a solução pode ser obtida através de métodos matemáticos convencionais. Por outro lado, se as relações matemáticas são muito complexas, talvez se faça necessária a utilização de combinações de metodologias.

1.5.3 Solução do modelo

O objetivo desta fase é encontrar uma solução para o modelo proposto. Ao contrário das outras fases, que não possuem regras fixas, a solução do modelo é baseada geralmente em técnicas matemáticas existentes.

No caso de um modelo matemático, a solução é obtida pelo algoritmo mais adequado, em termos de rapidez de processamento e precisão da resposta. Isto exige um conhecimento profundo das principais técnicas existentes. A solução obtido, neste caso, é dita "ótima".

1.5.4 Validação do modelo

Nessa altura do processo de solução do problema, é necessário verificar a validade do modelo. Um modelo é válido se, levando-se em conta sua inexatidão em representar o sistema, ele for capaz de fornecer uma previsão aceitável do comportamento do sistema.

Um método comum para testar a validade do sistema é analisar seu desempenho com dados passados do sistema e verificar se ele consegue reproduzir o comportamento que o sistema apresentou.

1 - Introdução à pesquisa operacional Pesquisa Operacional

Prof. Erico Lisboa 4 http://www.ericolisboa.eng.br

É importante observar que este processo de validação não se aplica a sistemas inexistentes, ou seja, em projeto. Nesse caso, a validação é feita pela verificação da correspondência entre os resultados obtidos e algum comportamento esperado do novo sistema.

1.5.5 Implementação da solução

(Parte 1 de 2)

Comentários