UNIVERSIDADE FEDERAL DE SANTA MARIA
CENTRO DE TECNOLOGIA
DEPARTAMENTO DE PRODUÇÃO E SISTEMAS
PESQUISA OPERACIONAL
Denis Rasquin Rabenschlag
2005
PESQUISA OPERACIONAL
ÍNDICE
1 A INFLUÊNCIA DA PESQUISA OPERACIONAL NO PROCESSO DE TOMADA DE
DECISÃO .............................................................................................................................1
1.1 INTRODUÇÃO ..............................................................................................................1
1.2 A TOMADA DE DECISÃO .........................................................................................3
1.3 PRINCIPAIS CARACTERÍSTICAS DO PROCESSO DE TOMADA DE
DECISÃO ......................................................................................................................4
1.4 OBSTÁCULOS A UMA DECISÃO RACIONAL .......................................................5
1.5 O ENFOQUE GERENCIAL DA P.O. .........................................................................7
1.6 A METODOLOGIA DE UM ESTUDO DE P.O. ........................................................8
2 MODELAGEM ...................................................................................................................13
2.1 O PROCESSO DE MODELAGEM .........................................................................13
2.2 VANTAGENS DA UTILIZAÇÃO DO PROCESSO DE MODELAGEM ..............15
2.3 TIPOS DE MODELOS ..............................................................................................15
2.4 PRINCIPIOS DE MODELAGEM ..............................................................................16
2.5 MODELOS DE OTIMIZAÇÃO ..................................................................................18
2.5.1 Procedimentos para Desenvolver Problemas de Otimização .................20
2.6 EXERCÍCIOS .............................................................................................................22
3 PROGRAMAÇÃO LINEAR ..............................................................................................28
3.1 SOLUÇÃO GRÁFICA ................................................................................................29
3.2 SOLUÇÃO ALGÉBRICA – MÉTODO SIMPLEX ...................................................32
3.2.1 Etapas do Método Simplex ..........................................................................32
3.2.2 Utilização das Variáveis Artificiais ..............................................................34
3.3 EXERCÍCIOS .............................................................................................................35
4 PROBLEMAS DE TRANSPORTE .................................................................................36
4.1 FORMULAÇÃO DO MODELO ................................................................................38
4.1.1 Problema de Transporte Equilibrado ..........................................................38
4.1.2 Problema de Transporte Desequilibrado ....................................................40
4.2 METODOLOGIA DE SOLUÇÃO .............................................................................41
4.2.1 Método do Custo Mínimo ..............................................................................41
4.2.2 Método de Vogel ............................................................................................42
4.2.3 Método U – V ou Distribuição Modificada ..................................................42
4.2.4 Circuito de Alpondras ....................................................................................43
4.3 DEGENERAÇÃO DO PROBLEMA DE TRANSPORTE ......................................43
4.4 SOLUÇÕES MÚLTIPLAS ........................................................................................44
4.5 PROBLEMA DE TRANSPORTE DE MAXIMIZAÇÃO ..........................................44
4.6 EXERCÍCIOS .............................................................................................................45
5 PROBLEMAS DE DESIGNAÇÃO .................................................................................49
5.1 PROBLEMA EQUILIBRADO ....................................................................................51
5.2 PROBLEMA DESEQUILIBRADO ...........................................................................51
5.3 PROBLEMA DE MAXIMIZAÇÃO ............................................................................52
5.4 EXERCÍCIOS .............................................................................................................53
D.R.R.
PESQUISA OPERACIONAL
6 REDE PERT-CPM ............................................................................................................55
6.1 INTRODUÇÃO ............................................................................................................55
6.2 CONSTRUÇÃO DA REDE PERT/CPM .................................................................56
6.3 METODOLOGIA DE UTILIZAÇÃO ..........................................................................59
6.4 CÁLCULO DA REDE ................................................................................................60
6.4.1 O Tempo de Execução do Projeto ...............................................................60
6.4.2 O Caminho Crítico .........................................................................................61
6.4.3 Os Tempos Operacionais das Atividades ..................................................61
6.4.4 As Folgas ........................................................................................................62
6.5 ESTIMATIVA DOS TEMPOS DE EXECUÇÃO DAS ATIVIDADES ...................63
6.6 EXERCÍCIOS .............................................................................................................65
7 BIBLIOGRAFIA ..................................................................................................................68
D.R.R.
II
PESQUISA OPERACIONAL
1 A INFLUÊNCIA DA PESQUISA OPERACIONAL NO
PROCESSO DE TOMADA DE DECISÃO
1.1 INTRODUÇÃO
O nome "Pesquisa Operacional" apareceu pela primeira vez durante a Segunda
Grande Guerra, quando equipes de pesquisadores procuraram desenvolver métodos
para resolver determinados problemas de operações militares. O fato que marcou o
surgimento da pesquisa operacional foi a formação de uma equipe de especialistas de
diversas disciplinas, com treino científico para fins de estudar a melhor eficiência no
uso de equipamentos de radar. Esta equipe foi chefiada pelo físico Blackett, e ficou
conhecida como Circo de Blackett, e embora recebesse esse nome depreciativo foi
altamente eficiente na tarefa que lhe foi confiada. Houve fatos anteriores mas este
marcou o início dos trabalhos das equipes de analistas operacionais que começaram
a se expandir na Grã-Bretanha e após no Canadá, na Austrália e nos Estados Unidos.
O sucesso dessas aplicações levou o mundo acadêmico a empresarial a procurar
utilizar as técnicas criadas em problemas de administração.
Desde seu nascimento, esse novo campo de análise de decisão caracterizou-se
pelo uso de conhecimentos científicos por equipes interdisciplinares, no esforço de
determinar
a
melhor
utilização
de
recursos
limitados.
Essa
característica
multidisciplinar das aplicações de Pesquisa Operacional deu um novo enfoque - o
enfoque sistêmico - aos problemas de decisão das empresas, pois ultrapassou as
fronteiras da especialidade. O especialista tem tendência natural a enquadrar todos os
problemas dentro dos limites de sua cultura, mesmo porque é nesse campo que ele se
sente mais confortável. Além disso, a medida que se expandiam as empresas diminuía
cada vez mais a possibilidade de serem administradas por um único homem.
Conseqüentemente, o dono da indústria começou a dividir seu trabalho, atribuindo
parte deste a outras pessoas. Começaram a surgir, por exemplo, os gerentes de
produção, financeiros, de venda, de pesquisa e de desenvolvimento, e com o
crescimento industrial que se seguiu, tais funções foram por sua vez, fracionadas.
D.R.R.
PESQUISA OPERACIONAL
Novos mercados surgiram, novas fontes de matéria-prima foram descobertas tornando
as operações industriais geograficamente dispersas, exigindo a criação de novos
centros de produção e escritórios de vendas, cada qual com administração própria.
Um aspecto importante e negativo desta evolução foi que não se aplicou o
conhecimento científico às novas funções de direção que iam surgindo na
Administração. Até pouco tempo o dirigente vivia isolado com seus problemas e para
solucioná-los usava apenas a sua capacidade de julgamento adquirida através da
experiência. Entretanto exigia-se cada vez mais do dirigente que passou a necessitar
de ajuda de pessoas com mais experiência dos problemas que surgiam e com mais
tempo para consulta-los. Isto provocou o aparecimento dos consultores de
administração, cuja atividade no início não se baseava nem na ciência nem na
pesquisa científica. Somente após o surgimento efetivo da pesquisa operacional,
desenvolvida nas organizações militares a partir da Segunda Guerra Mundial é que se
teve o emprego da pesquisa científica para auxiliar o dirigente.
Outra característica importante que a Pesquisa Operacional possui e que facilita
muito o processo de análise de decisão é a utilização de modelos. Isto permite a
"experimentação", o que significa que uma decisão pode ser mais bem avaliada e
testada antes de ser efetivamente implementada. A economia de recursos e a
experiência adquirida advindas da experimentação, por si só, justificam o conhecimento e a utilização da Pesquisa Operacional como instrumento de administração de
empresas.
O imenso progresso da Pesquisa Operacional se deve também, em grande
parte, ao desenvolvimento dos computadores digitais, em face de sua velocidade de
processamento e capacidade de armazenamento e recuperação das informações.
Outro fato que atualmente muito contribui para o uso intensivo de modelos em análise
de decisões é a disseminação dos microcomputadores, que se tornaram unidades de
processamento descentralizadas dentro das empresas. Isto está levando os
profissionais de Pesquisa Operacional a desenvolverem modelos mais versáteis, mais
rápidos e, principalmente, interativos, que permitem maior participação do homem no
desenrolar dos cálculos.
Resumidamente pode-se conceituar Pesquisa Operacional como o uso do
método científico para prover os departamentos executivos de elementos quantitativos
D.R.R.
2
PESQUISA OPERACIONAL
para tomada de decisões com respeito a operações sob seu controle, sendo as
principais características as seguintes:
a) Orientação para sistemas: esta orientação baseia-se no fato de que em
sistemas organizados o comportamento de qualquer parte afeta a todas as demais.
Assim os analistas em pesquisa operacional procuram analisar o problema de todos
os ângulos possíveis a fim de darem uma solução favorável ao todo, e não a um
departamento específico;
b) Emprego de equipes interdisciplinares: é necessário analisar e avaliar o
problema segundo o maior número de pontos de vista possível. Eis a razão das
equipes de pesquisa interdisciplinar;
c) Aplicação do método científico a problemas de controle.
1.2 A TOMADA DE DECISÃO
Uma vez que a Pesquisa Operacional é um ramo da ciência administrativa que
fornece instrumentos para a análise de decisões, vamos, na seqüência conceituar e
listar as principais características de um processo de tomada de decisão.
O objetivo que temos em vista é a procura de entendimento das características
principais do processo e de suas dificuldades, de forma que possamos compreender
como a Pesquisa Operacional, vista como um conjunto de técnicas quantitativas, pode
auxiliar a gerência na preparação e na tomada de decisão.
Podemos entender a tomada de decisão como o processo de identificar um
problema ou uma oportunidade e selecionar uma linha de ação para resolvê-lo. Um
problema ocorre quando o estado atual de uma situação é diferente do estado
desejado. Uma oportunidade ocorre quando as circunstâncias oferecem a chance do
indivíduo/organização ultrapassar seus objetivos e/ou metas, logo, uma decisão é o
resultado de um processo que se desenvolve a partir do instante em que o problema
foi detectado. Este conceito explicita, claramente, a importância do processo de
preparação na tomada de decisão.
D.R.R.
3
PESQUISA OPERACIONAL
1.3 PRINCIPAIS CARACTERÍSTICAS DO PROCESSO DE TOMADA
DE DECISÃO
As características principais do processo decisório que têm importância na
conceituação de racionalidade da ação gerencial estão descritas e comentadas a
seguir.
a) Processo de decisão seqüencial
Mesmo quando se tem a impressão de que a decisão foi tomada de impulso, ela
é conseqüência de uma série de fatos anteriores que criaram as bases para se chegar
à decisão. Uma decisão significativa é uma compilação de muitas decisões,
abrangendo um leque de aspectos do problema e, freqüentemente, requerendo um
longo período de tempo. É, muitas vezes, difícil apontar com precisão o ponto exato do
processo no qual a decisão foi tomada, afluindo durante as discussões na forma de
consenso.
b) Processo complexo
Além do fato de que quase sempre a informação relativa ao problema é
insuficiente, o processo decisório consiste de um inter-relacionamento entre pessoas,
responsabilidades pelo serviço, comunicação e sistemas de informações, códigos de
ética e moral e, às vezes, interesses e objetivos diferentes dos participantes. O
inter-relacionamento entre esses elementos e o grau de importância de cada um muda
com a evolução do processo, ao longo do tempo. É claro, também, que dentro da
empresa o próprio processo varia, dependendo do problema e do nível de decisão
requerido. Assim, os processos diferem em:
§
tamanho do grupo de decisão;
§
tipos de sistemas de informações gerenciais;
§
tipos de decisões que devem ser tomadas;
§
estilo de liderança dos administradores;
§
nível da decisão dentro da empresa.
c) Processo envolve valores subjetivos
Embora a maior parte do processo que deve ser seguido para preparar melhores
D.R.R.
4
PESQUISA OPERACIONAL
decisões seja identificável e clara, podendo ser repetida por outras pessoas ou em
outras ocasiões, o método pelo qual o valor de julgamento do executivo é colocado na
decisão é estritamente pessoal. É enorme o número de fatores intuitivos, provenientes
de experiência pessoal e personalidade, envolvidos no processo decisório.
Evidentemente, não se pode negar a importância desses fatores na qualidade da
decisão tomada.
d) Processo em ambiente institucional
Todas as companhias têm uma estrutura organizacional própria que influência e
muitas vezes condiciona o processo decisório. O inter-relacionamento entre pessoas,
a forma como se processa o fluxo de informações, as características da organização e
o sistema hierárquico são fatores que afetam fundamentalmente o processo de
tomada de decisão.
1.4 OBSTÁCULOS A UMA DECISÃO RACIONAL
Diversas dificuldades e obstáculos aparecem para conturbar o processo de
tomada de uma decisão estritamente racional, por mais vontade que o administrador
tenha de não se deixar influenciar. Dentre eles podemos destacar:
§
Tempo Disponível Para a Tomada de Decisão: às vezes, a urgência de uma
solução faz com que o administrador tome uma decisão com conhecimento
incompleto dos dados do problema;
§
A Importância da Decisão: pode demorar mais ou menos tempo em função
da análise a ser feita devido à maneira como uma decisão afeta a empresa;
§
O Ambiente: às vezes gera forças que podem transformar uma boa decisão
em fracasso, por exemplo, flutuações da política econômica do governo;
§
Certeza / Incerteza e Risco: dependendo do grau de risco ou de certeza de
determinadas variáveis, uma decisão necessita ou não de uma análise mais
aprofundada e cuidadosa;
§
Agentes Decisores: algumas limitações são de caráter pessoal do
administrador, como força do hábito, falta de memória e distração,
prejulgamentos a valores pessoais, etc;
D.R.R.
5
PESQUISA OPERACIONAL
§
Conflito de Interesses: dificuldades que surgem devido ao caráter político da
decisão, como, por exemplo, a necessidade de compromisso entre diferentes
posições e órgãos da empresa.
No entanto, existem duas dificuldades que são inerentes ao problema e que
podem influenciar fundamentalmente a qualidade da decisão. A seguir será feita uma
discussão mais detalhada.
a) Escolha do problema certo para resolver
Fazer certas as coisas é muito importante, porém o administrador deve se
dedicar em primeiro lugar a encontrar as coisas certas para fazer. Isto significa que o
primeiro passo para uma tomada de decisão racional é saber qual o problema que
requer solução. Normalmente, os problemas não aparecem com um rótulo impresso
pedindo uma solução, mas surgem através de sintomas: reclamações, atrasos,
prejuízos, etc. Assim, a primeira tarefa do administrador deve ser identificar claramente
qual é o problema que causa aqueles efeitos perturbadores. Conforme Peter Drucker,
"a fonte mais comum de enganos, na administração, é a ênfase em encontrar a
resposta certa em lugar de procurar a questão certa para responder".
b) Conhecimento insuficiente
A condição ideal para um processo de decisão racional seria a posse de um
conhecimento completo acerca de todas as alternativas possíveis, como também
acerca das possíveis conseqüências de cada alternativa. Contudo, na vida real essa
condição é praticamente impossível, e o administrador deve tomar suas decisões com
base em informações incompletas ou parciais. Isto ocorre por várias razões.
Em primeiro lugar, informação tem custo, o que significa que, quanto mais
informação o administrador pedir, mais tempo e dinheiro serão gastos para sua
obtenção. Por outro lado, se pouca informação cria um ambiente de incerteza para o
processo de decisão, informação demais também pode prejudicar, já que exigiria
tempo e habilidades extras para análise. Desta forma, o administrador, muitas vezes,
prefere suprir uma parte da falta de informações com sua experiência pessoal.
D.R.R.
6
PESQUISA OPERACIONAL
1.5 O ENFOQUE GERENCIAL DA P.O.
A Pesquisa Operacional pode ser vista segundo dois ângulos diferentes, dois
enfoques contrários na abordagem, mas coerentes e complementares na aplicação
prática no campo da administração.
O enfoque tradicional é o conceito quantitativo da Pesquisa Operacional. Neste, a
Pesquisa Operacional é definida como uma ciência que visa a aplicar métodos
matemáticos e estatísticos à solução de problemas de decisão, através de uma
abordagem sistêmica, pela utilização de modelos. Essa definição, conceitualmente
exata, leva à idéia - que grande parte dos administradores tem - de que a Pesquisa
Operacional apenas fornece um conjunto de técnicas e métodos que são úteis para a
solução de determinados problemas, quando esses podem ser escritos na forma
correta.
É uma visão, até certo ponto, correta, que foi por muito tempo extremamente útil
ao desenvolvimento dessa ciência, pois alinhou em torno de si um contingente
numeroso de matemáticos, engenheiros, físicos, economistas e pessoas de muitas
outras especialidades, pesquisando e desenvolvendo métodos para a solução de
problemas. Esse esforço resultou numa coleção de métodos matemáticos e algoritmos
de tal porte que é praticamente impossível um especialista de Pesquisa Operacional
conhecer todos.
No entanto, na área da administração, essa linha tradicional esbarrou no fato de
que os administradores de nível mais elevado dentro das empresas (que são os que
efetivamente tomam as decisões) se sentiam incomodados com o rigor matemático
dos métodos de Pesquisa Operacional e, muitas vezes, frustrados pela pouca
flexibilidade dos modelos que somente respondiam a perguntas padronizadas. Assim,
os executivos viam, e ainda vêem, a Pesquisa Operacional como uma ciência que
desenvolveu métodos operacionais que servem, às vezes, para resolver certos tipos de
problemas.
A outra visão decorre de um conceito qualitativo da Pesquisa Operacional. Nesse
caso, a importância dos métodos matemáticos desenvolvidos pelo esforço dos
pesquisadores está menos na solução dos problemas e mais nas suas formulações. A
importância da PO estaria, então, na sua influência sobre o modo pelo qual os
administradores abordam os problemas, na maneira como os formulam, na avaliação
D.R.R.
7
PESQUISA OPERACIONAL
que fazem do relacionamento com outros problemas e na forma usada para sua
comunicação a outras pessoas.
Nessa abordagem qualitativa, o enfoque central é deslocado do método de
solução (geralmente um algoritmo matemático complexo) para a formulação e para a
modelagem, ou seja, para o diagnóstico do problema. Perde importância o rigor
matemático da solução, e ganha relevância o espírito crítico e a sensibilidade para
descobrir o problema correto e analisar quais informações são fundamentais para a
decisão e quais são acessórias, apenas completando, sem, no entanto, afetar os
resultados.
O enfoque qualitativo da Pesquisa Operacional é o reconhecimento de que a
abordagem quantitativa dos problemas fornece uma estrutura de raciocínio e análise
que permite descobrir qual é a informação necessária. A informação abundante
atrapalha tanto quanto a falta de informação. E, como toda informação tem um custo, o
problema principal torna-se avaliar o potencial da informação com relação a seu custo.
Podemos considerar que a finalidade de toda informação é reduzir o grau de
incerteza envolvida na decisão. Assim, a informação só tem valor no contexto de uma
situação específica, e sua importância para o administrador reside na possibilidade de
poder alterar a decisão.
É nesse aspecto do problema de decisão que a Pesquisa Operacional cumpre
uma função importante. Na ausência de uma abordagem quantitativa, para avaliar o
potencial da nova informação, a decisão de comprá-la é mais governada pelo temor
do desconhecido do que por uma análise racional de custos e benefícios.
O conhecimento de disciplinas exatas e o treinamento em abordagem
quantitativa de problemas levam o administrador a pensar nos problemas em termos
precisos e a usar técnicas elaboradas de análise, procurando enfocar a estrutura
básica dos problemas ao invés de suas características particulares. O resultado, em
muitos casos, não é uma nova ferramenta de administração, mas uma nova estrutura
conceitual de trabalho para o administrador, uma nova maneira de pensar.
1.6 A METODOLOGIA DE UM ESTUDO DE P.O.
De uma forma geral, um estudo de Pesquisa Operacional desenvolve-se
D.R.R.
8
PESQUISA OPERACIONAL
conforme o diagrama da figura abaixo. Logicamente que essa seqüência de passos
não é rígida, mas indica as principais etapas que devem ser vencidas. Exceto a fase
de Solução do Modelo que se baseia em métodos e técnicas bem desenvolvidos, as
demais fases não seguem regras fixas e definidas. Os procedimentos necessários
para essas fases dependem do tipo do problema em análise e do ambiente que o
envolve.
Definição do
problema
Construção
do modelo
Solução do
modelo
Validação
do modelo
Implementação
da solução
Avaliação final
Experiência
FIG. 1 – Diagrama das fases de um estudo de Pesquisa Operacional.
Apesar das dificuldades aparentes de fixação de regras para a execução dessas
fases, é conveniente que seja feita alguma discussão sobre elas de forma a servir de
guia geral de procedimento. Os retornos de informação, indicados na figura 1 entre as
diferentes etapas representam revisões que as considerações derivadas da análise de
uma etapa provocam em etapas precedentes.
a) Definição do problema
A definição do problema, do ponto de vista da Pesquisa Operacional, baseiase
em três aspectos principais que devem ser discutidos:
§
uma descrição exata dos objetivos do estudo;
§
uma 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. A equipe
encarregada do estudo deve procurar captar e refletir, na formulação do problema, os
desejos e necessidades dos executivos com relação ao problema de decisão.
Da mesma forma, é essencial que as alternativas de decisão e as limitações
D.R.R.
9
PESQUISA OPERACIONAL
existentes sejam todas explicitadas, para que as soluções obtidas no final do processo
sejam válidas e aceitáveis. Quanto mais precisa esta definição, mais fáceis serão as
etapas posteriores.
b) Construção do modelo
Estando bem definidas as características do caso em estudo, a partir destas
deve-se construir uma representação formal do mesmo, isto é, deve-se conseguir
expressar de forma, mais ou menos exata, a realidade através de um modelo.
O modelo mais apropriado para a representação do sistema deve ser escolhido
com base na definição do problema. Se o modelo elaborado tem a forma de um
modelo-padrão, como, por exemplo, de programação linear, a solução pode ser obtida
por métodos matemáticos convencionais.
Por outro lado, se as relações matemáticas são muito complexas ou mesmo
indefinidas, poderemos usar a técnica da simulação e, em alguns casos, haverá
necessidade de usarmos uma combinação de duas metodologias.
c) Solução do modelo
Esta terceira fase tem por objetivo encontrar uma solução para o modelo
construído.
No caso de modelos matemáticos, a solução é obtida pelo algoritmo mais
adequado, em termos de rapidez de processamento e precisão de resposta. Isto exige
do analista de Pesquisa Operacional um conhecimento profundo das principais
técnicas. A solução obtida, neste caso, é dita ótima.
Entretanto, como o modelo de otimização nunca é representação perfeita da
realidade do sistema, a solução ótima obtida para o modelo pode não ser a solução
ótima para o sistema. Então espera-se que o modelo seja uma boa representação do
problema e, conseqüentemente, que a solução ótima obtida seja uma boa
aproximação da solução ótima do sistema e que seja pelo menos significativamente
melhor que a política ou o procedimento que ela irá substituir.
Se os modelos de simulação são utilizados, o conceito de otimalidade não é
bem definido, e a solução obtida é uma avaliação aproximada das medidas do
sistema ou do objetivo a ser atingido.
D.R.R.
10
PESQUISA OPERACIONAL
d) Validação do modelo
Nesta altura do processo de solução do problema, é necessário verificar a
validade do modelo. Um modelo é válido se, a despeito de sua inexatidão em
representar o sistema, ele for capaz de fornecer uma previsão aceitável de seu
comportamento.
Um método comum para testar a validade do modelo é analisar seu desempenho
com dados passados do sistema e verificar se ele consegue reproduzir o
comportamento que este manifestou. Conforme os resultados, ou se retrocede as
etapas anteriores refazendo o problema, no caso negativo, ou passa-se à fase da
implementação da solução obtida, no caso satisfatório.
É importante observar que esse 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.
e) Implementação da solução
Avaliadas as vantagens e a validade da solução obtida, esta deve ser convertida
em regras operacionais. A implementação, sendo uma atividade que altera uma
situação existente, é uma das etapas críticas do estudo. É conveniente que seja
controlada pela equipe responsável, pois, eventualmente, os valores da nova solução,
quando levados à prática, podem demonstrar a necessidade de correções nas
relações funcionais do modelo ou do conjunto dos possíveis cursos de ação, exigindo
a reformulação do modelo em algumas de suas partes.
A presença da equipe permite, também, superar mais facilmente as resistências
e oposições às alterações propostas na sistemática das operações e que,
normalmente, aparecem nessa fase do trabalho.
f) Avaliação final
A avaliação dos resultados obtidos em qualquer etapa do processo é de
fundamental importância, pois isto garantirá melhor adequação das decisões às
necessidades do sistema e aceitação mais fácil dessas decisões por todos os setores
D.R.R.
11
PESQUISA OPERACIONAL
envolvidos.
Nessa avaliação, um fator que tem papel primordial é a experiência do pessoal
envolvido no estudo. Não se deve esquecer que um modelo é apenas uma
representação simplificada, não conseguindo por isto captar todas as características e
nuanças da realidade. Assim, é com experiência e visão crítica que conseguimos
avaliar e determinar a aplicabilidade da decisão.
D.R.R.
12
PESQUISA OPERACIONAL
2 MODELAGEM
Para escolher a ação preferida, ou seja, a que mais se aproxima do objetivo
almejado, o executivo procura visualizar as conseqüências prováveis de cada
alternativa possível. É evidente que esse processo é tão mais simples e intuitivo
quanto mais simples for a decisão, não importando se é uma decisão doméstica ou
empresarial.
No entanto, mesmo em problemas simples onde o executivo não precisa formular
conscientemente listas de alternativas de ação e respectivas conseqüências, em
algum ponto do processo de decisão, ele deve fazer uma ligação entre o que pode
fazer e o que acontecerá em cada caso.
Isto significa que ele deve ter um modelo mental do processo para gerar as
conseqüências possíveis das ações. Contudo, a partir de um certo nível de
complexidade, torna-se quase impossível estimar corretamente as implicações de uma
decisão, sem avaliar corretamente a informação disponível, numa forma lógica e
ordenada. Esse tipo de análise estruturada dos dados é essencialmente uma forma de
modelagem.
Na definição de Pidd (1998) um modelo é uma representação externa e explícita
de parte da realidade vista pela pessoa que deseja usar aquele modelo para entender,
mudar, gerenciar e controlar parte daquela realidade.
2.1 O PROCESSO DE MODELAGEM
Quando os gerentes se vêem diante de uma situação na qual uma decisão deve
ser tomada entre uma série de alternativas conflitantes e concorrentes, duas opções
básicas se apresentam: 1) usar a sua intuição gerencial e 2) realizar um processo de
modelagem da situação e realizar exaustivas simulações dos mais diversos cenários,
de maneira a estudar mais profundamente o problema.
D.R.R.
PESQUISA OPERACIONAL
Até recentemente, a primeira opção se constituía na única alternativa viável, visto
que não existiam nem dados e/ou informações sobre os problemas, ou mesmo poder
computacional para resolvê-los. Com o advento dos microcomputadores e com o
aprimoramento da tecnologia de bancos de dados, esta deixou de ser a única opção
para os tomadores de decisão. Um número cada vez maior de empresas e tomadores
de decisão começou a optar pela segunda forma de tomadas de decisão, isto é,
através da elaboração de modelos para auxiliar este processo.
Na realidade, nos dias de hoje está ocorrendo o inverso de 20 anos atrás.
Possivelmente, a grande maioria dos tomadores de decisão está adotando a segunda
opção de agir. Devemos ressaltar dois fatos relevantes:
a) A quantidade de informações disponíveis cresceu exponencialmente nos
últimos anos com advento da internet, o que nos levou ao problema inverso de
20 anos atrás; a quantidade de dados é tão grande que se torna impossível
montar modelos com todas estas informações. Devemos, portanto, separar as
informações relevantes das irrelevantes, de maneira a modelar a situação para
que possamos analisá-la.
b) Muitos gerentes deixaram de utilizar sua intuição completamente, o que é
bastante prejudicial ao processo de tomada de decisão, pois uma base de
conhecimentos pode estar sendo desperdiçada.
Portanto, achamos que as duas opções devem ser utilizadas conjuntamente, para
melhorar ainda mais o processo de tomada de decisão; a intuição do tomador de
decisão deve ajudá-lo na seleção das informações relevantes, nos possíveis cenários
a serem estudados, na validação do modelo e na análise de seus resultados dos
mesmos. Este processo pode ser representado pela Figura 2.
Mundo
Real
Mundo
Real
Mundo simbólico
Situação
Gerencial
Modelo
Resultado
Decisões
Intuição
Figura 2 - Processo de tomada de decisão.
D.R.R.
14
PESQUISA OPERACIONAL
2.2 VANTAGENS DA UTILIZAÇÃO DO PROCESSO DE
MODELAGEM
Diversas vantagens podem ser citadas quando o decisor utiliza um processo de
modelagem para a tomada de decisão, dentre elas destacam-se:
§
Os modelos forçam os decisores a tornarem explícitos seus objetivos.
§
Os modelos forçam a identificação e o armazenamento das diferentes
decisões que influenciam os objetivos.
§
Os modelos forçam a identificação e o armazenamento dos relacionamentos
entre as decisões.
§
Os modelos forçam a identificação das variáveis a serem incluídas e em que
termos elas serão quantificáveis.
§
Os modelos forçam o reconhecimento de limitações.
§
Os modelos permitem a comunicação de suas idéias e seu entendimento
para facilitar trabalho de grupo.
Dadas estas características, os modelos podem ser utilizados como ferramentas
consistentes para a avaliação e divulgação de diferentes políticas empresariais.
2.3 TIPOS DE MODELOS
O relacionamento entre variáveis em um modelo é, na maioria das vezes, escrito
em termos matemáticos. Existem diversas formas de gerar e utilizar essas relações, e
por isso existem vários tipos de modelos.
O modelo mais apropriado para um dado contexto ou problema depende de
vários fatores como:
§
natureza matemática das relações entre as variáveis;
§
objetivos do tomador de decisões;
§
extensão do controle sobre as variáveis de decisão;
§
nível de incerteza associado com o ambiente da decisão.
Com base nestas considerações, podemos dividir os modelos em dois grandes
tipos:
D.R.R.
15
PESQUISA OPERACIONAL
§
modelos de simulação;
§
modelos de otimização.
Será analisado mais detalhadamente o modelo de otimização, objeto principal da
disciplina. Porém, antes serão enumerados princípios básicos de modelagem,
baseados em Pidd (1998).
2.4 PRINCIPIOS DE MODELAGEM
Este item cobre alguns princípios gerais que podem ser aplicados ao
desenvolver um modelo que será útil nas ciências administrativas. Seu foco é
claramente prático; a idéia é dar ao aluno alguns pontos para considerar e alguns
princípios que lhe possam ser úteis. Mas é importante ter em mente que alguns destes
princípios são quase questões de estilo. Tais assuntos precisam ser internalizados e
personalizados.
PRINCÍPIO 1: Pensar complicado mas modelar simples
Modelos simples são mais fáceis de entender que os complexos. Escrevendo
sobre as características desejáveis de modelos de decisão, John Little (1970)
argumentou que uma propriedade essencial era que eles deviam ser simples. Isto
porque é mais fácil atingir a transparência com modelos simples. Por isso, estes
levantam uma chance maior de serem usados do que os complicados. Dentro das
ciências administrativas, os modelos são construídos para ajudar pessoas e
organizações a se tornarem mais efetivas no que fazem. Isto significa que seus
resultados precisam ser usados e isto requer confiança da parte do usuário. A
confiança é mais fácil de ser atingida quando o usuário é, pelo menos, capaz de
apreciar o trabalho global do modelo. É importante não ler isto como que sugerindo
que um modelo das ciências administrativas deve sempre ser limitado pela proeza
técnica das pessoas responsáveis pelo trabalho. Em vez disso, a idéia de
simplicidade precisa estar ligada com outra sugestão de que o modelo deveria ser
fácil de manipular. A idéia de que devemos "modelar simples e pensar complicado"
nos traz de volta para a idéia de que modelos são "ferramentas para pensar". Seria
errado interpretar esta frase como sendo "ferramentas para substituir o pensamento".
D.R.R.
16
PESQUISA OPERACIONAL
Em vez disso, eles são ferramentas que suportam e estendem o poder do
pensamento. Assim, um modelo complicado, que é pobremente empregado, pode ser
pior que um modelo simples usado como uma ferramenta para pensar
cuidadosamente.
PRINCÍPIO 2: Começar com pouco e acrescentar
O problema com o primeiro princípio de simplicidade é saber o quão simples ou
complicado se deve ser, e não existe resposta geral para isto. Em vez de tentar, no
estágio inicial, um modelo maravilhoso que incorpora todo aspecto da situação em
uma forma realista, nós começamos com alguma coisa manejável, que pode ter
considerações irrealistas. A intenção é aprender o que podemos deste simples
modelo e então refiná-lo gradativamente, sempre que necessário. Powell (1995)
chama de "prototipagem" a mesma abordagem, pois carrega a idéia de que é melhor
desenvolver rapidamente um modelo de trabalho, mesmo que imperfeito. Ele pode ser
refinado, ou mesmo abandonado, mais tarde.
PRINCÍPIO 3: Evitar megamodelos
Esteja ciente do propósito geral de modelos grandiosos que tentam incorporar
praticamente tudo. Tais modelos são difíceis de validar, de interpretar, de calibrar
estatisticamente e, mais importante, de explicar. Você pode tornar-se melhor, não com
um grande modelo, mas com um conjunto de modelos mais simples. (Raiffa,1982,
citado em Miser e Quode, 1990b)
PRINCÍPIO 4: Usar metáforas e analogias
Ao invés de ficar restrito a uma consideração direta do problema abordado, pode
ser útil tentar obter uma outra perspectiva das coisas. Este uso de outras perspectivas
deveria ser distinguido do uso de um modelo para entender diferentes pontos de vista
e interpretações. Aqui a idéia é que recursos como metáforas, analogias e problemas
relacionados podem ser de grande ajuda. A idéia das analogias é levar as pessoas a
obterem novas visões de coisas que poderiam ser muito familiares ou, no extremo
oposto, não são entendidas. Em termos de modelagem das ciências administrativas,
isto significa tentar obter novos insights que poderiam levar a modelos úteis.
D.R.R.
17
PESQUISA OPERACIONAL
PRINCÍPIO 5: Descartar dados, se necessário
É o modelo que deveria conduzir os dados e não vice-versa. Isto significa que o
analista deve tentar desenvolver algumas idéias do modelo e seus parâmetros e, a
partir disto, deve pensar sobre o tipo de dado que poderia ser necessário. Dados não
são substitutos para o pensamento cuidadoso e crítico. Na vida real, os dados devem
ser requeridos, justificados e coletados antes de poderem ser analisados, eles não
são gratuitos, e sua coleta tem um custo assim como sua interpretação e análise.
PRINCÍPIO 6: Construir modelos pode ser como desenredar-se
Uma vez que um modelo, como usado nas ciências administrativas, é o resultado
de uma tentativa de representar alguma parte da realidade de forma tal que as ações
possam ser tomadas ou algum entendimento possa ser melhorado, poderia se pensar
que a construção de modelo é um processo linear e altamente racional, na qual
progressos suaves são feitos e na qual tudo se encaixa perfeitamente. Na prática, o
que se verificou em alguns estudos, é que modeladores experientes pulam de tópico
para tópico enquanto modelam e precisam refinar suas idéias constantemente.
2.5 MODELOS DE OTIMIZAÇÃO
Em diversas áreas do mundo real existe a escassez de um certo produto ou
matéria-prima por sua dificuldade de produção e/ou de obtenção, entre outras razões.
Esta dificuldade gera problemas para empregar melhor estes recursos escassos de
forma eficiente e eficaz. Busca-se, portanto, maximizar ou minimizar uma quantidade
(Lucro, Custo, Receita, nº de produtos, entre outros), chamada de objetivo, que
depende de um ou mais recursos escassos. Estes processos de otimização de
recursos são aplicados a diversas áreas e entre elas podemos citar:
D.R.R.
§
Determinação de Mix de Produtos.
§
Escalonamento de Produção.
§
Roteamento e Logística.
§
Planejamento Financeiro.
§
Carteiras de Investimento.
18
PESQUISA OPERACIONAL
§
Análise de Projetos.
§
Alocação de Recursos de Mídia.
§
Designação de Equipe.
A área que estuda a otimização de recursos é denominada Programação
Matemática. Nela a quantidade a ser maximizada ou minimizada é descrita como uma
função matemática dos recursos (variáveis de decisão) escassos. As relações entre
as variáveis são formalizadas através de restrições ao problema expressas como
equações e/ou inequações matemáticas. De uma maneira geral, os problemas de
Programação Matemática podem ser representados da seguinte forma:
Otimizar:
z = f (x1,x2,...,xn)
Sujeito a
g 1 = ( x1 , x 2 ,..., xn )  b1
≤
g 2 = ( x1, x 2 ,..., x n )  b2
=
...
 ≥ ...
g m ( x1, x 2 ,..., x n  bm
Onde:
xj
- representa as quantidades das variáveis utilizadas; (j = 1,2 . .. n)
bj
- representa a quantidade disponível de um determinado recurso;
(j = 1,2 ... m)
X
- vetor de xj .;
f(X) - função-objetivo;
gj (X) - funções utilizadas nas restrições do problema;
n
- número de variáveis de decisão;
m
- número de restrições do modelo.
Por ser uma área muito extensa é subdividida em áreas menores dependendo do
tipo das funções utilizadas nas funções-objetivo e restrições. Entre estas podemos
citar:
§
Programação Linear - Programação Matemática em que todas as
funções-objetivo e restrições são representadas por funções lineares.
D.R.R.
19
PESQUISA OPERACIONAL
§
Programação Não-linear - Programação Matemática em que pelo menos uma
das funções-objetivo e/ou restrições são representadas por funções
não-lineares.
Entre
os
diversos
tipos
de
Programação
Não-linear
encontram-se alguns tipos importantes, como a Programação Côncava,
Convexa e Quadrática.
Nos próximos capítulos falaremos mais detalhadamente sobre problemas de
programação linear e da maneira mais adequada para resolvê-los.
2.5.1 Procedimentos para Desenvolver Problemas de Otimização
Os passos básicos que compõem o desenvolvimento de problemas de
otimização estão relacionados a seguir.
a) Definição do problema
Inicialmente o administrador deve reconhecer que existe um problema para o qual
é indicada a procura da melhor solução, pela pesquisa dos valores ótimos das
variáveis de decisão.
Em geral, podemos considerar que será mais útil empregar técnicas de
otimização, em vez de simulação, para procurar iterativamente uma solução ótima, ou
próxima da ótima, quando:
§
existirem muitas variáveis de decisão ou quando as variáveis puderem
assumir valores numa faixa ampla de viabilidade, fazendo com que os
modelos de simulação se tornem muito lentos;
§
existirem restrições nos recursos ou variáveis que tornam complexo o
processo de escolha dos valores das variáveis;
§
os sistemas forem tais que algumas variáveis devem ter seus valores
calculados de forma precisa, para respeitar restrições ou evitar grandes
variações no resultado final.
b) Identificação das variáveis relevantes
O conjunto de variáveis relevantes para um modelo de otimização inclui:
§
D.R.R.
as variáveis de decisão para as quais o administrador procura valores ótimos;
20
PESQUISA OPERACIONAL
§
variáveis exógenas (ou variáveis não controláveis, têm seus valores
determinados externamente ao modelo) que servem de base para a definição
de restrições ou de variáveis endógenas (ou variáveis controláveis, têm seus
valores dependentes de uma ou mais variáveis, sendo calculadas
internamente ao modelo);
§
variáveis endógenas que, dependendo dos valores de outras, muitas vezes
entram na formação da função-objetivo, que o administrador deve especificar.
c) Formulação da função-objetivo
A função-objetivo reflete o critério de otimização das variáveis de decisão e deve
ser escrita na forma matemática.
d) Formulação das restrições
Em grande número de modelos de otimização, as variáveis são sujeitas a
algumas restrições, que devem ser escritas em forma matemática. Da mesma forma, o
relacionamento entre as variáveis deve ser formulado matematicamente.
e) Escolha do método matemático de solução
Tendo definido o problema, devemos agora escolher um método matemático
apropriado para a solução do modelo. A escolha do método é feita tendo em vista o
tipo de modelo matemático criado e as análises e questões para as quais o modelo
deve fornecer subsídios.
f) Aplicação do método de solução
O método de solução é simplesmente um exercício matemático que pode ser
realizado manualmente ou por computador. Em qualquer dos casos, um conhecimento
do algoritmo será necessário, seja para desenvolver o processo de cálculo, seja para
acompanhar a solução do computador e entender suas mensagens.
g) Avaliação da solução
Uma vez obtida a solução, esta deve ser verificada e avaliada à luz das
expectativas e experiências do administrador, antes de sua efetiva implementação. É
D.R.R.
21
PESQUISA OPERACIONAL
claro que, nessa fase do modelo, tanto pode ser aceito como pode ser necessário proceder as correções, para incorporar novas restrições, novas variáveis ou novos
critérios. É importante lembrar que a maioria das decisões devem ser tomadas em um
ambiente de risco e incerteza e que grande parte dos modelos de otimização são
determinísticos. Assim, uma estimativa do risco deve ser conseguida através de uma
análise de sensibilidade pós-otimização.
2.6 EXERCÍCIOS
1) Uma pequena empresa fabrica dois tipos de produtos similares entre si, sendo que
cada produto passa pelas mesmas 3 máquinas para ser manufaturado. Como cada
máquina possui um determinado valor limite de horas semanais para produzir e cada
produto necessita de tempos diferenciados para completar o processo de manufatura,
o gerente de produção deseja saber qual a quantidade a fabricar por semana de cada
produto a fim de maximizar o lucro da empresa. O quadro abaixo apresenta um
esquema do problema proposto.
Máquina J
Máquina K
Máquina L
Lucro por unidade
Horas necessárias por
unidade
Produto A
Produto B
3
2
2
2
2
4
R$ 12,00
R$ 8,00
Horas disponíveis por semana
Até 42
Até 30
Até 48
2) O vendedor de uma revenda de automóvel ganha comissão da 10% e 20% sobre o
preço de venda de cada unidade dos modelos LS e TS respectivamente. Seu contrato
com o dono da loja diz que ele deve vender no mínimo 3 unidades do modelo LS e 2
unidades do modelo TS por mês. O dono da loja tem disponibilidade para aplicar no
mês atual UM 80.000, sendo que o custo de compra é de UM 8.000 por unidade do
modelo LS e UM 10.000 por unidade do modelo TS. Historicamente a loja vende no
mínimo 6 automóveis por mês. Sabendo que o preço da venda ao consumidor é de
UM 15.000 e UM 20.000 para modelos LS e TS respectivamente. Qual o número de
D.R.R.
22
PESQUISA OPERACIONAL
unidades de cada modelo que devem ser vendidas por mês de modo que o vendedor
tenha o máximo rendimento?
3) Uma empresa que aluga equipamentos para controle de qualidade, possui 2 tipos
de aparelhos, o Quality Top (QT) e o Quality Basic (QB). Ela possui 7 aparelhos do tipo
QT, que podem inspecionar 40 peças/hora, com um custo operacional de UM 8,00 por
hora. Possui também 10 aparelhos do tipo QB, que inspecionam 30 peças/hora, com
custo operacional de UM 7,00 por hora. Sabendo que o máximo de peças a serem
inspecionadas é 2600 peças por dia (8 horas de trabalho por dia) e que a empresa
cobra um aluguel de UM 22/hora por aparelho tipo QT e UM 17/hora por aparelho tipo
QB, elaborar o modelo de PL que permita calcular o número de aparelhos de cada um
dos dois tipos que devem ser alugados a fim de maximizar o lucro da empresa.
4) Uma indústria produz determinado móvel em dois modelos, o luxo e o standard. O
modelo luxo é produzido com um lucro de US$ 300,00 por unidade e o standard com
um lucro de US$ 100,00 por unidade O modelo standard requer 2 horas de fabricação,
ocupa uma área de 4 m2 por unidade no armazenamento e não necessita de pintura.
Já o modelo luxo requer 3 horas de fabricação, ocupa 3 m2 por unidade no
armazenamento e 1 hora para pintura. O tempo disponível para elaboração encontrase limitado em 24 horas, o espaço para armazenagem em 36 m2 e a seção de pintura
dispõe de 6 horas. Pergunta-se quantas unidades de cada modelo de móvel devem
ser fabricadas a fim de maximizar o lucro da empresa?
5) Uma metalúrgica deseja maximizar sua receita bruta. A tabela a seguir ilustra a
proporção de cada material na mistura para a obtenção das ligas passíveis de
fabricação. O preço está cotado em Reais por tonelada da liga fabricada. Também em
toneladas estão expressas as restrições de disponibilidade de matéria-prima.
Formular o modelo de Programação Matemática.
D.R.R.
23
PESQUISA OPERACIONAL
Restrições/Custo
Cobre
Zinco
Chumbo
Preço de Venda
(R$ por Ton)
Liga Especial de Baixa
Resistência (*)
0,5
0,25
0,25
R$ 3.000
Liga Especial de Alta
Resistência (*)
0,2
0,3
0,5
R$ 5.000
Disponibilidade de
Matéria-prima
16 Ton
11 Ton
15 Ton
Ton de minério
(*) -------------------Ton de liga
6) As especificações para construção de uma estrada determinam uma espessura de
revestimentos de 12 a 48 cm. O revestimento pode ser feito com concreto e/ou asfalto.
As especificações também requerem uma resistência final de no mínimo 9 cm de
concreto. Sabe-se que 3 cm de asfalto equivalem à resistência de 1 cm de concreto.
Sabe-se também que cada cm de espessura de 1 m2 custa UM 10.000,00 e UM
3.500,00 para respectivamente concreto e asfalto. Se o objetivo é minimizar os custos
da estrada, quais as espessuras de asfalto e concreto a adotar?
7) Uma empresa mineradora possui duas jazidas diferentes que produzem um dado
tipo de minério. Depois do minério ser triturado ele é classificado em três classes:
superior, médio e inferior. Existe uma certa demanda para cada classe de minério. A
empresa de mineração possui uma fábrica de beneficiamento com a capacidade para
12 toneladas da classe superior, 8 da média e 24 da inferior por semana. A empresa
gasta UM 900,00 por dia para operar a primeira jazida e UM 720,00 para operar a
segunda. Essas jazidas tem contudo, capacidades diferentes. Durante um dia de
operação, a primeira jazida produz 6 toneladas de minério de classe superior, 2 de
classe média e 4 de classe inferior, enquanto que a segunda jazida produz diariamente
2 toneladas de minério de classe superior, 2 de classe média e 12 de classe inferior.
Pergunta-se quantos dias por semana deve operar cada jazida para satisfazer, da
maneira mais econômica, as encomendas feitas à empresa?
8) Uma companhia produz dois tipos de camisas: manga longa e manga curta. Na
companhia, o único ponto crítico é a mão-de-obra disponível. A camisa de manga
longa consome 50 % a mais de mão-de-obra do que a de manga curta. Sabe-se
também que se toda a produção fosse concentrada na disponibilização de camisas de
D.R.R.
24
PESQUISA OPERACIONAL
manga curta a companhia poderia entregar 400 camisas de manga curta por dia. O
mercado limita a produção diária de camisas em 150 mangas longas e 300 mangas
curtas. O lucro bruto por camisa de manga longa é de UM 5,00 e por camisa de manga
curta UM 3,5 . Formular o problema de modo a permitir a determinação das
quantidades de camisas a produzir de modo a otimizar o lucro.
9) A empresa Serra Serra Serrador fabrica três tipos de madeiras compensadas
(placas de aglomerados). Os dados abaixo resumem a produção em horas por
unidade em cada uma das três operações de produção, o tempo máximo disponível
em cada operação e o lucro unitário de cada placa:
Aglomerado
Placa A
Placa B
Placa C
Tempo máximo disponível
I
2
5
10
900
II
2
5
3
400
Operações em horas
III
Lucro por Unidade
4
$40
2
$30
2
$20
600
Quantas unidades de cada placa de aglomerado devem ser produzidas, de maneira a
otimizar o lucro da Serraria?
10) Um sitiante está planejando sua estratégia de plantio para o próximo ano. Por
informações obtidas nos órgãos governamentais, sabe que as culturas de trigo, arroz e
milho serão as mais rentáveis na próxima safra. Por experiência, sabe que a
produtividade de sua terra para as culturas desejadas é a constante na tabela abaixo:
Restrições do problema do plantio
Cultura
Trigo
Arroz
Milho
Produtividade em kg por m2
(experiência)
0,2
0,3
0,4
Lucro por kg de Produção
(Informações do Governo)
10,8 centavos
4,2 centavos
2,03 centavos
Por falta de um local de armazenamento próprio, a produção máxima, em toneladas,
está limitada a 60. A área cultivável do sítio é de 200.000 m2. Para atender as
demandas de seu próprio sítio, é imperativo que se plante 400 m2 de trigo, 800 m2 de
arroz e 10.000 m2 de milho.
D.R.R.
25
PESQUISA OPERACIONAL
11) Uma grande fábrica de móveis dispõe em estoque de 250 metros de tábuas, 600
metros de pranchas e 500 metros de painéis de conglomerado. A fábrica normalmente
oferece uma linha de móveis composta por um modelo de escrivaninha, uma mesa de
reunião, um armário e uma prateleira. Cada tipo de móvel consome uma certa
quantidade de matéria prima, conforme a tabela abaixo. A escrivaninha é vendida por
UM 100, a mesa por UM 80, o armário por UM 120 e a prateleira por UM 20. Pede-se
exibir um modelo de Programação Linear que maximize a receita com a venda dos
móveis.
Restrições/Custos
Tábua
Prancha
Painéis
Valor de
Revenda (UM)
Quantidade de material em metros
Consumidos por unidade do produto
Escrivaninha
Mesa
Armário
Prateleira
1
1
1
4
0
1
1
2
3
2
4
0
100
80
120
20
Disponibilidade
do Recurso (m)
250
600
500
12) A fábrica de aço Boca do Monte S/A tem duas instalações, uma em Santa Maria SM e outra em São Pedro do Sul - SPS, cada uma produzindo dois tipos de aço, o
C.A. 50 e o C.A. 60. Devido a restrições de ordem operacional, nenhuma das
instalações pode funcionar mais do que 18h por dia. Na instalação de SM, leva-se 2h
para produzir 1 tonelada de aço C.A 50 e 1h para produzir 1 tonelada de aço C.A. 60.
Na instalação de SPS, leva-se 1h para produzir 1 tonelada de aço C.A. 50 e 3h para
produzir 1 tonelada de aço C.A. 60. Na instalação SM, o custo por tonelada aço C.A.
50 é de UM 35 e UM 30 para o aço C.A. 60, enquanto que na instalação SPS, o custo
por tonelada na fabricação de cada um dos dois tipos de aço é de UM 25. A usina de
aço tem a obrigação de produzir diariamente pelo menos 14 toneladas de aço C.A. 50
e 16 toneladas de aço C.A. 60. Como deve ser organizada a produção para que o
custo da quantidade necessária de cada tipo de aço seja o menor possível?
13) O objetivo do presente programa é determinar, em uma dieta para a redução
calórica, as quantidades de certos alimentos que deverão ser ingeridos diariamente,
D.R.R.
26
PESQUISA OPERACIONAL
de modo que determinados requisitos nutricionais sejam satisfeitos a custo mínimo.
Existem vários problemas abordando esse tema, o presente exemplo é um dos mais
simples possíveis. Suponha que, por motivos justificáveis, uma certa dieta alimentar
esteja restrita a leite desnatado, carne magra de boi, carne de peixe e uma salada de
composição bem conhecida. Sabendo-se ainda que os requisitos nutricionais serão
expressos em termos de vitaminas A, C e D e controlados por suas quantidades
mínimas (em miligramas), uma vez que são indispensáveis à preservação da saúde da
pessoa que estará se submetendo à dieta. A tabela abaixo resume a quantidade de
cada vitamina em disponibilidade nos alimentos e a sua necessidade diária para a
boa saúde de uma pessoa.
Restrições de nutrientes na dieta alimentar
Vitamina
Leite
(litro)
Carne
(kg)
Peixe
(kg)
Salada
(100 g)
A
C
D
Custo
2 mg
50 mg
80 mg
2 reais
2 mg
20 mg
70 mg
4 reais
10 mg
10 mg
10 mg
1,5 real
20 mg
30 mg
80 mg
1 real
Requisito
Nutricional
Mínimo
11 mg
70 mg
250 mg
Formular o programa para a otimização dos recursos envolvidos.
D.R.R.
27
PESQUISA OPERACIONAL
3 PROGRAMAÇÃO LINEAR
Os problemas de alocações de recursos escassos a atividades competitivas são
resolvidos pelas técnicas de Programação Linear (PL). Estas técnicas são
apropriadas para os casos em que variáveis do problema estão linearmente
relacionadas entre si. A sua aplicação tem sido grande no contexto industrial e
produzem às vezes uma respeitável economia. Mesmo que a PL não seja o único meio
de otimizar os retornos de um determinado sistema, muitos dos relacionamentos
fundamentais das quantidades tornam convidativa a sua utilização.
Os estudos dos sistemas de produção apresentam muitas oportunidades para as
aplicações da PL, pois ela pode ser empregada vantajosamente nos estágios de
planejamento, análise e controle. Os problemas aplicáveis incluem o planejamento da
localização com maior facilidade de suprimento a fim de minimizar os custos de
transporte, a análise das operações e métodos para aumentar os lucros e o controle
do carregamento das máquinas para maximizar a utilização.
Resumidamente, a PL é definida como sendo um conjunto de técnicas
matemáticas com as quais pode ser determinada uma solução ótima para problemas
que apresentam várias soluções possíveis, e indica um método interativo que
determina a melhor combinação de valores que as variáveis do modelo devem assumir
a fim de otimizar a solução, com cada variável obedecendo a certas restrições.
Um problema de PL está em sua forma padrão se existir a maximização da
função-objetivo e se todas as restrições forem do tipo menor ou igual, bem como os
termos constantes e variáveis de decisão não-negativos. Matematicamente
representa-se um problema padrão por:
Maximizar: Z = c 1x1 + c 2x2 + . . . + c nxn
D.R.R.
PESQUISA OPERACIONAL
Sujeito a:
a11x1 + a12x1 + . . . + a1nxn ≤ b1
a21x1 + a22x1 + . . . + a2nxn ≤ b2
.
.
am1x1 + am2x1 + . . . + amnxn ≤ bm
x1, x2, …, xn ≥ 0
ou na forma reduzida:
Maximizar:
Z=
n
∑c x
j j
j=1
n
Sujeito a:
∑a x
j=1
ij
j
≤ bi (i = 1,2,...,m)
x1, x2, …, xn ≥ 0
Uma padronização de termos deve ser introduzida a fim de facilitar o
entendimento. Solução é qualquer especificação de valores para as variáveis de
decisão, independente de se tratar de uma escolha desejável ou permissível. Solução
Viável é uma solução em que todas as restrições são satisfeitas. Solução Ótima é uma
solução viável que tem o valor mais favorável da função-objetivo, isto é, maximiza ou
minimiza a função-objetivo em toda a região viável, podendo ser única ou não.
3.1 SOLUÇÃO GRÁFICA
A seleção de uma combinação ótima é uma introdução ideal aos métodos de PL.
Determinar a proporção de produção de cada produto quando os recursos de
produção são limitados é um exemplo típico das aplicações da PL, que mostram como
utilizar recursos escassos para maximizar o lucro. Uma combinação de dois produtos
tem como vantagem a simplicidade que permite colocar em questão os fatos básicos.
D.R.R.
29
PESQUISA OPERACIONAL
Uma das tarefas difíceis da avaliação dos sistemas de produção é reconhecer
qual a melhor maneira de atacar o problema. O conhecimento das exigências da PL
que serão dadas a seguir deverá revelar se o problema está sujeito a esta forma de
solução.
1º) O objetivo deve ser definido explicitamente.
2º) Os recursos devem ser limitados.
3º) As varáveis devem ser linearmente relacionadas, e estes relacionamentos
são expressos por inequações ou equações.
Quando um problema envolve apenas duas variáveis de decisão, a solução ótima
de um problema de PL pode ser encontrada graficamente.
Após a modelagem do problema, a metodologia a seguir é:
a) colocar retas no gráfico para cada restrição;
b) identificar o polígono das soluções possíveis;
c) traçar uma reta para função-objetivo;
d) tirar paralelas à função-objetivo;
e) se o problema for de minimização, o ponto ótimo é obtido a partir da paralela
de “Z” até encontrarmos o ponto mais próximo da origem, dentro do polígono
das soluções possíveis. Se o problema for de maximização, o ponto ótimo é
aquele mais afastado da origem dentro do polígono de soluções possíveis.
A fim de demonstrar o método gráfico e seus casos especiais (soluções
múltiplas, soluções ilimitadas e problemas sem solução), são propostos os exemplos
abaixo.
1) Max Z = 5x1 + 2x2
Sujeito a:
x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≤ 9
x1, x2 ≥ 0
2) Min Z = 7x1 + 9x2
Sujeito a:
D.R.R.
30
PESQUISA OPERACIONAL
- x1 + x2 ≤ 2
x1 ≤ 5
x2 ≤ 6
3x1 + 5x2 ≥ 15
5x1 + 4x2 ≥ 20
x1, x2 ≥ 0
3) Min Z = 6x1 + 10x2
Sujeito a:
- x1 + x2 ≤ 2
x1 + 2x2 ≥ 1
x1 ≤ 5
x2 ≤ 6
3x1 + 5x2 ≥ 15
5x1 + 4x2 ≥ 20
x1, x2 ≥ 0
4) Max Z = 6x1 + 10x2
Sujeito a:
- x1 + x2 ≤ 2
x2 ≤ 6
3x1 + 5x2 ≥ 15
5x1 + 4x2 ≥ 20
x1, x2 ≥ 0
5) Max Z = x1 + x2
Sujeito a:
x1 + x2 ≤ 12
x1 + x2 ≥ 20
x1, x2 ≥ 0
D.R.R.
31
PESQUISA OPERACIONAL
3.2 SOLUÇÃO ALGÉBRICA – MÉTODO SIMPLEX
A resolução de um problema de PL consiste basicamente em resolver sistemas
de equações lineares e calcular o valor da função-objetivo. Comparando os diversos
valores obtidos para esta função-objetivo, escolhe-se como solução do problema o
resultado do sistema de equações que fornece o maior valor, no caso de resolvermos
um problema padrão de PL, ou seja, de maximização.
Esse procedimento, apesar de correto e elegante, é bastante trabalhoso, já que
temos de resolver todos os sistemas para podermos escolher o que dá maior valor
para a função-objetivo, ou menor no caso de minimização. Em um problema real de
PL, onde pode-se ter, por exemplo, 40 equações e 50 variáveis, o número de sistemas
de equações que deveríamos resolver é extremamente elevado, o que é impraticável,
mesmo para um computador.
Assim, para termos condições de resolver o problema de PL, precisamos de
uma sistemática que nos diga:
§
qual o sistema de equações que deve ser resolvido;
§
que o próximo sistema a ser resolvido fornecerá uma solução melhor que as
anteriores;
§
como identificar uma solução ótima, uma vez que a tenhamos encontrado.
Essa sistemática é o método Simplex, e de forma resumida pode-se dizer que é
um processo iterativo para determinar soluções básicas viáveis para um sistema de
equações e testá-las quanto à otimidade. As etapas utilizadas no método para atender
às três questões acima estão descritas no próximo tópico.
3.2.1 Etapas do Método Simplex
a) Transformação das desigualdades em igualdades através da introdução
de variáveis de folga (falta ou excesso)
inequações de sinal ≤ adiciona-se a variável de folga.
inequações de sinal ≥ subtrai-se a variável de folga.
b) Montar o Quadro Simplex
Colocar os coeficientes de todas as variáveis com os respectivos sinais, da
D.R.R.
32
PESQUISA OPERACIONAL
função objetivo (cj ), das variáveis nas equações (aij ) e os termos independentes (bi )
são então transferidos para uma tabela que é a Solução Básica Inicial (SBI) do
problema:
Variáveis Naturais
Base
xn+1
xn+2
...
xn+m
Zj
x1
a11
a21
...
am1
c1
x2
a12
a22
...
am2
c2
x3
a13
a21
...
am3
c3
...
...
...
...
...
Variáveis de Folga
xn
a1n
a21
...
amn
cn
xn+1
1
0
...
0
cn+1
xn+2
0
1
...
0
cn+2
...
...
...
...
...
...
Solução
xn+m
0
0
0
1
cn+m
bi
b1
b2
...
bm
0
Divisão
c) Troca de Base
Em cada iteração será determinada uma nova solução básica (outro ponto
extremo). Para isso é necessário realizar a troca de base. A escolha da variável que
deve entrar na base é feita pela REGRA SIMPLEX 1.
c.1) REGRA SIMPLEX 1
A seleção da Variável que entra na base depende dos valores de Zj . A variável
selecionada será aquela que apresentar o maior valor de Zj . Se todos os valores de Zj
são ≤ 0, então a solução ótima foi encontrada.
A variável que sai da base é dada pela REGRA SIMPLEX 2.
c.2) REGRA SIMPLEX 2
A seleção da variável que deve deixar a base é feita pelo valor obtido pela
divisão dos números da coluna solução (bi ) pelos coeficientes a ij na coluna da variável
que entrar na base.
Selecione a linha com a menor razão (ignore as razões com denominador zero ou
negativo). A variável desta linha deve deixar a base.
d) Pivoteamento
O processo de pivoteamento envolve a obtenção da matriz dos coeficientes das
varáveis básicas como uma matriz identidade, visto que somente uma variável básica
D.R.R.
33
PESQUISA OPERACIONAL
entra na tabela, a cada iteração, a matriz identidade é completada usando as
operações de linha para obter coeficiente unitário na posição do elemento pivô, aij na
linha que saiu e coluna de entrada e coeficientes zeros nas demais posições da coluna
pivô (coluna da variável que entrou na base).
Para obter coeficiente unitário na posição pivô divide-se os termos da linha pivô
(linha da variável que deixou a base) pelo elemento pivô. Registra-se a nova linha no
novo quadro. As seguintes operações de linha são feitas para obter zeros nas demais
posições da coluna pivô, usando a seguinte fórmula:
[Nova Linha “n”] = [Antiga Linha “n”] – {[Coeficiente da Coluna Pivô] x [Nova Linha Pivô]}
Esta fórmula é aplicada para cada linha que não seja pivô e cada equação
resultante é registrada no novo quadro. Obtém-se, assim, a matriz dos coeficientes das
variáveis básicas como matriz identidade. Na coluna solução tem-se os valores das
variáveis básicas, sendo as variáveis não básicas nulas.
e) Verificação da Otimidade
Se todos os valores Zj forem ≤ 0 a solução é ótima, porém se existir algum Zj > 0,
repete-se o processo desde a troca de base, isto é, calcula-se a próxima solução
básica.
3.2.2 Utilização das Variáveis Artificiais
Ocorrência:
a) Quando há inequação de sinal ≥ pois nesse caso teremos que colocar variável
de folga negativa.
b) Quando existir b i negativo e a inequação for do tipo ≤.
c) Quando tivermos uma equação.
Quando ocorrer variáveis artificiais no problema, o método, chamado de Método
das Duas Fases, será o seguinte:
a) Deve-se acrescentar uma função objetiva W que será minimizada a fim de
anular as variáveis artificiais;
D.R.R.
34
PESQUISA OPERACIONAL
b) O problema simplex terá duas fases:
Fase I : Minimizar W, isto é, W = 0 anulando as variáveis artificiais.
Fase II: Otimizar a função objetiva Z.
c) A função objetiva W artificial será
W = D 1x1 + D 2x2 + . . . + D nxn + D n+1xn+1 + . . . D n+m xn+m + . . . + D n+m+k xn+m+k
Onde: xn+m+k = variáveis artificiais
n
Dj = ∑ A ij
das equações que possuem variáveis artificiais
W = ∑ bi
das equações que possuem variáveis artificiais
i+1
d) Otimização da fase I
1º) Quando os Dj
≤
e W = 0, a função objetiva está otimizada passando então
para a fase II, eliminando a linha de coeficientes de W e a coluna de variáveis
artificiais.
2º) Quando os D j
≤
e W < 0 o problema não tem solução viável.
3.3 EXERCÍCIOS
Resolver todos do item 2.5
D.R.R.
35
PESQUISA OPERACIONAL
4 PROBLEMAS DE TRANSPORTE
O problema de transporte é um tipo especial de problema de PL, sendo que sua
resolução pelo Método Simplex é bastante trabalhosa. Por isso foi desenvolvido um
algoritmo especial para a resolução. O algoritmo de transporte visa simplificar a
obtenção da solução ótima, entretanto, nada impede que os modelos de transporte
sejam resolvidos pelo método simplex, uma vez que este, resolve qualquer modelo de
programação linear.
Este modelo visa minimizar o custo total do transporte, envolvendo “m” origens
cada uma dotada de “ai ” (i = 1,2, . . ., m) unidades disponíveis de um produto
homogêneo, e “n” destinos cada um dos quais requerendo “bj ” (j = 1,2, . . . , n) unidades
deste produto. Os números “ai ” e “bj ” são inteiros e positivos. O custo “cij ” de
transportar uma unidade da origem “i” para o destino “j” é conhecido para cada valor
de “i” e “j”. Matematicamente o problema é definido da seguinte maneira:
Função-objetivo:
m n
Min Z =
∑ ∑ c ij xij
i=1 j=1
Sujeito a:
n
∑ xij = ai (i = 1,2,...,m)
j=1
(4.1)
m
∑ xij = bj (j = 1,2,...,n)
j=1
x ij ≥ 0 ( i = 1, 2, . . . , m) e (j = 1, 2, . . . , n)
D.R.R.
PESQUISA OPERACIONAL
Observe que nas restrições do modelo todos os coeficientes das variáveis são
iguais a 1. Comparando as restrições de oferta e demanda, obtém-se:
m
n
i=1
j=1
∑ ai = ∑ b j
(4.2)
Esta igualdade indica que o modelo de transporte exige uma igualdade entre
oferta total e demanda total (problema equilibrado). Para explicar o algoritmo de
transporte é necessário representar o modelo (4.1), por meio da tabela a seguir:
DESTINOS
1
2
. . .
n
OFERTA
c11
c 21
.
.
.
cm1
c12
c 22
.
.
.
c m2
. . .
. . .
c1n
c 2n
.
.
.
c mn
a1
a2
.
.
.
am
ORIGENS
1
2
.
.
.
m
. . .
m
∑ ai
DEMANDA
b1
b2
. . .
bn
i =1
n
∑bj
j =1
Quadro 4.1.
Necessitar-se-ia de outro quadro envolvendo as quantidades a serem
transportadas da origem “i” ao destino “j”.
DESTINOS
1
2
. . .
n
OFERTA
x11
x 21
.
.
.
x m1
x12
x22
.
.
.
x m2
. . .
. . .
x1n
x2 n
.
.
.
x mn
a1
a2
.
.
.
am
ORIGENS
1
2
.
.
.
m
. . .
m
∑ ai
DEMANDA
b1
b2
. . .
bn
i =1
n
∑bj
j =1
Quadro 4.2.
D.R.R.
37
PESQUISA OPERACIONAL
Como se deseja que a solução combine “n” custos e as quantidades
transportadas envolvidas entre as origens “i” e os destinos “j”, nada mais lógico que
trabalhar-se com a combinação dos dois quadros.
DESTINOS
1
. . .
2
n
OFERTA
ORIGENS
1
2
.
.
.
M
c11
x11
c12
x12
c 21
x 21
c 22
x22
.
.
.
. . .
c1n
a1
x1n
c 2n
a2
x2 n
.
.
.
cm1
x m1
. . .
.
.
.
c m2
x m2
. . .
.
.
.
c mn
am
x mn
m
∑ ai
DEMANDA
b1
b2
. . .
bn
i =1
n
∑bj
j =1
Quadro 4.3.
4.1 FORMULAÇÃO DO MODELO
Através da formulação do modelo de transporte pode-se notar que os
coeficientes das variáveis são unitários envolvendo um só tipo de variável. Dois casos
podem ocorrer: o problema de transporte equilibrado, onde a oferta é igual à demanda,
e o problema de transporte desequilibrado, onde a oferta é diferente da demanda.
Ambos serão apresentados a seguir.
4.1.1 Problema de Transporte Equilibrado
Supondo que um fazendeiro possui quatro granjas A, B, C e D, produzindo
D.R.R.
38
PESQUISA OPERACIONAL
diariamente 50.000, 50.000, 60.000 e 30.000 litros de leite respectivamente. Vende
toda a produção em três cidades I, II e III, que necessitam 70.000, 70.000 e 50.000
litros de leite diariamente. O custo de transporte por litro está na tabela abaixo:
GRANJA A
GRANJA B
GRANJA C
GRANJA D
CIDADE I
10
15
12
13
CIDADE II
15
10
16
18
CIDADE III
12
16
10
16
O modelo pode ser formulado da seguinte maneira:
Seja xij ( i = A, B, C e D; j = I, II, III) a quantidade a ser transportada da granja “i”
para a cidade “j”.
O modelo de transporte será:
Min Z = 10 xAI + 15xAII + 12xAIII + 15xBI +10xBII + 16xBIII + 12xCI + 16xCII + 10xCIII +
13xDI + 18xDII + 16xDIII
Sujeito a:
xAI + xAII + xAIII = 50.000
xBI + xBII + xBIII = 50.000
xCI + xCII + xCIII = 60.000
xDI + xDII + xDIII
= 30.000
xAI + xBI + xCI + xDI = 70.000
xAII + xBII + xCII + xDII = 70.000
xAIII + xBIII + xCIII+ xDIII
= 50.000
e xiJ ≥ 0 para i = A, B, C, D e j = I, II, III.
Pode-se observar que a oferta total de leite é de 190.000 litros e é igual à
demanda. Neste caso o problema é equilibrado.
D.R.R.
39
PESQUISA OPERACIONAL
4.1.2 Problema de Transporte Desequilibrado
Agora vamos supor que duas fábricas, FA e FB abastecem dois depósitos D1 e
D2, sendo as quantidades ofertadas e demandadas de unidades de produto estão
relacionadas abaixo:
Fábrica A: 20 unidades
Fábrica B: 40 unidades
∑ Oferta = 60 unidades
As quantidades requeridas em cada depósito são:
Depósito 1: 30 unidades
Depósito 2: 20 unidades
∑ Demanda = 50 unidades
Os custos unitários de transporte aparecem no quadro abaixo:
D1
D2
FA
10
25
FB
20
15
Neste caso a oferta total é maior que a demanda total, indicando que será
necessário fazer estocagem do produto. Para equilibrar a oferta com a demanda, criase um depósito (consumidor) fictício com demanda igual a 10 unidades que é a
diferença entre a oferta e a demanda total.
Sendo xij ( i = A, B, C e D; j = I, II, III) a quantidade a ser transportada da fábrica “i”
para o depósito “j”.
As quantidades xA3 e xB3 devem ficar estocadas nas fábricas A e B, pois não
existe o depósito 3.
Os custos CA3 e CB3 representam os custos unitários de estocagem em cada
depósito, serão considerados como C A3 = C B3 = 0.
A formulação do modelo será:
Min Z = 10 xA1 + 25xA2 + 20xB1 +15xB2
Sujeito a:
xAI + xAII + xAIII = 20
xBI + xBII + xBIII = 40
D.R.R.
40
PESQUISA OPERACIONAL
xAI + xBI = 30
xAII + xBII = 20
xAIII + xBIII = 10
Pode-se ter também o somatório da demanda maior que o somatório da oferta.
Neste caso cria-se uma fábrica (produtor) fictícia e procede-se como no caso
mostrado anteriormente.
4.2 METODOLOGIA DE SOLUÇÃO
Após verificar se o problema de transporte é equilibrado ou não, e se não for
equilibrá-lo conforme foi mostrado acima, parte-se para a obtenção da Solução Básica
Inicial (SBI) através de dois métodos mais comuns, que são:
a) Método do custo mínimo.
b) Método de Vogel.
O objetivo de cada método é obter uma SBI viável. Antes de se aplicar o modelo
de SBI, precisa-se apontar o número de variáveis básicas do problema de transporte.
O número de variáveis básicas é (m + n – 1), porque as restrições são de igualdade, e
este conjunto de (m + n) equações tem uma equação extra ou redundante que pode ser
eliminada sem mudar a região viável. Qualquer uma das restrições é satisfeita sempre
que as outras (m + n – 1) restrições forem satisfeitas. A seguir apresentar-se-á o
procedimento para selecionar as variáveis básicas de tal modo que satisfaça a todas
as restrições.
4.2.1 Método do Custo Mínimo
Procedimentos:
1º) Localize no quadro de custos o menor Cij e coloque nessa célula, a maior
quantidade permitida pela oferta e demanda correspondente.
2º) Atualize os valores de oferta e demanda que foram modificados e volte a
localizar o menor Cij . O procedimento se repete até que sejam esgotadas
todas as ofertas e supridas todas as demandas.
D.R.R.
41
PESQUISA OPERACIONAL
4.2.2 Método de Vogel
Procedimentos:
1º) Para cada linha e coluna do problema, calcule a diferença entre os dois
menores custos unitários (C ij ).
2º) Escolher a linha ou coluna que tenha a maior diferença, onde seleciona-se a
variável que tiver o menor custo (C ij ).
3º) Na célula escolhida, colocar a maior quantidade possível permitida pela
oferta e demanda.
4º) Repetir o procedimento até esgotar as quantidades de ofertas e demandas
(todas restrições satisfeitas).
Pode-se utilizar 2 critérios para desempate:
1º) Havendo empate entre linhas ou colunas, seleciona-se entre as possíveis a
célula de menor custo unitário.
2º) Havendo empate entre linhas e/ou colunas e células com menor custo,
escolhe-se a linha ou coluna onde é possível fazer a maior atribuição.
4.2.3 Método U – V ou Distribuição Modificada
É o primeiro passo para verificar se a solução encontrada é a solução ótima do
problema de transporte. Antes de proceder ao cálculo dos valores de “U” e “V” testa-se
a SBI quanto à degeneração através da seguinte fórmula: (m + n –1) = número de
células básicas (células cheias pela distribuição realizada), onde m = número de linhas
e n = número de colunas do quadro.
Procedimentos:
1º) Preparar a matriz que contenha os custos associados às células para cada
alocação feita;
2º) Estabelecer o conjunto de números Vj e outro conjunto Ui , da seguinte
maneira:
b) Arbitrar Ui = 0.
b) Matematicamente calcular, com auxílio das células cheias, a partir de C ij
= Ui + V j , as demais células básicas.
D.R.R.
42
PESQUISA OPERACIONAL
c) Através da equação Qij = Cij – (Ui + Vj ) calcular os custos associados
para as células vazias.
d) Se houver qualquer valor negativo de Qij , a solução não é ótima, aplicar o
Circuito de Alpondras.
e) Se todos os valores Qij forem positivos ou nulos a solução é ótima e
então deve-se interpretar o resultado obtido.
4.2.4 Circuito de Alpondras
Este método é utilizado para redistribuir os valores de oferta e demanda caso a
solução encontrada não seja a solução ótima
Procedimentos:
1º) Localizar a célula que tem o menor valor negativo, em caso de empate devese fazer uma escolha arbitrária.
2º) Traçar um circuito de avaliação que deve começar e terminar na célula
escolhida no 1º item.
3º) Iniciar o circuito com o sinal (+), em cada troca de direção atribuir sinais
alternados (+) e (-), sendo permitida a troca de direção apenas em células
ocupadas.
4º) Escolher a menor quantidade (x0 = elemento pivô) onde o sinal do circuito for
negativo.
5º) Somar ou subtrair essa quantidade, conforme o sinal do circuito.
Após completar o procedimento, aplicar novamente o método U – V. Repetir o
procedimento até não existir mais QiJ < 0.
Vamos proceder à resolução dos dois problemas propostos acima!
4.3 DEGENERAÇÃO DO PROBLEMA DE TRANSPORTE
Pode ocorrer em qualquer estágio da solução do problema de transporte.
A degeneração ocorre quando o número de células ocupadas for menor que a
quantidade (m + n) – 1, e pode ser resolvida fazendo-se uma alocação infinitamente
pequena
D.R.R.
ε
em uma célula conveniente. A alocação de
ε
é feita por inspeção e não
43
PESQUISA OPERACIONAL
afeta os totais da linha ou coluna, pois se trata de uma quantia muito pequena. A
colocação de
ε
em determinada célula segue as normas de qualquer alocação
comum. Quando se obtém a solução ótima, ε é igual a zero.
4.4 SOLUÇÕES MÚLTIPLAS
Quando na solução ótima o custo associado for igual a zero, Qij = 0, significa que
o problema possui mais de uma solução ótima, e elas serão tantas outras soluções
ótimas quantos o número de custos associados iguais a zero existirem. Observe no
problema das Cooperativas, descrito acima, os valores dos custos associados da
solução ótima. Para achar a(s) outra(s) solução(ões) utiliza-se o circuito de Alpondras
a partir da célula onde o Qij = 0.
4.5 PROBLEMA DE TRANSPORTE DE MAXIMIZAÇÃO
Neste tipo de problema trabalha-se com os valores de lucros unitários e não mais
com os custos unitários de transporte. Neste caso, escolhe-se o mais valor de lucro
unitário e subtrai-se dos demais valores da tabela formando então uma nova tabela e a
partir desta resolve-se o problema como minimização.
Para ilustrar este caso, vamos resolver o problema abaixo.
Uma empresa de transporte de cargas está assinando um contrato com três
fábricas para transportar as peças produzidas para três centros de consumo conforme
mostra a tabela a seguir.
Lucro líquido por peça transportada
D.R.R.
C.C1
C.C2
C.C3
Oferta
FA
20
30
15
1000
FB
10
20
18
1500
FC
40
25
17
1000
Demanda
1500
800
1200
44
PESQUISA OPERACIONAL
4.6 EXERCÍCIOS
1. Uma vinícola do sul de Santa Catarina possui três fábricas e três armazéns nos
quais os vinhos são envelhecidos. Como as fábricas e os armazéns estão localizados
em diferentes locais do estado, a empresa deseja saber quantos tonéis de vinho deve
enviar de cada fábrica para cada armazém de forma a minimizar o seu custo de
transporte. As capacidades das fábricas e dos armazéns (em número de tonéis), bem
como os custos de transporte por tonel, estão explicitados na tabela a seguir.
Fábricas
F1
F2
F3
Capacidade dos armazéns
A1
20
10
12
200
Armazéns
A2
16
10
18
400
A3
24
8
10
300
Capacidade
das fábricas
300
500
200
2. Um grupo empresarial que fabrica um tipo de calçados para homens possui três
fábricas, em cidades diferentes, que abastece três lojas em cidades diferentes. Os
calçados são transportados encaixotados aos pares, por via rodoviária, para as três
lojas com os custos unitários de transporte mostrados na tabela abaixo. O custo de
produção do par de calçado mais a caixa é de UM 100,00 para a fábrica A, UM 110,00
para a fábrica B e de UM 105,00 para a fábrica C. A produção mensal das fábricas é
de 700, 600 e 600 unidades, respectivamente, enquanto os consumidores solicitam
mensalmente 500, 700 e 500 unidades, respectivamente. O preço de venda por par é
diferente para cada distribuidor, sendo de UM 200,00 para a loja 1, UM 230,00 para a
loja 2 e UM 180,00 para a loja 3. Sabendo que não existe ligação entre a loja 1 e a
fábrica B, determinar qual será o destino da produção de cada fábrica de modo a
maximizar o lucro de vendas. Encontre todas as soluções ótimas possíveis.
Custos unitários de transporte
Fábrica A
Fábrica B
Fábrica C
D.R.R.
Loja 1
50
*
65
Loja 2
70
70
80
Loja 3
40
30
50
45
PESQUISA OPERACIONAL
3. Uma fábrica necessita produzir mensalmente as seguintes quantidades de produtos:
Produto
Classe A
350
Produto
Classe B
250
Produto
Classe C
280
Produto
Classe D
200
Esses quatro produtos podem ser produzidos por qualquer uma das três máquinas
disponíveis, que tem as seguintes capacidades mensais, para qualquer tipo de
produto.
Máquina I
270
Máquina II
320
Máquina III
400
O gerente de produção pode agilizar sua produção mensal produzindo as quantidades
acima no menor tempo possível, para isso foram determinados os tempos unitários de
processamento que são dados abaixo:
Produto
Classe A
Produto
Classe B
Produto
Classe C
Produto
Classe D
Máquina I
3
Máquina II
2,5
Máquina III
4
2
3
4
2,5
1
3,5
4
2
5
Os custos operacionais das máquinas são de UM 12,00; UM 15,00 e UM 10,00 para a
Máquina I, Máquina II e Máquina III, respectivamente. Os custos unitários de matériaprima são de UM 18,00; UM 20,00; UM 15,00 e UM 20,00 para os produtos Classe A,
Classe B, Classe C e Classe D, respectivamente. Determine como deverá ser
programada a produção para minimizar o tempo de processamento total e qual será o
custo mensal total. Responda ainda se há outra solução ótima para o problema.
4. As vendas previstas de junho a dezembro de um novo produto a ser lançado no
mercado pela empresa DPS são:
Junho = Julho = 300 unidades
Outubro = 500 unidades
Agosto = 400 unidades
Novembro = 600 unidades
Setembro = 450 unidades
Dezembro = 1000 unidades
D.R.R.
46
PESQUISA OPERACIONAL
A produção destas 3550 unidades deve ser iniciada em junho e concluída em outubro,
sendo a disponibilidade máxima, em horário normal e extraordinário, para produzir
este novo produto é a seguinte:
Horário Normal
Horário Extraordinário
Junho = Julho = 600 unidades
Junho = Julho = 200 unidades
Agosto = Setembro = 500 unidades
Agosto = Setembro = 600 unidades
Outubro = 300 unidades
Outubro = 700 unidades
Considerando que o custo unitário para produzir no horário normal é de UM 100 por
unidade e em horário extra é o dobro, enquanto o custo de estocagem é de UM 10 por
unidade/mês, determine a melhor programação mensal para a produção deste novo
produto de maneira a satisfazer ao máximo a previsão de vendas, reduzindo ao
mínimo os custos de produção e estocagem.
5. Quatro vendedores de gasolina A, B, C, e D necessitam mensalmente 50.000,
40.000, 60.000 e 40.000 galões. É possível receber gasolina de três localidades I, II e
III, que dispõem respectivamente de 80.000, 100.000 e 50.000 galões, por mês.
Os lucros de envio de 1.000 galões estão na tabela abaixo (em UM):
A
B
C
D
I
7.000
6.000
6.000
6.000
II
5.000
8.000
6.000
7.000
III
8.000
5.000
8.000
6.000
Determinar as quantidades de gasolina que devem ser enviadas de cada localidade
para cada vendedor de tal forma que as necessidades de cada vendedor sejam
satisfeitas e o lucro de transporte seja máximo.
6. A LCL Motores Ltda. fornece motores para um grande número de equipes de
Fórmula 1. A companhia detém uma série de contratos de entregas futuras
programadas para o próximo ano. As entregas deverão ocorrer trimestralmente, de
acordo com as necessidades das equipes. A tabela abaixo resume, por trimestre, as
D.R.R.
47
PESQUISA OPERACIONAL
entregas programadas, a capacidade máxima de produção e o custo unitário de
produção. As entregas são feitas no final do trimestre e os motores podem ser
armazenados por quantos trimestres forem necessários, ao custo de 0,015 milhão de
reais por trimestre. A diretoria deseja minimizar os custos totais de produção. Quantos
e quando os motores pedidos devem ser produzidos?
Dados relevantes de Escala de Produção
Trimestre
1º
2º
3º
4º
D.R.R.
Pedidos
Contratados
10
15
25
20
Capacidade
de Produção
25
35
30
10
Custo Unitário de Produção
(em milhões R$)
1,08
1,11
1,10
1,13
48
PESQUISA OPERACIONAL
5 PROBLEMAS DE DESIGNAÇÃO
O problema de designação ou de alocação de tarefas pode ser modelado e
resolvido de maneira análoga ao modelo de transporte. Para isso basta introduzir as
seguintes restrições:
b) Número de origens = número de destinos (m = n);
b) Capacidade de cada origem = 1 (ai = 1 para todo i);
c) Demanda de cada destino = 1 (bj = 1 para todo j).
Matematicamente, o modelo de designação é definido como a otimização
(maximização ou minimização) da função:
n
n
∑∑c x
i=1 j=1
ij
(5.1)
ij
Em que C ij são os coeficientes de custo e lucro sujeitos as restrições:
n
∑x
i=1
ij
n
∑x
j=1
ij
=1
j = 1, 2, 3, . . . ,n
(5.2)
=1
i = 1, 2, 3, . . . ,n
(5.3)
xij = 0 ou 1 para todo xij.
Claro que apenas uma origem “i” abastecerá um único destino “j”, de modo que
as últimas restrições do modelo (5.2) e (5.3) serão equivalentes. O problema consiste
em determinar como as designações devem ser feitas de forma a minimizar o custo
total.
O modelo da designação, sendo um caso especial do modelo de transporte,
D.R.R.
PESQUISA OPERACIONAL
admite também um algoritmo particular para a sua otimização. Como as capacidades
de cada origem e as demandas de cada destino são unitárias, o algoritmo da
designação será baseado apenas na seguinte matriz:
DESTINOS
1
2
. . .
n
c11
c 21
.
.
.
c n1
c12
c 22
.
.
.
cn2
. . .
. . .
c1n
c 2n
.
.
.
c nn
ORIGENS
1
2
.
.
.
N
. . .
Caso tivermos mais origens que destinos deve-se criar destinos fictícios com
custo para execução e vice-versa. Sempre deverá existir igualdade entre origens e
destinos, isso significa que os números de linhas e colunas da tabela devem ser
obrigatoriamente iguais.
O problema de designação dispõe de um método especial para a sua resolução,
o Método Húngaro, e que consiste das seguintes etapas:
1ª ) Subtrair o menor elemento de cada linha dos elementos restantes desta
mesma linha.
2ª ) Subtrair o menor elemento de cada coluna dos elementos restantes desta
mesma coluna (a ordem destas duas primeiras etapas pode ser invertida).
3ª ) Após, testar a otimalidade da designação das tarefas traçando um número
mínimo de retas que cubram todos os zeros da tabela. Se o número de retas
for igual ao número de linhas ou colunas, a solução encontrada é a ótima. As
retas são traçadas horizontal ou verticalmente, não sendo permitidas retas em
diagonal.
4ª ) Quando a solução ótima não é alcançada, escolhe-se o menor custo não
coberto pelas retas. Então subtrai-se este menor valor de custo de todos os
valores não cobertos pelas retas e soma-se este mesmo valor aos valores das
células que estão na intersecção das retas. Os valores de custos riscados uma
única vez permanecem inalterados.
D.R.R.
50
PESQUISA OPERACIONAL
5ª ) Testar novamente a otimidade do problema conforme a 3ª etapa, caso ainda
não seja a solução ótima, repetir a 4a etapa. As atribuições são feitas
escolhendo-se os zeros na tabela e obedecendo às restrições em que apenas
uma correspondência será atribuída para cada origem.
5.1 PROBLEMA EQUILIBRADO
O problema de designação é equilibrado quando o número de origens é igual ao
número de destinos. O exemplo abaixo ilustra este caso.
Quatro edifícios diferentes devem ser construídos em um campus universitário
por quatro empreiteiras diferentes. Como todos os edifícios devem obrigatoriamente
ser construídos ao mesmo tempo e a capacidade das empreiteiras é construir
somente um edifício, o pró-reitor de planejamento deve decidir qual construção deve
ser designada para qual empreiteira a fim de minimizar o custo total para a
universidade.
Cada empreiteira fez suas propostas no tocante às quatro construções que
aparecem na tabela abaixo em milhares de UM.
Empreiteira A
Empreiteira B
Empreiteira C
Empreiteira D
Edifício I
480
560
960
420
Edifício II
480
600
940
440
Edifício III
500
600
900
540
Edifício IV
440
680
850
460
5.2 PROBLEMA DESEQUILIBRADO
O problema de designação é desequilibrado quando o número de origens é
diferente do número de destinos. Então deve-se criar um destino fictício ou uma
origem fictícia para equilibrar o problema. O exemplo abaixo ilustra este caso.
Uma fábrica possui quatro locais diferentes para receber três máquinas novas.
Em função do layout a máquina A não pode ser instalada no lugar 4. O custo de
manuseio de materiais, em UM por hora, envolvendo cada máquina com as
respectivas posições, é dado a seguir. Sabe-se ainda que não existe nenhum fluxo de
material entre as novas máquinas. O objetivo é designar as novas máquinas aos locais
D.R.R.
51
PESQUISA OPERACIONAL
disponíveis de modo a minimizar o custo total de manuseio de materiais. O gerente de
produção também quer saber se existe mais de uma maneira de designar as
máquinas aos locais com o mesmo custo mínimo total.
Máquina A
Máquina B
Máquina C
Lugar 1
50
30
30
Lugar 2
10
10
30
Lugar 3
30
40
40
Lugar 4
X
30
20
5.3 PROBLEMA DE MAXIMIZAÇÃO
No caso de maximização procede-se da mesma maneira que no problema de
transporte, ou seja, escolhe-se o valor máximo e subtrai-se dos demais valores. A
partir desta nova tabela se procede como no problema de minimização. Quando a
solução ótima é encontrada o valor máximo total será encontrado a partir dos valores
unitários da tabela original. Um problema de maximização é mostrado abaixo.
O diretor de uma empresa precisa enviar quatro gerentes para quatro lojas
localizadas em cidades vizinhas. A seleção será realizada em função eficiência de
vendas obtida pelos vendedores em cada cidade. O diretor atribui a nota conforme as
vendas realizadas por cada um deles durante um período de pesquisa e os resultados
estão na tabela abaixo. Se o objetivo é maximizar as vendas, qual a cidade deve ser
atribuída a cada vendedor?
n
C1
C2
C3
C4
VA
8
9
7
5
VB
7
7
8
3
VC
6
8
5
7
VD
5
5
6
8
m
D.R.R.
52
PESQUISA OPERACIONAL
5.4 EXERCÍCIOS
1. Uma empresa pretende enviar novos diretores regionais para quatro locais de
distribuição. Os custos com a nova organização de cada um dos quatro diretores e os
quatro possíveis locais de trabalho estão dados na tabela abaixo. Determinar a melhor
distribuição a fim de minimizar o custo total da nova organização.
(Custos em UM 1.000,00)
n
I
II
III
IV
A
2
1
4
2
B
3
4
1
6
C
1
2
6
5
D
1
3
3
7
m
2. Uma transportadora possui cinco caminhões localizados em 5 cidades diferentes.
Como ela necessita atender 6 outras cidades é importante saber qual a designação
que minimiza a quilometragem total percorrida. A quilometragem entre as cidades
aparece na tabela abaixo. Apresente todas as alternativas.
DAS
CIDADES
1
2
A
B
C
D
E
20
15
18
8
12
15
32
15
24
20
PARA AS CIDADES
3
4
26
46
2
12
18
40
26
12
22
10
5
6
32
28
6
22
22
12
20
14
20
15
3. Certo gerente esta diante do problema de ter que designar quatro métodos novos
para três instituições produtoras. A designação dos novos métodos aumentará os
lucros conforme as quantidades mostradas a seguir. Se apenas um método puder ser
atribuído a cada instituição produtora, determine a atribuição ótima.
D.R.R.
53
PESQUISA OPERACIONAL
Lucros em mil UM.
INSTITUIÇÃO PRODUTORA
I
II
III
12
9
13,5
10
11
12,5
11,5
10
10
13
12
10,5
MÉTODO
Método 1
Método 2
Método 3
Método 4
4. Uma empresa possui quatro territórios e dispõe de quatro vendedores para serem
designados. Os territórios não são igualmente ricos em seu potencial de vendas.
Espera-se que o potencial de vendas seja o seguinte:
TERRITÓRIO
I
II
III
IV
VENDAS
60.000
50.000
40.000
30.000
Os vendedores diferem em sua habilidade. Estima-se que trabalhando sob mesmas
condições suas vendas seriam com a seguinte eficiência, A = 70%, B = 50%, C = 50%
e D = 40%. Se o objetivo é maximizar as vendas totais, qual deve ser o território
atribuído a cada vendedor?
5. Resolver o problema de designação, considerando um problema de minimização e
depois um problema de maximização.
n
1
2
3
4
5
A
12
8
7
15
4
B
7
9
17
14
10
C
9
10
12
6
7
D
7
8
14
6
10
E
9
6
12
10
6
m
D.R.R.
54
PESQUISA OPERACIONAL
6 REDE PERT-CPM
6.1 INTRODUÇÃO
Projetos são constituídos de conjuntos únicos de operações projetadas para
atingir certos objetivos, dentro de um dado limite de tempo. Para muitos projetos, esse
tempo envolvido é longo e os custos associados são significativamente altos; existem
por vezes centenas e até milhares de atividades que devem ser planejadas e
coordenadas para que o projeto esteja terminado dentro do prazo, do custo e dos
padrões de qualidade especificados.
Duas das mais conhecidas técnicas de planejar e coordenar projetos em grande
escala são o PERT (Program Evaluation and Review Technique) e o CPM (Critical
Path Method). São técnicas especialmente úteis em situações onde os gerentes têm
responsabilidade pelo planejamento, programação e controle de grandes projetos
contendo muitas atividades levadas a cabo por diferentes pessoas, de diferentes
habilidades.
O PERT foi desenvolvido em 1958, graças aos esforços conjuntos da marinha
norte-americana, da Lockheed Aircraft e da firma de consultoria Booz, Allen and
Hamilton. O problema que se punha à época era o desenvolvimento do submarino
atômico Polaris, cujo projeto envolvia milhares de operações a cargo de mais de 3.000
empreiteiros e subempreiteiros. Hoje
em dia, o PERT é usado tipicamente em
projetos cujas estimativas de tempo não podem ser previstas com certeza, obrigando
ao uso de conceitos estatísticos.
O CPM foi desenvolvido em 1957, quando consultores da Remington Rand
Univac (divisão da Sperry Radn Corporation) receberam, por parte da Du Pont
Corporation, a tarefa de criar uma técnica de programação para a construção,
manutenção e desativação de fábricas de processos químicos. O CPM é usado para
projetos cujos tempos de operações podem ser considerados determinísticos, ou seja,
conhecidos com certeza. Com o tempo, entretanto, as diferenças entre o PERT e o
D.R.R.
PESQUISA OPERACIONAL
CPM foram se atenuando e pode-se dizer, atualmente, que essas duas técnicas têm
muito em comum. Os conceitos que iremos desenvolver, como regra geral, valem tanto
para o PERT como para o CPM.
6.2 CONSTRUÇÃO DA REDE PERT/CPM
O processo de construção do Diagrama de Rede para um projeto (quer se fale
em PERT ou CPM) envolve, preliminarmente, a especificação de todas as atividades
que compõem o projeto. Esta é uma etapa chave, que dá base à construção do
Diagrama propriamente dito.
Na construção do Diagrama de Rede, cada atividade será representada por uma
seta, que se inicia e termina em um nó. Existem diversas regras básicas para se
indicar as relações entre as atividades.
Para que o Diagrama se preste à cálculos, é também necessário que sejam
especificadas as durações das atividades. Conforme vimos, no caso CPM a duração
é determinística, e no caso do PERT ela é probabilística.
Vejamos agora as convenções fundamentais para a construção de um Diagrama
de Rede:
1a) Cada atividade é representada por uma única seta, cujo comprimento não
precisa guardar relação com a duração da atividade. É a execução real de uma tarefa,
consome tempo e recursos.
2a) Eventos são pontos significativos na execução do projeto, não consomem
tempo nem recursos. Numa rede PERT / CPM utiliza-se um único evento inicial e um
único evento final. Os eventos são representados pelos nós “i” e “j”. A figura abaixo
mostra a representação pelo método americano.
i
Aij
j
i = Evento inicial da atividade A ij
j = Evento final da atividade A ij
D.R.R.
56
PESQUISA OPERACIONAL
3a) Atividades fantasmas ou fictícias são as que não tem execução real, a
duração é nula. Elas auxiliam no traçado da rede, permitindo uma representação
correta do traçado da mesma.
São utilizadas quando:
1. Temos atividades em paralelo, para permitir a representação correta;
2. Para permitir a representação de certas dependências entre atividades, sem
alterar a ordem tecnológica do projeto.
Representação:
a)
Aij
1
Aij
1
2
3
Bij
Bij
2
INCORRETA
CORRETA
b) Supondo que os trechos abaixo pertençam a uma mesma rede
1
1
A
3
5
A
3
2
B
D
6
C
Isto é, que a atividade B(3, 5) dependa da atividade A(1, 3), que a atividade D(3,
6) dependa da atividade A(1, 3) e C(2, 3), para obtermos a representação correta,
introduzimos uma atividade fictícia:
D.R.R.
57
PESQUISA OPERACIONAL
A
3
B
5
1
C
4
D
4a) Atividades de espera são atividades que embora não representam
execução real, consomem tempo, como por exemplo a secagem de uma lage na
construção de um prédio.
5a) A ordem tecnológica consiste em dispor e interligar as atividades de acordo
com as imposições técnicas do projeto.
6a) Atividades em série são aquelas que se realizam uma após a outra.
7a) Atividades em paralelo são as que podem ser realizadas simultaneamente.
A
1
B
2
3
C
4
8a) Atividades precedentes são as que incidem para dentro de um evento
inicial.
9a) Atividades sucessoras são as que incidem para fora de um evento final.
A
2
C
1
4
B
3
D
Atividade A precede atividade C
Atividade D sucede atividade B
D.R.R.
58
PESQUISA OPERACIONAL
10a) Alguns cuidados no traçado da rede PERT /CPM devem ser observados:
a) Não permitir circuito
A
2
C
1
3
B
4
D
b) Que entre eventos sucessivos só exista uma e somente uma atividade.
6.3 METODOLOGIA DE UTILIZAÇÃO
1) Fase do planejamento: determinação das atividades que compreendem o
projeto.
a) Atividades a serem executadas;
b) Ordem tecnológica;
c) Duração das atividades.
2) Fase do traçado da rede: relacionar as atividades, suas dependências e
suas durações.
3) Fase do cálculo da rede:
a) Determinação do tempo de execução do projeto;
b) Determinação dos tempos operacionais das atividades;
c) Determinação das folgas;
d) Determinação do caminho crítico.
D.R.R.
59
PESQUISA OPERACIONAL
Exemplo:
Determinar o traçado da rede PERT/CPM para o programa abaixo.
SIMBOLOGIA
A
B
C
D
E
F
G
H
ATIVIDADE
PRECEDENTE
A
A
B
C
D, F, G
ATIVIDADE
SUCESSORA
E,D
F
G
H
H
H
-
DURAÇÃO
(MÍN)
10
15
5
20
15
5
10
15
a
m
b
8
10
3
15
8
3
8
10
10
14
4
20
15
5
10
15
12
24
11
15
22
7
12
20
6.4 CÁLCULO DA REDE
6.4.1 O Tempo de Execução do Projeto
A data mais cedo de um evento é o tempo necessário para que o evento seja
atingido, considerando que não haja atrasos imprevistos nas atividades que o
precedem. Ao evento inicial atribui-se o valor zero (0) e para os demais usamos a
fórmula:
DC(j) = MAX { DC(i) + D (i,j) }
Onde:
DC = Data mais cedo
i = Evento inicial da atividade
j = Evento final da atividade.
A data mais tarde de um evento é a data limite, de restrições de um evento, para
que um evento seja otimizado. É a última data em que o evento será concluído, e é
dada por:
DT(i) = MIN { DT(j) – D(i,j) }
Este cálculo é realizado no sentido inverso da rede.
D.R.R.
60
PESQUISA OPERACIONAL
6.4.2 O Caminho Crítico
É o caminho que não apresenta folga nos eventos do projeto e que permite a
realização de todas as atividades, ou seja:
DC(i) = DT(i)
Exemplo:
Calcular as datas + cedo, data + tarde e caminho crítico para a rede abaixo:
A=10
1
B=15
C=5
2
3
4
F=5
D=2
H=15
50
E=1
5
6
G=
6.4.3 Os Tempos Operacionais das Atividades
O tempo de início mais cedo (TIC) de uma atividade é o valor correspondente a
data mais cedo do evento inicial da referida atividade.
TIC (i,j) = DC(i)
O tempo de término mais cedo (TTC) de uma atividade é a soma da data mais
cedo do evento inicial da referida atividade mais a duração da atividade.
TTC(i,j) = DC(i) + D (i,j)
O tempo de término mais tarde (TTT) de uma atividade é o valor
correspondente a data mais tarde do evento final da referida atividade.
TTT(i,j) = DT(j)
O tempo de início mais tarde (TIT) de uma atividade é a data mais tarde do
evento final da referida atividade menos a duração da atividade.
TIT (i,j) = DT(j) – D(i,j)
D.R.R.
61
PESQUISA OPERACIONAL
6.4.4 As Folgas
A folga do evento (FE) é o intervalo de tempo existente entre a data mais cedo
e a data mais tarde.
FE(i) = DT(i) – DC(i)
A folga de uma atividade (FA) é o intervalo de tempo existente entre o tempo de
término mais tarde e o tempo de início mais cedo de uma atividade.
FA(i,j) = TTT(i,j) – TIC (i,j)
A folga total de uma atividade (FT) é o tempo máximo que o início de uma
atividade pode ser retardado sem que altere o tempo total de execução do projeto.
FT(i,j) = TTT(i,j) – TIC (i,j) – D(i,j)
A folga livre de uma atividade (FL) é o tempo que o início de uma atividade
pode ser retardada sem interferir no início de qualquer atividade sucessora.
FL(i,j) = DC(j) – DC(i) – D(i,j)
Exemplo:
Para a rede abaixo calcular:
a) Os tempos operacionais e datas das atividades;
b) As folgas da rede.
A=10
1
B=15
C=5
D.R.R.
2
3
4
F=5
D=2
H=15
50
E=1
5
6
G=
62
PESQUISA OPERACIONAL
SIMB.
A
B
C
D
E
F
G
H
TIC
0
0
0
10
10
15
5
30
TIT
0
10
15
10
30
25
20
30
TTC
10
15
5
30
25
20
15
45
TTT
10
25
20
30
45
30
30
45
FL
0
0
0
0
20
10
15
0
FA
10
25
20
20
35
15
25
15
FT
0
10
15
0
20
10
15
0
1
2
3
4
5
6
FE
0
0
10
15
0
0
6.5 ESTIMATIVA DOS TEMPOS DE EXECUÇÃO DAS AT IVIDADES
Construído o Diagrama de Rede para um projeto, precisamos obter a duração de
cada atividade, para determinar o caminho crítico, calcular a duração do projeto e a
folga de cada atividade em particular. Saberemos assim quais atividades devem ser
objeto de atenção especial para que não atrasem (aquelas que pertencem ao caminho
crítico).
No caso do CPM, como a utilização típica é em projetos onde se pode ter
estimativas bem acuradas de tempo, cada atividade tem uma só medida
(determinística) de tempo.
Quanto ao PERT, empregado em projetos cujas atividades têm uma certa
imprecisão na duração, convencionalmente são feitas três estimativas de tempo para
cada atividade:
§
Estimativa OTIMISTA (a): é uma estimativa do tempo mínimo que uma
atividade pode tomar. É obtida supondo-se condições totalmente favoráveis
na execução da atividade.
§
Estimativa MAIS PROVÁVEL (m): é uma estimativa do tempo normal que
uma atividade deve tomar. É o resultado que ocorreria mais freqüentemente
se a atividade fosse feita um grande número de vezes.
§
Estimativa PESSIMISTA (b): é uma estimativa do tempo máximo que uma
atividade pode durar. Só ocorre em condições totalmente adversas. A
possibilidade de eventos drásticos e catastróficos não é considerada, a
menos que eles sejam um risco claramente associado ao projeto.
Uma hipótese que se faz é a de que os tempos de atividade são distribuídos
segundo uma distribuição beta, onde a estimativa MAIS PROVÁVEL m é a moda. A
D.R.R.
63
PESQUISA OPERACIONAL
distribuição pode ser inclinada para a direita, para a esquerda ou centrada,
dependendo da relação entra a, m, e b.
Assumida a distribuição beta, calcula-se o tempo esperado, E(x) = te de cada
atividade, dado pela fórmula:
t
e
=
a + 4m + b
6
Onde a variância é dada por:
 b −a 
V(x) = 

 6 
2
A variância total de um projeto é identificada pelo símbolo σ T2 e é a soma das
variâncias do caminho crítico.
A variância de um evento é identificada pelo símbolo
σ E2 e é a variância das
atividades que produziram a data + cedo deste.
A distribuição dos valores “a”, “m” e “b” segue uma distribuição beta, que para
efeitos de cálculo será considerada aproximadamente normal. Sendo:
X-µ
Z = 
σT
Onde:
µ = T = Tempo total de execução
X = TE = Tempo considerado de execução
σT2 = Desvio padrão normal de execução
σT = ∑ V(X)caminh o crítico
Tabela de valores de uma função de distribuição normal
Z
0,0
0,1
0,2
0,3
0,4
0,5
0,6
D.R.R.
P(Z)
0,5000
0,5398
0,5793
0,6179
0,6554
0,6915
0,7257
P(-Z)
0,5000
0,4602
0,4207
0,3821
0,3446
0,3085
0,2743
64
PESQUISA OPERACIONAL
Continuação da tabela de valores:
Z
0,7
0,8
0,9
1,0
1,1
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2,0
2,1
2,2
2,3
2,4
2,5
2,6
2,7
2,8
2,9
3,0
3,0
P(Z)
0,7580
0,7881
0,8159
0,8413
0,8643
0,8849
0,9032
0,9192
0,9332
0,9452
0,9554
0,9641
0,9713
0,9772
0,9821
0,9861
0,9893
0,9918
0,9938
0,9953
0,9965
0,9974
0,9981
0,9987
1,0000
P(-Z)
0,2420
0,2119
0,1841
0,1587
0,1357
0,1151
0,0968
0,0808
0,0668
0,0548
0,0446
0,0359
0,0287
0,0228
0,0179
0,0139
0,0107
0,0082
0,0062
0,0047
0,0035
0,0026
0,0019
0,0013
0,0000
6.6 EXERCÍCIOS
1. Para o programa de atividades abaixo relacionadas determinar:
a) O diagrama de rede;
b) As datas e folgas dos eventos;
c) Os tempos operacionais e folgas das atividades;
d) O caminho crítico.
D.R.R.
SIMB.
A
B
C
D
E
F
G
H
ATIVIDADE
Raspagem do exterior
ATIV. PREC.
-
ATIV. SUC.
D
TEMPO(dias)
4
Remoção papel de parede
Remoção dos armários
Pintura externa
Colocação piso cozinha
Pintura paredes internas
Pintura decorativa interior
Reacabam. piso madeira
A
C
B
F,E
G
F
E
G
G
H
-
5
2
6
3
3
4
5
65
PESQUISA OPERACIONAL
2. Para o programa de atividades dados a seguir, determinar o diagrama de rede, as
datas dos eventos e o caminho crítico:
ATIVIDADE
Escolher a cidade
Escolher o auditório
Escolher patrocinadores
Programar conferências
Recolher conferencistas
Remeter convites
Preparar local e divulgar
Preparar material
Selecionar participantes
Transporte conferencistas
Rec. partic. e conferencistas
SIMB.
A
B
C
D
E
F
G
H
I
J
K
PREC.
A
A
D
B, C
B, C
E, G
F
E
H, I, J
SUC.
C, B
G, F
G, F
E
J, H
I
H
K
K
K
-
TA
1,0
3,5
2,0
4,0
6,0
10,0
10,0
2,0
2,0
5,0
1,5
TM
2,0
4,5
2,5
6,5
8,0
16,0
15,0
4,0
3,0
11,0
3,0
TB
3,0
8,5
6,0
12,0
16,0
28,0
20,0
6,0
4,0
17,0
4,5
3. Para o quadro das atividades abaixo da rede PERT/CPM, determinar:
a) O tempo de execução do projeto;
b) O caminho crítico;
c) Qual deveria ser o tempo de término do projeto para termos 95% de certeza de sua
execução?
ATIVIDADE
A
B
C
D
E
F
G
H
I
J
K
ATIV. PREC.
D
C
A
B, F
E
H, I
E
ATIV. SUC.
G
H
F
E
I, K
H
J
J
-
te
5
6
7
5
2
4
18
6
2
6
8
σT
0,30
0,44
0,55
0,71
1,00
0,70
0,95
1,10
0,95
0,75
1,00
4. Dado o programa abaixo, determinar o caminho crítico.
ATIVIDADE
A
B
C
D
D.R.R.
ATIV. PREC.
A
ATIV. SUC.
D
E
F
G, H
DURAÇÃO
10
12
15
13
66
PESQUISA OPERACIONAL
Continuação da tabela:
ATIVIDADE
E
F
G
H
I
J
K
L
M
N
O
P
ATIV. PREC.
B
C
D
D
E
F
F
G, H, I
I
J, K
L, M, N
O
ATIV. SUC.
I
J, K
L
L
L, M
N
N
O
O
O
P
-
DURAÇÃO
9
8
15
12
10
13
17
18
22
20
21
12
5. Para o programa abaixo, determinar:
a) O diagrama de rede e o caminho crítico;
b) A probabilidade de concluir o projeto em 25 dias;
c) Qual o tempo que devemos prever para o projeto para termos a certeza de sua
conclusão com uma probabilidade de 96%?
d) Qual a probabilidade de concluir o projeto entre 25 e 30 dias?
ATIVIDADE
A
B
C
D
E
F
G
H
I
J
K
D.R.R.
ATIV. PREC.
A
D
A
B, C, D
D
E, I
G, H
ATIV. SUC.
B, F
G
G
G, H, E
J
K
K
J
-
te
2
4
3
6
6
6
6
7
5
6
6
σT
0,11
0,44
0,44
1,78
1,78
2,78
2,78
1,78
0,44
1,78
0,69
67
PESQUISA OPERACIONAL
7 BIBLIOGRAFIA
ACKOFF, Russel L.; SASIENI, Maurice W.. Pesquisa Operacional. S.P: Livros
Técnicos e Científicos Ltda, 1971.
ANDRADE, Eduardo Leopoldino de. Introdução à Pesquisa Operacional: métodos
e modelos para análise de decisão. 2. ed. R.J. LTC Ltda, 2000.
HILLIER, Frederick S.. Introdução à Pesquisa Operacional. R.J.: Editora Campus /
Editora da Universidade de São Paulo, 1988.
LACHTERMACHER, Gerson. Pesquisa Operacional na tomada de decisões. R.J.:
Editora Campus, 2002.
LOESCH, Cláudio; HEIN, Nelson. Pesquisa Operacional: Fundamentos e Modelos.
Blumenau: Editora da FURB, 1999.
MIRSHAWKA, Victor. Pesquisa Operacional. S.P.: Editora Nobel, 1980.
PIDD, Michael. Modelagem Empresarial: ferramentas para tomada de decisão.
Tradução de Gustavo Severo de Borba et al. P.A.: Artes Médicas, 1998.
SHIMIZU, Tamio. Pesquisa Operacional em Engenharia, Economia e
Administração: modelos básicos e métodos computacionais. R.J.: Editora
Guanabara Dois, 1984.
D.R.R.