Programação Linear_1

Prévia do material em texto

1
Programação Linear
Introdução
Prof. Antonio Carlos Coelho
2
Por Que Modelos de 
Programação Matemática
 Constatação básica:
Recursos limitados e escassos 
 exemplos: tempo, dinheiro, recursos naturais, capacidade 
instalada
Necessidades ilimitadas e crescentes
 princípios de eficiência e eficácia
Objetivo do modelo:
Possibilitar aos agentes econômicos decidir sobre o 
melhor uso dos recursos limitados
Proporcionar a otimização da alocação de recursos 
escassos de modo a maximizar lucros e minimizar 
custos
3
Alocação de recursos com 
restrição única
 Uma indústria automobilística fabrica 2 modelos de 
veículos com as seguintes características:
MC unitária
$ 55.000
$ 54.000
Preço de
venda
$ 260.000
$ 258.000
Custo 
variável
$ 205.000
$ 204.000
Modelo 4 portas
Modelo 2 portas
 Cada porta possui uma maçaneta, que é igual para todas as 
portas. 
 Num determinado mês, há uma restrição de 8.000 maçanetas. 
 Quanto devo produzir de cada modelo para maximizar a 
Margem de Contribuição para a empresa no período?
4
Alocação de recursos com 
restrição única
Princípio geral: 
fabricar o produto que proporciona maior MC 
por fator limitativo:
4 portas: $ 55.000/4 maçanetas = $ 13.750/ maçaneta
2 portas: $ 54.000/2 maçanetas = $ 27.000/ maçaneta
5
Alocação de recursos com 
restrição única
Solução: 
produzir modelo de 2 portas 
4.000 veículos (8.000 maçanetas / 2 portas)
• MC total: 4.000u X $ 54.000 = $ 216.000.000
Se produzir modelo de 4 portas
2.000 veículos (8.000 maçanetas / 4 portas)
• MC total: 2.000u X $ 55.000 = $ 110.000.000
6
Aplicam-se modelos de Programação:
Linear
Linear Inteira
Multiobjetiva (goal programming)
Não Linear
Outros modelos:
Simulação
Análise da Decisão
E quando há mais restrições?
7
É uma técnica matemática que auxilia na 
determinação da melhor utilização dos 
recursos limitados de uma organização 
em problemas com relações lineares
Programação Linear
8
Programação Linear
APLICAÇÕES USUAIS 
Planejamento Operacional
Determinar o mix de produtos que maximiza 
o lucro da empresa
Determinar logística e rotas que minimizam 
o custo de transporte
Planejamento Financeiro:
Determinar a alocação de recursos em 
carteiras de investimento que maximizem o 
retorno e/ou minimizem o risco
9
Desenvolvendo o Modelo
Características 
Envolve uma decisão a ser tomada
Existem restrições a serem consideradas 
nas alternativas de decisão
Existe uma meta ou objetivo a ser 
maximizado ou minimizado
10
Desenvolvendo o Modelo
1) Análise e Compreensão do problema
2) Montagem do Modelo
1) identificação das variáveis de decisão
2) definição das restrições
3) formulação da função objetivo
3) Solução do Modelo 
11
Expressando Matematicamente
A decisão é representada pelas variáveis de 
decisão 
• X1, X2, ... , Xn
O objetivo é representado por uma função-
objetivo do tipo
• MAX (MIN) V = f (X1, X2, ... , Xn)
12
Expressando Matematicamente
As restrições são representadas pelo parâmetro b, 
expressas de 3 maneiras possíveis:
menor ou igual
• f (X1, X2, ... , Xn)  b
maior ou igual 
• f (X1, X2, ... , Xn)  b
igual
• f (X1, X2, ... , Xn) = b
13
Fórmula Geral 
MAX (MIN) V = c1X1 + c2X2 + ... + cnXn
Sujeito a:
a11X1 + a12X2 + ... + a1nXn  b1
ak1X1 + ak2X2 + ... + aknXn  bk
am1X1 + am2X2 + ... + amnXn = bm
...
...
Onde:
c1, c2, ... , cn = margem de contribuição; medida de custo; 
taxa de retorno, etc.
aij = quantidade do fator de restrição consumido em cada 
unidade produzida ou disponível para utilizar, etc.
bi = valor máximo ou mínimo do recurso escasso
14
Resolvendo o Modelo
Solução Gráfica
Solução Matricial
Método Simplex
Solução Computacional
15
Exemplo
Variáveis de decisão
Dois tipos de banheira
Margens diferentes de Contribuição
Restrições
Disponibilidade de Mão de Obra
Disponibilidade de Canos
Disponibilidade de Bombas
16
Exemplo
Função Objetivo
MAX: 350x1 + 300x2
Sujeito a:
Fatores de Produção → Limitação
Bombas 1x1 + 1x2  200
Horas de Mão de Obra 9x1 + 6x2  1.566
Canos (metros) 12x1 + 16x2  2.880
17
Exemplo
Função Objetivo
MAX: 350x1 + 300x2
Sujeito a: 
1x1 + 1x2  200
9x1 + 6x2  1.566
12x1 + 16x2  2.880
x1 ≥ 0
x2 ≥ 0
18
Solução Gráfica
x1
x2
Restrição de tubos
Restrição de trabalho
Restrição de bombas
Função 
Objetivo
Solução ótima
19
Solução Gráfica
 Como determinar a solução ótima?
A) A partir da visualização do encontro das 
curvas de nível com as retas de restrição
B) A partir da comparação dos diversos 
pontos extremos, para escolher o maior 
(menor) valor
20
Solução Gráfica
Sumário da Solução Gráfica
• Desenhe a reta de cada restrição no gráfico
• Identifique a área de soluções factíveis, isto 
é, a área do gráfico que simultaneamente 
satisfaz a todas as restrições
• Encontre a solução ótima por um dos 
métodos a seguir descritos
21
Métodos Gráficos
a) Desenhe uma ou mais curvas de nível da função objetivo 
e determine a direção na qual curvas paralelas resultam 
em aumentos no valor da função objetivo 
b) Desenhe curvas paralelas na direção do crescimento até 
que a curva toque a área de soluções em um único ponto
c) Encontre às coordenadas deste ponto 
a) Identifique as coordenadas de todos os pontos extremos 
da área de soluções factíveis e calcule os respectivos 
valores da função objetivo.
b) O ponto com o maior valor da função-objetivo é a solução 
ótima
22
Solução Matricial
A resolução de um problema de 
programação linear consiste em
 resolver sistemas algébricos lineares e 
calcular o valor da função-objetivo
Escolher dentre os diversos resultados 
obtidos para a função-objetivo, aquele 
que fornece o maior (menor) valor
23
Método Simplex
Baseia-se nas variáveis de FOLGA
Base para os relatórios de Sensibilidade 
do software SOLVER
Sistema com n variáveis e m equações
Seleciona m variáveis (BÁSICAS)
As demais assumem valor = 0 (NÃO BÁSICAS)
Calcula Função Objetivo para cada rodada
Escolhe a de maior valor
24
Solução Computacional
Para Problemas mais Complexos
Solução via Excel
Ferramenta Solver
25
Condições Especiais
1. Alternância de Soluções Ótimas 
2. Restrições Redundantes
3. Soluções Ilimitadas
4. Soluções de Impossibilidade
 As duas primeiras não impossibilitam o modelo
 As duas últimas impossibilitam o uso do modelo
26
Condições Especiais
Alternância de Soluções Ótimas:
 Ocorre quando há mais de um ponto que maximiza (ou 
minimiza) o valor da função objetivo
 A existência de mais de uma solução possível não 
inviabiliza o uso da ferramenta Programação Linear
Restrições Redundantes:
 Ocorre quando uma restrição não faz diferença na 
determinação da área de soluções factíveis
27
Soluções Ilimitadas
MAX: x1 + x2
Sujeito a:
x1 + x2  400
- x1 + 2x2  400
x1  0 
x2  0
 Ocorre quando são encontradas soluções nas quais a 
função objetivo é infinitamente grande (maximização) ou 
infinitamente pequena (minimização)
Exemplo:
28
Soluções Ilimitadas
x1
x2
29
Solução Impossível
Exemplo:
MAX: x1 + x2
Sujeito a:
x1 + x2  150
x1 + 2x2  200
x1  0
x2  0