programación dinámica

El modelo de volumen de carga o mochila
El modelo de volumen de carga o mochila representa un modelo característico de asignación de recursos, en el cual se reparte un recurso limitado entre una cantidad finita de actividades (económicas). El objetivo es maximizar una función de retribución asociada.
El modelo clásico de la mochila tiene que ver con el caso de un soldado (o un montañista) quedebe decidir cuáles son los artículos más valiosos que debe llevar en su mochila, también llamado problema de conjunto de fuga o equipo de vuelo, en el que un piloto de un avión a reacción debe determinar los artículos más valiosos que debe llevar a bordo y el problema de carga del contenedor en el que un barco con capacidad limitada de volumen o peso se carga con fletes valiosos.
La ecuaciónrecursiva para desarrollar el problema general se tiene:
: Representa la capacidad limitada (Peso) en lb, T, kg, etc.
: El número de artículos i
: Cantidad de unidades del artículo i en la mochila
: Ingreso por unidad del artículo i
Peso por unidad del artículo i

El problema general se representa con el siguiente programa lineal entero:

Sujeto a:


Los elementos del modelo son:
Laetapa i se representa con el articulo i, i=1, 2, 3,….., n.
Las alternativas en la etapa i, se representan por , la cantidad de unidades del articulo i que entran en la mochila. El ingreso correspondiente es . Donde es el máximo entero menor o igual con = 0, 1, 2, … , n.
El estado en la etapa i se representa por Xi, el peso total asignado a las etapas (artículos) i, i+1,….,n. Esta definición serefleja que la restricción del peso es la única que vincula entre sí a todas las etapas
Definiremos a:
Como el ingreso máximo para las etapas i, i+1 y n dado el estado
La forma más sencilla de determinar la ecuación recursiva es un procedimiento de dos pasos
Paso 1. Expresar en función de como sigue
.
= 0,1,.....,


Paso 2. Expresar , en función de para asegurar que el ladoizquierdo, , sea función solo de . Por definición, (Representa el peso que se utiliza en la etapa i)
Así, , y la ecuación recursiva apropiada es:

= 0,1,.....,

Ejemplo
1) Un barco de 4 toneladas se carga con uno o más de tres artículos. La siguiente tabla muestra el peso unitario, wi en toneladas, y el ingreso por unidad ri en miles de dólares, para el articulo i. Como los pesos unitarioswi y el peso máximo W son enteros, el estado xi solo debe tener valores enteros ¿Cómo se debe cargar el barco para maximizar los ingresos totales?:
Articulo
wi = Toneladas
ri = Miles de dólares
1
2
31
2
3
47
3
1
14

= Representa la capacidad limitada. W= 4
: El número de artículos i. i = 1, 2 y 3
: Cantidad de unidades del artículo i en la mochila. , y
: Ingreso por unidad delartículo i. , y
Peso por unidad del artículo i. , y

Etapa 3.
No se conoce de antemano el peso exacto por asignar a la etapa 3 (artículo 3), pero debe asumir uno de los valores 0, 1, … , 4 (porque W=4 TON). Los estados X3=0 y X3=4, respectivamente, representan los casos extremos de no embarcar nada del articulo 3 y de asignar a el toda la capacidad del barco. Los valores restantes de X3(= 1, 2 y 3) implican una asignación parcial de la capacidad del barco al artículo 3. De hecho, el intervalo mencionado de valores de X3 cubre todas las asignaciones posibles de capacidad del barco al artículo 3.
Como w3=1 TON por unidad, la cantidad máxima de unidades que se pueden cargar del artículo es 4/1=4, lo que significa que los valores posibles de m3 son 0, 1, 2, 3 y 4. Solo es posibleuna m3 alternativa si w3m3 X3. Así, todas las alternativas no factibles (aquellas para las que w3m3 > X3) quedan excluidas. La ecuación siguiente es la base para comparar las alternativas de la etapa 3:

El cuadro siguiente compara las alternativas factibles para cada valor de X3
Estados posibles en la etapa 3 (X3)
14m3
Ganancia optima

Cantidad optima de artículos 3
()

m3 = 0
m3 =1...