敵地輸送コスト最適化

敵地での輸送コスト最小化問題を考えてみましょう。

具体的には、敵地にある複数の拠点から自国の拠点への輸送を最適化する問題です。

以下に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

from pulp import *

# 問題の定義
problem = LpProblem("War Transportation Problem", LpMinimize)

# 変数の定義
base_names = ["Base1", "Base2", "Base3"]  # 自国の拠点
enemy_bases = ["Enemy1", "Enemy2", "Enemy3"]  # 敵地の拠点

# 輸送量変数
transport_vars = LpVariable.dicts("Transport", (base_names, enemy_bases), lowBound=0, cat="Integer")

# 輸送コスト辞書の定義
transport_cost_dict = {
    "Base1": {
        "Enemy1": 10,
        "Enemy2": 8,
        "Enemy3": 6
    },
    "Base2": {
        "Enemy1": 9,
        "Enemy2": 7,
        "Enemy3": 5
    },
    "Base3": {
        "Enemy1": 11,
        "Enemy2": 9,
        "Enemy3": 7
    }
}

# 目的関数の定義
problem += lpSum(transport_vars[base][enemy] * transport_cost_dict[base][enemy]
                 for base in base_names for enemy in enemy_bases)

# 制約条件の定義
# 各自国の拠点からの輸送量は、自国の拠点の供給量以下である必要がある
supply_dict = {"Base1": 100, "Base2": 150, "Base3": 200}
for base in base_names:
    problem += lpSum(transport_vars[base][enemy] for enemy in enemy_bases) <= supply_dict[base]

# 各敵地の拠点への輸送量は、敵地の拠点の需要量以上である必要がある
demand_dict = {"Enemy1": 80, "Enemy2": 120, "Enemy3": 100}
for enemy in enemy_bases:
    problem += lpSum(transport_vars[base][enemy] for base in base_names) >= demand_dict[enemy]

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

# 結果の出力
print("Optimal Solution:")
for base in base_names:
    for enemy in enemy_bases:
        print(f"Transport from {base} to {enemy}: {transport_vars[base][enemy].varValue}")

このコードでは、自国の拠点から敵地の拠点への輸送量を最小化するように最適化問題を設定しています。

自国の拠点と敵地の拠点の数、各拠点の供給量と需要量、および輸送コストを適切に設定する必要があります。

上記のコードを適切に実行することで、最適な輸送計画が得られ、各自国の拠点から敵地の拠点への輸送量が表示されます。

[実行結果]

Optimal Solution:
Transport from Base1 to Enemy1: 30.0
Transport from Base1 to Enemy2: 0.0
Transport from Base1 to Enemy3: 70.0
Transport from Base2 to Enemy1: 0.0
Transport from Base2 to Enemy2: 120.0
Transport from Base2 to Enemy3: 30.0
Transport from Base3 to Enemy1: 50.0
Transport from Base3 to Enemy2: 0.0
Transport from Base3 to Enemy3: 0.0

各自国の拠点から敵地の拠点への輸送量が表示されています。

例えば、”Transport from Base1 to Enemy1: 30.0” は、自国の Base1 から敵地の Enemy1 への輸送量が30であることを示しています。

同様に、他の組み合わせも表示されています。

目的関数である輸送コストを最小化するために、各自国の拠点から敵地の拠点への輸送量が適切に決定されました。

制約条件（自国の拠点の供給量と敵地の拠点の需要量）も満たされています。

最適解を基にしたこの輸送計画は、輸送コストを最小化しながら効率的な物資補給を実現するために活用できます。

ダイエット 最適化

ダイエットに関する最適化問題として、ある人が目標とする栄養素やカロリー摂取量を達成するための最小費用を求める問題を考えます。

この問題は、食品の栄養価と価格が与えられた場合、各食品をどの程度摂取するかを決定することによって解決できます。

解法

以下は、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

from pulp import *

# 栄養価と価格のデータ
food = ['apple', 'banana', 'beef', 'chicken', 'milk']
cost = {'apple': 0.5, 'banana': 0.25, 'beef': 2.5, 'chicken': 1.5, 'milk': 0.4}
calories = {'apple': 50, 'banana': 100, 'beef': 250, 'chicken': 150, 'milk': 120}
protein = {'apple': 0.5, 'banana': 1.0, 'beef': 25, 'chicken': 30, 'milk': 8}
fat = {'apple': 0.2, 'banana': 0.4, 'beef': 18, 'chicken': 5, 'milk': 5}
carbs = {'apple': 13, 'banana': 27, 'beef': 0, 'chicken': 0, 'milk': 12}

# 目標とする栄養素の量
target_calories = 1500
target_protein = 100
target_fat = 50
target_carbs = 200

# 問題を定義する
prob = LpProblem("diet problem", LpMinimize)

# 各食品の摂取量を表す変数を定義する
food_vars = LpVariable.dicts("food", food, lowBound=0, cat='Continuous')

# 目的関数を定義する
prob += lpSum([cost[f] * food_vars[f] for f in food]), "Total Cost"

# 制約条件を定義する
prob += lpSum([calories[f] * food_vars[f] for f in food]) >= target_calories, "Calories Minimum"
prob += lpSum([calories[f] * food_vars[f] for f in food]) <= target_calories + 100, "Calories Maximum"
prob += lpSum([protein[f] * food_vars[f] for f in food]) >= target_protein, "Protein Minimum"
prob += lpSum([fat[f] * food_vars[f] for f in food]) >= target_fat, "Fat Minimum"
prob += lpSum([carbs[f] * food_vars[f] for f in food]) >= target_carbs, "Carbs Minimum"

# 問題を解く
prob.solve()

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

この例では、最小化したい変数を cost[f] * food_vars[f] で表し、目的関数は lpSum([cost[f] * food_vars[f] for f in food]) として定義されています。

制約条件は、それぞれの栄養素の最小値を表す不等式制約として設定されています。

また、各変数の下限は0に、上限は指定されていません。

最適化問題をPuLPで解いた結果、各食品の摂取量が計算され、総費用も表示されます。

これにより、与えられた栄養目標を達成する最小費用が求められます。

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

[実行結果]

Status: Optimal
food_apple = 0.0
food_banana = 2.745098
food_beef = 0.0
food_chicken = 0.44444444
food_milk = 10.490196
Total Cost = 5.54901956

Status: Optimalという結果が得られたことから、問題が最適化されたことがわかります。

さらにバナナを2.74、鶏肉を0.44、牛乳を10.49摂取すると、目標のカロリー、タンパク質、脂質、炭水化物を達成することができ、総費用は5.549ドルになることを示しています。

税金 最適化

税金に関する最適化問題の例として、税金の申告を行う個人が受ける税金控除の種類や額を最適に選択する問題を考えてみましょう。

具体的には、以下のような問題設定を考えます。

ある個人が申告する税金の総額を $T$ とします。

この個人は、以下のような種類の税金控除を受けることができます。

🔹住宅ローン控除: 最大で $H$ 円までの住宅ローンの利息を控除できる。
🔹教育費控除: 最大で $E$ 円までの教育費を控除できる。
🔹寄附金控除: 寄附金のうち、最大で $D$ 円までを控除できる。

この個人は、これらの控除を組み合わせて、総支払額である $T$ 円を最小限に抑えたいと考えています。

解法

最小限の支払額を求めるために、PuLPを用いた線形計画法を適用してみましょう。

数学モデルを以下に示します。

【変数】

🔹$h$: 住宅ローン控除額
🔹$e$: 教育費控除額
🔹$d$: 寄附金控除額

【目的関数】

🔹$\min$ $T - (h+e+d)$

【制約条件】

🔹住宅ローン控除は $H$ 円以内でなければならない：$h \leq H$
🔹教育費控除は $E$ 円以内でなければならない：$e \leq E$
🔹寄附金控除は $D$ 円以内でなければならない：$d \leq D$
🔹総控除額は総支払額 $T$ 以下でなければならない：$h+e+d \leq T$

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

from pulp import *

# 最大の住宅ローン控除額
H = 500000

# 最大の教育費控除額
E = 100000

# 最大の寄附金控除額
D = 30000

# 総支払額
T = 1000000

# 問題を定義
prob = LpProblem("tax_optimization", LpMinimize)

# 変数を定義
h = LpVariable("h", 0, H)
e = LpVariable("e", 0, E)
d = LpVariable("d", 0, D)

# 目的関数を定義
prob += T - (h + e + d)

# 制約条件を定義
prob += h <= H
prob += e <= E
prob += d <= D
prob += h + e + d <= T

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

# 結果を表示
print(f"Status: {LpStatus[status]}")
print(f"Optimal value: {value(prob.objective)}")
print(f"h: {value(h.value())}, e: {value(e.value())}, d: {value(d.value())}")

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

[実行結果]

Status: Optimal
Optimal value: 370000.0
h: 500000.0, e: 100000.0, d: 30000.0

この結果から、総支払額 $T$ が $1000000$ 円の場合、最小限の支払額は $370000$ 円であり、そのうち $500000$ 円が住宅ローン控除、$100000$ 円が教育費控除、$30000$ 円が寄附金控除であることがわかります。

給食 最適化

給食に関する最適化問題の例として、以下の問題を考えてみます。

ある学校では、毎日ランチとしてA,B,Cの3種類のメニューから1つを提供します。

各メニューには以下のような栄養素が含まれます。

また、各クラスには生徒が20名ずつ在籍しており、1日に必要な栄養素の量は以下の通りとします。

このとき、1日の給食で提供する各メニューの量を決定し、必要な栄養素を満たすことができる最小のコストを求める最適化問題を考えます。

解法

下記のコードでは、変数a,b,cをそれぞれメニューA,B,Cの提供量とし、目的関数 2a + 3b + 4c を最小化するように設定しています。

制約条件は、各栄養素の必要量を満たすように設定しています。

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

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

import pulp

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

# 変数の定義
a = pulp.LpVariable('a', lowBound=0, cat='Continuous')
b = pulp.LpVariable('b', lowBound=0, cat='Continuous')
c = pulp.LpVariable('c', lowBound=0, cat='Continuous')

# 目的関数の定義
problem += 2 * a + 3 * b + 4 * c

# 制約条件の定義
problem += 700 * a + 600 * b + 800 * c >= 10000
problem += 30 * a + 25 * b + 20 * c >= 500
problem += 10 * a + 15 * b + 20 * c >= 200
problem += 50 * a + 40 * b + 60 * c >= 700

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

# 解の出力
print('Result:')
print(f'a: {pulp.value(a)}')
print(f'b: {pulp.value(b)}')
print(f'c: {pulp.value(c)}')
print(f'Minimum Cost: {pulp.value(problem.objective)}')

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

[実行結果]

Result:
a: 15.0
b: 0.0
c: 2.5
Minimum Cost: 40.0

この結果から、メニューAを15人分、メニューBを0人分、メニューCを2.5人分提供することで、必要な栄養素を満たすことができ、最小のコストは40であることがわかります。

おにごっこ最適化

おにごっこに関する最適化問題の例として、5人でおにごっこをする場合、どのように逃げた方が最適か？という問題を考えてみます。

解法

以下は、PuLPを用いた解法です。

まず、必要なライブラリをインポートします。

1

from pulp import *

次に、問題の定式化を行います。この問題では、以下のようになります。

🔹変数
　x_i (i = 1, 2, …, 5): i番目の逃げる場所に行くかどうか (1: 逃げる, 0: 逃げない)
🔹目的関数
　逃げる人数の最大化
🔹制約条件
　逃げる人数は4人以下

これをPuLPで表現すると、以下のようになります。

1
2
3
4
5
6
7
8
9
10
11

# 問題の定義
prob = LpProblem('Onigokko', LpMaximize)

# 変数の定義
x = [LpVariable('x{}'.format(i), cat='Binary') for i in range(1, 6)]

# 目的関数の定義
prob += lpSum(x)

# 制約条件の定義
prob += lpSum(x) <= 4

ここで、lpSum()はPuLPが提供する関数で、与えられたリストの要素の和を計算します。

制約条件は、<=で表現しています。

次に、PuLPを使って求解を行います。

1
2

# 求解
status = prob.solve()

このようにして、求解が終了しました。最後に、結果を表示してみます。

1
2
3
4
5
6

# 結果を表示
print('Status:', LpStatus[status])
for i in range(1, 6):
    print('x{} = {}'.format(i, int(value(x[i - 1]))))
print('Optimal value:', value(prob.objective))

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

[実行結果]

Status: Optimal
x1 = 1
x2 = 1
x3 = 1
x4 = 1
x5 = 0
Optimal value: 4.0

結果から、最適解が得られ、1番目、2番目、3番目、4番目の場所に逃げることが最適解になることが分かりました。

また、逃げる人数は4人であることも分かります。

出店最適化

あなたはピザ店を経営しており、新しい店舗を出店することにしました。

出店する場所は3つあり、それぞれの場所には以下のような特徴があります。

🔹場所1：人口密度が高いが、家賃が高い
🔹場所2：人口密度が低いが、家賃が安い
🔹場所3：人口密度と家賃のバランスがとれている

あなたは、出店する店舗の場所を最適化することにしました。

以下の制約条件を考慮して、各場所の評価スコアを計算し、最も評価スコアが高い場所に店舗を出店することにしました。

🔹店舗の出店数は1つ
🔹店舗の出店費用はすべて同じ
🔹各場所には、人口密度、家賃、および場所による固有の評価スコアがあります。
　評価スコアは0から100までのスケールで測定されます。
🔹人口密度が高い場所ほど評価スコアが高くなるが、家賃が高い場合は低くなる。
🔹家賃が安い場所ほど評価スコアが高くなるが、人口密度が低い場合は低くなる。
🔹人口密度と家賃のバランスがとれている場所ほど評価スコアが高くなる。

各場所の人口密度、家賃、および場所による固有の評価スコアは以下の通りとします。

解法

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

# ①必要なライブラリをインポート
from pulp import *

# ②問題を定義する
prob = LpProblem('出店最適化', LpMaximize)

# ③変数を定義する
x1 = LpVariable('場所1', 0, 1, LpInteger)
x2 = LpVariable('場所2', 0, 1, LpInteger)
x3 = LpVariable('場所3', 0, 1, LpInteger)

# ④目的関数を定義する
prob += 70 * x1 + 50 * x2 + 80 * x3

# ⑤制約条件を定義する
prob += x1 + x2 + x3 == 1
prob += 90 * x1 + 50 * x2 + 70 * x3 <= 100
prob += 100 * x1 + 50 * x2 + 70 * x3 <= 100

# ⑥最適化を実行する
status = prob.solve()

# ⑦結果を表示する
print('出店する場所:', end=' ')
if x1.value() == 1:
    print('場所1')
elif x2.value() == 1:
    print('場所2')
elif x3.value() == 1:
    print('場所3')

print('最適な評価スコア:', value(prob.objective))

①必要なライブラリをインポート

PuLPを使うために必要なライブラリをインポートしています。

②問題を定義する

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

第一引数には問題の名前を指定し、第二引数には最大化か最小化かを指定します。

ここでは「出店最適化」という名前で最大化問題を定義しています。

③変数を定義する

LpVariable関数を使って変数を定義します。

第一引数には変数の名前を指定し、第二引数には変数の下限値、第三引数には変数の上限値、第四引数には変数の型（整数値か連続値か）を指定します。

ここでは、場所1、場所2、場所3の3つの変数を定義しています。各変数は0または1の整数値をとります。

④目的関数を定義する

目的関数を定義します。

ここでは、ピザ店を出店する場所によって得られる評価スコアを最大化するように設定しています。

場所1に出店すると70点、場所2に出店すると50点、場所3に出店すると80点の評価スコアが得られると仮定しています。

⑤制約条件を定義する

制約条件を定義します。ここでは、以下の条件を設定しています。

🔹出店する場所は1つだけである。
🔹場所1、場所2、場所3のそれぞれで得られる評価スコアが、100点以下である。

⑥最適化を実行する

LpProblem関数で定義した問題を解くために、solveメソッドを呼び出します。

解を求めるアルゴリズムはPuLPが自動的に選択します。

⑦結果を表示する

解の値を出力します。value関数を使って目的関数の値を取得しています。

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

[実行結果]

出店する場所: 場所3
最適な評価スコア: 80.0

この結果から、ピザ店を出店する最適な場所は場所3であり、評価スコアは80点であることが分かります。

今回の例では、ピザ店を出店する場所を最適化する問題を定義し、PuLPを使って解くことで、最適な出店場所とそのときの評価スコアを求めました。

薬の処方

薬の処方に関する最適化問題を考えてみます。

例えば、ある患者に対して複数の薬剤が処方される場合、以下のような問題を最適化することができます。

目的:

　🔹与えられた症状や疾患に最も効果的な薬剤の組み合わせを見つける。

制約条件:

　🔹処方された薬剤の総量が過剰でないこと。
　🔹薬剤の相互作用がないこと。
　🔹薬剤の副作用を最小化すること。
　🔹患者のアレルギーや過去の治療経験を考慮すること。

解法

この問題をPuLPを使って解くには、以下のような手順を踏むことができます。

1. 処方された薬剤を変数として定義する。

2. 目的関数を定義する。

　薬剤の総効果を最大化します。

3. 制約条件を定義する。

　薬剤の総量が過剰でないこと、薬剤の相互作用がないこと、薬剤の副作用を最小化すること、患者のアレルギーや過去の治療経験を考慮することなどが挙げられます。

4. PuLPを使って問題を解く。

5. 解を出力する。

　どの薬剤をどの程度処方するかを表示します。

以下は、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

from pulp import *

# 変数の定義
x1 = LpVariable("x1", lowBound=0)
x2 = LpVariable("x2", lowBound=0)
x3 = LpVariable("x3", lowBound=0)

# 目的関数の定義
prob = LpProblem("Prescription", LpMaximize)
prob += 2*x1 + 3*x2 + 4*x3

# 制約条件の定義
prob += x1 + x2 + x3 <= 1000
prob += 0.5 * x1 + x2 + x3 <= 800
prob += x1 + x2 + 2 * x3 <= 1500

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

# 結果の出力
print("Status:", LpStatus[status])
print("Optimal Solution:")
for v in prob.variables():
    print(v.name, "=", v.varValue)
print("Optimal Value =", value(prob.objective))

この例では、薬剤x1、x2、x3の各総量が制限内で最も効果的な組み合わせを求めることが目的となります。

変数x1、x2、x3はそれぞれ、薬剤x1、x2、x3の総量を表しています。

目的関数は、薬剤の総効果を最大化するように定義されています。

制約条件は、各薬剤の総量が規定の制限内に収まるように設定されています。

この例では、PuLPを使って簡単に最適な薬剤の組み合わせを求めることができます。

実際の医療現場では、このような最適化技術が、医師の意思決定を支援するツールとして役立つことが期待されています。

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

[実行結果]

Status: Optimal
Optimal Solution:
x1 = 0.0
x2 = 100.0
x3 = 700.0
Optimal Value = 3100.0

これは、薬剤x1を0単位、薬剤x2を100単位、薬剤x3を700単位処方することで、疾患に対する最大の効果が得られることを示しています。

また、最適な薬剤の組み合わせによって、総効果は3100となります。

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

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

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

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

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