Metodo del simplesso

Appunto inviato da martibxb
/5

Appunto sul metodo del simplesso per fasi (7 pagine formato doc)

Metodo del simplesso

In inglese SIMPLEX è il generico nome per il poligono, o poliedro, o iperpoliedro che rappresentano geometricamente le soluzioni accettabili.
Il metodo del simplesso è un metodo algebrico, iterativo, che nel caso di non degenerazione raggiunge la soluzione ottima in un numero finito di passi(algoritmo).


1.
Fase 1 
La I fase del metodo del simplesso consiste nella ricerca di una soluzione basica accettabile iniziale;
prendendo in considerazione il sistema in forma canonica, è sufficiente porre a zero tutte le prime n-m variabili ed assegnare alle m variabili (slack, ecc.) restanti, i cui coefficienti tecnici formano una matrice unitaria, un valore uguale al corrispondente termine noto bi.
Questa soluzione iniziale in un problema di massimo è senz’altro la peggiore tra le soluzioni basiche accettabili, dato che con questa soluzione il valore della funzione obiettivo è zero.


2.
Fase 2 
La II fase consiste in un test di ottimalità, basato sul valutare se un qualche cambiamento della soluzione attuale (l’inserimento di una variabile esclusa dalla base e conseguente fuoriuscita di una che è presente) può incrementare o meno la F.O.
Definiamo variabile entrante in base quella che è posta a 0 nella situazione attuale, e che al passaggio successivo, nella fase 3, verrà immessa nella base, acquisendo un valore positivo; allo stesso modo la variabile uscente sarà quella che, attualmente in base e in generale con valore diverso da 0 (a parte il caso di degenerazione), nel passaggio successivo sarà posta a 0.