Me dirás: “¿Qué tiene los vuelos low cost y el problema de la mochila con las matemáticas?”. Intentaremos responder a esta pregunta a continuación.

El problema de la maleta de mano (o problema de la mochila):

Cualquiera que haya emprendido alguna vez un viaje con el objetivo de ahorrar dinero en un vuelo low cost sabe muy bien que hacer una maleta respetando los límites establecidos para el equipaje de mano es todo menos pan comido.

Probablemente, sin embargo, no todos ustedes saben que este problema, tradicionalmente conocido como el "problema de la mochila", es más bien un problema matemático complejo. No entraré en el detalle de explicar lo complejo que es. Para los curiosos, os remitimos a la entrada de wikipedia sobre problemas de NP-Complete .

Si la cosa se limitara a preparar una mochila respetando un peso determinado, podríamos pensar que este problema merecería especial atención.

El hecho es, sin embargo, que muchos problemas reales se remontan en última instancia al problema de la mochila. La belleza de las matemáticas suele ser esta: te enfrentas a un problema y luego descubres que puedes usar esa misma forma de resolverlo en muchos otros contextos.

Estos son solo algunos ejemplos:

Modelo matemático: formalicemos el problema de la mochila 0-1

Así que veamos cómo formalizar el problema de la mochila expresándolo en lenguaje matemático. También en este caso, las matemáticas demostrarán ser absolutamente efectivas (matematicas aplicadas ).

Analizaremos aquí solo el caso en el que los objetos no se pueden dividir pero solo se puede elegir si ponerlos en la mochila (tomamos 1) o no ponerlos en la mochila (tomamos 0). En el caso de nuestro ejemplo inicial de equipaje de mano, tiene mucho sentido imponer la opción 0-1 también porque llevar medio suéter no es muy útil.

Señalamos que también existe la versión fraccionada del mismo problema (en lugar de darme por vencido y llevar un queso entero, me llevé  una fracción de un queso; una cuña de queso!).

En el caso 0-1 tenemos una lista de

n

objetos, el peso de cada uno y el valor correspondiente. A todo ello se suma la limitación del peso máximo admisible.

tenemos, por tanto,

n

Variables

Cada variable genérica, indicada como

, solo puede ser cero o uno:

También tenemos que la suma de los pesos debe ser inferior a un valor máximo y que nuestro objetivo es maximizar el valor de los objetos que metemos en la mochila. En fórmulas:

donde con

indicamos el valor del objeto

y con

el peso correspondiente. Recordamos que con el símbolo

se indica la operación de suma; puesto en su totalidad la segunda relación, por ejemplo, es equivalente a:

Ahora que hemos "formalizado" el problema, la siguiente pregunta es: ¿cómo lo soluciono?

En el siguiente párrafo veremos uno de los posibles métodos de solución que utiliza un algoritmo particular llamado "codicioso". ¡Confirma una vez más la idea de que los algoritmos nos rodean!

El algoritmo codicioso

Tratemos de pensar juntos en los posibles métodos para tratar el problema.

Lo primero que, por lo general, uno siempre intenta es buscar la solución haciendo todos los intentos posibles. Este método se llama método de fuerza bruta. Tener una computadora, en papel, es un método prometedor dado que hacemos el esfuerzo de hacer una máquina. Sin embargo, si la cantidad de objetos es grande, este método no se puede aplicar porque, incluso si tiene la computadora más poderosa del mundo, no podría calcular el resultado en un tiempo razonablemente finito (solo para entender: toma un siglo y ya es hermoso el tu avión que se fue!).

De hecho, para cada objeto de la lista tengo que elegir si tomarlo o no; cada elemento adicional duplica las opciones posibles y en general estas crecen a medida que

Por ejemplo si tengo 3 objetos tengo

casos, mientras que si tengo 1000 objetos tengo

que es un número, como diría Dante Alighieri, para "hacer temblar las venas y las muñecas" por lo grande que es.

Está claro que debemos buscar, por tanto, un criterio "inteligente" para elegir y evitar intentar caminos inútiles. En otras palabras, es necesario reducir los posibles caminos a seguir.

El algoritmo codicioso que, recordemos, significa codicioso, hace exactamente eso: ofrece una forma de elegir porque, después de haber ordenado los objetos, elige el que "te hace más tentador"... veamos con un ejemplo para entender mejor.

Consideremos el siguiente caso:

Tenemos nueve artículos para poner en nuestra mochila/contenedor hipotético. Para cada uno de ellos se indica el valor y el peso.

Por ejemplo El primer objeto tiene valor 50 y peso 31. Si optamos por tomarlo debemos decir que la variable

0

si quisiéramos excluirlo con

indicamos el peso máximo permitido.

Así que ordenemos los nueve elementos según su valor y obtendremos la siguiente secuencia:

(65,55,50,45,40,35,25,18,16)

Basado en la idea del algoritmo voraz, se toma primero el objeto 2, que corresponde al valor máximo

y por lo tanto tendremos que

Una vez elegido el término, comprobamos que el peso de los elementos seleccionados es inferior al máximo (en el primer paso la cosa es trivial claro). Luego procedemos iterativamente, eligiendo el segundo de la lista ordenada o

Verifique que la suma de los dos primeros términos seleccionados no exceda de 100 (de hecho, tenemos  39+28<100) y se repite de nuevo. Si por casualidad el objeto elegido para agregar tiene un peso tal que supera la restricción, intenta elegir el siguiente y así sucesivamente...

A estas alturas estamos seguros que el lector atento está pensando que este método tiene un problema. De hecho, al tomar gradualmente objetos de mayor valor no estamos teniendo en cuenta su peso; podría ser, en efecto, que colocando dos objetos de menor valor pero de poco peso se logre obtener un mayor valor.

¿Cómo podemos tener en cuenta también el peso a la hora de elegir el objeto?

La respuesta sencilla es crear una nueva lista que llamaremos rendimiento en la que cada término viene dado por la relación entre el valor y el peso:

Esta elección, teniendo en cuenta no solo el valor sino también el peso, ofrece la posibilidad de encontrar una mejor solución.

En este punto, queda una última pregunta: "¿Es la secuencia que encuentras siempre la mejor solución?"

La respuesta es "¡lamentablemente no!". De hecho, el algoritmo voraz proporciona un método muy simple para encontrar una solución "buena" pero no la mejor. Como te anticipé, el problema parece sencillo pero no lo es.

Al final de esta publicación, inserto un video que nos explica fácilmente algoritmos de solución.

ideas educativas

Agrego una pista para una posible actividad didáctica a realizar con  los alumnos. Tómalo como lo que es: sólo un borrador de una actividad, sin pretender ser exhaustiva, que se presta a ser realizada prácticamente a cualquier edad.

Desde muchos sectores se habla en la enseñanza de las matemáticas de incluir, especialmente con alumnos mayores, actividades grupales que tengan un "enfoque de laboratorio" o, trivializando un poco, que contemplen actividades experimentales en las que los alumnos se enfrenten a problemas concretos también "ensuciándose las manos".

El problema de la mochila realmente se presta a una actividad de este tipo. Divide la clase en

equipos (compruébelo usted mismo según el número de estudiantes) Traiga (o haya traído) a la escuela

maletas/mochilas/contenedores y

lista correspondiente de artículos similares y una balanza. En cada objeto pega una pegatina con el precio y el peso indicados.

Cada equipo deberá proponer la secuencia de objetos a embalar, formalizando el razonamiento (¡algoritmo!) utilizado para encontrar la solución (para los alumnos mayores, sería muy útil didácticamente un posterior análisis y comparación de los diferentes métodos propuestos).

Al final del tiempo dado, cada equipo deberá poner la maleta en la báscula para verificar que la solución propuesta respeta la restricción de peso.

Si quieres dejar comentarios en los comentarios para mejorar/criticar esta idea, ¡adelante!

Creemos que es útil para todos.

Video del problema de la mochila

En este video se habla sobre el problema matematico de la mochila 0-1 (Knapsack Problem), un problema muy interesante en el área de la optimización. También vemos el modelo matemático para una mochila y 3 objetos.