:: RO - Inviti a cena ::
Testo
Il ricercatore operativo, stanco di studiare per l'esame, vuole concedersi alcuni giorni di allegria e pianifica di invitare a cena alcune sue amiche (una per sera, naturalmente). Alcune tra le ragazze si conoscono tra loro e se una fosse invitata ciò sarebbe risaputo dalle sue amiche. Onde evitare spiacevoli scene di gelosia, il piano degli inviti a cena deve essere perciò congegnato in modo che nessuna delle invitate sia amica di un'altra invitata. Il giovanotto attribuisce un indice di gradimento ad ogni ragazza, pari al piacere di passare la serata con lei, e desidera naturalmente che gli inviti siano tali da massimizzare il gradimento complessivo, cioè la somma degli indici di gradimento delle ragazze invitate.
Formulare il problema come problema di PLI (Max Independent Set pesato) e risolvere con LINDO il seguente esempio:
Valori:
Samantha 100
Jessica 100
Melissa 90
Pamela 85
Naomi 50
Anastasia 20
Genoveffa 15
Gertrude 10
Amicizie:
Samantha - Jessica - Melissa
Jessica - Melissa - Pamela
Jessica - Gertrude
Melissa - Genoveffa
Pamela - Naomi
Gertrude - Genoveffa - Naomi
Gertrude - Genoveffa - Anastasia
Soluzione ottima: Valore ottimo:
Samantha, Pamela, Anastasia 205
Soluzione
Nella parte dei vincoli che si vede nella soluzione qui sotto, ce ne sono di due tipi: quelli a 2 variabili e quelli a 3 variabili.
I vincoli a 2 variabili riguardano le coppie di ragazze che sono amiche. Ad esempio, Pamela e Naomi fanno parte di una coppia. Ma nel testo notiamo che ci sono anche triplette di amiche. Possiamo allora raggruppare i vincoli in triplette. La cosa di per sé non cambia il risultato, ma c'è un'osservazione da fare.
Prendiamo i primi tre vincoli:
x1 + x2 <= 1
x1 + x3 <= 1
x2 + x3 <= 1
Se voglio raggrupparli in un vincolo solo, potrei scrivere
2x1 + 2x2 + 2x3 <= 3
da cui tiro fuori, dividendo per due:
x1 + x2 + x3 <= 1.5
E questo significa che il mio incolo di binarietà non è propriamente espresso dal vincolo. Infatti, il fatto che ho un gruppo di 3 amiche vuol dire che devo invitarne solo 1 di quel gruppo. D'accordo che le variabili sono dichiarate binarie, e che quindi i valori non interi saranno scartati, ma se scrivo le cose per bene, ovvero
x1 + x2 + c3 <= 1
allora il solutore trova subito un upper bound migliore, rispetto a prima, mettendoci meno tempo.
Per gli amanti delle definizione, questo vincolo triplo si chiama vincolo di clique, dove la clique è un sottografo completo di un grafo. E infatti questo vincolo rappresenta proprio una clique di amiche di cui solo una va prescelta.
! Inviti a cena
! Variabili: x(i) = invito a cena ragazza i = 1..8 (binaria)
!funzione obiettivo: max valore complessivo
max 100 x1 + 100 x2 + 90 x3 + 85 x4 + 50 x5 + 20 x6 + 15 x7 + 10x8
st
! Vincoli su inviti indipendenti: non posso invitare coppie di amiche che si conoscono
! Li scrivo nella forma x1 + x2 <= 1
!x1 + x2 <= 1
!x1 + x3 <= 1
!x2 + x3 <= 1
x1 + x2 + x3 <= 1
!x2 + x4 <= 1
!x3 + x4 <= 1
x2 + x3 + x4 <= 1
x4 + x5 <= 1
x2 + x8 <= 1
x3 + x7 <= 1
!x5 + x8 <= 1
!x5 + x7 <= 1
!x7 + x8 <= 1
x5 + x7 + x8 <= 1
!x8 + x6 <= 1
!x7 + x6 <= 1
x6 + x7 + x8 <= 1
end
int 8
