Resenha de ihc

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 da Mochila (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 de preenchê-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 21 problemas 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 do anterior 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 o nú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 de NxM, 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 | 2