5

会社の変更の結果として、私たちは座席表を再調整する必要があります。1つの部屋に10台の机があります。いくつかの理由で他の机より人気があります。1つの解決策は、帽子からデスク番号を引き出すことです。私たちはそれを行うためのより良い方法があると思います。

私たちは10の机と10人を持っています。このコンテストのすべての人に、机に入札するための50個の仮想トークンを与えましょう。1つの机にいくら入札するかは制限がなく、「ここだけ座りたい、期間」と言って50個全部入れることができます。すべてのデスクに5トークンを与えることで、「私は気にしない」と言うこともできます。

重要な注意：他の人が何をしているのか誰も知りません。誰もが自分の最善の利益だけに基づいて決定する必要があります（おなじみのように聞こえますか？）

ここで、これらの架空の結果が得られたとしましょう。

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

さて、私たちが見つける必要があるのは、私たちに最大の満足を与える1つ（または複数）の構成です（つまり、人々はすべての入札を考慮し、グループ全体を最大化して、必要なデスクを手に入れます。当然のことながら、仮定は机の上に1つ以上の入札があれば、彼/彼女はそれをもっと欲しがる）。

人数が10人しかないので、考えられるすべての構成を総当たり攻撃で調べることができると思いますが、この種の問題を解決するためのより良いアルゴリズムがあるのではないかと思いました。

4

2 に答える 2

3

あなたはハンガリーのアルゴリズムを使用して解決できる割り当て問題を見ているようです。これはよく研究された問題であり、おそらくWeb上にコードがあり、すぐに使用できます。

あなたの場合、コスト= 50を使用できます-入札して上記を使用します（割り当ての問題に対する任意の解決策）。

于 2010-06-11T13:15:32.203 に答える
0

さらに高速に、Excelを使用している場合は、SOLVERのバージョンも利用できるはずです。入札マトリックス（入札で10x10）、割り当てマトリックス（0/1割り当てで10x10）を設定し、sumproduct（bids、assignments）を使用して割り当ての値を計算し、それを目的関数にして、制約を追加するだけです。デスクへの人の割り当てと人へのデスクの割り当ては1つだけです。[オプション]>[線形モデル]チェックボックスがオンになっていることを確認し、[非負であると想定]して解決してください。サンプルの10x10の問題を設定しました-問題なく動作しているようです。

于 2010-06-11T21:01:04.903 に答える