Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 28 vistas

    Investigacion Operativa - Clase 28

    Cargado por

    Jose Manuel Molina Cuarite
    El documento proporciona una introducción a la programación dinámica. Explica que la programación dinámica se aplica típicamente a problemas de optimización que involucran muchas soluciones posibles. Divide los problemas grandes en subproblemas más pequeños que son más fáciles de resolver, y luego combina las soluciones de los subproblemas para generar la solución del problema original. También describe los cuatro elementos clave de la programación dinámica: el principio de optimalidad de Bellman, la definición recursiva de la solución óptima,

    Copyright:

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

    Investigacion Operativa - Clase 28

    Cargado por

    Jose Manuel Molina Cuarite
    28 vistas15 páginas
    El documento proporciona una introducción a la programación dinámica. Explica que la programación dinámica se aplica típicamente a problemas de optimización que involucran muchas soluciones posibles. Divide los problemas grandes en subproblemas más pequeños que son más fáciles de resolver, y luego combina las soluciones de los subproblemas para generar la solución del problema original. También describe los cuatro elementos clave de la programación dinámica: el principio de optimalidad de Bellman, la definición recursiva de la solución óptima,

    Descripción original:

    N

    Título original

    INVESTIGACION OPERATIVA - CLASE 28

    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 proporciona una introducción a la programación dinámica. Explica que la programación dinámica se aplica típicamente a problemas de optimización que involucran muchas soluciones posibles. Divide los problemas grandes en subproblemas más pequeños que son más fáciles de resolver, y luego combina las soluciones de los subproblemas para generar la solución del problema original. También describe los cuatro elementos clave de la programación dinámica: el principio de optimalidad de Bellman, la definición recursiva de la solución óptima,

    Copyright:

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

    Investigacion Operativa - Clase 28

    Cargado por

    Jose Manuel Molina Cuarite
    El documento proporciona una introducción a la programación dinámica. Explica que la programación dinámica se aplica típicamente a problemas de optimización que involucran muchas soluciones posibles. Divide los problemas grandes en subproblemas más pequeños que son más fáciles de resolver, y luego combina las soluciones de los subproblemas para generar la solución del problema original. También describe los cuatro elementos clave de la programación dinámica: el principio de optimalidad de Bellman, la definición recursiva de la solución óptima,

    Copyright:

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

    UNIDAD 4: PROGRAMACIÓN ENTERA Y

    MULTIOBJETIVO PROGRAMACIÓN DINÁMICA


    PROGRAMACIÓN DINÁMICA

    Al final de la sesión, el estudiante


    Logro de la comprende la programación dinámica
    sesión utilizando información de los autores.
    PROGRAMACIÓN DÍNAMICA

    Es aplicada típicamente a problemas de


    optimización, donde puede haber muchas
    soluciones, cada una tiene un valor asociado y
    pretendemos obtener la solución con valor
    óptimo.
    PROGRAMACIÓN DÍNAMICA

    Al igual que ”dividir y conquistar”, el problema


    es dividido en subproblemas de tamaños
    menores que son más fáciles de resolver.
    PROGRAMACIÓN DÍNAMICA

    Una vez resueltos estos subproblemas, se


    combinan las soluciones obtenidas para
    generar la solución del problemas original.
    PROGRAMACIÓN DÍNAMICA

    ¿A qué problemas se aplica?


    Esta técnica se aplica sobre problemas que a
    simple vista necesitan un alto coste
    computacional como:
    PROGRAMACIÓN DÍNAMICA

     Subproblemas optimales:
    La solución óptima a un problema puede ser
    definida en función de soluciones óptimas a
    subproblemas de tamaño menor,
    generalmente de forma recursiva.
    PROGRAMACIÓN DÍNAMICA

     Solapamiento entre subproblemas:


    Al plantear la solución recursiva, un mismo
    problema se resuelve más de una vez.
    PROGRAMACIÓN DÍNAMICA

    Elementos de la Programación Dinámica


    1. Principio de Optimalidad de Bellman.
    2. Definición Recursiva de la solución optima.
    3. Enfoque ascendente.
    4. Búsqueda solución optima.
    PROGRAMACIÓN DÍNAMICA

    Principio de optimalidad:
    Si en una sucesión óptima de decisiones o
    elecciones, cada subsucesión es a su vez
    óptima.
    Es decir, si miramos una subsolución de la
    solución óptima, debe ser solución del
    subproblema asociado a esa subsolución.
    PROGRAMACIÓN DÍNAMICA
    Para desarrollar el proceso de Programación
    Dinámica se debe:
    1. Ver si se aplica el Principio de Optimalidad de
    Bellman:
     Encontrar la estructura de la solución.
     Dividir el problema en subproblemas y determinar
    si se puede aplicar el principio de optimalidad.
    PROGRAMACIÓN DÍNAMICA

    2. Definición recursiva de la solución optimal:


    Definir el valor de la solución óptima en
    función de valores de soluciones para sub-
    problemas de tamaño menor.
    PROGRAMACIÓN DÍNAMICA
    3. Calcular el valor de la solución optimal utilizando
    un enfoque ascendente.
     Determinar el conjunto de subproblemas distintos a
    resolver.
     Obtener los valores con un enfoque ascendente y
    almacenar los valores que vamos calculado.
     En etapas posteriores se utilizaran los valores
    previamente calculados
    PROGRAMACIÓN DÍNAMICA

    4. Determinar la solución óptima a partir de la


    información previamente calculada.
    PREGUNTAS

    También podría gustarte