Programação Linear
Introdução
Prof. Antonio Carlos Coelho
1
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
2
Alocação de recursos com
restrição única

Uma indústria automobilística fabrica 2 modelos de
veículos com as seguintes características:
Modelo 4 portas
Modelo 2 portas



Preço de
venda
$ 260.000
$ 258.000
Custo
variável
$ 205.000
$ 204.000
MC unitária
$ 55.000
$ 54.000
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?
3
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
4
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
5
E quando há mais restrições?
Aplicam-se modelos de Programação:
Linear
Linear Inteira
Multiobjetiva (goal programming)
Não Linear
Outros modelos:
Simulação
Análise da Decisão
6
Programação Linear
É 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
7
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
8
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
9
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
10
Expressando Matematicamente
A decisão é representada pelas variáveis de
decisão
• X1, X2, ... , Xn
O objetivo é representado por uma funçãoobjetivo do tipo
• MAX (MIN) V = f (X1, X2, ... , Xn)
11
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
12
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
13
Resolvendo o Modelo
Solução Gráfica
Solução Matricial
Método Simplex
Solução Computacional
14
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
15
Exemplo
Função Objetivo
MAX: 350x1 + 300x2
Sujeito a:
Fatores de Produção → Limitação
1x1 + 1x2 
200
Horas de Mão de Obra 9x1 + 6x2  1.566
Canos (metros)
12x1 + 16x2  2.880
Bombas
16
Exemplo
Função Objetivo
MAX: 350x1 + 300x2
Sujeito a:
1x1 + 1x2  200
9x1 + 6x2  1.566
12x1 + 16x2  2.880
x1
≥
0
x2 ≥
0
17
Solução Gráfica
x2
Função
Objetivo
Solução ótima
Restrição de trabalho
Restrição de bombas
Restrição de tubos
x1
18
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
19
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
20
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
21
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
22
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
23
Solução Computacional
Para Problemas mais Complexos
Solução via Excel
Ferramenta Solver
24
Condições Especiais
1.
2.
3.
4.
Alternância de Soluções Ótimas
Restrições Redundantes
Soluções Ilimitadas
Soluções de Impossibilidade
 As duas primeiras não impossibilitam o modelo
 As duas últimas impossibilitam o uso do modelo
25
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
26
Soluções Ilimitadas
 Ocorre quando são encontradas soluções nas quais a
função objetivo é infinitamente grande (maximização) ou
infinitamente pequena (minimização)
Exemplo:
MAX:
x1 + x2
Sujeito a:
x1 + x2  400
- x1 + 2x2  400
x1
 0
x2  0
27
Soluções Ilimitadas
x2
x1
28
Solução Impossível
Exemplo:
MAX:
Sujeito a:
x1 +
x2
x1 + x2  150
x1 + 2x2  200
x1

0
x2 
0
29