Resenha de ihc

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (423 palavras )
  • Download(s) : 0
  • Publicado : 4 de março de 2013
Ler documento completo
Amostra do texto
Trabalho Prático de Heurística e Metaheurística
Relatório do Problema - Mochila Inteira Múltipla

Nome : Bruno Medeiros Rafael

Definição do Problema da Mochila Inteira Múltipla
O Problema daMochila (PM) é um problema de Otimização Combinatória cujo nome resulta de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores, com o objetivo depreenchê-la com o maior valor possível sem exceder o peso máximo admissível. É um problema bem conhecido na literatura e tem sido extensivamente estudado por diversos autores.
O problema da mochila é um dos 21problemas NP-completos de Richard Karp, exposto em 1972. A formulação do problema é extremamente simples, porém sua solução é mais complexa.
O problema da Mochila Inteira Múltipla (MIM) difere doanterior no sentido de que neste problema pode haver mais de uma unidade de cada item;

Modelagem do Problema

Onde:
xij = indica a quantidade de itens j alocados na mochila j;
uj = indica onúmero max de item j;
wj = indica o peso do item j;
Modelagem computacional
Para construir uma solução viável para o problema do MIM foi utilizado de 6 vetores e uma matriz, como detalhado a seguir:
W– Vetor que guarda o peso de cada item;
P – vetor que guarda o benefício(ou valor) de cada item;
Q – vetor que guarda a quantidade livre de cada item;
Moch_p - guarda o benefício de cada mochila;Moch_w – guarda peso de cada mochila
Moch_cap – guarda a capacidade de cada mochila
Esses três últimos vetores possuem o tamanho correspondente ao número de mochila.
Matriz – é uma matriz deNxM, onde N é o numero de itens e M é o número de mochilas do problema. Cada posição contém um número de um determinado tipo de item que esta na mochila.

Problema teste
* Vetor de Itens
Itens| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Peso (kg) | 15 | 18 | 13 | 23 | 9 | 10 | 11 | 5 | 14 | 5 |
Valor | 5 | 7 | 6 | 10 | 8 | 3 | 4 | 1 | 7 | 3 |
Quantidade | 2 | 3 | 2 | 3 | 2 | 2 |...
tracking img