Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PL - Pizze - 6.02.07 ::
Testo del problema
Per festeggiare il superamento dell’esame di Ricerca Operativa, due amici escono in pizzeria e, affamatissimi per l’immane sforzo compiuto, ordinano tre pizze diverse. Ognuno dei due attribuisce diversi valori di gradimento percentuale alle tre pizze; i valori sono riportati nel file PIZZE.TXT. I due amici vorrebbero dividersi le pizze in modo che ciascuno sia il più contento possibile e, riconoscendo la conflittualità dei loro obiettivi, decidono ovviamente di formulare il problema e risolverlo in modo scientifico.
Considerare separatamente i due casi: (a) senza vincoli sulla quantità di pizza mangiata da ciascuno; (b) con il vincolo che ciascuno mangi l’equivalente di una pizza e mezzo.
Trovare la soluzione ottima con le seguenti funzioni obiettivo:
- massimizzare il grado di contentezza del più scontento
- massimizzare il grado di contentezza del più contento
- massimizzare il grado di contentezza totale
Dati
Le pizze sono tre: ai formaggi, ai salumi, alle verdure.
========================================================
Tabella 1: Percentuale di gradimento
Amico Formaggi Salumi Verdure
1 0.3 0.5 0.2
2 0.7 0.2 0.1
Formulazione del problema
Dati
- amici = 2 (numero di amici)
- pizze = 3 (numero di pizze)
- gradij (percentuale gradimento della pizza i=1..3 per l'amico j=1..2) [%]
Variabili
Conviene separare in due variabili distinte le quantità di pizze mangiate dai due amici. Quindi:
- xi (quantità di pizza i=1..3 mangiata dall'amico 1)
- yi (quantità di pizza i=1..3 mangiata dall'amico 2)
Le variabili sono continue e non negative.
Funzione obiettivo
Nel problema non ci viene chiesto di massimizzare il gradimento di uno solo dei due amici, ma di entrambi. Dovremmo quindi avere due funzioni obiettivo per ciascuno di essi da considerare contemporaneamente, ma dal momento che ciò non è realizzabile trasformeremo una delle due in un vincolo (che definiremo poi).
Come funzione obiettivo manterremo:
max (somma)i gradij * xi (per j=1)
Per poter rispondere alle richieste del testo (massimizzare il grado di contentezza del più scontento, massimizzare il grado di contentezza del più contento, massimizzare il grado di contentezza totale) ricorreremo in un secondo momento con l'analisi parametrica.
Vincoli
- come prima cosa definiamo il vincolo che rappresenta la funzione obiettivo che riguarda il secondo amico:
(somma)i gradij * yi >= 0 (per j=2)
Caso (a):
- vincolo che impone che ogni pizza sia mangiata per intero:
xi + yi = 1 (per ogni i)
Caso (b):
- vincolo che impone che ogni pizza sia mangiata per intero:
xi + yi = 1 (per ogni i)
- vincolo che impone che ogni amico mangi la stessa quantità di pizza. Notare che non va bene un'espressione con questa forma:
(somma)i xi = (somma)i yi
perché sappiamo che Lindo vuole
Lindizzazione del problema
Caso (a)
! esercizio - Pizze
! variabili: x(i) = quantità di pizza i mangiata dall'amico 1
! y(i) = quantità di pizza i mangiata dall'amico 2
! le variabili sono continue e non negative
! funzione obiettivo (riguardante l'amico 1)
max 0.3 x1 + 0.5 x2 + 0.2 x3
st
! vincolo che trasforma la funzione obiettivo riguardante l'amico 2
vinFO2) 0.7 y1 + 0.2 y2 + 0.1 y3 >= 0
! caso (a): vincolo che impone di mangiare la pizza per intero
pizza1) x1 + y1 = 1
pizza2) x2 + y2 = 1
pizza3) x3 + y3 = 1
end
Caso (b):
! esercizio - Pizze
! variabili: x(i) = quantità di pizza i mangiata dall'amico 1
! y(i) = quantità di pizza i mangiata dall'amico 2
! le variabili sono continue e non negative
! funzione obiettivo (riguardante l'amico 1)
max 0.3 x1 + 0.5 x2 + 0.2 x3
st
! vincolo che trasforma la funzione obiettivo riguardante l'amico 2
vinFO2) 0.7 y1 + 0.2 y2 + 0.1 y3 >= 0
! caso (b): vincolo che impone di mangiare la pizza per intero
pizza1) x1 + y1 = 1
pizza2) x2 + y2 = 1
pizza3) x3 + y3 = 1
! caso (b): vincolo che impone che gli amici mangino la stessa quantità di pizza
ugPizza) x1 + x2 + x3 - y1 - y2 - y3 = 0
end
Le tre funzioni obiettivo richieste nel testo
Caso (a)
Riportiamo il report della soluzione del caso (a):
LP OPTIMUM FOUND AT STEP 0
OBJECTIVE FUNCTION VALUE
1) 1.000000
VARIABLE VALUE REDUCED COST
X1 1.000000 0.000000
X2 1.000000 0.000000
X3 1.000000 0.000000
Y1 0.000000 0.300000
Y2 0.000000 0.500000
Y3 0.000000 0.200000
ROW SLACK OR SURPLUS DUAL PRICES
VINFO2) 0.000000 0.000000
PIZZA1) 0.000000 0.300000
PIZZA2) 0.000000 0.500000
PIZZA3) 0.000000 0.200000
NO. ITERATIONS= 0
Facciamo ora l'analisi parametrica sul vincolo che rappresenta la seconda funzione obiettivo, fissando il nuovo valore a 1:
RIGHTHANDSIDE PARAMETRICS REPORT FOR ROW: VINFO2
VAR VAR PIVOT RHS DUAL PRICE OBJ
OUT IN ROW VAL BEFORE PIVOT VAL
0.000000E+00 0.000000E+00 1.00000
SLK 2 Y1 2 0.000000E+00 0.000000E+00 1.00000
X1 Y3 3 0.700000 -0.428571 0.700000
X3 Y2 5 0.800000 -2.00000 0.500000
1.00000 -2.50000 0.372529E-07
Rispondiamo ora alle richieste del testo:
- massimizzare il grado di contentezza del più contento: evidentemente è la situazione in cui uno dei due amici mangia tutto e l'altro non mangia niente. Infatti quando uno dei due amici ha soddisfazione complessiva 1, l'altro ha 0
- massimizzare il grado di contentezza del più scontento: dobbiamo confrontare nei risultati dell'analisi parametrica la colonna del valore attuale del vincolo sulla seconda funzione obiettivo ("RHS VAL") e il valore ottimo corrispondente del problema ("OBJ VAL"). In questo modo osserviamo che l'OBJ VAL che massimizza l'RHS VAL (ricordando sempre che il primo deve essere maggiore del secondo) è quello in cui il primo e il secondo amico hanno grado di contentezza pari a 0.7
- massimizzare il grado di contentezza totale: evidentemente è lo stesso risultato del punto precedente, ovvero quello in cui entrambi hanno grado di contentezza pari a 0.7
Caso (b)
Riportiamo il report della soluzione del caso (b):
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 0.6500000
VARIABLE VALUE REDUCED COST
X1 0.500000 0.000000
X2 1.000000 0.000000
X3 0.000000 0.100000
Y1 0.500000 0.000000
Y2 0.000000 0.200000
Y3 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
VINFO2) 0.450000 0.000000
PIZZA1) 0.000000 0.150000
PIZZA2) 0.000000 0.350000
PIZZA3) 0.000000 0.150000
UGPIZZA) 0.000000 0.150000
NO. ITERATIONS= 2
Facciamo ora l'analisi parametrica sul vincolo che rappresenta la seconda funzione obiettivo, fissando il nuovo valore a 1:
RIGHTHANDSIDE PARAMETRICS REPORT FOR ROW: VINFO2
VAR VAR PIVOT RHS DUAL PRICE OBJ
OUT IN ROW VAL BEFORE PIVOT VAL
0.000000E+00 0.000000E+00 0.650000
SLK 2 X3 2 0.450000 0.000000E+00 0.650000
X1 Y2 3 0.750000 -0.166667 0.600000
Y3 ART 5 0.800000 -3.00000 0.450000
1.00000 -INFINITY INFEASIBLE
Rispondiamo ora alle richieste del testo:
- massimizzare il grado di contentezza del più contento: in questo caso la soluzione ottima si trova nel punto (0.65 , 0.45)
- massimizzare il grado di contentezza del più scontento: per lo stesso ragionamento fatto nel caso (a), la soluzione ottima si trova nel punto (0.65 , 0.45)
- massimizzare il grado di contentezza totale: ??
Torna alla pagina di Ricerca Operativa
