Programación dinámica/Problema de la mochila

El tema que ocupa es solucionar el “problema de la mochila”, antes de ahondar en lo que recoge este concepto, sería conveniente ubicarlo en su ámbito de utilización.

El problema de la mochila representa un problema de programación entera, estando ésta última dentro del campo de la Programación Matemática. Veamos qué se entiende por cada uno de estos conceptos:

Programación matemática

El problema de Programación matemática se define como: “El criterio racional de distribución o asignación de recursos escasos entre fines competitivos en un instante de tiempo determinado”; es decir, que lo que trata de dilucidar es cómo un sujeto, - entendiendo por tal cualquier persona, empresa, asociación, Administración Pública, etc. que se plantee un problema de esta índole – debe escoger, basándose en criterios racionales, entre varias posibilidades la que de forma más certera le permita conseguir su objetivo.

Ejemplo: supóngase una empresa que fabrica caramelos de limón y de naranja de forma artesanal, para lo que utiliza azúcar y zumos de limón y naranja, respectivamente. Esta empresa incurre en los siguientes costes en el proceso de fabricación:

Zumo de naranja: 0’20 € / L

Zumo de limón: 0’25 € / L

Azúcar moreno: 0’30 € / kg

Azúcar blanca: 0’15 € / kg

Nota: de cada litro de zumo salen 100 caramelos y de cada kg de azúcar 10

Como máximo puede comprar 100 L de zumo de naranja y 50 L de zumo de limón. Necesita al menos 100 kg de azúcar moreno y 200 kg de azúcar blanca. El importe del que dispone para realizar estos insumos (compras) es de 100€.

Además sabe que:

• El coste de cada caramelo de limón es de 0 ’02 € / unidad y el precio de venta es de 0’06 € /ud
• El coste de cada caramelo de naranja es de 0 ’015 € / ud. y el precio de venta es de 0’05 € /ud

En este caso se desea determinar la asignación de recursos (zumos y azúcar) que permitirán obtener los mayores beneficios (diferencia entre ingresos por ventas y costes de fabricación), teniendo en cuenta la restricción presupuestaria de la empresa (los 100€ que como máximo puede emplear para la compra de materias primas). La resolución de este problema mediante programación matemática pasará por plantear el siguiente modelo:

Maximizar (0’06- 0’02) x1 + (0’05- 0’015) x2

sujeto a: (0’20/100) x1 ≤ 100

(0’25/100) x2 ≤ 50

(0’30/10) x1 + (0’30/10) x2 ≥ 100

(0’15/10) x1 + (0’15/10) x2 ≥ 200

x1 + x2 ≤ 100

x1, x2 ≥ 0

siendo x1 el número de caramelos de limón y x2 el número de caramelos de naranja

Una vez resuelto obtendremos el número óptimo de caramelos que la empresa debe fabricar para obtener el máximo beneficio posible.

Programación entera

Hay ocasiones en las que obtener una solución no entera, es decir, un número con decimales no resulta conveniente porque es incongruente con la situación que se está planteando en el problema. Pensemos, por ejemplo, en una empresa que fabrica pantalones y los distribuye a comercios minoristas (tiendas que venden directamente a consumidores finales y no a otras empresas para que éstas a su vez vendan a otras empresas). Esta empresa deberá comerciar con piezas enteras (pantalones terminados), por ello, para ella no sería válida una respuesta que le indicara que debe vender 1’75 pantalones para obtener beneficios.

Por tanto, denominaremos problema de programación entera a aquel en el que exijamos que todas las variables lo sean. Así, el planteamiento de un problema de Programación Entera es el siguiente:

Maximizar F(x) = C x

sujeta a: A x ≤ b

x ≥ 0

xi enteras con i =1,...,n

siendo "C" los coeficientes que acompañan a las variables (i.e. beneficio por pantalón), "A" las cantidades de los factores que han de ser utilizadas(i.e. cantidad de tela, de hilo),"b" la cantidad máxima disponible de cada recurso y "x" la variable objetivo (i.e. número de pantalones).

Ejemplo: la empresa Costuritas S.L. confecciona y comercializa camisas y pantalones vaqueros, para ello puede adquirir, como máximo, 50 m² tela vaquera al día. Sabe que para una camisa se requieren 1,5 m² de tela y para un pantalón 2 m².

Los requerimientos de personal responden a la siguiente tabla:

Personal Cortadores Tiempo Costureros Tiempo Planchadores Tiempo

Pantalones 1 1/3h 2 1/3h 1 1/6h

Camisas 3 1/3h 3 1/2h 1 1/4h

El número máximo de cortadores de tela que puede contratar es 12, debido a la disponibilidad de máquinas, el de costureros es 20 y el de planchadores 15.

Se ha estimado la demanda, y en el mejor escenario posible se ha obtenido la siguiente previsión de ventas: 18 pantalones, 16 camisas diarias.

El beneficio obtenido por cada pantalón vendido es de 15€, por cada camisa, se ganan 12'5€. Se desea saber qué producción es la que maximiza el beneficio anual de esta empresa.

A partir de los anteriores datos procederemos a plantear el problema, teniendo en cuenta que:

x1 = pantalones; x2 = camisas

Función a maximizar: 15 x1 + 12’5 x2

Número de cortadores y tiempo empleado en cada unidad: 1/3 x1 + 3/4 x2 ≤12

Número de costureros y tiempo empleado en cada unidad: 2/3 x1 + 3/2 x2 ≤20

Número de planchadores y tiempo empleado en cada unidad: 1/6 x1 + 1/4 x2≤15

Requerimientos de tela: 2 x1 +1’5 x2≤50

Producción máxima de pantalones al día: x1≤18

Producción máxima de camisas al día: x2 ≤16

Restricciones de no negatividad: x1, x2 ≥ 0

Maximizar 15 x1 + 12’5 x2

sujeto a: 1/3 x1 + 3/4 x2 ≤12

2/3 x1 + 3/2 x2 ≤20

1/6 x1 + 1/4 x2 ≤15

2 x1 +1’5 x2 ≤ 50

x1 ≤ 18

x2 ≤ 16

x1, x2 ≥ 0

De la resolución de este sistema se obtiene la siguiente solución: El beneficio máximo diario es de 336’67€, la producción que maximiza dicho beneficio es de 18 pantalones/día y 5 camisas/día. Como puede apreciarse tanto las camisas como los pantalones son un número entero.

El problema de la mochila, planteamiento teórico

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.

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.

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.

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)

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:

$Max\sum _{i=1}^{N}b_{i}x_{i}$

$s.a.\ x_{i}\in \{0,1\}\ \forall i=1\ldots N$

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.

Fuente

La fuente consultada para este punto (2.2) ha sido: FORMULACIÓN Y RESOLUCIÓN DE MODELOS DE PROGRAMACIÓN MATEMÁTICA EN INGENIERÍA Y CIENCIA de Enrique Castillo, Antonio J. Conejo, Pablo Pedregal, Ricardo García y Natalia Alguacil (20 de febrero de 2002)

Métodos de resolución

Este problema se ha resuelto tradicionalmente mediante Programación Lineal Entera, de la que se habló de forma genérica en la introducción.

Nota: en el punto 3 de este escrito, se resolverá de forma práctica un problema de mochila empleando este método.

El hecho de que se trate de programación Lineal hace referencia a que la función a optimizar y las inecuaciones que constituyen las restricciones han de ser lineales, es decir, han de ser funciones cuyas incógnitas estén elevadas exclusivamente a la unidad.

EJEMPLO:

(x +1) es una función lineal

(x +y +6) es una función lineal

(x +y + xy –5) no es lineal

(x^3 + y +6) no es lineal

(x^2 +1) no es lineal

(x^2*y –2) no es lineal

Existe otra forma de resolver este tipo de problema, a través de los denominados algoritmos voraces. Una aproximación voraz consiste en que cada elemento a considerar se evalúa una única vez, siendo descartado o seleccionado, de tal forma que si es seleccionado forma parte de la solución, y si es descartado, no forma parte de la solución ni volverá a ser considerado para la misma. Con este método no siempre es posible dar una solución a un problema.

Ejemplo: si continuamos con el ejemplo de “Escribe bien S.A.” vemos que la solución intuitiva que aportamos se corresponde con el método de algoritmos voraces comentado en el párrafo anterior.

Si quisiéramos resolver el problema mediante programación lineal entera tendríamos que plantear el modelo, del mismo modo que hicimos con Costuritas S.L. al comentar cómo se expresa un problema a solucionar por este método.

Otro sistema para resolver el problema de la mochila es mediante algoritmos genéticos que son métodos de optimización que tratan de hallar (xi,...,xn) tales que sea máximo.

Algoritmos voraces

a) Aplicación del método:

Partimos de la formulación del problema de la mochila aportada anteriormente:

Maximizar [Sumatoria (bi*xi) desde i= 1 hasta n]

sujeto a: xi Є {0,1} con i =1,..., n

[Sumatoria (ci*xi) desde i=1 hasta n] < P

La utilización de un algoritmo voraz consiste en introducir en la mochila según orden decreciente de utilidad (beneficio) los diversos objetos. En una primera etapa, se adicionarán unidades enteras hasta que, por motivo de capacidad, no sea posible seguir introduciendo enteros y haya que añadir la porción que quepa del siguiente objeto.

b) Concepto de solución óptima:

Teorema: si se ordenan los objetos de forma de decreciente en cuanto a su relación (utilidad/ponderación = bi/ci) y se introducen en la mochila enteros en este orden mientras quepan y cuando no quede capacidad para uno entero se añade la porción que aún tenga cabida el resultado al que se llega es una solución óptima.

Algoritmos genéticos

Consisten en métodos adaptativos de optimización que tratan de hallar (xi,...,xn) tales que [Sumatoria (bi*xi) desde i= 1 hasta n] sea máximo. Pueden usarse para resolver problemas de búsqueda y optimización. Se basan en el proceso genético de los organismos vivos, por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Para utilizar un algoritmo genético hacen falta tres elementos:

Descripción de la población de individuos: cada individuo representa una solución factible a un problema dado. A cada individuo se le asigna un valor ó puntuación, relacionado con la bondad de dicha solución.

Función de evaluación (llamada función de ajuste) : encontrar una expresión matemática que puntúe a cada individuo de forma que nuestro ideal sea un máximo o un mínimo.

Selección o Mecanismos de reproducción: la función de selección de padres más utilizada, es la denominada función de selección proporcional a la función objetivo, en la cual cada individuo tiene una probabilidad de ser seleccionado como padre que es proporcional al valor de su función objetivo, es decir, indica que cada objeto de la mochila tendrá una probabilidad de ser seleccionado que dependerá de la relación que exista entre beneficios y el peso que ocupa.

El problema de la mochila, desarrollo práctico:

NOTA: Este, al igual que todos los ejemplos incluidos en este trabajo, son fruto de la invención, todo parecido con la realidad o datos aportados no son vinculantes ni han sido obtenidos de ninguna fuente privada.

3.1. Planteamiento del problema

El Club Baloncesto Unicaja de Málaga ante la lesión de Daniel Santiago y la escasa aportación del pívot brasileño Vitor Faverani se plantea reforzar el juego interior para la disputa de los play-offs por el título a partir del 17 de mayo, para ello la secretaria técnica del equipo ha sondeado el mercado y ha encontrado a 5 jugadores que pueden adaptarse a lo requerido por el entrenador. Para reforzar el equipo el Unicaja dispone de un presupuesto máximo de 50.000 $ / mes. En la siguiente tabla aparece una relación de los candidatos a ser fichados junto con su aportación esperada y el sueldo que percibirían.

JUGADOR/EQUIPO SUELDO APORTACIÓN

Esteban Batista (Hawks) 50000 $ 15

Jared Reiner (Sioux Falls) 25200 $ 8

Chriss Burgess (Ulsan Phoebus) 36000 $ 15

Marcus Goree (Benetton) 47000 $ 17

K.C. Walekowski (Farho Vigo) 12000 $ 7

Como puede apreciarse, en este caso, estamos aplicando el problema de la mochila a una situación de índole económico. Nuestra intención es elegir los mejores jugadores –aquellos cuya aportación es mayor, es decir, los que proporcionan una mayor utilidad – para el Unicaja optimizando también el desembolso que conlleva una nueva contratación. Sin perder en ningún momento de vista la restricción de 50.000 $.

Formulación del problema

Una vez se ha planteado el problema, el siguiente paso lógico es formularlo en términos matemáticos, recuérdese que se está intentando llegar a una solución cuantitativa concreta y no simplemente intuitiva.

Maximizar 15x1 + 8x2 + 15x3 + 17x4 +7x5

sujeto a: 50000x1 + 25200x2 + 36000x3 + 47000x4 + 12000x5 < 50000

            x1,x2,x3,x4,x5 Є {0,1}

siendo:

x1 Esteban Batista (Hawks)

x2 Jared Reiner (Sioux Falls)

x3 Chriss Burgess (Ulsan Phoebus)

x4 Marcus Goree (Benetton)

x5 K.C. Walekowski (Farho Vigo)

El conjunto de ecuaciones que aparecen en las líneas precedentes constituyen la formulación matemática del problema que estamos tratando de resolver. Para una mejor comprensión del lector, analizaremos lo que representa cada una de ellas.

La primera ecuación: 15x1 + 8x2 + 15x3 + 17x4 +7x5 es la suma de las utilidades que reporta cada jugador, representa, por tanto, la utilidad que percibirá Unicaja en función de la combinación de jugadores que elija, puesto que se trata de la utilidad (en este caso, estará medida por el número de partidos que el jugador haga ganar o en los que tenga un peso importante) al club de Baloncesto le interesará que sea lo mayor posible. De ahí que el objetivo sea maximizar la función.

Las otras dos inecuaciones representan el conjunto de restricciones del problema, la primera de ella: 50.000x1 + 25.200x2 + 36.000x3 + 47.000x4 + 12.000x5 < 50.000, se corresponde con la expresión [Sumatoria (ci*xi) desde i=1 hasta n] < P, donde, los ci o pesos del objeto “i”, se corresponden con los salarios de cada jugador y las xi representan a cada jugador, al igual que ocurre en la ecuación anterior. P es la restricción presupuestaria del equipo, es decir, son los 50.000 $ mensuales de los que puede disponer para remunerar a sus nuevos jugadores.

La última inecuación: x1,x2,x3,x4,x5 Є {0,1}, trata de indicar que estamos ante un problema dicotómico en el que cada variable puede tomar sólo el valor 1 o el valor 0. En este caso, si x toma el valor 1 querrá decir que el jugador es contratado y si toma el valor 0, será señal de que el club prefiere prescindir de él.

Solución del problema planteado

El problema de elección que afronta el Club Baloncesto Unicaja se puede resolver por distintas vías:

- Por el método tradicional: a través de la maximización del problema anteriormente formulado mediante

   métodos de programación lineal entera.

- Por algoritmos: existen tipos de algoritmos (genéticos, voraces), pero en esta ocasión mostraremos el

   algoritmo más intuitivo y sencillo de ver. Este algoritmo es el denominado "voraz". Dejamos a un lado el
   algoritmo genético ya que al ser poco intuitivo y tener cierta complejidad (no en su teoría, sino en su
   práctica) podría hacer que el lector tuviera cierta reticencia a continuar con su lectura y comprensión.

Método tradicional(Programación Lineal Entera)

Retomemos el problema formulado e reinterpretemos dicha formulación para comprender mejor cómo vamos a resolver el problema de elección de jugadores (vamos a repetir de forma resumida el desarrollo del punto 3.2.)

Maximizar 15x1 + 8x2 + 15x3 + 17x4 +7x5

sujeto a: 50000x1 + 25200x2 + 36000x3 + 47000x4 + 12000x5 < 50000

            x1,x2,x3,x4,x5 Є {0,1}

Lo que pretendemos es maximizar el valor que los jugadores contratados aportarían al equipo, teniendo en cuenta que hay un presupuesto al que ajustarse (50000 $/mes). No hemos de olvidar que la solución a este problema habrá de darse en números enteros, ya que es imposible contratar una porción de jugador.

¿Por qué las variables sólo pueden tomar los valores “0” ó “1”?

- Si x =0 el jugador no debe ser contratado, ya que su aportación no maximizaría el valor aportado al equipo.

- Si x =1 el jugador deberá ser contratado, ya que su aportación maximizará el valor que los jugadores dan

   al equipo.

Con todo esto, y comprendida la formulación planteada, procedamos a resolver el problema con los métodos tradicionales. Aquí utilizaremos el programa Mathematica 5.0, el cual nos dará una rapidísima solución sin ninguna dificultad en su obtención.

Así lo introduciremos en Mathematica:

P =NMaximize[{15x1+8x2+15x3+17x4+7x5, 5000x1+25200x2+36000x3+47000x4+12000x5≤50000, x1≥0, x2≥0, x3≥0, x4≥0, x5≥0, x1≤1, x2≤1, x3≤1, x4≤1, x5≤1, x1$\in$Integers, x2$\in$Integers, x3$\in$Integers, x4$\in$Integers, x5$\in$Integers},{x1,x2,x3,x4,x5}]

Y la solución que obtendremos será la siguiente:

{22., {x1->0, x2->0, x3->1, x4->0, x5->1}

Esto es, contrataremos a los jugadores correspondientes a las variables 3 y 5: Chriss Burgess (del Ulsan Phoebus) y K.C. Walekowski (del Farho Vigo). Y haciendo esto obtendremos una aportación (utilidad para el equipo)de los jugadores al equipo de 22.

Algoritmos voraces

El método de algoritmo voraces es muy parecido a aquello que llaman "la cuenta de la vieja". Se trata, simplemente, de elegir la opción más lógica de acuerdo con un criterio. Para este ejemplo escogeremos como criterio el ratio "Aportación/Sueldo".

Parece lógico ponderarlo así, ya que tenemos en cuenta ambos factores en la decisión. Cuanto más alto sea este ratio, preferible será contratar a este jugador. Reconsideraremos el sueldo, dividiéndolo por 1000 para hacer el ratio más operativo, lo que obtendremos será llamado *Sueldo*.

Jugador (Equipo) *Sueldo* Aportación Ratio

Esteban Batista (Hawks) 50 15 0,3000

Jared Reiner (Sioux Falls) 25,2 8 0,3175

Chriss Burgess (Ulsan Phoebus) 36 15 0,4167

Marcus Goree (Benetton) 47 17 0,3617

K.C. Walekowski (Farho Vigo) 12 7 0,5833

Como hemos dicho, escogeremos aquellos jugadores con mejor ratio hasta agotar el presupuesto.

- K.C. Walekowski: ratio =0.58333, sueldo = 12000 $

- Chriss Burgess: ratio =0.41666, sueldo = 36000 $, total acumulado = 48000 $

Como no hay más jugadores cuyo sueldo pueda entrar en presupuesto, éste es nuestro resultado definitivo por algoritmos voraces.

El resultado que nos ofrece el método de algoritmos voraces coincide con el obtenido por el método tradicional. Aquí lógica y matemáticas puras coinciden y se refrendan mutuamente, por lo que la directiva del club no deberá tener dudas en la contratación de nuestros dos nuevos fichajes:

 - K.C. Walekowski

 - Chriss Burgess