1
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 (tamanho
padrão).
Estas peças são depois divididas em tamanhos
menores a serem definidos de acordo com a necessidade do
cliente.
O problema do corte consiste em determinar como
cortar 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.
2
O Problema do Corte
Unidimensional
Peça Padrão de tamanho L:
L
Itens pedidos:
l1
l2
l3
3
O Problema do Corte
Unidimensional
Esquemas de corte:
Esquema 1:
5 peças l1
L
l1 l1 l1 l1
l1
4
O Problema do Corte
Unidimensional
Esquemas de corte:
Esquema 1:
5 peças l1
Esquema 2:
2 peças l2
L
l1 l1 l1 l1
l1
L
l2
l2
5
O Problema do Corte
Unidimensional
Esquemas de corte:
L
Esquema 1:
5 peças l1
Esquema 2:
2 peças l2
Esquema 3:
1 peça l2
2 peças l3
l1 l1 l1 l1 l 1
L
l2
l2
L
l2
l3
l3
6
O Problema do Corte
Unidimensional
Como Definir um Esquema de corte?
Encontrar as soluções da seguinte equação:
l1 y1  l2 y2  ...  lm ym  L
y j   0 e i nte i ro,j  1,...,m
7
O Problema da Mochila Inteiro
maxz  v1 x1  v2 x2  ...  vn xn
p1 x1  p2 x2  ...  pn xn  C
x j   0 e i nte i ro,j  1,...,m
8
O Problema do Corte Unidimensional
Vamos considerar um problema onde:
L = 170 cm
l1= 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?
30 y1  50 y2  55 y3  170
y j  0 e i nte i ro,j  1,2,3
9
O Problema do Corte Unidimensional
Existem 27 esquemas de corte possíveis. Entre estes temos:
1
l1
l2
l3
perda
0
0
1
115
30 y1  50 y2  55 y3  170
10
O Problema do Corte Unidimensional
Existem 27 esquemas de corte possíveis. Entre estes temos:
l1
l2
l3
perda
1
19
0
0
1
115
2
0
2
0
30 y1  50 y2  55 y3  170
11
O Problema do Corte Unidimensional
Existem 27 esquemas de corte possíveis. Entre estes temos:
l1
l2
l3
perda
1
19
22
0
0
1
115
2
0
2
0
3
1
0
30
30 y1  50 y2  55 y3  170
12
O Problema do Corte Unidimensional
Existem 27 esquemas de corte possíveis. Entre estes temos:
l1
l2
l3
perda
1
19
22
23
0
0
1
115
2
0
2
0
3
1
0
30
4
1
0
0
30 y1  50 y2  55 y3  170
13
O Problema do Corte Unidimensional
Existem 27 esquemas de corte possíveis. Entre estes temos:
l1
l2
l3
perda
1
19
22
23
24
0
0
1
115
2
0
2
0
3
1
0
30
4
1
0
0
1
2
0
5
30 y1  50 y2  55 y3  170
14
O Problema do Corte Unidimensional
Existem 27 esquemas de corte possíveis. Entre estes temos:
l1
l2
l3
perda
1
19
22
23
24
27
0
0
1
115
2
0
2
0
3
1
0
30
4
1
0
0
1
2
0
5
2
1
1
40
30 y1  50 y2  55 y3  170
15
Construindo um modelo para o Problema do Corte
Unidimensional
Neste problema temos:
elementos conhecidos:
16
Construindo um modelo para o Problema do Corte
Unidimensional
Neste problema temos:
elementos conhecidos: esquema de corte, demanda de cada ítem
17
Construindo um modelo para o Problema do Corte
Unidimensional
Neste problema temos:
elementos conhecidos: esquema de corte, demanda de cada ítem
elementos desconhecidos:
18
Construindo um modelo para o Problema do Corte
Unidimensional
Neste problema temos:
elementos conhecidos: esquema de corte, demanda de cada ítem
elementos desconhecidos: quantas vezes um determinado esquema
de corte será usado
19
Construindo um modelo para o Problema do Corte
Unidimensional
Neste problema temos:
elementos conhecidos: esquema de corte, demanda de cada ítem
elementos desconhecidos: quantas vezes um determinado esquema
de corte será usado
objetivo a ser alcançado:
20
Construindo um modelo para o Problema do Corte
Unidimensional
Neste problema temos:
elementos conhecidos: esquema de corte, demanda de cada ítem
elementos desconhecidos: quantas vezes um determinado esquema
de corte será usado
objetivo a ser alcançado: usar o menor número possível de
esquemas de corte
21
Construindo um modelo para o Problema do Corte
Unidimensional
Neste problema temos:
elementos conhecidos: esquema de corte, demanda de cada ítem
elementos desconhecidos: quantas vezes um determinado esquema
de corte será usado
objetivo a ser alcançado: usar o menor número possível de
esquemas de corte
restrições:
22
Construindo um modelo para o Problema do Corte
Unidimensional
Neste problema temos:
elementos conhecidos: esquema de corte, demanda de cada ítem
elementos desconhecidos: quantas vezes um determinado esquema
de corte será usado
objetivo a ser alcançado: usar o menor número possível de
esquemas de corte
restrições: o número de itens obtidos com os esquemas de corte
usados de ser maior ou igual a demanda
23
Construindo um modelo para o Problema do Corte
Unidimensional
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:
x j = número de vezes que o esquema de corte j será usado.
24
Construindo um modelo para o Problema do Corte
Unidimensional
Objetivo a
Usar o menor número possível de esquemas de corte:
minz  x1  x2  ...  xn
Objetivo b
Seja rj a perda associada ao esquema de corte j
Minimizar a perda total:
minz  r1 x1  r2 x2  ...  rn xn
25
Construindo um modelo para o Problema do Corte
Unidimensional
Restrições
O 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:
a11 x1  a12 x2  ...  a1n xn  b1
De uma maneira geral, a restrição relativa ao item i é dada por:
ai 1 x1  ai 2 x2  ...  ain xn  bi
26
Modelo de Otimização Para o Problema do Corte
Unidimensional
min(ou max)z  x1  x 2  ...  x n
sujeit o a
(Objetivo a)
a11 x1  a12 x 2  ...  a1n x n  b1
a 22 x1  a 22 x 2  ...  a 2 n x n  b2
...
a m1 x1  a m 2 x 2  ...  a mn x n  bm
x1 , x 2 ,...x n  0, e int eiras
27
Modelo de Otimização Para o Problema do Corte
Unidimensional
Podemos escrever as restrições do problema na forma
matricial:
 a11 a12 ... a1n
a
 21 a 22 ... a 2 n
 ...

a m1 a m 2 ... a mn

  x1   b1 
 x  b 
  2  2 
 *     
    
  x n  bm 
    
Observe que cada coluna da matriz esta associada a
um esquema de corte.
Em geral n ==> 
Impossível de ser gerado ou mesmo armazenado:
Geração de colunas - Problema da Mochila
28
Problema do Corte Unidimensional
Exemplo 1a
• Considerando apenas 6 padrões de corte:
min z  x1  x19 
x22 
x23 
x24  x27
sujeito a
0   2 
 3
 4
1 
 2
0 x  0 x  1 x  1 x  2 x  1 x
  1   19   22   23   24   27
1 2
0
0
0
1
 80 
 120
110
x1 , x19 , x22 , x23 , x24 , x27  0, inteiro
29
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:
o esquema de corte 19 55 vezes
At19 = (2, 0, 2)
o esquema de corte 24 60 vezes
At24 = (1,2, 0)
com sobra de 90 itens do tipo 1
30
Problema do Corte Unidimensional
Exemplo 1b
• Considerando apenas 6 padrões de corte:
minz  115x1 
0 x19 
30x22 
0 x23 
40x24  5 x27
sujeitoa
 0
 2
 3
 4
1 
 2
 80 
0 x  0 x  1 x  1 x   2 x  1 x  120
  1   19   22   23   24   27  
1
 2
0
0
0
1
110
x1 , x19 , x22 , x23 , x24 , x27  0, inteiro
31
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:
o esquema de corte 19 55 vezes
At19 = (2, 0, 2)
o esquema de corte 23 120 vezes
At23 = (4, 0, 1)
teremos sobra de 510 itens do tipo 1
32
Esquemas de corte para o Problema do Corte
Unidimensional - Exemplo 1
000000123450001231212341212
000123000001210000011112211
123000000001121112200000011
Existem 27 esquemas de corte
33
Problema do Corte Unidimensional
Exemplo 1a - Solução
Considerando todos os esquemas de corte possíveis (27):
Usar:
o esquema de corte 3 30 vezes:
At3 = (0, 0, 3)
o esquema de corte 13 20 vezes
At13= (0, 2, 1)
o esquema de corte 25 40 vezes
At25= (2, 2,0)
Não há sobra de itens
Custo total = 90
34
Problema do Corte Unidimensional
Exemplo 1b - Solução
Considerando todos os esquemas de corte possíveis (27):
Usar:
o esquema de corte 19
55 vezes:
At19 = (2, 0, 2)
o esquema de corte 23 120 vezes
At23= (4, 1, 0)
Sobram 510 itens do tipo 1
Custo total = 0
35