USO DE LA FUNCIÓN BUSCARX() PARA IMPLEMENTAR EL ALGORITMO DE OPTIMIZACIÓN UTILIZANDO EL MÉTODO SIMPLEX EN UNA HOJA DE CÁLCULO

 

Ángel Sánchez Sánchez, M.C. *      Miguel Ángel Contreras Jiménez, Ing. **      Juan José García Rodríguez, M.G.C. *      Eva Mercedes Alvarado Brady, M.A.I. *


Tecnológico Nacional de México

ITS de Poza Rica


*Docente del Tecnológico Nacional de México ,      **Alumno de la Maestría en Ingeniería en el TecNM

Citar

 

Resumen

Se ha propuesto una implementación del método simplex en una hoja de cálculo utilizando principalmente la función BUSCARX() junto con las operaciones de renglón necesarias. Esta implementación permite generar tablas subsecuentes de manera iterativa, incrementando la función objetivo del problema de programación lineal. El proceso consiste en relacionar la información inicial del modelo tabulado con la que se genera sucesivamente, hasta que se alcanza la condición que detiene la ejecución del método simplex. El resultado final muestra el desglose de todas las tablas requeridas para obtener los valores de las variables y la función objetivo en cada paso. Esto conduce a la solución óptima del problema de programación lineal, que incluye las variables de holgura al inicio. En resumen, la propuesta ofrece una forma eficiente de implementar el método simplex en una hoja de cálculo, facilitando el seguimiento y la comprensión del proceso de optimización en problemas de programación lineal.

Palabras Clave: simplex, hoja de cálculo, optimización, automatización.

 

Abstract

A proposal for implementing the simplex method on a spreadsheet is developed, primarily using the XLOOKUP() function along with the necessary row operations to generate subsequent tables iteratively, incrementing the objective function of the linear programming problem being implemented. The subsequent tables are obtained by relating the initial information of the tabulated model to the information being generated until the condition that stops the execution of the simplex method is met. Finally, a breakdown of all the necessary tables is presented to generate each of the values taken by the variables and the achieved objective function at each step until culminating with the solution that leads to the optimization of the objective function of the linear programming model incorporated with its slack variables at the beginning.

Keywords: simplex, spreadsheet, optimization, automatization.

 

Introducción

El uso de hojas de cálculo facilita el cómputo de datos y agiliza su tratamiento, permitiendo generar información con mayor agilidad, el algoritmo clásico de optimización de programación lineal conocido como simplex, se ha implementado en su forma tabular, que por excelencia usa tablas que se incorporan a una hoja de cálculo con relativa facilidad y ayuda a visualizar su comportamiento, así como su evolución y procedimiento al generar tantas tablas como el problema de programación lineal (PL) inicial lo requiera, a partir de la incorporación de los datos que describen al problema a resolver.

La idea se centra en generar las tablas subsecuentes anidando la información inicial con las funciones propias de la hoja de cálculo, y de esta forma desarrollar tantas tablas como lo requiera el algoritmo simplex hasta encontrar la solución que optimiza el planteamiento original utilizando principalmente la función BUSCARX().

El concepto de optimización puede utilizarse para la maximización o para la minimización, el método simplex es un procedimiento algebraico de optimización el cual utiliza conceptos que fundamentalmente son de tipo geométrico y representa un método eficiente para dar solución a problemas de programación lineal (Hillier & Lieberman, 2010).

En problemas de minimización, la condición de optimalidad requiere seleccionar la variable de entrada como la variable no básica con el coeficiente objetivo más positivo en la ecuación objetivo, la regla exacta opuesta del caso de maximización (Taha, 2012).

El algoritmo utilizado, contempla el establecimiento de las siguientes condiciones para el proceso tales como la determinación de la condición de optimalidad en donde la variable de entrada en un problema de maximización (minimización) es la variable no básica con el coeficiente más negativo (positivo) en la fila Z. Los vínculos se rompen arbitrariamente. El óptimo se alcanza en la iteración en la cual los coeficientes en la fila Z son no negativos (no positivos).

La otra condición es la factibilidad para casos de maximización o de minimización, en la que la variable de salida es la variable básica asociada con la relación mínima no negativa con el denominador estrictamente positivo. Los vínculos se rompen arbitrariamente.

El siguiente elemento del proceso de solución contempla el empleo de operaciones de filas de Gauss-Jordan en donde se definen:

 

1. Fila pivote

1. Reemplace la variable de entrada en la columna Básica con la variable de entrada.
2. Nueva fila pivote = Fila pivote actual ÷ Elemento pivote.

2. Todas las demás filas, incluida la Z

Nueva fila = (Fila actual) - (Su coeficiente en la columna pivote) * (Nueva fila pivote).

Los pasos del método simplex son

Paso 0. Determine la solución factible básica inicial.

Paso 1. Seleccione una variable de entrada utilizando la condición de optimalidad.

Deténgase si no hay variable de entrada; la última condición es óptima. De otro modo, prosiga con el paso 2.

Paso 2. Seleccione una variable de salida utilizando la condición de factibilidad.

Paso 3. Aplique los cálculos de Gauss-Jordan para determinar la nueva solución básica. Vaya al paso 1.

MÉTODOLOGÍA

Se parte de la suposición, que la persona que incorpora los datos a la tabla inicial conoce sobre la adecuación del modelo a resolver, para implementarlo en el algoritmo simplex, es decir, incorpora las variables de holgura a cada una de las restricciones haciendo factible la tabla inicial con la solución trivial en el origen.

Con ayuda de la hoja de cálculo Excel en su versión 2002 compilación 1252.22145 con una licencia de suscripción institucional Microsoft Office 365 ProPlus, y a partir de un modelo de programación lineal (PL) cuya función objetivo debe maximizarse, donde intervienen tres variables con igual número de restricciones del tipo “menor que”, se recurre principalmente a la función BUSCARX() entre otras de las funciones de Excel para generar el seguimiento del algoritmo que utiliza el método simplex, que, con ayuda de la forma tabular a través de un proceso recursivo, va dando lugar a diferentes tablas hasta llegar a la tabla final con la información de los valores que van tomando cada una de las variables para ir mejorando la solución hasta optimizar al modelo PL, de esta forma se puede visualizar el valor de la función objetivo en cada interacción.

El modelo propuesto a utilizar para la implementación fue publicado por Saez (2003) en su trabajo de Análisis de Sensibilidad para el curso Fundamento de Investigación de Operaciones en la Universidad Técnica Federico Santa María, Colombia.

 

 

Recordando que por cada restricción del tipo “menor que” (≤) es necesario incorporar una variable de holgura, la propuesta inicial con el modelo a implementar involucra la incorporación una variable de holgura por cada restricción del modelo como lo muestra el modelo PL.

 

 

Se visualiza la tabla inicial de datos donde los datos a incorporar están marcados con un color gris y se muestra en la Tabla 1. Los datos para incorporar son parte de los elementos característicos del método simplex, como lo son el vector cj que requiere de cada uno de los coeficientes que caracterizan a la función objetivo, además de los renglones que contienen a los coeficientes de cada una de las variables involucradas en las restricciones junto con los coeficientes del lado derecho bj del modelo de PL.

 

 

A la tabla inicial se le incorpora una columna y una fila a la izquierda y en la parte superior para identificar las restricciones y el número de variable que corresponden al modelo PL, de igual forma se rescatan la fila y la columna que corresponde al elemento que se debe pivotear, para facilitar los cálculos. Se ocupa una columna más a la derecha para realizar la operación de dividir los elementos del lado derecho entre los coeficientes de la columna de la variable a incorporar a la solución, con la finalidad de encontrar la variable que saldrá de la base. De igual forma se rescata el elemento pivote en la parte superior, con la finalidad de preparar la información que se utiliza para generar las tablas siguientes.

PROPUESTA

Se utiliza la función BUSCARX() para recuperar los elementos de los cálculos posteriores, es decir, la columna y fila que contienen al elemento pivote dentro de la tabla inicial. Para identificar el elemento cj-zj más positivo se incorpora la función MAX() y de forma análoga para ubicar al cociente menor se utiliza la función MIN(), tal como se muestra en Tabla 2.

 

 

Estas operaciones permiten identificar la fila y el elemento pivote para generar la siguiente tabla que asegura ir incrementando la función objetivo. Para generar los elementos de la siguiente tabla se deben realizar las operaciones de renglón que garanticen la entrada de la variable seleccionada cuyo coeficiente es el mayor en el vector cj-zj y la salida de la variable básica con coeficiente calculado más pequeño en ambos casos debe ser mayor a cero. La incorporación de las funciones que permiten las operaciones de renglones se muestra a continuación en la Tabla 3.

 

 

Al interior de la tabla se requieren operaciones de renglón que garanticen la incorporación de la variable entrante y la asignación como variable básica, esto se logra siempre manipulando al renglón que contiene a la variable entrante divido entre el pivote y para el resto se debe multiplicar al renglón por el inverso aditivo del número que se requiere hacer la unidad y sumado al renglón original, bajo esto dos supuesto se utiliza una condicional que realice una de las dos acciones, comparando el número de la fila con la fila seleccionada donde se ubica la variable que se incorpora a la solución básica del modelo.

CONCLUSIÓN Y RECOMENDACIONES

El trabajo cumple el propósito al generar las tablas del algoritmo del método simplex, facilitando los cálculos reiterativos que se presentan en cada una de las tablas que muestran el avance ordenado y sistemático para llegar a la solución óptima del modelo planteado.

Se ha probado con distintos valores y se ha llegado a la solución final de forma exitosa, sin embargo, se comprueba que el número total de tablas generadas puede superar al número declarado, para lo cual se requiere copiar la última tantas veces como sea necesario para anidar las respuestas con respecto a la anterior hasta lograr la solución final.

Se logra generar un procedimiento automatizado para un problema con tres variables y tres restricciones, que se puede generalizar expandiendo las opciones a un número finito de n variables y aplicar a diferentes áreas de la ciencia.

Se recomienda hacer uso de la función SI.ERROR() para evitar la aparición de inconsistencias en los cálculos, se debe evitar el uso generalizado de la función MIN() al encontrar el número más pequeño del coeficiente del lado derecho, ya que se debe descartar aquellos valores que toman valores negativos.

BIBLIOGRAFÍA Y REFERENCIAS

1. Hiller & Leberman. (2010). Introducción a la Investigación de operaciones.México: MacGrawHill.


2. Saez Robert, E. (2003). Fundamentos de Investigación de Operaciones I.(U. T. María, Ed.) Obtenido de Análisis de Sensibilidad: https://www.inf.utfsm.cl/~esaez/fio/s2_2003/apuntes/sensibilidad-2003-2.pdf


3. Taha, H. (2021). Investigación de operaciones.Hiller & Leberman. (2010). Introducción a la Investigación de operaciones. México: MacGrawHill. Saez Robert, E. (2003). Fundamentos de Investigación de Operaciones I. (U. T. María, Ed.) Obtenido de Análisis de Sensibilidad: https://www.inf.utfsm.cl/~esaez/fio/s2_2003/apuntes/sensibilidad-2003-2.pdf Taha, H. (2021). Investigación de operaciones. México: Pearson.