割り当て最適化 PuLP

割り当て最適化

割り当て最適化問題の例として、「3人のスタッフが5つのタスクに割り当てられる場合、全体的な生産性を最大化する割り当てを決定する」という問題を考えてみます。

PuLPを使ってこの問題を解くコードは以下のようになります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from pulp import *

# 問題の初期化
problem = LpProblem("Task Assignment Problem", LpMaximize)

# 変数の定義
staff = ['Staff1', 'Staff2', 'Staff3']
tasks = ['Task1', 'Task2', 'Task3', 'Task4', 'Task5']
x = LpVariable.dicts('x', [(i, j) for i in staff for j in tasks], lowBound=0, upBound=1, cat=LpInteger)

# 目的関数の定義
problem += lpSum([x[i, j] for i in staff for j in tasks])

# 制約条件の定義
for j in tasks:
    problem += lpSum([x[i, j] for i in staff]) == 1

for i in staff:
    problem += lpSum([x[i, j] for j in tasks]) <= 2

# 問題の解決
status = problem.solve()

# 結果の出力
print("ステータス:", LpStatus[status])
for i in staff:
    for j in tasks:
        if x[i, j].value() == 1:
            print(i, "は", j, "に割り当てられました。")

このコードでは、問題を LpProblem として初期化し、変数 x を定義します。

変数 x は、スタッフとタスクのペアに対してバイナリ変数を持つ辞書型データとして定義されます。

目的関数は、割り当てられたタスクの数を最大化するように定義されます。

制約条件として、各タスクには1人のスタッフが割り当てられ、各スタッフには最大で2つのタスクが割り当てられるように定義されます。

最後に、PuLPの solve() メソッドを呼び出して問題を解決し、結果を出力します。

このコードを実行すると、以下のような結果が出力されます。

[実行結果]
ステータス: Optimal
Staff1 は Task2 に割り当てられました。
Staff1 は Task5 に割り当てられました。
Staff2 は Task1 に割り当てられました。
Staff3 は Task3 に割り当てられました。
Staff3 は Task4 に割り当てられました。

これは、最適な割り当てが見つかったことを示しています。

たとえば、スタッフ1はタスク2とタスク5に、スタッフ2はタスク1に、スタッフ3はタスク3とタスク4に割り当てられました。

これにより、各スタッフに最大で2つのタスクが割り当てられ、割り当てられたタスクの総数が最大になっています。

なお、PuLPはオープンソースの数理最適化モデリング言語であり、線形および混合整数線形最適化問題を解くための強力なツールです。

PuLPを使用することで、上記のような最適化問題を簡単にモデル化し、解決することができます。