Algoritmo di ottimizzazione della seduta aperta

Question

Come risultato di cambiamenti nell'azienda, dobbiamo riorganizzare il nostro piano di seduta: una stanza con 10 postazioni. Alcuni banchi sono più popolari di altri per una serie di motivi. Una soluzione sarebbe quella di disegnare un numero di scrivania da un cappello. Pensiamo che ci sia un modo migliore per farlo.

Abbiamo 10 postazioni e 10 persone. Diamo a ogni persona in questo concorso 50 gettoni ipotetici per fare offerte sulle scrivanie. Non c'è limite a quanto si fa su una scrivania, si possono mettere tutti e 50, che direbbero "Voglio sedermi solo qui, punto". Puoi anche dire "Non mi interessa" dando a ogni banco 5 segnalini.

Nota importante: nessuno sa cosa fanno gli altri. Ognuno deve decidere in base solo sulla sua/il suo interesse (suona familiare?)

Ora consente di dire che abbiamo ottenuto questi risultati ipotetici:

# | Desk# >| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 
1 | Alise | 30 | 2 | 2 | 1 | 0 | 0 | 0 | 15 | 0 | 0 | = 50 
2 | Bob | 20 | 15 | 0 | 10 | 1 | 1 | 1 | 1 | 1 | 0 | = 50 
    ... 
10 | Zed | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | = 50 

Ora, quello che dobbiamo trovare è che uno (o più) configurazione (s) che ci dà la massima soddisfazione (cioè le persone prendono gli sportelli che volevano tenendo conto di tutte le offerte e massimizzando sul totale del gruppo.) Naturalmente, l'ipotesi è che più si è disposti sulla scrivania più lo si vuole).

Dato che ci sono solo 10 persone, penso che possiamo potenziarlo forzatamente esaminando tutte le possibili configurazioni, ma mi stavo chiedendo se esiste un algoritmo migliore per risolvere questo tipo di problemi?

Answer 1

Sembra che tu stia guardando il Assignment Problem che può essere risolto utilizzando Hungarian Algorithm. Questo è un problema ben studiato e probabilmente troverai il codice sul web, pronto per l'uso.

Nel tuo caso è possibile utilizzare il costo = 50 - offerta e utilizzare quanto sopra (qualsiasi soluzione al problema di assegnazione).

Answer 2

Ancora più veloce, se si dispone di Excel si dovrebbe avere una versione di SOLVER disponibile pure. Basta impostare la matrice di offerta (10x10 con offerte), matrice di assegnazione (10x10 con assegnazioni 0/1), utilizzare sumproduct (offerte, assegnazioni) per calcolare il valore di un compito, rendere tale funzione obiettiva e aggiungere vincoli in modo che un solo incarico di persone a scrivanie e scrivanie per le persone. Assicurati di aver selezionato le opzioni> casella "modello lineare" e "si presuma non-negativo" e risolvi il problema! Ho appena creato un esempio di problema 10x10 - sembra funzionare bene.