El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.
ECUACIÒN RECURSIVA:
Como acudir a datos anteriores para lograr el objetivo.
En los tipos de Programación dinámica tenemos:
- Deterministica
- Probabilistica.
Donde tiene mayor aplicación la Programación Dinámica es en la resolución de problemas de optimización. En este tipo de problemas se pueden presentar distintas soluciones, cada una con un valor, y lo que se desea es encontrar la solución de valor óptimo (máximo o mínimo).
Tenemos:
Ejercicio Nº 1:
- Un barco de 4 toneladas se carga con uno o más de tres artículos. La siguiente tabla proporciona el peso por unidad, Wi, en toneladas y la utilidad por unidad, Ri en miles de dolares por el articulo i ¿Cómo se debe cargar el barco el barco para maximizar la utilidad total?
Debido a que los pesos por unidad ,Wi y el peso màximo W asumen todos los valores enteros, el estado Xi, solo puede asumir valores enteros.
Etapa 3:
El peso exacto que se va asignar a la etapa 3 (Articulo 3) no se conoce con anticipación pero debemos suponer uno delo valores 0,1,2,3,4 (Debido a que W= 4 toneladas). Los estados X3= 0 y X3= 4, representan los casos extremos de no embarcarle el artículo 3 y de asignarle todo el barco.
Debido a que W3= 1 tonelada por unidad, el número máximo de unidades de artículo 3 que se puede cargar es de 4/1 = 4, entonces los posibles valores para M= 0,1,2,3,4
Las siguientes tablas compara las alternativas factible para cada valor de X3
Se debe tener en cuenta la utilidad por unidad.
Etapa 2:
Debido a que W2= 3 tonelada por unidad, el número máximo de unidades de artículo 2 que se puede cargar es de 4/3 = 1, entonces los posibles valores para M= 0,1
Se debe tener en cuenta la utilidad por unidad- 47 M2
Etapa 1:
Debido a que W1= 2 tonelada por unidad, el número máximo de unidades de artículo 1 que se puede cargar es de 4/2 = 2, entonces los posibles valores para M= 0,1,2
Se debe tener en cuenta la utilidad por unidad- 31 M3
La solución Óptima se determina de la siguiente manera :
Dado que:
W= 4 toneladas ( De la etapa 1)
X1= 4 da la alternativa óptima de M1 = 2 ; lo que significa que se cargarán en el barco dos unidades del articulo 1. La utilidad asociada es de 62000 dólares.
Ejercicio Nº 2:
Una compañía necesita determinar la política de reemplazo óptimo para una máquina que en la actualidad tiene 3 años, durante los 4 años próximos( n= 4) es decir, hasta principios del año 5. La siguiente tabla proporciona los datos del problema.
La compañía requiere que una máquina de seis años se reemplace. El costo de una máquina nueva es de 100 000 dólares.
La determinación de los valores factibles para la edad de la máquina en cada etapa es un tanto difícil .
Resumen de la Red en el siguiente diagrama:
 |
| R = Reemplazarla o K= Conservarla. |
Separamos por etapas, para empezar a trabajar:
Al principio del año 2, si ocurre el reemplazo la máquina nueva tendrá un año de edad , de lo contrario con la máquina vieja tendrá 4 años. La misma lógica aplica al principio de los años 2 al 4. Si una máquina de un año de edad se reemplaza al principio de los años 2 y 3, su reemplazo tendrá un año al principio del siguiente año. Además, al principio del año 4, una máquina de cinco años se debe reemplazar y al final del año 4 recuperamos las máquinas.
La red muestra que al principio del año 2, las edades posibles de las máquinas son 1 y 4 años. Para principios del año 3, las edades posibles son 1,2,5 años y para principios del año 4, las edades posibles son 1,2,3 y 6 años.
ETAPA 4:
ETAPA 2:
ETAPA 1:
La solución Óptima se determina de la siguiente manera :
Al principio del año 1 la decisión óptima dada t= 3 es reemplazar la máquina. Por tanto la máquina nueva tendrá un año al principio del año 2 y t= 1 al principio del año 2 requiere ya sea conservar o reemplazar la máquina. Si se reemplaza, la máquina nueva tendrá 1 año al principio del año ; de lo contrario, la máquina que se conservo tendrá 2 años.
El proceso continua asì hasta el cuarto año.
Las políticas alternativas óptimas empezando en el año 1 son ( R,K,K,R) y (R,R,K,K). El costo total es de 55300 dólares.
.jpg)
