Algoritmo di ottimizzazione dello spazio aperto

Question

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

Abbiamo 10 scrivanie e 10 persone. Diamo a ogni persona in questo concorso 50 ipotetici token per fare offerte sui banchi. Non c'è limite di quanto fai un'offerta su una scrivania, puoi mettere tutti 50, il che direbbe "Voglio sedermi solo qui, punto". Puoi anche dire "Non mi interessa" dando ogni scrivania 5 token.

Nota importante: nessuno sa cosa stanno facendo gli altri. Tutti devono decidere in base solo al suo miglior interesse (sembra familiare?)

Ora diciamo che abbiamo ottenuto questi ipotetici risultati:

#  | 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, ciò che dobbiamo trovare è che una (o più) configurazione che ci dà la massima soddisfazione (cioè le persone ottengono scrivanie che volevano prendere in considerazione tutte le offerte e massimizzare il totale del gruppo. Naturalmente l'ipotesi è il Più uno spinto sulla scrivania, più lo vuole).

Dal momento che ci sono solo 10 persone, penso che possiamo bruto costringerlo a guardare in tutte le possibili configurazioni, ma mi chiedevo che esiste un algoritmo migliore per risolvere questo tipo di problemi?

Answer 1

Sembra che tu stia guardando il Problema di assegnazione che può essere risolto usando Algoritmo ungherese. Questo è un problema ben studiato e probabilmente troverai codice sul web, pronto per l'uso.

Nel tuo caso puoi utilizzare costi = 50 - offrire e utilizzare quanto sopra (qualsiasi soluzione per il problema dell'assegnazione).

Answer 2

Ancora più veloce, se hai Excel dovresti avere anche una versione del risolutore disponibile. 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 incarico, rendere la tua funzione obiettivo e aggiungere vincoli in modo che ci sia Solo un incarico di persone a scrivanie e scrivanie alle persone. Assicurati di avere le opzioni> "Modello lineare" controllato e assumi "non negativo" e risolvi! Ho appena impostato un problema 10x10 di esempio - sembra funzionare bene.