Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 76 vistas

    Investigacion de Operaciones Ii: Escuela de Ingeniería Industrial Ing. Pedro Fernando González Cabeza

    Cargado por

    walter
    El documento describe los modelos de programación lineal entera y algunos algoritmos para resolverlos. Existen modelos puros donde todas las variables deben ser enteras y mixtos donde solo un subconjunto lo es. El algoritmo de ramificación y acotamiento (Branch and Bound) es un método general para obtener soluciones enteras óptimas dividiendo el problema en subproblemas más pequeños.

    Copyright:

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

    Investigacion de Operaciones Ii: Escuela de Ingeniería Industrial Ing. Pedro Fernando González Cabeza

    Cargado por

    walter
    76 vistas12 páginas
    El documento describe los modelos de programación lineal entera y algunos algoritmos para resolverlos. Existen modelos puros donde todas las variables deben ser enteras y mixtos donde solo un subconjunto lo es. El algoritmo de ramificación y acotamiento (Branch and Bound) es un método general para obtener soluciones enteras óptimas dividiendo el problema en subproblemas más pequeños.

    Título original

    20200509090518.pptx

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

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

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento describe los modelos de programación lineal entera y algunos algoritmos para resolverlos. Existen modelos puros donde todas las variables deben ser enteras y mixtos donde solo un subconjunto lo es. El algoritmo de ramificación y acotamiento (Branch and Bound) es un método general para obtener soluciones enteras óptimas dividiendo el problema en subproblemas más pequeños.

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    76 vistas12 páginas

    Investigacion de Operaciones Ii: Escuela de Ingeniería Industrial Ing. Pedro Fernando González Cabeza

    Cargado por

    walter
    El documento describe los modelos de programación lineal entera y algunos algoritmos para resolverlos. Existen modelos puros donde todas las variables deben ser enteras y mixtos donde solo un subconjunto lo es. El algoritmo de ramificación y acotamiento (Branch and Bound) es un método general para obtener soluciones enteras óptimas dividiendo el problema en subproblemas más pequeños.

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    de 12

    INVESTIGACION DE

    OPERACIONES II
    Escuela de Ingeniería Industrial
    Ing. Pedro Fernando González Cabeza
    Programación Lineal Entera
    • En investigación de operaciones I aprendimos a resolver
    modelos de P. L. Por el método simplex y el dual simplex, el
    resultado obtenido podía ser cualquier número real, sin
    embargo, existen problemas que no aceptan como solución
    un número real, por ejemplo, pensemos en el problema de
    selección de personal, en este caso no podemos colocar 1.5
    empleados. Por esta razón se han desarrollado algoritmos
    especiales para la búsqueda de soluciones enteras de
    modelos de P. L.
    Clasificación de los Modelos de
    programación Lineal Entera
    • Los problemas que resuelven corresponden a los llamados modelos de programación lineal entera (P.
    L. E.). Estos modelos se clasifican de la siguiente manera:

    • Modelos de P. L. E. puros. Cuando todas las variables de decisión sólo tienen sentido si toman valores
    enteros.

    • Modelos de P. L. E. mixtos. Cuando alguna de las variables de decisión pueden tomar valores reales y
    sólo un subconjunto está restringido a tomar valores enteros.
    Modelo de P. L. E. Binarios.- Cuando las variables de decisión
    sólo pueden tomar dos valores, por ejemplo, verdadero o falso, esto se representa con cero o uno
    Algoritmos de Programación
    Entera
    Se han desarrollado métodos generales para obtener las restricciones
    especiales del punto óptimo continuo.

    1. Método de Ramificación y Acotamiento (B&B Branch and Bound).: El primer


    algoritmo B&B fue desarrollado por A. Land y G. Doig en 1960, para el
    problema general de programación lineal entera mixta y pura. Puede
    materializar ventajas computacionales.
    2. Métodos Gráficos.
    3. Método del Plano Cortante.
    4. Método de Gomory.
    Algoritmo de Ramificacón y Acotamiento
    (Branch and Bound) A. Land y G.Doig
    1. Resolver la relajación del Modelo de PL.
    2. Son enteros?
    * Si: Esta es la solución al modelo de PLE
    * No: Ir al paso 3.
    3. Ramificación y acotamiento: Se plantean y se resuelven dos nuevos sub problemas del Modelo de PL agregando una
    nueva restricción al problema anterior
    * Xi <= Si (a un problema)
    * Xi >= Si +1 (al otro)
    Si es el valor en la solución de una variable que debe ser entera y no es.
    Ramificar hasta que se cumpla alguna de las siguientes condiciones:
    * Todas las variables que lo requieran son enteras.
    * No hay soluciones factibles.
    * La solución es peor que la mejor encontrada hasta el momento
    Almacene la mejor solución entera de todas las iteraciones. Cuando no pueda ramificar más esa será la solución óptima.

    También podría gustarte