Resolviendo problemas de programación lineal usando el método simplex

La programación lineal es una manera de lograr los mejores resultados en un modelo matemático. Este modelo está representado por relaciones lineales. El propósito de la programación lineal es encontrar el valor máximo o mínimo de una cantidad particular, que puede expresarse como una ecuación en restricciones específicas. El método simplex es un algoritmo popular usado para resolver problemas de programación lineal.

¿Qué es el método simplex?

El método simplex es un procedimiento paso a paso para resolver problemas de programación lineal. Está diseñado para manejar ecuaciones con más de dos variables y restricciones más complejas. La belleza del método simplex es que convierte el problema en un proceso sistemático usando una forma tabular llamada un tableau simplex.

Problema de programación lineal

Antes de profundizar más en el método simplex, entendamos cómo es un problema de programación lineal. Un problema típico de programación lineal tendrá lo siguiente:

1. Una función objetivo para maximizar o minimizar.
2. Restricciones en forma de desigualdades lineales.
3. Variables no negativas.

Por ejemplo:

Maximizar: Z = 3x + 2y
sujeto a:
2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x, y ≥ 0

Aquí, Z es la función objetivo que se quiere maximizar. Las restricciones están representadas por desigualdades. Ambas variables x e y deben ser mayores o iguales a cero.

Pasos del método simplex

El método simplex involucra varios pasos principales:

Paso 1: Convertir desigualdades en ecuaciones

Convertir desigualdades en igualdades añadiendo variables de holgura. Las variables de holgura representan la diferencia entre los lados izquierdo y derecho de la desigualdad.

Considere las restricciones:

2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24

Añadir las variables de holgura s1, s2 y s3 para cambiarlas:

2x + y + s1 = 18
2x + 3y + s2 = 42
3x + y + s3 = 24

Ahora, las ecuaciones lineales tienen variables de holgura que inicialmente se establecen en cero.

Paso 2: Configurar el tableau simplex

Crear una tabla simplex inicial a partir de las ecuaciones que transformaste. La tabla se ve algo así:

| x | y | s1 | s2 | s3 | Solución |
, 2 | 1 | 1 | 0 | 0 | 18 |
, 2 | 3 | 0 | 1 | 0 | 42 |
, 3 | 1 | 0 | 0 | 1 | 24 |
, -3 | -2 | 0 | 0 | 0 | 0 |

Nota: La fila inferior se forma restando los coeficientes de la función objetivo. Esta fila ayuda a determinar la optimización.

Paso 3: Identificar el elemento pivote

Se selecciona un elemento pivote para cambiar la solución de tal manera que tome nuevas dimensiones hacia la solución óptima. Los puntos principales en este proceso incluyen:

• Seleccionar el número más negativo en la fila inferior de la tabla. Este será la columna pivote.
• Calcular la proporción de los valores de solución con los coeficientes en la columna pivote (ignorando coeficientes cero y negativos). La proporción positiva más pequeña determinará la fila pivote.

Por ejemplo:

Proporción: (18/2) = 9, (42/2) = 21, (24/3) = 8 

La proporción más pequeña es 8, que corresponde a la fila pivote. Y para este ejemplo, dado que -3 es el más negativo en la fila inferior, la columna pivote es la que tiene 3.

Paso 4: Realizar operaciones de fila

Utilizar operaciones elementales de fila para cambiar el elemento pivote a 1 y ajustar los otros elementos en la columna a 0. Este paso asegura la convergencia hacia una solución óptima.

Paso 5: Iterar

Repetir los pasos 3 y 4 hasta que no haya más números negativos en la fila inferior. Cuando se alcanza este punto, la solución factible original encontrada es óptima.

Un ejemplo práctico usando el método simplex

Crisis

Maximizar la función Z = 5x + 4y, sujeta a:

y + 2x ≤ 20 
2x + 3y ≤ 30 
2x + y ≤ 15 
x, y ≥ 0

Paso 1: Convertir a ecuación con variable de holgura

x + 2y + s1 = 20
2x + 3y + s2 = 30
2x + y + s3 = 15

Paso 2: Configurar el tableau simplex

| x | y | s1 | s2 | s3 | Solución |
, 1 | 2 | 1 | 0 | 0 | 20 |
, 2 | 3 | 0 | 1 | 0 | 30 |
, 2 | 1 | 0 | 0 | 1 | 15 |
| -5|-4 | 0 | 0 | 0 | 0 |

Paso 3: Identificar el elemento pivote

El elemento con -5 es la columna pivote. Calculando la proporción para la tercera columna:

Proporción: (20/1) = 20, (30/2) = 15, (15/2) = 7.5

El valor positivo más pequeño es 7.5. El elemento en (Fila 3, Columna 1) será el pivote.

Paso 4: Realizar operaciones de fila

Hacer que el elemento pivote sea igual a 1:

| x | y | s1 | s2 | s3 | Solución |
, 1 | 2 | 1 | 0 | 0 | 20 |
| 1 | 1.5| 0 | 0.5| 0 | 7.5 | <- fila pivote (elemento pivote 1 creado)
, 2 | 1 | 0 | 0 | 1 | 15 |
| -5|-4 | 0 | 0 | 0 | 0 |

Ajustar las operaciones de fila para hacer los otros elementos de la columna cero y repetir el proceso hasta que no haya negativos en la fila inferior.

Paso 5: Solución óptima

A través de sucesivas iteraciones, finalmente:

| x | y | s1 | s2 | s3 | Solución |
, 1 | 0 | 1 | 1 | 0 | 5 |
| 0 | 1 | 0 | 1.5| 0 | 12.5 |
, 0 | 0 | -1 |-1.5| 1 | -7.5 |
| 0 | 0 | 0 |0.5 | 0 | 35 |

Los valores x = 5 y y = 12.5 maximizan la función objetivo Z hasta un valor de 35.

Conclusión

El método simplex es una herramienta de optimización poderosa para la programación lineal. Puede manejar múltiples variables de manera eficiente, guiando hacia un punto óptimo delimitado por restricciones. La naturaleza procedimental permite un análisis exhaustivo de escenarios prácticos donde los recursos son limitados, asegurando una utilización óptima.

Comentarios