Capítulo 2

Programação Linear
 Introdução
 Umas das técnicas mais utilizadas para a
resolução dos problemas de pesquisa
operacional é a programação linear
 Simplicidade do modelo e facilidade de
implementação facilitam a sua aplicação
 As aplicações são feitas em sistemas
estruturados
 Produção
 Finanças
 Controle de estoques
 Etc.
 Modelo

 É modelo matemático da programação

linear é composto:
 Função objetiva linear;
 Restrições técnicas
 Grupo de inequações, também lineares
 Modelo
Exemplo

Lucro  2 x1  3 x2
 4 x1  3 x2  10
ténicas
 6 x1  x2  20
restrições 
de não negatividade x1  0
 
  x2  0
 Modelo

 Variáveis controladas ou de decisão

 X1 e X2
 Função objetiva
 Mede o desempenho do sistema
 Neste caso, mede o capacidade de gerar lucro
para cada solução
 O que se quer é maximizar o lucro
 Modelo

 Restrições
 São as limitações impostas a solução, ou seja,
garante que as soluções estão de acordo com
as limitações técnicas impostas pelo sistema
 As restrições de não negatividade são
obrigatórias quando se utilizar a programação
linear
 Modelo

 A construção do modelo matemático,

no caso um modelo linear, é a parte
mais complicada.
 Não ha regra fixa, mas pode-se sugerir
um roteiro para ordenar raciocínio
 Roteiro

 Quais as variáveis de decisão?

 Explicar as decisões que devem ser tomadas e
representar as possíveis decisões através de
variáveis chamadas variáveis de decisão
 Isto é:
 Programação de produção: quantidades a produzir
no período
 Programação de investimento: decisões de
investimento (quanto e quando)
 Roteiro

 Qual o objetivo?
 Objetivo da tomada de decisão
 Maximização do lucro ou receitas
 Minimização de custos, perdas, etc.

 A função objetivo
 Expressão que calcula o valor do objetivo (Lucro,
Custo, Receita, etc.) em função das variáveis de
decisão
 Roteiro

 Quais restrições?
 Cada restrição deve expressa como uma
relação linear (igualdade, desigualdade)
 As restrições devem ser expressas com as
variáveis de decisão
 Exemplo 1
 Uma empresa fabrica dois produtos P1 e P2. O
lucro unitário do produto P1 é 1.000 unidades
monetárias e o lucro unitário do produto P2 é de
1.800 unidades monetárias. A empresa precisa
de 20 horas para fabricar uma unidade de P1 e
de 30 horas para fabricar uma unidade de P2. O
tempo anual de produção disponível para isto é
de 1.200 horas. A demanda esperada para cada
produto é de 40 unidades anuais para P1 e 30
unidades anuais para P2. Qual o plano de
produção para que a empresa maximize seu
lucro nestes itens? Construa o modelo de
programação linear para esse caso.
 Exemplo 1
 Dois produtos P1 e P2
 Lucro
 P1 1.000
 P2 1.800
 Tempo para fabricar (total 1.200h)
 P1 20h
 P2 30h
 Demanda anual
 P1 40
 P2 30
 Exemplo 1

 Quais a variáveis?
 Plano de produção
 X1 quantidade anual a produzir de P1
 X2 quantidade anual a produzir de P2
 Exemplo 1

 Qual o objetivo?
 Maximizar o lucro
 Lucro de P1 = 1.000 . x1
 Lucro de P2 = 1.800 . X2
 Lucro Total: L = 1.000 . X1 + 1.800 . X2
 Objetivo
 Maximizar L = 1.000 . X1 + 1.800 . X2
 Exemplo 1
 Restrições
 Disponibilidade de horas: 1.200h
 P1: 20x1
 P2: 30x2

 Horas ocupadas: 20x1 + 30x2

 Restrição: 20x1 + 30x2 <= 1.200

 Demanda
 P1 x1 <= 40
 P2 x2 <= 30
 Exemplo 1
max L  1.000 x1  1.800 x2
 20 x1  30 x2  1.200
 
ténicas x1  40
  x  30
Re strições   2
 
de não negatividade  x1 0

  x2  0
 Exemplo 2
 Para uma boa alimentação, o corpo necessita de
vitaminas e proteínas. A necessidade mínima de
vitaminas é de 32 unidades por dia e a de proteínas é de
36 unidades por dia. Uma pessoa tem carne ovos para
alimentar. Cada unidade de carne contém 4 unidades de
vitaminas e 6 unidades de proteínas. Cada unidade de
ovo contém 8 unidades de vitaminas e 6 unidades de
proteínas.
 Qual a quantidade diária de carne e ovos que deve ser
consumida para suprir as necessidades de vitaminas e
proteínas com o menor custo possível? Cada unidade de
carne custa 3 unidades monetárias e cada unidade de
ovo custa 2,5 unidades monetárias
 Exemplo 2
 Boa alimentação
 Vitamina mínimo de 32
 Proteínas mínimo de 36
 Comida
 Carne 4v e 6p
 Ovo 8v e 6p
 Custo
 Carne 3u
 Ovo 2,5u
 Exemplo 2

 Quais a variáveis?
 Decidir a quantidade de ovo e carne
 X1 quantidade de carne
 X2 quantidade de ovos
 Exemplo 2

 Qual o objetivo?
 Minimizar o custo
 Custo carne = 3 . x1
 Custo ovo = 2,5 . X2
 Custo Total: C = 3 . X1 + 2,5 . X2
 Objetivo
 Minimizar C = 3 . X1 + 2,5. X2
 Exemplo 2

 Restrições
 Necessidade mínima de vitaminas: 32u
 P1: 4x1
 P2: 8x2

 Total de vitaminas: 4x1 + 8x2

 Restrição: 4x1 + 8x2 >= 32

 Exemplo 2

 Restrições
 Necessidade mínima de proteínas: 36u
 P1: 6x1
 P2: 6x2

 Total de vitaminas: 6x1 + 6x2

 Restrição: 6x1 + 6x2 >= 36

 Exemplo 2
min C  3 x1  2,5 x2
 4 x1  8 x2  32
ténicas
 6 x1  6 x2  36
Re strições 
de não negatividade x1  0
 
  x2  0
 Solução

 Exemplo 1
 Exemplo 2
Capítulo 2

Método Gráfico
 Conceito

 Esta técnica consiste:

 Representar num sistema de eixos ortogonais
o conjunto de possíveis soluções
 O conjunto de pontos (x1, x2) que satisfaçam
as restrições
 O desempenho é avaliado para representação
da função objetivo
 As solução são classificadas de acordo com a
posição no gráfico
Gráfico do conjunto de soluções

 A representação gráfica de uma equação

linear com duas variáveis é uma reta
 A representação gráfica de uma inequação
linear com duas variáveis é um dos
semiplanos
Gráfico do conjunto de soluções
 Exemplo: representar x1 + 2x2 >= 10
 Construir a reta x1 + 2x2 = 10
 x1 = 0  x2 = 5
 x = 0  x1 = 10
2
 Testar a inequação x1 + 2x2 >= 10
 Escolha qualquer ponto de uma das regiões
 x1 = 10, x2 = 5
 10 +2 . 5 >= 10  20>= 10  verdadeiro
 Ou x1 = e x2 = 0
 0 + 0 > 10  falso
Gráfico do conjunto de soluções

(10,5) Verdadeiro
5
Região de soluções

x1 + 2x2 = 10

(0,0) falso

10
Gráfico do conjunto de soluções
 Exemplo 2: representar
 x1+3x2<=12
 2x1+x2>=16
 x1>=0
 x2>=0
 Retas
 R01 x1=0  x2=4 x2=0  x1=12
 R02 x1=0  x2=16 x2=0  x1= 8
 As outras duas representam o primeiro quadrante
Gráfico do conjunto de soluções

 Para testar: ponto (8, 16)

 x1+3x2<=12  8+3.16<=12  56<=12 NOK
 2x1+x2>=16  2.8+16=>16  32>=16 OK
 Eu prefiro: ponto (0, 0)
 x1+3x2<=12  0 <=12 OK
 2x1+x2>=16  0 =>16 NOK
 Gráfico do conjunto de soluções

16 (8,16) x1 >=0
x2>=0

2x1+x2>=16

x1+3x2<=12

(0,0) 8 12
 Avaliação do Objetivo
 Maximizar L=2x1+5x2
 3x1+4x2 <= 24
 2x1+1x2 <= 8
 x1>=0
 x2>=0
 Solução
 R01  x1 = 0  x2 = 6
 x1 = 8  x2 = 0
 R02  x1 = 0  x2 = 8
 x1 = 4  x2 = 0
 Avaliação do Objetivo
 Escolher um valor arbitrário para L:
 10, então, 2x1+5x2=10
 Se x1=0  2 . 0 + 5. x2 = 10  x2=2
 Se x2=0  2 . X1 + 5 . 0 = 10  x1=5
 20, então, 2x1+5x2=20
 Se x1=0  2 . 0 + 5. x2 = 20  x2=4
 Se x2=0  2 . X1 + 5 . 0 = 20  x1=10 2x
 Avaliação do Objetivo

 Verifica-se
 A medida que atribuímos valores para L,
obtemos retas paralelas;
 A medida que o valor de L aumenta, a reta se
afasta da origem do sistema
 Portanto
 Pode-se concluir que ponto em que passa a
paralela de maior valor que passa pela região
de solução é ponto de máximo
 Exemplo maximizar

L= 30

L= 20

L= 10
Cresce
 Exemplo

 Minimizar Z=2x +3x

1 2

 x1+x2>=5
 5x1+x2>=10
 x1<=8
 x1>=0
 x2>=0
 Solução

 x1+x2=5
 X1=0  x2=5
 X2=0  x1=5
 5x1+x2=10
 X1=0  x2=10
 X2=0  x1=2
 x1=8
 Solução

 Usando o ponto (0, 0)

 x1+x2>=5  0+0>=5
 NOK
 5x1+x2>=10  0 + 0>=10
 NOK
 x1<=8  0<= 8
 OK (direção do ponto)
 Solução

 Função objetivo
 Z=6  2x1+3x2=6
 X1=0  x2= 2
 X2=0  x1=3

 Z=12  2x1+3x2=12
 X1=0  x2=4
 X2=0  x1=6
 Exemplo - minimizar

L= 12

L= 06
Cresce

L= 10