La resolución de problemas de investigación de operaciones mediante la aplicación del método gráfico permite visualizar su área de solución factible, dentro de la cual es posible hallar un valor máximo o mínimo que permite encontrar una solución óptima.

Sin embargo, a pesar de la precisión del método gráfico solo es posible aplicarlo en aquellos problemas que presentan dos o menos variables, por lo que cuando se plantea un problema con tres o más variables resulta necesario recurrir a un algoritmo denominado método simplex.

Propósito general

Adquirir habilidades para construir modelos de programación lineal y resolverlos a través del método simplex.

Propósitos específicos

• Comprender el método simplex en un problema de programación lineal.
• Solucionar problemas de maximización y minimización con el método simplex.
• Apropiar el uso de herramientas informáticas para la solución de problemas de programación lineal.

El método simplex es un algoritmo matemático que permite aplicar la teoría según la cual, la solución óptima de un problema de investigación de operaciones en procesos determinísticos está asociada con un punto extremo y dicho punto se define por medio de las soluciones básicas de la forma estándar de un modelo de programación lineal.

El matemático y físico George Bernard Dantzig desarrolló el método simplex en 1946 y es considerado el padre de la programación lineal.

Este método trabaja con variables artificiales que se determinan según el número de restricciones que se obtienen del modelo matemático resultante de la formulación de un problema de programación lineal.

Estas variables artificiales pueden ser de «holgura» o de «superávit» y dependen del signo de la igualdad resultante de una restricción. Cuando el signo es menor igual (≤) se usa la variable de holgura y se suma a esta restricción, pero cuando el signo es mayor igual (≥) se usa la variable superávit y se resta.

En este apartado se describen una a una las operaciones o pasos del algoritmo que se aplica en los problemas de programación lineal en los que la optimización hace referencia a la maximización. De igual manera se desarrolla un ejemplo en el que se aplica este algoritmo y se resuelve un problema.

Le invitamos a conocer el algoritmo y a dar clic sobre el ícono de esquemas interactivos para ver el desarrollo del ejercicio.

Tras analizar el caso de la maximización, a continuación se expone el algoritmo que se aplica cuando en un problema de programación lineal la optimización hace referencia a la minimización.

Le invitamos a conocer el algoritmo de minimización y a dar clic sobre el ícono de esquemas interactivos para ver el desarrollo de un ejemplo en el que se aplica.

De acuerdo con Padilla, López y Jaén (s. f.), el método de la M grande es una representación obtenida a partir del método simplex y usada para resolver problemas en los que el origen no forma parte de la región factible de un problema de programación lineal.

Puntualizan los autores que para desarrollar este método se siguen los mismos pasos que en el método simplex cambiando la función objetivo e incluyendo las variables artificiales, las cuales tendrán que ser multiplicadas por un número que sea suficientemente grande para que no se elimine a través de las operaciones.

Este método es llamado «M», pues solo podrá eliminarse cuando se sume o reste con otra M.

En los problemas de programación lineal en los que los límites de las restricciones son exactamente iguales a algo el método simplex no permite un desarrollo óptimo, pues este método hace referencia a la maximización o minimización y se calcula usando los signos de las desigualdades ≤ o ≥. Es por esta razón que para el desarrollo de este tipo de problemas se suele recurrir al método de la M grande, también llamado método de penalización.

Las variables artificiales para trabajar en este apartado dependen del signo de la igualdad resultante de la restricción, tal como se muestra en la imagen que aparece en pantalla.

Le invitamos a conocer los pasos del algoritmo para la aplicación del método de la gran M en un caso de maximización, y a dar clic sobre el ícono de esquemas interactivos para ver un ejemplo de aplicación de este método.

Para recordar... A pesar de que el método de la M grande permite optimizar de una mejor manera que el método simplex estándar, no es tan efectivo como parece, pues depende de la subjetividad en el valor que se le otorgue a la M.

Las variables artificiales que se trabajan en este apartado dependen del signo de la igualdad resultante de una restricción. Cuando el signo es ≤ se debe aplicar una variable de holgura y se suma una restricción Hi; cuando el signo es ≥ se debe aplicar una variable de superávit, se suma una variable R con coeficiente M y se resta la variable Si, y cuando el signo es = se suma la variable R con coeficiente M.

Para resolver este tipo de ejercicios se debe aplicar el algoritmo para la aplicación del método de la M grande.

El método de las dos fases es una representación «obtenida del método simplex, usado para resolver problemas donde el origen no forma parte de la región factible de un problema de programación lineal» (Reyes, s. f.). Su principal diferencia con el método anterior radica en que el método de la M grande puede ser un poco complejo, pues en él prima el valor que le asigne quien lo está desarrollando.

Para resolver un problema con el método de las dos fases se siguen los mismos pasos que en el método simplex, pero se cambia la función objetivo y se incluyen las variables artificiales, pues su objetivo es eludir el uso de la constante que se utiliza en el método de la M grande.

Para recordar... El método de las dos fases es el mecanismo óptimo para resolver problemas de programación lineal.

Este es el método óptimo para resolver problemas de programación lineal, razón por la cual se utiliza para crear herramientas informáticas. Para su aplicación existen dos fases:

Primera fase

Se reemplaza la función objetivo por la maximización de la suma de las variables artificiales diferentes a las de holgura o superávit y se resuelve. Dichas variables son las Ri del modelo, a las cuales se les asigna un coeficiente de menos uno en la función objetivo. Cuando Z de la maximización sea igual a cero se continúa con la segunda fase, de lo contrario el problema tendrá una solución no factible, es decir que no tendrá solución.

Segunda fase

Se inicia con la última iteración de la primera fase eliminando las columnas en las que se encuentren las variables artificiales Ri. Se toma la función objetivo del programa inicial que se halla en el estado primal inicial, se igualan a cero todas las variables artificiales y se eliminan las restricciones por medio de la técnica de Gauss-Jordan.

Algoritmos de maximización con el método de las dos fases Haga clic sobre el enlace para conocer los algoritmos que se deben usar en estas dos fases.

Para resolver problemas de minimización con el método de las dos fases se debe proceder de la siguiente manera:

Primera fase

Se reemplaza la función objetivo por la minimización de la suma de las variables artificiales diferentes a las de holgura o superávit y se resuelve. Dichas variables son las Ri del modelo, a las cuales se les asigna un coeficiente de menos uno en la función objetivo. Cuando Z de la minimización sea igual a cero se continúa con la segunda fase, de lo contrario el problema tendrá una solución no factible, es decir que no tendrá solución.

Le invitamos a conocer el algoritmo de esta primera fase.

Segunda fase

Se inicia con la última iteración de la primera fase eliminando las columnas en las que se encuentren las variables artificiales Ri. Se toma la función objetivo del programa inicial que se halla en el estado primal inicial, se igualan a cero todas las variables artificiales y se eliminan las restricciones por medio de la técnica de Gauss-Jordan.

Le invitamos a conocer el algoritmo de la segunda fase.

Actividad de aprendizaje

Haga clic sobre el enlace para acceder a una actividad que le permitirá poner en práctica los conceptos estudiados en esta unidad.

Material de apoyo

El método simplex es un algoritmo repetitivo que permite mejorar la solución de una función objetivo mediante la utilización de iteraciones o tablas. El proceso finaliza cuando es imposible mejorar el valor de la función objetivo; es decir, cuando se ha encontrado su solución óptima.

Cuando se busca el máximo valor posible de la función se habla de un caso de maximización, pero cuando se busca su valor mínimo posible se habla de minimización. Además de maximizar o minimizar, el método simplex permite resolver problemas que están sujetos a limitaciones o restricciones.

Por otra parte, cuando el problema tiene tres o más variables se recurre al método simplex que únicamente trabaja con restricciones o limitaciones cuyas inecuaciones sean del tipo menor igual o mayor igual, y sus coeficientes independientes sean mayores o iguales a cero.

Trabajar únicamente con los signos matemáticos «≥» y «≤» limita las posibilidades de resolver un problema, pues en algunos casos se hace necesaria la utilización del signo «=», y para ello existe una derivación del método simplex llamada el método de la M grande, que permite resolver este tipo de problemas, pero es muy subjetivo ya que depende del valor que el usuario desee asignarle a la variable M.

En aquellos casos en los que no se pueda aplicar ninguno de los métodos anteriores es posible usar el método de las dos fases, el cual se usa para resolver problemas en los que el origen no forma parte de la región factible de un problema de programación lineal.

Estudio de caso

Haga clic sobre el enlace para acceder un ejercicio que deberá resolver con la herramienta PHP Simplex.