Comprenent el Mètode de la Gran M en Programació Lineal
Aprèn a gestionar restriccions de 'major o igual a' i 'igual a' utilitzant variables artificials i el mètode de penalització de la Gran M.
Per què necessitem el Mètode de la Gran M?
El mètode Simplex estàndard gestiona fàcilment restriccions de ≤ afegint variables de folgança. No obstant això, quan un problema de programació lineal conté restriccions de ≥ o =, trobar una solució bàsica factible inicial esdevé difícil. Aquí és on entra el mètode de la Gran M.
Introduint Variables Artificials
Per cada restricció de ≥, restem una variable d'excés i afegim una variable artificial. Per cada restricció de =, simplement afegim una variable artificial. Les variables artificiales no tenen cap significat físic; són purament eines matemàtiques per posar en marxa l'algorisme Simplex.
La Penalització de la Gran M
No podem permetre que les variables artificials formin part de la solució òptima final. Per forçar-les a sortir, els assignem una penalització massiva a la funció objectiu:
- Per a un problema de maximització, restem M × Ai (on M és un nombre molt gran).
- Per a un problema de minimització, sumem M × Ai.
Resolent amb la Gran M
El procés segueix aquests passos:
- Afegir variables d'excés i artificials per posar el problema en forma estàndard.
- Assignar la penalització de la Gran M a les variables artificials en la funció objectiu.
- Realitzar operacions de fila preliminars perquè les variables artificials formin una matriu identitat vàlida en el tableau inicial.
- Procedir amb les iteracions estàndard del Simplex.
Interpretant el Resultat
Si el tableau òptim final encara conté una variable artificial amb un valor diferent de zero, el problema original és inviable. Si totes les variables artificials han estat portades a zero, has trobat la veritable solució òptima.