Skip to content

Solución: planificando el repostaje

by en 02/06/2013

¡Hola *.*!

Se acaba la semana, y toca resolver el acertijo que os planteábamos el lunes. Consistía en decidir el modo de realizar el repostaje óptimo para un graaaan camión conociendo las gasolineras a lo largo de nuestra ruta y el precio del combustible en cada una de ellas. Como restricción adicional, nuestro enorme camión tenía un depósito preocupantemente pequeño, de sólo 200 litros, algo bastante reducido si consideramos que la criatura consumía un litro por kilómetro recorrido.

Como otras semanas, Borja nos propuso su solución… ¡y acertó! Veamos cómo se resuelve.

Al principio del recorrido, el camión tenía 100 litros de combustible. Y tenía que llegar a una ciudad situada a 600 kilómetros de distancia, con las siguientes gasolineras en el camino:

Kilómetro 50 100 200 250 300 350 400 450 550
Precio del litro (¢) 700 900 800 850 750 1000 950 800 1100

Para resolver el acertijo podemos aplicar lo que en informática se conoce como algoritmo voraz. En concreto, vamos a ir tomando decisiones que son las más óptimas en el momento de hacerlas y que nos llevarán, al final, también a la mejor solución global.

Lo primero que tenemos que decidir es ¿en qué gasolinera paramos primero? Al principio el camión tiene 100 litros de combustible, por lo que podremos llegar a las gasolineras situadas en los puntos kilométricos 50 y 100. No tiene sentido, de momento, mirar más allá, porque no podremos llegar a las siguientes si no paramos antes. De esas dos, es más rentable parar en la primera, por ser más barata.

La siguiente pregunta es ¿cuánto combustible echamos? Una medida conservadora sería llenar el depósito, pero antes de hacerlo, es mejor pensar en la siguiente gasolinera en la que vamos a parar. Para eso, volvemos a mirar la distancia a la que podemos llegar desde aquí:

Kilómetro 50 100 200 250 300 350 400 450 550
Precio del litro (¢) 700 900 800 850 750 1000 950 800 1100
Paradas X

La tabla nos indica que desde la gasolinera del kilómetro 50, podemos llegar a tres, las situadas en los kilómetros 100, 200 y 250. Todas ellas son más caras que la gasolinera en la que estamos. Por tanto ¡cuanto más combustible compremos ahora mucho mejor! Lo más rentable es llenar por tanto el depósito entero. Dado que al salir teníamos 100 litros y sólo nos hemos movido 50 kilómetros, tendremos que echar 150 litros para llenar el depósito.

Kilómetro 50 100 200 250 300 350 400 450 550
Precio del litro (¢) 700 900 800 850 750 1000 950 800 1100
Paradas 150

Un punto importante aquí es que la decisión de llenar el depósito no significa que vayamos a parar en la última gasolinera. Y de hecho esa es la siguiente pregunta. ¿En cuál de las tres que tenemos accesibles paramos? Igual que hicimos antes, lo mejor es parar en la más barata, incluso aunque nos sobre combustible. Eso nos lleva a la gasolinera del kilómetro 200, a la que llegaremos con 50 litros en el depósito.

Kilómetro 50 100 200 250 300 350 400 450 550
Precio del litro (¢) 700 900 800 850 750 1000 950 800 1100
Paradas 150 X

Y ahora, ¿cuánto echamos? Podríamos llenar el depósito como hicimos antes. Pero en esta ocasión tenemos al alcance una gasolinera más barata que aquella en la que estamos. Lo óptimo será echar tanto combustible como podamos en esa gasolinera más barata. Y para eso, lo ideal es llegar a ella con el depósito vacío. Es decir, en la gasolinera actual, en el kilómetro 200, vamos a echar la mínima cantidad posible de combustible para llegar a la primera gasolinera más barata que ella, situada en el kilómetro 300. Necesitaremos un total de 100 litros que, al tener 50 aún, supone que tenemos que repostar únicamente 50 litros. En este caso la decisión de cuánto echar y en qué gasolinera parar a continuación la hemos tomado a la vez. La nueva situación es la siguiente:

Kilómetro 50 100 200 250 300 350 400 450 550
Precio del litro (¢) 700 900 800 850 750 1000 950 800 1100
Paradas 150 50 X

Como la primera vez, ahora todas las gasolineras alcanzables son más caras que la actual, por lo que llenaremos el depósito. Además, nos interesa parar en la gasolinera alcanzable más barata que, en este caso, es la más alejada, situada en el kilómetro 450:

Kilómetro 50 100 200 250 300 350 400 450 550
Precio del litro (¢) 700 900 800 850 750 1000 950 800 1100
Paradas 150 50 200 X

¡Ya vamos llegando al final! Es importante recordar que necesitamos llegar al kilómetro 600 con 100 litros de gasolina. Eso no vamos a poderlo conseguir desde el kilómetro 450, por lo que tendremos que repostar una vez más. La última gasolinera es más cara que la actual, por lo que ahora mismo nos interesa llenar el depósito. En este momento aún tenemos 50 litros, de modo que echaremos 150 litros más:

Kilómetro 50 100 200 250 300 350 400 450 550
Precio del litro (¢) 700 900 800 850 750 1000 950 800 1100
Paradas 150 50 200 150 X

¡Esta es la gasolinera más cara de todas! Nos quedan 100 litros en el depósito, que no son suficientes para llegar al kilómetro 600 y dejar otros 100. Queremos ahorrar, por lo que echaremos el mínimo imprescindible para conseguir cumplir este objetivo. Y eso significa que echaremos los últimos 50 litros. Nuestro viaje queda:

Kilómetro 50 100 200 250 300 350 400 450 550
Precio del litro (¢) 700 900 800 850 750 1000 950 800 1100
Paradas 150 50 200 150 50

¿Cuánto nos cuesta en total? Basta multiplicar los litros que hemos echado en cada gasolinera por su coste. Como dijo Borja, el montante total llega a 470000 ¢ o, sea 4.700 €. ¡¡Una pequeña fortuna!!

Como siempre, si te gusta programar y te animas, puedes probar tu solución aquí. Programarlo es un poco lío, porque hay que tener cuidado con las condiciones de los bucles, con la posibilidad de que las gasolineras estén demasiado alejadas y no podamos llegar a nuestro destino, y con la necesidad de acabar con los 100 litros al final. Pero ¡es reconfortante hacer un programa que parece que “piensa”! 🙂

¡Hasta mañana!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: