Material de Pesquisa Operacional - FGV 2011.2 - Resumo

Prévia do material em texto

Conteúdo Resumido de
Métodos Quantitativos
Conteúdo da Seção 1
Introdução a modelagem matemática;
Utilização de planilhas eletrônicas em administração.
Abordagem de Management Science
no processo de tomada de decisão
Management Sciences
– 	Área de estudo que utiliza computadores, estatística e matemática para resolver problemas de negócios.
Três objetivos inter-relacionados:
– 	Converter dados em informações significativas.
Transformar dados brutos (números e fatos) em dados, através de seu armazenamento de forma organizada. Os Sistemas de Informações Gerenciais (SIG) serão responsáveis pela transformação destes dados em Informações Gerenciais que podem ser utilizadas no processo de tomada de decisão através dos Siste-mas de Apoio à Decisão. 
– 	Apoiar a tomada de decisão transferíveis e independentes.
Através dos Sistemas de Apoio à Decisão, dar suporte às decisões para que estas sejam independentes do decisor e assegurar que o processo de tomada de decisão seja claro e transparente.
– 	Criar sistemas úteis para usuários não técnicos.
Facilitar, através de sistemas de fácil utilização, os processos de tomada de decisão operacional, gerencial e estratégico.
Abordagem de Management Science
no processo de tomada de decisão
Modelo de Computador
Modelo de Computador é um conjunto de relações matemáticas e hipóteses lógicas implementadas em computador como uma representação de um problema real de tomada de decisão.
Durante a última década foi observado que uma das maneiras mais efetivas de se resolver problemas de negócios consiste na utilização de modelos de computador baseados em planilhas eletrônicas.
Processo de Modelagem
Características:
Força os decisores a tornarem explícitos seus objetivos.
Força a identificação e armazenamento das diferentes decisões que influenciam os objetivos.
Força a identificação e armazenamento dos relacionamentos entre as decisões.
Força a identificação das variáveis a serem incluídas e em que termos elas serão quantificáveis.
Força o reconhecimento de limitações.
Permitem a comunicação de suas ideias e seu entendimento para facilitar o trabalho de grupo.
Realismo
– Um modelo só tem valor se o seu uso provoca melhores decisões.
Intuição
– Modelos quantitativos e intuição gerencial não se encontram em lados opostos.
– Intuição é crucial durante a interpretação e implementação.
Modelos Simbólicos (Características)
Um modelo sempre simplifica a realidade.
Um modelo simbólico deve conter detalhes suficientes para que:
– 	Os resultados atinjam suas necessidades.
– 	O modelo seja consistente com os dados.
– 	O modelo possa ser analisado no período de tempo disponível a sua concepção.
Modelos de Tomada de Decisão
São modelos simbólicos nos quais algumas variáveis representam decisões que devem ser tomadas.
Modelos Determinísticos
– São modelos nos quais todas as variáveis relevantes são assumidas como certas e disponíveis.
Modelos Probabilísticos ou Estocásticos
– São modelos nos quais uma ou mais variáveis não são conhecidas com certeza.
Tipos de Modelagem
Modelagem Dedutiva
– Hipóteses das variáveis relevantes e suas interligações
– Modelagem de cima para baixo, maior peso no conhecimento do modelador a respeito das variáveis e parâmetros.
Modelagem Inferencial
– Análise dos dados para estabelecimento das relações entre variável.
– Modelagem de baixo para cima.
Tipos de Modelagem (Esquema)
Modelo Caixa Preta e Diagrama de Blocos
– São instrumentos úteis na organização do problema e trazem o benefício de ajudar o início da documentação do modelo.
– Apesar de não resolverem o problema final, estas ferramentas auxiliam sobremaneira o entendimento da complexidade do modelo e a identificação das variáveis importantes.
Modelo Caixa Preta
– Para confeccioná-la, criamos uma caixa chamada "modelo" e listamos ao seu lado esquerdo, representando as variáveis e os parâmetros de entrada, todos os fatores cruciais para a concretização do resultado final, o qual é apresentado ao lado direito da caixa, como saída do modelo.
Exemplo:
– Seja a empresa pastéis e pastelões Ltda.
Variável de decisão: preço de venda do pastel.
Parâmetros: o preço médio praticado pela concorrência, os custos de matéria-prima, os custos de processamento e os custos fixos.
Diagrama de Blocos
Diagramas de Blocos são úteis na organização do modelo e trazem o benefício de ajudar o início da documentação do modelo.
Um diagrama de blocos mostra as relações entre as diversas variáveis do modelo, isto é, mostra como a partir das variáveis exógenas e dos parâmetros, chegamos até as variáveis de medida de performance.
Exemplo: no caso da empresa pastéis e pastelões Ltda.
Análise de Ponto de Equilíbrio
Muitas vezes desejamos descobrir qual a quantidade mínima que devemos produzir para viabilizarmos a produção de um produto.
Este estudo se chama ponto de equilíbrio e se baseia nas equações de Receita e Custos de um determinado produto.
Análise de Ponto de Equilíbrio (Diagrama de Blocos)
Caso LCL impressoras Ltda.
A LCL Impressoras Pessoais, líder na produção de impressoras no Brasil, espera lançar um novo tipo de impressora laser colorida de baixo custo. Para tal, fez uma pesquisa junto aos consumidores potenciais para determinar a demanda que teria para cada tipo de preço. Ao mesmo tempo fez um levantamento dos custos fixos e variáveis para junto com o preço determinar uma curva de oferta. 
Com as informações apresentadas abaixo, determine o preço e a quantidade de equilíbrio. 
Equação de Receita
Equação de Custo Total
Ponto de Equilíbrio
Atingir Meta – Excel 
Ponto de Equilíbrio – Excel 
Lucro = 0 para que quantidade?
Para
 569 unid.
Conteúdo da Seção 2
Problemas de programação linear:
– Resolução pelo método gráfico;
– O Problema do Artesão;
– Minimização;
– Restrições Redundantes;
– Solução Múltipla, limitada e inviável.
Problemas de otimização
Em problemas reais de otimização busca-se maximizar ou minimizar uma quantidade específica, chamada objetivo, que depende de um número finito de variáveis de entrada.
As variáveis de entrada podem ser:
– Independentes uma das outras.
– Relacionadas uma com as outras por meio de uma ou mais restrições.
Programação Matemática
Um problema de programação matemática é um problema de otimização no qual o objetivo e as restrições são expressos como funções matemáticas e relações funcionais.
Variáveis de Decisão
X1, X2, ..., Xn, são as chamadas variáveis de decisão.
As variáveis de decisão são valores que podemos escolher livremente (variáveis independentes).
As variáveis de decisão representam as opções que um administrador tem para atingir um objetivo.
– Quanto produzir para maximizar o lucro?
– Quanto comprar de uma ação para minimizar o risco da carteira? 
Programação Linear
Um problema de programação matemática é linear se a função objetivo f(x1, x2, ..., xn) e cada uma das funções que representam as restrições forem lineares, isto é, na forma abaixo:
e
Quebrando a linearidade
A presença de qualquer das expressões abaixo tornam o problema não linear.
Exemplos:
–
–
–
Programação Linear (Exemplos)
Programação Linear (Áreas de Aplicação)
Administração da Produção.
Análise de Investimentos.
Alocação de Recursos Limitados.
Planejamento Regional.
– Logística (Custo de transporte; Localização de rede de distribuição)
Programação Linear (Hipótese de Aditividade)
Considera as atividades (variáveis de decisão) do modelo como entidades totalmente independentes, não permitindo que haja interdependência entre as mesmas, isto é, não permitindo a existência de termos cruzados, tanto na função-objetivo como nas restrições.
Esta é a própria hipótese de linearidade do PPL (problema de programação linear).Programação Linear (Hipótese de Proporcionalidade)
O valor da função-objetivo é proporcional ao nível de atividade de cada variável de decisão, isto é, o valor da função-objetivo se altera de um valor constante dada uma variação constante da variável de decisão.
Programação Linear (Hipótese de Divisibilidade)
Assume que qualquer variável de decisão pode assumir qualquer valor positivo fracionário.
Esta hipótese pode ser quebrada, dando origem a um problema especial de programação linear, chamado de problema inteiro.
Programação Linear (Hipótese de Certeza)
Assume que todos os parâmetros do modelo são constantes conhecidas. Em problemas reais a certeza quase nunca é satisfeita, provocando a necessidade de análise de sensibilidade dos resultados.
Programação Linear (Terminologia)
No campo da Programação Linear, solução é qualquer especificação de valores para as variáveis de decisão, não importando se esta se trata de uma escolha desejável ou permissível.
Classificação das Soluções
Solução Viável
É uma solução em que todas as restrições são satisfeitas;
Solução Inviável
É uma solução em que alguma das restrições ou as condições de não-negatividade não são atendidas;
Exemplos de Solução Viável e Inviável
Valor da Função-Objetivo
É especialmente importante verificar como fica o valor da função-objetivo (Z) nas soluções viáveis que podemos determinar:
A Solução Ótima
A Solução Ótima é uma solução viável especial.
Dentre todas as soluções viáveis, aquela(s) que produzir(em) o valor da função-objetivo otimizado é chamada de ótima;
A grande questão é como determinar a solução ótima.
Programação Linear – Solução Gráfica
Quando o problema envolve apenas duas variáveis de decisão, a solução ótima de um problema de programação linear pode ser encontrada graficamente.
x1 + x2 ≤ 7
x1 + x2 = 7 reta limite
x1 + x2 ≤ 7 região abaixo da reta limite
Programação Linear – Solução Gráfica (Exercício)
Considere o seguinte problema de LP (Linear Programming).
Solução:
Programação Linear – Restrições Redundantes
Uma restrição é dita redundante quando a sua exclusão do conjunto de restrições de um problema não altera o conjunto de soluções viáveis deste.
É uma restrição que não participa como uma aresta (limitador) do conjunto de soluções viáveis.
Exemplo: resolva o seguinte problema.
Solução:
Exercício de Aplicação – O Problema do Artesão
Um artesão faz colares e brincos para vender num bazar que acontece todos os dias. Ele os vende por R$ 10,00 e R$ 5,00, respectivamente. Ele nunca conseguiu vender mais de 10 colares e 8 brincos por dia. Um colar é feito em 20 minutos enquanto um brinco é feito em 40 minutos. O artesão trabalha 4 horas por dia antes de ir para o bazar. Quantos colares e quantos brincos ele deve produzir para maximizar a sua receita diária?
Questões levantadas:
Quem deve tomar a decisão?
O artesão.
O que o decisor deve decidir?
Quantos colares e brincos deve produzir por dia.
Com que objetivo ele deve tomar a decisão?
Maximizar sua receita.
Com que restrições a decisão será tomada?
Tempo para produção
Demanda dos consumidores (colares/brincos) 
A decisão do artesão:
Precisamos traduzir a decisão do Artesão em um modelo de programação linear para resolvê-lo;
Chamemos de x1 e x2 as quantidades de colares e brincos que ele faz por dia, respectivamente.
O Objetivo do Artesão é maximizar sua receita.
O modelo para a decisão do artesão:
Função-objetivo
– Maximizar a receita		Max Receita = 10x1 + 5x2
Restrições
– Demanda de Colares		x1 10
– Demanda de Brincos		x2 8
– Tempo Padrão			20x1 + 40x2 240
– Não Negatividade			x1, x2 0
Problemas de Minimização
O processo de resolução gráfica de um problema de minimização é análogo ao de maximização, isto é:
Utiliza as restrições para determinar o conjunto de soluções viáveis.
Utiliza a função-objetivo para determinar a solução ótima.
A diferença é que a solução ótima levará a função-objetivo ao menor valor possível.
Exemplo:
Encontre a solução ótima de:
Solução Gráfica:
Soluções Múltiplas
Até agora todos os problemas apresentaram apenas uma única solução ótima, isto é, apenas uma solução viável levava a função-objetivo ao seu valor ótimo.
Existem problemas em que uma ou mais soluções viáveis nos levam ao mesmo valor ótimo, isto é, existem soluções múltiplas.
O problema do artesão – modificado
Um artesão faz colares e brincos para vender num bazar que acontece todos os dias. Ele os vende por R$ 10,00 e R$ 5,00, respectivamente. Ele nunca conseguiu vender mais de 10 colares e 8 brincos por dia. Um colar é feito em 20 minutos enquanto um brinco é feito em 40 minutos. O artesão trabalha 4 horas por dia antes de ir para o bazar. Quantos colares e quantos brincos ele deve produzir para atingir uma receita diária de R$ 50,00?
Questões levantadas:
Quem deve tomar a decisão?
– O artesão.
O que o decisor deve decidir?
– Quantos colares e brincos deve produzir por dia.
Com que objetivo ele deve tomar a decisão?
– Atingir a receita mínima.
Com que restrições a decisão será tomada?
– Tempo para produção.
– Demanda dos consumidores (colares/brincos).
– Receita mínima.
A decisão do artesão:
Precisamos traduzir a decisão do Artesão em um modelo de programação linear para resolvê-lo;
Chamemos de x1 e x2 as quantidades de colares e brincos que ele faz por dia, respectivamente.
O Objetivo do Artesão é atingir a receita mínima.
O modelo para a decisão do artesão:
Função-objetivo
– Minimizar a receita		Min Receita = 10x1 + 5x2
Restrições
– Demanda de Colares		x1 10
– Demanda de Brincos		x2 8
– Tempo Padrão			20x1 + 40x2 240
– Receita Mínima			10x1 + 5x2 50
– Não Negatividade			x1, x2 0
Soluções Ilimitadas
Um problema de programação linear apresenta soluções ilimitadas quando uma das variáveis não tem nenhuma restrição de crescimento ou decrescimento e este fato causa que a função-objetivo não tenha valor ótimo que possa ser identificado.
Exemplo: 
Encontre a solução ótima:
Solução Inviável
Um problema de programação linear é dito inviável quando o conjunto de soluções viáveis é vazio.
Considere o problema
Solução Gráfica
Programação Linear e Convexidade
Conjunto Convexo em R2
– Para quaisquer dois pontos do conjunto, todos os pontos que formam o segmento de reta que os unem fazem parte do conjunto.
Método Simplex – Teoremas Fundamentais
Teorema I
– O conjunto de todas as soluções viáveis de um modelo de Programação Linear formam um conjunto convexo.
Teorema II
– Toda solução compatível básica, do sistema de equações lineares de um modelo de programação linear, é um ponto extremo do conjunto de soluções viáveis, isto é, do conjunto convexo de soluções.
Exemplo:
Considere o problema e sua solução gráfica.
Nos pontos extremos temos os seguintes valores para Z
Teorema III
– Se a função-objetivo possui um ótimo finito, então pelo menos uma solução ótima é um ponto extremo do conjunto convexo de soluções viáveis.
Teorema IV
– Se a função-objetivo assume o ótimo em mais de um ponto extremo do conjunto de soluções viáveis, então ela toma o mesmo valor para qualquer ponto do segmento da reta que une esses pontos extremos.
Verificação Geométrica do Teorema III
O valor da função-objetivo varia quando esta se desloca. Logo, o valor ótimo (mínimo ou máximo) será obtido deslocando-se o máximo ou o mínimo na função-objetivo.
Verificação Geométrica do Teorema IV
Entretanto, a função-objetivo pode assumir uma inclinação tal que no ponto ótimo ela coincida com a inclinação de alguma restrição.
Método Simplex – Teoremas Fundamentais
Considere a solução gráfica do problema.
Exercícios Propostos
Livro Texto 1
– Exercícios 1 a 10, Cap. 2.1, pp. 24-25.
– Exercícios 1 a 10,Cap. 2.3, pp. 34-36.
Conteúdo da Seção 3
Resolver problemas usando Solver do Excel:
– Definindo o modelo no Solver
– Obtendo a solução
Resolvendo Problemas
Usando Microcomputador
Usaremos softwares genéricos e específicos para resolver problemas de Programação Linear
– Solver do Excel® 
– LINGO® e What’s Best® (encartados na 4ª edição do livro texto)
Para resolver problemas de otimização utilizando o solver do Excel devemos designar células para representarem:
As variáveis de decisão
A função-objetivo
Os lados esquerdos das restrições (LHS)
Os lados direitos das restrições (RHS)Usando Solver do Excel
Designação de Células
Exemplo:
Considere o Problema
Usando Solver do Excel
Entrando os Parâmetros do Modelo
Célula do Valor Ótimo
Definindo o Lado
Esquerdo das Restrições (LHS)
Usando Solver do Excel – Iniciando o Solver
Definindo a Célula de Destino
Definindo as Restrições
Definindo Condições de Não Negatividade
Usando Solver do Excel – Verificando a Resposta
Solver do Excel – Relatório de Resposta
Solver do Excel – Relatório de Sensibilidade
Solver do Excel – Relatório de Limites
Exercício Proposto
Resolva o problema usando o solver do Excel
Solução: Resolvendo Problemas
Usando Solver do Excel – Modelo
Obtendo a solução – Solver 
Exercício Proposto
Livro Básico 1: Exercícios 3.1, 1 a 10, pp. 59-60
Livro Básico 2: Exercícios de Revisão, 1 – 34, pp. 129 – 131
Conteúdo da Seção 4
Aplicações no Mundo Real
– Caso LCL Liquidificadores Ltda.
– Caso LCL Previdência Privada.
– Caso LCL Shopping Ltda.
– Caso LCL Trading Ltda.
– Caso LCL Supermercados Ltda.
Caso LCL Liquidificadores Ltda. 
A LCL Liquidificadores Ltda. recebeu recentemente R$ 850.000,00 em pedidos de seus três modelos. Cada liquidificador necessita de um determinado número de horas de trabalho nos setores de montagem, teste e empacotamento. A LCL pode terceirizar, tanto a montagem como o teste, de parte ou a totalidade de sua produção. A tabela a seguir resume essas informações necessárias para resolver o problema da necessidade de terceirização.
Variáveis de Decisão
– P1 – Nº liquidificadores do modelo 1 produzidos pelo LCL.
– P2 – Nº liquidificadores do modelo 2 produzidos pelo LCL.
– P3 – Nº liquidificadores do modelo 3 produzidos pelo LCL.
– T1 – Nº liquidificadores do modelo 1 terceirizados pelo LCL.
– T2 – Nº liquidificadores do modelo 2 terceirizados pelo LCL.
– T3 – Nº liquidificadores do modelo 3 terceirizados pelo LCL.
Função-objetivo: Min 40P1 + 80P2 + 110P3 + 60T1 + 90T2 + 140T3
Restrições de Produção
P1 + 2P2 + 0,5P3 6000 (montagem)
P1 + P2 + P3 5000 (teste)
2,5P1 + 2,5T1 + P2 + T2 + 4P3 + 4T3 15000 (empacotamento) 
Restrições de Demanda
P1 + T1 = 2000 (liquidificador do tipo 1)
P2 + T2 = 2000 (liquidificador do tipo 2)
P3 + T3 = 1500 (liquidificador do tipo 3)
O Modelo
Min Z = 40P1 + 80P2 + 110P3 + 60T1 + 90T2 + 140T3
s.r.	1P1 + 2P2 + 0,5P3 6000
	1P1 + 1P2 + 1P3 5000
	2,5P1 + 2,5T1 + P2 + T2 + 4P3 + 4T3 15000
	P1 + T1 = 2000
	P2 + T2 = 2000
	P3 + T3 = 1500
	P1; P2; P3; T1; T2; T3 0
Parâmetros do Solver
Resposta
Caso LCL Previdência Privada S.A.
A LCL Investimentos S.A., gerencia recursos de terceiros através da escolha de carteiras de investimento para diversos clientes, baseados em bonds de diversas empresas. Um de seus clientes exige que:
– Não mais de 25% do total seja aplicado em um único investimento.
– Mais de 50% do total deve ser aplicado em títulos de Bancos.
– O total aplicado em títulos de telefonia deve ser no máximo de 30% do total investido.
A tabela a seguir mostra os dados dos títulos selecionados
Variáveis de Decisão
– B1 – Percentual do total aplicado no Banco 1.
– B2 – Percentual do total aplicado no Banco 2.
– B3 – Percentual do total aplicado no Banco 3.
– T1 – Percentual do total aplicado no Telcom 1.
– T2 – Percentual do total aplicado no Telcom 2.
– T3 – Percentual do total aplicado no Telcom 3.
Função-Objetivo
Restrição de Orçamento: B1 + B2 + B3 + T1 + T2 + T3 = 100
Restrições de Máximo de Aplicação por Tipo de Título
B1 25 B2 25 B3 25
T1 25 T2 25 T3 25
Restrições de Mínimo de Aplicação em Título de Bancos: 
B1 + B2 + B3 50
Restrições de Máximo de Aplicação em Título de Telecomunicação: 
T1 + T2 + T3 30
Parâmetros do Solver
Resposta
Caso LCL Shopping Ltda.
A LCL Shopping Ltda, deseja estabelecer o número de seguranças de horário integral que deve contratar para iniciar suas atividades. Para fazê-lo, recebeu uma estimativa com o mínimo seguranças por dia da semana. O sindicato dos seguranças mantém um acordo trabalhista que determina que cada empregado deve trabalhar três dias consecutivos por semana e que os shopping devem ter apenas empregados em regime de horário integral (24hs). Sabendo-se que o shopping só abrirá de 2ª à sábado. Formule o problema de maneira a resolver o problema.
Dados
Variáveis de decisão
– N2 – nº de funcionários que iniciam atividades na 2ª feira.
– N3 – nº de funcionários que iniciam atividades na 3ª feira.
– N4 – nº de funcionários que iniciam atividades na 4ª feira.
– N5 – nº de funcionários que iniciam atividades na 5ª feira.
Função Objetivo
Min Z = N2 + N3 + N4 + N5
Restrições de Nº Mínimo de Empregados
N2 10 ; N2 + N3 12
N2 + N3 + N4 13 ; N3 + N4 + N5 14
N4 + N5 16 ; N5 17
Parâmetros do Solver
Resultado
Caso LCL Trading Ltda.
A LCL Trading Ltda. Possui 1 armazém com capacidade de armazenamento de 300.000 toneladas de grãos. No início do mês de janeiro a LCL tinha 17.000 toneladas de grãos de trigo armazenadas. Considerando que em cada mês você pode comprar ou vender trigo a preços pré-fixados pelo governo (tabela a seguir), em qualquer quantidade desejada, desde que sujeitas as restrições de armazenagem e o estoque inicial do mês (vendas máximas no mêsi = saldo mês(i-1). Formule o problema de maneira a maximizar o lucro da operação nos seis próximos meses.
Variáveis de Decisão
– QCi – Quantidade de Grãos Comprados no mês i
– QVi – Quantidade de Grãos Vendidos no mês i
Variáveis Auxiliares
– SFi – Saldo Final no mês i
– SF0 – Saldo Final em Dezembro anterior = 17000 ton.
Função Objetivo
Restrições Auxiliares de Saldo Armazenado
SFi = SFi-1 + QCi – QVi para i = 1, ..., 6 
Restrições de Armazenagem
SFi 300.000 para i = 1, ..., 6 
Restrições de Quantidade Vendida
QVi SFi-1 para i = 1, ..., 6 
O modelo no Excel
Parâmetros do Solver
Resultado
Caso LCL Supermercados Ltda.
A LCL Supermercados Ltda. quer construir uma nova unidade. O total 
R$ 1.500.000 da obra será pago a construtora em três parcelas de R$ 400.000 ao final do 2º, 5º e 8º mês e uma parcela de R$ 300.000 ao final do 10º mês, quando se espera que a construção esteja terminada. A empresa dispõe de 4 tipos de investimentos (tabela a seguir) que podem ser utilizados a fim de gerar caixa para quitar a construção de maneira a reduzir a necessidade total de caixa.
Variáveis de Decisão
– Ai – Valor aplicado ao final do mês i-1 na aplicação: A (i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
– Bi – Valor aplicado ao final do mês i-1 na aplicação: B (i = 1, 3, 5, 7, 9)
– Ci – Valor aplicado ao final do mês i-1 na aplicação: C (i = 1, 4, 7)
– Di – Valor aplicado ao final do mês i-1 na aplicação: D (i = 1)
Função Objetivo: Min A1 + B1 + C1 + D1
Restrições:
O modelo no Excel
Parâmetros do Solver
Resultado
Exercícios Propostos
Livro Básico 1
– 	Exercícios 3.2, 1 a 10, pp. 80-83
– 	Resolver utilizando Excel
Exercícios 2.2, 1 a 10 pp. 32-33.
Exercícios 2.4, 1 a 10 pp. 40-41.
Exercícios 2.5, 1 a 10 pp. 48-49.
Livro Básico 2
– 	Problemasde Aplicação 3.3 – 3.30, pp. 132-139.
Conteúdo da Seção 5
Análise de Sensibilidade
– Interpretação Econômica do Problema Dual
– Preço de Sombra – Shadow Price
– Custo Reduzido – Reduced Cost
– Intervalos de Validação
– Solução Degenerada
Caso Motorela Celulares
Analisando todos os Relatórios do Excel
– Relatório de Respostas
Análise Econômica
– Relatório de Sensibilidade
– Relatório de Limites
Preço de Sombra
O preço-sombra para o recurso i mede o valor marginal deste recurso em relação ao lucro total;
O preço-sombra é a quantidade que o valor ótimo da função-objetivo (Z) seria melhorado, caso a quantidade do recurso i (bi) fosse aumentada de uma unidade.
Preço de sombra – solução gráfica
Vamos medir o efeito de aumentar a terceira constante em 3 unidades?
O conjunto de soluções viáveis foi alterado
A solução ótima também foi alterada
No problema original Z = 1600 e no problema modificado Z = 5200/3
Portanto:
– Alteração no valor da Função-objetivo:
– Logo, preço de sombra:
Preço sombra no Excel
Relatório de Análise de Sensibilidade – Preço Sombra no Excel
Considere agora a seguinte modificação.
Preço de sombra – solução gráfica
O conjunto de soluções viáveis foi alterado
Essa restrição não limitava à solução ótima inicial, que não foi alterada.
Qual é o preço de sombra desta restrição? ZERO
Preço Sombra no Excel
Relatório de Análise de Sensibilidade – Preço Sombra no Excel
Relatório de Análise de Sensibilidade – Preço Sombra no Excel 
Análise de Sensibilidade – Interpretação no Excel
Para o Excel, o conceito de Preço-Sombra está relacionado ao valor nominal do efeito na função-objetivo, isto é, quando a função-objetivo aumenta (sinal de +) ou diminui (sinal de -) em valor absoluto.
Relatório de Análise de Sensibilidade
As quantidades informadas pelas grandezas Preço-Sombra refletem as consequências de alterações unitárias.
– Alterações diferentes da unidade provocarão consequências proporcionais.
Entretanto, estes valores só podem ser garantidos dentro de intervalos apontados nos relatórios, se a solução ótima não for degenerada.
O preço sombra é constante enquanto o valor do LHR estiver no intervalo permitido.
Custo Reduzido
O custo reduzido de uma variável é:
– o total que o coeficiente da variável na função-objetivo deve melhorar para que ela deixe de ser zero na solução ótima;
– quanto o valor ótimo da função-objetivo irá piorar para cada unidade que a variável aumente a partir de zero, mantidos os coeficientes das variáveis da função-objetivo;
No problema abaixo a solução ótima tem x2 = 0.
Neste caso o Custo Reduzido mede quanto deveria ser reduzido o custo de produção de x2 (minimização) ou melhorado a sua lucratividade (maximização) para que na solução ótima o valor de x2 deixe de ser zero.
Custo reduzido – relatório de sensibilidade
Custo Reduzido no Excel
Para modificar o valor de uma variável na solução ótima para diferente de zero temos que:
– Para um custo reduzido positivo, subtrair o mesmo do coeficiente da função-objetivo.
– Para um custo reduzido negativo, adicionar o mesmo do coeficiente da função-objetivo.
Caso Motorela Celulares
Para produzir 3 tipos de telefones celulares, a fábrica da Motorela utiliza três processos diferentes, o de montagem, a configuração e a verificação. Para fabricar o celular Multi-Tics, são necessárias 0,1 h de montagem, 0,2 h de configuração e 0,1 h de verificação. O mais popular Star Tic Tac requer 0,3 h de montagem, 0,1 h de configuração e 0,1 h de verificação. Já o modelo Vulcano necessita de 0,4 h de montagem, 0,3 h para configuração, porém, em virtude de seu circuito de última geração, não necessita de verificação.
A fábrica dispõe de capacidade de 290 hs/mês na linha de montagem, 250 hs/mês na linha de configuração e 110 hs/mês na linha de verificação. Os lucros unitários dos produtos Multi-Tics, Star Tic-Tac e Vulcano são R$ 100, R$ 210 e R$ 250, respectivamente e a Motorela consegue vender tudo o que produz. Sabe-se ainda que o presidente da Motorela exige que cada um dos três modelos tenha produção mínima de 100 unidades e quer lucrar pelo menos R$ 25.200/mês com o modelo Star Tic-Tac. O presidente também exige que a produção do modelo Vulcano seja pelo menos o dobro do modelo Star Tic-Tac. Resolva utilizando o Solver do Excel.
Variáveis de Decisão
– X1 – Número de celulares Multi-Tics produzidos mensalmente.
– X2 – Número de celulares Star Tic-Tacs produzidos mensalmente.
– X3 – Número de celulares Vulcanos produzidos mensalmente.
Função Objetivo
– Maximizar o Lucro da Motorela: Max 100x1 + 210x2 + 250x3
Restrições
– Linha de Montagem		0,1x1 + 0,3x2 + 0,4x3 ≤ 290
– Linha de Configuração		0,2x1 + 0,1x2 + 0,3x3 ≤ 250
– Linha de Verificação		0,1x1 + 0,1x2 ≤ 110
– Produção Mínima			x1 ≥ 100; x2 ≥ 100; x3 ≥ 100
– Lucro Mínimo Star Tic-Tac	210x2 ≥ 25200
– Produção Vulcano		x3 ≥ 2x2
– Não Negatividade			x1; x2; x3 ≥ 0 
Modelo
Max 100x1 + 210x2 + 250x3
0,1x1 + 0,3x2 + 0,4x3 ≤ 290
0,2x1 + 0,1x2 + 0,3x3 ≤ 250
0,1x1 + 0,1x2 ≤ 110
x1 ≥ 100 ; x2 ≥ 100 ; x3 ≥ 100
210x2 ≥ 25200
x3 ≥ 2x2
x1, x2 e x3 ≥ 0
Modelo no Excel
Parâmetros do Solver
Marcar os Relatórios Desejados
Solução
Análise dos Relatórios
– Que restrições limitam a solução ótima?
– Quanto deve ser melhorado no lucro unitário para que se produza o modelo Star Tic-Tac?
Relatório de sensibilidade
– Até quanto você pagaria por uma hora de verificação terceirizada?
Relatório de sensibilidade
Alterando o Problema para Verificar Resultado
– Problema Alterado – Mesmo Valor Ótimo
Até quanto você pagaria por uma hora de montagem terceirizada?
Relatório de Sensibilidade
– O que significa o preço-sombra de -20 na última restrição?
Cada unidade adicional de Vulcano com relação ao dobro de Star-Tac provoca perda de lucratividade de R$ 20,00, isto é, a função-objetivo diminui de 20.
Alterando o Problema para Verificar Resultado
Intervalos de Validação do Preço-Sombra e do Custo Reduzido
A análise de sensibilidade determina os intervalos em que o Custo Reduzido e o Preço-Sombra são válidos.
Uma razão para se estabelecer esses intervalos está ligada a hipótese de certeza assumida em modelos de programação linear.
Análise de Sensibilidade – Solução Degenerada
A solução de um problema de Programação Linear algumas vezes apresenta uma anomalia conhecida como degeneração.
Uma solução de uma PL é dita degenerada quando o valor de incremento ou decremento de uma restrição é igual a zero.
A presença de degeneração altera a interpretação da análise de sensibilidade em um certo número de maneiras.
Quando a solução ótima é degenerada
– O valor do Custo Reduzido pode não ser único.
– O valor de incremento e decremento dos coeficientes da função-objetivo permanecem válidos. De fato, os valores podem se alterar substancialmente acima desses valores, sem que a solução ótima se altere.
– O valor do Preço-Sombra e seus intervalos podem continuar sendo interpretados da mesma maneira, contudo podem não ser únicos.
Analisando todas as respostas do Excel
Modelo
Solicitando os relatórios desejados
Análise de sensibilidade no Excel
Relatório de respostas
– Agrupar => LHS = RHS
– Sem Agrupar => LHS ≠ RHS, quando a variável de folga for básica e diferente de zero.
– Variável de Folga.
Relatório de respostas – observação importante
– O Excel determina que a restrição tem status “Sem Agrupar” quando a variável de folga daquela restrição é básica. Geralmente, isto significa que existe folga, e, portanto, LHS (diferente) RHS.
– Entretanto, é possível acontecer da variável de folga ser básica e igual a zero. Neste caso, a restrição terá status Agrupar e LHS = RHS.
Relatório de Limites
 Prof. M.Sc. Fábio Hipólito 		Métodos QuantitativosPág.47Email do Prof. M.Sc. Fábio Hipólito: paraofabio@gmail.com 	 www.fabiohipolito.com.br
– A coluna inferior Limite indica o menor valor que cada variável pode assumir, considerando, que todas as outras não se alterem, para que a solução continue viável. A coluna ao lado mostra o valor que a função-objetivo assume nessa solução.
– A coluna Superior Limite indica o maior valor que cada variável pode assumir, considerando, que todas as outras não se alterem, para que a solução continue viável. A coluna ao lado mostra o valor que a função-objetivo assume nessa solução.
Exercícios Propostos
– Livro Básico 1: Exercícios 4.2, 1-5, pp. 114-118
– Livro Básico 2: Problemas 4.1 – 4.65, pp. 189-201
Conteúdo da Seção 6
Modelos de Rede
– Regra do Fluxo Balanceado
– Modelos de Transporte
Caso LCL Motocicletas S.A.
– Modelos de Escala de Produção
Caso LCL Fórmula Turismo Ltda.
Caso LCL Fogões Ltda.
– Modelos de Rede de Distribuição
Caso Automóveis Brasil
– Modelos de Menor Caminho
– Modelos de Fluxo Máximo
Modelos em Rede
Modelos de rede podem ser utilizados em diversas áreas tais como transportes, energia e comunicações para modelagem de diversos tipos de problemas.
Uma rede é um conjunto de vértices ou nós ligados entre si por um conjunto de arcos.
Num modelo de rede cada nó terá uma denominação ou numeração específica.
As variáveis de decisão estarão ligadas aos arcos existentes entre os nós.
– X12 – pode indicar o nº de veículos que passa na estrada que liga a cidade 1 à cidade 2.
– X34 – pode indicar o nº de geladeiras que é entregue pela fábrica 3 no revendedor 4.
A função-objetivo do problema de rede de distribuição é dada por:
Onde:
– cij é o custo unitário de transporte de uma unidade do produto de i para j.
– Xij é o número de produto transportados na rota de i para j.
Regra de Fluxo Balanceado
Uma maneira de modelar as restrições de um problema de rede é seguir a Regra Fluxo Balanceado para cada nó.
Nesta regra para cada nó da rede devemos estabelecer a diferença entre as variáveis que estão chegando (entradas) ao nó, menos as variáveis que estão deixando o nó (saídas).
O sinal da restrição varia com ofertas e demandas totais Xij – é uma entrada para o nó j e é uma saída do nó i.
O lado direito das restrições serão as ofertas ou demandas de cada nó.
Caso de Oferta Total = Demanda Total
Caso a Oferta Total > Demanda Total
	
Caso a Oferta Total < Demanda Total
Caso LCL Motocicletas S.A.
A LCL Motocicletas S.A. possui 3 fábricas localizadas em Cuiabá, Santo André e Florianópolis. A produção deve ser entregue em Recife, Salvador e Fortaleza. Considerando os custos de transporte unitários, as capacidades de produção das fábricas e as demandas dos centros consumidores que estão especificados na tabela a seguir, determine quanto deve ser produzido e entregue por cada fábrica em cada centro consumidor de forma a minimizar os custos de transporte.
Variáveis de decisão
– Existem 9 variáveis para expressar a quantidade transportada em cada uma das possíveis vias.
– xij= Quantidade transportada da fábrica i para o centro consumidor j.
Modelo gráfico
O Modelo	Parâmetros no Solver
 
Solução
Problema de Rede – Aplicação 
O problema de rede não é aplicado apenas a problemas de distribuição de mercadorias das fábricas para centros distribuidores;
O mesmo tipo de formulação pode ser aplicado a outros tipos de problemas, tais como:
– Problemas de Escala de Produção;
– Problemas de Layout de fábricas;
Caso LCL Fórmula Turismo Ltda.
– A GLP Fórmula Turismo Ltda. fornece motores para equipes de fórmula turismo. A companhia detém contratos de entregas futuras programadas para o próximo ano. As entregas deverão ocorrer a cada quadrimestre. A tabela resume as entregas programadas, a capacidade máxima de produção e o custo de produção por quadrimestre incluindo o custo de armazenamento. Formule o problema para achar o número de motores que devem ser fabricados em cada quadrimestre de maneira a atender os pedidos contratados.
Representação Gráfica do Modelo
Solução
Caso LCL Fogões Ltda.
– A LCL Fogões Ltda. deseja realizar o escalonamento de sua produção para os próximos 3 meses. Sua fábrica pode produzir mensalmente, em horário normal, 250 fogões a um custo de R$ 35,00, e em horário extra, 50 unidades a um custo de R$ 40,00. Considere que é possível armazenar durante um mês a um custo unitário de R$ 5,00 sem restrições de espaço. Suponha que as demandas para os próximos quatro meses são de 140, 200 e 130. Qual a escala de produção a ser seguida?
Para resolver este problema, criaremos uma rede onde:
– Cada nó representará uma unidade produtora ou unidade receptora.
São 6 unidades produtoras (2 por mês)
São 3 unidades receptoras (3 meses)
– Cada arco está relacionado ao custo de produção e/ou armazenagem.
Solução
Caso Automóveis Brasil
– A Automóveis Brasil terá duas fábricas no Brasil, uma em Salvador (1) e outra em Santo André (2), e está estudando a forma de distribuição de seus carros para diversas revendas de Minas Gerais, nas cidades de Juiz de Fora (3), B. Horizonte (4), Barbacena (5) e Tiradentes (6). A seguir é apresentada a rede de revendas da Automóveis Brasil, seus custos de transporte unitários, demandas das revendas e as capacidades das fábricas. Determine a forma como a entrega de veículos deve ser realizada pelas fábricas às revendas.
Variáveis de Decisão
– Xij – Nº de Carro remetidos de i para j
Exemplo:
– X14 – Nº de Carro remetidos de 1 para 4
Função-Objetivo = Minimizar o Custo de Distribuição
– Min 20X13 + 10X14 + 40X15 + 10X23 + 20X24 + 40X25 + 25X36 + 35X45 + 25X46 + 15X56 + 10X65
Como a oferta total é maior que a demanda total, devemos utilizar a seguinte restrição em todos os nós:
entradasnó i – saídasnó i ≥ [oferta/demanda]nó i
Modelo
Solução
Problemas de Menor Caminho
Se considerarmos uma rede na qual o arco signifique a distância entre dois pontos (nós) e desejarmos achar a rota que une estes pontos com distância mínima, teremos um problema do tipo do Menor caminho.
Este tipo de problema pode ser generalizado e aplicado a distribuição de produtos, entre outros.
Exemplo:
Considere a rede abaixo que representa a ligação rodoviária entre duas cidades (A e B). O tamanho dos arcos representa a distância entre pontos da malha rodoviária entre as cidades.
Este problema pode ser visto como um problema de rede de distribuição de oferta de um caminhão (A = -1) e ponto de demanda de um caminhão (B = +1) e os demais pontos da malha sem demanda ou oferta (=0)
Solução
Problema do Fluxo Máximo
Nesse tipo de problema temos uma rede de nós e arcos, e desejamos que o maior fluxo de uma grandeza possa fluir de um determinado nó para outro.
Nesse tipo de problema, mais de um caminho pode ser utilizado simultaneamente.
Aplicações
– Rede de distribuição de água, luz, gás e tráfego na internet.
Problemas de Rede – Problema do Fluxo Máximo
Como resolver o problema?
– Adicionar um arco artificial ligando o ponto de saída (A) ao ponto de chegada (B).
– Maximizar o fluxo no arco artificial criado (fluxo grande).
– Utilizar a regra de balanceamento de redes.
– As grandezas associadas aos arcos são o fluxo máximo em cada trecho da rede, portanto restrições no modelo.
– O valor de Oferta/Demanda em cada nó é igual a zero.
Exercícios Propostos
Livro Básico 1
– Exercícios 5.1, 1 – 10, pp. 134 – 136
– Exercícios 5.2, 1 – 10, pp. 152 – 153
Livro Básico 2
– Problemas 5.1 – 5.31, pp. 263 – 269
Conteúdo da Seção 7
Programação Inteira
– Solução Gráfica
– Solução Excel
Caso GLP Tecnologia S.A.
Variáveis Binárias e Condições Lógicas
Programação Não Linear
Caso GLP Computadores
Programação Inteira
São problemas de programação matemática em que a função objetivo, bem como as restrições,são lineares, porém uma ou mais variáveis de decisão podem apenas assumir valores inteiros.
Esse problema pode apresentar dois tipos básicos:
– Programação Inteira Total – onde todas as variáveis de decisão são do tipo inteiro.
– Programação Inteira Mista – onde apenas uma parte das variáveis são do tipo inteiro, enquanto outras são do tipo real.
A primeira ideia que pode vir à mente é resolver o problema como se fosse um problema de programação linear e arredondar os valores ótimos encontrados para cada uma das variáveis de decisão inteiras.
Para problemas de grande porte, isto geralmente gerará uma solução aceitável (próxima do ótimo real) sem a violação de nenhuma das restrições.
Para problemas menores, esse tipo de procedimento poderá nos levar a soluções inviáveis ou não ótimas.
Programação Inteira – Problema Relaxado
A todo problema de programação inteira está associado um problema com a mesma função-objetivo e as mesmas restrições, com exceção da condição de variáveis inteiras. A esse problema se dá o nome de Problema Relaxado.
Programação Inteira – Conjunto de Soluções Viáveis
Programação Inteira – Solução Gráfica
Programação Inteira – LP Relaxado
– Em um problema de MAXIMIZAÇÃO, o valor ótimo da função-objetivo, do Problema Relaxado, sempre representa um limite superior ao respectivo Problema Inteiro.
– Em um problema de MINIMIZAÇÃO, o valor ótimo da função-objetivo, do Problema Relaxado, sempre representa um limite inferior ao respectivo Problema Inteiro.
– Nenhum ponto inteiro vizinho ao ponto ótimo do problema relaxado é necessariamente viável.
– Mesmo que um dos vizinhos seja viável.
Não é necessariamente o ponto ótimo inteiro.
Não é obrigatoriamente uma solução aceitável.
Programação Inteira
– Comparativamente ao LP correspondente, o IP levará muito mais tempo para obter um valor ótimo.
– Isso está ligado ao fato que diversos problemas de LP são resolvidos sucessivamente para se obter a solução de um IP.
– A solução obtida num problema IPL ou MIPL
Sem análise de sensibilidade.
– Deve ser efetuada alterando-se o problema e obtendo-se nova solução.
Não provê informação similar ao preço de sombra.
Muitos softwares que realizam programação inteira são parte integrante de pacotes de programação linear e produzem análise de sensibilidade, independente desta não ter valor no âmbito de programação inteira.
Usando Solver do Excel – Definindo Variáveis Inteiras
Usando Solver do Excel – Definindo Variáveis Binárias
Caso GLP Tecnologia S/A
– A GLP Tecnologia S/A tem que planejar seus gastos em investimentos para o próximo ano. A empresa pré-selecionou 3 projetos e deve escolher dentre esses quais deve priorizar em função de suas restrições orçamentárias. Os dados relevantes encontram-se na tabela abaixo. Considere a taxa de desconto de 9% a.a.
Variáveis de Decisão
Função Objetivo = Maximizar o somatório NPV
Max 104,01X1 + 123,81X2 + 170,35X3
Restrições Orçamentárias
70x1 + 80x2 + 130x3 ≤ 200	- 	Ano 1
15x1 + 30x2 + 20x3 ≤ 70		- 	Ano 2
15x2 ≤ 50				-	Ano 3
20x1 + 10x2 + 30x3 ≤ 30		-	Ano 4
20x1 + 10x2 + 20x3 ≤ 70		-	Ano 5
Solução
Variáveis Binárias e Condições Lógicas
As variáveis binárias também se prestam a selecionar alternativas que sejam condicionais.
No exemplo anterior imagine que não mais de um dos projetos 1, 3 e 4 pudesse ser selecionado. Deveríamos então adicionar: X1 + X3 + X4 ≤ 1
Se apenas um dos projetos e apenas um dos projetos 1, 2 e 4 tivesse que ser escolhido obrigatoriamente, deveríamos incluir: X1 + X2 + X4 = 1
Imagine agora que o projeto 1 dependa de uma tecnologia que deve ser desenvolvida pelo projeto 2, isto é, o projeto 1 só pode ser aprovado se e somen-te se o projeto 2 for aceito. Deveríamos então incluir:
Programação Não Linear
De forma geral um problema de programação não linear tem a seguinte forma:
Nenhum algoritmo resolve todos os problemas que podem ser incluídos neste formato.
Solução Gráfica
Considere o Problema de Programação Linear e sua solução gráfica
Considere o Problema e sua solução gráfica
A solução ótima de um problema de programação não linear (NLP), diferentemente de um problema de LP, pode ser qualquer ponto do conjunto de soluções viáveis.
Isso torna os problemas de NLP muito mais complexos, obrigando os algoritmos de solução a pesquisar todas as soluções viáveis.
O Excel utiliza o algoritmo GRG (generalized reduced gradient) para chegar à solução para um dado problema.
O algoritmo não garante que a solução encontrada é uma solução global.
O Solver às vezes tem dificuldades de achar soluções para problemas que tenham condições iniciais para as variáveis iguais a zero. Uma boa medida é começar a otimização com valores diferentes de zero para as variáveis de decisão.
Uma maneira prática para tentar minorar o problema de máximos e mínimos locais é começar a otimização de diversos pontos iniciais, gerados aleatoriamente.
Se todas as otimizações gerarem o mesmo resultado, você pode ter maior confiança, não a certeza, de ter atingido um ponto global.
Programação Não Linear – Controle de Estoque
Um dos modelos mais simples de controle de estoque é conhecido como Modelo do Lote Econômico.
Esse tipo de modelo assume as seguintes hipóteses:
–A demanda (ou uso) do produto a ser pedido é praticamente constante durante o ano.
– Cada novo pedido do produto deve chegar de uma vez no exato instante em que este chegar a zero.
Determinar o tamanho do pedido e a sua periodicidade dado os seguintes custos:
– Manutenção de Estoque – Custo por se manter o capital no estoque e não em outra aplicação, rendendo benefícios financeiros para a empresa.
– Custo do Pedido – Associado a trabalho de efetuar o pedido de um determinado produto.
– Custo de Falta – Associado a perdas que venham a decorrer da interrupção da produção por falta do produto.
Variável de Decisão: 
Q – Quantidade por Pedido
Função Objetivo = 
Onde:
D = Demanda Anual do Produto
C = Custo Unitário do Produto
S = Custo Unitário de Fazer o Pedido
Cm = Custo unitário de manutenção em estoque por ano
Caso GLP Computadores
– A GLP Computadores deseja diminuir o seu estoque de placa-mãe. Sabendo-se que o custo unitário da placa-mãe é de R$ 100,00, o custo anual unitário de manutenção de estoque é de R$ 3,00 e o custo unitário do pedido é de R$ 5,00, encontre o lote econômico para atender a uma demanda anual de 1000 placa-mãe. 
Exercícios Propostos
Livro Básico 1
– Exercícios 6, 1 – 10, pp. 167 – 169 
– Exercícios 7, 1 – 6, pp. 193 – 194
Livro Básico 2
– Problemas 6.1 – 5.25, pp. 303 – 306
– Problemas 7.1 – 7.46, pp. 359 – 364