看護師スケジュール作成問題

医療に関する最適化問題の例として、病院の看護師スケジュール作成問題を考えてみましょう。

この問題では、病院で働く看護師の勤務シフトをスケジュールする必要があります。

スケジュールは、各看護師の希望や能力に応じて、労働法や病院の規則に準拠しなければなりません。

PuLPを使用して、看護師のスケジュールを最適化し、病院の運営を改善することができます。

以下が、この問題を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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

from pulp import *

# ①条件を定義する
# 看護師の数
num_nurses = 5

# シフトの数
num_shifts = 3

# 各シフトで必要な看護師の数
shift_requirements = [2, 1, 2]

# 看護師の希望を表す二次元配列。0は不可能、1は可能。
# 希望は、勤務シフトを表すインデックスで表されます。
# たとえば、nurse_preferences[0][1] == 1は、看護師0が2番目のシフトを希望していることを示します。
nurse_preferences = [[0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1], [0, 1, 0]]

# ②問題を定義する
problem = LpProblem("Nurse Scheduling", LpMinimize)

# ③変数を作成する
shifts = LpVariable.dicts("Shift", ((n, s) for n in range(num_nurses) for s in range(num_shifts)), cat='Binary')

# ④目的関数を設定する
problem += lpSum([shifts[(n, s)] for n in range(num_nurses) for s in range(num_shifts)])

# ⑤制約条件を設定する
for s in range(num_shifts):
    problem += lpSum([shifts[(n, s)] for n in range(num_nurses)]) >= shift_requirements[s]
    
for n in range(num_nurses):
    problem += lpSum([shifts[(n, s)] for s in range(num_shifts)]) == 1
    
for n in range(num_nurses):
    for s in range(num_shifts):
        if nurse_preferences[n][s] == 0:
            problem += shifts[(n, s)] == 0

# ⑥問題を解く
status = problem.solve()

# ⑦結果を出力する
print("ステータス:", LpStatus[status])

for n in range(num_nurses):
    for s in range(num_shifts):
        if value(shifts[(n, s)]) == 1:
            print("看護師{}は、シフト{}に割り当てられました".format(n, s))

① 条件を定義する

最初に、看護師の数、シフトの数、各シフトで必要な看護師の数、および各看護師のシフト希望を表す二次元配列を定義します。

② 問題を定義する

PuLPの LpProblem() 関数を使用して、問題を定義します。

この問題は、看護師のスケジュール作成を目的としています。

PuLPの LpMinimize モードを使用して、最小化問題を解決します。

③ 変数を作成する

PuLPの LpVariable.dicts() 関数を使用して、shifts 変数を作成します。

各変数は、看護師があるシフトに割り当てられる場合は1、そうでない場合は0を取るバイナリ変数です。

④ 目的関数を設定する

PuLPの lpSum() 関数を使用して、目的関数を設定します。

目的関数は、スケジュールに割り当てられたシフトの数を最小化することです。

⑤ 制約条件を設定する

PuLPの += 演算子を使用して、制約条件を設定します。

最低限必要な看護師数の制約条件、各看護師が1つのシフトにしか割り当てられない制約条件、および各看護師がシフト希望に従って割り当てられる制約条件を設定します。

⑥ 問題を解く

PuLPの solve() 関数を使用して、問題を解決します。

最適解が見つかれば、そのステータスが返されます。

⑦ 結果を出力する

最後に、割り当てられた各看護師のシフトを表示します。

看護師の番号とシフトの番号が表示されます。

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

[実行結果]

ステータス: Optimal
看護師0は、シフト2に割り当てられました
看護師1は、シフト2に割り当てられました
看護師2は、シフト0に割り当てられました
看護師3は、シフト0に割り当てられました
看護師4は、シフト1に割り当てられました

ステータスが Optimalであることが示されています。

これは、問題が最適解を見つけることができたことを示しています。

次に、各看護師がどのシフトに割り当てられたかが表示されます。

例えば、看護師0は2番目のシフトに割り当てられました。

これは、制約条件と目的関数を満たし、最適なスケジュールに割り当てられたことを意味します。

このプログラムによって、病院の看護師スケジュール作成問題が解決され、最適なスケジュールが得られました。

生産計画問題

生産計画問題の例を考えます。

3つの製品（A、B、C）を製造するために必要な原材料の量、1つの生産ラインの生産能力、および各製品の利益率が与えられています。

各製品は少なくとも1つ以上生産する必要があります。

製品の生産量を最適化して、最大の利益を得ることが目的です。

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 *

# 1. 問題の定義
prob = LpProblem("Production Planning Problem", LpMaximize)

# 2. 変数の定義
A = LpVariable("Product A Units", lowBound=0, cat='Integer')
B = LpVariable("Product B Units", lowBound=0, cat='Integer')
C = LpVariable("Product C Units", lowBound=0, cat='Integer')

# 3. 目的関数の定義
prob += 3000*A + 5000*B + 2000*C

# 4. 制約条件の定義
prob += 3*A + 2*B + 1.5*C <= 1500
prob += 1.5*A + 2.5*B + 3*C <= 3000
prob += A + B + C <= 1000
prob += A >= 1
prob += B >= 1
prob += C >= 1

# 5. 最適化の実行
prob.solve()

# 6. 結果の表示
print("Status:", LpStatus[prob.status])
for v in prob.variables():
    print(v.name, "=", v.varValue)
print("Total Profit = ", value(prob.objective))

1. 問題の定義

LpProblem関数を使用して問題を定義しています。

LpProblem関数は、第1引数に問題名、第2引数に最小化か最大化を指定します。

ここでは、”Production Planning Problem”という名前の最大化問題を定義しています。

2. 変数の定義

LpVariable関数を使用して、問題に必要な変数を定義しています。

LpVariable関数は、第1引数に変数の名前、lowBoundに変数の下限、catに変数の種類を指定します。

ここでは、”Product A Units”、”Product B Units”、”Product C Units”という名前の整数変数を定義しています。

3. 目的関数の定義

目的関数を定義しています。

ここでは、各製品の単位あたりの利益と各製品の製造量を掛けた値を合計して、最大化するようにしています。

4. 制約条件の定義

制約条件を定義しています。ここでは、各製品の製造に必要な原料の量、製品の総製造量に関する制約を定義しています。

また、各製品を少なくとも1つ生産する必要があるため、各変数に対して下限制約も設定しています。

5. 最適化の実行

solve関数を呼び出して、問題を解きます。

6. 結果の表示

解が得られたら、status属性を使用して最適性のステータスを表示し、variables属性を使用して各変数の最適な値を表示し、objective属性を使用して最適な目的関数値（総利益）を表示します。

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

[実行結果]

Status: Optimal
Product_A_Units = 1.0
Product_B_Units = 747.0
Product_C_Units = 2.0
Total Profit =  3742000.0

これにより、各製品を少なくとも1つ生産し、最大の利益である3742000ドルを得るために、1単位の製品A、747単位の製品B、および2単位の製品Cを製造する必要があることが確認できました。

割り当て最適化

割り当て最適化問題の例として、「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を使用することで、上記のような最適化問題を簡単にモデル化し、解決することができます。

為替ヘッジ問題

FX（外国為替）に関して最適化問題の一例として、為替ヘッジ問題が挙げられます。

為替ヘッジとは、外国通貨での取引によるリスクを減らすために、為替レートの変動に対して保護することです。

以下の例では、ある企業が米ドルで仕入れた商品を日本円で販売する場合の為替ヘッジ問題を考えます。

企業は、ある時点で米ドルを使って商品を購入する必要がありますが、商品の販売は数ヶ月後に行われます。

この間に、円/ドルの為替レートが変動することにより、企業の利益に影響を与える可能性があります。

企業は、為替レート変動のリスクを軽減するために、先物市場で円/ドルの未決済契約（フォワード契約）を取引することを考えています。

最適化問題は、フォワード契約を取引する数量を決定することです。

フォワード契約の数量が大きいほど、為替レート変動によるリスクは小さくなりますが、フォワード契約にかかるコストが増加します。

一方、フォワード契約の数量が少ないほど、コストは低くなりますが、リスクは大きくなります。

最適化問題をPuLPを用いて解いてみましょう。

以下のコードは、PuLPを用いた為替ヘッジ問題の最適化問題を解く例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import pulp

# 問題の設定
problem = pulp.LpProblem('FX Hedge Problem', pulp.LpMinimize)

# 変数の定義
forward_contract = pulp.LpVariable('Forward Contract', lowBound=0)

# 目的関数の定義
problem += 0.01 * forward_contract

# 制約条件の定義
problem += 10000 * forward_contract >= 1000000
problem += 10000 * forward_contract <= 2000000

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

# 結果の出力
print('Optimal Solution:')
print('Forward Contract Quantity =', pulp.value(forward_contract))
print('Minimum Cost =', pulp.value(problem.objective))

上記のコードでは、PuLPを使用して最小化問題を定義しています。

変数 forward_contract は、フォワード契約の数量を表しています。

目的関数は、フォワード契約にかかるコストを最小化するように設定しています。

フォワード契約の数量が増加すると、コストが増加することに注意してください。

制約条件では、フォワード契約の数量が、1ドルあたり100円から200円の範囲内に収まるように設定しています。

この制約条件は、フォワード契約によるリスク軽減とコスト増加のバランスを取るために必要です。

最後に、PuLPの solve() メソッドを呼び出して問題を解決し、フォワード契約の数量と最小コストを出力します。

解決結果には、PuLPの LpStatus 列挙型を用いてアクセスすることができます。

解が正常に見つかった場合、LpStatusOptimal が返されます。

上記のコードを実行すると、以下のような結果が得られます。

[実行結果]

Optimal Solution:
Forward Contract Quantity = 100.0
Minimum Cost = 1.0

この結果から、最適なフォワード契約の数量は100であり、最小コストは1万ドルであることがわかります。

これは、企業がリスクを軽減するためにフォワード契約を100万ドル分取引することが最も適していることを示しています。

多目的最適化問題

多目的最適化問題の例として、以下の問題を考えてみましょう。

🔹ある工場で、製品 A と製品 B を生産することができます。
🔹製品 A の生産には 2 時間かかり、製品 B の生産には 3 時間かかります。
🔹工場は最大10時間稼働することができます。
🔹製品 A 1 個あたりの利益は 10 ドルで、製品 B 1 個あたりの利益は 15 ドルです。
🔹工場で作ることのできる製品の最大量は 50 個です。

利益を最大化するためには製品Aと製品Bをそれぞれ何個作成すればよいでしょうか。

解法・ソースコード

PuLPを使用して、この問題を解決していきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from pulp import *

# ①問題の定義
prob = LpProblem("Multiple Objectives Problem", LpMaximize)

# ②変数の定義
A = LpVariable("A", 0, 50, LpInteger)
B = LpVariable("B", 0, 50, LpInteger)

# ③目的関数の定義
prob += 10 * A + 15 * B, "Total Profit"

# ④制約条件の定義
prob += 2 * A + 3 * B <= 10, "Time Limit"
prob += A + B <= 50, "Production Limit"

# ⑤問題の解決
prob.solve()

# ⑥結果の表示
print("A =", value(A))
print("B =", value(B))
print("Total Profit =", value(prob.objective))

①問題の定義

「Multiple Objectives Problem」という名前の最大化問題を作成するために、LpProblem()関数を使用します。

②変数の定義

変数AとBを作成し、LpVariable()関数を使用して上限値、下限値、および変数の種類（整数）を指定します。

③目的関数の定義

目的関数を定義するために、LpProblem()で作成した最大化問題である「prob」に、prob += を使用して目的関数を追加します。

「10 * A + 15 * B」という式を使用して、AとBの変数の重み付き合計を定義し、「Total Profit」という名前を付けます。

④制約条件の定義

制約条件を定義するために、LpProblem()で作成した最大化問題である「prob」に、prob += を使用して制約条件を追加します。

1つ目の制約条件では、「2 * A + 3 * B」が「10」以下である必要があります。

この制約条件の名前は「Time Limit」となっています。

2つ目の制約条件では、「A + B」が「50」以下である必要があります。

この制約条件の名前は「Production Limit」となっています。

⑤問題の解決

「prob」で定義された最大化問題を解くために、prob.solve()関数を使用します。

⑥結果の表示

最適解の結果を表示するために、value()関数を使用して、変数A、B、および目的関数の値を表示します。

実行結果は以下の通りです。

[実行結果]

A = 2.0
B = 2.0
Total Profit = 50.0

この結果から、最大化された製品 A は 2 個、製品 B は 2 個であり、それらの総利益は 50 ドルであることがわかります。

医療最適化

医療システムにおける最適化問題の一つとして、患者が異なる病院から受け取る医療サービスを最適化する問題があります。

この問題は、患者が最適な医療を受け、病院の効率を向上させることが目的です。

以下は、この問題をPuLPを使用して解決する方法の例です。

問題：

ある地域には3つの病院があり、それぞれが特定の専門分野に長けています。

患者はそれぞれの病院で必要な医療サービスを受ける必要があり、各病院の受け入れ可能な患者数には制限があります。

目標は、全ての患者が最適な病院で治療を受けることができるように、患者を病院に割り当てることです。

解法・ソースコード

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
30
31

from pulp import *

# ①問題を定義する
problem = LpProblem("Hospital Patient Assignment Problem", LpMinimize)

# ②患者がどの病院に割り当てられるかを決定する変数を定義する
patient_to_hospital = LpVariable.dicts("Patient to Hospital", 
                                      [(i, j) for i in range(3) for j in range(10)],
                                      cat="Binary")

# ③目的関数を設定する
costs = [[10, 20, 30, 40, 50, 60, 70, 80, 90, 100],
         [30, 25, 35, 45, 55, 65, 75, 85, 95, 105],
         [50, 45, 40, 35, 30, 25, 20, 15, 10, 5]]
problem += lpSum([patient_to_hospital[(i, j)] * costs[i][j] for i in range(3) for j in range(10)])

# ④制約条件を設定する
hospital_capacities = [5, 7, 3]
for i in range(3):
    problem += lpSum([patient_to_hospital[(i, j)] for j in range(10)]) <= hospital_capacities[i]
for j in range(10):
    problem += lpSum([patient_to_hospital[(i, j)] for i in range(3)]) == 1

# ⑤問題を解く
problem.solve()

# ⑥結果を出力する
for i in range(3):
    for j in range(10):
        if value(patient_to_hospital[(i, j)]) == 1:
            print("Patient {} is assigned to Hospital {}".format(j+1, i+1))

①問題を定義する

最適化問題を定義しています。

問題の名前は “Hospital Patient Assignment Problem” で、最小化問題として設定されています。

②患者がどの病院に割り当てられるかを決定する変数を定義する

患者がどの病院に割り当てられるかを決定する変数を定義しています。

この変数は、患者と病院のインデックスの組み合わせのリストとして指定されており、バイナリ変数として定義されています。

この変数が1の場合、患者がその病院に割り当てられたことを示します。

③目的関数を設定する

目的関数を設定しています。

この問題の目的は、患者を割り当てるために必要なコストを最小化することです。

ここで、各患者と病院の組み合わせに対するコストが定義されており、それらの積の和が目的関数として定義されています。

④制約条件を設定する

制約条件を設定しています。

病院の収容能力を超えないように、各病院に割り当てられる患者の数を制限しています。

また、各患者は1つの病院にしか割り当てられないように、患者ごとに制約条件を設定しています。

⑤問題を解く

問題を解くために、PuLPのsolve関数を呼び出しています。

⑥結果を出力する

各患者がどの病院に割り当てられたかを表示しています。

各患者に対して、割り当てられた病院の番号が表示されます。

実行結果は以下の通りです。

[実行結果]

Patient 1 is assigned to Hospital 1
Patient 3 is assigned to Hospital 1
Patient 4 is assigned to Hospital 1
Patient 6 is assigned to Hospital 1
Patient 7 is assigned to Hospital 1
Patient 2 is assigned to Hospital 2
Patient 5 is assigned to Hospital 2
Patient 8 is assigned to Hospital 3
Patient 9 is assigned to Hospital 3
Patient 10 is assigned to Hospital 3

１つ目の病院は5人までしか受け入れることができるため、患者1, 3, 4, 6, 7が病院1に割り当てられました。

同様に、病院2は7人まで、病院3は3人までしか受け入れることができないため、患者2と5は病院2に、患者8、9、10は病院3に割り当てられました。

生産最適化

ある工場で、3つの製品A,B,Cを生産することを考えます。

それぞれの製品は、以下のような生産時間、生産量制限、利益が決まっています。

その他の条件は以下の通りです。

🔹工場の生産時間は1日8時間まで。
🔹製品は最低1つ以上生産する必要がある。

これらの制約条件下で、利益を最大化するように各製品の生産量を決定してください。

解法・ソースコード

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
30

from pulp import *

# ①問題の定義
prob = LpProblem(name="factory_production", sense=LpMaximize)

# ②変数の定義
A = LpVariable(name="A", lowBound=0, cat="Integer")
B = LpVariable(name="B", lowBound=0, cat="Integer")
C = LpVariable(name="C", lowBound=0, cat="Integer")

# ③目的関数の定義
profit = 5*A + 3*B + 7*C
prob += profit

# ④制約条件の定義
prob += A*2 + B*1 + C*3 <= 8  # 1日8時間まで
prob += A <= 2  # 製品Aの生産量制限
prob += B <= 3  # 製品Bの生産量制限
prob += C <= 1  # 製品Cの生産量制限
prob += A + B + C >= 1  # 製品は最低1つ以上生産する必要がある

# ⑤最適化の実行
status = prob.solve()

# ⑥結果の表示
print(f"Status: {LpStatus[status]}")
print(f"Optimal Solution: {value(prob.objective)}")
print(f"Production of A: {A.varValue}")
print(f"Production of B: {B.varValue}")
print(f"Production of C: {C.varValue}")

①問題の定義

問題のインスタンスを作成します。

この問題は、目的関数を最大化することを目的としています。

②変数の定義

LpVariable 関数を使用して、変数A、B、Cを定義しています。

これらは、それぞれ製品A、B、Cの生産量を表しています。これらの変数は、非負の整数値をとります。

③目的関数の定義

profit = 5A + 3B + 7*Cは、利益を表す目的関数を定義しています。

④制約条件の定義

制約条件を設定しています。

例えば、prob += A2 + B1 + C*3 <= 8は、1日あたり8時間までしか生産できないという制約を表しています。

prob += A <= 2、prob += B <= 3、prob += C <= 1は、それぞれ製品A、B、Cの生産量制限を表しています。

また、prob += A + B + C >= 1は、製品を最低1つ以上生産する必要があるという制約を表しています。

⑤最適化の実行

status = prob.solve()は、最適化を実行しています。

⑥結果の表示

print 関数を使用して、最適化の結果を表示しています。

LpStatus[status]は、最適化の状態を表します。

value(prob.objective)は、目的関数の最適値を表します。

A.varValue、B.varValue、C.varValueは、それぞれ製品A、B、Cの最適な生産量を表しています。

上記のコードを実行すると、以下のように最適解が得られます。

[実行結果]

Status: Optimal
Optimal Solution: 21.0
Production of A: 1.0
Production of B: 3.0
Production of C: 1.0

製品Aを1個、製品Bを3個、製品Cを1個生産すれば、利益を最大化することができることがわかりました。

最大利益は21(千円)となります。

ナップサック問題

PuLPを使用してナップサック問題を解いてみます。

例題:

🔹ナップサックの容量：15
🔹商品A: 価値10, 重さ5
🔹商品B: 価値12, 重さ6
🔹商品C: 価値8, 重さ3
🔹商品D: 価値15, 重さ7
🔹商品E: 価値4, 重さ2

このナップサック問題では、15の容量を持つナップサックに、価値と重さが異なる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
30

from pulp import *

# ①問題を定義する
prob = LpProblem("Knapsack Problem", LpMaximize)

# ②商品の価値と重量を定義する
items = {
    "A": {"value": 10, "weight": 5},
    "B": {"value": 12, "weight": 6},
    "C": {"value": 8, "weight": 3},
    "D": {"value": 15, "weight": 7},
    "E": {"value": 4, "weight": 2}
}

# ③変数を定義する
item_vars = LpVariable.dicts("Item", items.keys(), lowBound=0, cat='Binary')

# ④目的関数を定義する
prob += lpSum([items[i]["value"] * item_vars[i] for i in items])

# ⑤制約条件を定義する
prob += lpSum([items[i]["weight"] * item_vars[i] for i in items]) <= 15

# ⑥問題を解く
prob.solve()

# ⑦結果を表示する
print("Optimal Solution: ", value(prob.objective))
for i in items:
    print(i, ": ", value(item_vars[i]))

①問題を定義する

問題を定義し、最大化問題であることを指定します。

“Knapsack Problem”は問題名であり、必須ではありませんが、問題が複雑になる場合、有用であることがあります。

②商品の価値と重量を定義する

問題に必要なデータを定義します。各商品には価値と重量があります。

この例では、5つの商品を定義しています。

③変数を定義する

商品を選択するための変数を定義します。

LpVariable.dictsを使用して、”Item”という名前の変数を作成します。

items.keys()は、変数の名前を商品名（A、B、C、D、E）に設定します。

lowBound=0は、変数が0以上であることを指定します。

cat=’Binary’は、変数がバイナリ変数であることを指定します。

これは、商品が選択されたかどうかを示すために0または1で設定されることを意味します。

④目的関数を定義する

目的関数を定義します。

この例では、商品の選択によって生じる価値の総和を最大化します。

lpSumを使用して、すべての商品の価値を変数に乗じ、それらを合計します。

⑤制約条件を定義する

制約条件を定義します。

この例では、ナップサックの容量を制限しています。

lpSumを使用して、すべての商品の重量を変数に乗じ、それらを合計し、合計が15以下であることを指定します。

⑥問題を解く

PuLPを使って問題を解きます。

⑦結果を表示する

最適解を表示します。

最適解は、value(prob.objective)を使用して得られます。

問題に使用された各変数の値を表示するために、forループが使用されています。

prob.variables()はすべての変数を返します。

各変数の名前と値を表示するには、 i.nameと i.varValueを使用します。

コードを実行すると下記のような実行結果になります。

[実行結果]

Optimal Solution:  33.0
A :  1.0
B :  0.0
C :  1.0
D :  1.0
E :  0.0

この結果から、最適な解は、商品A、商品C、および商品Dをナップサックに詰め込み、価値を合計33にすることです。

商品BとEは選択されなかったことがわかります。

旅行最適化

旅行に関する最適化問題の例を考えます。

3つの都市を訪れる旅行者が、最短距離の経路でそれぞれの都市を訪れるようにルートを決めるのが目的です。

解法・ソースコード

Pythonの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
30
31
32
33
34
35
36
37

import pulp

# 問題の定義
problem = pulp.LpProblem('Traveling Problem', pulp.LpMinimize)

# 都市の座標 (x, y)
cities = {
    'City 1': (20, 50),
    'City 2': (40, 20),
    'City 3': (60, 70)
}

# 距離を計算する関数
def distance(city1, city2):
    return ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5

# 変数の定義
routes = pulp.LpVariable.dicts('Route', ((i, j) for i in cities for j in cities if i!=j), cat='Binary')

# 目的関数の定義
problem += pulp.lpSum([routes[(i, j)] * distance(cities[i], cities[j]) for i in cities for j in cities if i!=j])

# 制約条件の定義
for i in cities:
    problem += pulp.lpSum([routes[(i, j)] for j in cities if i!=j]) == 1

for j in cities:
    problem += pulp.lpSum([routes[(i, j)] for i in cities if i!=j]) == 1

# 解く
problem.solve()

# 結果を表示
print("最短距離: ", pulp.value(problem.objective))
for v in problem.variables():
    if v.varValue == 1:
        print(v.name)

各都市を訪れるルートをバイナリ変数で表現し、目的関数には各ルートの距離を加算します。

制約条件として、各都市を正確に1回訪れなければならず、同じ都市には戻れないことを設定します。

最後に、PuLPを使用して問題を解決し、最適なルートを表示します。

上記のコードを実行すると、以下のような結果が表示されます。

[実行結果]

最短距離:  134.6285203759807
Route_('City_1',_'City_3')
Route_('City_2',_'City_1')
Route_('City_3',_'City_2')

都市1、都市3、都市2の順で訪れると、最短距離が134.62であることを示しています。

また、この結果には、各都市を訪れるためのルートが表示されています。

例えば、’Route_(‘City_1’,_’City_3’)’は、都市1から都市3へのルートを示しています。

人員スケジューリング問題

人員スケジューリング最適化の例題として、従業員のシフトスケジュールを最適化する問題を考えてみましょう。

次のような条件を設定します。

🔹従業員は、1日あたり8時間を超えて働くことはできません。
🔹従業員が、1週間あたりに働くことができる最大時間数はあらかじめ決まっています。
🔹従業員は、週に1日は必ず休む必要があります。

解法・ソースコード

この問題を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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

from pulp import *

# ①従業員のリスト
employees = ['Alice', 'Bob', 'Charlie', 'David', 'Tom', 'Nancy']

# ②日付のリスト
days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']

# ③必要な従業員数
shift_requirements = {
    'Monday': 2,
    'Tuesday': 2,
    'Wednesday': 3,
    'Thursday': 2,
    'Friday': 3,
    'Saturday': 3,
    'Sunday': 1
}

# ④各従業員が働く最大時間数
work_hours = {
    'Alice': 40,
    'Bob': 40,
    'Charlie': 40,
    'David': 40,
    'Tom': 40,
    'Nancy': 40
}

# ⑤問題を定義する
problem = LpProblem('Shift_Scheduling', LpMinimize)

# ⑥変数を定義する
shifts = LpVariable.dicts('shifts', (employees, days), 0, 1, LpInteger)

# ⑦目的関数を定義する
problem += lpSum([shifts[e][d] for e in employees for d in days])

# ⑧制約条件を追加する
# 各従業員は週に1日は必ず休む
for e in employees:
    problem += lpSum([shifts[e][d] for d in days]) >= 1

# 各日のシフトには、必要な人数が割り当てられる必要がある
for d in days:
    problem += lpSum([shifts[e][d] for e in employees]) == shift_requirements[d]

# 各従業員は1日に8時間までしか勤務できない
for e in employees:
    problem += lpSum([shifts[e][d] for d in days]) <= 8

# 各従業員が1週間に働くことができる時間数
for e in employees:
    problem += lpSum([shifts[e][d] for d in days]) * 8 <= work_hours[e]

# ⑨問題を解く
status = problem.solve()

# ⑩解を表示する
print(f'Solution status: {LpStatus[status]}')

for d in days:
    print(f'\n{d}')
    for e in employees:
        if value(shifts[e][d]) == 1:
            print(f'  {e} is working.')
        else:
            print(f'  {e} is off.')

①従業員のリストを作成しています。

②日付のリストを作成しています。

③各日に必要な従業員数を格納する辞書を作成しています。

④各従業員が働くことができる最大時間数を格納する辞書を作成しています。

⑤問題を定義するために、PuLPでLpProblemオブジェクトを作成しています。
　第一引数には問題の名前を指定し、第二引数には最小化するのか、最大化するのかを指定します。

⑥変数を定義しています。
　shiftsという名前のLpVariableオブジェクトを作成します。
　このオブジェクトはemployeesとdaysの2つのインデックスを持ちます。
　変数は、0から1の整数値を取ります。

⑦目的関数を定義しています。
　目的関数は、すべての従業員と日に対して、その従業員がその日に働く場合に1、そうでない場合に0を取るshifts変数の総和です。
　この目的関数は、スケジュールの総コストを最小限に抑えるように最適化されます。

⑧制約条件を追加しています。
　まず、各従業員が週に1日は必ず休むようにします。
　次に、各日のシフトには、必要な人数が割り当てられる必要があるようにします。
　各従業員は1日に8時間までしか勤務できないようにし、各従業員が1週間に働くことができる時間数を制限します。

⑨問題を解くために、PuLPのsolveメソッドを呼び出します。
　解決策が見つかった場合は、status変数にSolvedという文字列が格納されます。
　見つからなかった場合は、Infeasibleという文字列が格納されます。

⑩解を表示するために、各日について、各従業員が働いているかどうかを示す出力を行っています。
　これは、shifts変数の値が1の場合にその従業員が働いていることを示します。
　それ以外の場合は、その従業員が休みであることを示します。

実行結果は以下のようになります。

[実行結果]

Solution status: Optimal

Monday
  Alice is working.
  Bob is off.
  Charlie is off.
  David is off.
  Tom is working.
  Nancy is off.

Tuesday
  Alice is off.
  Bob is working.
  Charlie is off.
  David is off.
  Tom is off.
  Nancy is working.

Wednesday
  Alice is working.
  Bob is working.
  Charlie is working.
  David is off.
  Tom is off.
  Nancy is off.

Thursday
  Alice is off.
  Bob is off.
  Charlie is off.
  David is working.
  Tom is working.
  Nancy is off.

Friday
  Alice is off.
  Bob is working.
  Charlie is working.
  David is working.
  Tom is off.
  Nancy is off.

Saturday
  Alice is off.
  Bob is off.
  Charlie is working.
  David is working.
  Tom is off.
  Nancy is working.

Sunday
  Alice is off.
  Bob is off.
  Charlie is off.
  David is off.
  Tom is working.
  Nancy is off.

各曜日に誰が働けばよいのかシフトスケジュールを組むことができました。