TECNOLOGICO NACIONAL DE MEXICO.
TECNOLOGICO NACIONAL DE HERMOSILLO.
INGENIERIA EN GESTION EMPRESERIAL.
Materia:
Cadena de suministros
Actividad:
1.4 INVESTIGACIÓN
Alumna:
Lopez Sanchez Ana Sofia
Grupo:
G8A
Profesor de la asignatura:
Carlos Fernando Escoboza Valadez
Hermosillo, Sonora a 27 de febrero de 2024.
INVESTIGACIÓN
El problema de la mochila (Knaspack problem) es un problema clásico en los
problemas denominados COP (por sus siglas en inglés Combinatorial Optimization
Problem – Problemas de Optimización Combinatoria) de Inteligencia Artificial. Este
problema es considerado NP (Non Probabilistic Problem) ya que existe una
combinación 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, elección
múltiple, elección de un producto de diferentes categorías, como un problema
relacionado con el peso de los productos, como un problema relacionado con el
monto económico, entre otros. El presente trabajo tiene como objetivo dar un
panorama general de este problema y su aplicación en la vida real.
ALGORITMO BASE:
El algoritmo base, como se presenta en la descripción, está orientado hacia un
conjunto finito de artículos que tienen un peso específico y que deberán guardados
en un contenedor (mochila) con una capacidad limitada, teniendo como función
objetivo, el minimizar el espacio utilizado.
Las formulas 1 – 3 presentan el algoritmo básico del problema de la mochila (KP) [3]:
Where:
xj -> Variables de decisión
wj -> Peso w del item j
c -> Capacidad total del contenedor (mochila)
n -> número de items
La fórmula 1 hace referencia a maximizar los resultados del proyecto a partir de la
integración de múltiples variables que pertenecen al proyecto actual identificado por
el subíndice j. La fórmula 2 indica que es necesario estimar el peso total de los
artículos que serán guardados en un contenedor cuya capacidad es determinada
por la variable c. La fórmula 3 indica que las variables de decisión 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 número límite de artículos mj por ítem del tipo j, el
problema KP puede ser presentado de la siguiente manera (fórmulas 1.1, 2.1 y 3.1),
siendo una variante de la representación del problema base:
Cuando la variante se enfoca a un grupo de artículos ilimitados, el problema se
puede representar de la siguiente manera (fórmulas 1.2, 2.2 y 3.2):
Para la variante del Problema de la Mochila donde se pueden elegir múltiples ítems
de diferentes tamaños y beneficios, la variable de decisión afecta de manera directa
la función objetivo, definiendo, en las fórmulas 1.3, 2.3 y 3.3, la representación
matemática de esta variante:
El problema denominado 0-1 Knapsack Problem, se tienen un número k clases,
donde se puede elegir solo un ítem j, donde el número total de ítems seleccionados
para ocupar el contenedor, es presentado con la variable Ni, donde i=1,2, …, k y se
tiene como función objetivo, maximizar el beneficio (fórmulas 1.4, 2.4 y 3.4).
APLICACIONES
Como parte de la aplicación del Problema de la mochila como una forma de emular
situaciones reales donde es necesario acomodar artículos 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, tamaños y valores de beneficio. Por
otra parte, en la misma aduana, es necesario almacenar, de manera temporánea,
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 criptografía, en el caso de descifrar contraseñas, este problema se
puede ver como un número 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
artículos.
Como parte de la aplicación del problema de la mochila, y haciendo una revisión de
la literatura actual se pueden resolver problemas relacionados con:
La selección de proyectos, donde cada proyecto se puede como un
contenedor de diferentes ítems tales como: personas, recursos, etc. [16].
En la solución de problemáticas donde es necesario detectar patrones de
corte [17].
En situaciones donde se problemas de distribución de carga (física, eléctrica,
etc.) [18, 19].
Cuando se requiere abastecer vehículos de transporte y entrega de
productos de diferentes tamaños que deben ser colocados en múltiples
compartimentos de igual o diferente tamaño [20],
Asignación de procesadores y datos en sistemas distribuidos [21].
ALGORITMOS PROPUESTOS PARA DAR SOLUCIÓN
Para la solución del Problema de la Mochila, Fernández y Velázquez [13], proponen
la técnica de programación dinámica, empleando cuatro tipos de visualización: árbol
de recursión, grafo de dependencia, tabla de valores y tabla de decisiones.
Almeida, Giménez y López [14], mencionan que la experimentación es un factor clave
cuando se requiere ajustar una metaheurísticas a un problema; en este caso,
proponen, para la solución del Problema de la mochila, el uso de metaheurísticas
parametrizadas, mediante la combinación de parámetros.
Dorta et al. [15] proponen la ramificación y acotación como un método orientado a la
solución de Problemas de Optimización Combinatoria; como parte de su propuesta,
buscan reducir el número de soluciones factible mediante la exploración sistemática
del área de soluciones (árbol de soluciones), eliminando las soluciones que no son
mejores que la solución actual, eliminando la rama correspondiente y los subnodos
y hojas que dependen de ésta.
CONCLUSIONES
El problema de la mochila, es tal vez, el problema más analizado entre los
investigadores de Inteligencia Artificial, considerando que las variables son
identificadas con base en las características de los artículos que se guardarán en
un contenedor (mochila) con características relativas a la capacidad, a las
dimensiones o a la resistencia de los materiales. Y, por otra parte, su aplicación es
de forma directa a diversas situaciones de la vida real donde las variables
contempladas pueden emular dichas situaciones.
