Programação Linear Programação Linear - Prof. Helder Costa

Programação Linear1x

2x

0

Programação Linear - Prof. Helder Costa


O que é!

Uma disciplina no âmbito da pesquisa operacional

Busca a otimização de uma função objetivo, considerando o conjunto de soluções possíveis

Comportamento linear para função objetivo e e equações de restrição


Provocação:Exemplo Carpintaria

Uma fábrica de artefatos de madeira produz:• Mesa; e,

• Cadeira.

Quantas cadeiras e quantas mesas ela deve produzir?


Exemplo Carpintaria

Custo Preço de venda

Lucro

M 10 15 5

C 5 12 7

• Qual o objetivo?

• Minimizar custo?

• Maximizar receita?

• Maximizar lucro?


Exemplo Carpintaria:Escrevendo a função objetivo

Função objetivo para minimização dos custos• min (z) = 10*M + 5*C

Função objetivo para maximização da receita• max (z) = 15*M + 12*C

Função objetivo para maximização do lucro• min(z) = 5*M + 7*C


Lucro

M 10 15 5

C 5 12 7


Função objetivo:Forma geral para minimização

min (z) = c1*x1 + c2*x2 + ... + cn*xn

• C1 = Custo unitário de produção do ítem 1

• C2 = Custo unitário de produção do ítem 2

• Cn = Custo unitário de produção do ítem 3

• x1 = quantidade de produção do ítem 1




Função objetivo:Forma geral para maximização

max (z) = l1*x1 + l2*x2 + ... + ln*xn

• l1 = Lucro unitário de produção do ítem 1

• l2 = Lucro unitário de produção do ítem 2

• ln = Lucro unitário de produção do ítem 3





Análise gráfica da função objetivo

Z=12000

Z=600

Z=300

Direção de aumento de

“z = receita total”

Comportamento da função receita

0

10

20

30

40

50

60

70

80

90

100

0 80

Mesas

Cad

eira

s


Resultados da otimização:Exemplo Carpintaria


• produzir “zero” cadeiras• produzir “zero” mesas


• produzir um número “infinito” de cadeiras • produzir um número “infinito” de cadeiras

Função objetivo para maximização do lucro• max (z) = 5*M + 7*C

• produzir um número “infinito” de cadeiras • produzir um número “infinito” de cadeiras


Lucro

M 10 15 5

C 5 12 7


Provocação


Lucro

M 10 15 5

C 5 12 7

• Resultados para o objetivo?

• Minimizar custo?

• produzir “zero” cadeiras

• produzir “zero” mesas.

•Maximizar receita?

•Maximizar lucro?

• produzir um número “infinito” de cadeiras

• produzir um número “infinito” de cadeiras


Provocação 2

Há restrições?


Alguns tipos de restrições Mão de obra Tempo Energia Matéria Prima Capital disponível Fluxo de caixa Demanda Fornecimento Prazo ....


Exemplos de restrições para o problema da carpintaria

Produção mínima:• 10 cadeiras

• 5 mesas

Produção máxima• 60 mesas

• 90 cadeiras


Representação gráfica das restrições: região de soluções factíveis

Região de soluções factíveis/viáveis

0

10

20

30

40

50

60

70

80

90

100

0 80

Mesas

Cad

eira

s

X2=20

X1=10

X1=60

X2=90


Representação gráfica das restrições: região de soluções factíveis

Região de soluções factíveis/viáveis

0

10

20

30

40

50

60

70

80

90

100

0 80

Mesas

Cad

eira

s

Região viável


Ponto ótimo?

0

10

20

30

40

50

60

70

80

90

100

0 80

Mesas

Cad

eira

s

Região viável

Z=600

Z=300



Z=12000


Ponto ótimo?

0

10

20

30

40

50

60

70

80

90

100

0 80

Mesas

Cad

eira

s

Região viável

Z=12000

Z=600

Z=300



Ponto ótimo =

Receita máxima


Ponto ótimo?

0

10

20

30

40

50

60

70

80

90

100

0 80

Mesas

Cad

eira

s

Região viável

Z=12000

Z=600

Z=300



Ponto ótimo: Sempre um dos vértices da região factível


Programação linear:Escrevendo um modelo


• S.a:

• X1 >= 5

• X2 >= 10

• X1 =< 60

• X2 =< 90

• X1 , X2 : Inteiros



Função objetivo para maximização do lucro• max (z) = 5*M + 7*C

• S.a:

• X1 >= 5

• X2 >= 10

• X1 =< 60

• X2 =< 90





• S.a:

• X1 >= 5

• X2 >= 10

• X1 =< 60

• X2 =< 90


Programação Linear - Prof. Helder CostaProgramação Linear - Prof. Helder Costa

Exemplo da carpintaria 2

Disponibidade de recursosMaterial 1 Material 2 Material

3Máquina 1 Máquina 2

300 120 200 400 300

Produção RecursosLucro Mínima Máxima Material

1

Material

2

Material

3

Máquina

1

Máquina

2

M 5 5 60 4 2 0 4 3

C 7 10 90 4 0 2 2 2

B 8 --- 100 4 0 1 1 1


Exemplo da carpintaria:Modelo de programação Linear

Maximização do lucro• max (z) = 5*M + 7*C + 8*C • S.a:

• X1 >= 5

• X2 >= 10

• X3 >= 0

• X1 =< 60

• X2 =< 90

• X3 =< 100

• 4*M + 4*C + 4*C =< 300• 2*M =< 120• 2*C + 1*C =< 200• 4*M + 2*C + 1*C =< 400• 3*M + 2*C + 1*C =< 300

• X1 , X2 , X3 : Inteiros


Solução

Métodos• Simplex

• Pontos interiores

Sistemas computacionais de apoio• Lindo

• Lingo

• Matlab

• Excell (Solver)

Caso

Logística de armazéns e o Problema de Transportes


O Problema clássico

Transporte de itens ao custo mais baixo

Fontes com fornecimento fixo

Destinos com demandas constantes



Exemplo

Três armazéns

Três centros de consumo


Depósitos

Localidade Capacidade

Rio de Janeiro 500

Curitiba 600

Fortaleza 300

Total 1400


Mercados de consumo

Localidade Demanda

São Paulo 400

Belo Horizonte 300

Salvador 600

Total 1300


O problema de transporte

Localidade Demanda

São Paulo 400

Brasília 300

Salvador 600

Total 1300

Localidade Capacidade

Rio de Janeiro 500

Curitiba 600

Recife 300

Total 1400


Custos : Origem-Destino

Localidade São Paulo Brasília Salvador

Rio de Janeiro 5 8 12

Curitiba 6 10 15

Recife 30 25 7


Tableau

Para

De

Rio de Janeiro

Curitiba

Recife

Demanda

São Paulo Brasília Salvador Disponível

5

6

30

8

10

25

12

15

7

400 300 600

300

600

500



Solução ótima?Localidade São Paulo Brasília Salvador Capacidade Consumido Sobra

Rio de Janeiro 5 8 12 500 0

0 300 0 300 200

Curitiba 6 10 15 600 0

400 200 0 600 0

Recife 30 25 7 300 0

0 100 0 100 200

Demanda 400 600 200

Demanda atendida 400 600 300

Custos 2400 6900 0 9300


Exercício:

Elaborar o modelo de programação linear para a resolução do problema de transporte apresentado nas transparências anteriores.

XLS


Dúvidas?

Documents

Programação Linear Programação Linear - Prof. Helder Costa