← Tornar al Blog••10 min de lectura

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.

Calculadora Interactiva

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.

Obrir Calculadora Simplex →

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)

Basex₁x₂e₁s₂a₁RHSRaó Mínima
Z-(3 + M)-(5 + M)M00-2M—
a₁11-10122 / 1 = 2 (mín) ← Fila Pivote
s₂230101212 / 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:

Basex₁x₂e₁s₂a₁RHSRaó Mínima
Z20-505 + M10—
x₂11-1012-1 ≤ 0 (ignorat)
s₂-1031-366 / 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$:

Basex₁x₂e₁s₂a₁RHS
Z1/3005/3M20
x₂2/3101/304
e₁-1/3011/3-12

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

  1. Oblidar l'operació prèvia a la fila Z abans de pivotar per cancel·lar el terme $M$.
  2. Confondre el signe de $M$ (és $-M$ en maximització i $+M$ en minimització).
  3. Dividir per nombres negatius o zero a la prova de la raó mínima.
  4. 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.

Iniciar Calculadora Simplex