Comprendiendo el Método de la Gran M en Programación Lineal (Ejemplo Paso a Paso)
Domina el método de la Gran M para restricciones de >= e = en Programación Lineal. Aprende la diferencia entre variables de holgura, exceso y artificiales con un ejemplo resuelto paso a paso.
Prueba la Calculadora de Simplex y Análisis de Sensibilidad Paso a Paso
Introduce tu función objetivo y restricciones para ver cada tabla de iteración, pivotes y análisis de sensibilidad en tiempo real.
¿Por qué necesitamos el Método de la Gran M?
El algoritmo Simplex estándar requiere una solución básica factible inicial (SBFI) para comenzar a iterar. Cuando todas las restricciones son desigualdades del tipo ≤ con lados derechos no negativos, hallar dicha base es directo: sumar una variable de holgura no negativa a cada restricción genera inmediatamente una matriz identidad correspondiente al origen $(x_1=0, x_2=0, \dots)$.
Sin embargo, los problemas de optimización reales suelen incluir restricciones de mayor o igual (≥) o de igualdad estricta (=). En el origen, estas restricciones se violan, por lo que $(0,0)$ no es factible. El Método de la Gran M proporciona un mecanismo algebraico para construir una base artificial y dirigir nuestra Calculadora del Método Simplex hacia la solución óptima.
Diferencia entre Variables de Holgura, Exceso y Artificiales
- Variables de Holgura ($s_i ≥ 0$): Se suman a restricciones ≤ ($+s_i$). Representan capacidad de recurso no consumida.
- Variables de Exceso ($e_i ≥ 0$): Se restan de restricciones ≥ ($-e_i$). Indican el excedente sobre el requerimiento mínimo. En $x=0$, $-e_i = b_i ⇒ e_i = -b_i < 0$, violando la no negatividad; por ello no pueden ser variables básicas iniciales.
- Variables Artificiales ($a_i ≥ 0$): Se suman ($+a_i$) a restricciones ≥ (junto con $-e_i$) y a restricciones =. No tienen ningún significado físico o económico; actúan como catalizadores algebraicos para formar la base inicial.
La Penalización de la Gran M en la Función Objetivo
Dado que las variables artificiales no existen en el problema real, deben ser forzadas a cero en la solución óptima asignándoles una penalización masiva $M$ ($M \gg 0$):
- En Maximización: Restamos $M \times a_i$: $\max Z = \sum c_j x_j - M \sum a_i$.
- En Minimización: Sumamos $M \times a_i$: $\min Z = \sum c_j x_j + M \sum a_i$.
Ejemplo Numérico Resuelto y Validado Paso a Paso
Resolvamos el siguiente modelo. Puedes comprobar este mismo ejercicio en nuestra Calculadora del Método Simplex:
Maximizar Z = 3x₁ + 5x₂
Sujeto a:
x₁ + x₂ ≥ 2 (Restricción 1: Requerimiento mínimo)
2x₁ + 3x₂ ≤ 12 (Restricción 2: Disponibilidad de recurso)
x₁, x₂ ≥ 0
Paso 1: Conversión a Forma Estándar
- Restricción 1 (≥): $x_1 + x_2 - e_1 + a_1 = 2$
- Restricción 2 (≤): $2x_1 + 3x_2 + s_2 = 12$
- Variables: $x_1, x_2, e_1, s_2, a_1 ≥ 0$. Base inicial: ${a_1, s_2}$.
Paso 2: Operación Previa de Fila en Z
La función objetivo con penalización es $Z - 3x_1 - 5x_2 + M a_1 = 0$. Como $a_1$ está en la base, eliminamos su coeficiente en la fila Z restando $M \times (\text{Fila } 1)$:
Nueva Fila Z = [Z - 3x₁ - 5x₂ + M a₁] - M × [x₁ + x₂ - e₁ + a₁ = 2]
⇒ Z - (3 + M)x₁ - (5 + M)x₂ + M e₁ + 0s₂ + 0a₁ = -2M
Paso 3: Tableau Simplex Inicial (Iteración 0)
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | RHS | Razón Mínima |
|---|---|---|---|---|---|---|---|
| Z | -(3 + M) | -(5 + M) | M | 0 | 0 | -2M | — |
| a₁ | 1 | 1 | -1 | 0 | 1 | 2 | 2 / 1 = 2 (mín) ← Pivote |
| s₂ | 2 | 3 | 0 | 1 | 0 | 12 | 12 / 3 = 4 |
Paso 4: Iteración 1
Entra $x_2$ (costo más negativo $-(5+M)$) y sale $a_1$ (razón mínima 2). El elemento pivote es 1 en la fila $a_1$. Tras las operaciones de Gauss-Jordan, la variable artificial $a_1$ abandona la base y el término $M$ se cancela del RHS:
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | RHS | Razón Mínima |
|---|---|---|---|---|---|---|---|
| Z | 2 | 0 | -5 | 0 | 5 + M | 10 | — |
| x₂ | 1 | 1 | -1 | 0 | 1 | 2 | -1 ≤ 0 (ignorado) |
| s₂ | -1 | 0 | 3 | 1 | -3 | 6 | 6 / 3 = 2 ← Pivote |
Paso 5: Iteración 2 (Tableau Óptimo Final)
Entra $e_1$ (coeficiente $-5$) y sale $s_2$ (razón $6/3 = 2$). El elemento pivote es 3 en la fila $s_2$:
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | RHS |
|---|---|---|---|---|---|---|
| Z | 1/3 | 0 | 0 | 5/3 | M | 20 |
| x₂ | 2/3 | 1 | 0 | 1/3 | 0 | 4 |
| e₁ | -1/3 | 0 | 1 | 1/3 | -1 | 2 |
Interpretación de la Solución
Todos los costos reducidos en la fila Z son no negativos ($1/3 ≥ 0, 5/3 ≥ 0, M ≥ 0$). Se ha alcanzado la solución óptima:
- Variables de decisión: $x_1^* = 0$, $x_2^* = 4$.
- Variables de exceso y holgura: $e_1 = 2$ (la restricción 1 se supera en 2 unidades), $s_2 = 0$ (la restricción 2 está saturada).
- Valor objetivo óptimo: $Z^* = 3(0) + 5(4) = 20$.
- Factibilidad: La variable artificial $a_1$ salió de la base ($a_1 = 0$).
Puedes contrastar este resultado geométricamente en nuestra Calculadora del Método Gráfico.
Detección de Infactibilidad
Si se alcanza la condición de parada del Simplex pero alguna variable artificial permanece en la base con valor estrictamente positivo ($a_i > 0$), el problema original es infactible (incompatible).
Gran M frente al Método de Dos Fases
La Gran M resuelve el problema en una única fase pero puede presentar imprecisiones de coma flotante en computadoras. Por ello, en software profesional se suele preferir el Método de las Dos Fases.
Errores Típicos en Exámenes
- Olvidar la sustitución inicial en la fila Z para eliminar $M$ de las variables artificiales básicas.
- Equivocar el signo de $M$ (debe ser $-M$ en maximización y $+M$ en minimización).
- Dividir por números negativos o ceros en la prueba de la razón mínima.
- No interpretar los precios sombra; consulta nuestra guía sobre precios sombra en análisis de sensibilidad.
¿Listo para resolver tu propio problema de Programación Lineal?
Obtén soluciones paso a paso al instante con tablas de iteración completas, análisis de sensibilidad y precios sombra.