Modelo de Corte com Heurística Gulosa

Prévia do material em texto

Aula 57
Módulo 6.7 – Modelos de Corte: 1 barra by A.A.
Pesquisa Operacional II
1
Heurística Gulosa
	Item	Utilidade (ui)	Volume (vi)	Razão (ui/vi)
	1	3	5	0,60
	2	3	4	0,75
	3	7	5	1,40
	4	2	3	0,33
	5	6	5	1,20
	6	7	8	0,88
	7	5	5	1,00
	8	8	9	0,89
b = 15 
Utilidade
Total: 18
Volume
Total: 15
2
Max 
S.a.:
MODELO COMPLETO GERAL
Utilidade total
Capacidade 
da mochila
Modelo Matemático de PLI
Número de itens
3
Utilidade
Total: 18
Volume
Total: 15
Modelo no GUSEK
b
Modelo de Corte
u1/v1
Número de vezes que um item é utilizado
Max
S.a.:
5
Modelo no GUSEK
Modelo no GUSEK
Modelo no GUSEK
b
Modelo de Corte
Total de facas
Max
S.a.:
9
Modelo no GUSEK
Modelo no GUSEK
Modelo no GUSEK
Aula 57
Módulo 6.7 – Modelos de Corte: 1 barra by A.A.
Pesquisa Operacional II
13
 
å
=
£
n
i
i
i
b
x
v
1
å
=
n
i
i
i
x
u
1
n
i
x
i
,
,
1
,
0
1
L
=
=
 
 
 
ou
 
n
i
x
u
x
i
i
i
,
,
1
,
inteiro
 
 
,
 
0
L
=
£
£
n
i
x
u
x
i
i
i
,
,
1
,
inteiro
 
 
,
 
0
L
=
£
£
 
1
å
=
£
n
i
i
F
x