Delineación de zonas de manejo rectanguares en agricultura usando generación de columnas

Abstract

Resumen extenso ver multimedia o impresoEn la presente tesis se propone y desarrolla una estrategia algorítmica de resolución para el problema de dividir un terreno agrícola en zonas de manejo sitio-específico rectangulares. Este es un problema de programación lineal entera propuesto por Cid-García et al. (2013), el cual es extendido con posterioridad por Albornoz et al. (2014) a uno bi-objetivo. En este último se minimiza la cantidad de zonas en las que se divide un terreno de cultivo y se maximiza la homogeneidad interna de estas zonas (la homogeneidad interna de una zona es medida a través de su varianza, que es calculada en base a un muestreo geo-referenciado del suelo). Se destaca que no es necesario modificar la formulación original del problema para aplicar el método de generación de columnas en su resolución. En este contexto, su relajación lineal puede ser considerada como el Problema Maestro, y es posible derivar un Subproblema cuya resolución permite encontrar las columnas asociadas a las respectivas variables del Problema Maestro. Este Subproblema resulta ser un problema de programación no lineal entera, cuya resolución mediante métodos genéricos es bastante costosa en términos computacionales. No obstante, es posible resolver este problema mediante la simple enumeración parcial o total de sus soluciones factibles, lo que se logra en tiempos bastante razonables. Se exploraron varias alternativas en cuanto a la forma en que se exploran las soluciones factibles del Subproblema, y la extensión de esta búsqueda en cada iteración del algoritmo de generación de columnas. El algoritmo finaliza al encontrar la solución para el Problema Maestro, es decir, para la relajación lineal del problema original. Solo terminada las iteraciones del algoritmo, se impone la condición de integralidad a las variables del Problema Maestro Reducido resultante, que es resuelto a optimalidad. Los algoritmos se implementaron en AMPL, y cada Problema Maestro Reducido, incluyendo el que es resuelto en variables enteras, se resuelve utilizando CPLEX 12.4. Los resultados obtenidos son muy satisfactorios en la medida que se incrementa el tamaño del problema, e indican que la mejor alternativa es proponer nuevas zonas (soluciones factibles del Subproblema) de tamaños cada vez menores en la medida que se desarrolla el proceso de generación de columnas.