1. 2 O Problema do Corte Unidimensional Indústrias de papel, tecido, vidro, barras de aço, entre outras, fabricam seus produtos em peças de tamanho fixo

1

2

O Problema do Corte Unidimensional

Indústrias de papel, tecido, vidro, barras de aço , entre outras,fabricam seus produtos em peças de tamanho fixo (tamanhopadrão). Estas peças são depois divididas em tamanhosmenores a serem definidos de acordo com a necessidade docliente. O problema do corte consiste em determinar comocortar o menor número de peças de tamanho padrão L,atendendo a uma demanda , bi, por itens de tamanho li,

i=1,...,m.

3


Peça Padrão de tamanho L:

L

l1 l2 l3

Itens pedidos:

4


Esquemas de corte:Esquema 1:5 peças l1 l1 l1 l1 l1

L

l1

5


Esquemas de corte:Esquema 1:5 peças l1

Esquema 2:2 peças l2

l1 l1 l1 l1

L

l1

l2

L

l2

6


Esquemas de corte:Esquema 1:5 peças l1

Esquema 2:2 peças l2

Esquema 3:1 peça l2

2 peças l3

l1l1 l1 l1

L

l1

l2

L

l2

L

l2 l3 l3

7


Como Definir um Esquema de corte?Encontrar as soluções da seguinte equação:

Lylylyl mm ...2211

m1,...,j inteiro, e 0 jy

8

O Problema da Mochila Inteiro

Cxpxpxp nn ...2211

nnxvxvxv ...zmax 2211

m1,...,j inteiro, e 0 jx

9


Vamos considerar um problema onde:L = 170 cml1= 30 cm, l2=50cm, l3=55cm

e a demanda para os itens menores é:d1= 80, d2=120, d3=110

Quantos esquemas de corte são possíveis?

170555030 321 yyy1,2,3j inteiro, e 0 jy

10


Existem 27 esquemas de corte possíveis. Entre estes temos:

1

l1 0l2 0l3 1perda 115

170555030 321 yyy

11



1 19

l1 0 2l2 0 0l3 1 2perda 115 0

170555030 321 yyy

12



1 19 22

l1 0 2 3l2 0 0 1l3 1 2 0perda 115 0 30

170555030 321 yyy

13



1 19 22 23

l1 0 2 3 4l2 0 0 1 1l3 1 2 0 0perda 115 0 30 0

170555030 321 yyy

14



1 19 22 23 24

l1 0 2 3 4 1l2 0 0 1 1 2l3 1 2 0 0 0perda 115 0 30 0 5

170555030 321 yyy

15



1 19 22 23 24 27

l1 0 2 3 4 1 2l2 0 0 1 1 2 1l3 1 2 0 0 0 1perda 115 0 30 0 5 40

170555030 321 yyy

16

Construindo um modelo para o Problema do Corte Unidimensional

Neste problema temos:

elementos conhecidos:

17



elementos conhecidos: esquema de corte, demanda de cada ítem

18




elementos desconhecidos:

19




elementos desconhecidos: quantas vezes um determinado esquema

de corte será usado

20






objetivo a ser alcançado:

21






objetivo a ser alcançado: usar o menor número possível de

esquemas de corte

22







esquemas de corte

restrições:

23







esquemas de corte

restrições: o número de itens obtidos com os esquemas de corte

usados de ser maior ou igual a demanda

24


jx

VARIÁVEIS DE DECISÃO

Quantas vezes usar um determinado esquema de corte

Faça j = 1,2,3,...n representar os diversos esquemas de corte

Defina então: = número de vezes que o esquema de corte j será usado.

25


Objetivo aObjetivo aUsar o menor número possível de esquemas de corte:

Objetivo bObjetivo bSeja rj a perda associada ao esquema de corte jMinimizar a perda total:

nxxxz ...min 21

nnxrxrxrz ...min 2211

26


RestriçõesO número de itens obtidos de cada tipo deve ser maior ou

igual a demanda.

Seja aij o número de peças do tipo i obtidas usando o esquema de corte j. Para atender a demanda do item 1 temos que:

11212111 ... bxaxaxa nn

ininii bxaxaxa ...2211

De uma maneira geral, a restrição relativa ao item i é dada por:

27

Modelo de Otimização Para o Problema do Corte Unidimensional

(Objetivo a)(Objetivo a)

inteiras e ,0,...,...

.........

a sujeito...max)min(

21

2211

22222122

11212111

21

n

mnmnmm

nn

nn

n

xxxbxaxaxa

bxaxaxabxaxaxa

xxxzou

28

Modelo de Otimização Para o Problema do Corte Unidimensional

Podemos escrever as restrições do problema na forma matricial:

mnmnmm

n

n

b

bb

x

xx

aaa

aaaaaa

2

1

2

1

21

22221

11211

*...

.........

Observe que cada coluna da matriz esta associada aum esquema de corte.

Em geral n ==>

Impossível de ser gerado ou mesmo armazenado:Geração de colunas - Problema da Mochila

29

Problema do Corte Unidimensional Exemplo 1a

• Considerando apenas 6 padrões de corte:

inteiro,0,,,,,

11012080

112

021

014

013

202

100

a sujeito min

27242322191

27242322191

27242322191

xxxxxx

xxxxxx

xxxxxxz

30

Problema do Corte Unidimensional Exemplo 1a - Solução

Considerando apenas 6 padrões de corte:LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 115.0000

Usar:Usar:o o esquema de corte 19esquema de corte 19 55 vezes 55 vezes AAtt

19 19 = (2, 0, 2)= (2, 0, 2)o o esquema de corte 24esquema de corte 24 60 vezes 60 vezes AAtt

24 24 = (1,2, 0)= (1,2, 0) com sobra de 90 itens do tipo 1com sobra de 90 itens do tipo 1

31

Problema do Corte Unidimensional Exemplo 1b

• Considerando apenas 6 padrões de corte:

inteiro,0,,,,,

11012080

112

021

014

013

202

100

a sujeito 5400300115min

27242322191

27242322191

27242322191

xxxxxx

xxxxxx

xxxxxxz

32

Problema do Corte Unidimensional Exemplo 1b - Solução

Considerando apenas 6 padrões de corte:

LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 0.0000000E+00

Usar:Usar: o o esquema de corte 19esquema de corte 19 55 vezes 55 vezes AAtt

19 19 = (2, 0, 2)= (2, 0, 2) o o esquema de corte 23esquema de corte 23 120 vezes 120 vezesAAtt

23 23 = (4, 0, 1)= (4, 0, 1)teremos sobra de 510 itens do tipo 1teremos sobra de 510 itens do tipo 1

33

Esquemas de corte para o Problema do Corte Unidimensional - Exemplo 1

0 0 0 0 0 0 1 2 3 4 5 0 0 0 1 2 3 1 2 1 2 3 4 1 2 1 2

0 0 0 1 2 3 0 0 0 0 0 1 2 1 0 0 0 0 0 1 1 1 1 2 2 1 1

1 2 3 0 0 0 0 0 0 0 0 1 1 2 1 1 1 2 2 0 0 0 0 0 0 1 1

Existem 27 esquemas de corte

34

Problema do Corte Unidimensional Exemplo 1a - Solução

Considerando todos os esquemas de corte possíveis (27):

Usar:Usar: o o esquema de corte 3esquema de corte 3 30 vezes: 30 vezes:AAtt

3 3 = (0, 0, 3)= (0, 0, 3) o o esquema de corte 13esquema de corte 13 20 vezes 20 vezes AAtt

1313= (0, 2, 1)= (0, 2, 1)o o esquema de corte 25esquema de corte 25 40 vezes 40 vezesAAtt

2525= (2, 2,0)= (2, 2,0)

Não há sobra de itensNão há sobra de itens

Custo total = 90Custo total = 90

35

Problema do Corte Unidimensional Exemplo 1b - Solução

Considerando todos os esquemas de corte possíveis (27):

Usar:Usar:

o o esquema de corte 19esquema de corte 19 55 vezes: 55 vezes:

AAtt19 19 = (2, 0, 2)= (2, 0, 2)

o o esquema de corte 23esquema de corte 23 120 vezes 120 vezes AAtt

2323= (4, 1, 0)= (4, 1, 0)

Sobram 510 itens do tipo 1Sobram 510 itens do tipo 1

Custo total = 0Custo total = 0

Documents

1. 2 O Problema do Corte Unidimensional Indústrias de papel, tecido, vidro, barras de aço, entre outras, fabricam seus produtos em peças de tamanho fixo