要件

まず調整さんを出してもらいましょう。

・一人あたりどこかの日程に必ず参加する
・日程ごとの人数はできる限り等しくする

これを頑張って定式化しましょう。

まず、
$P$ = (メンバーの集合)
$D$ = (日程の集合)
とします。

$p\in P, d\in D$に対し、

\mathrm{hope}[p][d] = \left\{
\begin{array}{ll}
1 & (pがdに○) \\
0 & (pがdに×)
\end{array}
\right.

と調整さんの結果から定数を決めます。

次に変数を設定します。

$\mathrm{attend}[p][d]= (1or0)$は、$p$が$d$に実際に参加するかを表す変数です。
$M$は各日程の参加人数の上限です。これの最小化を目指すことで、各日程にばらつきない人数を割り当てることができます。

定式化するとこんな感じ。

\begin{align}
\mathrm{min} &\ M \\
\mathrm{s.t} \ &\forall d\in D\ \Sigma_{p \in P}\mathrm{hope}[p][d]\times \mathrm{attend}[p][d] \leq M \\
&\forall p\in P\ \Sigma_{d \in D}\mathrm{hope}[p][d]\times \mathrm{attend}[p][d] = 1

\end{align}

制約条件の一つ目の式は、それぞれの日において、参加人数はM以下という条件。
制約条件の二つ目の式は、それぞれの人は、必ず１回だけ参加するという条件。

これをガンガンときましょう。

コード

chousei.py

import pulp

date = ["3/8", "3/9", "3/11", "3/15"]
people = # ここにメンバーの名前のリストを入れる

_table = [
[1,1,1,1], 
[0,1,0,0],
[1,1,0,0],
[0,1,1,0],
[1,0,0,0],
[1,1,0,1],
[1,0,0,0],
[0,1,0,1],
[0,1,1,0],
[1,1,1,1],
[1,1,1,1],
[1,1,0,0],
[1,0,0,1],
[0,1,1,1],
[0,1,0,0],
[1,1,1,1]] #調整さんの結果を書く


table = {}
for i,p in enumerate(people):
    table[p] = {}
    for j,d in enumerate(date):
        table[p][d] = _table[i][j]
# 辞書型に変換

problem = pulp.LpProblem('chousei', pulp.LpMinimize)
attend = pulp.LpVariable.dicts('attend', (people, date), 0, 1, 'Binary')
M = pulp.LpVariable('M', 0, 1000, 'Integer')
problem += M

for p in people:
    each_people = 0
    for d in date:
        each_people += table[p][d]*attend[p][d]
    problem += each_people == 1

for d in date:
    each_date = 0
    for p in people:
        each_date += table[p][d]*attend[p][d]
    problem += each_date <= M

problem.solve()

for d in date:
    each_date = ''
    for p in people:
        if(table[p][d] == 1　and attend[p][d].value() > 0):
            each_date += p
    print "{}: {}".format(d, each_date)

改良

このままだと年長者だけが固まる日程ができる可能性があるので、メンバー一人一人に重みをつけておいて、各日程ごとの重みの和の上限も最小化するみたいなことをすると良いと思います。気が向いたら解説します。

調整さんと整数線形計画

要件

コード

改良