Scribd
Cargar
336 vistas9 páginas

Programacion Dinámica Determinística

Este documento describe el problema de la mochila, que consiste en determinar los artículos más valiosos que se pueden cargar en una mochila o contenedor teniendo en cuenta limitaciones de peso. Explica cómo resolver este problema de optimización usando programación dinámica determinística, dividiendo el problema en etapas recursivas donde en cada etapa se maximiza el valor total considerando las restricciones de peso y las soluciones de etapas anteriores. Como ejemplo, analiza el problema de cargar artículos en un barco de 4 toneladas para maxim

Cargado por

Anita Paz Rodríguez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
336 vistas9 páginas

Programacion Dinámica Determinística

Este documento describe el problema de la mochila, que consiste en determinar los artículos más valiosos que se pueden cargar en una mochila o contenedor teniendo en cuenta limitaciones de peso. Explica cómo resolver este problema de optimización usando programación dinámica determinística, dividiendo el problema en etapas recursivas donde en cada etapa se maximiza el valor total considerando las restricciones de peso y las soluciones de etapas anteriores. Como ejemplo, analiza el problema de cargar artículos en un barco de 4 toneladas para maxim

Cargado por

Anita Paz Rodríguez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

PROGRAMACIÓN DINÁMICA DETERMINISTICA

Ing. Luis Mantilla Rodriguez


[email protected]
EL PROBLEMA DE LA MOCHILA
Consiste en determinar los artículos más valiosos que una persona debe cargar en su mochila.

Representa un modelo de asignación de recursos, los mismos que son limitados por varias
actividades económicas. El objetivo es maximizar el rendimiento total.

Conocido también como : problema del equipo de vuelo (determinar los artículos más valiosos
que un piloto de avión debe llevar a bordo), y problema de carga de un contenedor (determinar
los artículos más valiosos que se cargarán en un buque).
CASO 1 : EL PROBLEMA DE LA MOCHILA
Un barco de 4 Ton puede cargarse con uno o más de tres artículos. La siguiente tabla muestra el
peso unitario p en Ton y el ingreso unitario r en $ para cada artículo n. El objetivo es determinar
que cantidad de cada artículo debemos cargar al barco para maximizar el rendimiento total.

No cargar unidades de cualquier artículo, no genera ningún ingreso.


Solución : FASE DE ANALISIS

Capacidad en peso del barco W = 4 Ton

Elementos del modelo :


Etapas (n) : C/u de los artículos a cargar en la mochila
Variables (Xn) : Cantidad del artículo n a cargar en la mochila Xn ≤ (W/pn)
Estado (Sn) : Capacidad de peso disponible en el barco en la etapa n.

o El límite de peso es la única restricción que liga a todas las etapas.


o Dado que pn y W son enteros, el estado Sn asume sólo valores enteros.
Solución : FASE DE ANALISIS
Etapa 3 :
En la etapa 3, X3 puede tomar los valores : 0,1,2,3 ó 4 und del artículo 3, porque el peso del
artículo 3 es 1 Ton y el barco tiene 4 Ton de capacidad.
El ingreso que deja el articulo 3 = (14000)(X3), la función recurrente será :

f3(S3) = max 14000X3


X3 = 0,1,2,3,4

Tabla inferior resume los cálculos para la etapa 3


Solución : FASE DE ANALISIS
Etapa 2 :
En la etapa 2, X2 puede tomar solo los valores 0 y 1, puesto que solamente podemos cargar 0 ó
1 und del artículo 2, dado que el peso de éste artículo es 3 Ton y el barco tiene solamente 4 Ton
de capacidad.
El ingreso que deja el articulo 2 es (47000)(X2), a este ingreso hay que sumarle el ingreso óptimo
que deja la etapa 3, por cada nivel de estado. La función recurrente será entonces :

f2(S2) = max 47000X2 + f3(S2 – 3X2)


X2 = 0,1

La siguiente tabla resume los cálculos para la etapa 3 :


Solución : FASE DE ANALISIS
Etapa 1 :
En la etapa 1, X1 puede tomar solo los valores 0, 1 y 2, puesto que solamente podemos cargar 0,
1 ó 2 und del artículo 1, dado que el peso de éste artículo es 2 Ton y el barco tiene solamente 4
Ton de capacidad.
El ingreso que deja el articulo 1 es (31000)(X1), a este ingreso hay que sumarle el ingreso óptimo
que deja la etapa 2, por cada nivel de estado. La función recurrente será entonces :

f1(S1) = max 31000X1 + f2(S1 – 2X1)


X2 = 0,1,2

La siguiente tabla resume los cálculos para la etapa 1 :


Solución : FASE DE DESICION
Etapa 1 : Mejor desición cargar 2 und del artículo 1, utilidad = $62000

Etapa 2 : Mejor desición cargar 0 und del artículo 2, peso disponible = 0

Etapa 3 : Mejor desición cargar 0 und del artículo 3, peso disponible = 0


GRACIAS POR SU ATENCION

También podría gustarte