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.
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è 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.
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.