生産最適化

ある工場で、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を使ってナンプレ問題を解くことができました。

巡回セールスマン問題

巡回セールスマン問題（Traveling Salesman Problem）は、すべての都市を一度だけ訪れ、最短距離で戻ってくる経路を求める問題です。

以下は、NetworkXを使用して巡回セールスマン問題を解く例です。

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

import networkx as nx
import matplotlib.pyplot as plt

# 5つの都市の座標を設定
positions = {1: (0, 0), 2: (1, 1), 3: (2, 0), 4: (3, 1), 5: (4, 0)}

# 距離を計算する関数を定義
def distance(u, v):
    x1, y1 = positions[u]
    x2, y2 = positions[v]
    return ((x1-x2)**2 + (y1-y2)**2)**0.5

# グラフを作成
G = nx.Graph()
G.add_nodes_from(positions.keys())
for u in positions:
    for v in positions:
        if u < v:
            G.add_edge(u, v, weight=distance(u, v))

# 巡回セールスマン問題を解く
tsp = list(nx.algorithms.approximation.traveling_salesman_problem(G))

# 解を表示
print("最短距離の順序：", tsp)
print("最短距離：", sum(distance(u, v) for u, v in zip(tsp, tsp[1:]+tsp[:1])))

# グラフを可視化
pos = positions
nx.draw(G, pos=pos, with_labels=True)
nx.draw_networkx_edges(G, pos=pos, edgelist=[(u, v) for u, v in zip(tsp, tsp[1:]+tsp[:1])], edge_color='r')
plt.show()

このコードでは、5つの都市の座標を定義し、距離を計算する関数を定義しています。

その後、座標をノードとし、距離をエッジとしたグラフを作成します。

nx.algorithms.approximation.traveling_salesman_problem関数を使用して、巡回セールスマン問題を解きます。

解は、最短距離の順序として返されます。

最後に、解を表示しグラフを可視化しています。

[実行結果]

全点対最短経路問題

全点対最短経路問題（All-Pairs Shortest Path Problem）は、グラフ理論の基本的な問題の一つで、ある重みつきグラフにおいて、すべての頂点の間の最短経路を求める問題です。

具体的には、グラフの任意の2つの頂点u, vに対して、uからvへの最短経路の重みを求めます。

この問題は、ワーシャル-フロイド法やダイクストラ法などのアルゴリズムを使用して解決できます。

全点対最短経路問題は、多くの実世界の問題に適用されます。

例えば、都市間の移動にかかる最小コストを求める問題や、ネットワークの最小距離を求める問題などがあります。

また、グラフが静的である場合には、問題の解決に多項式時間がかかりますが、グラフが動的である場合には、解決が困難であることが知られています。

例題

すべての頂点のペアの最短経路を求めてみます。

NetworkXは、ワーシャル-フロイド法を実装した関数 shortest_pathを提供しています。

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

import networkx as nx

# 無向グラフの定義
G = nx.Graph()

# 頂点の追加
G.add_nodes_from([1, 2, 3, 4, 5])

# 辺の追加
G.add_edge(1, 2, weight=5)
G.add_edge(1, 3, weight=2)
G.add_edge(1, 4, weight=6)
G.add_edge(2, 3, weight=3)
G.add_edge(2, 4, weight=2)
G.add_edge(3, 4, weight=1)
G.add_edge(3, 5, weight=4)
G.add_edge(4, 5, weight=6)

# 全点対最短経路を求める
all_shortest_paths = dict(nx.shortest_path(G))

# 結果を表示する
for source in all_shortest_paths:
    for target in all_shortest_paths[source]:
        if source != target:
            print(f"{source} から {target} までの最短経路: {all_shortest_paths[source][target]}")

まず、グラフを定義します。

nx.Graph() によって空の無向グラフを定義し、add_nodes_from メソッドを使用して頂点を追加し、add_edge メソッドを使用して辺を追加しています。

また、各辺には weight 属性を設定して、重みつきグラフとして定義しています。

次に、shortest_path 関数を使用して、すべての頂点のペアの最短経路を求めます。

ただし、この方法は全点対最短経路を求めるために必要な計算量が大きくなってしまい、大きなグラフには適用しづらい場合があります。

[実行結果]

1 から 2 までの最短経路: [1, 2]
1 から 3 までの最短経路: [1, 3]
1 から 4 までの最短経路: [1, 4]
1 から 5 までの最短経路: [1, 3, 5]
2 から 1 までの最短経路: [2, 1]
2 から 3 までの最短経路: [2, 3]
2 から 4 までの最短経路: [2, 4]
2 から 5 までの最短経路: [2, 3, 5]
3 から 1 までの最短経路: [3, 1]
3 から 2 までの最短経路: [3, 2]
3 から 4 までの最短経路: [3, 4]
3 から 5 までの最短経路: [3, 5]
4 から 1 までの最短経路: [4, 1]
4 から 2 までの最短経路: [4, 2]
4 から 3 までの最短経路: [4, 3]
4 から 5 までの最短経路: [4, 5]
5 から 3 までの最短経路: [5, 3]
5 から 4 までの最短経路: [5, 4]
5 から 1 までの最短経路: [5, 3, 1]
5 から 2 までの最短経路: [5, 3, 2]

すべての頂点のペアの最短経路を求めることができました。

問題

ある男女10人のグループがあり、男女間には好意があると仮定します。

このグループを、男女のペアを作ることができるようにマッチングさせることを考えます。

ただし、それぞれの男性・女性が同時に複数の異性とのペアを持てないものとします。

以下の男女間の好意度が与えられています。

この好意度を最大化するように、マッチングを決定してください。

解法

NetworkXライブラリを使ってグラフを作成します。

このグラフのノードは男女それぞれの番号で表されます。

辺には好意度に対応する重みが付いています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import networkx as nx

# グラフを定義する
G = nx.Graph()
G.add_nodes_from(["F1", "F2", "F3", "F4", "F5"], bipartite=0)
G.add_nodes_from(["M1", "M2", "M3", "M4", "M5"], bipartite=1)
G.add_weighted_edges_from([
    ("F1", "M1", 70), ("F1", "M2", 90), ("F1", "M3", 80), ("F1", "M4", 80), ("F1", "M5", 70),
    ("F2", "M1", 60), ("F2", "M2", 10), ("F2", "M3", 80), ("F2", "M4", 70), ("F2", "M5", 60),
    ("F3", "M1", 70), ("F3", "M2", 70), ("F3", "M3", 100), ("F3", "M4", 70), ("F3", "M5", 60),
    ("F4", "M1", 80), ("F4", "M2", 80), ("F4", "M3", 80), ("F4", "M4", 50), ("F4", "M5", 60),
    ("F5", "M1", 90), ("F5", "M2", 90), ("F5", "M3", 90), ("F5", "M4", 90), ("F5", "M5", 30)
])

# 最大重みマッチングを求める
max_matching = nx.max_weight_matching(G)
print(max_matching)

NetworkXライブラリを用いて、与えられたグラフの最大重みマッチングを求めています。

まず、nx.Graph()を使って空のグラフを定義し、Gという変数に格納しています。

次に、add_nodes_fromを使って、グラフのノードを追加しています。

ここでは、[“F1”, “F2”, “F3”, “F4”, “F5”]と[“M1”, “M2”, “M3”, “M4”, “M5”]という2つの集合を作り、それぞれに対してbipartite=0とbipartite=1という属性を付与しています。

これによって、グラフが二部グラフであることを示しています。

その後、add_weighted_edges_fromを使って、グラフの辺を追加しています。

ここでは、各辺に対して、始点、終点、重みを設定しています。

最後に、nx.max_weight_matchingを使って、最大重みマッチングを求め、結果をmax_matchingに格納しています。

[実行結果]

{('F4', 'M1'), ('F1', 'M2'), ('M4', 'F5'), ('M3', 'F3'), ('F2', 'M5')}

最大重みマッチングによって、以上のような男女のペアを作ることができました。