Ingeniera en Gestin Empresarial

Materia: cadena de suministro

Proyecto: Mochila Knapsack
PROFESOR: Porras Sandoval Aldo David
Alumnos: Jhonatan Isaid Martnez lvarez
Abel Valenzuela
Brenda Saracho
Cesar Alvarado
Jesus Guillermo
Victoria de Durango 04/09/2017

1
Problema de la mochila Knapsack
El problema de la mochila es un problema simple, hay una persona que tiene una mochila con
una cierta capacidad y tiene que elegir que elementos pondr en ella.

Cada uno de los elementos tiene su peso y aporta un beneficio sin excederse de la capacidad
permitida.Este problema es considerado NP ya que existe una combinacin exponencial de
instancias que, en su totalidad, no pueden ser resueltas. Existen variantes relacionadas con
este problema: problema con cantidad de productos limitada, problema con cantidad de
productos ilimitada, eleccin mltiple, eleccin de un producto de diferentes categoras, como
un problema relacionado con el peso de los productos, como un problema relacionado con el
monto econmico, entre otros.
La Mochila que es conocido como un Problema de Optimizacin Combinatoria de tipo NP-hard.
Este problema es una generalizacin de los problemas donde se tiene un contenedor (mochila)
con o sin restricciones, y donde la solucin base es mediante la programacin entera
dicotmica.
DEFINICIN
El problema de la mochila (KP) puede ser definido con un conjunto de n artculos donde cada
artculo es identificado por nx, con un valor entero px, y un peso wx. El problema consiste en
elegir un subconjunto de n artculos maximizando el beneficio obtenido considerando el peso
total de los artculos seleccionados, sin exceder la capacidad c de la mochila [2].
Dorta et al. [15], definen el Problema de la mochila de la siguiente manera: Se dispone de una
mochila de capacidad C y de un conjunto de N objetos, donde los objetos son indivisibles.
Describen a un objeto k que tiene un beneficio bk y un peso pk, para k = 1,2,, N. Para los
autores, el problema consiste en averiguar qu objetos se pueden insertar en la mochila sin
exceder la capacidad total de la misma, obteniendo el mximo beneficio.
ALGORITMO BASE
El algoritmo base, como se presenta en la descripcin, est orientado hacia un conjunto finito
de artculos que tienen un peso especfico y que debern guardados en un contenedor (mochila)
con una capacidad limitada, teniendo como funcin objetivo, el minimizar el espacio utilizado.
Las formulas 1 3 presentan el algoritmo bsico del problema de la mochila (KP) [3]:

Donde:

2
xj -> Variables de decisin
wj -> Peso w del item j
c -> Capacidad total del contenedor (mochila)
n -> nmero de items
La frmula 1 hace referencia a maximizar los resultados del proyecto a partir de la integracin
de mltiples variables que pertenecen al proyecto actual identificado por el subndice j. La
frmula 2 indica que es necesario estimar el peso total de los artculos que sern guardados en
un contenedor cuya capacidad es determinada por la variable c. La frmula 3 indica que las
variables de decisin pertenecen al proyecto identificado por el valor j, es decir, forman parte
del proyecto (valor 1) o no forman parte de dicho proyecto (valor 0)
VARIANTES DEL PROBLEMA
La variante donde se tiene un nmero lmite de artculos mj por tem del tipo j, el problema KP
puede ser presentado de la siguiente manera (frmulas 1.1, 2.1 y 3.1), siendo una variante de
la representacin del problema base:

Cuando la variante se enfoca a un grupo de artculos ilimitados, el problema se puede

representar de la siguiente manera (frmulas 1.2, 2.2 y 3.2):

Para la variante del Problema de la Mochila donde se pueden elegir mltiples tems de diferentes
tamaos y beneficios, la variable de decisin afecta de manera directa la funcin objetivo,
definiendo, en las frmulas 1.3, 2.3 y 3.3, la representacin matemtica de esta variante:

3
El problema denominado 0-1 Knapsack Problem, se tienen un nmero k clases, donde se puede
elegir solo un tem j, donde el nmero total de tems seleccionados para ocupar el contenedor,
es presentado con la variable Ni, donde i=1,2, , k y se tiene como funcin objetivo, maximizar
el beneficio (frmulas 1.4, 2.4 y 3.4).

APLICACIONES
Como parte de la aplicacin del Problema de la mochila como una forma de emular situaciones
reales donde es necesario acomodar artculos de diferentes dimensiones en un espacio
reducido.
Se puede emplear, como ejemplo, el uso de contenedores en las aduanas, donde se requiere
enviar tems de diferentes pesos, tamaos y valores de beneficio. Por otra parte, en la misma
aduana, es necesario almacenar, de manera tempornea, los contenedores mismos, por lo que
este problema puede ser resuelto con base en la soluciones propuesta para el problema de la
mochila.
En aspectos de criptografa, en el caso de descifrar contraseas, este problema se puede ver
como un nmero de contenedores que pueden tener n valores cada uno. En otro sentido,
cuando es necesario traducir un texto encriptado, en el momento de identificar los espacios,
cada palabra puede fungir como un contenedor de ni tems (caracteres de la palabra), donde
cada caracter i puede tener n posibles artculos.
Como parte de la aplicacin del problema de la mochila, y haciendo una revisin de la literatura
actual se pueden resolver problemas relacionados con:

La seleccin de proyectos, donde cada proyecto se puede como un contenedor de

diferentes tems tales como: personas, recursos, etc. [16].
En la solucin de problemticas donde es necesario detectar patrones de corte [17].

4
 En situaciones donde se problemas de distribucin de carga (fsica, elctrica, etc.) [18, 19].
Cuando se requiere abastecer vehculos de transporte y entrega de productos de
diferentes tamaos que deben ser colocados en mltiples compartimentos de igual o
diferente tamao [20],
Asignacin de procesadores y datos en sistemas distribuidos.
Despediciar la menor cantidad de materiales(materiales limitante)
Aprovechar al mximo el uso de las maquinas (tiempo limitante)

Se utiliza para modelar diferentes situaciones

En los sistemas de apoyo de fianza:para encontrar el mayor eqwuilibrio entre el

capital y el redimnmiientpo financiero.
En la carga del barco o del avin :todo el equipaje debe ser llevado ,sin ser
sobrecargado .
En el corte de materiales:para minizar las cadas.
CONCLUSIONES

El problema de la mochila, es tal vez, el problema ms analizado entre los investigadores de

Inteligencia Artificial, considerando que las variables son identificadas con base en las
caractersticas de los artculos que se guardarn en un contenedor (mochila) con caractersticas
relativas a la capacidad, a las dimensiones o a la resistencia de los materiales. Y, por otra parte,
su aplicacin es de forma directa a diversas situaciones de la vida real donde las variables
contempladas pueden emular dichas situaciones

EJEMPLO PRCTICO
Problema de la Mochila
Un armador tiene un carguero con capacidad de hasta 700 toneladas. El carguero
transporta contenedores de diferentes pesos para una determinada ruta. En la ruta
actual el carguero puede transportar algunos de los siguientes contenedores:

El analista de la empresa del armador desea determinar el envo (conjunto de

contenedores) que maximiza la carga transportada. Para ello se propone el
siguiente modelo de Programacin Entera:
Variables de Decisin:
Funcin Objetivo: Consiste en maximizar la carga que transportar el carguero.

5
Restricciones: El peso de la carga transportada no puede exceder la capacidad
mxima del carguero.

La solucin ptima consiste en transportar los contenedores C1, C2, C3, C4, C8,
C9 y C10, con un valor ptimo de 700 (toneladas), es decir, se utiliza la capacidad
completa del carguero. Notar que otra solucin ptima consiste en transportar los
contenedores C1, C3, C4, C5, C6, C7, C8 y C9 lo que reporta un similar valor en la
funcin objetivo.