El problema de la mochila, planteamiento teórico

El problema de la mochila, planteamiento teórico

[editar] Definición

Un problema típico de programación entera es el que nos ocupa, “el problema de la mochila”, que responde a la siguiente situación: imagínese hacer una excursión a la que solo podemos llevar una mochila que, lógicamente, tiene una capacidad limitada. Cada objeto que introducimos ocupa un volumen dentro de la misma y en contrapartida durante el viaje nos proporcionará un beneficio o utilidad (ejemplo: una cantimplora), el problema surge cuando debemos elegir qué objetos seleccionar para llevar en la mochila de forma que nuestro beneficio sea máximo (tengamos todo lo necesario) sin exceder su capacidad.

Esta situación se presenta con cierta frecuencia en los ámbitos económico e industrial, donde la mochila suele representar la restricción presupuestaria (cantidad máxima de recursos económicos de los que se dispone) y donde la utilidad de los objetos seleccionados se equipara a un beneficio económico por adquirir o llevar a cabo ciertas acciones.

Veamos a continuación un ejemplo de la aplicación del planteamiento de la mochila al ámbito económico.

Ejemplo: una empresa que fabrica lapiceros, “Escribe Bien S.A.” que en el ejercicio económico que se cierra ha obtenido un excedente de 300.000€ (su beneficio neto, una vez descontados los impuestos y retribuidos los fondos propios es de 300.000€), esto le hace replantearse una posible inversión productiva (ampliar la capacidad productiva, ampliar la fábrica, contratar más trabajadores,....) que le permita incrementar su cartera de productos (número de productos que tiene en el mercado). El gerente de la empresa, Don L, reúne a sus asesores financieros y comerciales para que determinen de forma conjunta qué productos serán los escogidos para la ampliación de cartera.

Los asesores comerciales sugieren los siguientes productos, basándose en estudios de mercado que han realizado para estimar la cifra de negocios que cada nuevo producto generará:

- Lápices de colores con un beneficio de 200.000 €, esta cuantía es la que relacionamos con la utilidad que mencionábamos en la definición.

- Gomas de borrar con un beneficio de 100.000 €

- Minas para portaminas con un beneficio de 250.000 €

- Carboncillos con un beneficio de 150.000 €

Por su parte, los asesores financieros han estudiado los costes que implica reformar las instalaciones productivas para poder incrementar la cartera de productos, estos costes se podrían equiparar al volumen que ocupan los objetos dentro de la mochila, por tanto, la suma de estos costes deberá ser menor a la capacidad de la mochila, en este caso, los recursos financieros sobrantes: 300.000€.

- Coste de las instalaciones para fabricar lápices de colores: 75.000 €

- Coste de las instalaciones para fabricar gomas de borrar: 150.000 €

- Coste de las instalaciones para fabricar minas para portaminas: 100.000 €

- Coste de las instalaciones para fabricar carboncillos: 50.000 €

Intuitivamente escogerá fabricar aquel producto que mayores beneficios le dé, si con la inversión en la fabricación de ese nuevo producto no consume los 300.000 € podrá plantearse aumentar aún más su cartera y así sucesivamente mientras le resten recursos.

[editar] Formulación

Para facilitar la comprensión del lector, antes de incorporar a este escrito la formulación del problema, analizaremos las partes de las que se compone la misma.

[editar] Datos del problema

- n: número de objetos entre los que se puede elegir.

- ci : peso del objeto “i” - se refiere el objeto “í”-ésimo que no es más que una forma de hacer referencia a un objeto cualquiera que pueda ser incluido en la mochila -, es decir, ci representa el coste de escoger un objeto, en tanto en cuanto va a ocupar un “espacio de la mochila” que dejará fuera otros objetos.

- bi: utilidad o beneficio que proporciona cada objeto, de nuevo se hace referencia al objeto i-ésimo.

- P: capacidad de la mochila, equivale al presupuesto máximo del que se dispone.

[editar] Variables a tener en cuenta

Los elementos a introducir en la mochila van a ser nuestras variables objeto de análisis, cada variable la denotaremos como xi. El rasgo más importante de nuestras xi es que se tratan de variables dicotómicas o binaria, es decir, sólo pueden tomar dos valores, en este caso, escogeremos el valor “1” (si el objeto se incluye en la mochila) ó “0” (si el objeto se excluye de la mochila)

[editar] Restricciones

La restricción vendrá marcada por la capacidad máxima de la mochila, de tal forma que la suma de todos los objetos multiplicados por el espacio que ocupan en la mochila no podrá exceder dicha capacidad máxima. Su formulación matemática es la que sigue:

Función a maximizar

Tal y como se expresa en la definición, el objetivo de este problema es seleccionar aquellos objetos que introducidos en la mochila nos proporcionan una mayor utilidad. En otras palabras, lo que debemos hacer es maximizar la utilidad de nuestra mochila.

Si redefinimos el problema introduciendo los elementos que mencionamos en las líneas precedentes llegaremos a la siguiente formulación:

“El problema de la mochila consiste en llenar una mochila con n objetos. Cada objeto i tiene un peso determinado ci siempre positivo y una utilidad o valor asociado, también positivo, bi. Se ha de considerar además que la mochila tiene una capacidad limitada P, por tanto, se han de escoger aquellos objetos xi que maximicen la utilidad de quien llena la mochila sin exceder su capacidad”.

Ahora procederemos a formular el problema de la mochila:

[pic 1]

Nota: pueden existir otras restricciones técnicas que nada tengan que ver con las anteriormente citadas que serían comunes a cualquier problema de Programación Matemática.

[editar] Fuente

1.6 Usos De Programas De Computadora.

Se utilizaron como apoyo para dar solución a problemas requiriendo algún software, por ejemplo winqsb.

Ingresando el problema a WINQSB.

El programa maneja 3 tipos de problemas los cuales pueden ser:

• La diligencia (la Ruta más Corta) el Problema.
• El Problema de la mochila.
• La producción y Planificación del inventario.

Ejemplo 1 Problema de la diligencia (Stagecoach Problem):

...