PO c02 v2005

1

2 Modelos de Programação Linear
Conteúdos do Capítulo w Problemas de Programação Linear n n n n n Resolução pelo método gráfico
O Problema do Pintor
Minimização
Restrições Redundantes
Solução Múltipla, Ilimitada e Inviável

w Casos w Caso Alumilâminas S.A. w Caso Esportes Radicais S.A w Problema da Fazenda w Problema da Mistura w Problema da Dieta w Problema do Estoqu w Análise de sensibilidade

2

Programação Matemática w 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.

Otimizar : z = f ( x1 , x 2 ,..., x n ) g 1 ( x1 , x 2 ,..., x n )   b1
≤
 g ( x , x ,..., x n )   b 2
Sujeito a : 2 1 2
=
:
≥ : g n ( x1 , x 2 ,..., x n )   b n

Variáveis de Decisão w w

x1 , x2,...,xn , são as chamadas Variáveis de Decisão.
As variáveis de decisão são aqueles valores que representam o cerne do problema, e que podemos escolher (decidir) livremente. w As variáveis de decisão representam as opções que um administrador têm para atingir um objetivo.
¦
Quanto produzir para maximizar o lucro?
¦
Quanto comprar de uma ação para minimizar o risco da carteira?

3

Programação Linear w Um problema de programação matemática é linear se a função objetivo e cada uma das funções que representam as restrições forem lineares, isto é, na forma abaixo:

f ( x1 , x 2 ,..., x n ) = c1 x1 + c 2 x 2 + ... + c n x n g i ( x 1 , x 2 , . . . , x n ) = a i 1 x 1 + a i 2 x 2 + . . . + a in x n

Quebrando a Linearidade w A presença de qualquer das expressões abaixo tornam o problema não linear.
Exemplos:
n

( x1 )n para n ≠ 1

log a (x1 ) para qualquer base a a x1 para qualquer valor de a

Exemplos

max x1 + x2

min x1 + 2 x2

s.r.

s.r.

2 x1 + 4 x2 ≤ 20

2 x1 + 3x2 ≥ 20

180x1 + 20x2 ≤ 600

180x1 + 20x2 = 600

x1 , x2 ≥ 0

x1 , x2 ≥ 0

4

Programação Linear
Áreas de Aplicação w w w w w Administração da Produção
Análise de Investimentos
Alocação de Recursos Limitados