Swappa : Uni / Ricerca Operativa - PL - Pizze

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)
grad_ij (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:

x_i (quantità di pizza i=1..3 mangiata dall'amico 1)
y_i (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 grad_ij * x_i (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 grad_ij * y_i >= 0 (per j=2)

Caso (a):

vincolo che impone che ogni pizza sia mangiata per intero:
x_i + y_i = 1 (per ogni i)

Caso (b):

vincolo che impone che ogni pizza sia mangiata per intero:
x_i + y_i = 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 x_i = (somma)_i y_i
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