Problema de La Mochila

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
 72
 
  Problema de la mochila El problema de la mochila es un problema de programación entera, estando ésta última dentro del campo de la programación matemática y consiste en escoger un conjunto de artículos para llenar una mochila de modo de que se cumplan ciertas restricciones. 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ógicam
Share
Transcript
  Problema de la mochila El problema de la mochila es un problema deprogramación entera,estando ésta últimadentro del campo de laprogramación matemáticay consiste en escoger un conjunto deartículos para llenar una mochila de modo de que se cumplan ciertas restricciones. Definición Un problema típico de programación entera es el que nos ocupa, “el problema de lamochila”, 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 capacidadlimitada. Cada objeto que introducimos ocupa un volumen dentro de la misma y encontrapartida durante el viaje nos proporcionará un beneficio o utilidad (ejemplo:una cantimplora), el problema surge cuando debemos elegir qué objetosseleccionar 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 derecursos económicos de los que se dispone) y donde la utilidad de los objetosseleccionados se equipara a un beneficio económico por adquirir o llevar a cabo ciertasacciones.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 ejercicioeconómico que se cierra ha obtenido un excedente de 300.000€ (su beneficio neto, una vez descontados los impuestos y retribuidos lo s 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 carterade 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 formaconjunta qué productos serán los escogidos para la ampliación de cartera.Los asesores comerciales sugieren los siguientes productos, basándose en estudios demercado que han realizado para estimar la cifra de negocios que cada nuevo productogenerará: - 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 lasinstalaciones productivas para poder incrementar la cartera de productos, estos costes sepodrían equiparar al volumen que ocupan los objetos dentro de la mochila, por tanto, lasuma 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.00 0 €  - 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óndel 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 “i” -ésimo que no es más que una forma dehacer referencia a un objeto cualquiera que pueda ser incluido en la mochila -, esdecir, 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 alobjeto 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 setratan 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 quela suma de todos los objetos multiplicados por el espacio que ocupan en la mochila nopodrá 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 seleccionaraquellos 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íneasprecedentes 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 limitadaP, 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: Nota: pueden existir otras restricciones técnicas que nada tengan que ver con lasanteriormente citadas que serían comunes a cualquier problema de ProgramaciónMatemática Métodos de resolución Este problema se ha resuelto tradicionalmente medianteprogramación linealentera.El hecho de que se trate de programación lineal hace referencia a que la función aoptimizar y las inecuaciones que constituyen las restricciones han de serlineales,esdecir, han de ser funciones cuyas incógnitas estén elevadas exclusivamente a la unidad.Existe otra forma de resolver este tipo de problema, a través de los denominadosalgoritmos voraces.Una aproximación voraz consiste en que cada elemento a considerarse evalúa una única vez, siendo descartado o seleccionado, de tal forma que si esseleccionado forma parte de la solución, y si es descartado, no forma parte de lasolución ni volverá a ser considerado para la misma. Con este método no siempre esposible 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 comentadoen el párrafo anterior.Si quisiéramos resolver el problema mediante programación lineal entera tendríamosque plantear el modelo, del mismo modo que hicimos con Costuritas S.L. al comentarcómo se expresa un problema que solucionar por este método.Otro sistema para resolver el problema de la mochila es mediantealgoritmos genéticosque son métodos de optimización que tratan de hallar (xi,...,xn) tales que sea máximo.  Planteamiento del problema  El Club Baloncesto Unicaja de Málaga ante la lesión de Daniel Santiago y la escasaaportación del pívot brasileño Vitor Faverani se plantea reforzar el juego interior para ladisputa de los play-offs por el título a partir del 17 de mayo, para ello la secretariatécnica del equipo ha sondeado el mercado y ha encontrado a 5 jugadores que puedenadaptarse a lo requerido por el entrenador. Para reforzar el equipo el Unicaja dispone deun presupuesto máximo de 50.000 $ / mes. En la siguiente tabla aparece una relación delos candidatos a ser fichados junto con su aportación esperada y el sueldo quepercibirían.JUGADOR/EQUIPO SUELDO APORTACIÓNEsteban Batista (Hawks) 50000 $ 15Jared Reiner (Sioux Falls) 25200 $ 8Chriss Burgess (Ulsan Phoebus) 36000 $ 15Marcus Goree (Benetton) 47000 $ 17K.C. Walekowski (Farho Vigo) 12000 $ 7Como puede apreciarse, en este caso, estamos aplicando el problema de la mochila auna 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 nuevacontratació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érminosmatemáticos, recuérdese que se está intentando llegar a una solución cuantitativaconcreta y no simplemente intuitiva. Maximizar 15x1 + 8x2 + 15x3 + 17x4 +7x5sujeto 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)
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x