Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 273 vistas

    IO - Problema de La Mochila

    Cargado por

    Davis Jazmin
    Este documento describe cómo resolver el problema de la mochila mediante el método de ramificar y acotar. El problema de la mochila implica elegir los elementos a llevar en una mochila de capacidad limitada para maximizar el beneficio total, sin sobrepasar la capacidad. El método genera todas las posibles soluciones a través de un árbol de decisión y elige la solución óptima. Se presenta un ejemplo numérico para ilustrar el proceso.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    IO - Problema de La Mochila

    Cargado por

    Davis Jazmin
    273 vistas3 páginas
    Este documento describe cómo resolver el problema de la mochila mediante el método de ramificar y acotar. El problema de la mochila implica elegir los elementos a llevar en una mochila de capacidad limitada para maximizar el beneficio total, sin sobrepasar la capacidad. El método genera todas las posibles soluciones a través de un árbol de decisión y elige la solución óptima. Se presenta un ejemplo numérico para ilustrar el proceso.

    Descripción original:

    Libro

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe cómo resolver el problema de la mochila mediante el método de ramificar y acotar. El problema de la mochila implica elegir los elementos a llevar en una mochila de capacidad limitada para maximizar el beneficio total, sin sobrepasar la capacidad. El método genera todas las posibles soluciones a través de un árbol de decisión y elige la solución óptima. Se presenta un ejemplo numérico para ilustrar el proceso.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    273 vistas3 páginas

    IO - Problema de La Mochila

    Cargado por

    Davis Jazmin
    Este documento describe cómo resolver el problema de la mochila mediante el método de ramificar y acotar. El problema de la mochila implica elegir los elementos a llevar en una mochila de capacidad limitada para maximizar el beneficio total, sin sobrepasar la capacidad. El método genera todas las posibles soluciones a través de un árbol de decisión y elige la solución óptima. Se presenta un ejemplo numérico para ilustrar el proceso.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 3

    RESOLUCIN DEL PROBLEMA DE LA MOCHILA POR EL METODO DE

    RAMIFICAR Y ACOTAR
    Angela Maria Devia, Carlos Eduardo Rodriguez
    Universidad Nacional de Colombia. Bogot D. C., Colombia.
    {amdevias,cerodriguezl}@unal.edu.co

    Abstract. El problema de la mochila ha sido ampliamente estudiado en el desarrollo de algoritmos


    ya que permite evaluar la eficacia de los mismos. Las caractersticas de este problema son
    fcilmente relacionadas con situaciones reales en las empresas y, en general, en cualquier actividad
    que requiera la asignacin de recursos. Pero no implica sencillamente una eleccin de recursos, sino
    que adems condiciona la eleccin del recurso a cierto beneficio que se obtendr al asignarlo y a
    ciertos factores que restringen su eleccin a partir de la capacidad que se tiene para poder asignarlo.
    En este documento describiremos matemticamente las caractersticas de este problema y como
    puede ser solucionado a travs del mtodo de ramificar y acotar, uno de los algoritmos lineales ms
    frecuentes y aunque no es muy eficiente en cuanto a tiempo de solucin se refiere, es el que
    permite considerar realmente todas las posibles soluciones de un problema real.

    Keywords: Programacin Entera, knapsack problem, problema de la mochila, rbol de ramificar y


    acotar.

    Introduccin

    El problema de la mochila surge a partir de la siguiente situacin: Deseamos hacer una


    excursin al campo, pero slo podemos llevar con nosotros una mochila, la cual tiene una
    capacidad de almacenamiento limitada. Poseemos varios elementos que podramos llevar y
    podran ser muy tiles para diferentes situaciones, pero la capacidad de la mochila no es
    suficiente para permitirnos llevarlos todos. Tenemos que elegir los elementos que llevaremos
    de tal forma que los que llevemos nos proporcionen el mayor beneficio posible y que estos
    quepan en la mochila. Este problema es muy frecuente en las empresas cuando se toman
    decisiones respecto al presupuesto y las inversiones. A travs de este mtodo de
    programacin lineal entera, se busca llegar a concluir la cantidad de elementos que se van a
    llevar en la mochila. Este mtodo nos permite concluir cuales elementos se llevan o no se
    llevan y esto es representado a travs de un cero (0) cuando no se lleva y con un uno (1) si el
    elemento es elegido para llevar en la maleta.

    Definicin formal del problema

    El problema definido matemticamente se describe de la siguiente forma: se cuenta con un


    conjunto de objetos de tamao , cada uno de dichos objetos tiene un peso y un beneficio
    donde se cargaran los objetos seleccionados,
    , y una mochila con una capacidad de
    representaremos la solucin mediante el vector de tamao , donde puede tomar valor
    de 0 o 1 dependiendo si el objeto es o no llevado en la mochila. En las lneas siguientes se
    define el problema en trminos de las variables establecidas.

    Descripcin del mtodo de ramificar y acotar

    El mtodo consiste en la evaluacin de todas las posibles soluciones al problema a partir de las
    caractersticas inciales del mismo, considerando en cada etapa una decisin respecto a los
    elementos del problema, esto es lo que se considera como la eleccin o no del elemento para
    ir dentro de la mochila. Los pasos del algoritmo de ramificar y acotar para un problema con
    variables binarias (0 1) son:
    1. Se plantean las restricciones y la funcin objetivo del problema.
    2. Se da la primera solucin de la funcin objetivo donde todas las variables son cero.
    3. Se elige la variable i=i+1 y se divide el rbol del algoritmo en dos: por un lado, cuando la
    variable es igual a cero (o sea que el elemento no se lleva) y por el otro lado, cuando la
    variable es igual a uno (o sea cuando el elemento si va en la mochila o es incluido en la
    solucin). Decimos que las soluciones de este paso son relacionadas con la solucin que les
    dio origen con un arco el cual se identa con la eleccin para la variable y estas soluciones
    son posicionadas en la etapa i=i+1.
    4. Si i=n, entonces se termina el algoritmo y se comparan las posibles soluciones para as elegir
    la que mejor satisface la funcin objetivo del problema. Si i<n, entonces se contina con el
    paso 3 para cada una de las soluciones obtenidas.
    Veamos un ejemplo de cmo se realiza el mtodo de ramificar y acotar.

    Ejemplo del problema de la mochila resuelto por el mtodo

    Un viajero cuenta con 5 objetos que puede cargar en su mochila, pero desgraciadamente
    nicamente puede llevar el conjunto de objetos que no sobrepasen la capacidad W de dicha
    mochila, si adems de todo cada objeto le proporciona un beneficio al viajero, cul es el
    conjunto de objetos que el viajero debe llevar para maximizar su beneficio y no sobrepasar el
    peso restringido por la capacidad de la mochila?
    Los datos del problema se describen a continuacin:

    El vector Solucin inicial es:

    Entonces, el rbol que describe el proceso de ramificar y acotar es el siguiente:

    Bibliografa

    Winston, Wayne L.: Investigacin de operaciones: Aplicaciones y Algoritmos. Captulo 9,


    9458515. Ed. Iberoamrica. Mxico D. F., Mxico. (1994)
    Brassard, Gilles.: Fundamentos de algoritmia. Captulo 6, seccin 6.5, 227241. Ed. Prentice
    Hall. Madrid, Espaa. (1997)

    También podría gustarte