Métodos Quantitativos na Logística

Prévia do material em texto

Métodos Quantitativos Aplicados à Logística
INTRODUÇÃO À PESQUISA OPERACIONAL
Surgiu com este nome durante a 2a Grande Guerra, quando equipes de pesquisadores procuravam desenvolver métodos para resolver determinados problemas de operações militares. Seu sucesso fez com que usassem as técnicas criadas em problemas de administração.
Caracteriza-se pelo uso de técnicas e métodos científicos qualitativos por equipes interdisciplinares, para determinar a melhor utilização de recursos limitados e para programação otimizada das operações de uma empresa. Utiliza-se também modelos, o que permite a experimentação e podendo a decisão ser mais bem avaliada e testada antes de ser implementada.
O grande progresso da Pesquisa Operacional se deve ao desenvolvimento dos computadores digitais, devido sua velocidade e processamento e capacidade de armazenamento e recuperação das informações.
Pesquisa Operacional (P.O ) é o ramo da ciência administrativa que fornece instrumentos para análise de decisões. O objetivo que temos é entender as características principais do processo e suas dificuldades, de forma que se compreenda como a P.O pode auxiliar a gerência na preparação e tomada de decisões.
Decisão é o resultado de um processo que se desenvolve à partir do instante em que o problema foi detectado, o que ocorre geralmente através da percepção de sintomas. À partir dessa percepção, inicia-se a fase de identificação do problema, que é o verdadeiro processo decisório. As características principais do processo decisório são :
· Processo Seqüencial
Uma decisão significativa abrange muitas decisões e requer um longo período de tempo. Fica muito difícil apontar com precisão o ponto exato do processo em que a decisão foi tomada.
· Processo Complexo
É complexo por diversos fatores, além de se tratar do inter-relacionamento entre pessoas, responsabilidades pelo serviço, comunicação e sistemas de informações, códigos e ética e moral e também interesses e objetivos diferentes dos participantes.
Dentro da empresa 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 de decisão dentro da empresa.
· Processo com Valores Subjetivos
Existem valores intuitivos adquiridos da experiência pessoal e da personalidade, e que são importantes na qualidade da decisão tomada.
· Processo em Ambiente Institucional
Todas as companhias têm sua estrutura organizacional própria que influencia e condiciona o processo decisório.
A qualidade de uma decisão é tão mais elevada quanto maior for o grau de satisfação dos interesses envolvidos, adaptação dos meios necessários aos objetivos procurados e consistência do uso de ação.
A P.O tem sido vista por gerentes e praticantes sob dois enfoques diferentes quanto à abordagem:
a ). Enfoque Clássico ou Tradicional – A P.O é definida como arte de aplicar técnicas de modelagem a problemas de decisão e resolver os modelos obtidos através de métodos matemáticos e estatísticos, visando obter uma solução ótima. Entretanto traz pouca flexibilidade devido o rigor matemático.
b ). Enfoque Atual – Perde importância o rigor matemático da solução, e ganham relevância o espírito crítico, 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 afetar os resultados.
TÉCNICAS DE PESQUISA OPERACIONAL
A Pesquisa Operacional deve se desenvolver segundo as fases indicadas abaixo: 
 Percepção ou demanda por solução
Essa seqüência de passos não é rígida, mas indica as principais etapas que devem ser vencidas. Com exceção da solução do modelo, as demais fases não seguem regras fixas e definidas, dependem somente do tipo do problema em análise e do ambiente que o envolve.
A ) Definição do Problema
 São três os aspectos principais: descrição exata dos objetivos do estudo; identificação das alternativas de decisão existentes e ; reconhecimento das limitações, restrições e exigências do sistema.
B ) Construção do Modelo
Esta é a fase onde o modelo mais apropriado para representação do sistema é escolhido com base na definição do problema.
Se o modelo elaborado tem a forma de um modelo padrão, como por exemplo Programação Linear, a solução é obtida por métodos matemáticos convencionais. Agora, se as relações matemáticas são complexas ou indefinidas, usamos a técnica da simulação ou até a combinação dos dois métodos.
C ) Solução do Modelo
Encontra uma solução para o modelo construído. No caso de modelos matemáticos, a solução é dita “ótima”.
Nos modelos de simulação, o conceito de “otimalidade” não é bem definido, a solução obtida é uma avaliação aproximada das medidas do sistema ou do objetivo a ser atingido.
D ) Validação do Modelo
Um modelo é valido se for capaz de fornecer uma previsão aceitável do comportamento do sistema e uma resposta que possa contribuir para a qualidade da decisão a ser tomada.
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 é uma das etapas mais críticas do estudo. A presença de equipe procura superar as resistências e oposições às alterações propostas.
F ) Avaliação Final
É de fundamental importância, pois garantirá melhor adequação das decisões às necessidades do sistema e aceitação mais fácil dessas decisões por todos os setores envolvidos. Nesta avaliação, um fator importante é a experiência do pessoal envolvido. 
· TIPOS DE MODELOS
Podemos identificar diversos tipos de modelos, dependendo da forma como o processo de decisão é abordado pelo analista e da própria natureza da decisão, tais como: modelos conceituais; simbólicos ou matemáticos; heurísticos.
Modelos Conceituais – Relacionam de forma seqüencial e lógica as informações e as fases do processo de decisão, de forma a permitir o desenvolvimento controlado e consistente com os objetivos em mente.
Modelos Matemáticos – Pressupõem que todas as informações e variáveis relevantes do problema de decisão podem ser quantificadas, nos levando a utilizar símbolos matemáticos para representá-las e a usar funções matemáticas para descrever as ligações entre elas e a operação do sistema.
Modelos Heurísticos – São construídos quando a complexidade do problema é tal que a utilização de relações matemáticas torna-se impraticável ou dispendiosa. Esses modelos são baseados em regras empíricas ou intuitivas que, dada a solução para o problema, permitem o avanço para outra solução mais aprimorada. São modelos construídos com base nas técnicas de “inteligência artificial”.
· Modelos Matemáticos
A metodologia da Pesquisa Operacional é mais desenvolvida para soluções de problemas que podem ser representados por modelos matemáticos. O modelo mais apropriado para um dado contexto ou problema depende de vários fatores como a natureza matemática das relações entre as variáveis; objetivos do encarregado da decisão; extensão do controle sobre as variáveis de decisão; e nível de incerteza associado ao ambiente da decisão.
Com base nestas considerações, podemos dividir os modelos matemáticos em dois grandes tipos: modelos de simulação e modelos de otimização.
Modelos de simulação - Procuram oferecer uma representação do mundo real com o objetivo de permitir a geração e análise de alternativas, antes da implementação de qualquer uma delas. Por este motivo dão um considerável grau de liberdade e flexibilidade com relação à escolha mais conveniente. 
Modelos de otimização – Não permite flexibilidade na escolha da alternativa, já que é estruturado para selecionar uma única , que será considerada “ótima”, segundo o critério estabelecido pelo analista. Esses modelos são mais especializados e encontram utilização em problemas onde as variáveis podem assumir muitos valores ou variar em intervalos muito amplos. 
TEORIA DA LOCALIZAÇÃO
 A definiçãoda localização de instalações em uma rede logística, sejam elas fábricas, depósitos ou terminais de transporte, é um problema comum e dos mais importantes para os profissionais de logística. Sua importância decorre dos altos investimentos envolvidos e dos profundos impactos que as decisões de localização têm sobre os custos logísticos. Caracterizados por um alto nível de complexidade e pelo intensivo uso de dados, os estudos de localização atualmente dispõe de novas tecnologias de informação que permitem tratar os sistemas logísticos de forma efetivamente integrada.
 1. Estrutura dos problemas de localização
 De forma geral, os estudos de localização tratam do problema de minimizar os custos de uma rede logística, estando esta sujeita às restrições de capacidade das instalações, tendo que atender a uma determinada demanda e devendo satisfazer certos limites de nível de serviço. Os dados de entrada para análise são as previsões de demanda para cada produto, as limitações de capacidade e as taxas de produção, as prováveis localizações da instalações, as possíveis ligações entre elas e os respectivos custos de transporte de cada modal.............................................................
 O que geralmente queremos determinar nesta situação é onde as fábricas devem ser localizadas; quais fornecedores deverão ser utilizados; quantos centros de distribuição a empresa deve operar; onde eles devem estar localizados; que clientes ou zonas de mercado devem ser supridos de cada centro de distribuição; que linhas de produto devem ser produzidas ou estocadas em cada fábrica ou centro de distribuição; que modalidades de transporte devem ser usados para suprimento e para distribuição.
 Estas questões possuem forte interdependência entre si e não devem, portanto, ser analisadas de forma seqüencial ou segmentada. Na sua análise é preciso considerar os trade-off's existentes entre as decisões relacionadas ao transporte, ao posicionamento do estoque na rede e ao número e localização das instalações. O que se pretende é obter um solução ótima, que atenda ao nível de serviço desejado ao menor custo total da operação.
 Decisões de localização
Nível de Serviço 
 Custo Total Decisões de Decisões de 
 Transporte Estoque 
2. Complexidade e dimensão dos problemas
 
 Os problemas de localização, tipicamente, possuem uma complexidade bastante alta e envolvem um volume de dados muito grande. A complexidade é devida ao fato de a análise ter que lidar com um conjunto extenso de variáveis de decisão que se influenciam mutuamente. Além disto, o número de possíveis alternativas a serem analisadas e comparadas é muito alto, mesmo para problemas de pequeno porte. São onde começam as dificuldades na realização destes estudos: na maioria da empresas os dados existem mas não estão estruturados, pois normalmente não existem sistemas de informação voltados para a sua geração. Como conseqüência, cerca de 2/3 do tempo de estudos de localização de instalações são gastos na aquisição e preparação dos dados.
 Embora as dificuldades pareçam grandes, atualmente estão disponíveis um grande número de ferramentas computacionais que tornam mais fácil as tarefas de modelagem e otimização do problema e de tratamento da grande massa de dados tipicamente presente nos estudos de localização. É o que abordaremos a seguir.
3. Ferramentas para análise
 Desde a década de 70 já estavam desenvolvidas as bases para as aplicações computacionais de estudos de localização de instalações. Mas os problemas de dimensões práticas, de larga escala, estavam basicamente restritos à comunidade acadêmica ou aos órgãos governamentais, através da utilização de computadores mainframes. Foi muito recentemente, depois da ampla utilização de computadores pessoais dotados de processadores de alta velocidade, que se expandiu o uso comercial de ferramentas computacionais aplicadas ao problema de localização.
 No Brasil a oferta ainda é limitada, mas já se fazem presentes os representantes de algumas das principais empresas fornecedoras de softwares nesta área. No entanto, como as barreiras geográficas não são, neste caso, limitadores tão sérios, pode-se ter acesso aos mesmos produtos disponíveis no mercado internacional.
 Os softwares em sua maioria possuem modelos pré-determinados de redes logísticas. São modelos genéricos que representam grande parte dos sistema reais. A diferença entre eles está na capacidade de representar os custos e restrições operacionais envolvidos. Praticamente todos consideram os custos de transporte (suprimento, distribuição e transferência), os custos de armazenagem, e os custos de compra ou produção. O mesmo não acontece com os custos de estoque que estão mais relacionados à dimensão temporal, ainda não bem tratada pelos softwares de localização, mais voltados para a dimensão espacial ou geográfica.
As restrições básicas são as restrições de capacidade, que limitam os fluxos de produtos através das instalações, as restrições de demanda e, menos básicas em função de maior 
dificuldade de modelagem, as restrições de nível de serviço. Estas últimas são geralmente de dois tipos:
· as que limitam o tempo máximo de atendimento através da limitação da distância máxima entre uma zona de demanda e a instalação mais próxima
· as que limitam o número máximo de instalações que podem atender a uma determinada zona de demanda, garantido assim exclusividade de suprimento. 
4. Organização dos estudos de localização 
 As possíveis aplicações para os estudos de localização são muito amplas. Se as olharmos em função do nível das decisões, em termos de serem mais estratégicas ou mais operacionais, temos alguns exemplos:
· Nível Estratégico - determinação do número, tamanho e localização de fábricas e depósitos. 
· Nível Tático - definição da alocação dos clientes aos centros de distribuição e dos centros de distribuição às fábricas.
· Nível Operacional - elaboração de planos de contingência, onde se pretende realocar de forma ótima os clientes em caso, por exemplo, da parada de uma linha de produção em uma fábricas. 
 Por outro lado, os estudos de localização podem ser usadas com objetivos mais exploratórios, quando se deseja avaliar o impacto de mudanças no ambiente de negócios da empresa sobre a sua estrutura de suprimento e distribuição. É o que chamamos de análise de cenários. 
 As análises paramétricas são também aplicações interessantes, onde se estuda o impacto da variação sistemática de um único fator sobre as variáveis de interesse: por exemplo, pode-se estar interessado no efeito da variação do número de centros de distribuição sobre o custo total. Ou no efeito do aumento da capacidade de produção sobre o custo de transporte. O objetivo das análises paramétricas é o de quantificar relações relevantes para tomada de decisão, através da construção de curvas paramétricas, obtidas através de várias corridas com o modelo.
PROBLEMA DO TRANSPORTE
1. Introdução:
 Dados a estrutura de fontes de produção ou origens de um produto, a rede de caminhos possíveis de transporte e os destinos para os quais os produtos devem se dirigir, o objetivo da modelagem e estudo do problema é determinar o carregamento da rede de transporte que minimiza o custo total do transporte.
 No planejamento de uma rede logística de distribuição a função transporte agrega o valor “lugar” ao produto, o sistema de transporte tem um papel fundamental e indispensável e, desta forma, deve ser cuidadosamente planejado com o objetivo de atingir o que se espera dele, com o menor acréscimo possível no custo final do produto.
 Vamos considerar a situação descrita a seguir: temos que transportar produtos das várias origens onde estão estocados para vários destinos ondesão necessários. Conhecemos os custos unitários de transporte de cada origem para cada destino (Cij - custo unitário de transporte da origem i para o destino j). Devemos decidir quanto transportar de cada origem para cada destino (Xij - quantidade a ser transportada da origem i para o destino j).
 O objetivo é completar a transferência dos produtos com o menor custo possível. Em princípio, vamos supor que a quantidade disponível nas origens seja exatamente igual ao total das necessidades nos destinos.
· Modelo linear do transporte
 Variáveis de decisão: xij - Quantidade a ser transportada da origem i para o destino j.
 Objetivo: minimizar o custo do transporte.
 min. C = 10x11 + 12x12 + 20x21, + 8x22 + 6x31 + 15x32
onde:
 10x11 = custo unitário de transporte da origem 1 para o destino 1
 x
 quantidade a ser transportada da origem 1 para o destino 1
 =
 custo do transporte da origem 1 para o destino 1 
 Restrições: 
As quantidades retiradas das origens devem ser a disponibilidade em cada uma:
 Origem1 - retiradas x11 + x12 = 50 Disponibilidade O1
 Origem2 - retiradas x21 + x22 = 100 Disponibilidade O2
 Origem3 - retiradas x31 + x32 = 120 Disponibilidade O3
 As quantidades transportadas para cada destino devem ser a necessidade. em cada um deles:
 Destino1 - Chegadas x11 + x21 + x31 = 100 necessidade D1
 Destino2 - Chegadas xI2 + x22 + x32 = 170 necessidade D2
 O modelo fica então resumido a:
 min. C = 10x11 + 12x12 + 20x21 + 8x22 + 6x31 + 15x32 
Sujeito a:
 x11 +xI2 = 50
 x21 + x22 = 100
 x31 + x32 = 120
 x11 + x21 + x31 = 100
 x12 + x22 + x32 = 170
 xij >= O para i =1,2,3 e j = 1,2.
· Caso de sistemas não equilibrados:
 O modelo descrito anteriormente pode representar também sistemas de transporte que não obedeçam à condição de equilíbrio entre oferta (disponibilidade nas origens) e demanda (necessidade de destinos).
 O enquadramento no modelo se faz com a criação de origens ou destinos auxiliares para receber a diferença entre oferta e demanda. Os custos unitários para origens ou destinos auxiliares é zero. Na solução do modelo, as quantidades que eventualmente sejam transportadas de origens auxiliares ficam faltando nos destinos. As quantidades que são transportadas para destinos auxiliares, na verdade ficam depositadas nas origens.
 Exemplo: O modelo representado no quadro está desequilibrado
 D1 D2 D3
 O1 10 12 9 20
 O2 4 9 8 30
 O3 6 12 10 10
 25 36 5 
 Criando-se uma origem auxiliar para receber a diferença 66 - 60 = 6, teremos o sistema equilibrado:
 D1 D2 D3
 O1 10 12 9 20
 O2 4 9 8 30
 O3 6 12 10 10
 A 0 0 0 6
 25 36 5
 Uma solução possível para o problema é mostrada no quadro, onde o
 valor das células representa as quantidades transportadas de cada origem
 para cada destino.
 D1 D2 D3
 O1 20 20
 O2 5 25 30
 O3 10 10
 A 1 5 6
 25 36 5
 As quantidades xA2 = 1 e xA3 = 5 transportadas a partir da origem auxiliar A, na verdade, ficam faltando nos destinos, isto é, o destino D2, recebe apenas 35 unidades. O destino D3 não recebe nenhuma mercadoria.
2. Algoritmo dos Transportes
 A solução do problema do transporte, como todo problema representado por um modelo de programação linear, pode ser obtida pelo método Simplex. Entretanto, devido a suas características especiais, podemos descrever um método que, embora mantenha fazes e critérios do Simplex, tem os cálculos simplificados.
 1a Parte - CÁLCULO DA SOLUÇÃO BÁSICA INICIAL
 Uma solução básica para o problema é um conjunto de valores a transportar que obedecem a duas condições:
· Satisfazem as restrições de origem e destino;
· Não apresentam circuitos entre as variáveis básicas.
a) Método do canto noroeste
 A partir da cela superior esquerda transportamos o máximo possível da origem ao destino correspondente. Esse procedimento zera a disponibilidade da linha ou da 
coluna da cela. O próximo transporte será feito na cela contígua (à direita ou abaixo) que tenha disponibilidade de linha e coluna correspondente.
 Exemplo: Calcular a solução inicial do quadro de transportes:
 D1 D2 D3
 O1 12 9 8 10
 O2 13 12 6 20
 O3 7 9 5 10
 A 3 2 8 15
 8 30 17 55
Solução:
 8 2 10
 20 20
 8 2 10 
 15 15
 8 30 17 55 
 
 1o transporte: x11 = 8 (primeira linha mantém disponibilidade de 2)
 2o transporte: x12 = 2 (segunda coluna mantém disponibilidade de 28)
 3o transporte: x22 = 20 (segunda coluna mantém disponibilidade de 8)
 4o transporte: x23 = 8 (terceira linha mantém disponibilidade de 2)
 5o transporte: x33 = 2 (terceira coluna mantém disponibilidade de 15)
 6o transporte: x43 = 1 5
 O método do canto noroeste garante a não-formação de circuitos entre
 as variáveis básicas, além de satisfazer as condições de contorno (restrições
 de origem e destino).
b) Método de Vogel ou método das penalidades
 Penalidade em uma linha ou coluna é a diferença positiva entre os dois custos de menor valor na linha ou coluna.
 A idéia desse método é fazer o transporte com prioridade na linha ou coluna que apresenta a maior penalidade. Como o transporte é feito na célula de menor custo, tenta-se evitar com isso o transporte na célula de custo maior, evitando-se assim incorrer num aumento de custo igual à penalidade calculada.
 Descrição do método:
 a. Calcular a penalidade para cada linha ou coluna. Escolher a linha ou coluna para transporte, que tenha a maior penalidade. Caso haja empate, escolha arbitrariamente uma delas.
 b. Transportar o máximo possível na linha ou coluna escolhida, elegendo a célula de menor custo unitário de transporte. Esse procedimento zera a oferta ou demanda da célula correspondente. A linha ou coluna que tenha sua disponibilidade zerada deve ser eliminada.
 c. Retornar ao item a, até que todos os transportes tenham sido realizados.
2a Parte - CRITÉRIO DE OTIMALIDADE
 Obtida urna solução inicial para o quadro de transportes, o passo seguinte é verificar se essa solução pode ou não ser melhorada. Como no método Simplex, isso pode ser avaliado observando-se os coeficientes das variáveis não básicas na função objetivo, que deverá estar escrita em termos dessas variáveis.
 Descrição:
 a. Escrever a função objetivo em termos das variáveis não básicas. Para tanto,vamos multiplicar cada restrição de linha pelo número -Ui, e cada restrição de coluna pelo número –Vj, e somar as novas linhas e colunas na função objetivo de tal maneira que os coeficientes das variáveis básicas sejam todos nulos.
 Teremos, então:
 se xij é básico --> Cij - Ui – Vj = 0
 Essas igualdades compõem um sistema de m + n - 1 equações com m + n incógnitas. A solução do sistema pode ser obtida atribuindo-se um valor arbitrário a uma das incógnitas e calculando-se o valor das outras.
 Com esses valores, calculamos os coeficientes das variáveis não básicas:
 xij não básico ---> coeficiente = Cij – Ui – Vj
 Se todos esses valores forem positivos, a solução é ótima. Se houver coeficiente negativo, a variável correspondente entra na base para melhorar o valor do objetivo.
 b. Entrar com a variável cujo coeficiente negativo tenha o maior valor absoluto.
 c. Montar um circuito de compensação entre as variáveis básicas, a partir da variável que entra. Esse circuito é feito partindo-se da variável que entra e seguindo-se alternativamente na direção da linha e da coluna, subtraindo e somando o valor da entrada até o retorno à variável de entrada. Com isso as restrições de linha e coluna ficam satisfeitas.
 d. Escolher para a variável que entra o maior valor possível, sem tornar nenhuma variável básica negativa. Esse valor corresponde ao menor valor das células onde a variável que entra estiver sendo subtraída. Teremos, então, uma nova solução básica.
 e. Voltar ao item a, até que a solução seja ótima, isto é, não apresente coeficiente negativo nas variáveis não básicas.
3. Problema da Degenerescência
 Vimos que igualando os coeficientes das variáveis básicas a zero, o resultado é um sistema que apresenta uma variável a mais que o número de equações. Atribuímos um valor arbitrário para a variável livre e obtivemos um conjunto único de valores para as incógnitas.
 Pode ocorrer, entretanto, que haja menos variáveis básicas do que o necessário na solução, o que resulta menos equações do que as desejadas (duas, três ou mais equações a menos que o número de variáveis).
 Dizemos nesse caso que a solução é degenerada. Ao calcular os valores de U e V do sistema para o critério de otimalidade, não conseguimos um conjunto único de valores para U e V.
 A solução para o caso é criar variáveis básicas auxiliares, quantas forem necessárias para que o número de equações seja apenas um a menos que o número de variáveis. Essas variáveis básicas auxiliares devem ter um valor tão próximo de zero que não alteram as condições de contorno do problema (restrições de origem e destino).
 O cuidado que devemos tomar ao acrescentar variáveis básicas auxiliares é que elas não formem circuitos com as variáveis básicas originais.
4. Caso de Maximização
 Alguns modelos de programação linear, embora tenham objetivo de maximização, podem ser tratados como modelos de transportes. Como o modelo de transportes minimiza o objetivo, a solução consiste em transformar o objetivo em minimização. Isto pode ser feito de duas maneiras:
 a. Multiplicar a função objetivo por -1, o que equivale a trocar o sinal dos custos unitários de transporte.
 b. Trabalhar com um novo quadro, onde os custos unitários de transporte são os complementos dos preços originais para algum valor fixo, geralmente o maior valor da tabela original.
5. Caso da Impossibilidade de Transporte
 Pode ocorrer que determinado transporte de uma origem para um destino não possa ser realizado. Neste caso, colocamos como custo de transporte, naquela célula da tabela de custos, um símbolo M, que representa um número muito grande. Desta forma:
 Ao construir a solução básica inicial, evitamos esta célula, onde não é possível o transporte.
 Como o número M é muito grande, ao calcular os coeficientes das variáveis não básicas, o coeficiente desta célula nunca será negativo, o que impede o aparecimento, na célula, de uma variável básica trazendo como conseqüência a ausência daquele transporte.
O MÉTODO SIMPLEX
1. Apresentação:
 Esse método é formado por um grupo de critérios para escolha de soluções básicas que melhorem o desempenho do modelo, e também de um teste de otimalidade. Para isso, o problema deve apresentar uma solução básica inicial. As soluções básicas subseqüentes são calculadas com a troca de variáveis básicas por não básicas, gerando novas soluções.
 Os critérios para escolha de vetores e conseqüentemente das variáveis que entram e saem para a formação da nova base constituem o centro do simplex.
 Suponhamos inicialmente que o modelo apresente uma solução básica inicial. Os modelos com restrições do tipo < e com termos da direita não negativos têm uma solução básica formada pelas variáveis de folga.
Exemplo.
 No modelo:
 maximizar z = 3x1 + 5x2
 sujeito a:
 2x1 + 4x2 < =10
 6x1 + x2 < = 20
 x1 - x2 < =30
 x1 > 0, x2 >=0
 Acrescentando as variáveis de folga nas restrições:
2x1 + 4x2 +, xF1 = 10
 6x1 + X2 + xF2 = 20
 x1 - x2 + xF3 = 30
 x1 >= 0, x2 > = 0, xF1 > = 0, xF2 > = 0, xF3> = 0 
 
Podemos visualizar uma solução formada pelas variáveis de folga. 
 
Basta fazer x1 = O e x2 = O e teremos: xF1 = 10, xF2 = 20, xF3 = 30. 
Ou escrevendo na forma de vetores:
 1 0 0 10 
 0 xF1 + 1 xF2 + 0 xF3 = 20
 0 0 1 30
Os vetores do primeiro membro constituem uma base do R3, e a solução neste caso é uma solução básica inicial: x1 = 0, x2 = 0, xF1 = 10, xF2 = 20 e xF3 = 30, formada portanto pelas variáveis de folga.
2. Descrição do Método para Maximização
 1a Parte: Teste de otimalidade para a solução.
 Consiste em avaliar o efeito da permuta de uma variável básica por outra não básica, com a conseqüente formação de nova solução. Se a entrada de urna variável não básica puder melhorar o desempenho do sistema, a solução testada não é ótima.
 Essa avaliação é possível quando a função objetivo está escrita somente em termos das variáveis não básicas.
 Voltando ao exemplo anterior, a função objetivo está escrita na forma:
 max z = 3x1 + 5x2 
e obtivemos, fazendo x1 = 0, x2 = 0, uma solução básica inicial formada pelas variáveis de folga xF1 = 10, xF2 = 20 e xF3 = 30.
 No caso, as variáveis básicas são xF1, xF2 e xF3, e as não básicas x1 e x2.
 Portanto, a função objetivo está escrita com as variáveis não básicas.
 Examinando a função objetivo e a solução inicial x1 = 0, x2 = O e z = 0, com z = 3x1, + 5x2, temos:
 Se x1 entra na base com valor 1, o valor de z passa de z = O para z = 3, aumentando 3 unidades, exatamente o valor do coeficiente de x1.
 Se x2 entra na base com valor 1, o valor de z passa de z = O para z = 5, aumentando 5 unidades, exatamente o valor do coeficiente de x2.
 Por outro lado, se o coeficiente de x1 ou x2 fosse negativo, a entrada dessa variável diminuiria o valor de z, de acordo com seu coeficiente. Podemos concluir que enquanto a função objetivo apresentar variáveis não básicas com coeficientes positivos, ela poderá ser aumentada, não sendo portanto a solução ótima.
 Vamos reescrever, agora, a função objetivo com todas as variáveis à esquerda:
 z = 3x1 + 5x2 => z - 3x1 - 5x2 = 0
 Os coeficientes positivos à direita são negativos à esquerda, portanto, coeficientes negativos à esquerda indicam que o valor de z pode ser aumentado com a entrada da variável na base, e na proporção de seu coeficiente. Escrito dessa forma, a solução testada só será ótima quando as variáveis não básicasnão apresentarem coeficientes negativos.
 2a Parte: Cálculo da nova solução básica
a) Variável que entra na base: entra na base a variável com coeficiente negativo de maior valor absoluto. A idéia é melhorar rapidamente o valor de z.
Examinando a função objetivo do exemplo anterior:
 z - 3x1 - 5x2 = O ou z = 3x1 + 5x2
 entra a variável x2, pois cada unidade a mais em x2 aumenta z em 5 unidades.
 b) Variável que sai: sai a variável que primeiro se anula com a entrada da variável escolhida no item anterior, no caso x2, que entra com maior valor possível.
 Ela pode ser descoberta dividindo-se os termos da direita das restrições pelos coeficientes positivos da variável que entra. O menor valor indica que a variável básica dessa linha é a que primeiro se anula e sairá da base.
 No exemplo:
 2x1 + 4x2 + xF1 = 10 10 4 = 2,5 ( Sai
 6x1 + x2 + xF2 = 20 20 1 = 20
 x1 + x2 + xF3 = 30 30 (-1) = -30
 (
 entra 
 A última divisão (30 (-1)) não pode ser considerada, pois daria valor negativo para a variável na próxima base, o que não é possível. Portanto, sai a variável da primeira linha, no caso xF1.
c) Elemento pivô
 A coluna da variável que entra e a linha da variável que sai identificam um elemento comum chamado pivô.
 A linha da variável que sai é também linha pivô. No caso, a primeira linha é a pivô e o coeficiente 4 de x2 é o elemento pivô.
d) Calculando a nova solução:
d1. Vamos organizar a função objetivo e restrições numa tabela com colunas formadas pelos coeficientes de cada variável e outra dos termos independentes.
 z x1 x2 XF1 xF2 xF3 b
 1 -3 -5 0 0 0 0
 0 2 4 1 0 0 10 ( Sai (linha pivô)
 0 6 1 0 1 0 20
 0 1 -1 0 0 1 30
 (
 entra
d2. Dividimos a linha pivô pelo valor do elemento pivô, obtendo uma nova linha com pivô unitário.
 linha pivô: 0 2 (4) 1 0 10 10
 dividindo por 4: 0 0,5 (1) 0,25 0 0 2,5 -> nova linha pivô
d3. Vamos reescrever cada uma das outras linhas da seguinte maneira:
 10- Multiplicar os elementos da nova linha pivô pelo coeficiente da variável que entra da outra linha, com sinal trocado.
 20- Somar termo a termo com os elementos da outra linha.
Exemplo: Coeficiente da variável que entra (x2) na primeira linha é -5. Então:
 nova linha pivô: 0 0,5 1 0,25 0 0 2,5
 x (5): 0 2.5 5 1.25 0 0 12,5
 + primeira linha: 1 -3 -5 0 0 0 0 _ 
 sorna = nova
 primeira linha: 1 -0,5 0 1,25 0 0 12,5
O coeficiente da variável que entra (x2) na terceira linha é 1. Então:
 nova linha pivô: 0 0,5 1 0,25 0 0 2,5
 x (-1): 0 -0,5 -1 -0,25 0 0 -2,5
 + terceira linha: 0 6 1 0 1 0 20
 sorna = nova
 terceira linha: 0 5,5 0 -0,25 1 0 17,5
O coeficiente da variável que entra na quarta linha é -1. Então:
 nova linha pivô: 0 0,5 1 0,25 0 0 2,5
 x (1): 0 0,5 1 0,25 0 0 2,5
 + quarta linha: 0 1 -1 0 0 1 30
 soma = nova
 quarta linha: 0 1,5 0 0,25 0 1 32,5
Reescrevendo a nova tabela com os resultados obtidos teremos:
 z x1 x2 xF1 xF2 xF3 b
 1 -0,5 0 1,25 0 0 12,5
 0 0,5 1 0,25 0 0 2,5
 0 5,5 0 -0,25 1 0 17,5
 0 1,5 0 0,25 0 1 32,5
De onde concluímos a nova solução:
 Variáveis não básicas Variáveis básicas Valor de z
 x1 = O x2 = 2,5 z = 12,5
 xF1 = O xF2 = 17,5
 xF3 = 32,5
 A função objetivo na nova solução está escrita em termos das variáveis não básicas x1 e xF1. As variáveis básicas têm coeficientes nulos.
 A solução obtida tem z = 12,5, contra z = O da solução inicial. É melhor, mas ainda não é ótima, pois o coeficiente de x1 na função objetivo é negativo.
 Cálculo da nova solução:
Variável que entra: x, (coeficiente negativo de maior valor absoluto na função objetivo)
Variável que sai:
 Vamos dividir os termos independentes pelos coeficientes positivos de xl:
 2,5 ( 0,5 = 5
 17,5 ( 5,5 = 3,18 -> menor valor: sai a variável dessa linha no caso xF2
 32,5 ( 1,5 = 21,67
Nova linha pivô = terceira linha
 Elemento pivô: 5,5
 nova linha pivô = linha pivô ( 5,5
 linha pivô: 0 5,5 0 -0,25 1 0 17,5
 ( 5,5: 0 1 0 -0,045 0,18 0 3,18
O coeficiente da variável que entra (x1) na primeira linha é -0,5. Então:
 nova linha pivô: 0 1 0 -0,045 0,18 0 3,18
 x 0,5: 0 0,5 0 -0,022 0,09 0 1,59
 + primeira linha: 1 -0,5 0 1,25 0 0 12,5
 soma = nova
 primeira linha: 1 0 0 1,227 0,09 0 14,09
O coeficiente da variável que entra (x1) na segunda linha é 0,5. Então:
 nova linha pivô: 0 1 0 -0,045 0,18 0 3,18
 x -0,5: 0 -0,5 0 0,022 -0,09 0 -1,59
 + segunda linha: 0 0,5 1 0,25 0 0 2,5
 soma = nova
 segunda linha: 0 0 1 0,272 -0,09 0 0,91
O coeficiente da variável que entra na quarta linha é 1,5. Então:
 nova linha pivô: 0 1 0 -0,045 0,18 0 3,18
 x -1,5: 0 -1,5 0 0,067 -0,27 0 -4,77
 + quarta linha: 0 1,5 0 0,25 0 1 32,5
 soma = nova
 quarta linha: 0 0 0 0,317 -0,27 1 27,73
Reescrevendo a nova tabela com os resultados obtidos teremos:
 z x1 x2 xF1 xF2 xF3 b
 1 0 0 1,227 0,09 0 14,09
 0 0 1 0,272 -0,09 0 0,91
 0 1 0 -0,045 0,18 0 3,18
 0 0 0 0,317 -0,27 1 27,73
 A nova solução será portanto:
 Variáveis não básicas Variáveis básicas Valor de z
 xF1 = 0 x1 = 3,18 z = 14,09xF2 = 0 x2 = 0,91
 xF3 = 27,73
 A função objetivo está escrita em termos das variáveis não básicas xF1
 e xF2, pois os coeficientes das variáveis básicas são nulos. O valor de z
 passou de z = 12,5 para z = 14,09. Essa solução é ótima, pois os coeficientes
 das variáveis não básicas na função objetivo são positivos. Se xF1, ou xF2
 entrar na base, o valor de z diminui, contrariando o objetivo.
3. Solução de um Modelo Geral de Programação Linear pelo Método Simplex :
 Os modelos de programação linear apresentados até agora têm as seguintes características:
 - a função objetivo deve ser maximizada;
 - todas as varáveis de decisão são não negativas;
 - apresentam uma solução básica inicial.
 A aplicação do Simplex, como foi apresentada, exige essas três carac-
 terísticas no modelo. Caso isso não ocorra, devemos procurar um modelo
 equivalente que possua essas três características, para então usar o Simplex.
· Problema da minimização
 Se a função objetivo for de minimização, devemos multiplicá-la por -1,
 obtendo uma função equivalente para maximização.
Exernplo:
 Minimizar z = 3x1 - 4x2 + x3
 x1 +x2+x3 ( 10
 Sujeito a: 2x1 + x2 – x3 ( 20
 x1( x2 ( X3 ( 0
O modelo equivalente é:
 Maximizar (-z) = -3x1 + 4x2 – x3
 x1 +x2+x3(10
 Sujeito a: 2x1 + x2 - x3 ( 20
 xl ( 01 x2 ( 01 x3 ( 0
Resolvido o modelo equivalente, teremos a solução do modelo original
 com a troca do sinal de z.
· Problema da variável livre
 Se alguma variável do modelo não possuir a condição de não negativi-
 dade, podemos substituí-Ia pela diferença de duas outras variáveis não nega-
 tivas, pois um número qualquer sempre pode ser escrito como a diferença de
 dois números positivos.
Exemplo:
 max z = x1 + 2x2 + x3
 x1 + x2 + x3 ( 10
 Sujeito a: 2 x1 + 3x2 ( 20
 x1 ( 0 , x2 => livre
 Fazendo x2 = x4 – x5 , com x4 ( 0 e x5 ( 0 e substituindo no modelo
 anterior, teremos o modelo equivalente:
 max z = x1 + 2x4 - 2x5 + x3
x1 + x4 - x5 + x3 ( 10
 Sujeito a: . 2 x1 + 3x4 - 3x5 ( 20
 
x1( 0, x4 ( 0, x5 ( 01 x3 ( 0
 Com todas as variáveis não negativas. A solução deste modelo resolve
 o anterior. 
· Problema da solução básica inicial
Nos modelos resolvidos até agora pelo Simplex, as restrições são todas do tipo ( com os termos da direita positivos. O acréscimo das variáveis de folga fornece neste caso uma solução básica inicial.
 O problema aparece quando:
 1º a restrição é do tipo ( : a variável de folga é subtraída e seu valor é
 negativo, quando se anulam as variáveis de decisão.
 2º a restrição é do tipo = : não recebe a variável de folga.
 Neste caso, acrescentamos em cada uma das restrições do tipo ( e = variáveis auxiliares ai com a formação de um novo modelo. A solução básica inicial do novo modelo é formada pelas variáveis de folga das restrições do tipo ( e pelas variáveis auxiliares ai
 Exemplo:
 Maximizar z = x1 + x2 + x,
 2x1 + x2 - x3 ( 10
 Sujeito a: x1 + x2 + 2x3 ( 20
 2x1 + x2 + 3x3 = 60
 x1 ( 0, x2 ( 0, x3 ( 0
 a) Acrescentando as variáveis de folga:
 2x1 + x2 - x3 + xF1 =10
 x1 + x2 + 2x3 - xF2 = 20
 2 x1 + x2 + 3x3 = 60
 Não temos uma solução básica inicial devido à segunda e à terceira restrições.
 b) Acrescentando na segunda e terceira restrições as variáveis auxi-
 liares a2 e a3 :
 2 x1 + x2 - x3 + xF, = 10
 x1+ X2 + 2x3 - xF2 + a2 = 20
 2x1 + x2 + 3x3 + a3 = 60
 teremos agora uma solução básica inicial: xF1 = 10 , a 2 = 20, a3 = 60 com as
 outras variáveis todas nulas.
· Retorno ao modelo original:
O retorno ao modelo original deve ser feito com a eliminação das
 variáveis auxiliares e a manutenção da solução básica. Isto pode ser feito de
 duas maneiras:
4. Problema da degeneração
 No desenvolvimento do Simplex, a linha pivô é a restrição que apresen-
 ta o menor quociente não negativo, na divisão dos termos independentes pelos
 coeficientes positivos da variável que entra.
 Pode ocorrer que haja mais de um resultado nessas condições. Deve-
 mos escolher arbitrariamente um deles para calcular a solução. Entretanto,
 essa solução apresentará variáveis básicas com valor nulo. A saída de uma
 variável básica nula provoca o aparecimento de outra variável básica nula na
 solução seguinte, sem alteração do valor do objetivo.
 Neste caso, a solução é chamada degenerada. Se os coeficientes da
 função objetivo retornam não negativos em alguma iteração, o caso não apre-
 senta dificuldade. O problema aparece quando as iterações levam a circuitos,
 sem caracterizar a solução ótima. Embora o caso seja muito raro, há maneiras
 de solucioná-lo. Entretanto, ao nível desta exposição esse método não tem
 interesse.
5. Problema da Solução Ilimitada
 Isto ocorre quando a variável que entra na base não possui em sua
 coluna nenhum coeficiente positivo. Os programas de computador, neste caso,
 apresentam a última solução básica antes que a solução se torne ilimitada.
6. Caso de Soluções Múltiplas
 Se na solução ótima o coeficiente de uma variável não básica é zero,
 ele poderá entrar na base sem alterar o valor do objetivo, gerando outra solu-
 ção ótima. Neste caso, qualquer combinação linear dessas duas soluções
 também será solução ótima.
PROGRAMAÇÃO DINÂMICA
1. Definições Preliminares
 A Programação Dinâmica (PD) é uma técnica matemática de utilidade freqüente para se tomar uma seqüência de decisões inter-relacionadas. Os aspectos básicos que caracterizam problemas de PD são apresentados a seguir.
 A .O problema pode ser dividido em estágios, também chamados de etapas, com a necessidade de estabelecer-se uma decisão política a cada estágio. A decisão tomada em um estágio particular relaciona-se com os estágios considerados.
 B. Cada estágio (ou etapa) tem um conjunto de estados associados a ele. Em geral, os estados representam várias condições possíveis dentro das quais o sistema poderia estar naquele estágio do problema. Este conjunto de estados pode ser finito ou infinito.
 C. O efeito da decisão política é o de transformar o estado do estágio atual para um estado do próximo estágio. Quando o estado do próximo estágio é univocamente determinado pela decisão política sobre o estado atual, estaremos tratando de um problema de PD determinística. Pode ocorrer ainda que o estado destino dependa, além dos fatores já citados, de alguma distribuição probabilística. Neste último caso, estaremos diante de um problema de PD probabilística.
 D. Dado o estado atual, uma política ótima para os estágios restantes é independente da política adotada nos estágios anteriores. Esta propriedade é chamada de princípio da condição de ótimo, ou ainda de princípio da otimalidade de Bellman.
 Em contraste com a PL, não existe uma formulação matemática padrão para resolver toda a categoria de problemas de PD. Ao contrário, a PD é um tipo geral de abordagem para a solução de problemas, onde as equações particulares têm que ser desenvolvidas para se ajustarem a cada situação em particular.
.
2. Princípio da Otimalidade
 Serásuposto que se deseje analisar, em particular, o estado i no estágio n. Será também designado por k, uma decisão política tomada, onde k ( K (um conjunto de possíveis decisões a serem tomadas). Como um estado sempre pertence a um estágio, pode-se considerar sua localização pelo par (estágio,estado).
 Quando se considera a transição ( n, i ) ---> ( n+l, j ), deve-se considerar que o estado j alcançado dependa de n, i e da decisão k. A saber:
 j = t (n , i , k) ( 1 )
 
Onde t é a equação de transição. Se t é uma função que determina j univocamente a partir de seus argumentos, teremos um problema de PD determinística. Se t é uma variável aleatória, teremos um problema de PD probabilística.
 A cada transição existe um valor numérico a ela associado, designado por
 c ( n , i , j ), que pode ser a medida de algum custo ou contribuição associada a esta
 transição.
 A seguir é exibida a representação de parte de um problema de PD determinística, em forma de um grafo, envolvendo dois estágios e representando as possíveis transições 
 (n , i ) --- > ( n+l , j ).
Associado a uma transição em particular a partir de (n , i ) e de uma decisão política k, temos um valo, funcionalmente representado por f(n,i,k). Este valor numérico é usado para se poder estabelecer a decisão política através de algum objetivo, como maximizar ou minimizar este valor. Assim, entre todas as possíveis decisões, deve-se selecionar aquela que maximize / minimize o objetivo pretendido, o que fornece a decisão política ótima k* e um valor f* ( n ,i ) correspondente. A saber, a escolha de f* ( n ,i ) ocorre de acordo com
 f * (n, i ) = max k(K / min{f (n, i, k)j = f (n, i, k*) ( 2 ) 
Para aplicá-la, é necessário que previamente tenham sido calculados todos os f(n,i,k), para todas as decisões k possíveis a partir de (n , i ). Para cada transição (n ,i ) ((n+ l ,j ), f(n , i ,k) é calculado a partir do valor numérico associado à transição c(n,i,j ) e do valor f*(n + l ,j ). A relação pode variar de modelo a modelo. Pode ser um modelo simplesmente aditivo :
 f(n, i, k ) = c (n, i, j ) + f*(n + l, j ) ( 3 ) 
 Caso a função de recorrência represente, em um problema, quantias monetárias, e os estágios sejam períodos de tempo, e as quantias monetárias sejam capitalizadas nestes períodos de tempo de acordo com uma taxa (, é comum empregar-se técnicas de análise de solução que empreguem métodos decisórios baseados no valor presente. Para isto, o fator multiplicativo 1/(1+( ) é utilizado para transformar uma quantia monetária do momento n+1 para o momento n. Este fator deve, então, ser convenientemente introduzido na equação ( 3 ), gerando a equação ( 4 ), que deve ser empregada em tais problemas.
 f(n, i, k ) = c (n, i, j ) + 1/(1+() x f*(n+l, j ) ( 4 )
 A equação ( 2 ) em conjunto com alguma equação como ( 3 ) ou ( 4 ) estabelece uma relação recursiva, que é um modelo matemático para o princípio da otimalidade de Bellman e que pode ser enunciado como: dado o estado atual, uma política ótima para os estágios restantes é independente da política adotada nos estágios anteriores. Este principio resume a metodologia utilizada na resolução de problemas de PD: ( i ) conhecer o valor de f* para todos os estados do último estágio, a priori , e ( ii ) resolver, partindo do penúltimo estágio, e retroceder até alcançar o estágio inicial. 
3. Programação Dinâmica Determinística
 Esta seção ilustra o uso da PD deterministica através de dois exemplos.
 Exemplo 1. Suponha que se deseje estabelecer uma rota aérea de mínimo custo
 entre um aeroporto de saída, num país 0, até um aeroporto em outro país 4. Para
 isto, é necessário fazer escalas passando por aeroportos de 3 outros países
 (1, 2 e 3, nesta ordem), comprando-se passagens aéreas para cada vôo. A rede de
 possíveis vôos é ilustrada abaixo.
Conhecem-se os preços dos bilhetes de passagens aéreas, dados pelas tabelas abaixo. As linhas identificam o aeroporto de partida do vôo e as colunas o aeroporto de destino.
 do país 0 ao país 1 do país 1 ao país 2
 1 2 3 1 2 3
 1 168 175 196 1 340 353 309
 2 298 364 279
 3 315 333 296
 do país 2 ao país 3 do país 3 ao país 4
 1 2 3 1
 1 158 174 162 1 340
 2 146 135 124 2 316
 3 187 205 222 3 323
 Neste caso, os países são os estágios e os aeroportos são os estados.
 Solução:
 Podemos denotar a decisão k como correspondendo ao estado de destino da
 transição, ou seja, fazer simplesmente a equação j = t (n, i, k ) ser j = k para a
 transição (n, i ) ( ( n+l, j ).
 A função f*( n, i ) será o custo mínimo a ser ainda desembolsado para
 chegar-se ao destino (4,1). Assim, f*(4,1) = 0, dado que no destino nada mais
 será desembolsado.
 Os preços das passagens aéreas serão os valores c (n, i, j ). Como o custo de
 toda a rota é da forma aditiva simples, emprega-se a f (n, i, k ) = c (n, i, j ) + f*(n+l, j ).
 A escolha da função de recorrência será feita por selecionar-se
 
f * (n, i) = rnin k( K (f (n, i, k ) (.
 As tabelas abaixo sintetizam os resultados dos cálculos dos f (n, i, j ) realizados nas células correspondentes às decisões k (em fundo cinza). Iniciando os cálculos em n = 3, temos, para cada estado, uma única decisão, de forma que K = (1(.
i \ j = 1 k* f* (3, i )
 1 340+0=340 1 340 
 2 316+0=316 1 316
 3 323+0--323 1 323
 Para n = 2, K = {1,2,3)
 i \ j = 1 2 3 k* f*(2,i)
 1 158+340= 498 174+316= 490 162+323= 485 3 485
 2 146+340= 486 135+316= 451 124+323= 447 3 447
 3 187+340= 527 205+316= 521 222+323= 545 2 521
 para n = 1, K = (1,2,3 (
 i \ j = 1 2 3 k* f*(1,i )
 1 340+485= 825 353+447= 800 309+521=830, 2 800
 2 298+485= 783 364+447= 811 279+521-800 1 783
 3 315+485= 800 333+447= 780 296+521=8171 2 780
 e para n = 0, K = {1,2,3}.
 1\j= 1 2 3 k* f* (0, i)
 1 168+800=968 175+783= 958 196+780=976 2 958
Conclui-se, que desta forma a viagem pode ser realizada ao menor custo de 958 u.m. , na sequência ( 0,1 ) ( ( 1,2 ) ( ( 2,1 ) ( ( 3,3 ) ( ( 4,1 ) . 
4. Programação Dinâmica Probabilística
 Na PD probabilística, a transição ao estado do estágio seguinte não fica
 determinada pelo estado e decisão política no estágio atual. Após a decisão, pode
 ocorrer que a transição ao próximo estado do estágio seguinte dependa do acaso,
 isto é, dependa de uma variável aleatória que segue uma distribuição de
 probabilidade e que pode eventualmente estar condicionada ao estado, estágio e
 decisão política do estágio atual. Ou, simplesmente, em j = t (n,i,k), a função t é
 uma variável aleatória, no sentido de que a transição (n,i,k) ---> ( n+l, j ), representadana figura a seguir, possui probabililidade Pr ( j ( (n,i,k)].
 Estágio n+1
 
 estágio n
Pr(1( (n,i.k)( 1 f*(n+1,1)
 
 
 decisão k (n,i,k) Pr(2( (n,i,k)( 2 f*(n+1,2)
 i c(n,i,k)
 
 
Pr(m( (n,i,k)( m f*(n+1,m)
Quando o diagrama acima é expandido para incluir todos os estados e decisões possíveis em todos os estágios, temos a árvore de decisão do problema.
 Por causa da estrutura probabilística, a relação entre f(n,i,k) e f*( n+l,j ) difere um pouco da PD determinística. A forma precisa dependerá da estrutura particular do problema a otimizar. Em qualquer caso, adota-se o critério do máximo / mínimo valor esperado (máximo, se contribuição, mínimo s,e custo), de acordo com as possíveis decisões. No caso de simples aditividade, a relação recursiva poderá ser descrita pela fórmula (6.5).
 m
 f (n, i, k) = c(n, i, k) + ( Pr[ j( (n, i, k)] x f * (n + 1, j) (6.5)
 j=l
 Nesta, o somatório reflete o valor esperado da função de recorrên.cia no
 estágio posterior n+1, para todos possíveis estados de transição. Ela deve ser
 adicionada ao custo ou contribuição decorrente da decisão tomada em (n,i).
 Exemplo 2,
Uma unidade de um certo item pode ser produzida em uma fábrica
 em uma semana. O comprador fez um pedido de uma unidade para ser entregue
 no final da primeira semana e um pedido de mais uma unidade para ser entregue
 no final da semana seguinte. Ao ser entregue o item no final da primeira semana,
 o comprador submete-o a uma análise de qualidade. De acordo com a
 conformidade do produto, o comprador decide comprá-lo, pagando a quantia de
 600 u.m. na próxima semana, ou rejeitá-lo, constituindo assim uma perda total
 para o produtor.
 Para o produção de um ítem em uma semana, podem ser alocadas urna ou
 duas unidades de produção. Cada unidade de produção alocada gera um custo
 total de 100 u.m. (maquinaria, mão-de-obra, matéria-prima, ete), e ambas são
 independentes entre si. Uma unidade de produção, isoladamente, tem
 probalidade igual a 0,5 para produzir um item em conformidade com o controle
 de qualidade do comprador. Estes dados de custo e probabilidade referem-se às
 condições atuais para a produção da primeira semana.
 Para a segunda semana, as unidades de produção sofrerão um
 aperfeiçoamento tecnológico que elevará a probabilidade de conformidade para
 0,65, e também elevará o custo total de uma unidade de processo em 50%.
 Represente o diagrama do problema decisório e determine a melhor política
 decisória ao inicio de cada semana de produção, em todas as situações.
· Modelagem e Resolução do Problema.
 A decisão k significa o número de unidades de produção a serem alocadas
 para a semana. Cada estágio é o início de uma semana. Os estados representam o
 número de itens aceitos pelo comprador referente à produção da semana anterior.
 As contribuições c(n,i,k) referentes a cada decisão refletem a receita da venda da
 unidade entregue ao comprador na semana anterior, menos os custos de
 produção.
 Assim, na semana 0, existe apenas o custo de 100 u.m., caso seja
 empregada uma unidade de processo, ou 200 u.m., caso sejam empregadas duas
 unidades de processo. Já para a semana posterior, os custos elevam-se para 150
 u.m., se k = 1, e 300 u.m., caso k = 2. Por sua vez, na semana 1, se tiver sido
 aceito o item produzido na semana anterior, deve-se considerar a contribuição o
 efeito adicional da receita de 600, menos quanto ao custo das unidades de
 produção empregadas, resultando assim numa contribuição positiva. Ao final, no
 início da semana 2, o valor da função de recorrência reflete a receita adicional da
 venda do ítem produzido na semana 1, que pode ser 0 ou 600, caso o item seja
 recusado ou aceito, respectivamente.
 Desta forma, a árvore decisória fica assim representada:
 
 K=2 (0,75 ) 1 300 K=2 (0,8775) 1 600
 
-200 450 (0,1225)
 0 
 -100 (0,50) -300 (0,65)
 
 K=1 (0,50) 0 -150 K=1 (0,35) 0 0
Com relação à distribuição de probabilidades quando n =0 , i =0 e k = 2,
 deve-se considerar que o item não será aceito, se ambas as unidades de processo
 não conseguirem o item aceitável, isto é, Pr[ 0( (0,0,2) = Pr[la. unidade de
 processo fracassar] x Pr( 2a. unidade de processo fracassar] = 0,5 x 0,5 = 0,25 e
 assim: Pr[ 1( (0,0,2) = 1 - Pr[ 0 ( (0,0,2) = 1 - 0,25 = 0,75.
Raciocino idêntico é aplicado para n = 1, k = 2.
 De acordo com a equação 6.5, tem-se, então,
 f(1,1,1) = 450 + 0,65 x 600 + 0,35x0 = 840,00;
 f(1,1,2) = 300 + 0,8775 x 600 + 0,1225 x 0 = 826,50;
 f*(1,1) = max{ 840,00, 826,501( = 840,00, e assim k* = 1.
Os resultados de todos os cálculos estão sumarizados nas tabelas a seguir.
 f(1,i,k)
 i / k 1 2 k* f*(1,i)
 0 240,00 226,50 1 240,00 
 1 840,00 826,50 1 840,00
 f (0,i,k)
 i / k 1 2 k* f*(0,i)
 0 440,00 490,00 2 490,00
Assim, as decisões ótimas são alocar duas unidades de produção para a
 primeira produção (semana 0) e alocar uma única unidade de produção para a
 próxima produção, independente de haver sido aceito ou não o ítem produzido
 anteriormente.
DESIGNAÇÃO
· Problema da Designação
1. Introdução:
 Um caso especial do modelo de transportes é aquele em que cada
 origem tem uma unidade disponível e cada destino necessita também de uma
 unidade. É o caso de escalar vendedores para regiões de vendas, máquinas
 para diversos locais etc.
 Essa característica torna o algoritmo de soluções bastante simples.
 Antes de aplicá-lo, devemos verificar se o modelo está equilibrado. No modelo
 de designação, o número de origens deve ser igual ao número de destinos
 devido a sua característica. Caso isso não ocorra, devemos construir origens
 ou destinos auxiliares, com custo de transferência zero.
2. Descrição do Algoritmo
a. Subtrair de cada linha seu menor valor. Em seguida fazer o mesmo com as colunas. Cada linha e cada coluna deverá então apresentar pelo menos um elemento nulo.
b. Designar origens para destinos nas células em que aparece o elemento nulo. Dar preferência a linhas ou colunas que tenham apenas um zero disponível. Cada designação efetuada invalida os outros zeros na linha e na coluna da célula designada. Se a designação se completa, o problema está resolvido. Se não:
c. Cobrir os zeros da tabela com o menor número de linhas possível.
 Isto pode ser feito da seguinte forma:
· marcar as linhas sem designação;
· marcar as colunas com zeros nas linhas marcadas;
· marcar as linhas com designação nas colunas marcadas;
· voltar a marcar as colunascom zeros nas linhas marcadas até que não seja possível marear novas linhas ou colunas;
· riscar as linhas não marcadas e as colunas marcadas.
d. Subtrair o menor valor dentre os números não cobertos, de todos os elementos da tabela. A reposição necessária nas linhas e colunas com zeros para impedir o aparecimento de custos negativos na tabela resulta no quadro em que:
· os elementos não cobertos ficam diminuídos deste número;
· os elementos no cruzamento de coberturas ficam aumentados desse número;
· os outros elementos permanecem iguais.
e. Retomar ao item b.
Exernplo: O quadro representa os custos de transporte de uma máquina dos locais de depósito para as fábricas onde deverão ser instaladas. Designar uma máquina para cada fábrica com o menor custo total possível no programa:
 F1 F2 F3 F4
 L1 10 12 15 16
 L2 14 12 13 18
 La 10 16 19 15
 L4 14 12 13 15
 Solução:
 Subtrair o menor número Subtrair o menor número
 de cada linha de cada coluna
 
 0 2 5 6 0 2 4 3
 2 0 1 6 2 0 0 3
 0 6 9 5 0 6 8 2
 2 0 1 3 2 0 0 0
Designar nos zeros de linhas ou colunas (prefira linhas ou colunas com apenas um zero). Anule os outros zeros.
solução:
 Designação Custo
 L1 ( F1 10
 L2 ( F2 1 2
 L3 ( F3 1 3
 L4 ( F4 1 5
 Total Custo 50
3. Caso de Maximização
 Caso a tabela de transferência traga retornos que devem ser maximi-
 zados, o modelo deverá ser substituído por outro de minimização. Como no
 problema dos transportes, isto pode ser feito multiplicando a função objetivo
 por -1, ou transformando o quadro num quadro de perdas (complemento em
 relação a um valor fixo).
 Exemplo: O quadro representa as eficiências de quatro vendedores,
 testados em quatro regiões. Os potenciais de vendas nas regiões são conheci-
 dos. Designar um vendedor para cada região para maximizar o valor total das
 vendas.
 Capacidade de cada vendedor de atingir o potencial da região em %
 R1 R2 R3 R4
 V1 70 60 80 90
 V2 70 80 70 90
 V3 60 90 60 70
 V4 70 80 70 80
Potencial de vendas em milhares de $
 R1 = 100
 R2 = 80
 R3 = 60
 R4 = 90
Solução: Quadro de vendas ou retornos ( % x Potencial de Vendas )
70
48
48
81
70
64
42
81
60
72
36
63
70
64
42
72
Quadro de perdas : subtrair de 81
9
33
33
0
9
17
39
0
21
9
45
18
11
17
39
9
Solução :
 Subtrair o menor número Subtrair o menor número
 de cada linha de cada coluna
11
33
33
0
9
33
3
0
11
17
39
0
9
17
9
0
12
0
36
9
10
0
6
9
2
8
30
0
0
8
0
0
 Designação Vendas ( em milhares de $ )
 V1 ( R3 
 48
 V2 ( R4
 81
 V3 ( R2 
 72
 V4 ( R1
 70
Total de vendas 271
PROGRAMAÇÃO INTEIRA E MISTA
 Os problemas de Programação Inteira e Mista são, a princípio, estruturados da mesma forma que os de PL. O que os caracteriza é a presença de ao menos uma restrição de integridade. Entende-se por restrição de integridade imposta a uma variável a exigência feita quanto aos possíveis valores que podem ser assumidos pela variável: deve assumir um número inteiro.
 É o caso onde uma variável representa, por exemplo, a quantidade de carros produzidos. Ao impor restrições de integridade para estas variáveis, temos um problema de Programação Inteira /Mista. Se todas as variáveis devem ser inteiras, costuma-se denominar o problema de programação inteira; caso as restrições de integridade sejam impostas apenas a algumas variáveis do modelo, mas não todas, temos um problema de programação mista. Não obstante, a técnica de resolução empregada é a mesma.
 Para ilustrar, o exemplo abaixo servirá para introduzir algumas idéias básicas e auxilia posteriormente na compreensão da técnica da ramificação
progressiva de resolução. Neste exemplo, as restrições de integridade foram impostas às duas variáveis do modelo.
 Exemplo 1.
 Max Z = 2x1 + x2
 sujeito a
 xl +x2(5
 -x1 + x2 ( O
 6x1 + 2x2 ( 21
 xl, x2 ( O e x1, x2 inteiros
 Na figura a seguir é apresentada a representação gráfica do problema. A solução ótima ao problema de PL (sem considerar as restrições de integridade) encontra-se no vértice correspondente a x,* = 2,75 e X2* = 2,25. O valor correspondente da função objetivo é Z* = 7,75.
No entanto, dadas as restrições de integridade, esta solução não pode ser aceita. É necessário pesquisar sobre os valores de soluções inteiras.
 Poder-se-ia esperar que o simples arredondamento das variáveis não inteiras para o inteiro mais próximo pudesse resolver o problema de determinação do ótimo do problema de programação inteira apresentado.
 Neste caso, a solução inteira ótima seria x1* = 3 e x2*= 2. No entanto, esta solução deixa de ser compatível, pois não satisfaz à restrição 6x1 + 2x2 ( 21. Desta forma, não basta resolver o problema como se fosse um problema de PL e arredondar os valores das variáveis para inteiros mais próximos (acima ou abaixo), esperando que esta seja a solução ótima ao problema. Pode ocorrer, nestes casos de simples arredondamento, que a solução arredondada deixe de satisfazer a todas as restrições ou que a solução realmente não seja a ótima.
 Poder-se-ia, a princípio, pesquisar todas as soluções inteiras contidas dentro do conjunto So de soluções compatíveis do problema de PL. Neste caso, são poucos os pontos que correspondem a soluções inteiras e que são compatíveis. Eles são os pontos de cruzamento da grade sobre So.
As soluções inteiras compatíveis são: (0,0), (1,0), (2,0), (3,0), (1,1), (2, 1), (3,1) e (2,2). Computando o valor da função objetivo, verifica-se que (3,1) é ponto interior de So e solução inteira compatível ótima do problema. Observe-se que este ponto nem sequer é a solução inteira compatível mais próxima do ponto extremo ótimo do problema de PL. Fica assim descartado o uso de métodos de obtenção do ótimo para o problema de programação inteira ou mista baseados em considerações geométricas ou de proximidade ao ponto extremo ótimo do problema de PL.
 Um procedimento algorítmico mais bem elaborado é imprescindível. Uma alternativa é a Técnica de Ramificação e Limite'. Embora existam outros algoritmos de programação inteira, como o de Balas e de Gomory, algoritmos de enumeração lexicográfica, etc., o algoritmo da Ramificação e Limite parece ser o de emprego mais comum. Em termos de eficiência computacional, na comparação entre os diversos algoritmos, não existe uma palavra final. Isto é, enquanto o algoritmode Ramificação e Limite é mais eficiente que os demais para determinados problemas, pode suceder o contrário em outros.
1. Técnica da Ramificação e limite
 O objetivo desta seção é explanar as idéias centrais a respeito de um método muito popular de resolução de problemas de Programação Inteira e Mista: a técnica de Ramificação e Limite (RL). A introdução da técnica de RL será inicialmente apresentada de maneira informal.
 Inicialmente, resolve-se o problema como sendo um problema de PL puro, ignorando-se totalmente as restrições de integridade. Se foi obtida uma solução ótima limitada e se todas as restrições de integridade forem satisfeitas, a presente solução é ótima ao problema de programação inteira ou mista e finaliza-se o procedimento de resolução. Em caso de solução ótima ilimitada ou impossível, finaliza-se também o procedimento de resolução. Senão, ao menos alguma restrição de integridade foi violada.
 Uma das restrições de integridade violada servirá para provocar uma dicotomia no conjunto de soluções compatíveis S0, forçando a resolução de dois novos problemas de PL. Este processo de criar dicotomias, ao ser aplicado repetidas vezes, conduz à criação de uma árvore binária de busca de solução. Cada um dos dois novos problemas gerados pelo processo de dicotomia possui a mesma função objetivo e restrições do problema pai, isto é, o problema que gerou a dicotomia, mas a cada um adiciona-se uma restrição, tomando-se como base os dois inteiros mais próximos da variável não-inteira que corresponde à restrição de integridade violada
 Para ilustrar a forma como a dicotomia é realizada, ela será aplicada sobre o exemplo 1. Neste problema, x1 = 2,75 será utilizado para produzir a primeira dicotomia, embora a escolha também pudesse recair sobre x2 ao invés de x1.Criam-se assim dois novos problemas de PL, cada um com a mesma função objetivo e as mesmas restrições. Porém, ao primeiro adicionamos uma restrição da forma x1 ( 2 e ao segundo adicionamos a restrição x1 ( 3, pois 2 e 3 são os
 inteiros mais próximos a 2,75. Esta dicotomia produz subconjuntos disjuntos S1 e S2 de S0, em cada um dos quais uma nova solução ótima será pesquisada.
O método Simplex aplicado ao espaço de solução S1, ou seja, ao problema inicial mais a restrição x1 ( 2, conduz à solução ótima x1 = 2, x2=2 e Z = 5. No espaço de solução S2, ou seja, ao problema inicial mais a restrição x1 ( 3, a solução ótima será x1 = 3, x2 =1,5 e Z = 7,5.
 Neste ponto será útil começar a acompanhar o processo de resolução através de uma árvore de resolução, na qual cada um dos nodos representa exatamente um problema de PL e sua solução. Nos ramos da árvore serão colocadas as restrições incorporadas pelo processo de dicotomia. No momento presente. a árvore será
Os espaços de solução de cada nodo servem também para rotular os nodos. Assim, serão feitas referências aos nodos S0, S1, S2, etc. Note que, em S1, uma solução inteira já foi alcançada. Não há, no entanto, forma de determinar se esta solução inteira é ótima. Como neste nodo não há mais nenhuma restrição de integridade violada, não haverá mais ramificação a partir deste ponto. Mas, em S2, a variável x2 é não-inteira. Esta variável irá ocasionar nova dicotomia, gerando conjuntos S3 e S4e respectivas soluções. A expansão da árvore, a partir do nodo S2é vista a seguir.
Como S4 é um espaço de soluções compatíveis vazio, não haverá nenhuma solução compatível. Este também será um nodo da árvore a partir do qual não haverá mais ramificação. Em S3, a ramificação ainda será possível, pois x1 não satisfaz à restrição de integridade. A partir deste nodo, a ramificação será como segue.
Neste ponto, nenhuma ramificação adicional será possível. S5 apresenta também uma solução inteira. Além disso, a solução correspondente a S5 é melhor que a solução correspondente a S1, dado que o objetivo é de maximização. Portanto S5 exibe a solução ótima ao problema, x1* = 3, x2* = 1, Z* = 7.
2. Limites de Pesquisa para a Ramificação
 O Algoritmo da RL é uma abordagem enumerativa que toma vantagem no fato de que em um problema de PL inteira ou mista o conjunto de valores das variáveis inteiras é finito. Na seção anterior foram apontadas duas situações que impedem um uma ramificação posterior a partir de um determinado nodo:
· todas as restrições de integridade são atendidas na solução ótima do nodo;
· conjunto solução do nodo é vazio, isto é, não há solução compatível.
Admita-se que na solução ótima ao problema de PL em Sk ocorra que a variável xi tenha valor não-inteiro, tal que n < xi < n+1, com n inteiro, e que existe uma restrição de integridade sobre xi. Neste caso, a ramificação pode ser produzida a partir desta variável. Constrói-se assim um novo problema de PL por introduzir uma restrição da forma xj < n, que irá determinar o conjunto solução Sr = Sk ( (n ( xi ( n (, e outro nodo por introduzir-se a restrição xi > n + 1, que irá determinar o conjunto solução Sr+1 = Sk ( (x ( xi ( n + 1 }. Neste caso teremos: 
(i) Sr ( Sr+1 = (, e 
(ii) Sr , Sr+1 ( Sk
Admita-se que o problema é de maximização. Se Sr ( (, então Max { Z = c'x ( x ( Sk ( ( Max { Z = c'x ( x ( Sr (ou, ainda, Zk ( Zr . Fato similar ocorre se Sr+1 ( ( : então Zk ( Zr+1 . Desta forma, o processo de ramificação gera sempre uma árvore que, a níveis mais baixos, possui valores não-crescentes para a função objetivo. Além do mais, se a solução ótima em Sk é única, tem-se Zk > Zr (desde que Sr ( ( ) e Zk > Zr+1 (desde que Sr+1 ( ( ), determinando um decrescimento nos valores da função objetivo.
 Caso se trate de um problema de minimização, sucede o contrário. Se Sr ( ( , então Min ( Z = c'x ( x ( Sk } ( Min ( Z = c'x ( x ( Sr } ou, ainda, Zk ( Zr. Fato similar ocorre se Sr+1 ( (: então Zk ( Zr+1. Desta forma, o processo de ramificação gera uma árvore que, a níveis mais baixos, possui valores não-decrescentes para a função objetivo. Além do mais, se a solução ótima em Sk é única, term-se Zk < Zr (desde que Sr ( ( ) e Zk < Zr+1 (desde que Sr+1 ( ( ), determinando um crescimento nos valores da função objetivo. 
 Além do mais, se o problema de Programação inteira ou mista tem seu ótimo em Sk, este ponto de ótimo deve encontrar-se em Sr ou em Sr+1 , pois o processo de bifurcação apenas elimina de Sk a faixa de valores de xi
compreendida entre n e n+1, proibitiva a esta variável devido a restrição de
integridade imposta sobre xi. Admitindo que o problema tenha urna solução
ótima limitada, esta deve encontrar-se no nodo-raiz So do problema e,
consequentemente, em algum dos nodos segundo algum caminho que parta
de S0.
 Será visto que há uma terceira situação que pode podar a árvore gerada pela técnica de RL. Para compreendê-la de forma conveniente, admita-se que um determinado nodo tenha o conjunto de soluções compatíveis Sk.
 O comportamento monotônico de não-crescimento ou não-decrescimento da função objetivo, de acordo com o objetivo pretendido, maximizar ou minimizar, permite estabelecer um novo critério de poda no processo de ramificação. Imagine-se, a título de exemplo, um problema de maximização no qual já tenha sido descoberta uma solução que atenda a todas as restrições - inclusive de integridade - com valor ótimo Zr = 500. Porém, o processo de construção da árvore ainda não acabou. Prosseguindo por outro caminho, recai-se em um nó em cuja solução ocorre o valor Zs = 485. O que dizer desta nova solução? Certamente é pior que a anterior. Mesmo que alguma restrição de integridade não tenha sido atendida nesta nova solução, certamente não valerá a pena prosseguir a bifurcação a partir deste nodo. Por que? Porque as soluções compatíveis que descendem a partir deste nodo terão valores para a função objetivo nunca superiores a 485, sendo, portanto, soluções piores à solução que obteve Zr = 500.
 Embora esta situação não tenha chegado a ocorrer no exemplo estudado na seção precedente, ela pode vir a ocorrer facilmenteem problemas de maior porte. Assim deve-se considerar que a poda controlada desta forma salva esforços computacionais, por evitar que a ramificação enverede por caminhos que seguramente não conduzem a melhores soluções.
 Assim, no algoritmo de RL será adotado este mecanismo de controle,
através de um valor Zlimite . Antes de prosseguir com alguma ramificação por algum dos nodos da árvore, será sempre feita uma comparação com este valor limitante, para ver se vale a pena prosseguir com a ramificação por este caminho. Pode ser necessário redefinir este valor: isto ocorre quando uma solução melhor, que atenda a todas as restrições (inclusive de integridade), é encontrada. Nos problemas de maximização, Zlimite atua como um limite inferior na pesquisa, isto é, só interessa prosseguir a ramificação através de nodos onde Z > Zlimite . Nos problemas de minimização, Zlimite atua como um limite superior na pesquisa, isto é, só interessa prosseguir a ramificação através de nodos onde Z < Zlimite.
Teoria das Filas
1. Introdução:
 Um dos sintomas mais freqüentes de funcionamento deficiente de um sistema é o congestionamento de clientes. Quando o número de clientes à espera de atendimento, num banco por exemplo, é permanentemente muito grande, é sinal de que o número de caixas não está adequadamente dimensionado.
 Um dos tópicos da Pesquisa Operacional com muitas e variadas aplicações no campo da administração das empresas é a Teoria das Filas, que trata de problemas de congestionamento de sistemas, onde a característica principal é a presença de "clientes" solicitando "serviços" de alguma forma. Em sua expressão mais simples, um sistema de filas é composto por elementos que querem ser atendidos em um posto de serviço e que, eventualmente, devem esperar até que o posto esteja disponível. As aplicações em administração são muitas:
· Estabelecimento de uma política de atendimento ao público em empresas concessionárias de serviços públicos, determinando o número de atendentes e a especialização de cada um.
· Estudo de um sistema de almoxarifados, de forma a determinar os custos totais de operação.
· Estudo da operação de um centro de processamento de dados, com o objetivo de determinar políticas de atendimento e prioridades para execução dos serviços.
· Determinação de equipes de manutenção em grandes instalações, onde há custos elevados associados aos equipamentos danificados, à espera de reparos.
· Estudo de operação de caixas (bancos, supermercados etc.) com o objetivo de estabelecer uma política ótima de atendimento ao público.
Vários outros casos de aplicação podem ser citados: programação de tráfego aéreo em aeroportos, determinação de capacidade em pátios de estacionamento de automóveis, tempo de espera em comunicações telefônicas, sincronização de semáforos, estudo e programação de linhas de montagem etc.
Em todos os exemplos citados existem clientes solicitando serviços, que são limitados por restrições próprias do sistema. Assim, existe a possibilidade de que esses clientes venham a formar filas, até que o serviço solicitado possa ser prestado.
 Por exemplo, no caso do sistema de manutenção, os clientes são os equipamentos danificados que solicitam serviços (reparos) do pessoal das equipes (atendentes) e que, eventualmente, devem formar uma fila e esperar sua vez.
 É importante observar que, nesse caso, há dois eventos distintos ocorrendo, de uma maneira geral, de forma aleatória:
· os equipamentos não se danificam regularmente, de hora em hora por exemplo;
· por mais bem-treinada que seja a equipe, os tempos gastos nos reparos não são sempre os mesmos.
 Dessa forma, pode ocorrer que num determinado dia não há um só equipamento para reparo, enquanto no dia seguinte o número de equipamentos danificados é superior à capacidade de atendimento da equipe, provocando congestionamento no sistema.
 São essas irregularidades na ocorrência dos eventos que determinam o funcionamento desse tipo de sistema e que serão expressas em termos probabilísticos no estudo da Teoria das Filas.
 Quando, em qualquer dos casos acima, o tamanho da fila ultrapassa o valor esperado ou considerado normal, podemos dizer que o sistema está entrando em congestionamento, e, nesta situação, a qualidade e a produtividade do sistema caem e o custo total de operação tende a crescer sem controle. Esta é a principal razão que justifica o estudo dos problemas de congestionamento.
2. Fatores Condicionantes da
 Existem diversos fatores que condicionam a operação de um sistema, ou seja, podem interferir tanto que o desempenho do sistema passa a ser função deles. Esses fatores podem ser classificados em:
· forma dos atendimentos
· forma das chegadas
· disciplina da fila
· estrutura do sistema.
· Forma dos Atendimentos
 De forma geral, os postos de atendimento são formados por pessoas, instalações e equipamentos que devem operar em sintonia de forma a prestar um bom serviço.
 Por isso, existem diversos elementos passíveis de atuação por parte do administrador, com o objetivo de aprimorar o desempenho do sistema:
· dimensionamento da capacidade
· treinamento dos atendentes
· rotinas administrativas
· sistemas de informações etc.
 Todos esses elementos podem ser observados, pesquisados, avaliados e aprimorados. O resultado da interação desses fatores aparece, para o cliente, como o tempo gasto em cada atendimento ou como o número de atendimentos que o sistema consegue fornecer.
 Assim, essa é a variável que o administrador deve observar em primeiro lugar.
O primeiro passo no estudo de um sistema de filas é o levantamento estatístico do número de clientes atendidos, por unidade de tempo, ou do tempo gasto em cada atendimento.
Esse tempo pode ser regular, ou seja, todos os atendimentos têm a mesma duração ou aleatórios, que é a situação mais comum, em que cada cliente exige um tempo próprio para solução de seu problema.
A finalidade do levantamento estatístico é, então, deten-ninar a distribuição de probabilidades do número de atendimentos ou da duração de cada atendimento.
O resultado obtido é uma função de distribuição de probabilidades como as mostradas na Fig. 6.1
Além disso, mais dois fatores devem ser analisados na definição do regime de atendimento:
· Disponibilidade do serviço, já que alguns sistemas só atendem durante um certo intervalo de tempo, enquanto outros estão em disponibilidade.
· Capacidade de atendimento simultâneo do sistema, isto é, o número de postos de seviço que podem atender os clientes. Existem sistemas com apenas 1 posto ou com vários postos de atendimento, conforme será visto à frente.
· Forma de Chegadas
 As chegadas de clientes a um sistema ocorrem, na maioria dos casos de interesse para a administração, de forma aleatória, ou seja, o número de clientes que chegam por unidade de tempo varia ao acaso. Toma-se importante, dessa forma, realizar um levantamento estatístico com a finalidade de descobrir se o processo de chegadas pode ser caracterizado por urna distribuição de probabilidades. Para que essa caracterização possa ser feita, o processo de chegadas tem necessariamente que estar no chamado "estado estacionário". Isso significa que a distribuição de probabilidades que identifica o processo hoje será a mesma de amanhã.
 Ao contrário, quando a distribuição de probabilidades de um evento varia com o tempo, o sistema é dito no estado "não-estacionário" ou "transitório".
 Assim, a afluência de público a uma agência bancária é um processo estacionário, já que depende das condições normais de negócio existentes na localidade. Porém, a iminência de uma greve bancária prolongada ou um boato de falência, por exemplo, levaria o sistema para o estado "não-estacionário", já que provocaria uma corrida ao banco. Isso significa que a distribuição de probabilidades que explica o evento aleatório das chegadas normais seria diferente da distribuição que explicaria as chegadas, no caso de corridaao banco.
 A distribuição de probabilidades do número de chegadas é uma função como a mostrada na Fig. 6.2:
· Disciplina da Fila
 A disciplina da fila é um conjunto de regras que determinam a ordem em que os clientes serão atendidos. Esse atendimento pode ser feito pela ordem de chegada (primeiro a chegar é o primeiro a ser atendido), pela ordem inversa de chegada (último a chegar é o primeiro a ser atendido), atendimento com prioridade para certas classes etc.
· Estrutura do Sistema
 Além das características gerais de um sistema de filas, estudadas nos itens anteriores, é importante determinar sua estrutura, que é, também, um elemento fundamental do estudo.
 Os sistemas de filas podem ter estruturas muito variadas, e cada caso exige um estudo analítico diferente.
 A estrutura mais simples é mostrada na Fig. 6.3, onde temos um sistema de 1 fila e 1 canal.
 A Fig. 6.4 mostra um sistema de 1 fila e 3 canais em paralelo, enquanto a Fig. 6.5 mostra um sistema complexo de filas e canais em série e em paralelo.
3. Medidas de Efetividade de um Sistema
 No estudo de um sistema de filas, podem ser determinadas várias medidas de efetividade com a finalidade de indicar seu desempenho, como por exemplo:
· percentagem do tempo em que o posto de atendimento permanece ocioso ou ocupado;
· tempo médio que cada cliente gasta na fila de espera;
· tempo médio gasto pelo cliente no sistema, isto é, a média dos tempos computados desde
· instante de entrada até o de saída;
· número médio de clientes na fila, em uma unidade de tempo, ou, o que é a mesma coisa, tamanho médio da fila;
· número médio de clientes no sistema em uma unidade de tempo;
· probabilidade de existir um número n de clientes no sistema.
 A escolha do parâmetro depende do objetivo do estudo. Por exemplo, no dimensionamento de um pátio de estacionamento, a área do pátio poderá ser proporcional ao número médio de veículos no sistema.
 A probabilidade de haver um número maior que essa média é o risco que se corre de que o pátio não seja suficiente.
 Pode ocorrer que num determinado estudo os objetivos sejam conflitantes. Por exemplo, no estudo de um posto de atendimento ao público, é necessário haver um compromisso entre o número médio de clientes na fila e o tempo ocioso do atendente, já que um varia inversamente com o outro e ambos têm peso econômico.
SIMULAÇÃO DE MONTE CARLO
1. Introdução:
 A simulação de um sistema é a operação de um modelo que representa esse sistema, geralrnente em computadores, respeitando todas as regras e condições reais a que o sistema está submetido. O modelo permite manipulações que seriam inviáveis no sistema real que elo representa, devido ao custo ou à impossibilidade de realizá-las.
 A simulação sempre foi usada pela humanidade como forma de representar os processo relativos aos sistemas onde as pessoas viviam. Nesse caso estão as esculturas, pinturas e todas as formas de representação de idéias. Na ciência, a utilização de modelos é uma atividade corriqueira, desde os modelos em escala reduzida (barragens, topografia, edificações etc.), modelos de aviões para estudo de aerodinâmica e modelos analíticos de processos físicos e mentais.
 O uso moderno da palavra "simulação", com o sentido que tem em Pesquisa Operacional, tem sua origem em um trabalho de Von Newmann e Ulam de 1940, quando eles associaram a expressão "análise de Monte Carlo" a uma técnica matemática que utilizaram para resolver problemas de blindagem em reatores nucleares.
O tratamento dado aqui à simulação obedece às seguintes restrições:
· O método apresentado, embora geral, está restrito a problemas relativos a empresas.
· O método mostrado tem caráter didático, já que é quase manual.
· Os modelos usados aqui são modelos lógicos ou matemáticos aplicados a problemas de
· administração.
· Os problemas discutidos envolvem uma ou mais variáveis que têm características
· probabilísticas e que, por isso, não podem ser determinados com certeza, como por exemplo demanda de consumidores, tempos de produção etc.
2. Razões para usar simulação
Muitas razões podem ser enumeradas para justificar o uso da simulação em administração.
Dentre elas podemos destacar:
· Pode ser impossível ou muito oneroso observar diretamente certos processos no mundo real.
Por exemplo, o estudo de sincronização de sinais de trânsito de uma certa via poderia ser realizado experimentalmente, ajustando sucessivamente os semáforos e verificando as conseqüências em termos de congestionamento, acidentes etc. 
É evidente que esse processo não pode ser implementado na prática, e a alternativa é criar modelos das situações reais (número e características das vias, intensidade e tipo do trânsito etc.) para testes em computadores.
· O sistema observado pode ser tão complexo a ponto de tomar-se impossível descrevê-lo em termos de um conjunto de equações matemáticas de solução analítica viável.
Por exemplo, a representação global de uma grande empresa, envolvendo múltiplas atividades, como produção, vendas, marketing, planejamento e muitos órgãos, como departamentos e divisões.
· Outro exemplo são os sistemas de estoques em série e em paralelo que devem ser estudados de forma a se ter uma política de operação com mínimo custo.
Mesmo sendo possível desenvolver um modelo matemático do sistema em foco, a sua solução pode ser muito trabalhosa e pouco flexível.
Um exemplo disso é um sistema de filas, com múltiplos canais e com característi-
cas de atendimento e de chegadas de clientes definidas por distribuições pouco conhecidas.
3. Vantagens do uso da simulação
· A simulação permite estudar e experimentar complexas interações internas de um dado sistema, seja ele uma empresa ou parte da mesma.
· Através da simulação, podem ser estudadas algumas variações no meio ambiente e verificados seus efeitos no sistema total.
· A experiência adquirida em construir os modelos e realizar a simulação pode conduzir a uma melhor compreensão do sistema, com possibilidades de melhorá-lo.
· A simulação de sistemas complexos pode fornecer valiosa introvisão no sentido de descobrir as variáveis mais importantes do sistema e a forma como elas interagem.
· A simulação pode ser usada para experiências com novas situações, sobre as quais se tem pouca ou mesmo nenhuma informação, com o intuito de preparar a administração para o que possa acontecer.
· A simulação pode servir como um primeiro teste para se delinearem novas políticas e regras de decisão para a operação de um sistema, antes de experimentar no sistema real.
4. Fases na realização de uma simulação
· Formulação do Problema e Coleta de Dados
Devem ser explicitamente definidos os objetivos da simulação, a amplitude e profundidade que se quer da análise, e os recursos disponíveis. É evidente que essa definição inicial do problema pode ser alterada durante a realização do processo da simulação.
 A coleta de dados é um processo de recolhimento dos fatos e informações disponíveis que serão processados quando houver necessidade. De posse da formulação do problema, como explicado acima, os dados devem ser coletados observando os seguintes cuidados:
· deve haver uma quantidade suficiente de dados;
· os dados devem ser qualitativamente confiáveis;
· os dados devem ser significativos para o processo de decisão.
A coleta de dados é uma atividade que pode influenciar na formulação do problema, uma vez que permite definir o escopo do modelo, sua validade e, até mesmo, o grau de confiabilidade dos resultados obtidos no final da simulação.
· Identificação das Variáveis e das Condições do Sistema
Como primeiro passo da modelagem, devem ser identificadas as variáveis do problema. É importante definir, também, as relações entre as variáveis, as condições e restrições do sistema, de forma a possibilitar a construção de um modelo que represente, o mais fielmente possível, sua operação no mundo real.
· Construção do Modelo
Essa talvez seja a parte mais difícil doprocesso de simulação e que deve ser realizada com mais cuidado. A dificuldade decorre do fato de que, na construção de modelos, são exigidas tanto arte quanto técnica, para que eles representem bem os sistemas, levando em conta todas as relações importantes, tanto entre as variáveis internas do sistema quanto entre este e o meio ambiente que o cerca.
Conhecidos os objetivos, os dados disponíveis, as variáveis do processo, as relações e condições reais, a construção do modelo consiste na formulação das equações que devem representar as inter-relações do sistema e no estabelecimento de limites de variação dos resultados e valores.
· Validação do Modelo com Dados Históricos
 Uma vez construído o modelo, é necessário saber se ele atende aos objetivos da simulação, representando corretamente o sistema em estudo. Os testes com o modelo devem abranger também os dados, de forma a verificar sua consistência.
 O primeiro teste que se faz, normalmente, é a operação do modelo com dados históricos e condições conhecidas, com o objetivo de se conseguir reproduzir o desempenho do sistema obtido na realidade.
 Caso o modelo seja aceito, deve ser realizado um programa específico de computador ou dependendo do caso, uma planilha eletrônica utilizando algum programa existente no mercado. Essas tarefas exigem conhecimentos específicos na área de computação.
· Realização dos Experimentos e Análise Estatística dos Resultados
 A realização dos experimentos será explicada detalhadamente nos itens seguintes.
 Os resultados de um exercício de simulação compõem, normalmente, uma distribuição de valores que deve ser analisada, através da utilização de técnicas estatísticas, com o objetivo de se estimar o desempenho esperado do sistema e suas possíveis variações, obtendo-se com isto uma estimativa do risco envolvido na operação.
5. Exemplo de modelagem para simulação
 Vamos analisar dois problemas que exemplificam a técnica de modelagem para a simulação. 
 Não existem regras que possam definir a construção de modelos de uma forma inequívoca, e essa operação é muito facilitada pelo conhecimento específico do problema focalizado. Nos exemplos apresentados, vamos representar a operação dos sistemas através de fluxogramas dos processos.
 O objetivo da elaboração de fluxograma de processos é a representação da lógica de operação dos sistemas, procurando-se captar todas as relações com o ambiente externo, as interações entre as diversas variáveis e a evolução cronológica dos eventos. Essa é, sem dúvida alguma, a parte mais difícil da construção dos modelos. Os fluxogramas formam a base da construção do modelo computacional.
6. Método de Monte Carlo
 O método de Monte Carlo é um processo de operar modelos estatísticos de forma a lidar experimentalmente com variáveis descritas por funções probabilísticas. Por exemplo, no modelo anterior de planejamento e controle de estoque, a demanda e o prazo de entrega são descritos por funções de probabilidades. Como o tratamento analítico desse modelo é muito trabalhoso, pode-se usar o método de Monte Carlo para analisar experimentalmente os efeitos conjuntos das duas variáveis aleatórias no sistema.
· Conceito Fundamental
O método de Monte Carlo baseia-se num conceito estatístico simples.
Seja x uma variável aleatona com as seguintes características:
· função de distribuição de probabilidades: f(x),
· função cumulativa de probabilidades: F(x).
Se definirmos uma nova variável aleatória y = F(x), esta tem uma distribuição uniforme sobre o intervalo fechado (0,1).
Assim, como a função cumulativa de probabilidades representa as características aleatórias da variável em questão, a função
 y = F(x)
é uma relação entre duas variáveis:
· variável x, com distribuição aleatória própria
· vcariável y, com distribuição uniforme , entre O e 1.
7. Números aleatórios
 Um dos elementos necessários à aplicação do método de Monte Carlo é um gerador de números aleatórios. Isto pode ser conseguido de três formas: 
· Uso de urna tabela de números aleatórios, 
· Usar rotinas ou programas já implantadas em computadores digitais.
· Utilizar um método aritmético para calcular uma seqüência de números aleatórios, a partir de uma equação recursiva. 
. Softwares para simulação . 
Eduardo Saliby 
 A crescente popularidade de uso da simulação como ferramenta de modelagem e análise de problemas resultou em uma vasta e também crescente disponibilidade de softwares de simulação no mercado. Como estes softwares normalmente representam dispêndios consideráveis para as empresas que adquirem uma licença de uso, sua seleção adequada passa a ser um dos fatores chave no sucesso dos projetos de simulação (e do emprego da equipe responsável!) a serem futuramente desenvolvidos. Assim sendo, esta seleção deverá ser feita cada vez mais com base em critérios objetivos, levando em conta não apenas as características dos produtos mas também das aplicações que se pretende desenvolver. Como em qualquer situação de decisão complexa, informação é um fator chave, sendo este o principal objetivo do presente trabalho: fornecer informações básicas sobre estes produtos e, mais importante ainda, contribuir para um processo de busca de informações mais eficiente.
 Nosso interesse principal são os softwares de simulação a eventos discretos. No entanto, dependendo da aplicação, não se deve desconsiderar a possibilidade de uso de planilhas eletrônicas (EXCEL® e outros) e produtos acessórios (como o @RISK da Palisade Corporation), especialmente no caso de situações mais simples em que a variável tempo não é relevante (as chamadas "one-shot simulations") ou situações em que relógio pode ser modificado a intervalos constantes. Além disso, cabe também uma menção aos softwares de apoio estatístico à simulação, tais como os que servem para identificar distribuições de probabilidade para os dados de entrada (Ex: BestFit e ExpertFit) ou voltados para uma melhor análise de resultados e experimentação.
 Hoje, com um micro Pentium, numa configuração padrão (32Mb de RAM), já dispomos de uma máquina capaz de processar aplicações bastante complexas e antes inimagináveis. No entanto, o software passou a representar um fator crucial no uso da simulação. Assim, embora se disponha atualmente de bons produtos no mercado, a sua maior sofisticação, aliada a um custo cada vez mais elevado, tornou a escolha do software de simulação uma difícil decisão. Anteriormente, a dificuldade que residia num número reduzido de opções: Linguagens Gerais de Programação (FORTRAN, Pascal,…), ou às poucas Linguagens Específicas para Simulação (GPSS, SIMULA, GASP, SLAM) transferiu-se hoje para uma difícil e por vezes cara escolha dentre um elevado número de produtos e um permanente esforço de atualização em relação a estes produtos. 
Softwares de simulação de caráter geral
 Podemos dividir em duas grandes categorias os softwares de simulação hoje disponíveis: 
 De natureza geral (aqui focalizados);
 Voltados para aplicações específicas, tais como manufatura, serviços, telecomunicações, reengenharia e outros. 
 Os softwares de caráter geral são, naturalmente, os mais conhecidos. Com a certeza de estarmos (não intencionalmente!) omitindo vários destes produtos, apresentamos no quadro abaixo uma lista (em ordem alfabética) dos principais softwares, empresa responsável, endereço da Homepage (quando disponível) e a informação que dispomos a respeito da existência de representante no Brasil. Em sua grande maioria, as empresas citadas são especializadas em simulação, oferecendo também outros produtos - tais como simuladores voltados para aplicações específicas, derivadosdo software de caráter geral - e serviços - tais como consultoria e treinamento. Quase todos estes softwares têm demos disponíveis, seja através de contato direto com a empresa, seu representante, via internet (cuidado que, em geral, são arquivos pesados!). De qualquer forma, uma maneira prática e rápida para se saber mais sobre cada um destes produtos, é visitando as respectivas Homepages e "sites" relacionados.
	PRIVATE
Produto
	Empresa
	Endereço da HomePage
	Representante
	ARENA
	Systems Modeling Corporation
	www.sm.com
	Sim
	AutoMod
	Autosimulations
	www.autosim.com
	Sim
	Extend
	Imagine That
	www.imaginethatinc.com
	Não
	GPSS H
	Wolverine Software
	ND*
	Sim
	Micro Saint
	Micro Analysis & Design
	www.madboulder.com
	Sim
	ProModel
	ProModel Corporation
	www.promodel.com
	Sim
	SIMPLE ++
	AESOP (Alemanha)
	www.aesop.de
	ND*
	Simscript II.5 e MODSIM III
	CACI Products Company
	www.caciasl.com
	ND*
	TAYLOR IIb
	F&H Simulations (Holanda)
	www.taylorii.com
	ND*
	VisSim
	Visual Solutions
	www.vissim.com
	Sim
*ND - Não disponível
 A crescente popularidade de uso da simulação como ferramenta de modelagem e análise de problemas resultou em uma vasta e também crescente disponibilidade de softwares de simulação no mercado. Como estes softwares normalmente representam dispêndios consideráveis para as empresas que adquirem uma licença de uso, sua seleção adequada passa a ser um dos fatores chave no sucesso dos projetos de simulação (e do emprego da equipe responsável!) a serem futuramente desenvolvidos. Assim sendo, esta seleção deverá ser feita cada vez mais com base em critérios objetivos, levando em conta não apenas as características dos produtos mas também das aplicações que se pretende desenvolver. Como em qualquer situação de decisão complexa, informação é um fator chave, sendo este o principal objetivo do presente trabalho: fornecer informações básicas sobre estes produtos e, mais importante ainda, contribuir para um processo de busca de informações mais eficiente.
 Nosso interesse principal são os softwares de simulação a eventos discretos. No entanto, dependendo da aplicação, não se deve desconsiderar a possibilidade de uso de planilhas eletrônicas (EXCEL® e outros) e produtos acessórios (como o @RISK da Palisade Corporation), especialmente no caso de situações mais simples em que a variável tempo não é relevante (as chamadas "one-shot simulations") ou situações em que relógio pode ser modificado a intervalos constantes. Além disso, cabe também uma menção aos softwares de apoio estatístico à simulação, tais como os que servem para identificar distribuições de probabilidade para os dados de entrada (Ex: BestFit e ExpertFit) ou voltados para uma melhor análise de resultados e experimentação.
 Hoje, com um micro Pentium, numa configuração padrão (32Mb de RAM), já dispomos de uma máquina capaz de processar aplicações bastante complexas e antes inimagináveis. No entanto, o software passou a representar um fator crucial no uso da simulação. Assim, embora se disponha atualmente de bons produtos no mercado, a sua maior sofisticação, aliada a um custo cada vez mais elevado, tornou a escolha do software de simulação uma difícil decisão. Anteriormente, a dificuldade que residia num número reduzido de opções: Linguagens Gerais de Programação (FORTRAN, Pascal,…), ou às poucas Linguagens Específicas para Simulação (GPSS, SIMULA, GASP, SLAM) transferiu-se hoje para uma difícil e por vezes cara escolha dentre um elevado número de produtos e um permanente esforço de atualização em relação a estes produtos. 
Características gerais dos produtos
 Algumas características marcantes são comuns à maioria dos produtos que disputam este rico mercado. Dentre elas citamos a busca de um ambiente de trabalho que seja o mais amigável possível, de preferência um aplicativo Windows, com facilidades para a modelagem, depuração, visualização da execução, análise estatística de resultados e geração de relatórios.
 Mas, sem dúvida, a característica de maior apelo comercial são os recursos de animação. Estes, vão desde simples implementações com símbolos gráficos (círculos, quadrados, etc..) piscando na tela e mostrando valores numéricos que descrevem o estado do sistema (tamanho de filas, por exemplo), até sofisticados recursos de animação 3-D que, obviamente, demandam elevado esforço computacional e encarecem o produto. Nossa atitude em relação a esta tendência é um pouco conservadora: a partir de um certo nível de sofisticação da animação, vemos poucas vantagens adicionais para um estudo de simulação, inclusive com o risco de se desviar a atenção da lógica do modelo à sua visualização. Mas, também, reconhecemos o poder sedutor de uma saída animada, de tal forma que uma solução de compromisso entre os dois extremos (nenhuma animação ou animação sofisticada) nos parece a melhor alternativa.
 Ainda com relação aos sistemas de animação, enquanto a maioria dos sistemas (Ex: Arena, ProModel, Automod, Taylor) permitem a visualização da simulação em "tempo real", ou seja, enquanto ela roda, outra opção é o uso de um animador "off-line" como é o caso do PROOF Animation da Wolverine (a mesma empresa que produz o GPSS/H, uma nova versão do velho GPSS). No caso do PROOF, o programa animador lê os dados de um arquivo texto (trace file), gerado por uma rodada de simulação anterior, e, com base nestes dados mais um arquivo de lay-out, possibilita uma visualização animada da simulação. Esta opção se aplica ao GPSS, mas também pode ser utilizada com outros softwares, tais como o SIMUL (Saliby, 1996); para isso, basta a simulação gerar o arquivo texto (trace file) no formato requerido pelo PROOF.
 Outra característica marcante destes novos produtos, e nisso eles são mais parecidos entre si, diz respeito à etapa de modelagem/programação. Neste caso, dispõe-se geralmente de uma vasta biblioteca de blocos de modelagem/programação que são selecionados via menu, posicionados e conectados via mouse ("drag and drop"). Cabe ainda ao usuário preencher os dados adicionais necessários, em janelas associadas a cada um destes blocos. Mas, não se animem! Numa aplicação real, o usuário sempre terá alguma programação a fazer, ao contrário do que os vendedores de software geralmente afirmam! E aí, podem surgir dificuldades práticas, pois o usuário poderá ser obrigado a decifrar um código de simulação gerado na linguagem específica do aplicativo e saber como fazer as alterações necessárias. Em geral, esta intervenção requer um grau de conhecimento do software que vai muito além do conhecimento dos blocos básicos de modelagem/programação. 
Algumas Sugestões
Jerry Banks (1997), um dos autores que mais têm escrito sobre o assunto, forneceu uma lista de fatores a serem considerados na seleção de um software de simulação, fatores estes descritos cada um deles por um conjunto de características. Um resumo destes fatores se segue:
Entrada (Input):
Recurso de apontar mouse e clicar;
Utilização de desenhos CAD;
Importação de arquivos;
Exportação de arquivos;
Sintaxe comprensível;
Controle interativo de execução;
Interface com outra linguagem;
Recurso para análise de dados de entrada.
Processamento:
Possibilidade de modelagem complexa (Powerful constructs);
Velocidade;
Flexibilidade de execução de corridas;
Geração de valores aleatórios;
Reinicialização de estatísticas e geradores (Reset);
Replicações independentes;
Variáveis globais e de atributo;
Programação: flexibilidade lógica;
Portabilidade
Saída (Output):
Relatórios padronizados;
Relatórios personalizados ("customizados");
Geração de gráficos;
Manutenção de bancos de dados;
Coleta do resultado de expressões matemáticas;
Medidas de desempenho específicas da aplicação ("customizadas");
Saída em arquivos.
Ambiente:
Facilidade de uso;
Facilidade de aprendizado;
Qualidade da documentação;
Recursos de animação;
Versão "Run Time".
Fornecedor do software:
Estabilidade;
História;
"Track record";
Suporte.
Custo:
Aquisição de licença;
Atualizações;
Treinamentoe suporte. 
Outros autores fornecem sugestões adicionais, merecendo destaque os seguintes fatores:
Uso de templates para modelagem mais rápida;
Uso do conceito de programação orientada a objetos;
Interface com outras ferramentas de software (CAD, planilhas, …)
Recursos de otimização experimental;
Aplicações Internet;
Controle em tempo real. 
Conclusão
Então, o que fazer para se escolher um destes produtos?
 Nossa sugestão é óbvia: informe-se o melhor possível! Hoje, com a Internet, tudo fica mais fácil, desde a consulta ao fabricante de software até o contato com grupos de interessados. Um esforço neste sentido é a realização periódica de encontros ou Workshops de simulação, reunindo a comunidade interessada. 
Bibliografia
· Ermes Medeiros da Silva, Elio Medeiros da Silva, Valter Gonçalves, Afrânio Carlos Murolo ; Pesquisa Operacional: Programação Linear / Simulação ; 3a Edição ; Editora Atlas ; 1998 .
· Claudio Loesch, Nelson Hein ; Pesquisa Operacional: Fundamentos e Modelos ; Editora da FURB ; 1999.
· Eduardo Leopoldino de Andrade ; Introdução à Pesquisa Operacional: Métodos e Modelos para a Análise de Decisão ; 2a Edição ; Editora LTC ; 1998.
· www.cel.coppead.ufrj.com.br 
Índice
· Introdução à Pesquisa Operacional , 01
· Técnicas de Pesquisa Operacional , 02
· Teoria da Localização , 05 
· Método do Transporte , 08
· Método Simplex , 14
· Programação Dinâmica , 23
· Designação , 30
· Programação Mista / Inteiros , 34
· Teoria das Filas , 40
· Simulação de Monte Carlo , 46
· Softwares de Simulação , 51
· Bibliografia , 56
(0,25)
 i
 j
Decisão k
c( n,i,j ) 
Estágio n
Estágio n+1 
1
1
1
10
2
2
2
1
3
3
3
País 1
País 2
País 3
 País 4 
(destino)
País 0
(origem)
Definição do problema
 Construção do modelo
 Solução do modelo
 Avaliação
 Validação do modelo
 Experiência
Implementação dos resultados
Vétice da soução ótima x1* = 2,75 e x2* = 2.25
X1
X2
X2
x1
S0
X2
X1
S1
S2
S0
x1 = 2,75
x2 = 2,25
Z = 7,75
S2
x1 = 3
x2 = 1,5
Z = 7,5
S1
x1 = 2
x2 = 2
Z = 5
x1 ( 3
x1 ( 2
x1 ( 1
x1 ( 2
S3
x1= 3,167
x2 = 1
Z = 7,333
S4 = (
Solução impossível
S2
x1 = 3
x2 = 1,5
Z = 7,5
x1 ( 3
x1 ( 4
S5
x1 = 3
x2 = 1
Z = 7
S6 = (
 Solução impossível
S3
x1= 3,167
x2 = 1
Z = 7,333
x1 ( n
x1 ( n+1
Sr
......
xi = n 
Zr
Sr+1
......
xi = n+1
Zr+1
Sk
......
xi
Zk
� EMBED MSPhotoEd.3 ���
� EMBED MSPhotoEd.3 ���
PAGE 
14
_1042479077.bin
_1042479344.bin