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.
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 e fi;
le 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.
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 gi 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.
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 è 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.
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, indicato con v (N), deve avere una corrispondenza fisica, poiché l’algebra puo fornire risultati non realizzabili: =1 j∈S
xij
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
