Comprendiendo el Método de la Gran M en Programació Lineal
Aprende a manejar restricciones de 'mayor o igual a' e 'igual a' usando variables artificiales y el método de penalización de la Gran M.
¿Por qué necesitamos el Método de la Gran M?
El método Simplex estándar maneja fácilmente restricciones de ≤ añadiendo variables de holgura. Sin embargo, cuando un problema de programación lineal contiene restricciones de ≥ o =, encontrar una solución básica factible inicial se vuelve difícil. Aquí es donde entra el método de la Gran M.
Introduciendo Variables Artificiales
Por cada restricción de ≥, restamos una variable de exceso y añadimos una variable artificial. Por cada restricción de =, simplemente añadimos una variable artificial. Las variables artificiales no tienen significado físico; son puramente herramientas matemáticas para poner en marcha el algoritmo Simplex.
La Penalización de la Gran M
No podemos permitir que las variables artificiales formen parte de la solución óptima final. Para forzarlas a salir, les asignamos una penalización masiva en la función objetivo:
- Para un problema de maximización, restamos M × Ai (donde M es un número muy grande).
- Para un problema de minimización, sumamos M × Ai.
Resolviendo con la Gran M
El proceso sigue estos pasos:
- Añadir variables de exceso y artificiales para poner el problema en forma estándar.
- Asignar la penalización de la Gran M a las variables artificiales en la función objetivo.
- Realizar operaciones de fila preliminares para que las variables artificiales formen una matriz identidad válida en el tableau inicial.
- Proceder con las iteraciones estándar del Simplex.
Interpretando el Resultado
Si el tableau óptimo final todavía contiene una variable artificial con un valor distinto de cero, el problema original es inviable. Si todas las variables artificiales son llevadas a cero, has encontrado la verdadera solución óptima.