PROGRAMACIN DINMICA

PROGRAMACIN DINMICATareasN de tareas que se procesaranTiempo estimado de terminacin (das)Calificacin sobre el valorCategora 1412Categora 2338Categora 32411Categora 42720Problema de la mochilaUn recipiente con cierta capacidad. Varios conjuntos de elementos con ciertas caractersticas y con cierto valor. Se requiere llenar el recipiente maximizando su valorEtapa 4

X3 = X4 -7d4Etapa 3

X2 = X3 -4d3Etapa 2

X1 = X2 -3d2Etapa 1

X0 = X1 -1d1r4 (X4, d4)= 20d4d4d3d2d1r3 (X3, d3)= 11d3r2 (X2, d2)= 8d2r1 (X1, d1)= 2d1X4 = 10X3 X2 X1 X0 Variables de estadoX3 = X4 -7d4X2 = X3 -4d3X1 = X2 -3d2X0 = X1 -1d1

Funciones de rendimientor4 (X4, d4)= 20d4r3 (X3, d3)= 11d3r2 (X2, d2)= 8d2r1 (X1, d1)= 2d1Se definen como variable de estado XiSon los posibles valores que puede asumir en cada etapa del proceso. Los valores posibles con que se puede entrar a la siguiente etapa.

Se define como variable de decisin diSon los posibles valores que implica la decisin que se tome.

La funcin de rendimiento ri (xi, di)Es el impacto que se tiene de la decisin que se tome y las condiciones con que se entra a la etapa.X1d1*f1(X1)0001122243364485486487488489481048El anlisis comienza al final del proceso. Es conveniente, en la medida de lo posible, elaborar un esquema conceptual del problema de programacin dinmica. Conforme los datos del problema ver la tabla y conforme la notacin matemtica adoptada, se inicia en la etapa 1. r2(X2, d2) + f1(X1)d2*f2(X2)X1 = X2 - 3d2*X2 \ d2012300---00012---02124---042368--1804810--11015812--1122681416-2160781618-2181881620-22029816222432401081624263261r3(X3, d3) + f2(X2)d3*f3(X3)X2 = X3 - 4d3*X3 \ d301200--00012--02124--04238--08341011-111051213-113161615-016671819-11938202122222092423240,2249,1102627261276r4(X4, d4) + f3(X3)d4*f4(X4)X3 = 10 - 7d4*X4 \ d4011027281283La solucin del problema es: valor mximo f4(X4) = 28

En la etapa 4 (Categora de tarea 4) se deben seleccionar o decidir d*4 = 1,La variable de estado para entrar a la etapa 3 es X3 = 3, como se observa en la tabla de la etapa 4,Al entrar en la tabla de la etapa 3, se observa que la decisin es d*3 = 0, no seleccionar una actividad de categora 3, la variable de estado para entrar a la etapa 2 es, ver tabla 3, X2 = 3,Al entrar en la tabla 2, se tiene como decisin d*2 = 1, seleccionar una tarea de categora 2, la variable de estado X1 = 0, ver la tabla 2.Finalmente en la tabla 1, se decide d*1 = 0

No olvidar que la variable de estado son los das que quedan para realizar una accin.Un problema de produccinMesDemandaCapacidad de produccinCapacidad de almacenamientoCosto de produccin por unidadCosto de tenencia por unidadEnero232$175$30Febrero323$150$30Marzo332$200$40N = N de periodos (etapas en el planteamiento de programacin dinmicaDn = demanda durante la etapa n; n = 1, 2, , NXn = variable de estado que representa la cantidad disponible de inventario al principio de la etapa n; n = 1, 2, , Ndn = variable de decisin para la etapa n; la cantidad de produccin para el periodo correspondiente; n = 1, 2, , NPn = capacidad de produccin en la etapa n; n = 1, 2, , NWn = capacidad de almacenamiento al final de la etapa n; n = 1, 2, , NCn = costo de produccin por unidad en la etapa n; n = 1, 2, , NHn = costo de conservacin por unidad de inventario final de la etapa n; N = 1, 2, , NVariables de estadoX3 = 1X2 = X3 + d3 - 2X1 = X2 + d2 - 3X0 = X1 + d1 - 3Funcin de rendimientor1(X1, d1) = 200d1 + 40(X1 + d1 - 3)r2(X2, d2) = 150d2 + 30(X2 + d2 - 3)r3(X3, d3) = 175d3 + 30(X3 + d3 - 2)

Etapa 3(Enero)Etapa 2(Febrero)Etapa 1(Marzo)P3r3 (X3, d3)r2 (X2, d2)r1 (X1, d1)X3 = 1X2 X1 X0 D3W3d3P2D2W2d2P1D1W1d1El problema tiene las siguientes restricciones para cada una de las etapas:

Xn + dn - Dn < Wn; Xn + dn < Wn + Dn

Xn + dn < Pn

Xn + dn > Dn

En cada etapa se desea: min rn (Xn, dn) + fn-1 (Xn-1)

El problema de la etapa 1 es: min r1 (X1, d1) = 200d1 + 40(X1 + d1 - 3)

min r1 (X1, d1) = 240d1 + 40X1 - 120Sujeto a: X1 + d1 < 5 d1 < 3 X1 + d1 > 3X1d*1f1(X1) = r1 (X1, d1) = 240d1 + 40X1 - 120036001240021200300El problema de la etapa 2 es: min r2 (X2, d2) = 150d2 + 30(X2 + d2 - 3) + f1(X1)

min r2 (X2, d2) = 180d2 + 30X2 - 90 + f1(X1)Sujeto a: X2 + d2 < 6 d2 < 2 X2 + d2 > 3X2 \ d2180d2 + 30X2 - 90 + f1(X1)d*2f2(X2)X1 = X2 + d*2 - 30120----M-1--900290002-75073027301El problema de la etapa 3 es: min r3 (X3, d3) = 175d3 + 30(X3 + d3 - 2) + f2(X2)

min r3 (X3, d3) = 205d3 + 30X3 - 60 + f2(X2)Sujeto a: X3 + d3 < 4 d3 < 3 X3 + d3 > 2X3 \ d3205d3 + 30X3 - 60 + f2(X2)d*3f3(X3)X2 = X3 + d*3 - 201231-M12801315212801MesInventario inicialProduccinCosto de produccinInventario finalCosto de tenenciaCosto total mensualEnero12350130380Febrero1230000300Marzo0360000600total12501280