Asignacion De Recursos

PROGRAMACIÓN DINÁMICA DETERMINISTA “ASIGNACION DE
RECURSOS”
Willfredo Valbuena Amado1,2, Cod. 273208, wvalbuenaa@unal.edu.co
Universidad Nacional de Colombia. Bogotá D. C., Colombia
Resumen: Los problemas de asignación de recursos, en los que se
debe asignar una cantidad limitada de recursos entre varias
actividades, se pueden resolver con frecuencia con programación
dinámica.
Abstrac:The problems of allocation of resources, in which a limited
amount of resources between several activities is due to assign, can
be solved frequently with dynamic programming
Keywords:
Recursos.

Programación,

Dinámica,

Deterministica,

Asignación,

1. INTRODUCCION
La programación dinámica (PD) determina la solución óptima de un problema de
n variables descomponiéndola en n etapas,con cada etapa incluyendo un
subproblema de una sola variable. La ventaja en el aspecto de los cálculos es
que optimizaremos una sola variable, en vez de subproblemas de n variables. La
principal contribución de la PD es el principio de optimalidad, un marco de
referencia para descomponer el problema en etapas.
La programación dinámica es una técnica que se puede aplicar para resolvermuchos problemas de optimización. La mayor parte de las veces, la
programación dinámica obtiene soluciones con un avance en reversa, desde el
final de un problema hacia el principio con lo que un problema grande y
engorroso se convierte en una serie de problemas más pequeños y más
tratables.
1.1 NATURALEZA RECURSIVA DE LOS CÁLCULOS EN LA PD
Los cálculos en la PD se hacen recursivamente, en elsentido de la solución
óptima de un subproblema se utiliza como una entrada para el siguiente
subproblema. Para el momento en que resolvamos el último subproblema,
tendremos a mano la solución óptima para todo el problema. La forma en la cual
se hacen los cálculos recursivos depende de la forma en la cual descomponemos
el problema original. En particular, los subproblemas por lo común se unenpor
medio de algunas restricciones comunes. A medida que avanzamos de un
subproblema a otro, debemos dar razón de la variabilidad de estas restricciones.

2. CARACTERÍSTICAS DE LAS APLICACIONES DE PROGRAMACIÓN
DINÁMICA
A continuación veremos una explicación sobre las características que son
comunes en la mayor parte de las aplicaciones de la programación dinámica.
2.1 CARACTERÍSTICA 1
Elproblema se puede dividir en etapas; cada etapa requiere una decisión. En
muchos problemas de programación dinámica, la etapa es la cantidad de tiempo
que pasa desde el inicio del problema, en ciertos casos no se necesitan
decisiones en cada etapa.
2.2 CARACTERÍSTICA 2
Cada etapa tiene un número de estados asociados con ella. Por estado se
entiende la información que se necesita en cualquieretapa para tomar una
decisión óptima.
2.3 CARACTERÍSTICA 3
La decisión tomada en cualquier etapa indica cómo se transforma el estado en la
etapa actual en el
estado en la siguiente etapa. En muchos problemas, una decisión no determina
con certeza el estado de la siguiente etapa; en lugar de ello, la decisión actual
sólo determina la distribución de probabilidad del estado en la etapasiguiente.
2.4 CARACTERÍSTICA 4
Dado el estado actual, la decisión óptima para cada una de las etapas restantes
no debe depender de estados previamente alcanzados o de decisiones
previamente tomadas. A esta idea se le conoce como principio de optimalidad.
2.5 CARACTERÍSTICA 5
Si los estados del problema se han clasificado en uno de T etapas, debe haber
una fórmula recursiva que relacione el costoo recompensa durante las etapas t,
t+1,…, T con el costo o recompensa de las etapas t +1, t +2,…, T En esencia, la
fórmula recursiva formaliza el procedimiento de marcha atrás.

2.6 Algunas Aplicaciones De La Programación Dinámica Determinística
•
•
•
•
•
•

Modelo De La Ruta Más Corta
Modelo De Volumen-Carga “Mochila”
Modelo Del Numero De Empleados
Modelo De Reemplazo De Equipos...