Comprenent el Mètode de la Gran M en Programació Lineal (Exemple Pas a Pas)
Domina el mètode de la Gran M per a restriccions de >= i = en Programació Lineal. Aprèn la diferència entre variables d'holgura, excés i artificials amb un exemple resolt pas a pas.
Prova la Calculadora de Simplex i Anàlisi de Sensibilitat Pas a Pas
Introdueix la teva funció objectiu i restriccions per veure cada taula d'iteració, pivots i anàlisi de sensibilitat en temps real.
Per què necessitem el Mètode de la Gran M?
L'algorisme Simplex estàndard requereix una solució bàsica factible inicial (SBFI) per començar a iterar. Quan totes les restriccions són desigualtats del tipus ≤ amb termes independents no negatius, trobar aquesta base és immediat: sumar una variable d'holgura a cada restricció proporciona directament la base identitat a l'origen $(x_1=0, x_2=0, \dots)$.
Tanmateix, els models d'investigació operativa sovint presenten restriccions de major o igual (≥) o d'igualtat estricta (=). En aquests casos, l'origen no és factible. El Mètode de la Gran M resol aquesta dificultat introduint variables artificials fortament penalitzades per dirigir la nostra Calculadora del Mètode Simplex cap a l'òptim.
Diferència entre Variables d'Holgura, Excés i Artificials
- Variables d'Holgura ($s_i ≥ 0$): Se sumen a restriccions ≤ ($+s_i$). Representen recursos no consumits.
- Variables d'Excés ($e_i ≥ 0$): Es resten de restriccions ≥ ($-e_i$). Indiquen l'excedent per sobre del mínim. A l'origen, $-e_i = b_i ⇒ e_i = -b_i < 0$, violant la no-negativitat; per això no poden actuar com a base inicial.
- Variables Artificials ($a_i ≥ 0$): Se sumen ($+a_i$) a restriccions ≥ (juntament amb $-e_i$) i a restriccions =. No tenen cap significat físic ni econòmic; són recursos matemàtics temporals per construir la matriu identitat inicial.
La Penalització de la Gran M a la Funció Objectiu
Per garantir que les variables artificials siguin zero a la solució final, se'ls assigna un coeficient de penalització enorme $M$ ($M \gg 0$):
- En Maximització: Es resta $M \times a_i$: $\max Z = \sum c_j x_j - M \sum a_i$.
- En Minimització: Es suma $M \times a_i$: $\min Z = \sum c_j x_j + M \sum a_i$.
Exemple Numèric Resolt i Validat Pas a Pas
Resolem el següent problema lineal. Pots comprovar aquest mateix exercici pas a pas a la nostra Calculadora del Mètode Simplex:
Maximitzar Z = 3x₁ + 5x₂
Subjecte a:
x₁ + x₂ ≥ 2 (Restricció 1: Requeriment mínim)
2x₁ + 3x₂ ≤ 12 (Restricció 2: Disponibilitat de recurs)
x₁, x₂ ≥ 0
Pas 1: Forma Estàndard
- Restricció 1 (≥): $x_1 + x_2 - e_1 + a_1 = 2$
- Restricció 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}$.
Pas 2: Operació Prèvia de Fila en Z
L'equació objectiu penalitzada és $Z - 3x_1 - 5x_2 + M a_1 = 0$. Eliminem el coeficient d'$a_1$ restant $M \times (\text{Fila } 1)$:
Nova 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
Pas 3: Tableau Simplex Inicial (Iteració 0)
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | RHS | Raó Mínima |
|---|---|---|---|---|---|---|---|
| Z | -(3 + M) | -(5 + M) | M | 0 | 0 | -2M | — |
| a₁ | 1 | 1 | -1 | 0 | 1 | 2 | 2 / 1 = 2 (mín) ← Fila Pivote |
| s₂ | 2 | 3 | 0 | 1 | 0 | 12 | 12 / 3 = 4 |
Pas 4: Iteració 1
Entra $x_2$ (cost reduït més negatiu $-(5+M)$) i surt $a_1$ (raó mínima 2). El pivot és 1 a la fila $a_1$. Amb les operacions de fila de Gauss-Jordan, $a_1$ surt de la base i el terme $M$ es cancel·la del RHS:
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | RHS | Raó Mínima |
|---|---|---|---|---|---|---|---|
| Z | 2 | 0 | -5 | 0 | 5 + M | 10 | — |
| x₂ | 1 | 1 | -1 | 0 | 1 | 2 | -1 ≤ 0 (ignorat) |
| s₂ | -1 | 0 | 3 | 1 | -3 | 6 | 6 / 3 = 2 ← Fila Pivote |
Pas 5: Iteració 2 (Tableau Òptim Final)
Entra $e_1$ (coeficient $-5$) i surt $s_2$ (raó $6/3 = 2$). El pivot és 3 a 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ó de la Solució Òptima
Tots els costos reduïts a la fila Z són no negatius ($1/3 ≥ 0, 5/3 ≥ 0, M ≥ 0$). S'ha assolit la solució òptima:
- Variables de decisió: $x_1^* = 0$, $x_2^* = 4$.
- Excés i holgura: $e_1 = 2$ (la restricció 1 se supera en 2 unitats), $s_2 = 0$ (la restricció 2 és limitant/saturada).
- Valor objectiu màxim: $Z^* = 3(0) + 5(4) = 20$.
- Factibilitat: La variable artificial $a_1 = 0$, fora de la base.
Pots contrastar gràficament aquesta solució a la nostra Calculadora del Mètode Gràfic.
Detecció d'Infactibilitat
Si s'arriba a la condició d'aturada del Simplex però alguna variable artificial roman a la base amb valor estrictament positiu ($a_i > 0$), el problema és infactible (impossible).
Comparativa: Gran M vs Mètode de les Dues Fases
Mentre la Gran M és molt pedagògica, els solucionadors informàtics professionals prefereixen el Mètode de les Dues Fases per evitar problemes d'arrodoniment numèric amb la constant $M$.
Errors Típics d'Examen
- Oblidar l'operació prèvia a la fila Z abans de pivotar per cancel·lar el terme $M$.
- Confondre el signe de $M$ (és $-M$ en maximització i $+M$ en minimització).
- Dividir per nombres negatius o zero a la prova de la raó mínima.
- Consulta també la nostra guia sobre preus ombra en anàlisi de sensibilitat.
A punt per resoldre el teu propi problema de Programació Lineal?
Obtingues solucions pas a pas a l'instant amb taules d'iteració completes, anàlisi de sensibilitat i preus ombra.