Pesquisa Operacional

Pesquisa Operacional

Engenharia de Produção

DEPROT / UFRGS

Profs. Flavio Fogliatto, Ph.D.

1. INTRODUÇÃO À PESQUISA OPERACIONAL

A Pesquisa Operacional (PO) trata da modelagem matemática de fenômenos

estáticos ou dinâmicos. Os problemas estáticos são denominados por

determinísticos. Nestes problemas, todos os componentes são conhecidos a

priori e nenhuma aleatoriedade em sua ocorrência é admitida. Os problemas

dinâmicos são denominados estocásticos, e seus elementos apresentam uma

probabilidade de ocorrência em uma determinada forma. Este material aborda

problemas determinísticos de Pesquisa Operacional.

Os problemas de PO existem desde longa data. Somente a partir da 2a Grande

Guerra, todavia, passaram a ser tratados a partir de uma abordagem organizada,

sendo organizados na forma de uma disciplina ou área do conhecimento

(Ravindran et al., 1987). Os primeiros casos reportados de aplicação da PO

foram, em virtude de sua origem, de caráter militar. Somente após o final da

Segunda Grande Guerra, problemas civis passaram a ser estudados pela PO. Os

primórdios da PO encontram-se descritos no trabalho de Trefethen (1954).

Dois eventos motivaram o rápido desenvolvimento da PO. O primeiro foi o

desenvolvimento de um algoritmo simples para solucionar problemas de

programação linear (isto é, problemas determinísticos de PO), denominado

algoritmo simplex e proposto por George Dantzig em 1947. Tal algoritmo

permitiu a resolução manual de diversos problemas de PO, especialmente aqueles

de baixa complexidade. O segundo foi a proliferação dos microcomputadores e o

rápido aumento em sua velocidade de processamento.

Problemas de PO são usualmente modelados na forma de uma função objetivo

(por exemplo, maximizar o lucro da empresa) e diversas restrições (associadas,

por exemplo, à disponibilidade de matérias-primas, mão-de-obra, etc.). A chave

do algoritmo simplex está no formato da região limitada pelas restrições, comum

a todos os problemas de PO, conforme verificado por Dantzig; tal região é

denominada simplex. Quaisquer dois pontos selecionados no contorno de um

simplex, quando unidos por uma linha, resultam em uma linha interiamente

contida dentro do simplex. A partir dessa constatação, a busca pela solução ótima

em problemas de PO passou a ser limitada a pontos extremos da região simplex, o

que permitiu o desenvolvimento de um algoritmo de baixa complexidade

computacional por Dantzig.

Os problemas determinísticos de PO podem ser classificados em duas categorias

genéricas: problemas de programação (i) linear e (ii) não-linear. Somente os

problemas de programação linear podem ser resolvidos pelo algoritmo simplex.

Um problema qualquer de programação linear é um problema de otimização (isto

é, busca pela melhor dentre várias situações, utilizando um critério pré-

estabelecido de otimalidade), com as seguintes características (Bronson &

Naadimuthu,