Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - Esercizi di laboratorio ::
Esercizio 2: La fattoria
Problema
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.
Formalizzazione
Dati
| 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]
|
Variabili
| 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.
Vincoli
| ∑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]
|
Funzione obiettivo
Massimizzare il profitto, ovviamente.
Classificazione del problema
Osservazioni da fare:
- le variabili sono continue o no?
- i vincoli sono lineari o no?
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.
Risoluzione in Lindo
!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
Report
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.
Analisi di sensitività
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).
Analisi parametrica
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:
* la risorsa scarsa da selezionare è l'Acqua
* il vincolo è di tipo <=
* il termine noto della disuguaglianza è attualmente 400, ma possiamo (e dobbiamo) cambiarlo per effettuare l’analisi. Ad esempio diamo nuovo valore 1000000
* la checkbox "Text" fornirà un output testuale, dunque è meglio checkarla
* c'è un segno di spunta anche sull'opzione "Graphics", bisognerà scegliere se lo vogliamo in 2d o in 3d
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:
- variabili in base: x52, slack 2, slack 3 (tutte strettamente positive)
- vincoli attivi: acqua
Situazione dopo il primo cambio di base:
- variabili in base: x52, x51, slack 2
- vincoli attivi: acqua, area B
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:
- variabili in base: x52, x51, slack 2 (tutte strettamente positive)
- vincoli attivi: acqua, area B
Situazione dopo il primo cambio di base:
- variabili in base: x52, x51, x62
- vincoli attivi: acqua, area B, area A
In pratica abbiamo iniziato a coltivare il cereale 6 sul terreno B.
Situazione prima del terzo cambio di base:
- variabili in base: x52, x51, x62 (tutte strettamente positive)
- vincoli attivi: acqua, area B, area A
Situazione dopo il primo cambio di base:
- variabili in base: slack 4, x51, x62
- vincoli attivi: area B, area A
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.
Torna alla pagina di Ricerca Operativa
