Facility location game
Il gioco considerato è un problema di cost sharing: l'idea è quella di suddividere il costo di un servizio tra i vari giocatori in modo "fair".
Nel facility location un insieme N di clienti deve accedere a un certo servizio. Il servizio può essere erogato in diverse facility ed F è l'insieme di tutte le facility.
Costi e decisioni
L'erogazione del servizio ha i seguenti costi:
- Ciascun cliente j ∈ N può servirsi presso un centro i ∈ F che sia aperto, con un costo pari a dij;
- Per ogni centro i ∈ F il costo di apertura è fi;
La decisione da prendere è dunque quale facility aprire.
Tale situazione è formulabile come un problema di programmazione lineare intera. Le variabili del problema sono:
- yi, pari a 1 se la facility i è aperta e pari a 0 altrimenti;
- xij, pari a 1 se il cliente j si serve presso la facility i e pari a 0 altrimenti.
Formulazione del problema
Il problema è dunque
min ( ∑i ∈ F fi yi + ∑i ∈ F j ∈ N dij xij ) — questa è la funzione di costo
∑i ∈ F xij ≥ 1 — j ∈ N ogni cliente si deve servire presso una sola facility
xij ≤ yi — i ∈ F, j ∈ N se un cliente si serve presso una facility, essa deve essere aperta
xij, yi ∈ {0,1} — i ∈ F, j ∈ N
Facility location game
Il gioco considerato è un problema di cost sharing: l’idea è quella di suddividere il costo di un servizio tra i vari giocatori in modo fair.
Nel Facility location un insieme N di clienti deve accedere a un certo servizio. Il servizio può essere erogato in diverse facility ed F è l’insieme di tutte le facility.
Costi, variabili e apertura delle facility
L’erogazione del servizio ha i seguenti costi:
- Ciascun cliente j ∈ N può servirsi presso un centro i ∈ F che sia aperto, con un costo pari a dij;
- Per ogni centro i ∈ F il costo di apertura è fi;
Le decisioni da prendere sono dunque quale facility aprire.
Tale situazione è formulabile come un problema di programmazione lineare intera. Le variabili del problema sono:
- yi, pari a 1 se la facility i è aperta e pari a 0 altrimenti;
- xij, pari a 1 se il cliente j si serve presso la facility i e pari a 0 altrimenti.
Problema e vincoli
Il problema è dunque
min (∑i ∈ F fi yi + ∑i ∈ F ∑j ∈ N dij xij ) questa è la funzione di costo
∑i ∈ F xij ≥ 1 ∀ j ∈ N ↦ ogni cliente si deve servire presso una sola facility
xij ≤ yi ∀ i ∈ F, ∀ j ∈ N ↦ se un cliente si serve presso una facility, essa deve essere aperta
xij, yi ∈ {0, 1} ∀ i ∈ F, ∀ j ∈ N
Una soluzione ottima, indicata con v (N), deve avere una corrispondenza fisica, poiché l’algebra può fornire risultati non realizzabili: =1 j∈Sxij
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Recensioni
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
