【これでわかる！】pythonでアルバイトのシフト作成問題を解く方法をなるべく分かりやすく解説してみた

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

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

# 集合の定義
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 = LpProblem(sense=LpMinimize)

# 目的関数の設定
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)

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

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

# 集合の定義
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 = LpProblem(sense=LpMinimize)

# 目的関数の設定
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)