Pythonのオンライン学習サービスであるPyQの「数理的アプローチによる問題解決」という教材を少し学習してみました。

グラフ理論を実装するnetworkxというライブラリや、PuLPという線形最適化のライブラリなどについて学ぶことができます。具体的なコース内容はまた別の機会に紹介できればと思いますが、特にPuLPを使うと簡単に最適化が実行できて役に立ちそうでしたので、試しに業務割当てを最適化するプログラムを作ってみました。

なお私自身はあくまで経理マンであり、プログラミングは初心者ですので、プログラムが冗長で洗練されていない点はご了承ください。お気付きの点がありましたら、ご指摘いただけると助かります。

解きたい問題は何か？
Python + PuLPによる実装
ソルバーの実行と実行結果
使用したプログラム
もう少し複雑な問題を解いてみる

解きたい問題は何か？

複数のタスクを複数人のメンバーで、決められた時間内に処理することを考えます。このとき、それぞれのタスクを一人で完了させてもよいし、複数人で分担してもOKとします。

ここで、各々のメンバーがそれぞれのタスクを一人で完了させる時に、どのくらいの時間を要するかを考えます。未経験のため実施できない業務、また（過去に何度も行っているため）教育的配慮でアサインさせたくない業務などもあるでしょう。また、各々のメンバーの労働時間にも制約があります。

上記のような制約のもと、チームの総労働時間が最短となるような割り振りを考えます。

以下、具体例として、３つのタスクをA, B, Cの３人で分担することを考えます*1。各々の所要時間は以下の通りとします。たとえばAさんはTask 1が実施できず、Task 2は8時間、Task 3は6時間で一人で終わらせることができることを意味しています。

（単位：時間）	A	B	C
Task 1	―	7	4
Task 2	8	5	3
Task 3	6	―	2

労働時間の制約は以下の通りとします。Cさんはレビュアー的な立ち位置のため、基本的にはタスクを行わないという設定です。

（単位：時間）	A	B	C
労働時間数の上限	10	10	0.5

Python + PuLPによる実装

準備

以下、さっそくPythonで実装していきます。データ分析ライブラリとしておなじみのpandasの他、線形最適化のライブラリとしてPuLPとortoolpyをインポートします。

import pandas as pd
from pulp import LpProblem, lpSum, value, LpStatus
from ortoolpy import addvars

続いて、制約条件をpandasのDataFrameに格納します。ここではプログラム上に直接記載しますが、もちろんread_csvを用いて、csvファイルから読み込んでもOKです。

対応できないタスクについては、十分大きな数（ここでは100）を設定することで、最適化の際に選択されないようにしています。

df = pd.DataFrame({'A': [100, 8, 6],
                   'B': [7, 5, 100],
                   'C': [4, 3, 2]})

num_of_task = len(df) # タスク数
num_of_member = len(df.columns) # メンバー数

# 各々の労働時間数の上限を設定
df_limit = pd.DataFrame({'A': [10], 'B': [10], 'C': [0.5]})

線形最適化モデルの作成

ここから、線形最適化ライブラリのPuLPを用いて、線形最適化モデルを設定します。具体的には、モデルに目的関数と制約条件を設定します。

まず、LpProblemで空のモデルmを作成します。線形最適化には最大化と最小化とがありますが、LpProblemはデフォルトで目的関数を最小化するモデルが作成されるため、このままでOKです*2。

さらに、必要な変数を作成します。各々のメンバーについて、各々のタスクの分担割合を定める必要があるため、「タスク数×メンバー数」分の変数が必要になります。ここで、ortoolpyのaddvarsを使うと、非負かつ連続変数を簡単に作れるので非常に便利です。これらの変数もpandasのDataFrameに格納しておきます。

m = LpProblem() # 何も指定しないと目的関数を最小化
df_var = pd.DataFrame(addvars(num_of_task, num_of_member))

目的関数の設定

モデルを作った後は、目的関数を設定します。"m += （目的関数）"という書き方で設定できます。ここでの目的関数は、全てのメンバーの労働時間の合計になります。

lpSumは( )内の合計を計算できます。sumも使えますが、lpSumの方が高速で動作するようです。

# 目的関数
m += lpSum([df.iloc[:, i] * df_var[i] for i in range(num_of_member)])

制約条件の設定

続いて、制約条件を設定します。制約条件も同様に、"m += （制約条件）"という書き方で設定できます。目的関数も制約条件も書き方が同じなのが、少し不思議な感じがしますが、これでOKです。

制約条件は、各タスクの負担割合の合計が1（100%）になることと、各々の労働時間が上限を超えないこと、の二つです。

# 制約条件：割合は合計で100%とする
for i in range(num_of_task):
    m += lpSum(df_var.iloc[i]) == 1

# 制約条件：各々の労働時間の上限範囲内で業務を行う
for i in range(num_of_member):
    m += lpSum(df.iloc[:, i] * df_var[i]) <= df_limit.iloc[:, i]

作成したモデルの確認

以上で目的関数と制約条件を設定できました。正しく設定できたかどうかを確認するため、モデルmの内容を表示してみます。

print(m) # 目的関数、制約条件を表示

以下のように目的関数、制約条件、および変数が一覧で表示され、正しくモデルが作成されていることがわかります。

NoName:

MINIMIZE
100*v000001 + 7*v000002 + 4*v000003 + 8*v000004 + 5*v000005 + 3*v000006 + 6*v000007 + 100*v000008 + 2*v000009 + 0

SUBJECT TO
_C1: v000001 + v000002 + v000003 = 1
_C2: v000004 + v000005 + v000006 = 1
_C3: v000007 + v000008 + v000009 = 1
_C4: 100 v000001 + 8 v000004 + 6 v000007 <= 10
_C5: 7 v000002 + 5 v000005 + 100 v000008 <= 10
_C6: 4 v000003 + 3 v000006 + 2 v000009 <= 0.5

VARIABLES
v000001 Continuous
v000002 Continuous
v000003 Continuous
v000004 Continuous
v000005 Continuous
v000006 Continuous
v000007 Continuous
v000008 Continuous
v000009 Continuous

ソルバーの実行と実行結果

モデルが作成出来たら、以下のようにソルバーを実行します。実行自体は、solveで簡単に実行できますが、最適解が求まったかどうかを確認するため、合わせてステータスを表示しています。

m.solve() # ソルバーの実行
print('status = ' + LpStatus[m.status]) # ステータスの表示

以下の通り、最適解が得られたことがわかります*3。

status = Optimal

最適解を得られたので、具体的に求めた変数を表示するとともに、最小化された目的関数を計算します。valueを用いることで、変数に代入されている数値を取り出すことができます。

# 目的関数を最小化する変数および最適解の表示
total = 0
for i in range(num_of_task):
    print()
    for j in range(num_of_member):
        print(value(df_var.iloc[i][j]), end=' ')
        total += value(df_var.iloc[i][j]) * df.iloc[i][j]

print()
print('total = ' + str(total))

表示結果は以下の通りです。

0.0 1.0 0.0
0.4 0.6 0.0
0.75 0.0 0.25
total = 18.2

続いて、各メンバーの労働時間を表示します。

# 各人の労働時間の計算
total = 0

for j in range(num_of_member):
    total = 0
    for i in range(num_of_task):
        total += value(df_var.iloc[i][j]) * df.iloc[i][j]
    print(df.columns[j] + ": " + str(total))

表示結果は以下の通りです。

A: 7.7
B: 10.0
C: 0.5

線形最適化の結果、以下の結果が得られました。

No.	A	B	C	合計
Task 1	―	100%	―	100%
Task 2	40%	60%	―	100%
Task 3	75%	―	25%	100%
労働時間	7.7	10.0	0.5	18.2

使用したプログラム

以下にプログラムをまとめて記載しておきます。

import pandas as pd
from pulp import LpProblem, lpSum, value, LpStatus
from ortoolpy import addvars

df = pd.DataFrame({'A': [100, 8, 6],
                   'B': [7, 5, 100],
                   'C': [4, 3, 2]})

num_of_task = len(df) # タスク数
num_of_member = len(df.columns) # メンバー数

# 各々の労働時間数の上限を設定
df_limit = pd.DataFrame({'A': [10], 'B': [10], 'C': [0.5]})

m = LpProblem() # 何も指定しないと目的関数を最小化
df_var = pd.DataFrame(addvars(num_of_task, num_of_member))

# 目的関数
m += lpSum([df.iloc[:, i] * df_var[i] for i in range(num_of_member)])

# 制約条件：割合は合計で100%とする
for i in range(num_of_task):
    m += lpSum(df_var.iloc[i]) == 1

# 制約条件：各々の与えられた時間内で業務を行う
for i in range(num_of_member):
    m += lpSum(df.iloc[:, i] * df_var[i]) <= df_limit.iloc[:, i]

print(m) # 目的関数、制約条件を表示

m.solve() # ソルバーの実行

print('status = ' + LpStatus[m.status]) # ステータスの表示

# 目的関数を最小化する変数および最適解の表示
total = 0
for i in range(num_of_task):
    print()
    for j in range(num_of_member):
        print(value(df_var.iloc[i][j]), end=' ')
        total += value(df_var.iloc[i][j]) * df.iloc[i][j]

print()
print('total = ' + str(total))
print()

# 各人の所要時間の計算
total = 0

for j in range(num_of_member):
    total = 0
    for i in range(num_of_task):
        total += value(df_var.iloc[i][j]) * df.iloc[i][j]
    print(df.columns[j] + ": " + str(total))

もう少し複雑な問題を解いてみる

最後に、もう少し複雑な問題を試しに解いてみます。とある経理部における、月次決算のアサインの最適化を考えてみます。課長以下5人のメンバーで、10個のタスクを行うことを考えます。

それぞれのメンバーがタスクを一人で実施する際の所要時間は、以下の通りとします。

	（単位：時間）	A	B	C	D	E
1	入出金記帳	10	10	5	―	10
2	請求書処理	30	25	20	―	30
3	立替経費精算	25	20	15	―	30
4	売上・売上債権	30	20	―	20	30
5	棚卸資産	―	30	20	20	30
6	固定資産	20	―	30	―	30
7	社債・借入金	15	15	10	―	20
8	引当金	―	10	5	5	10
9	時価評価	10	10	15	10	10
10	税効果・税金計算	―	―	10	10	10

労働時間の制約は以下の通りとします。Bさんは時短のため労働時間が短く、Dさんは係長のため初歩的な仕事は行いません。そしてEさんは課長であり、基本的にはタスクを行わないという設定です。

（単位：時間）	A	B	C	D	E
労働時間数の上限	55	25	40	20	5

上記のプログラムを使って解いてみると、以下の結果となりました。

		A	B	C	D	E	合計
1	入出金記帳	―	―	100%	―	―	100%
2	請求書処理	30%	20%	50%	―	―	100%
3	立替経費精算	―	―	100%	―	―	100%
4	売上・売上債権	―	100%	―	―	―	100%
5	棚卸資産	―	―	25%	75%	―	100%
6	固定資産	100%	―	―	―	―	100%
7	社債・借入金	100%	―	―	―	―	100%
8	引当金	―	―	―	100%	―	100%
9	時価評価	100%	―	―	―	―	100%
10	税効果・税金計算	―	―	50%	―	50%	100%
	労働時間	54.0	25.0	40.0	20.0	5.0	144.0

*1:もちろん任意のm×nに拡張することも可能です。

*2:今回の目的は、総労働時間の最小化です。なお、最大化する場合は「(sense=LpMaximize)」と指定します。

*3:"m.status"を表示させると、最適解が得られた場合は「1」となります。

昭和生まれ30代経理マンが令和に始めたBlog

チーム内の業務割当てをPython + PuLPで最適化