整数計画法でアルバイトのシフトを作成してみた【経営工学を専門にしている大学生の日記】

## 事前準備
# pulpをインポート
! pip install pulp
from pulp import *
# numpyをインポート
import numpy as np
# ppprintをインポート
import pprint

# ランダムな値を固定する
np.random.seed(100)

## 問題の設定
# 問題を最小化に設定する
prob = LpProblem(sense=LpMinimize)

# 集合の定義
P = {i for i in range(16)} # バイトの集合
D = {i for i in range(7)} # 曜日の集合
S = {"d", "e", "n"} # シフトの集合
# パラメータの定義
NumP = {"d":4, "e":3, "n":2} # 各シフトに必要な人数のパラメータ
E = dict(zip(P,np.random.randint(20000, 80000, 16))) # 各バイトの希望賃金のパラメータ
W ={"d":1000, "e":1200, "n":1500} # 各シフトの時給のパラメータ

# 変数の定義
x = pulp.LpVariable.dicts("x",(P,D,S), cat=LpBinary)
t = pulp.LpVariable("t", cat = LpContinuous)

# 目的関数の設定
prob += t

# 制約条件の設定
# 目的関数を混合最適計画問題に表現したことによって生じた制約
for i in P:
  prob += lpSum(8*W[k] * x[i][j][k] for j in D for k in S) - E[i] <= t
  prob += E[i] - lpSum(8*W[k] * x[i][j][k] for j in D for k in S) <= t

# 各シフトの必要人数を満たす
for j in D:
  for k in S:
    prob += lpSum(x[i][j][k] for i in P) == NumP[k]

# 1日のシフトは1個まで
for i in P:
  for j in D:
    prob += lpSum(x[i][j][k] for k in S) <= 1

# 準夜勤→日勤を禁止
for i in P:
  for j in D:
    prob += x[i][j]["e"] + x[i][(j+1)%7]["d"] <= 1

# 夜勤→日勤を禁止
for i in P:
  for j in D:
    prob += x[i][j]["n"] + x[i][(j+1)%7]["d"] <= 1

# 夜勤→純夜勤を禁止
for i in P:
  for j in D:
    prob += x[i][j]["n"] + x[i][(j+1)%7]["e"] <= 1

# 勤務日数は最大5日まで
for i in P:
  prob += lpSum(x[i][j][k] for j in D for k in S) <= 5

# 深夜勤は最大3連勤まで
for i in P:
  for j in D:
    prob += x[i][j]["n"] + x[i][(j+1)%7]["n"] + x[i][(j+2)%7]["n"] + x[i][(j+3)%7]["n"] <= 3

prob.solve() # 問題を解く

# 結果を表示
print(LpStatus[prob.status]) # 解の状態を表示（Optimalなら最適解が求められている)
print("Optimal Value =", value(prob.objective)) # 最適値を表示

# シフトを2次元リストで表す
data = [[] for i in range(len(P))]
for i in P:
  for j in D:
    if value(x[i][j]["d"]) == 1:
      data[i].append("日")
    elif value(x[i][j]["e"]) == 1:
      data[i].append("準")
    elif value(x[i][j]["n"]) == 1:
      data[i].append("深")
    else:
      data[i].append("×")
pprint.pprint(data)