Com Resoldre el Mètode Simplex Pas a Pas (Amb Exemples)
Domina el mètode Simplex per a programació lineal. Aprèn a configurar el tableau inicial, escollir variables pivot i iterar cap a la solució òptima.
Introducció al Mètode Simplex
El mètode Simplex és un procediment sistemàtic per resoldre problemes de programació lineal. Desenvolupat per George Dantzig el 1947, continua sent un dels algorismes més utilitzats per a l'optimització.
Pas 1: Forma Estàndard
Abans d'aplicar el mètode Simplex, has de convertir el problema de programació lineal a la seva forma estàndard. Això implica:
- Assegurar-se que l'objectiu sigui un problema de maximització.
- Convertir totes les desigualtats en igualtats introduint variables de folgança (per a ≤) o variables d'excés (per a ≥).
- Assegurar-se que totes les variables siguin no negatives.
Pas 2: El Tableau Inicial
Un cop en forma estàndard, construeix el tableau Simplex inicial. Aquesta matriu representa el sistema d'equacions. La fila inferior sol representar la funció objectiu (fila Z).
Pas 3: Escollir l'Element Pivot
La iteració és el nucli del mètode Simplex:
- Variable d'Entrada: Selecciona el valor més negatiu a la fila de la funció objectiu. Això identifica la columna pivot.
- Variable de Sortida: Realitza la prova de la raó mínima (divideix el costat dret RHS pels valors positius de la columna pivot). La raó no negativa més petita determina la fila pivot.
- La intersecció és el teu element pivot.
Pas 4: Operacions de Fila
Utilitza operacions elementals de fila per fer que l'element pivot sigui 1 i tots els altres elements de la columna pivot siguin 0. Això et donarà el tableau de la següent iteració.
Conclusió
Repeteix els passos 3 i 4 fins que no hi hagi valors negatius a la fila de la funció objectiu. En aquest punt, hauràs assolit la solució òptima!