Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 292 vistas

    Ejemplo de Ramificacion y Acotamiento

    Cargado por

    rigoberto marquez
    El documento describe un problema de programación lineal entera (PLE) que maximiza la función objetivo z = 21x1 + 11x2 sujeto a la restricción 7x1 + 4x2 ≤ 13. La relajación continua del problema tiene valor óptimo 39 con solución x1 = 1.9, x2 = 0. El algoritmo Branch & Bound es aplicado para encontrar la solución entera óptima, la cual es x1 = 0, x2 = 3, con valor óptimo 33.

    Copyright:

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

    Ejemplo de Ramificacion y Acotamiento

    Cargado por

    rigoberto marquez
    292 vistas2 páginas
    El documento describe un problema de programación lineal entera (PLE) que maximiza la función objetivo z = 21x1 + 11x2 sujeto a la restricción 7x1 + 4x2 ≤ 13. La relajación continua del problema tiene valor óptimo 39 con solución x1 = 1.9, x2 = 0. El algoritmo Branch & Bound es aplicado para encontrar la solución entera óptima, la cual es x1 = 0, x2 = 3, con valor óptimo 33.

    Título original

    98561932-Ejemplo-de-ramificacion-y-acotamiento.docx

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento describe un problema de programación lineal entera (PLE) que maximiza la función objetivo z = 21x1 + 11x2 sujeto a la restricción 7x1 + 4x2 ≤ 13. La relajación continua del problema tiene valor óptimo 39 con solución x1 = 1.9, x2 = 0. El algoritmo Branch & Bound es aplicado para encontrar la solución entera óptima, la cual es x1 = 0, x2 = 3, con valor óptimo 33.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    292 vistas2 páginas

    Ejemplo de Ramificacion y Acotamiento

    Cargado por

    rigoberto marquez
    El documento describe un problema de programación lineal entera (PLE) que maximiza la función objetivo z = 21x1 + 11x2 sujeto a la restricción 7x1 + 4x2 ≤ 13. La relajación continua del problema tiene valor óptimo 39 con solución x1 = 1.9, x2 = 0. El algoritmo Branch & Bound es aplicado para encontrar la solución entera óptima, la cual es x1 = 0, x2 = 3, con valor óptimo 33.

    Copyright:

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

    Ejemplo de ramificación y acotamiento

    𝑀𝑎𝑥 𝑧 = 21𝑥1 + 11𝑥2

    7𝑥1 + 4𝑥2 ≤ 13

    El dominio de puntos factibles para el modelo de Programación Lineal asociado es el área demarcada con
    verde. Dicho modelo tiene valor óptimo igual a 39, con X1=1,9 y X2=0. Esto corresponde a
    la relajación contínua del PLE y nos proporciona una cota superior del valor óptimo de dicho problema.

    Además, claramente la solución de la relación contínua no satisface la condición de integralidad del


    modelo de PLE. Finalmente, en el gráfico anterior se han marcado con azul todas aquellas
    combinaciones que satisfacen las restricciones del modelo de PLE. Claramente esto corresponde a un
    subdominio del problema lineal asociado lo que justifica que la relajación continua nos entrega una cota
    superior del valor óptimo del PLE.

    Al aplicar el algoritmo de Branch & Bound, el nodo inicial corresponde a la relajación continua y se van
    agregando las ramas o nodos necesarios hasta alcanzar la(s) soluciones que satisfacen las condiciones
    de integralidad.
    P0: Corresponde a la relajación continua del PLE.
    P1: Po + x1<=1. (solución inicial X1=1,9 aproximada al entero inferior)
    P2: Po + x1>=2 (solución inicial X1=1,9 aproximada al entero superior). Infactible.
    P11: P1 + x2<=1 (solución óptima X1=1 y X2=1. Valor Óptimo Z=33. Debido a que la solución satisface
    las restricciones de integralidad, se termina este nodo).
    P12: P1 + x2>=2 (solución X1=5/7 y X2=2. No es solución óptima de PLE debido a que X1 es aún
    fraccionario. Secontinua el método debido a que el Valor Óptimo Z=37 es mayor que el Valor Óptimo de
    P11, en caso contrario se detiene el método y P11 sería la solución óptima de PLE).
    P121: P12 + x1<=0 (X1=0 y X2=13/4. Z=35,75. Se continua siguiendo el mismo razonamiento anterior)
    P122: P12 + X1>=1 Infactible.
    P1211: P121 + X2<=3 (X1=0 y X2=3. Z=33 el Valor Óptimo más alto obtenido para los nodos con
    soluciones enteras). Se agota este nodo.
    P1212: P121 + x2>=4 Infactible.

    Luego la Solución Óptima del PLE) es X1=0 y X2=3 con Valor Óptimo Z=33.

    También podría gustarte