Método Simplex
El método simplex es un algoritmo usado para resolver problemas
de programación lineal. En este método, buscamos el valor óptimo
de una función objetivo, sujeto a una serie de restricciones. Para
entender el proceso del método simplex, vamos a explorar cada uno
de sus pasos de manera detallada.
por MANUEL ESTUARDO MORALES GONZALEZ
Formulación del Problema
Función Objetivo Restricciones
Definimos la función objetivo que queremos maximizar Definimos las restricciones del problema en forma de
o minimizar. Esta función representa la cantidad que ecuaciones o inecuaciones. Estas restricciones
buscamos optimizar en el problema. Por ejemplo, en un representan limitaciones o recursos disponibles para la
problema de producción, la función objetivo podría ser la solución del problema. Por ejemplo, en un problema de
maximización del beneficio o la minimización del coste producción, las restricciones podrían ser la cantidad de
de producción. materia prima disponible, el tiempo de producción o la
capacidad de almacenamiento.
Convertir a Forma Estándar
Ecuaciones Forma Estándar
Para trabajar con el método simplex, necesitamos El objetivo es convertir el problema a una forma
asegurar que todas las restricciones estén expresadas estándar, donde todas las restricciones son ecuaciones
como ecuaciones. Si una restricción es una inecuación, y las variables son no negativas. La función objetivo
la convertimos a una ecuación añadiendo una variable debe ser maximizada. Si la función objetivo es
de holgura. Estas variables de holgura representan la minimizada, se multiplica por -1.
cantidad de recursos no utilizados en cada restricción.
Las variables de holgura siempre son no negativas.
Tabla Simplex Inicial
Tabla Coeficientes Solución Inicial
La tabla simplex es una tabla que Cada celda de la tabla contiene La tabla simplex inicial
representa el problema de un coeficiente. Los coeficientes representa la solución básica
programación lineal en forma de la función objetivo se escriben inicial del problema. La solución
matricial. Las columnas en la última fila, mientras que los básica inicial se obtiene
representan las variables, coeficientes de las restricciones asignando valores de cero a
incluyendo las variables de se escriben en las filas todas las variables no básicas.
holgura, y las filas representan correspondientes. La columna de Las variables básicas tienen
las restricciones. La última fila recursos representa las valores que se pueden
representa la función objetivo. constantes de cada restricción. determinar a partir de la tabla
inicial.
Identificar la Columna Pivote
Coeficiente Negativo Variable de Entrada
En la fila de la función objetivo, buscamos el coeficiente La columna pivote representa la variable de entrada. Es
más negativo. Esta columna representa la variable no decir, la variable no básica que se convertirá en variable
básica que, si se aumenta su valor, causará una mejora básica en la siguiente iteración del método simplex.
en la función objetivo. En caso de que la función objetivo
sea minimizada, se busca el coeficiente más positivo.
Identificar la Fila Pivote
Cociente Variable de Salida
Para determinar la fila pivote, calculamos el cociente La fila con el cociente más pequeño será la fila pivote.
entre los valores de la columna de recursos y los La variable básica correspondiente a esta fila será la
coeficientes positivos de la columna pivote. Esto se hace variable de salida. La variable básica que se convertirá
para cada fila que contiene un coeficiente positivo en la en no básica en la siguiente iteración del método
columna pivote. simplex.
Operación Pivote
1 Convertir Pivote 2 Convertir Elementos
a0
Realizamos operaciones
en la tabla para convertir Para convertir los demás
el pivote en 1. Se divide elementos de la columna
cada elemento de la fila pivote en 0, se restan
pivote por el valor del múltiplos apropiados de la
pivote. fila pivote a las demás
filas.
3 Nueva Tabla Simplex
La tabla resultante es una nueva tabla simplex, que
representa una solución básica diferente del problema. La
solución básica representa una combinación de valores de las
variables que satisface las restricciones del problema. El valor
de la función objetivo se calcula con esta nueva solución
básica.
Repetir
Repetición Solución Óptima
Repetimos los pasos 4-6 hasta que no haya más Cuando ya no existen coeficientes negativos en la fila de
coeficientes negativos en la fila de la función objetivo. la función objetivo, la última tabla simplex representa la
En cada iteración, identificamos una nueva columna solución óptima del problema. Se puede leer
pivote, una nueva fila pivote y realizamos la operación directamente la solución óptima de la tabla simplex,
pivote. donde la variable básica correspondiente a cada
restricción tiene un valor determinado. Los valores de la
función objetivo y las variables básicas representan la
solución óptima del problema.