Desarrollo e Implementacion de Cortes en el Problema de Knapsack con Precedencias para Mejorar el Rendimiento en la Obtencion de Soluciones Enteras
Professor Advisor
dc.contributor.advisor
Espinoza González, Daniel
es_CL
Author
dc.contributor.author
Diaz Muñoz, Adrian Eduardo
es_CL
Staff editor
dc.contributor.editor
Facultad de Ciencias Físicas y Matemáticas
es_CL
Staff editor
dc.contributor.editor
Departamento de Ingeniería Industrial
es_CL
Associate professor
dc.contributor.other
Weintraub Pohorille, Andrés
Associate professor
dc.contributor.other
Epstein Numhauser, Rafael
Associate professor
dc.contributor.other
Durán Maggiolo, Guillermo
Admission date
dc.date.accessioned
2012-09-12T18:11:56Z
Available date
dc.date.available
2012-09-12T18:11:56Z
Publication date
dc.date.issued
2011
es_CL
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/102532
Abstract
dc.description.abstract
La industria minera del cobre forma un pilar fundamental en la economía de Chile y representa el 13% del PIB; además se abastece el 30% de la demanda a nivel mundial. Esta industria utiliza generalmente dos metodologías de explotación sobre los yacimientos: minería a cielo abierto y subterráneo. Ambas exhiben una gran complejidad en sus operaciones, lo que incide en la planificación de mediano y largo plazo. En esta tesis se trata el problema de la planificación de la extracción con secuenciamiento sobre un yacimiento que será explotado por una minería a cielo abierto. El modelo del secuenciamiento, se describe por: restricciones de capacidad de explotación; restricciones de precedencias, que inducen los segmentos de material que se deben extraer para alcanzar el depósito; y la naturaleza binaria de las variables de decisión que determinan: cuándo y cuál segmento de material se debe o no se debe explotar. La solución de este problema tiene como objetivo maximizar el valor presente neto del yacimiento. Sin embargo, obtener esta solución para los yacimientos reales es complejo, ya que el modelo de estos depósitos, exhiben una gran cantidad de restricciones y variables de decisión. Luego, para obtener una buena solución, se relaja la integralidad de las variables, y se mejora sucesivamente el problema relajado en base a desigualdades válidas fortalecidas (cortes). Lo anterior permite obtener una solución más cercana a la solución entera óptima, y a su vez un mejor valor presente neto del yacimiento.
La metodología que se utilizó para refinar el modelo relajado se basó en la teoría de separación que fue introducida por Gomory en 1969. Esta teoría permite inferir desigualdades válidas que satisfacen las condiciones de integralidad del problema de optimización entera, pero que son inadmisibles para la solución relajada. Cuando estas desigualdades se agregan al problema relajado de forma sucesiva, se obtiene cada vez una nueva solución que se aproxima más a la solución entera óptima.
En esta tesis se implementaron dos procedimientos para inferir las desigualdades. El primero, consiste en inferir una colección de desigualdades, en función de una técnica que considera de manera explícita el secuenciamiento del problema de optimización; y el segundo, determina una colección de cortes a partir del proceso constructivo de transformar un modelo con secuenciamiento a un modelo sin secuenciamiento. Cada procedimiento se aplicó de forma independiente y simultánea sobre un conjunto cuantioso de instancias de yacimientos simulados. Sobre esta colección se computaron dos métricas de calidad. La primera, estima la aproximación del modelo relajado mejorado respecto del modelo original; y la segunda, estima el cierre del gap entre las soluciones emitidas por ambos modelos. Ambas métricas se representan en gráficos de desempeño, para evaluar y analizar el valor promedio del rendimiento; y el comportamiento general que tuvo cada configuración.
En base a los resultados de yacimientos simulados y respecto de la mejor configuración de corte; se computó que el cierre promedio del gap alcanzó el 53.84 %; y la aproximación promedio del modelo relajado mejorado respecto del original alcanzó el 99.26 %.