PROGRAMACION DINAMICA A UNA
OPERACIÓN MINERA SUBTERRANEA
CURSO:
INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES
PROFESOR:
[Link] TURRIARTE CARLOS
INTEGRANTES:
DURAND VELI, ABEL 20152605G
HUAMAN BAZAN, DANY 20151161H
JIMENEZ ROMAN, JENNIFER 20152569K
SANTIVAÑEZ MILLA, CRISTIAN 20154505J
INTRODUCCION
La programación dinámica es un
método matemático de optimización por
excelencia, muy útil en la toma de
decisiones de la gerencia a la hora
planificar un proyecto, nos permite
optimizar variables que permitan reducir
costos y disminuir tiempos de trabajo.
La programación dinámica se desarrolla
solucionando subproblemas del
problema para luego encontrar la
solución optima del problema en su
conjunto.
OBJETIVOS
Comprender los diferentes usos de la
programación dinámica en una operación minera
subterránea.
Comprender de forma analítica la programación
dinámica como método de optimización.
ORIGEN
Después de que la investigación de operaciones
surgiera para abordar problemas específicos de la
segunda guerra mundial en los años 40,
rápidamente se vio que estas podían servir en
otras áreas de aplicación. Años posteriores se
investigaron nuevos temas de investigación , entre
los cuales se encontraba la teoría de los procesos
de decisión en múltiples pasos, que Richard
Bellman (1920 – 1984) abordo alrededor de 1952, y
para los cuales fue pensada originalmente la
programación dinámica.
PROGRAMACION DINAMICA
La programación dinámica es una
técnica que permite determinar de
manera eficiente las decisiones que
optimizan el comportamiento de un
Sistema que evoluciona a lo largo
de una serie de etapas, es decir, el
objetivo de la programación es
encontrar la secuencia de
decisiones que optimiza el
comportamiento de un proceso
polietapico.
CONCEPTOS MATEMATICOS BASICOS
TEOREMA DE OPTIMALIDAD DINAMICA
Bellman enuncio el siguiente teorema:
Una política óptima tiene la propiedad de que cualquiera
que sea el estado inicial y las decisiones iniciales, las
decisiones restantes deben constituir una política óptima
en relación con el estado resultante de las primeras
decisiones (de atrás hacia adelante).
CONCEPTOS MATEMATICOS BASICOS
EL DUAL CORRESPONDIENTE
BHAVAMANI Y CHEN enunciaron el dual correspondiente al teorema anterior
y este es como sigue: Una política óptima tiene la propiedad de que
cualesquiera que sean los estados y decisions siguientes; las decisiones
precedentes deben constituir una política óptima con respecto al estado
que sigue a la ultima decision (de adelante hacia atras).
CARACTERISTICAS DE LOS PROBLEMAS
DE LA PROGRAMACION DINAMICA
El problema se puede dividir en etapas que requieren una política de
decisión en cada una.
Cada etapa tiene cierto numero de estados asociados a ella.
El efecto de la política de decisión en cada etapa es transformar el
estado actual en un estado asociado con la siguiente etapa.
El procedimiento de solución esta diseñado para encontrar una
política optima para el problema.
Dado un estado actual, una política óptima para las etapas
restantes es independiente de la política adoptada en las
etapas anteriores (principio de optimalidad).
El procedimiento de solucion se inicia al encontrar la política óptima
para la ultima etapa.
Se dispone de una relación recursiva que identifica la política óptima
para la etapa n dada la política óptima para la etapa (n + 1).
APLICACIÓN:
Un carrito minero de 4 toneladas puede cargar material mineralizado de cobre con 3
diferentes leyes, la siguiente tabla muestra el peso unitario (wi) en toneladas y el ingreso
unitario (ri) en dólares por tonelada, para el ítem i ¿Cómo se debe cargar el carrito para
maximizar el rendimiento total?
MATERIAL 𝐰𝐢 (tn) 𝐫𝐢 ($/tn)
MINERALIZADO
1 2 31
2 3 47
3 1 14
Donde el material mineralizado 1 tiene de ley de 0.8 % de cobre; material 2, ley de 1% de
Cu y material 3, ley de 0.5 % de Cu.
Como la unidad peso wi y el peso máximo w son enteros, el estado Xi solo
asume valores enteros.
Etapa 3:
El peso exacto que se asignará a la etapa 3 (elemento 3) no se conoce
con anticipación, pero se puede suponer uno de los valores 0, 1, ... y 4
(porque w = 4 toneladas y w3 = 1 tn). Un valor de m3 es factible solo si w3
m3 ≤ x3. Por lo tanto se excluyen todos los valores no factibles (con w3 m3
> x3). El ingreso para el articulo 3 es 14 m3. En consecuencia, la ecuación
recursiva para la etapa 3 es:
máx
f3 x 3 = 14m3
m3 = 0,1, … , 4
La siguiente tabla resume los cálculos para la etapa 3:
14m3 SOLUCION
OPTIMA
x3 m3 = 0 m3 = 1 m3 = 2 m3 = 3 m3 = 4 f3 (x3 ) m3
0 0 - - - - 0 0
1 0 14 - - - 14 1
2 0 14 28 - - 28 2
3 0 14 28 42 - 42 3
4 0 14 28 42 56 56 4
Etapa 2:
4 máx
máx m2 = = 1, o m2 = 0, 1, f2 x2 = 47m2 + f3 x2 − 3m2
3 m3 = 0,1
47m2 + f3 x2 − 3m2 SOLUCION
OPTIMA
x2 m2 = 0 m2 = 1 f2 x2 m∗2
0 0+0=0 - 0 0
1 0 + 14 = 14 - 14 0
2 0 + 28 = 28 - 28 0
3 0 + 42 = 42 47 + 0 = 47 47 1
4 0 + 56 =56 47 + 14 = 61 61 1
Etapa 1:
4 máx
máx m1 = = 2, o m1 = 0, 1, 2, f1 x1 = 31m2 + f2 x1 − 2m1
2 m3 = 0,1,2
31m2 + f2 x1 − 2m1 SOLUCION
OPTIMA
x1 m1 = 0 m1 = 1 m1 = 2 f1 x1 m1∗
0 0+0=0 - - 0 0
1 0 + 14 = 14 - - 14 0
2 0 + 28 = 28 31 + 0 = 31 - 31 1
3 0 + 47 =47 31 + 14 = 45 - 47 0
4 0 + 61 = 61 31 + 28 = 59 62 + 0 = 62 62 2
la solución óptima se determina de la siguiente manera: Dado w = 4
toneladas, del estado 1, X1 = 4 se da la alternativa óptima m1∗ = 2, lo
que significa que 2 unidades del material mineralizado 1 se
cargarán en el carrito minero.
Esta asignación deja X2 = X1 – 2 m1∗ = 4 – 2 x 2 = 0 para las etapas 2 y
3. De la etapa 2, X2 = 0 da por resuelto, m2∗ = 0, lo cual deja X3 = X2 -
3m2 = 0 – 3 x 0 = 0 unidades para la etapa 3.
Luego, a partir de la etapa 3, X3 = 0 da m∗3 = 0. Por lo tanto, la
solución óptima completa son m1∗ = 2, m2∗ = 0 y m∗3 = 0. El rendimiento
asociado es f1 4 = 62 dólares por tonelada.
GRACIAS