Açık alan oturma optimizasyonu algoritması

Question

Şirketteki değişiklikler sonucunda, oturma planımızı yeniden düzenlemeliyiz: bir odada 10 masa vardır. Bazı masalar, nedenlerden dolayı diğerlerinden daha popüler. Bir çözüm şapkadan bir masa numarası çizmek olacaktır. Bunu yapmanın daha iyi bir yolu olduğunu düşünüyoruz.

10 masa ve 10 kişiye sahibiz. Bu yarışmaya katılan herkese 50 varsayımsal jetona masalarda teklif vermesini sağlar. Bir masaya ne kadar teklif verdiğinize dair bir sınırlama yoktur, "Sadece burada, periyodda oturmak istiyorum" diyen 50'nin tümünü yerleştirebilirsiniz. Ayrıca her masaya 5 jeton vererek “umurumda değil” diyebilirsiniz.

Önemli not: kimse başkalarının ne yaptığını bilmiyor. Herkes sadece kendi/onu yararına üzerinden karar verme vardır (tanıdık geliyor?)

Şimdi bu varsayımsal sonuçlar elde diyelim: Artık

# | 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 

, ne bulmalıyız olduğunu bir (veya daha fazla) bize maksimum memnuniyet sağlayan konfigürasyon (lar) (yani insanlar tüm teklifleri hesaba katmayı ve grubun toplamını maksimize etmeyi istedikleri masaları alırlar. Tabii ki varsayım, daha fazla kişi istediği masanın üzerinde daha fazla bir şeydir.).

Sadece 10 kişi olduğu için, tüm olası konfigürasyonlara bakmaya zorlayabileceğimizi düşünüyorum, ama bu tür problemleri çözmek için daha iyi bir algoritma olduğunu merak ediyordum?

Answer 1

Hungarian Algorithm kullanarak çözülebilen Assignment Problem'a bakıyorsunuz. Bu iyi araştırılmış bir sorundur ve muhtemelen web üzerinde kullanıma hazır kod bulacaksınız.

Sizin durumunuzda cost = 50 - bideyi kullanabilir ve yukarıdakileri kullanabilirsiniz (atama problemine herhangi bir çözüm).

Answer 2

Daha da hızlı bir şekilde, eğer Excel'iniz varsa, SOLVER'in de mevcut bir versiyonuna sahip olmalısınız. Sadece teklif matrisinizi (tekliflerle 10x10), atama matrisini (0/1 atamalarla 10x10) ayarlayın, bir tahminin değerini hesaplamak için sumproduct (teklifler, ödevler) kullanın, hedef işlevinizi yapın ve bu yüzden kısıtlamalar ekleyin. İnsanların masalarına ve masalarına insanlardan sadece bir ödevi. Seçenekler> "lineer model" kutucuğuna sahip olduğunuzdan ve "negatif olmayan" aldığınızdan ve çözüldüğünüzden emin olun! Ben sadece bir örnek 10x10 sorun kurdum - Tamam çalışıyor gibi görünüyor.