El Mètode de les Dues Fases en Programació Lineal (Guia pas a pas)
Aprèn a resoldre problemes de programació lineal amb variables artificials utilitzant el Mètode Simplex de les Dues Fases, una alternativa robusta al mètode de la Gran M.
Per Què Existeix el Mètode de les Dues Fases
L'algorisme Simplex estàndard requereix una solució bàsica factible inicial (SBF) per començar a iterar. Per a problemes que contenen únicament restriccions ≤, això és trivial: afegir una variable de folgança a cada restricció proporciona immediatament una base identitat. Tanmateix, quan un model inclou restriccions de ≥ o =, l'origen no és factible i no existeix una base inicial òbvia. El Mètode de les Dues Fases resol això amb major estabilitat numèrica que el mètode de la Gran M.
Configuració del Problema: Forma Estàndard
Considera el següent programa lineal (PL):
Maximitzar Z = 2x&sub1; + 3x&sub2;
Subjecte a:
x&sub1; + x&sub2; ≤ 4 (restricció 1)
x&sub1; + 2x&sub2; ≥ 6 (restricció 2)
x&sub1;, x&sub2; ≥ 0
Per convertir-lo a forma estàndard:
- Restricció 1 (≤): afegir variable de folgança s&sub1; → x&sub1; + x&sub2; + s&sub1; = 4
- Restricció 2 (≥): restar variable d'excés s&sub2; i afegir variable artificial a&sub1; → x&sub1; + 2x&sub2; − s&sub2; + a&sub1; = 6
Fase I: Trobar una Solució Bàsica Factible Inicial
Construïm la funció objectiu auxiliar: Minimitzar W = a&sub1;
Si podem portar W a zero, haurem eliminat totes les variables artificials de la base.
Pas 1 — Construir el Tableau de Fase I
Actualitzem la fila W amb una operació de fila preliminar per posar a zero el coeficient de a&sub1;:
Fila-W = Fila-W − (restricció 2)
⇒ W + x&sub1; + 2x&sub2; − s&sub2; = 6
| VB | x&sub1; | x&sub2; | s&sub1; | s&sub2; | a&sub1; | CD |
|---|---|---|---|---|---|---|
| W | 1 | 2 | 0 | −1 | 0 | 6 |
| s&sub1; | 1 | 1 | 1 | 0 | 0 | 4 |
| a&sub1; | 1 | 2 | 0 | −1 | 1 | 6 |
Pas 2 — Iteració 1
- Variable d'entrada: x&sub2; (coeficient 2 a fila W).
- Prova de raó mínima: Fila s&sub1;: 4/1 = 4; Fila a&sub1;: 6/2 = 3 ← mínim. Surt a&sub1;.
- Pivot: Dividir fila pivot entre 2, eliminar x&sub2; de les altres files.
| VB | x&sub1; | x&sub2; | s&sub1; | s&sub2; | a&sub1; | CD |
|---|---|---|---|---|---|---|
| W | 0 | 0 | 0 | 0 | −1 | 0 |
| s&sub1; | 1/2 | 0 | 1 | 1/2 | −1/2 | 1 |
| x&sub2; | 1/2 | 1 | 0 | −1/2 | 1/2 | 3 |
W = 0. Fase I completada. SBF: x&sub1; = 0, x&sub2; = 3, s&sub1; = 1, s&sub2; = 0.
Fase II: Optimitzant l'Objectiu Original
Eliminem la columna a&sub1; i reemplacem la fila W amb la fila Z original, reexpressada en termes de variables no bàsiques actuals.
Pas 3 — Tableau de Fase II inicial
| VB | x&sub1; | x&sub2; | s&sub1; | s&sub2; | CD |
|---|---|---|---|---|---|
| Z | −1/2 | 0 | 0 | −3/2 | −9 |
| s&sub1; | 1/2 | 0 | 1 | 1/2 | 1 |
| x&sub2; | 1/2 | 1 | 0 | −1/2 | 3 |
Pas 4 — Iteració 2
- Variable d'entrada: s&sub2; (coeficient −3/2 a fila Z).
- Prova de raó mínima: Fila s&sub1;: 1 ÷ (1/2) = 2. Surt s&sub1;.
Tableau final òptim:
| VB | x&sub1; | x&sub2; | s&sub1; | s&sub2; | CD |
|---|---|---|---|---|---|
| Z | 2 | 0 | 3 | 0 | −12 |
| s&sub2; | 1 | 0 | 2 | 1 | 2 |
| x&sub2; | 1 | 1 | 1 | 0 | 4 |
Tots els coeficients Z són no negatius → solució òptima: x&sub1; = 0, x&sub2; = 4, Z = 12.
Si la Fase I Acaba amb W > 0
Si el valor mínim de W és estrictament major que zero, almenys una variable artificial roman a la base amb valor positiu. Això significa que el problema original és infactible. No té sentit continuar a la Fase II.
Dues Fases vs. Gran M: Comparativa
| Propietat | Mètode Dues Fases | Mètode Gran M |
|---|---|---|
| Estabilitat numèrica | Alta (sense constants grans) | Menor (M pot causar pèrdua de precisió) |
| Facilitat de configuració | Moderada (dos PLs separats) | Simple (un sol PL) |
| Detecció d'infactibilitat | W > 0 al final de Fase I | Variable artificial a la base final |
| Preferència en programari | Preferit per la majoria de solucionadors | Comú en exemples manuals de llibres de text |
Conclusió
El Mètode de les Dues Fases és l'estàndard per gestionar restriccions de ≥ i = en programació lineal. En separar clarament la detecció de factibilitat (Fase I) de l'optimització real (Fase II), evita els problemes numèrics d'una penalització gran arbitrària i proporciona un senyal clar quan un problema no té solució factible.