Quando il vettore x delle variabili di decisione ha solo due componenti il problema di programmazione lineare pu`o essere facilmente risolto per via grafica. Gli esempi che seguono, analizzati graficamente, illustrano le situazioni tipiche che si presentano nella soluzione di problemi di programmazione lineare.
Ricordiamo preliminarmente che nel piano cartesiano con assi coordinati (x1, x2) l’equazione ax1+ bx2= c
individua una retta. Tale retta al crescere di c si muove parallelamente a se stessa nella direzione individuata dal vettore [a b]T; e di conseguenza la disequazione
10x1 + 5x2 †25 10x 1 + 5x2 ‡25 5 4 3 2 1 10x + 5x =25 1 2 3 4 5 6 x 1 x 2
Figura 2.1:
Retta e semipiani individuati da un’equazione lineare.individua il semipiano posto rispetto alla retta ax1+ bx2= c dalla parte verso cui `e orientato il vettore [a b]T. Ad esempio, nella figura 2.1 sono rappresentati la retta 10x1+ 5x2 = 25, il vettore [10 5]T, e, punteggiato, il semipiano in cui risulta 10x1+ 5x2 ≥ 25. Consideriamo ora un esempio di problema di programmazione lineare con due variabili di decisione:
max 5x1+ 10x2
1) 10x1+ 5x2 ≤ 25 2) 4x1+ 10x2 ≤ 20 3) x1+ 1.5x2 ≤ 4.5
x ≥ 0.
I vincoli 1), 2) e 3) individuano i semipiani punteggiati rispettivamente nelle figure 2.2, 2.3 e 2.4.
x1 x2
5
2.5
10x + 5x † 25 1 2
x1 x2
4x 1 + 10x 2 † 20
5 2
Figura 2.3:
Regione individuata dal vincolo 2).I tre vincoli insieme, e quelli di non negativit`a delle variabili x1e x2, individuano la regione del piano (x1, x2) punteggiata in figura 2.5, in cui nessun vincolo `e violato; tale regione `e detta regione ammissibile. Notiamo, per inciso, che ai fini della determinazione della regione ammissibile, il terzo vincolo `e superfluo. La retta 5x1+ 10x2= z `e rappresentata in figura 2.6 per z = 10, z = 20 e z = 30. Sovrapponendo le figure 2.5 e 2.6 si constata che al crescere di z le rette corrispondenti alla funzione obiettivo, dette anche linee di livello, intersecano la regione ammissibile finch`e risulta z ≤ 21.875; non esistono invece punti della regione ammissibile in cui la funzione obiettivo assume un valore maggiore di 21.875. Questo valore `e quindi il massimo che la funzione obiettivo pu`o assumere compatibilmente con il soddisfacimento dei vincoli. Il massimo vincolato della funzione obiettivo `e assunto nel punto (x1 = 1.875, x2 = 1.25), come mostrato nella figura 2.7. In alcuni casi la soluzione del problema pu`o non essere unica, nel senso che vi possono essere pi`u punti del piano (x1, x2) che forniscono lo stesso valore massimo della funzione obiettivo. Ad esempio, se con i vincoli del caso precedente la funzione obiettivo, anzich`e quella data, fosse la z = 4x1+ 10x2, le rette corrispondenti all’equazione 4x1+ 10x2 = z, al variare di z, sarebbero parallele al segmento del perimetro della regione ammissibile determinato dal secondo vincolo, e quindi ogni punto di questo segmento fornirebbe una soluzione non unica del problema. La figura 2.8 illustra questo caso. Nei due esempi precedenti la soluzione del problema esiste, anche se nel secondo caso non `e unica. In altri problemi di programmazione lineare la soluzione pu`o non esistere. Un primo caso in cui si verifica questa circostanza `e quando la regione ammissibile risulta vuota. Ci`o avviene, ad esempio, se si cambia il verso della disuguaglianza del vincolo 3). Come evidenziato nella figura 2.9, in tal caso nessun punto del piano in cui risulta x1+ 1.5x2 ≥ 4.5 (zona tratteggiata) appartiene alla regione individuata dagli altri vincoli, e quindi nessun punto del piano soddisfa tutti i vincoli del problema.
In tal caso il problema non ha soluzione, indipendentemente dalla funzione obiettivo. Un altro caso in cui il problema di programmazione lineare pu`o non avere soluzione `e quando la regione ammissibile risulta illimitata. Se nell’esempio inizialmente considerato eliminiamo il vincolo di non negativit`a della variabile x1, la regione ammissibile diviene quella, illimitata, punteggiata in figura 2.10; in questo caso la soluzione del problema rimane invariata.
Se per`o richiediamo che la funzione obiettivo sia minimizzata anzich´e massimizzata, la stessa figura 2.10 evidenzia il fatto che nella regione ammissibile la funzione obiettivo pu`o assumere valori arbitrari-amente grandi in valore assoluto e negativi in segno. In altre parole, `e sempre possibile trovare nella
x
2
x + 1.5x † 4.51 2 3
4.5 x1
Figura 2.4:
Regione individuata dal vincolo 3).regione ammissibile un punto in cui la funzione obiettivo assume un valore pi`u basso di qualsiasi valore dato, e quindi il problema non ha soluzione.
Riassumendo, l’analisi grafica suggerisce che, per un problema di PL, si possono presentare i seguenti casi:
1. la regione ammissibile `e vuota: il problema non ha soluzione;
2. la regione ammissibile `e illimitata e la funzione obiettivo `e illimitata superiormente (se il problema `e di massimizzazione) o inferiormente (se il problema `e di minimizzazione): il problema non ha soluzione;
3. il problema ha soluzione ottima: • unica;
• non unica (e sono infinite).
Con riferimento al punto (2) notiamo che se la regione ammissibile `e illimitata non necessariamente il problema non ha soluzione (funzione obiettivo illimitata). Osserviamo infine che sembra lecito affermare, sempre in base agli esempi visti, che:
1. se la regione ammissibile `e non vuota, essa risulta essere un insieme convesso;
2. se il problema ha soluzioni, almeno una di esse si trova in un vertice del poligono convesso costituito dalla regione ammissibile.
Tutte queste osservazioni sono in effetti sostanzialmente corrette. Nel prossimo paragrafo discuteremo questo tipo di argomenti nel caso di problemi di PL con un numero qualunque di variabili, dando le definizioni e precisazioni necessarie.
Esempio 2.3.1 Risolviamo graficamente il problema di miscelazione descritto nel paragrafo 2.2.2. La regione ammissibile del problema `e rappresentata punteggiata in figura 2.11; nella stessa figura sono rappresentate le linee di livello corrispondenti ai valori della funzione obiettivo z pari a 420 e a 630, oltre a quella corrispondente al valore ottimo. La soluzione si trova nel punto x1= 58.33, x2= 41.66 ove
per la funzione obiettivo si ha il valore minimo vincolato z = 495.83. 2
Esempio 2.3.2 Risolviamo graficamente il problema di produzione descritto nel paragrafo 2.2.1. La regione ammissibile del problema `e rappresentata punteggiata in figura 2.12; nella stessa figura sono
5 3 2 2.5 4.5 5 x1 x 2
Figura 2.5:
Regione ammissibile del problema.x1 x2 2 4 6 5x + 10x 1 2 z =
Figura 2.6:
Linee di livello della funzione obiettivo.rappresentate le linee di livello corrispondenti ai valori della funzione obiettivo z pari a 600000 e a 2400000, oltre a quella corrispondente al valore ottimo. La soluzione si trova nel punto x1 = 200, x2 = 800, ove per la funzione obiettivo si ha il valore massimo vincolato z = 1440000. 2
Esercizio 2.3.3 Risolvi il problema di programmazione lineare determinato dalla funzione obiettivo da massimizzare z = x1+ 0.5x2 e dalla regione ammissibile punteggiata in figura 2.13.
x1 x2 1 2 3 2 6 z = 30 z = 10 z = 21.875
.
(1.875 , 1.25) 4Figura 2.7:
Soluzione grafica del problema.x1 x2 2 3.2 2 z = 10 0.8 z = 25 z = 40 5 8
Figura 2.8:
Caso di soluzione non unica.x2 5 3 2 2.5 4.5 x1 5
x 2 x1 1 2 3 -2 4 5x + 10x = z 1 2 z = 0 z = -20 z = 10 -4 2 -1 -2 z = -10
Figura 2.10:
Regione ammissibile illimitata.141.66 78.125 70 82,63. 100 105 125 120 100 180 z = 495.83 (58.33 , 41.66) z = 420 z = 630 x1 x2
1000 900 500 1000 1200 1800 2500 z = 1440000 900 400 (200, 800) z = 2400000 x2 x1 2000
Figura 2.12:
Soluzione grafica del problema di produzione.(0 , 10) (0 , 7) (5 , 0) ( 3 , 10 ) ( 7 ,9 ) x 2 (12 , 4) (10 , 0) z = 6 z = 10 1 x