Análisis de complejidad y resolución práctica de un problema de expansión empresarial.

Abstract

Este Trabajo de Fin de Grado es un estudio de las expansiones empresariales de forma principalmente teórica cuyo objetivo principal es exponer, practicar y ampliar algunos conocimientos aprendidos en el grado de Ingeniería Informática, e implementar una herramienta capaz de ayudar a tomar decisiones de expansión empresarial pese a manejar situaciones simplificadas. Comenzaremos explicando conceptos de complejidad computacional del tiempo y del espacio que serán importantes en el estudio y el algoritmo minimax. Continuaremos estableciendo la definición del problema de expansión empresarial de forma teórica. Una gran parte del trabajo se dedicará al análisis de la complejidad del problema. Primero demostraremos que pertenece a PSPACE usando un algoritmo minimax y después reduciremos polinómicamente el conocido problema PSPACE-completo TQBF a nuestro problema de expansión empresarial. Para ello, encontraremos una transformación de las posibles entradas de TQBF a entradas de nuestro problema de forma que sólo sea posible expandirse de una forma determinada que garantizará que la solución del problema de expansión sea siempre la misma que la del problema TQBF original. A continuación, explicaremos la herramienta que hemos desarrollado. Esta herramienta es capaz, entre otras cosas, de resolver problemas de expansión empresarial y TQBF y simular manualmente situaciones de expansión concretas. Estudiaremos el rendimiento de esta herramienta en función de varios parámetros. La herramienta utilizará un algoritmo minimax con poda alfa-beta. Habiendo demostrado la intratabilidad del problema, será necesario utilizar métodos heurísticos para resolverlo de forma subóptima. Concluiremos el estudio usando la herramienta desarrollada para estudiar un caso de expansión empresarial.This Final Degree Project is a study of business expansions in a mainly theoretical way whose main objectives are to showcase, apply and expand some concepts learned in the Computer Science Engineering degree, and to implement a tool capable of, despite handling simplified situations, helping to make business expansion decisions. We will begin explaining some computational complexity problems that will be important in the study and the minimax algorithm. Then, we will establish the theoretical definition of the problem of business expansions. A large part of the project will be devoted to the analysis of the complexity of the problem. First, we will prove it belongs to PSPACE using a minimax algorithm and then we will polynomically reduce the well-known PSPACE problem TQBF to our business expansion problem. To accomplish this, we will find a transformation of the possible inputs of TQBF to inputs of our problem so that it is only possible to expand in a certain way, which will guarantee that the solution of TQBF and the expansion problem match for every possible pair of inputs. Next, we will explain the tool we have developed. This tool is capable of, among other things, solve business expansion and TQBF problems and simulate concrete expansion situations manually. We will study the performance of this tool depending on various parameters. The tool will use a minimax algorithm with alpha-beta pruning. Having proven the intractability of the problem, it will be necessary to use heuristic methods to solve it suboptimally. We will conclude the study using the tool we have developed to study a case of business expansion.