Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 70 vistas

    Programacion Dinamica

    Cargado por

    Elida Yara Tucto Encarnación
    Este documento explica la programación dinámica. Se define como una técnica para resolver problemas de optimización dividiéndolos en subproblemas. Siguiendo el principio de Bellman, cada subproblema se resuelve de forma óptima almacenando las soluciones para usarlas luego. Esto evita calcular lo mismo varias veces. Como ejemplo, se explica cómo dar el vuelto de $49,20 usando la menor cantidad de billetes y monedas posible.

    Copyright:

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

    Programacion Dinamica

    Cargado por

    Elida Yara Tucto Encarnación
    70 vistas16 páginas
    Este documento explica la programación dinámica. Se define como una técnica para resolver problemas de optimización dividiéndolos en subproblemas. Siguiendo el principio de Bellman, cada subproblema se resuelve de forma óptima almacenando las soluciones para usarlas luego. Esto evita calcular lo mismo varias veces. Como ejemplo, se explica cómo dar el vuelto de $49,20 usando la menor cantidad de billetes y monedas posible.

    Descripción original:

    Curso de Herramientas Computarizadas

    Título original

    Programacion dinamica

    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?

    Este documento explica la programación dinámica. Se define como una técnica para resolver problemas de optimización dividiéndolos en subproblemas. Siguiendo el principio de Bellman, cada subproblema se resuelve de forma óptima almacenando las soluciones para usarlas luego. Esto evita calcular lo mismo varias veces. Como ejemplo, se explica cómo dar el vuelto de $49,20 usando la menor cantidad de billetes y monedas posible.

    Copyright:

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

    Programacion Dinamica

    Cargado por

    Elida Yara Tucto Encarnación
    Este documento explica la programación dinámica. Se define como una técnica para resolver problemas de optimización dividiéndolos en subproblemas. Siguiendo el principio de Bellman, cada subproblema se resuelve de forma óptima almacenando las soluciones para usarlas luego. Esto evita calcular lo mismo varias veces. Como ejemplo, se explica cómo dar el vuelto de $49,20 usando la menor cantidad de billetes y monedas posible.

    Copyright:

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

    UNIVERSIDAD NACIONAL

    HERMILIO VALDIZN
    E.A.P INGENIERA INDUSTRIAL
    HERRAMIENTAS COMPUTARIZADAS

    TEMA:

    PROGRAMACION
    DINAMICA

    DOCENTE:
    ALUMNA:

    PEDRO VILLAVICENCIO
    TUCTO ENCARNACIN, ELIDA YARA

    HCO-PER

    INTRODUCCIN

    Existe una serie de problemas matemticos cuya solucin se


    puede dar mediante el empleo de un algoritmo recursivo o
    mediante la implementacin de una resolucin por etapas,
    planteando una serie de sub problemas a partir del problema
    principal; en ambos casos, la solucin puede ser catica,
    agrandar el tamao del problema o simplemente, el mtodo
    empleado convertirse en impracticable. Esto puede mejorar
    sustancialmente mediante la Programacin Dinmica, PD.

    QU ES LA PROGRAMACIN DIMMICA?
    La Programacin Dinmica es una tcnica de programacin
    que se emplea tpicamente para resolver problemas de
    optimizacin en los cuales el problema principal se encuadra
    en varios subproblemas, solucionando cada uno de ellos y
    luego ligando las soluciones de una forma ptima, donde la
    solucin final permita resolver y tomar decisiones correctas a
    problemas actuales y futuros.

    A QU PROBLEMAS SE APLICA?
    Esta tcnica se aplica sobre problemas que a simple vista
    necesitan un alto coste computacional (posiblemente
    exponencial) donde:
    Subproblemas optmales: La solucin ptima a un
    problema puede ser definida en funcin de Soluciones ptimas
    a subproblemas de tamao menor, generalmente de forma
    recursiva.
    Solapamiento entre subproblemas: Al plantear la solucin
    recursiva, un mismo problema se resuelve ms de una vez

    QU SE LOGRA?
    La PD utiliza un enfoque ascendente (botton-up) para obtener la
    solucin, primero calcula las soluciones ptimas a problemas de
    tamao pequeo. Utilizando dichas soluciones encuentra
    soluciones a problemas de mayor tamao.
    La idea de la PD es encontrar la solucin a los subproblemas y
    almacenarlos en alguna estructura (diccionario) para utilizarlas
    posteriormente.
    Por tanto, es ms eficiente que la fuerza bruta que resuelve el
    mismo subproblema una y otra vez.
    -- Evita calcular lo mismo varias veces. Usualmente se utiliza
    una matriz que se rellena conforme las soluciones a los
    Subproblemas que son calculados (espacio vs. tiempo).

    ELEMENTOS DE LA PROGRAMACIN DINMICA

    Los siguientes cuatro elementos conforman la resolucin de un


    problema mediante PD:
    1. Principio de Optimalidad de Bellman
    2. Definicin Recursiva de la solucin optimal
    3. Enfoque ascendente
    4. Bsqueda solucin optima

    PRINCIPIO DE OPTIMALIDAD DE BELLMAN

    Una secuencia ptima de decisiones que resuelve un


    problema debe cumplir la propiedad de que cualquier
    subsecuencia de decisiones debe ser tambin optima respecto
    al subproblema que resuelve.
    Esto es, la solucin optima a cualquier instancia no trivial de
    un problema es una combinacin de soluciones ptimas de
    algunas de las sub-instancias.

    CARACTERSTICAS DE UN PROBLEMA DE
    Para que un problema pueda ser resuelto con la tcnica
    PD
    de programacin dinmica, debe cumplir con ciertas
    caractersticas:
    - Naturaleza secuencial de las decisiones: El problema
    puede ser dividido en etapas.
    - Cada etapa tiene un numero de estados asociados a
    ella.
    - La decisin ptima de cada etapa depende solo del
    estado actual y no de las decisiones anteriores.
    - La decisin tomada en una etapa determina cual
    ser el estado de la etapa siguiente.
    En sntesis, la poltica ptima desde un estado s de la
    etapa k a la etapa final esta constituida por una
    decisin que transforma s en un estado s de la etapa k
    +1 y por la poltica ptima desde el estado s hasta la
    etapa final.

    RESOLUCIN DE UN PROBLEMA DE PD
    Para resolver un problema de programacin dinmica debemos
    al menos cumplir con:
    Identificacin de etapas, estados y variable de decisin:

    Cada etapa debe tener asociado una o mas decisiones


    (problema de optimizacin), cuya dependencia de las decisiones
    anteriores esta dada exclusivamente por las variables de estado.
    Cada estado debe contener toda la informacin relevante para
    la toma de decisin asociada al perodo.
    Las variables de decisin son aquellas sobre las cuales
    debemos definir su valor de modo de optimizar el beneficio
    acumulado y modificar el estado de la prxima etapa.

    Descripcin de ecuaciones de recurrencia: Nos deben indicar


    como se acumula la funcin de beneficios a optimizar (funcin
    objetivo) y como varan las funciones de estado de una etapa a otra.
    Resolucin: Debemos optimizar cada subproblema por etapas en
    funcin de los resultados de la resolucin del subproblema siguiente.
    Al final obtendremos una solucin ptima para el problema.

    EL PROBLEMA DE LAS MONEDAS


    Mi empresa de colectivos
    El precio de los boletos puede llegar a cambiar en cualquier
    momento
    En todo momento se puede pagar con cualquier moneda o billete
    Tengo que dar el vuelto usando pocas monedas o billetes
    Vuelto usando pocas monedas?
    o El boleto, actualmente, sale $0,80
    o Viene alguien y paga con un billete de $50
    o El vuelto es $50 - $0.80 = $49,20
    o Si le llego a dar 492 monedas de 10 centavos, no se toma nunca mas mi
    colectivo

    Si se tienen los siguientes tipos de monedas y billetes:


    Monedas de 1, 5, 10, 25 y 50 centavos y de 1 peso
    Billetes de 2, 5, 10, 20, 50 y 100 pesos
    Si el vuelto de $49,20, Cul es la mejor manera (menos cantidad de
    billetes y monedas) de dar esa cantidad?
    20 + 20 + 5 + 2 + 2 + 10C+ 10C = 49,20
    En general, si voy tomando cada vez el billete mas grande que puedo,
    me da la cantidad mnima

    FALTA DAR

    ELIJO

    QUEDA

    $ 49,20

    20

    $ 29,20

    $ 29,20

    20

    $ 9,20

    $ 9,20

    $ 4,20

    $ 4,20

    $ 2,20

    $ 2,20

    $ 0,20

    10 C

    $ 10

    10 C

    $0

    $ 0,20
    $ 10

    CMO SE APLICA EL PRINCIPIO DEL


    PTIMO?

    Si requiero dar vuelto de $24,20


    En la anterior vuelto tenamos:
    $20 + $20 + $5 + $2 + $2 + $2c + $2c = $49,20
    Aplicando:
    $20 + $20 + $5 + $2 + $2 + $2c + $2c = $24,20

    CONCLUSIN
    La programacin Dinmica nos permite resolver un problema hallando soluciones sucesivas a sub
    problemas de menor tamao y ligndolas como solucin ptima del problema.
    Para desarrollar el proceso de PD se debe

    1. Ver si se aplica el Principio de Optimalidad de Bellman:


    Encontrar la estructura de la solucin:
    Dividir el problema en subproblemas y determinar si se puede aplicar el principio de Optimalidad.
    2. Definicin recursiva de la solucin optimal:
    Definir el valor de la solucin ptima en funcin de valores de soluciones para sub-problemas de
    tamao menor.
    3. Calcular el valor de la solucin optimal utilizando un enfoque ascendente.
    Determinar el conjunto de subproblemas distintos a resolver (tamao de la tabla)
    Identificar los subproblemas con solucin trivial
    Obtener los valores con un enfoque ascendente y almacenar los valores que vamos calculado en la
    tabla.
    En etapas posteriores se utilizaran los valores previamente calculados
    4. Determinar la solucin ptima a partir de la informacin previamente calculada.
    As, programacin dinmica consiste en solucionar el presente suponiendo que en cada etapa futura
    siempre se tomaran las decisiones correctas.

    WEBGRAFA
    www.edicionsupc.es
    www.lcc.uma.es
    www.cimat.mx
    www.sci2s.ugr.es
    www.decsai.ugr.es
    www.dc.uba.ar

    También podría gustarte