ATPS Pesquisa Operacional

PESQUISA

OPERACIONAL

1. INTRODUÇÃO À PESQUISA OPERACIONAL

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 desenvolvidos 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.3 Estrutura de Modelos Matemáticos

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

a) 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;

b) 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);

c) 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 aos 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 000 kg de carne e 30 000 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 às restrições e a função objetivo é linear; 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

...