為替ヘッジ問題

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.

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

プロセス最適化問題

【問題】
ある化学工場では、原料 A, B, C, D を混合して製品を作成するプロセスがあります。

原料の価格は以下の通りです。

🔹A: 30 円/kg
🔹B: 20 円/kg
🔹C: 10 円/kg
🔹D: 5 円/kg

製品の販売価格は 50 円/単位です。また、原料の供給量は以下の通りです。

🔹A: 200 kg
🔹B: 150 kg
🔹C: 100 kg
🔹D: 50 kg

各原料を最大限に使用することで得られる利益を求めてください。

解法

この問題は線形計画法を用いて解くことができます。以下は、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('Process Optimization', LpMaximize)

# ②変数の定義
A = LpVariable('A', lowBound=0, upBound=200, cat='Continuous')
B = LpVariable('B', lowBound=0, upBound=150, cat='Continuous')
C = LpVariable('C', lowBound=0, upBound=100, cat='Continuous')
D = LpVariable('D', lowBound=0, upBound=50, cat='Continuous')

# ③目的関数の定義
prob += 50 * (A + B + C + D) - 30 * A - 20 * B - 10 * C - 5 * D

# ④制約条件の定義
prob += A + B + C + D <= 450
prob += A <= 200
prob += B <= 150
prob += C <= 100
prob += D <= 50

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

# ⑥結果の出力
print('最大利益:', value(prob.objective))
print('原料 A:', value(A))
print('原料 B:', value(B))
print('原料 C:', value(C))
print('原料 D:', value(D))

①問題の定義

PuLP を使う場合、まず LpProblem オブジェクトを作成します。

第一引数に問題の名前、第二引数に最適化の種類を指定します。

この場合は最大化問題なので LpMaximize を指定しています。

②変数の定義

最適化する変数を定義します。

ここでは、原料 A, B, C, D の使用量をそれぞれ LpVariable オブジェクトとして定義しています。

第一引数に変数名を指定し、lowBound、upBound 引数で変数の下限値、上限値を指定します。

cat 引数では変数の種類を指定します。ここでは連続変数として定義しています。

③目的関数の定義

最大化したい目的関数を定義します。

ここでは、総原価が最小となるようにするため、原料 A, B, C, D の使用量をそれぞれ掛け合わせ、総原価を計算しています。

④制約条件の定義

最適化の制約条件を定義します。

ここでは、使用する原料の量がそれぞれの上限値を超えないようにするため、制約条件を設けています。

⑤問題の解決

PuLP を使って問題を解くには、solve() メソッドを呼び出します。

⑥結果の出力

最後に、value() 関数を使って、各変数の最適解を取得し、出力しています

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

[実行結果]

最大利益: 13750.0
原料 A: 150.0
原料 B: 150.0
原料 C: 100.0
原料 D: 50.0

各原料を最大限に使用することで、最大利益 13,750 円を得られるということが確認できました。

広告最適化問題

広告最適化問題を解決するために、PuLPを使用して線形計画問題にモデル化することができます。

あるWebサイトの広告枠に表示する広告を複数の広告主から選ぶ場合を考えます。

各広告主は、広告をクリックするユーザー数に応じて支払う広告費が異なります。

広告費の合計を最小化しながら、クリック率を最大化するように広告を選択することが目的です。

以下は、この問題を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

import pulp

# 問題設定
ads = ["A", "B", "C", "D"]
click_rates = {"A": 0.02, "B": 0.03, "C": 0.01, "D": 0.04}
costs = {"A": 1000, "B": 1200, "C": 800, "D": 1500}
max_budget = 5000

# モデルの作成
prob = pulp.LpProblem("Ad Optimization", pulp.LpMaximize)

# 変数の定義
x = pulp.LpVariable.dicts("ads", ads, lowBound=0, cat="Integer")

# 目的関数の定義
prob += pulp.lpSum([click_rates[i] * x[i] for i in ads])

# 制約条件の定義
prob += pulp.lpSum([costs[i] * x[i] for i in ads]) <= max_budget
prob += pulp.lpSum([x[i] for i in ads]) == 1

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

# 結果の出力
for i in ads:
    print(f"Ad {i}: {pulp.value(x[i])}")

この例では、pulp.LpProblem()で問題を設定し、pulp.LpVariable.dicts()で広告選択の変数を定義しています。

目的関数は、クリック率の合計を最大化するように設定し、制約条件は、広告費の合計が最大予算を超えないように設定しています。

prob.solve()で最適化を実行し、結果を出力しています。

このコードを実行すると、各広告の選択率が出力されます。

[実行結果]

Ad A: 0.0
Ad B: 0.0
Ad C: 0.0
Ad D: 1.0

この結果から、広告Dを選択することが最適であることがわかりました。

ナンプレ問題

下記のナンプレ問題を、PuLPを使って解いて下さい。

5 3 0 0 7 0 0 0 0 
6 0 0 1 9 5 0 0 0 
0 9 8 0 0 0 0 6 0 
8 0 0 0 6 0 0 0 3 
4 0 0 8 0 3 0 0 1 
7 0 0 0 2 0 0 0 6 
0 6 0 0 0 0 2 8 0 
0 0 0 4 1 9 0 0 5 
0 0 0 0 8 0 0 7 9

解法・ソースコード

ソースコードの構造と各部分の役割について説明します。

①問題の定義

まず、問題を定義するために pulp.LpProblem() 関数を使用しています。

この関数には、問題の名前と目的関数の種類を指定します。

ここでは、ナンプレ問題を解くために、”Sudoku Problem”という名前の問題を定義し、目的関数として pulp.LpMinimize を使用しています。

ただし、ナンプレ問題には目的関数が存在しないため、この値は問題の解法に影響しません。

②変数の定義

問題で扱う変数を定義します。

pulp.LpVariable.dicts() 関数を使用して、choices という名前の辞書を作成しています。

この辞書には、各マスに対応する9つの変数が含まれています。

つまり、choices[i][j][k] は、マス(i, j)に数字kが入っているかどうかを表す0または1の変数になります。

ここでは、cat=’Binary’という引数を指定することで、変数が0または1の整数値しかとらないようにしています。

③制約条件の定義

問題の制約条件を定義します。

各マスには1つの数字しか入らないことを表す制約条件を設定しています。

具体的には、各マスに入る数字の変数の和が1であるという条件を表しています。

④各行には1から9までの数字が1回ずつ現れる

各行には1から9までの数字が1回ずつ現れることを表す制約条件を設定しています。

⑤各列には1から9までの数字が1回ずつ現れる

④と同様に、各列には1から9までの数字が1回ずつ現れることを表す制約条件も設定しています。

⑥各3x3ブロックには1から9までの数字が1回ずつ現れる

各ブロックには1から9までの数字が1回ずつ現れることを表す制約条件も設定しています。

具体的には、各数字がブロック内のある1つのマスに現れるという条件を表しています。

各ブロックの左上のマスを(row, col)として、3x3のブロック内の各マスに対して、そのマスにnumが入っているかどうかを表す変数の和が1であるという制約条件を表しています。

⑦初期状態を設定

初期状態が与えられている場合は、その状態に合わせた制約条件も設定しています。

初期状態に数字が入っているマスに対して、そのマスに対応する変数を1に固定するという制約条件を表しています。

⑧解を求める

problem.solve() で定義した問題を解きます。

⑨解の表示

各変数がとる値を choices[row][col][num].value() で取得し、それを元に解を作成しています。

最終的には、解を二次元配列として solution に保存し、それを行ごとに表示しています。

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

import pulp

# ①問題の定義
problem = pulp.LpProblem("Sudoku Problem", pulp.LpMinimize)

# ②変数の定義
choices = pulp.LpVariable.dicts("Choice", (range(1, 10), range(1, 10), range(1, 10)), cat='Binary')

# ③制約条件の定義
# 各マスは1つの数字に限定される
for row in range(1, 10):
    for col in range(1, 10):
        problem += pulp.lpSum([choices[row][col][num] for num in range(1, 10)]) == 1

# ④各行には1から9までの数字が1回ずつ現れる
for row in range(1, 10):
    for num in range(1, 10):
        problem += pulp.lpSum([choices[row][col][num] for col in range(1, 10)]) == 1

# ⑤各列には1から9までの数字が1回ずつ現れる
for col in range(1, 10):
    for num in range(1, 10):
        problem += pulp.lpSum([choices[row][col][num] for row in range(1, 10)]) == 1

# ⑥各3x3ブロックには1から9までの数字が1回ずつ現れる
for row in range(1, 10, 3):
    for col in range(1, 10, 3):
        for num in range(1, 10):
            problem += pulp.lpSum([choices[i][j][num] for i in range(row, row + 3) for j in range(col, col + 3)]) == 1

# ⑦初期状態を設定
# ナンプレ問題の初期状態には、空きマスを0として表現します。
initial_state = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

for row in range(9):
    for col in range(9):
        if initial_state[row][col] != 0:
            problem += choices[row+1][col+1][initial_state[row][col]] == 1

# ⑧解を求める
problem.solve()

# ⑨解の表示
solution = [[0]*9 for _ in range(9)]
for row in range(1, 10):
    for col in range(1, 10):
        for num in range(1, 10):
            if choices[row][col][num].value() == 1:
                solution[row-1][col-1] = num

for row in solution:
    print(row)

このコードを実行すると、下記の結果を得ることができます。

[実行結果]

[5, 3, 4, 6, 7, 8, 9, 1, 2]
[6, 7, 2, 1, 9, 5, 3, 4, 8]
[1, 9, 8, 3, 4, 2, 5, 6, 7]
[8, 5, 9, 7, 6, 1, 4, 2, 3]
[4, 2, 6, 8, 5, 3, 7, 9, 1]
[7, 1, 3, 9, 2, 4, 8, 5, 6]
[9, 6, 1, 5, 3, 7, 2, 8, 4]
[2, 8, 7, 4, 1, 9, 6, 3, 5]
[3, 4, 5, 2, 8, 6, 1, 7, 9]

PuLPを使ってナンプレ問題を解くことができました。