Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - Esercizi di laboratorio ::
Esercizio 2: La fattoria
Indice
Una fattoria ha due lotti di terreno: A di 200 e B di 400 acri. Sei tipi di cereali numerati da 1 a 6 possono esservi coltivati. Per ogni quintale di cereale prodotto il profitto è dato dalla tabella seguente.
Cereale | 1 | 2 | 3 | 4 | 5 | 6 |
Profitto/quintale | 48 | 62 | 28 | 36 | 122 | 94 |
Ogni quintale di cereale necessita di una certa area (espressa in acri) e di una certa quantità di acqua (espressa in metri cubi) secondo questa tabella.
Cereale | 1 | 2 | 3 | 4 | 5 | 6 |
area su A | 0.02 | 0.03 | 0.02 | 0.016 | 0.05 | 0.04 |
area su B | 0.02 | 0.034 | 0.024 | 0.02 | 0.06 | 0.034 |
acqua | 120 | 160 | 100 | 140 | 215 | 180 |
Il volume totale di acqua disponibile è di 400mila metri cubi.
T = 2 | lotti di terreno | |
C = 6 | cereali | |
pi | profitto del cereale i (1, ... , C) per quintale | [€/q] |
arij | area necessaria per quintale di cereale i (1, ... , C) a seconda del tipo di terreno j (1, ... , T) | [acri] |
aci | quantità di acqua necessaria per quintale di cereale i (1, ... , C) | [m3] |
ltj | acri disponibili per terreno j (1, ... , T) | [acri] |
la | totale di acqua disponibile | [m3] |
xij ≥ 0 | quintali di cereali i (1, ... , C) da coltivare nel terreno j (1, ... , T) | [q] |
Notare il maggiore uguale a 0, condizione necessaria dato che non posso coltivare una quantità negativa di cereali.
∑i xij • arij ≤ ltj | per ogni j = 1, ... , T e con i = 1, ... , C | [acri] |
∑i xij • ∑j acij ≤ la | per ogni j = 1, ... , T e con i = 1, ... , C | [m3] |
Massimizzare il profitto, ovviamente.
max ∑i ∑j pi • xi | [€] |
Osservazioni da fare:
Le variabili sono variabili continue.
I vincoli sono espressi con un polinomio di primo grado, quindi il modello è lineare.
La funzione obiettivo è espressa con un polinomio di primo grado, quindi il modello è lineare.
Riassumendo: è un problema di programmazione lineare.
!Esercizio Fattoria !Variabili x(i)(j) = quintali di cerali da coltivare nel campo j [q] !Funzione obiettivo è massimizzare i guadagni [$/q] max 48 x11 + 48 x12 + 62 x21 + 62 x22 + 28 x31 + 28 x32 + 36 x41 + 36 x42 + 122 x51 + 122 x52 + 94 x61 + 94 x62 st !Vincoli sulle aree disponibili [acri] acri1) 0.02 x11 + 0.03 x21 + 0.02 x31 + 0.016 x41 + 0.05 x51 + 0.04 x61 <= 200 acri2) 0.02 x12 + 0.034 x22 + 0.024 x32 + 0.02 x42 + 0.06 x52 + 0.034 x62 <= 400 !Vincoli sull'acqua disponibile [metri cubi] acqua) 120 x11 + 120 x12 + 160 x21 + 160 x22 + 100 x31 + 100 x32 + 140 x41 + 140 x42 + 215 x51 + 215 x52 + 180 x61 + 180 x62 <= 400000 End |
Cliccando sul pulsante della risoluzione (il bersaglio) appare la seguente finestra di riepilogo:
Questo tipo di errore si manifesta quando si richiede la risoluzione di un problema in cui le variabili hanno valori molto grandi e molto piccoli (infatti in questo caso andiamo da 400000 a 0.016). Conviene dunque scalare il problema, magari cambiando l'unità di misura per l'acqua ed esprimendola in k metri cubi.
Avremo perciò:
!Esercizio Fattoria !Variabili x(i)(j) = quintali di cerali da coltivare nel campo j [q] !Funzione obiettivo è massimizzare i guadagni [$/q] max 48 x11 + 48 x12 + 62 x21 + 62 x22 + 28 x31 + 28 x32 + 36 x41 + 36 x42 + 122 x51 + 122 x52 + 94 x61 + 94 x62 st !Vincoli sulle aree disponibili [acri] acri1) 0.02 x11 + 0.03 x21 + 0.02 x31 + 0.016 x41 + 0.05 x51 + 0.04 x61 <= 200 acri2) 0.02 x12 + 0.034 x22 + 0.024 x32 + 0.02 x42 + 0.06 x52 + 0.034 x62 <= 400 !Vincoli sull'acqua disponibile [K metri cubi] acqua) 0.120 x11 + 0.120 x12 + 0.160 x21 + 0.160 x22 + 0.100 x31 + 0.100 x32 + 0.140 x41 + 0.140 x42 + 0.215 x51 + 0.215 x52 + 0.180 x61 + 0.180 x62 <= 400 end |
...che stavolta andrà a buon fine
LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1) 226976.7 VARIABLE VALUE REDUCED COST X11 0.000000 20.093021 X12 0.000000 20.093021 X21 0.000000 28.790693 X22 0.000000 28.790693 X31 0.000000 28.744186 X32 0.000000 28.744186 X41 0.000000 43.441860 X42 0.000000 43.441860 X51 0.000000 0.000000 X52 1860.465088 0.000000 X61 0.000000 8.139537 X62 0.000000 8.139537 ROW SLACK OR SURPLUS DUAL PRICES ACRI1) 200.000000 0.000000 ACRI2) 288.372101 0.000000 ACQUA) 0.000000 567.441833 NO. ITERATIONS= 1 |
Da cui osserviamo che il massimo del profitto è di 226976.7 € ottenuti coltivando esclusivamente sul terreno B col cereale 5, quello col miglior rapporto profitto/consumi. Notare che avrei avuto un risultato altrettanto ottimale se l'avessi coltivato sul campo A: la quantità di acri utilizzati non è una variabile stringente, dunque non influisce sulla soluzione. La variabile x51 ha infatti costo ridotto 0, quindi se entrasse in base varierebbe la soluzione ottima di 0, lasciandola di fatto inalterata.
Il vincolo stringente è quello sull’acqua, mentre le aree avanzano.
Ogni volta che facciamo calcolare la soluzione a Lindo, questi ci chiede attraverso la finestra di dialogo a sinistra se effettuare l'analisi di sensitività.
Finora abbiamo ignorato tale richiesta, ma stavolta clicchiamo su Yes.
In calce al consueto Report
verrà ora visualizzato un rapporto sulla sensitività della soluzione.
Nel nostro esempio avremo:
RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X11 48.000000 20.093018 INFINITY X12 48.000000 20.093018 INFINITY X21 62.000000 28.790691 INFINITY X22 62.000000 28.790691 INFINITY X31 28.000000 28.744184 INFINITY X32 28.000000 28.744184 INFINITY X41 36.000000 43.441856 INFINITY X42 36.000000 43.441856 INFINITY X51 122.000000 0.000000 INFINITY X52 122.000000 INFINITY 0.000000 X61 94.000000 8.139534 INFINITY X62 94.000000 8.139534 INFINITY RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE ACRI1 200.000000 INFINITY 200.000000 ACRI2 400.000000 INFINITY 288.372101 ACQUA 400.000000 1033.333374 400.000000 |
Le colonne allowable increase e allowable decrease indicano rispettivamente di quanto possono aumentare e diminuire i valori delle variabili senza che si esca dalla soluzione ottima. Nel nostro caso apprendiamo ad esempio che se il cereale 1 aumentasse il suo coefficiente di 20 allora diventerebbe anche lui ottimo e conveniente da coltivare; l'INFINITY nella colonna allowable decrease si spiega da sé: già così il valore non è ottimo, figuriamoci se lo diminuiamo! Consideriamo ora il cereale 5 nel campo 2, che può aumentare quanto si vuole di valore poiché è già ottimo e dunque può solo migliorare, ma non può diminuire assolutamente o uscirebbe dalla soluzione ottimale.
Dall'analisi viene ulteriormente evidenziato il fatto che le aree potrebbero aumentare di valore all’infinito senza variare la soluzione ottima: già ora non le sto usando tutte! Al contrario, possono diminuire massimo di 200 acri nel terreno A (tutto) e di 288.372101 nel B (la rimanenza).
Il vincolo sull’acqua è invece attivo dato che uso tutti i metri cubi disponibili. Quanta acqua potrei avere in più senza cambiare la base? Se superassimo i 1033.333374 metri cubi l’acqua non sarebbe più la risorsa scarsa, ma diventerebbe qualcun’altra (si arriverebbe al punto in cui avremo acqua in abbondanza ma scarsità di terreno da coltivare, che diventerebbe il nuovo vincolo attivo).
L’analisi di sensitività ci dice cosa accade al valore ottimo del problema solo all’interno dell’intervallo in cui può stare il termine noto del vincolo attivo (l’acqua). Per capire cosa succede al di fuori bisogna fare l’analisi parametrica.
Bisogna andare nel menù "Reports" e selezionare il comando "Parametrics...", che farà apparire questa finestra:
Osserviamo che:
<=
Diamo l'OK.
Prima di osservare il grafico notiamo che sono state aggiunte nuove informazioni al Report
:
RIGHTHANDSIDE PARAMETRICS REPORT FOR ROW: ACQUA VAR VAR PIVOT RHS DUAL PRICE OBJ OUT IN ROW VAL BEFORE PIVOT VAL 400.000 567.442 226977. SLK 3 X51 3 1433.33 567.442 813333. SLK 2 X62 2 2293.33 567.442 0.130133E+07 X52 SLK 4 4 2977.65 427.507 0.159388E+07 0.100000E+07 0.000000E+00 0.159388E+07 |
Le colonne indicano rispettivamente le variabili uscite di base (VAR OUT) ed entrate in base (VAR IN) per ognuno dei punti di cambio di discontinuità, stessa cosa per il PIVOT ROW, il valore del termine noto (RHS VAL), il prezzo duale di cui parleremo alla fine (DUAL PRICE BEFORE PIVOT) e la soluzione ottima (OBJ VAL).
In questa tabella sono contenute le informazioni per tracciare il grafico seguente (il valore 1000000 stara un po' la percezione della forma reale della curva.. si capirà meglio il suo andamento nelle considerazioni che faremo poi):
Il grafico parte dal punto con ascissa (RHS VAL) 400 e ordinata (OBJ VAL) 226977.
Quando arriva ad ascissa 1433.33 e ordinata 813333 avremo un primo cambio di base, e ci viene segnalato che diventa attiva la variabile slack 3. Ricordiamo brevemente l'ordine delle variabili: funzione obiettivo (1), area A (2), area B (3), acqua (4). Quindi questo cambio di base è caratterizzato dal fatto che siamo riusciti a riempire di cereali tutto il campo B.
Situazione prima del primo cambio di base:
Situazione dopo il primo cambio di base:
Quando arriviamo ad ascissa 2293,33 e ordinata 1301330 avremo un altro cambio di base, in cui diventa attiva la variabile slack 2. Ciò significa che siamo riusciti a riempire di cerali anche tutto il campo A.
Situazione prima del secondo cambio di base:
Situazione dopo il primo cambio di base:
In pratica abbiamo iniziato a coltivare il cereale 6 sul terreno B.
Situazione prima del terzo cambio di base:
Situazione dopo il primo cambio di base:
Il che significa che stiamo coltivando tutto il campo A col cereale 1 e tutto il campo B col cereale 6. L'acqua è diventata ora un vincolo strettamente positivo, ridondante, dunque non più attivo. Fino a quest’ultimo cambio di base era lei l'elemento vincolante, ovvero decideva lei cosa era realmente conveniente coltivare e cosa no; da ora non più.
Infine, breve considerazione sul prezzo duale. Il prezzo duale indica di quanto aumenta la funzione obiettivo a seconda del termine noto; da un punto di vista grafico corrisponde al coefficiente angolare, ed infatti l’ultimo segmento della nostra curva ha coefficiente 0, parallela all’asse.
Dall’analisi di sensitività sapevamo che l’acqua rimaneva una variabile scarsa da 400 a 1033.33, ora sappiamo cosa succede anche dopo.