Problema da Mochila Revistado

Prévia do material em texto

Aula 56
Módulo 6.6 – Problema da Mochila Revistado by A.A.
Pesquisa Operacional II
1
Quais itens devem ser colocados na mochila ?
Problema da Mochila
Utilidade
Volume
Fornecer uma nota para cada item (subjetivo !)
Medir para cada item (objetivo, mas dá muito trabalho !)
Para o trabalho:
Para o praia:
Criar lista:
Heurística Gulosa
Utilidade(U)
Volume(V)
Razão U/V
Item
7
7
5
6
3
4
CAP. MAX = 10
CAP. USADA = 
Heurística Gulosa
Utilidade(U)
Volume(V)
Razão U/V
Item
7
7
1.0
5
6
0.83
3
4
0.75
CAP. MAX = 10
CAP. USADA = 7
Heurística Gulosa
Utilidade(U)
Volume(V)
Razão U/V
Item
7
7
1.0
5
6
0.83
3
4
0.75
MAS...
CAP. MAX = 10
CAP. USADA = 10
Heurística Gulosa
Itens
Mochila
I1
I2
I3
I4
x1 = 1
x4 = 0
Variável de decisão: Item i participa (1) ou não (0) da Mochila
Problema Mochila Binária
u1
u4
Itens
Mochila
I1
I2
I3
I4
x1 = 1
x4 = 0
Máximo 
de itens
na mochila
M
Problema Mochila Binária
v1
v4
Max 
S.a.:
MODELO COMPLETO GERAL
Utilidade total
Capacidade 
da mochila
Modelo Matemático de PLI
Número de itens
9
 
# MODELO DO PROBLEMA DA MOCHILA
#
# Este problema encontra a mochila com o maior utilidade,
# respeitando a capacidade da mesma.
#
/* input data */
param n, integer, >= 1; # número de itens
param p, integer, >= 1; # capacidade da mochila
set E:={1..n}; # conjunto de itens
param u{E} >=0; # utilidade dos itens
param v{E} >=0; # volume dos itens
#Parametros para impressao dos resultados do modelo em arquivos.
param file, symbolic, default "ResumoMochila.txt";
/* Variável */
var x{E} binary;
/* Função Objetivo */
maximize TotalUtility: sum{i in E} u[i]*x[i];
/* Capacidade da Mochila */
s.t. capacity: sum{i in E} v[i]*x[i] <= p;
solve;
PARTE 1 - FORMULAÇÃO
Dados do modelo
Variáveis
Binárias
Modelo
Modelo no GUSEK
 
# MODELO DO PROBLEMA DA MOCHILA
#
# Este problema encontra a mochila com o maior utilidade,
# respeitando a capacidade da mesma.
#
/* input data */
param n, integer, >= 1; # número de itens
param p, integer, >= 1; # capacidade da mochila
set E:={1..n}; # conjunto de itens
param u{E} >=0; # utilidade dos itens
param v{E} >=0; # volume dos itens
#Parametros para impressao dos resultados do modelo em arquivos.
param file, symbolic, default "ResumoMochila.txt";
/* Variável */
var x{E} binary;
/* Função Objetivo */
maximize TotalUtility: sum{i in E} u[i]*x[i];
/* Capacidade da Mochila */
s.t. capacity: sum{i in E} v[i]*x[i] <= p;
solve;
PARTE 1 - FORMULAÇÃO
Modelo no GUSEK
11
/* RELATORIO */
printf '\n'
>> file;
printf '------------------------------------------------------\n'
>> file;
printf 'Solucao Encontrada \n'
>> file;
printf '------------------------------------------------------\n'
>> file;
printf ' \n'
>> file;
printf '------------------------------------------------------\n'
>> file;
printf " Item Alocação (1-Sim/0-Não) \n"
>> file;
printf{i in E} " %8s %8d \n", i, x[i]
>> file;
printf '------------------------------------------------------\n'
>> file;
printf 'Utilidade total (z): ' >> file;
printf ' %10.2f \n', TotalUtility >> file;
printf '----------------------\n' >> file;
printf '\n' >> file;
PARTE 2 -RELATÓRIO
Indica qual item foi alocado ou não na mochila ! 
Modelo no GUSEK
Fornece o valor da utilidade total da mochila !
/* Data section */
data;
param n:=3;
param p:=10;
param u:=[1] 7 [2] 5 [3] 3;
param v:= 1 7
 2 6
 3 4;
end;
PARTE 3 - DADOS
Dados do
Modelo
Modelo no GUSEK
/* Data section */
data;
param n:=3;
param p:=10;
param u:=[1] 7 [2] 5 [3] 3;
param v:= 1 7
 2 6
 3 4;
end;
PARTE 3 - DADOS
Modelo no GUSEK
PARTE 4 - RESULTADOS
Modelo no GUSEK
Aula 56
Módulo 6.6 – Problema da Mochila Revistado by A.A.
Pesquisa Operacional II
16
 
å
=
£
n
i
i
i
b
x
v
1
å
=
n
i
i
i
x
u
1
n
i
x
i
,
,
1
,
0
1
L
=
=
 
 
 
ou