PREVIOUS: Forma Standard e Forma Canonica
UP: Il Metodo del Simplesso
NEXT: Convergenza del Simplesso: Casi Degeneri

Programmazione Lineare

Il Metodo del Simplesso

Primo Caso Soluzione Ottima Unica
Secondo Caso Infinite Soluzioni Ottime
Terzo Caso Funzione Obiettivo Non Limitata
Quarto Caso Area Amissibile Vuota

Considerazioni sulla Soluzione Ottima

Una volta trovata la soluzione ottima con il metodo del simplesso, bisogna essere sicuri che non ve ne siano di migliori; a tale scopo viene utilizzato lo spazio delle decisioni

grafico2.JPG (40477 bytes)

 

primo vincolo secondo vincolo funzione obiettivo
5x1 + 10x2 £ 60 4x1 + 4x2 £ 40 6x1 + 8x2 = Z
Posto x1 = 0  Þ  x2 = 6 Posto x1 = 0  Þ  x2 = 40 Posto x1 = 4 e x2 = 3 Þ Z = 24
Posto x2 = 0  Þ  x1 = 12 Posto x2 = 0  Þ  x1 = 10 e' uno dei possibili valori di Z

La parte buona per il primo vincolo e' quella che si trova sotto la retta blu; la parte buona per il secondo vincolo e' quella che si trova sotto la retta viola: l'intersezione delle due aree da' origine all'area ammissibile, cioe' a quella zona del grafico che contiene tutte le possibili soluzioni del problema (area tratteggiata in verde)

Spostando la retta Z all'interno della soluzione ammissibile, si fa variare l'intersezione tra la retta e l'area; le coordinate dei punti risultanti dall'intersezione, sono tutte le possibili coppie di valori (x1, x2), tali da ottenere lo stesso valore di Z (tutti i punti sulla retta Z hanno lo stesso valore); quindi, per avere una soluzione ottima unica, basta fare scorrere la funzione obiettivo lungo l'area ammissibile, finche' l'intersezione tra le due non e' ridotta ad un unico punto; questo e' quanto accade in (x1, x2) = (8, 2), che sono proprio i valori trovati per x1 e x2 con il metodo del simplesso

Da quanto detto si puo' osservare che:

si lavora nello spazio a due dimensioni Þ due variabili     ai1x1 + ai2x2 = bi
si hanno due vincoli: i vincoli sono dei semipiani e la soluzione ottima deve appartenere alla loro intersezione Þ la regione ammissibile e' un poligono
si hanno m vincoli: il poligono che determina la regione ammissibile non avra' piu' di m + 2 lati, m vincoli piu' i due assi 
si lavora nello spazio a tre dimensioni Þ tre variabili     ai1x1 + ai2x2 + ai3x3 = bi     identifica un piano
si ha un unico vincolo: la regione ammissibile e' uno dei due semipiani in cui il piano viene suddiviso
si hanno piu' vincoli: la regione ammissibile e' un poliedro non regolare, cioe' un solido limitato e finito
si lavora nello spazio a n dimensioni Þ n variabili     ai1x1 + ai2x2 + ... + ainxn £ bi     identifica un iperpiano
si ha un unico vincolo: la regione ammissibile e' un iperpiano
si hanno piu' vincoli: la regione ammissibile e' piu' un poliedro non regolare, questo perche' puo' accadere che non sia limitata; in questo caso si parla di politopi, cioe' di intersezioni di iperspazi che non e' detto siano limitate e finite

Si possono fare le seguenti considerazioni (si consideri di lavorare in due dimensioni):

  1. Primo caso: soluzione ottima unica

    la retta relativa alla funzione obiettivo va a cadere su un vertice della regione ammissibile Þ si ha un'unica soluzione che massimizza la funzione obiettivo; e' il caso che e' stato trattato in Ricerca della Soluzione Ottima

  2. Secondo caso: infinite soluzioni ottime

    la retta relativa alla funzione obiettivo si posa su due vertici della regione ammissibile Þ si hanno infinite soluzioni che massimizzano la Z: oltre ai due vertici, bisogna considerare anche tutte le soluzioni che si trovano sulla retta che li collega

  3. Terzo caso: funzione obiettivo non limitata

    il piano individuato dai vincoli non e' limitato e la funzione obiettivo si muove nella direzione della regione ammissibile non limitata Þ non esiste soluzione ottima che massimizzi la Z proprio perche' la funzione obiettivo non e' limitata

  4. Quarto caso: area ammissibile vuota

    i vincoli non creano nessuna intersezione, hanno cioe' intersezione vuota Þ la regione ammissibile e' vuota, quindi non possono esserci soluzioni ottime