Métodos matemáticos de optimización. El algoritmo Simplex

Abstract

RESUMEN: Con la realización de este trabajo se ha pretendido analizar y comprender el método Simplex partiendo de la Investigación Operativa y seguido de la Programación Lineal. Primero, el trabajo comienza con un capítulo referente a la definición de la Investigación Operativa. También, se expone dónde surgió y cómo evolucionó gracias al avance tecnológico, además de formular el proceso que se debe de seguir para emplearla de manera correcta y llegar a la solución óptima de un problema. A continuación, se relata un pequeño apartado relacionado con la Programación Lineal. En dicho apartado, se abordan cuestiones referidas a la aparición de la Programación Lineal en la II Guerra Mundial pues fue una de las piezas clave para resolver los problemas surgidos en dicha época bélica. Actualmente tiene una gran relevancia, sobre todo en el ámbito empresarial. Asimismo, se explica el procedimiento a seguir para calcular y hallar las soluciones de un problema lineal. Seguidamente, se van a analizar y desarrollar los diferentes pasos de un ejemplo lineal de maximización de la función objetivo con dos variables de manera gráfica ya que con este procedimiento gráfico se podrá entender mejor la siguiente sección: el método Simplex. Posteriormente, el ensayo se va a centrar en el método Simplex, un algoritmo que ha ido evolucionando al mismo tiempo que avanzaban los ordenadores y que nos ayuda a descifrar problemas con más de tres variables. Primero, se explica cómo formular un modelo lineal tanto en su forma estándar como en su forma matricial. Después, se detalla cómo se hallan las soluciones básicas factibles con dicho método y cómo se interpretan geométricamente. Igualmente, se expone el proceso para convertir el problema en forma de tabla y la introducción de las variables artificiales. Todo lo mencionado será explicado con ejemplos para la mejor comprensión. Para finalizar el trabajo, se van a realizar dos casos prácticos desarrollados con el algoritmo Simplex, donde se siguen los pasos explicados en los apartados previos sobre cómo hallar las soluciones, además de comprobar que éstas coinciden con los vértices de la región factible.

ABSTRACT: The aim of this work is to analyse and understand the Simplex method starting from Operations Research and followed by Linear Programming. First, the book begins with a chapter on the definition of Operations Research. It also explains where it arose and how it evolved thanks to technological progress, as well as formulating the process that must be followed in order to use it correctly and arrive at the optimal solution to a problem. This is followed by a short section on Linear Programming. In this section, we deal with issues related to the appearance of Linear Programming in the Second World War, as it was one of the key elements in solving the problems that arose during that period of war. It is still very relevant today, especially in the business world. It also explains the procedure to be followed to calculate and find the solutions to a linear problem. Next, the different steps of a linear example of maximisation of the objective function with two variables will be analysed and developed graphically, as this graphical procedure will help to better understand the following section: the Simplex method. Subsequently, the essay will focus on the Simplex method, an algorithm that has evolved as computers have advanced and that helps us to decipher problems with more than three variables. First, it explains how to formulate a linear model in both its standard and matrix forms. It then details how the basic feasible solutions are found with this method and how they are interpreted geometrically. The process of converting the problem into table form and the introduction of the artificial variables is also explained. Everything mentioned will be explained with examples for a better understanding To conclude the work, we will carry out two practical cases developed with the Simplex algorithm, where we follow the steps explained in the previous sections on how to find the solutions, as well as checking that these coincide with the vertices of the feasible region.