Algoritmo del problema de la mochila mediante un ejemplo

Universidad del Caribe
Investigación de Operaciones Estocásticas
Algoritmo Modelo de la
Mochila
 Elaborado por:
 Hernández Pedraza Yahaira Sarahy 110300144
 Ing. Logística y Cadena de Suministro

Introducción
El modelo de la mochila tiene que ver clásicamente con el
hecho de determinar los artículos más valiosos que un
combatiente carga en una mochila.
El problema representa unmodelo de asignación de recursos
general en el cual se utilizan recursos limitados por varias
actividades económicas.
Y cuyo objetivo es maximizar el rendimiento total.
Para desarrollar el algoritmo se tomaran los datos del ejemplo
del barco de 4 toneladas de carga.

Definición del problema
Un barco de 4 toneladas se carga con uno o más de
tres artículos. La tabla siguiente muestra el pesounitario, wi, en toneladas, y el ingreso por unidad ri,
en miles de dólares, para el artículo i.
¿Cómo se debe cargar el barco para maximizar los
ingresos totales?

1

2

31

2

3

47

3

1

14

Paso 1.- Definir:
• Los n artículos (o n etapas) que se asignarán al barco. Para
este ejemplo, ya citado, el número de artículos es 3, este
dato es por lo tanto el número deetapas es tres.
• La capacidad (W) es de 4 toneladas
• Entender como la cantidad de unidades del articulo i (mi)
que pueden caber en el barco.

• El rendimiento o ingreso unitario (ri ), estos son para cada
articulo $31, $47 y $14.
• El peso unitario del articulo i, (wi ) para cada articulo el peso
unitario es de 2 ton, 3 ton y 1 ton.

Paso 2.- Definir
• El objetivo: es maximizar losingresos totales
aprovechando la máxima capacidad del barco.
• Variables: estas son mi = número de artículos del articulo i
a meter en el barco, donde i= 1,2,3
y estos valores
deben ser enteros.
• Función Objetivo: esta es Maximizar Z= 31m1 +47m2 +14m3
(son los ingresos de cada articulo por la variable mi o
número de artículos del articulo i para cargar el barco).
• La F.O. esta sujeta a larestricción de que el peso unitario
de cada articulo multiplicado por el número de artículos
que se obtenga en la solución no sea mayor a la capacidad
del barco, la cual es de 4 toneladas (2m1+ 3m2+ 1m1 ≤ 4
toneladas)
• Condición de No negatividad, es la siguiente: mi ≥ 0

Paso 3. Definir Ec. de Recursividad.
• Ecuación de la Recursividad, donde fi(xi) es el
rendimiento máximo para lasetapas i, i+1, y n, dado el
estado x del barco.

Paso 4.- Establecer el Inicio del procedimiento:
Los n artículos serán igual al número de etapas a evaluar,
por lo tanto el proceso como es de recursividad, inicia con
la última etapa. Comenzaremos en la etapa 3.

Paso 5. Evaluando la etapa 3
Paso 5.1 Primero definiremos la variabilidad de mi en
otras palabras los valores posibles que sesustituirán en la
etapa i, con la formula: mi = W/wi
Explicación del Paso 5.1 para determinar la variabilidad o
número de productos que pueden caber en el barco del
articulo tres , se sigue la formula: mi = W/wi .
Sustituyendo obtenemos que m3 es igual a 4 ton entre 1
tonelada del articulo 3, esto es igual a 4. Por lo tanto m3
puede tomar valores de 0 a 4.

Paso 5. Evaluando la etapa 3Paso 5.2 Definir los posibles estados de capacidad de Xi en
la etapa i.

Explicación del paso 5.2 X3 puede tomar estados de
capacidad del barco por ejemplo 0 no se ha metido
ningún producto del articulo 3 por lo tanto el barco esta
vacío, y así hasta que sea 4 lo cual se entiende que el
barco esta al tope de capacidad o sea lleno.

Paso 5. Evaluando la etapa 3
Paso 5.3 Resolver laecuación de recursividad
sustituyendo los valores de la variación de mi .
Explicación del paso 5.3 Por consiguiente sustituimos mi en la
Ecuación de Recursividad. Como es la etapa de inicio y no existe una
etapa superior que cumpla con la especificación de fi+1, solo se
multiplicará el valor a sustituir de m3 por el ingreso que genera una
unidad del articulo 3, en este caso es $14.

Paso 5....