이게 뭐야

1년 1조의 당신은, 체육제의 모습을 기록한 책자를 작성하게 되었다. 1년 1조의 20명의 학생으로부터 5장씩, 총 100장의 사진을 맡겼다.
자, 어떤 사진을 선택할까요?

정책

학생과 PTA에게 물어 보았습니다.

각 학생의 찍은 매수(피사체수라고 부르기로 한다)가 적은 사람이 없도록 하고 싶다.

위의 조건을 충족시킨 뒤, 많이 찍는 것이 좋다.

덧붙여 사진은 20장 이내에 담아야 한다.

파이썬으로 시도

사진 데이터 만들기

사진 데이터(어느 사진이 누구인지)를 작성한다.

python3

import numpy as np, pandas as pd
ni, nj, nu = 20, 100, 20 # 生徒数, 写真数, 選択する写真数
生徒s = ['生徒%.2d'%i for i in range(1,ni+1)]
np.random.seed(1)
mkst = lambda: set(np.random.choice(生徒s, max(1,int(np.random.normal(4,2))), False))
a = pd.DataFrame([('写真%.3d'%j, mkst()) for j in range(1,nj+1)],
    columns=['写真', '生徒'])
a[:3] # 最初の3行

사진
학생




0
사진 001
{학생 04, 학생 15, 학생 18, 학생 09, 학생 11, 학생 14, 학생 19}


1
사진 002
{학생 04, 학생 03}


2
사진 003
{학생 09, 학생 06, 학생 08, 학생 07, 학생 17}

풀다

목적함수는 적당히 「10×최소피사체수＋총피사체수」로 해보자.

python3

from pulp import *
from ortoolpy import addvar, addvars, addbinvars
m = LpProblem(sense=LpMaximize) # 数理モデル
a['x'] = addbinvars(nj) # 写真ごとの選択
y      = addvars(ni)    # 生徒ごとの被写体数
ymin   = addvar()       # 最小被写体数
m += 10*ymin + lpSum(y) # 目的関数
m += lpSum(a.x) == nu # 選択写真数
for yi,st in zip(y,生徒s):
    m += yi == lpSum(r.x for _,r in a.iterrows()
                     if st in r.生徒) # 各生徒の被写体数
    m += ymin <= yi
%time m.solve() # 求解
a['rx'] = np.vectorize(value)(a.x).astype(int) # 結果
ry      = np.vectorize(value)(y  ).astype(int) # 結果
print('%s 最小%d名 平均%.2f名'%
    (LpStatus[m.status], value(ymin), sum(ry)/ni))
>>>
Wall time: 39.2 ms
Optimal 最小5名 平均6.25名

선택한 사진을 보자.

python3

a[a.rx>0][:3] # 最初の3行

사진
학생
x
rx




0
사진 001
{학생 04, 학생 15, 학생 18, 학생 09, 학생 11, 학생 14, 학생 19}
v0122
1


11
사진 012
{학생 07, 학생 10, 학생 18, 학생 09, 학생 02, 학생 19}
v0133
1


13
사진 014
{학생 03, 학생 06, 학생 18, 학생 09, 학생 02, 학생 12, 학생 16}
v0135
1



학생별 피사체 수를 확인한다.

python3

%matplotlib inline
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'IPAexGothic'
plt.plot(ry)
plt.xlabel('生徒')
plt.title('被写体数');

클레임 대응

선택한 사진을 봐주자 조속히 "자신이 제출한 사진도 골라달라"고 클레임이 왔다.

「각 학생의 제출한 사진에서 1장씩 선택하는 것」을 제약 조건에 추가해 재실행해 보자.

python3

from more_itertools import chunked
m = LpProblem(sense=LpMaximize) # 数理モデル
a['x'] = addbinvars(nj) # 写真ごとの選択
y      = addvars(ni)    # 生徒ごとの被写体数
ymin   = addvar()       # 最小被写体数
m += 10*ymin + lpSum(y) # 目的関数
m += lpSum(a.x) == nu # 選択写真数
for yi,st in zip(y,生徒s):
    m += yi == lpSum(r.x for _,r in a.iterrows()
                     if st in r.生徒) # 各生徒の被写体数
    m += ymin <= yi
for t in chunked(a.iterrows(), 5): # 各生徒提出の5枚組
    m += lpSum(r.x for _,r in t) == 1 # 5枚組から1枚選ぶ
%time m.solve() # 求解
a['rx'] = np.vectorize(value)(a.x).astype(int) # 結果
ry      = np.vectorize(value)(y  ).astype(int) # 結果
print('%s 最小%d名 平均%.2f名'%
    (LpStatus[m.status], value(ymin), sum(ry)/ni))
>>>
Wall time: 54.1 ms
Optimal 最小5名 平均5.70名

최소 피사체 수는 5장으로 남았다. 이번에는 만족해 주신 것 같다.

이상